Fuzzy shlukování: algoritmus fuzzy c-means a body mezi shluky

Nechť d ≥ 1 a n ≥ 1 jsou přirozená čísla, x₁, …, x_n ∈ ℝ^d body a c ∈ ℕ, 1 ≤ c ≤ n, počet shluků. Přiřazení je zobrazení shluk : {1, …, n} → {1, …, c}, které bodu x_i přiřadí číslo jeho shluku. Pro středy v₁, …, v_c ∈ ℝ^d a přiřazení shluk je cena

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

kde ‖·‖ je euklidovská vzdálenost (další definice). Úloha k-means je najít středy a přiřazení, pro které je J nejmenší možné.

Lloydův algoritmus (přibližné řešení úlohy k-means). Vstup: body x₁, …, x_n ∈ ℝ^d a počet shluků c. Výstup: středy v₁, …, v_c a přiřazení shluk. Kroky:

1. Za počáteční středy zvol c navzájem různých bodů z x₁, …, x_n (náhodně).
2. Přiřazení: pro každé i = 1, …, n zvol shluk(i) ∈ argmin_{j ∈ {1, …, c}} ‖x_i − v_j‖²; je-li nejbližších středů víc a je mezi nimi dosavadní střed bodu, ponech bod v jeho shluku.
3. Zastavení: pokud se přiřazení oproti předchozímu průchodu nezměnilo, skonči a vrať středy a přiřazení.
4. Středy: pro každé j = 1, …, c označ S_j = {i : shluk(i) = j} a je-li S_j ≠ ∅, polož v_j = 1/|S_j| ∑_{i ∈ Sj} x_i (průměr bodů shluku; prázdný shluk střed nemění).
5. Pokračuj krokem 2.

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

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

V rovině (d = 2) je to obyčejná délka úsečky, třeba od bodu M1 = (4,5; 2,5) ke středu shluku A (1,73; 2,31), jak ho níže najde fuzzy c-means: √2,77² + 0,19² ≈ 2,78. Shlukování pracuje se čtvercem ‖·‖² — odpadne odmocnina a vzdálené body se trestají víc.

Nechť x₁, …, x_n ∈ ℝ^d, 1 ≤ c ≤ n a Lloydův algoritmus běží podle definice výše (včetně pravidla, že při shodné vzdálenosti zůstane bod ve svém shluku). Pak

1. žádný krok přiřazení ani krok středů nezvětší hodnotu J;
2. algoritmus skončí po konečně mnoha průchodech.

Důkaz: Přiřazení: každý člen ‖x_i − v_shluk(i)‖² se nahradí nejmenším ze všech ‖x_i − v_j‖², takže se nezvětší. Středy: pro neprázdnou množinu indexů S jednoho shluku s průměrem x̄ = 1/|S| ∑_i∈S x_i a libovolné v ∈ ℝ^d platí rozklad

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

(smíšený člen 2 ∑ (x_i − x̄) · (x̄ − v) je nulový, protože ∑ (x_i − x̄) = 0). Součet je tedy nejmenší pro v = x̄. Rozkladů n bodů do c shluků je konečně mnoho a J při každé změně přiřazení ostře klesne (při shodné vzdálenosti necháme bod v jeho shluku), takže se žádný rozklad nezopakuje. ∎

Věta neříká nic o tom, zda nalezený rozklad je ten s nejmenším J — jen že algoritmus nebude cyklit.

Nechť x₁, …, x_n ∈ ℝ^d jsou body, c ∈ ℕ, 2 ≤ c < n, počet shluků a m ∈ ℝ, m > 1, fuzzifikátor. Matice příslušností je matice U = (u_ij) typu n × c (i = 1, …, n čísluje body, j = 1, …, c shluky), která splňuje

1. u_ij ∈ [0, 1] pro všechna i, j;
2. ∑_j=1^c u_ij = 1 pro každé i — každý bod rozdělí celkovou příslušnost 1 mezi shluky;
3. 0 < ∑_i=1ⁿ u_ij < n pro každé j — žádný shluk není prázdný a žádný nepohltí všechny body úplně.

Pro matici příslušností U a středy 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 najít U a V s nejmenší cenou J_m a tento algoritmus pro její přibližné řešení. Vstup: body, c, m, přesnost ε > 0 a nejvyšší počet iterací. Výstup: U a V. Kroky:

1. Zvol počáteční středy v₁, …, v_c (např. c různých náhodných bodů).
2. Příslušnosti: pro všechna i, j spočítej d_ij = ‖x_i − v_j‖ (předpokládáme d_ij > 0) a u_ij = 1/∑_k=1^c (d_ij/d_ik)^2/(m−1).
3. Zastavení: pokud se od předchozího průchodu žádné u_ij nezměnilo o ε nebo víc, nebo byl vyčerpán počet iterací, skonči (po prvním průchodu se nekončí) a vrať U a V.
4. Středy: pro každé j = 1, …, c polož v_j = ∑_i=1ⁿ u_ij^m x_i/∑_i=1ⁿ u_ij^m a pokračuj krokem 2.

Oba výpočetní kroky plynou z podmínek optimality (věta níže): každý minimalizuje J_m při pevné druhé skupině proměnných.

Nechť x₁, …, x_n ∈ ℝ^d, c a m > 1 jsou jako v definici fuzzy c-means. Pak:

1. Pro pevné středy v₁, …, v_c, pro které jsou všechny vzdálenosti d_ij = ‖x_i − v_j‖ kladné, nabývá J_m na množině matic s u_ij ≥ 0 a ∑_j u_ij = 1 minima právě pro u_ij = 1/∑_k=1^c (d_ij/d_ik)^2/(m−1).
2. Pro pevnou matici U, ve které ∑_i u_ij^m > 0 pro každé j, nabývá J_m minima přes v₁, …, v_c ∈ ℝ^d právě pro v_j = ∑_i u_ij^m x_i/∑_i u_ij^m.

Důkaz. Příslušnosti při pevných středech. J_m je součet přes body a podmínky se týkají vždy jednoho řádku U, takže stačí pro jeden bod i minimalizovat ∑_j u_ij^m d_ij² za podmínky ∑_j u_ij = 1. Lagrangeova funkce je L = ∑_j u_ij^m d_ij² − λ (∑_j u_ij − 1). Z ∂L/∂u_ij = m u_ij^m−1 d_ij² − λ = 0 plyne u_ij = (λ/m)^1/(m−1) · d_ij^−2/(m−1). Dosazením do podmínky součtu se neznámá λ vykrátí a zbude

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

Vyšla kladná čísla, takže podmínku u_ij ≥ 0 není třeba hlídat zvlášť. Funkce u ↦ u^m d² je pro m > 1 a d > 0 na [0, 1] ostře konvexní, takže tento jediný stacionární bod je minimum. (Leží-li bod přesně ve středu, d_ij = 0, dostane k tomu shluku příslušnost 1; naše implementace to řeší tak, že vzdálenost nikdy neklesne pod 10⁻¹².)

Středy při pevných příslušnostech. J_m je ve v_j konvexní kvadratická funkce (ostře konvexní, protože ∑_i u_ij^m > 0) a ∂J_m/∂v_j = −2 ∑_i u_ij^m (x_i − v_j) = 0 dává v_j = ∑_i u_ij^m x_i/∑_i u_ij^m. ∎

Každý krok tedy J_m při pevné druhé skupině proměnných minimalizuje a nemůže ho zvětšit — stejný argument jako u k-means. Bezdek a kol. (1987, oprava původní věty Bezdeka z roku 1980) ukázali, že posloupnost má hromadné body ve stacionárních bodech J_m (ne nutně v globálním minimu).

Středy po devíti iteracích: A ≈ (1,73; 2,31), B ≈ (7,12; 2,87), C ≈ (4,51; 7,11). Pro m = 2 stačí převrácené čtverce vzdáleností (barvy podle zjednodušeného vzorce pro m = 2 v popisku výše):

M1 je ke středům A a B skoro stejně daleko (7,72 proti 7,03), a proto se mezi ně dělí téměř napůl; C je třikrát dál (ve čtverci), a tak dostane jen zbytek.

Nechť n ≥ 1, c ≥ 2 a U = (u_ij) je matice typu n × c s u_ij ∈ [0, 1] a ∑_j=1^c u_ij = 1 pro každé i (matice pří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, přičemž

1. PC(U) = 1, právě když je rozklad ostrý: v každém řádku je jedno u_ij = 1 a ostatní 0;
2. PC(U) = 1/c, právě když u_ij = 1/c pro všechna i, j — každý bod patří do všech shluků stejně.

(Pro každý řádek je ∑_j u_ij² ≤ ∑_j u_ij = 1 s rovností jen pro hodnoty 0 a 1, a podle Cauchyovy–Schwarzovy nerovnosti ∑_j u_ij² ≥ 1/c (∑_j u_ij)² = 1/c s rovností jen pro stejné hodnoty.)

Bod má ke středu 1 vzdálenost 1 a ke středu 2 vzdálenost 2. Ve vzorci pro příslušnost je člen k = 1 roven 1 a člen k = 2 má poměr 1/2, takže u₁ = 1/1 + (1/2)^2/(m−1) (barvy podle vzorce pro u_ij výše):

• m = 1,2: exponent 10, u₁ = 1/1 + 1/1 024 ≈ 0,999 — prakticky ostré přiřazení,
• 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.

Obecně: pro m → 1⁺ jde exponent 2/m − 1 do nekonečna, poměry d_ij/d_ik < 1 jdou k nule a ty > 1 do nekonečna, takže nejbližší střed dostane 1 a ostatní 0 (k-means). Pro m → ∞ jde exponent k nule, všech c členů součtu jde k 1 a u_ij → 1/c.

Nechť x₁, …, x_n ∈ ℝ^d, c ≥ 2, m > 1, U = (u_ij) matice příslušností typu n × c a v₁, …, v_c ∈ ℝ^d navzájem různé středy (typicky výsledek fuzzy c-means). Xieův–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‖².

Jmenovatel je kladný, protože středy jsou různé. Xie a Beni (1991) index zavedli s exponentem 2 (tj. pro m = 2); s obecným m se běžně používá ve stejném tvaru. Při porovnání rozkladů je lepší ten s menším XB.

Po skončení algoritmu je J₂ ≈ 166,73. Čtverce vzdáleností středů: A–B ≈ 29,4, A–C ≈ 30,8, B–C ≈ 24,79 (nejbližší jsou B a C). Pro n = 126 bodů (barvy podle vzorce výše):

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

Čtverce vzdáleností ke středům: A ≈ 54,07, B ≈ 91,88, C ≈ 24,29. I od nejbližšího středu C je tedy 4,9 daleko — přes šestinásobek směrodatné odchylky 0,8, se kterou jsou body shluků rozházené kolem středů. Podle vzorce pro m = 2 (barvy podle popisku u vzorce pro u_ij) dají převrácené hodnoty 1/54,07 ≈ 0,0185, 1/91,88 ≈ 0,0109 a 1/24,29 ≈ 0,0412 součet 0,0706 a pří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í jen poměry vzdáleností, ne jejich velikost: čím dál by bod ležel, tím víc by se poměry blížily 1 a příslušnosti 1/3 — ale k nule by nešly nikdy.

Nechť x₁, …, x_n ∈ ℝ^d, c ≥ 1, m > 1, v₁, …, v_c ∈ ℝ^d středy, d_ij = ‖x_i − v_j‖ a η₁, …, η_c > 0 předem zvolené parametry (obvykle odhadnuté z výsledku fuzzy c-means). Posibilistické c-means hledá matici U = (u_ij) typu n × c s u_ij ∈ [0, 1] — bez podmínky ∑_j u_ij = 1 — a středy, které 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ání triviálnímu řešení U = 0. Při pevných středech je minimum v

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

středy se počítají stejně jako u fuzzy c-means. η_j je „poloměr“ shluku j: bod ve vzdálenosti d² = η_j má příslušnost 1/2, pro m = 2 bod s d² = 9η_j jen 1/1 + 9 = 0,1. Příslušnost teď závisí na vzdálenosti k jedinému středu, ne na poměru k ostatním — odlehlý bod dostane malé hodnoty všude.