Fuzzy zhlukovanie: algoritmus fuzzy c-means a body medzi zhlukmi

Nech d ≥ 1 a n ≥ 1 sú prirodzené čísla, x₁, …, x_n ∈ ℝ^d body a c ∈ ℕ, 1 ≤ c ≤ n, počet zhlukov. Priradenie je zobrazenie shluk : {1, …, n} → {1, …, c}, ktoré bodu x_i priradí číslo jeho zhluku. Pre stredy v₁, …, v_c ∈ ℝ^d a priradenie shluk je cena

J(v₁, …, v_c, shluk) = ∑_i=1ⁿ ‖x_i − v_shluk(i)‖²,

kde ‖·‖ je euklidovská vzdialenosť (ďalšia definícia). Úloha k-means je nájsť stredy a priradenie, pre ktoré je J najmenšie možné.

Lloydov algoritmus (približné riešenie úlohy k-means). Vstup: body x₁, …, x_n ∈ ℝ^d a počet zhlukov c. Výstup: stredy v₁, …, v_c a priradenie shluk. Kroky:

1. Za počiatočné stredy zvoľ c navzájom rôznych bodov z x₁, …, x_n (náhodne).
2. Priradenie: pre každé i = 1, …, n zvoľ shluk(i) ∈ argmin_{j ∈ {1, …, c}} ‖x_i − v_j‖²; ak je najbližších stredov viac a je medzi nimi doterajší stred bodu, ponechaj bod v jeho zhluku.
3. Zastavenie: ak sa priradenie oproti predchádzajúcemu prechodu nezmenilo, skonči a vráť stredy a priradenie.
4. Stredy: pre každé j = 1, …, c označ S_j = {i : shluk(i) = j} a ak S_j ≠ ∅, polož v_j = 1/|S_j| ∑_{i ∈ Sj} x_i (priemer bodov zhluku; prázdny zhluk stred nemení).
5. Pokračuj krokom 2.

Nech d ≥ 1 a x = (x₁, …, x_d), v = (v₁, …, v_d) ∈ ℝ^d. Euklidovská vzdialenosť bodov x a v je nezáporné číslo

‖x − v‖ = √∑_r=1^d (x_r − v_r)².

V rovine (d = 2) je to obyčajná dĺžka úsečky, napríklad od bodu M1 = (4,5; 2,5) k stredu zhluku A (1,73; 2,31), ako ho nižšie nájde fuzzy c-means: √2,77² + 0,19² ≈ 2,78. Zhlukovanie pracuje so štvorcom ‖·‖² — odpadne odmocnina a vzdialené body sa trestajú viac.

Nech x₁, …, x_n ∈ ℝ^d, 1 ≤ c ≤ n a Lloydov algoritmus beží podľa definície vyššie (vrátane pravidla, že pri rovnakej vzdialenosti zostane bod vo svojom zhluku). Potom

1. žiadny krok priradenia ani krok stredov nezväčší hodnotu J;
2. algoritmus skončí po konečne mnohých prechodoch.

Dôkaz: Priradenie: každý člen ‖x_i − v_shluk(i)‖² sa nahradí najmenším zo všetkých ‖x_i − v_j‖², takže sa nezväčší. Stredy: pre neprázdnu množinu indexov S jedného zhluku s priemerom x̄ = 1/|S| ∑_i∈S x_i a ľubovoľné v ∈ ℝ^d platí rozklad

∑_i∈S ‖x_i − v‖² = ∑_i∈S ‖x_i − x̄‖² + |S| · ‖x̄ − v‖²

(zmiešaný člen 2 ∑ (x_i − x̄) · (x̄ − v) je nulový, pretože ∑ (x_i − x̄) = 0). Súčet je teda najmenší pre v = x̄. Rozkladov n bodov do c zhlukov je konečne veľa a J pri každej zmene priradenia ostro klesne (pri rovnakej vzdialenosti necháme bod v jeho zhluku), takže sa žiadny rozklad nezopakuje. ∎

Veta nehovorí nič o tom, či nájdený rozklad je ten s najmenším J — len že algoritmus nebude cykliť.

Nech x₁, …, x_n ∈ ℝ^d sú body, c ∈ ℕ, 2 ≤ c < n, počet zhlukov a m ∈ ℝ, m > 1, fuzzifikátor. Matica príslušností je matica U = (u_ij) typu n × c (i = 1, …, n čísluje body, j = 1, …, c zhluky), ktorá spĺňa

1. u_ij ∈ [0, 1] pre všetky i, j;
2. ∑_j=1^c u_ij = 1 pre každé i — každý bod rozdelí celkovú príslušnosť 1 medzi zhluky;
3. 0 < ∑_i=1ⁿ u_ij < n pre každé j — žiadny zhluk nie je prázdny a žiadny nepohltí všetky body úplne.

Pre maticu príslušností U a stredy V = (v₁, …, v_c) ∈ (ℝ^d)^c je cena

J_m(U, V) = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖².

Fuzzy c-means je úloha nájsť U a V s najmenšou cenou J_m a tento algoritmus na jej približné riešenie. Vstup: body, c, m, presnosť ε > 0 a najvyšší počet iterácií. Výstup: U a V. Kroky:

1. Zvoľ počiatočné stredy v₁, …, v_c (napr. c rôznych náhodných bodov).
2. Príslušnosti: pre všetky i, j vypočítaj d_ij = ‖x_i − v_j‖ (predpokladáme d_ij > 0) a u_ij = 1/∑_k=1^c (d_ij/d_ik)^2/(m−1).
3. Zastavenie: ak sa od predchádzajúceho prechodu žiadne u_ij nezmenilo o ε alebo viac, alebo bol vyčerpaný počet iterácií, skonči (po prvom prechode sa nekončí) a vráť U a V.
4. Stredy: pre každé j = 1, …, c polož v_j = ∑_i=1ⁿ u_ij^m x_i/∑_i=1ⁿ u_ij^m a pokračuj krokom 2.

Oba výpočtové kroky vyplývajú z podmienok optimality (veta nižšie): každý minimalizuje J_m pri pevnej druhej skupine premenných.

Nech x₁, …, x_n ∈ ℝ^d, c a m > 1 sú ako v definícii fuzzy c-means. Potom:

1. Pre pevné stredy v₁, …, v_c, pre ktoré sú všetky vzdialenosti d_ij = ‖x_i − v_j‖ kladné, nadobúda J_m na množine matíc s u_ij ≥ 0 a ∑_j u_ij = 1 minimum práve pre u_ij = 1/∑_k=1^c (d_ij/d_ik)^2/(m−1).
2. Pre pevnú maticu U, v ktorej ∑_i u_ij^m > 0 pre každé j, nadobúda J_m minimum cez v₁, …, v_c ∈ ℝ^d práve pre v_j = ∑_i u_ij^m x_i/∑_i u_ij^m.

Dôkaz. Príslušnosti pri pevných stredoch. J_m je súčet cez body a podmienky sa týkajú vždy jedného riadka U, takže stačí pre jeden bod i minimalizovať ∑_j u_ij^m d_ij² za podmienky ∑_j u_ij = 1. Lagrangeova funkcia je L = ∑_j u_ij^m d_ij² − λ (∑_j u_ij − 1). Z ∂L/∂u_ij = m u_ij^m−1 d_ij² − λ = 0 vyplýva u_ij = (λ/m)^1/(m−1) · d_ij^−2/(m−1). Dosadením do podmienky súčtu sa neznáma λ vykráti a zostane

u_ij = d_ij^−2/(m−1)/∑_k d_ik^−2/(m−1) = 1/∑_k (d_ij/d_ik)^2/(m−1).

Vyšli kladné čísla, takže podmienku u_ij ≥ 0 netreba strážiť zvlášť. Funkcia u ↦ u^m d² je pre m > 1 a d > 0 na [0, 1] ostro konvexná, takže tento jediný stacionárny bod je minimum. (Ak leží bod presne v strede, d_ij = 0, dostane k tomu zhluku príslušnosť 1; naša implementácia to rieši tak, že vzdialenosť nikdy neklesne pod 10⁻¹².)

Stredy pri pevných príslušnostiach. J_m je vo v_j konvexná kvadratická funkcia (ostro konvexná, pretože ∑_i u_ij^m > 0) a ∂J_m/∂v_j = −2 ∑_i u_ij^m (x_i − v_j) = 0 dáva v_j = ∑_i u_ij^m x_i/∑_i u_ij^m. ∎

Každý krok teda J_m pri pevnej druhej skupine premenných minimalizuje a nemôže ho zväčšiť — rovnaký argument ako pri k-means. Bezdek a kol. (1987, oprava pôvodnej Bezdekovej vety z roku 1980) ukázali, že postupnosť má hromadné body v stacionárnych bodoch J_m (nie nutne v globálnom minime).

Stredy po deviatich iteráciách: A ≈ (1,73; 2,31), B ≈ (7,12; 2,87), C ≈ (4,51; 7,11). Pre m = 2 stačia prevrátené štvorce vzdialeností (farby podľa zjednodušeného vzorca pre m = 2 v popise vyššie):

M1 je od stredov A a B takmer rovnako ďaleko (7,72 oproti 7,03), a preto sa medzi ne delí takmer napoly; C je trikrát ďalej (v štvorci), a tak dostane len zvyšok.

Nech n ≥ 1, c ≥ 2 a U = (u_ij) je matica typu n × c s u_ij ∈ [0, 1] a ∑_j=1^c u_ij = 1 pre každé i (matica príslušností). Koeficient rozkladu (partition coefficient) je číslo

PC(U) = 1/n ∑_i=1ⁿ ∑_j=1^c u_ij².

Vždy platí 1/c ≤ PC(U) ≤ 1, pričom

1. PC(U) = 1 práve vtedy, keď je rozklad ostrý: v každom riadku je jedno u_ij = 1 a ostatné 0;
2. PC(U) = 1/c práve vtedy, keď u_ij = 1/c pre všetky i, j — každý bod patrí do všetkých zhlukov rovnako.

(Pre každý riadok je ∑_j u_ij² ≤ ∑_j u_ij = 1 s rovnosťou len pre hodnoty 0 a 1, a podľa Cauchyho–Schwarzovej nerovnosti ∑_j u_ij² ≥ 1/c (∑_j u_ij)² = 1/c s rovnosťou len pre rovnaké hodnoty.)

Bod má k stredu 1 vzdialenosť 1 a k stredu 2 vzdialenosť 2. Vo vzorci pre príslušnosť je člen k = 1 rovný 1 a člen k = 2 má pomer 1/2, takže u₁ = 1/1 + (1/2)^2/(m−1) (farby podľa vzorca pre u_ij vyššie):

• m = 1,2: exponent 10, u₁ = 1/1 + 1/1 024 ≈ 0,999 — prakticky ostré priradenie,
• m = 2: exponent 2, u₁ = 1/1 + 1/4 = 0,8,
• m = 5: exponent 0,5, u₁ = 1/1 + 0,707 ≈ 0,586,
• m → ∞: exponent → 0, (1/2)⁰ = 1 a u₁ → 1/2.

Všeobecne: pre m → 1⁺ ide exponent 2/m − 1 do nekonečna, pomery d_ij/d_ik < 1 idú k nule a tie > 1 do nekonečna, takže najbližší stred dostane 1 a ostatné 0 (k-means). Pre m → ∞ ide exponent k nule, všetkých c členov súčtu ide k 1 a u_ij → 1/c.

Nech x₁, …, x_n ∈ ℝ^d, c ≥ 2, m > 1, U = (u_ij) matica príslušností typu n × c a v₁, …, v_c ∈ ℝ^d navzájom rôzne stredy (typicky výsledok fuzzy c-means). Xieho–Beniho index je číslo

XB(U, V) = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖²/n · min_{j ≠ k} ‖v_j − v_k‖².

Menovateľ je kladný, pretože stredy sú rôzne. Xie a Beni (1991) index zaviedli s exponentom 2 (t. j. pre m = 2); so všeobecným m sa bežne používa v rovnakom tvare. Pri porovnaní rozkladov je lepší ten s menším XB.

Po skončení algoritmu je J₂ ≈ 166,73. Štvorce vzdialeností stredov: A–B ≈ 29,4, A–C ≈ 30,8, B–C ≈ 24,79 (najbližšie sú B a C). Pre n = 126 bodov (farby podľa vzorca vyššie):

XB = 166,73/126 · 24,79 = 166,73/3 124 ≈ 0,053.

Štvorce vzdialeností k stredom: A ≈ 54,07, B ≈ 91,88, C ≈ 24,29. Aj od najbližšieho stredu C je teda 4,9 ďaleko — viac než šesťnásobok smerodajnej odchýlky 0,8, s ktorou sú body zhlukov rozhádzané okolo stredov. Podľa vzorca pre m = 2 (farby podľa popisu pri vzorci pre u_ij) dajú prevrátené hodnoty 1/54,07 ≈ 0,0185, 1/91,88 ≈ 0,0109 a 1/24,29 ≈ 0,0412 súčet 0,0706 a príslušnosti

u_A = 0,0185/0,0706 ≈ 0,26,   u_B = 0,0109/0,0706 ≈ 0,15,   u_C = 0,0412/0,0706 ≈ 0,58.

Vzorec vidí len pomery vzdialeností, nie ich veľkosť: čím ďalej by bod ležal, tým viac by sa pomery blížili 1 a príslušnosti 1/3 — ale k nule by nešli nikdy.

Nech x₁, …, x_n ∈ ℝ^d, c ≥ 1, m > 1, v₁, …, v_c ∈ ℝ^d stredy, d_ij = ‖x_i − v_j‖ a η₁, …, η_c > 0 vopred zvolené parametre (obvykle odhadnuté z výsledku fuzzy c-means). Posibilistické c-means hľadá maticu U = (u_ij) typu n × c s u_ij ∈ [0, 1] — bez podmienky ∑_j u_ij = 1 — a stredy, ktoré minimalizujú cenu

J(U, V) = ∑_i=1ⁿ ∑_j=1^c u_ij^m d_ij² + ∑_j=1^c η_j ∑_i=1ⁿ (1 − u_ij)^m.

Druhý člen bráni triviálnemu riešeniu U = 0. Pri pevných stredoch je minimum v

u_ij = 1/1 + (d_ij²/η_j)^1/(m−1),

stredy sa počítajú rovnako ako pri fuzzy c-means. η_j je „polomer“ zhluku j: bod vo vzdialenosti d² = η_j má príslušnosť 1/2, pre m = 2 bod s d² = 9η_j len 1/1 + 9 = 0,1. Príslušnosť teraz závisí od vzdialenosti k jedinému stredu, nie od pomeru k ostatným — odľahlý bod dostane malé hodnoty všade.