Folien zur Vektorquantisierung

Kohonen Lernalgorithmus
Input: X = {x1 , . . . , xn } ⊂ Rp
1. Wähle r, s ∈ N, eine Clusterzahl k = rs ∈ N, eine Lernrate lt > 0, eine Nachbarschaftsfunktion Nt , ferner N und ǫ > 0
2. Initialisiere Prototypen c1, . . . , ck ∈ Rp (k × p Matrix C )
3. Jeder Prototypen ci auf eine Gitterposition gi ∈ {1, . . . , r} × {1, . . . , s}.
4. repeat
Wähle x ∈ X
j ∗ = argminikx − ci k (winner detection)
for j = 1, . . . , n
cj = cj + lN (j, j ∗ )(x − cj ) (update)
5. until k∆Ck < ǫ über N Punktpräsentationen
Strey/Schwenker Praktikum NI1
1
Fuzzy ART-Map
Input: X = {x1 , . . . , xn } ⊂ Rp
1. Wähle k ∈ N, Lernrate β ∈ (0, 1), Vigilanzparameter ̺ ∈ (0, 1) und α > 0.
2. Berechne minj und maxj für j = 1, 2, . . . , p und transformiere die Inputs gemäß xµj :=
minj +(maxj −xµj)/(maxj − minj ).
3. Komplementkodierung der Inputs: xµ := (xµ , 1 − xµ ) für alle µ (gibt transformierte
MengeX ′)
4. Setze ci = 1 für alle i = 1, . . . , k.
5. WHILE noch ein Muster x vorhanden DO
Wähle xµ und setze I := {1, . . . , k}
REPEAT
|xµ ∧cj |
∗
j = argmaxj∈I α+|c | (winner detection)
∗
j
I = I \ {j }
UNTIL I = ∅ ∨ |xµ ∧ cj ∗ | ≥ ̺|xµ|
Strey/Schwenker Praktikum NI1
2
IF (|x ∧ cj ∗ | ≥ ̺|x|) ∧ (cj ∗ 6= 1)
THEN cj ∗ = β(x ∧ cj ∗ ) + (1 − β)cj ∗
IF (|x ∧ cj ∗ | ≥ ̺|x|) ∧ (cj ∗ = 1)
THEN cj ∗ = x
6. END
Hierbei ist x ∧ y := (min{x1, y1}, . . . , min{xn, yn}) und |x| =
Strey/Schwenker Praktikum NI1
P
i xi .
3
K-Means (Batch)
Input :X = {x1 , . . . , xn } ⊂ Rp
1. Wähle Clusteranzahl k ∈ {1, . . . , n} und maximale Iterationszeit tmax.
2. Setze t := 0 und Anfangspartition C(t) := {C1 (t), . . . , Ck (t)}von X .
3. Bestimme Schwerpunkte der k Cluster Cj (t) (k-means)
X
1
cj (t) :=
xµ
|Cj (t)| xµ∈C (t)
j
4. Bestimme Minimaldistanzpartition C(t + 1) durch
Cj (t + 1) = {xµ : kxµ − cj (t)k = min kxµ − ci(t)k}
i=1,...,k
j = 1, . . . , k
(Falls das Minimum nicht eindeutig ist, wähle j zufällig.)
5. Falls t < tmax dann t := t + 1 und Goto 3.
Strey/Schwenker Praktikum NI1
4
Austauschverfahren
Input :X = {x1 , . . . , xn } ⊂ Rp
1. Wähle Clusteranzahl k mit 1 ≤ k ≤ n, maximale Iterationszeit tmax, minimale Anzahl
Datenpunkte pro Cluster nmin
2. Setze t = 0 und bestimme eine Anfangspartition von X mit |Cj (t)| > nmin.
C(t) = {C1 (t), . . . , Ck (t)}
3. Berechne die k Schwerpunkte cj (t) und Abweichungssummen
e(Cj (t)) :=
X
µ
2
kx − cj (t)k
xµ ∈Cj (t)
4. Wähle einen Index µ. Dann sei xµ ∈ Cp(t).
5. Falls Cp (t) = nmin dann Goto 10
6. Transportierte nun xµ versuchsweise die Cluster Cj (t) mit j 6= p.
Strey/Schwenker Praktikum NI1
5
7. Berechne Zielfunktionsänderung
fµ,j := DVar(C(t)) − DVar(C j (t))
Hierbei ist C j (t) die Austauschclusterung
C j (t) = {C1 (t), . . . , Cp (t) \ {xµ}, . . . , Cj (t) ∪ {xµ }, . . . , Ck (t)}
8. Bestimme die Cluster und Cq mit der Eigenschaft
fµ,q = max fµ,j
j
(Eindeutigkeit von q durch zufällige Wahl)
9. Falls fµ,q > 0, also DVar(C(t)) > DVar (C j (t)), dann ordne den Datenpunkt xµ aus dem
Cluster Cp(t) dem Cluster Cq (t) zu.
Also:
C(t + 1) = Cq (t)
und bestimme die Schwerpunkte cq (t + 1) und cp(t + 1)..
10. Falls t < tmax dann t := t + 1 und Goto 4.
Strey/Schwenker Praktikum NI1
6
Fuzzy-k-means Algorithmus
Input: X = {x1 , . . . , xn } ⊂ Rp
1. Wähle Clusterzahl k ∈ N, den Fuzzifier b > 1 und die Toleranz ǫ > 0.
2. Initialisiere die fuzzy membership matrix F gemäß Nebenbedingung.
3. repeat
cj = Pn
1
b
µ=1 fµ,j
n
X
b
µ
fµ,j x ,
µ=1
1
fµ,j =
Pk
i=1
j = 1, . . . , k
kxµ−c
2
jk
kxµ −ci k2
1 ,
b−1
µ = 1, . . . , n j = 1, . . . , k
4. until k∆F k < ǫ
Strey/Schwenker Praktikum NI1
7
K-means (inkrementell)
Input: X = {x1 , . . . , xn } ⊂ Rp
1. Wähle Clusterzahl k ∈ N, ferner N und ǫ > 0
2. Initialisiere Prototypen c1, . . . , ck ∈ Rp (k × p Matrix C ) und ni = 0.
3. repeat
Wähle x ∈ X
j = argminikx − ci k (winner detection)
nj = nj + 1
cj = cj + n1 (x − cj ) (winner update)
j
4. until k∆Ck < ǫ über N Punktpräsentationen
Strey/Schwenker Praktikum NI1
8
LVQ 1
Input: X = {(x1 , y 1 ), . . . , (xn, y n)} ⊂ Rp × Ω hierbei ist
Ω = {1, . . . , L} eine endliche Menge von L Klassen(-Labels).
1. Wähle Prototypenzahl k ∈ N, eine Lernrate lt > 0 und N . Setze t = 0.
2. Initialisiere Prototypen c1, . . . , ck ∈ Rp.
3. Bestimme für alle ci eine Klasse ωi ∈ Ω.
4. repeat
Wähle Paar (x, y) ∈ X und t = t + 1
j ∗ = argminikx − ci k (winner detection + class from nearest neighbor)
if ωj ∗ 6= y then ∆ = −1 else ∆ = 1 (correct classification result?)
cj ∗ = cj ∗ + lt ∆(x − cj ∗ ) (winner update)
5. until t ≥ N
Strey/Schwenker Praktikum NI1
9

Download Report