Fuzzy shlukování - Fuzzy clustering

Fuzzy shlukování (označovaný také jako měkké shlukování nebo měkký k-prostředek) je forma shlukování, ve kterém každý z nich datový bod může patřit do více než jednoho klastru.

Shlukování nebo shluková analýza zahrnuje přiřazení datových bodů ke klastrům tak, aby položky ve stejném klastru byly co nejpodobnější, zatímco položky patřící k různým klastrům jsou co nejvíce odlišné. Klastry jsou identifikovány pomocí opatření podobnosti. Mezi tato opatření podobnosti patří vzdálenost, konektivita a intenzita. Na základě údajů nebo aplikace lze zvolit různá opatření podobnosti.^[1]

Srovnání s tvrdým shlukováním

V nefuzzy klastrování (také známé jako tvrdé klastrování) jsou data rozdělena do samostatných klastrů, kde každý datový bod může patřit pouze přesně jednomu klastru. Ve fuzzy klastrování mohou datové body potenciálně patřit do více klastrů. Například jablko může být červené nebo zelené (tvrdé shlukování), ale jablko může být také červené A zelené (fuzzy shlukování). Zde může být jablko do určité míry červené i do určité míry zelené. Místo toho, aby jablko patřilo zelené [zelená = 1] a ne červené [červené = 0], může jablko patřit zelené [zelené = 0,5] a červené [červené = 0,5]. Tyto hodnoty jsou normalizovány mezi 0 a 1; nepředstavují však pravděpodobnosti, takže tyto dvě hodnoty není třeba sečíst až 1.

Členství

Každému z datových bodů (tagů) jsou přiřazeny stupně členství. Tyto stupně členství označují stupeň, do kterého datové body patří každému klastru. Body na okraji kupy s nižšími stupni členství tedy mohou být v klastru v menší míře než body ve středu kupy.

Fuzzy C znamená shlukování

Jedním z nejpoužívanějších algoritmů fuzzy shlukování je algoritmus Fuzzy C-means clustering (FCM).

Dějiny

Shlukování fuzzy c-means (FCM) vyvinul J.C. Dunn v roce 1973,^[2] a vylepšil J.C.Bezdek v roce 1981.^[3]

Obecný popis

Fuzzy C-means algoritmus je velmi podobný k- znamená algoritmus:

• Vyberte několik klastrů.
• Přiřaďte koeficienty náhodně každému datovému bodu za to, že jste v klastrech.
• Opakujte, dokud se algoritmus nespojí (to znamená, že změna koeficientů mezi dvěma iteracemi není větší než ${ displaystyle varepsilon}$, daný práh citlivosti):
  • Vypočítejte těžiště pro každý klastr (viz níže).
  • Pro každý datový bod spočítejte jeho koeficienty toho, že jste v klastrech.

Těžiště

Jakýkoli bod X má sadu koeficientů udávající míru bytí v kth shluk w_k(X). S fuzzy C- znamená, že těžiště shluku je průměr všech bodů vážený stupněm jejich příslušnosti ke shluku, nebo matematicky

${ displaystyle c_ {k} = {{ součet _ {x} {w_ {k} (x)} ^ {m} x} nad { sum _ {x} {w_ {k} (x)} ^ {m}}},}$

kde m je hyperparametr, který řídí, jak fuzzy bude cluster. Čím vyšší je, tím nakonec bude klastr fuzzer.

Algoritmus

Algoritmus FCM se pokouší rozdělit konečnou sbírku ${ displaystyle n}$ elementy ${ displaystyle X = { mathbf {x} _ {1}, ..., mathbf {x} _ {n} }}$ do souboru fuzzy klastrů s ohledem na dané kritérium.

Vzhledem k konečné sadě dat vrátí algoritmus seznam ${ displaystyle c}$ klastrová centra ${ displaystyle C = { mathbf {c} _ {1}, ..., mathbf {c} _ {c} }}$ a dělící matice

${ displaystyle W = w_ {i, j} v [0,1], ; i = 1, ..., n, ; j = 1, ..., c}$, kde každý prvek, ${ displaystyle w_ {ij}}$ , řekni, do jaké míry, ${ displaystyle mathbf {x} _ {i}}$, patří do klastru ${ displaystyle mathbf {c} _ {j}}$.

Cílem FCM je minimalizovat objektivní funkci:

${ displaystyle { underset {C} { operatorname {arg , min}}} sum _ {i = 1} ^ {n} sum _ {j = 1} ^ {c} w_ {ij} ^ { m} left | mathbf {x} _ {i} - mathbf {c} _ {j} right | ^ {2},}$

kde:

${ displaystyle w_ {ij} = { frac {1} { sum _ {k = 1} ^ {c} left ({ frac { left | mathbf {x} _ {i} - mathbf {c} _ {j} right |} { left | mathbf {x} _ {i} - mathbf {c} _ {k} right |}} right) ^ { frac { 2} {m-1}}}}}$

Srovnání s K-means clustering

Shlukování K-means se také pokouší minimalizovat výše uvedenou objektivní funkci. Tato metoda se liší od metody k- znamená objektivní funkci přidáním hodnot členství ${ displaystyle w_ {ij}}$ a fuzzifikátor, ${ displaystyle m v R}$ , s ${ displaystyle m geq 1}$. Fuzzifikátor ${ displaystyle m}$ určuje úroveň neurčitosti klastru. Velký ${ displaystyle m}$ má za následek menší hodnoty členství, ${ displaystyle w_ {ij}}$, a tedy fuzzerové shluky. V limitu ${ displaystyle m = 1}$, členství, ${ displaystyle w_ {ij}}$ , konvergovat na 0 nebo 1, což znamená ostré rozdělení. Při absenci experimentů nebo znalostí domény ${ displaystyle m}$ je běžně nastaven na 2. Algoritmus také minimalizuje rozdíly uvnitř klastru, ale má stejné problémy jako 'k'-means; minimum je místní minimum a výsledky závisí na počátečním výběru vah.

Související algoritmy

Fuzzy C-means (FCM) s automaticky určeným počtem klastrů by mohly zvýšit přesnost detekce.^[4] Pomocí směsi Gaussianů spolu s algoritmus maximalizace očekávání je statisticky formalizovanější metoda, která zahrnuje některé z těchto myšlenek: částečné členství ve třídách.

Příklad

Pro lepší pochopení tohoto principu je níže uveden klasický příklad jednodimenzionálních dat na ose x.

Tuto datovou sadu lze tradičně seskupit do dvou klastrů. Výběrem prahové hodnoty na ose x jsou data rozdělena do dvou klastrů. Výsledné klastry jsou označeny „A“ a „B“, jak je vidět na následujícím obrázku. Každý bod patřící k datové sadě by proto měl koeficient členství 1 nebo 0. Tento koeficient členství každého odpovídajícího datového bodu je reprezentován zahrnutím osy y.

Ve fuzzy klastrování může mít každý datový bod členství ve více klastrech. Uvolněním definice koeficientů členství od striktně 1 nebo 0 se tyto hodnoty mohou pohybovat od jakékoli hodnoty od 1 do 0. Následující obrázek ukazuje datovou sadu z předchozího shlukování, ale nyní je použito fuzzy shlukování c-means. Nejprve lze vygenerovat novou prahovou hodnotu definující dva klastry. Dále se generují nové koeficienty členství pro každý datový bod na základě centroidů klastrů a vzdálenosti od každého centroidu klastru.

Jak je vidět, prostřední datový bod patří do klastru A a klastru B. hodnota 0,3 je koeficient členství tohoto datového bodu pro klastr A.^[5]

Aplikace

Problémy shlukování mají uplatnění v povrchových vědách, biologii, medicíně, psychologii, ekonomii a mnoha dalších oborech.^[6]

Bioinformatika

V oblasti bioinformatiky se shlukování používá pro řadu aplikací. Jedno použití je jako rozpoznávání vzorů technika pro analýzu dat genové exprese z microarrays nebo jiné technologie.^[7] V tomto případě jsou geny s podobnými expresními vzory seskupeny do stejného shluku a různé shluky zobrazují odlišné, dobře oddělené vzorce exprese. Použití shlukování může poskytnout vhled do genové funkce a regulace.^[6] Protože fuzzy shlukování umožňuje genům patřit do více než jednoho shluku, umožňuje identifikaci genů, které jsou podmíněně společně regulovány nebo společně exprimovány.^[8] Například na jeden gen může působit více než jeden Transkripční faktor a jeden gen může kódovat protein, který má více než jednu funkci. Fuzzy shlukování je tedy vhodnější než tvrdé shlukování.

Analýza obrazu

Fuzzy c-means byl velmi důležitý nástroj pro zpracování obrazu při shlukování objektů v obraze. V 70. letech matematici zavedli prostorový termín do algoritmu FCM, aby zlepšili přesnost shlukování pod hlukem.^[9] Dále byly použity algoritmy FCM k rozlišení mezi různými aktivitami pomocí funkcí založených na obrazech, jako jsou Hu a Zernike Moments.^[10] Alternativně A fuzzy logika model lze popsat na fuzzy množiny které jsou definovány na třech složkách barevného prostoru HSL HSL a HSV; Cílem funkcí členství je popsat barvy podle lidské intuice identifikace barev.^[11]

Marketing

V marketingu mohou být zákazníci seskupeni do fuzzy klastrů podle jejich potřeb, výběru značky, psychografických profilů nebo jiných oblastí souvisejících s marketingem.^{[Citace je zapotřebí ]}

Příklad zpracování obrazu

Obrázek segmentovaný fuzzy shlukováním, s původní (vlevo nahoře), seskupenou (vpravo nahoře) a mapou členství (dole)

Segmentace obrazu použitím k-znamená shlukování algoritmy se již dlouho používají pro rozpoznávání vzorů, detekci objektů a lékařské zobrazování. Avšak kvůli omezením v reálném světě, jako je hluk, stínování a odchylky v kamerách, tradiční tvrdé shlukování často nedokáže spolehlivě provádět úlohy zpracování obrazu, jak je uvedeno výše.^[12] Fuzzy shlukování bylo navrženo jako vhodnější algoritmus při výkonu těchto úkolů. Je uveden obrázek v šedé stupnici, který prošel fuzzy shlukováním v Matlabu.^[13] Původní obrázek je vidět vedle seskupeného obrázku. Barvy se používají k vizuálnímu znázornění tří odlišných shluků použitých k identifikaci příslušnosti každého pixelu. Níže je uveden graf, který definuje fuzzy koeficienty členství jejich odpovídajících hodnot intenzity.

V závislosti na aplikaci, pro kterou mají být použity fuzzy shlukovací koeficienty, lze použít různé techniky předběžného zpracování RGB snímky. RGB až HCL konverze je běžnou praxí.^[14]

Viz také

• Shlukování FLAME
• Shluková analýza
• Algoritmus maximalizace očekávání (podobná, ale statisticky formalizovanější metoda)

Reference