Klastrová analýza - Cluster analysis

Klastrová analýza nebo klastrování je úkolem seskupit sadu objektů takovým způsobem, aby se objekty ve stejné skupině (nazývané klastr ) navzájem (v jistém smyslu) podobaly více než těm v jiných skupinách (klastrech). Jedná se o hlavní úkol průzkumné analýzy dat a běžnou techniku ​​pro analýzu statistických dat , která se používá v mnoha oblastech, včetně rozpoznávání vzorů , analýzy obrazu , získávání informací , bioinformatiky , komprese dat , počítačové grafiky a strojového učení .

Samotná klastrová analýza není jeden konkrétní algoritmus , ale obecný úkol, který je třeba vyřešit. Toho lze dosáhnout různými algoritmy, které se významně liší v chápání toho, co tvoří klastr a jak je efektivně najít. Mezi oblíbené pojmy klastrů patří skupiny s malými vzdálenostmi mezi členy klastru, husté oblasti datového prostoru, intervaly nebo konkrétní statistické distribuce . Klastrování lze proto formulovat jako problém víceobjektové optimalizace . Vhodný algoritmus klastrování a nastavení parametrů (včetně parametrů, jako je funkce vzdálenosti, kterou chcete použít, prahová hodnota hustoty nebo počet očekávaných klastrů) závisí na individuální sadě dat a zamýšleném použití výsledků. Klastrová analýza jako taková není automatickým úkolem, ale iteračním procesem zjišťování znalostí nebo interaktivní víceúčelové optimalizace, která zahrnuje pokus a neúspěch. Často je nutné upravit předzpracování dat a parametry modelu, dokud výsledek nedosáhne požadovaných vlastností.

Kromě termínu shlukování existuje řada termínů s podobným významem, včetně automatické klasifikace , numerické taxonomie , botryologie (z řeckého βότρυς „hroznového vína“), typologické analýzy a detekce komunity . Drobné rozdíly jsou často ve využití výsledků: zatímco při dolování dat jsou výsledné skupiny předmětem zájmu, v automatické klasifikaci je zajímavá výsledná diskriminační síla.

Clusterová analýza byla vytvořena v antropologii Driverem a Kroeberem v roce 1932 a zavedena do psychologie Josephem Zubinem v roce 1938 a Robertem Tryonem v roce 1939 a Cattell ji skvěle začala používat od roku 1943 pro klasifikaci teorie vlastností v psychologii osobnosti .

Definice

Pojem „klastr“ nelze přesně definovat, což je jeden z důvodů, proč existuje tolik klastrových algoritmů. Existuje společný jmenovatel: skupina datových objektů. Různí výzkumníci však používají různé klastrové modely a pro každý z těchto klastrových modelů lze opět zadat různé algoritmy. Pojem klastr, jak jej nacházejí různé algoritmy, se ve svých vlastnostech výrazně liší. Pochopení těchto „klastrových modelů“ je klíčem k pochopení rozdílů mezi různými algoritmy. Mezi typické klastrové modely patří:

• Konektivita modelu s: napříkladhierarchické clusteringstaví modely založené na připojení na dálku.
• Těžiště model s: napříkladk-means algoritmusreprezentuje každý shluk jediným průměrným vektorem.
• Distribuční modely s: klastry jsou modelovány pomocí statistických distribucí, jako jsouvícerozměrné normální distribucepoužívanéalgoritmem maximalizace očekávání.
• Modely hustoty s: napříkladDBSCANaOPTICSdefinují klastry jako spojené husté oblasti v datovém prostoru.
• Subprostorové modely s: vbiclusteringu(také známém jako co-clustering nebo two-mode-clustering) jsou klastry modelovány jak s členy clusteru, tak s relevantními atributy.
• Skupina Model s: některé algoritmy neposkytují rafinovaný model jejich výsledků a jen poskytnout seskupení informací.
• Grafický model s:kliku, tj. Podmnožinu uzlů vgrafutak, že každé dva uzly v podmnožině jsou spojeny hranou, lze považovat za prototypovou formu klastru. Relaxace úplného požadavku konektivity (zlomek okrajů může chybět) jsou známé jako kvazi-kliky, jako vklastrovacím algoritmu HCS.
• Modely podepsaných grafů : Každá cesta v podepsaném grafu má znak z produktu značek na okrajích. Za předpokladů teorie rovnováhy mohou hrany měnit znaménko a vést k rozdvojenému grafu. Slabší „axiom shlukovatelnosti“ (žádný cyklus nemá přesně jednu zápornou hranu) přináší výsledky s více než dvěma klastry nebo podgrafy pouze s kladnými hranami.
• Neurální modely s: nejznámějšíneuronová síťbezdozoru jesamoorganizující se mapaa tyto modely lze obvykle charakterizovat jako podobné jednomu nebo více z výše uvedených modelů a včetně modelů subprostoru, když neurální sítě implementují formu analýzyhlavních komponentneboAnalýza nezávislých komponent.

"Klastrování" je v podstatě sada takových klastrů, které obvykle obsahují všechny objekty v datové sadě. Navíc může specifikovat vzájemný vztah klastrů, například hierarchii klastrů vložených do sebe. Klastry lze zhruba rozlišit jako:

• Pevné shlukování : každý objekt patří do klastru nebo ne
• Soft clustering (také:fuzzy shlukování ): každý objekt patří do určité míry ke každému clusteru (například pravděpodobnost, že patří do clusteru)

Existují také jemnější rozlišení, například:

• Striktní dělení clusterů : každý objekt patří přesně jednomu clusteru
• Striktní dělení clusterů s odlehlými hodnotami : objekty mohou také patřit do žádného clusteru a jsou považovány zaodlehlé hodnoty
• Překrývající se klastry (také:alternativní klastrování,klastrovánívíce pohledů): objekty mohou patřit do více než jednoho klastru; obvykle zahrnující tvrdé klastry
• Hierarchické klastrování : objekty, které patří do podřízeného klastru, také patří do nadřazeného klastru
• Klastrování podprostoru : při překrývajícím se klastrování se v rámci jednoznačně definovaného podprostoru neočekává překrývání klastrů

Algoritmy

Jak je uvedeno výše, klastrové algoritmy lze kategorizovat na základě jejich clusterového modelu. Následující přehled uvede pouze nejprominentnější příklady clusterovacích algoritmů, protože existuje možná více než 100 publikovaných klastrových algoritmů. Ne všechny poskytují modely pro své klastry, a proto je nelze snadno kategorizovat. Přehled algoritmů vysvětlených ve Wikipedii lze nalézt v seznamu statistických algoritmů .

Neexistuje objektivně „správný“ shlukovací algoritmus, ale jak bylo poznamenáno, „shlukování je v oku pozorovatele“. Nejvhodnější shlukovací algoritmus pro konkrétní problém je často nutné zvolit experimentálně, pokud neexistuje matematický důvod upřednostňovat jeden klastrový model před druhým. Algoritmus, který je navržen pro jeden druh modelu, obecně selže v sadě dat, která obsahuje radikálně odlišný druh modelu. Například k-means nemůže najít nekonvexní shluky.

Klastrování založené na konektivitě (hierarchické klastrování)

Klastrování založené na konektivitě, známé také jako hierarchické klastrování , je založeno na základní myšlence, že objekty budou více souviset s blízkými objekty než s objekty vzdálenějšími. Tyto algoritmy spojují „objekty“ a vytvářejí „shluky“ na základě jejich vzdálenosti. Klastr lze do značné míry popsat maximální vzdáleností potřebnou k připojení částí klastru. Na různých vzdálenostech se vytvoří různé klastry, které lze reprezentovat pomocí dendrogramu , což vysvětluje, odkud pochází společný název „ hierarchické shlukování “: tyto algoritmy neposkytují jediné rozdělení datové sady, ale naopak poskytují rozsáhlou hierarchii klastry, které se v určitých vzdálenostech navzájem spojují. V dendrogramu osa y označuje vzdálenost, ve které se shluky slučují, zatímco objekty jsou umístěny podél osy x tak, že se klastry nemíchají.

Klastrování založené na konektivitě je celá řada metod, které se liší způsobem výpočtu vzdálenosti. Kromě obvyklého výběru funkcí vzdálenosti musí uživatel také rozhodnout o kritériu vazby (protože klastr se skládá z více objektů, existuje více kandidátů pro výpočet vzdálenosti), které má použít. Oblíbené volby jsou známé jako klastrování s jedním spojením (minimální vzdálenost objektů), úplné seskupování spojení (maximální vzdálenost objektů) a UPGMA nebo WPGMA („nevážená nebo vážená metoda párové skupiny s aritmetickým průměrem“, známá také jako průměrná vazba shlukování). Kromě toho může být hierarchické klastrování aglomerativní (počínaje jednotlivými prvky a agregující je do klastrů) nebo dělící (počínaje úplnou sadou dat a rozdělením na oddíly).

Tyto metody nevytvoří jedinečné rozdělení datové sady, ale hierarchii, ze které uživatel stále potřebuje vybrat vhodné klastry. Nejsou příliš robustní vůči odlehlým hodnotám, které se buď projeví jako další klastry, nebo dokonce způsobí sloučení jiných klastrů (známé jako „fenomén řetězení“, zejména u klastrování s jedním spojením ). V obecném případě, složitost je pro aglomerativní shlukování a pro dělící shlukování , což z nich dělá příliš pomalé pro velké soubory dat. Pro některé speciální případy jsou známy optimální efektivní metody (složitosti ): SLINK pro jednolinkové a CLINK pro klastrování úplných vazeb. V komunitě dolování dat jsou tyto metody uznávány jako teoretický základ klastrové analýzy, ale často jsou považovány za zastaralé. Poskytly však inspiraci pro mnoho pozdějších metod, jako je klastrování založené na hustotě. ${\ displaystyle {\ mathcal {O}} (n^{3})}$${\ displaystyle {\ mathcal {O}} (2^{n-1})}$${\ displaystyle {\ mathcal {O}} (n^{2})}$

• Příklady shlukování vazeb
• 

  Jednoduché propojení na Gaussových datech. U 35 klastrů se největší klastr začíná fragmentovat na menší části, zatímco předtím byl ještě připojen k druhému největšímu díky jednolinkovému efektu.

• 

  Jednoduché propojení na klastrech založených na hustotě. Extrahováno 20 klastrů, z nichž většina obsahuje jednotlivé prvky, protože spojovací klastrování nemá pojem „šum“.

Klastrování na základě těžiště

Při klastrování na základě těžiště jsou klastry reprezentovány centrálním vektorem, který nemusí být nutně členem datové sady. Když je počet klastrů stanoven na k , k -m znamená shlukování formální definici jako problém optimalizace: najděte klastrová k centra a přiřaďte objekty k nejbližšímu středovému klastru tak, aby byly minimalizovány čtvercové vzdálenosti od klastru.

Je známo, že samotný problém optimalizace je NP-tvrdý , a proto je běžným přístupem hledat pouze přibližná řešení. Obzvláště dobře známou přibližnou metodou je Lloydův algoritmus , často jen označovaný jako „ algoritmus k-means “ (ačkoli jiný název zavedl tento název ). Najde však pouze lokální optimum a běžně se spouští několikrát s různými náhodnými inicializacemi. Variace k -průměrů často zahrnují takové optimalizace, jako je výběr toho nejlepšího z více běhů, ale také omezení centroidů na členy datové sady ( k -medoids ), výběr mediánů ( k -medians clustering ), výběr počátečních center méně náhodně ( k -means ++ ) nebo umožňující fuzzy přiřazení klastru ( fuzzy c -means ).

Většina K algoritmy -means typu vyžadují počet clusterů - k - být stanoveny předem, který je považován za jeden z největších nevýhod těchto algoritmů. Algoritmy navíc upřednostňují shluky přibližně podobné velikosti, protože vždy přiřadí objekt nejbližšímu těžiště. To často vede k nesprávnému oříznutí okrajů klastrů (což není překvapující, protože algoritmus optimalizuje centra klastrů, nikoli ohraničení klastrů).

K-means má řadu zajímavých teoretických vlastností. Nejprve rozdělí datový prostor do struktury známé jako Voronoiův diagram . Za druhé, je koncepčně blízký klasifikaci nejbližšího souseda a jako takový je populární ve strojovém učení . Za třetí, lze jej považovat za variantu shlukování založeného na modelu a Lloydův algoritmus jako variantu algoritmu maximalizace očekávání pro tento model popsaný níže.

• k -znamená příklady shlukování
• 

  k -means odděluje data do Voronoiho buněk, což předpokládá stejně velké shluky (zde nedostatečné)

• 

  k -prostředky nemohou představovat shluky založené na hustotě

Problémy se shlukováním na bázi těžiště, jako jsou k -prostředky a k -medoids, jsou speciálními případy problému s nekapacitovaným metrickým umístěním zařízení , kanonickým problémem v komunitách operačního výzkumu a výpočetní geometrie. V základním problému s umístěním zařízení (jehož existuje mnoho variant, které modelují propracovanější nastavení) je úkolem najít nejlepší skladová místa, která by optimálně obsluhovala danou sadu spotřebitelů. Na „sklady“ lze nahlížet jako na klastrové těžiště a na „spotřebitelská místa“ jako na data, která mají být seskupena. To umožňuje aplikovat dobře vyvinutá algoritmická řešení z literatury o umístění zařízení na v současné době zvažovaný problém shlukování na základě těžiště.

Klastrování založené na distribuci

Model klastrování, který je nejvíce blízký statistikám, je založen na distribučních modelech . Klastry pak lze snadno definovat jako objekty patřící s největší pravděpodobností do stejné distribuce. Praktickou vlastností tohoto přístupu je, že se velmi podobá způsobu generování umělých datových sad: vzorkováním náhodných objektů z distribuce.

I když je teoretický základ těchto metod vynikající, trpí jedním klíčovým problémem známým jako přetěžování , pokud nejsou na složitost modelu kladena omezení. Složitější model bude obvykle schopen lépe vysvětlit data, což činí výběr vhodné složitosti modelu ze své podstaty obtížným.

Jedna prominentní metoda je známá jako Gaussovy modely směsí (pomocí algoritmu maximalizace očekávání ). Zde je datová sada obvykle modelována s pevným (aby se zabránilo přeplňování) počtem Gaussových distribucí, které jsou inicializovány náhodně a jejichž parametry jsou iterativně optimalizovány tak, aby lépe odpovídaly datové sadě. To bude konvergovat k místnímu optimu , takže více běhů může přinést různé výsledky. Aby se dosáhlo pevného shlukování, objekty jsou často často přiřazovány Gaussově distribuci, do které s největší pravděpodobností patří; u měkkých klastrů to není nutné.

Klastrování založené na distribuci vytváří komplexní modely pro klastry, které mohou zachytit korelaci a závislost mezi atributy. Tyto algoritmy však kladou na uživatele další zátěž: pro mnoho reálných datových sad nemusí existovat žádný výstižně definovaný matematický model (např. Za předpokladu, že Gaussova rozdělení jsou poměrně silným předpokladem pro data).

• Příklady shlukování Gaussova modelu směsi
• 

  Na Gaussově distribuovaných datech funguje EM dobře, protože používá Gaussovy k modelování klastrů

• 

  Klastry založené na hustotě nelze modelovat pomocí Gaussových distribucí

Shlukování založené na hustotě

Při klastrování na základě hustoty jsou klastry definovány jako oblasti s vyšší hustotou než zbývající část sady dat. Objekty v řídkých oblastech - které jsou nutné k oddělení klastrů - jsou obvykle považovány za hlukové a hraniční body.

Nejoblíbenější metodou shlukování na základě hustoty je DBSCAN . Na rozdíl od mnoha novějších metod nabízí dobře definovaný klastrový model nazývaný „hustota dosažitelnosti“. Podobně jako shlukování založené na propojení je založeno na spojovacích bodech v rámci určitých prahů vzdálenosti. Spojuje však pouze body, které splňují kritérium hustoty, v původní variantě definované jako minimální počet dalších objektů v tomto poloměru. Klastr se skládá ze všech objektů spojených s hustotou (které mohou na rozdíl od mnoha jiných metod tvořit shluk libovolného tvaru) plus všechny objekty, které jsou v dosahu těchto objektů. Další zajímavou vlastností DBSCAN je, že jeho složitost je poměrně nízká - vyžaduje lineární počet dotazů na rozsah v databázi - a že zjistí v podstatě stejné výsledky (je určující pro základní a hlukové body, ale ne pro hraniční body) v každém běhu, proto není nutné jej spouštět vícekrát. OPTICS je zobecněním DBSCAN, které odstraňuje potřebu zvolit vhodnou hodnotu pro parametr range a vytváří hierarchický výsledek související s klastrováním vazeb . DeLi-Clu, Density-Link-Clustering kombinuje nápady z jednolinkového klastrování a OPTICS, zcela eliminuje parametr a nabízí vylepšení výkonu oproti OPTICS pomocí indexu R-stromu . ${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon}$

Klíčovou nevýhodou DBSCAN a OPTICS je, že očekávají nějaký druh poklesu hustoty pro detekci hranic klastru. Na sadách dat, například s překrývajícími se Gaussovými distribucemi - což je běžný případ použití umělých dat - budou hranice klastrů vytvářené těmito algoritmy často vypadat libovolně, protože hustota klastru se neustále snižuje. Na datové sadě sestávající ze směsí Gaussianů jsou tyto algoritmy téměř vždy překonány metodami, jako je EM clustering, které jsou schopné přesně modelovat tento druh dat.

Mean-shift je shlukovací přístup, kdy je každý objekt přesunut do nejhustší oblasti v jeho blízkosti na základě odhadu hustoty jádra . Nakonec se objekty sbíhají k lokálním maximům hustoty. Podobně jako klastrování k-means mohou tyto „atraktory hustoty“ sloužit jako zástupci datové sady, ale posunutí průměru může detekovat shluky libovolného tvaru podobné DBSCAN. Vzhledem k nákladnému iteračnímu postupu a odhadu hustoty je průměrný posun obvykle pomalejší než DBSCAN nebo k-Means. Kromě toho je použitelnost algoritmu průměrného posunu na vícerozměrná data bráněna nehladkým chováním odhadu hustoty jádra, což má za následek přílišnou fragmentaci klastrových chvostů.

• Příklady shlukování na základě hustoty
• 

  Klastrování založené na hustotě s DBSCAN .

• 

  DBSCAN předpokládá shluky podobné hustoty a může mít problémy s oddělením blízkých klastrů

• 

  OPTICS je varianta DBSCAN, která zlepšuje zpracování klastrů s různou hustotou

Klastrování založené na mřížce

Pro vícerozměrnou sadu dat se používá technika založená na mřížce . V této technice vytvoříme strukturu mřížky a porovnání se provádí na mřížkách (také známých jako buňky). Technika založená na mřížce je rychlá a má nízkou výpočetní náročnost. Existují dva typy metod klastrování založené na mřížce: STING a CLIQUE. Kroky zahrnuté v klastrovacím algoritmu založeném na mřížce jsou:

1. Rozdělte datový prostor na konečný počet buněk.
2. Náhodně vyberte buňku 'c', kde c by nemělo být procházeno předem.
3. Vypočítejte hustotu 'c'
4. Pokud je hustota 'c' větší než prahová hustota
   1. Označit buňku 'c' jako nový klastr
   2. Vypočítejte hustotu všech sousedů 'c'
   3. Pokud je hustota sousední buňky větší než prahová hustota, přidejte buňku do klastru a opakujte kroky 4.2 a 4.3, dokud nebude soused s hustotou vyšší než prahová hustota.
5. Kroky 2, 3 a 4 opakujte, dokud neprojdou všechny buňky.
6. Stop.

Nedávný vývoj

V posledních letech bylo vynaloženo značné úsilí na zlepšení výkonu stávajících algoritmů. Mezi nimi jsou CLARANS a BIRCH . S nedávnou potřebou zpracovávat větší a větší datové sady (také známé jako big data ), ochota obchodovat sémantický význam generovaných klastrů za účelem výkonu roste. To vedlo k vývoji metod před shlukováním, jako je seskupování vrchlíků , které dokáže efektivně zpracovávat obrovské soubory dat, ale výsledné „klastry“ jsou pouze hrubým předběžným rozdělením datové sady k následné analýze oddílů stávajícími pomalejšími metodami, jako je jako k-znamená shlukování .

U vysokodimenzionálních dat mnoho stávajících metod selže kvůli kletbě dimenzionality , což činí konkrétní distanční funkce ve vysokodimenzionálních prostorech problematickými. To vedlo k novým algoritmům klastrování pro vysokodimenzionální data, která se zaměřují na klastrování subprostoru (kde se používají pouze některé atributy a klastrové modely obsahují relevantní atributy pro klastr) a korelační klastrování, které také hledá libovolně otočený („korelovaný“) podprostor klastry, které lze modelovat poskytnutím korelace jejich atributů. Příklady takových klastrových algoritmů jsou CLIQUE a SUBCLU .

Myšlenky z metod klastrování založených na hustotě (zejména rodina algoritmů DBSCAN / OPTICS ) byly přizpůsobeny klastrování subprostoru (HiSC, hierarchické klastry podprostorů a DiSH) a korelačnímu klastrování (HiCO, hierarchické korelační klastrování, 4C pomocí „korelační konektivity“ a ERiC zkoumající hierarchické korelační klastry založené na hustotě).

Bylo navrženo několik různých klastrových systémů založených na vzájemných informacích . Jednou je variace informační metriky Marina Meilă ; další poskytuje hierarchické shlukování. Pomocí genetických algoritmů lze optimalizovat širokou škálu různých fit funkcí, včetně vzájemných informací. Také šíření víry , nedávný vývoj v oblasti počítačové vědy a statistické fyziky , vedlo k vytvoření nových typů shlukovacích algoritmů.

Hodnocení a hodnocení

Vyhodnocení (neboli „validace“) výsledků klastrování je stejně obtížné jako samotné klastrování. Populární přístupy zahrnují „ interní “ hodnocení, kde je shlukování shrnuto do jednoho skóre kvality, „ externí “ hodnocení, kde je klastrování srovnáváno s existující klasifikací „základní pravdy“, „ manuální “ hodnocení odborníkem na člověka a „ nepřímý “ "Hodnocení hodnocením užitečnosti klastrování v zamýšlené aplikaci."

Opatření interního hodnocení trpí problémem, že představují funkce, které samy lze považovat za klastrový cíl. Dalo by se například seskupit data nastavená koeficientem Silhouette; kromě toho, že pro to není známý účinný algoritmus. Použitím takového interního měřítka pro hodnocení se spíše porovnává podobnost problémů s optimalizací, a ne nutně, jak užitečné je shlukování.

Externí hodnocení má podobné problémy: pokud máme takové nálepky „základní pravdy“, pak bychom nepotřebovali seskupovat; a v praktických aplikacích takové štítky obvykle nemáme. Na druhé straně popisky odrážejí pouze jedno možné rozdělení datové sady, což neznamená, že neexistuje jiné a možná ještě lepší shlukování.

Žádný z těchto přístupů tedy nemůže v konečném důsledku posoudit skutečnou kvalitu shlukování, ale to vyžaduje lidské hodnocení, které je vysoce subjektivní. Nicméně takové statistiky mohou být docela informativní při identifikaci špatných shluků, ale neměli bychom zavrhovat subjektivní lidské hodnocení.

Interní hodnocení

Když je výsledek shlukování vyhodnocen na základě dat, která byla sama seskupena, nazývá se to interní hodnocení. Tyto metody obvykle přiřazují nejlepší skóre algoritmu, který vytváří klastry s vysokou podobností v rámci klastru a nízkou podobností mezi klastry. Jednou nevýhodou používání interních kritérií při hodnocení clusteru je, že vysoké skóre na interním měřítku nemusí nutně vést k efektivním aplikacím pro získávání informací. Toto hodnocení je navíc předpojato k algoritmům, které používají stejný model clusteru. Například k-means clustering přirozeně optimalizuje vzdálenosti objektů a interní kritérium založené na vzdálenosti pravděpodobně nadhodnotí výsledné shlukování.

Opatření interního hodnocení jsou proto nejvhodnější pro získání určitého vhledu do situací, kdy jeden algoritmus funguje lépe než jiný, ale to neznamená, že jeden algoritmus produkuje více platných výsledků než jiný. Platnost měřená takovým indexem závisí na tvrzení, že tento druh struktury v datové sadě existuje. Algoritmus navržený pro nějaký druh modelů nemá šanci, pokud soubor dat obsahuje radikálně odlišnou sadu modelů nebo pokud hodnocení měří radikálně odlišné kritérium. Klastrování k-means může například najít pouze konvexní klastry a mnoho hodnotících indexů předpokládá konvexní klastry. Na datové sadě s nekonvexními klastry není použití k -průměrů ani hodnotícího kritéria, které předpokládá konvexnost, správné.

Existuje více než tucet opatření interního hodnocení, obvykle založených na intuici, že položky ve stejném klastru by měly být více podobné než položky v různých klastrech. K posouzení kvality klastrových algoritmů na základě interního kritéria lze například použít následující metody:

• Davies – Bouldinův index

Index Davies-Bouldin lze vypočítat podle následujícího vzorce:

${\ Displaystyle DB = {\ frac {1} {n}} \ sum _ {i = 1}^{n} \ max _ {j \ neq i} \ left ({\ frac {\ sigma _ {i}+ \ sigma _ {j}} {d (c_ {i}, c_ {j})}} \ vpravo)}$

kde n je počet shluků, je těžiště klastru , je průměrná vzdálenost všech prvků v klastru k těžiště a je vzdálenost mezi těžnicemi a . Protože algoritmy, které vytvářejí klastry s nízkými vzdálenostmi uvnitř klastru (vysoká podobnost mezi klastry) a vysokými vzdálenostmi mezi klastry (nízká podobnost mezi klastry), budou mít nízký Davies – Bouldinův index, shlukovací algoritmus, který vytváří kolekci klastrů s nejmenší Davies – Bouldinův index je považován za nejlepší algoritmus na základě tohoto kritéria.${\ displaystyle c_ {i}}$${\ displaystyle i}$${\ displaystyle \ sigma _ {i}}$${\ displaystyle i}$${\ displaystyle c_ {i}}$${\ Displaystyle d (c_ {i}, c_ {j})}$${\ displaystyle c_ {i}}$${\ displaystyle c_ {j}}$

• Dunnův index

Dunnův index si klade za cíl identifikovat husté a dobře oddělené klastry. Je definován jako poměr mezi minimální vzdáleností mezi klastry a maximální vzdáleností uvnitř klastru. Pro každý oddíl clusteru lze Dunnov index vypočítat podle následujícího vzorce:

${\ Displaystyle D = {\ frac {\ min _ {1 \ leq i <j \ leq n} d (i, j)} {\ max _ {1 \ leq k \ leq n} d^{\ prime} ( k)}} \ ,,}$

kde d ( i , j ) představuje vzdálenost mezi klastry i a j a d '( k ) měří vnitroklastovou vzdálenost klastru k . Vzdálenost mezi klastry d ( i , j ) mezi dvěma klastry může být libovolný počet opatření vzdálenosti, jako je vzdálenost mezi těžnicemi klastrů. Podobně může být vzdálenost d '( k ) uvnitř klastru měřena různými způsoby, jako je maximální vzdálenost mezi jakoukoli dvojicí prvků v klastru  k . Protože vnitřní kritéria hledají klastry s vysokou podobností uvnitř klastru a nízkou podobností mezi klastry, jsou žádanější algoritmy, které vytvářejí klastry s vysokým Dunnovým indexem.

• Koeficient siluety

Koeficient siluety kontrastuje průměrnou vzdálenost k prvkům ve stejném klastru s průměrnou vzdáleností k prvkům v jiných klastrech. Objekty s vysokou hodnotou siluety jsou považovány za dobře seskupené, objekty s nízkou hodnotou mohou být odlehlé. Tento index funguje dobře s k -znamená shlukování a používá se také k určení optimálního počtu klastrů.

Externí hodnocení

V externím hodnocení jsou výsledky klastrování vyhodnocovány na základě dat, která nebyla pro klastrování použita, jako jsou známé popisky tříd a externí benchmarky. Tyto referenční hodnoty se skládají ze sady předem klasifikovaných položek a tyto sady často vytvářejí (experti) lidé. Sady referenčních hodnot lze tedy považovat za zlatý standard pro hodnocení. Tyto typy metod hodnocení měří, jak blízko je klastrování k předem určeným srovnávacím třídám. Nedávno se však diskutovalo, zda je to dostačující pro skutečná data, nebo pouze pro syntetické datové sady s faktickou základní pravdou, protože třídy mohou obsahovat vnitřní strukturu, přítomné atributy nemusí umožňovat oddělení klastrů nebo třídy mohou obsahovat anomálie . Navíc z hlediska objevování znalostí nemusí být reprodukce známých znalostí nutně zamýšleným výsledkem. Ve zvláštním scénáři omezeného shlukování , kde jsou již v procesu klastrování použity meta informace (například popisky tříd), je zadržování informací pro účely hodnocení netriviální.

Řada opatření je upravena z variant používaných k vyhodnocení klasifikačních úkolů. Namísto počítání, kolikrát byla třída správně přiřazena k jednomu datovému bodu (známému jako skutečná pozitiva ), takové metriky počítání párů posuzují, zda se předpokládá, že každý pár datových bodů, který je skutečně ve stejném klastru, bude ve stejném klastr.

Stejně jako u interního hodnocení existuje několik opatření externího hodnocení, například:

• Čistota : Čistota je měřítkem rozsahu, ve kterém klastry obsahují jedinou třídu. Jeho výpočet si můžeme představit následovně: Pro každý klastr spočítejte počet datových bodů z nejběžnější třídy v uvedeném klastru. Nyní vezměte součet přes všechny klastry a vydělte celkovým počtem datových bodů. Formálně, vzhledem k nějaké sadě klastrů a nějaké sadě tříd , což jsou oba dělící datové body, lze čistotu definovat jako:${\ displaystyle M}$${\ displaystyle D}$${\ displaystyle N}$

${\ Displaystyle {\ frac {1} {N}} \ sum _ {m \ in M} \ max _ {d \ in D} {| m \ cap d |}}$

Toto opatření nepenalizuje mnoho klastrů a více klastrů usnadní produkci vysoké čistoty. Skóre čistoty 1 je vždy možné vložením každého datového bodu do vlastního clusteru. Čistota také nefunguje dobře u nevyvážených dat, kde i špatně provádějící klastrovací algoritmy poskytnou vysokou hodnotu čistoty. Pokud se například datová sada velikosti 1000 skládá ze dvou tříd, z nichž jedna obsahuje 999 bodů a druhá obsahuje 1 bod, pak každý možný oddíl bude mít čistotu alespoň 99,9%.

• Randový index

Randův index vypočítá, jak podobné jsou klastry (vrácené algoritmem klastrování) srovnávacím klasifikacím. Lze jej vypočítat pomocí následujícího vzorce:

${\ displaystyle RI = {\ frac {TP+TN} {TP+FP+FN+TN}}}$

kde je počet pravdivých pozitiv, počet skutečných negativů , počet falešných pozitiv a počet falešných negativů . Počítané instance jsou počet správných párových přiřazení. To znamená, že je počet párů bodů, které jsou seskupeny v predikované oblasti a v sekci pozemní pravdy, je počet dvojic bodů, které jsou seskupeny dohromady v predikované sekci, ale ne v oblasti pozemní pravdy atd. datový soubor je velikost N, potom .${\ displaystyle TP}$${\ displaystyle TN}$${\ displaystyle FP}$${\ displaystyle FN}$${\ displaystyle TP}$${\ displaystyle FP}$${\ displaystyle TP+TN+FP+FN = {\ binom {N} {2}}}$

Jeden problém s Randovým indexem je, že falešně pozitivní a falešně negativní mají stejnou váhu. To může být pro některé klastrové aplikace nežádoucí charakteristikou. F-opatření řeší tento problém, stejně jako náhodně korigovaný upravený Randův index .

• F-opatření

F-opatření lze použít k vyvážení příspěvku falešných negativů vážením odvolání prostřednictvím parametru . Nechť přesnost a recall (oba externí hodnotící opatření sama o sobě) je definován takto: ${\ displaystyle \ beta \ geq 0}$

${\ displaystyle P = {\ frac {TP} {TP+FP}}}$

${\ displaystyle R = {\ frac {TP} {TP+FN}}}$

kde je přesnost frekvence a je odvolání rychlost. F-opatření můžeme vypočítat pomocí následujícího vzorce: ${\ displaystyle P}$${\ displaystyle R}$

${\ displaystyle F _ {\ beta} = {\ frac {(\ beta ^{2} +1) \ cdot P \ cdot R} {\ beta ^{2} \ cdot P+R}}}$

Kdy , . Jinými slovy, odvolání nemá žádný vliv na F-opatření, když a zvyšování přiděluje rostoucí množství váhy k vyvolání v konečném F-opatření.${\ displaystyle \ beta = 0}$${\ displaystyle F_ {0} = P}$${\ displaystyle \ beta = 0}$${\ displaystyle \ beta}$

Také se nebere v úvahu a může se lišit od 0 nahoru bez svázání.${\ displaystyle TN}$

• Jaccardův index

Jaccardův index se používá ke kvantifikaci podobnosti mezi dvěma datovými sadami. Index Jaccard nabývá hodnoty mezi 0 a 1. Index 1 znamená, že dvě datové sady jsou identické, a index 0 znamená, že datové sady nemají žádné společné prvky. Index Jaccard je definován následujícím vzorcem:

${\ displaystyle J (A, B) = {\ frac {| A \ cap B |} {| A \ cup B |}}} = {\ frac {TP} {TP+FP+FN}}}$

Toto je jednoduše počet unikátních prvků společných oběma sadám dělený celkovým počtem unikátních prvků v obou sadách.

Také se nebere v úvahu a může se lišit od 0 nahoru bez svázání.${\ displaystyle TN}$

• Index kostek

Symetrické měřítko kostek zdvojnásobuje váhu a přitom ignoruje : ${\ displaystyle TP}$${\ displaystyle TN}$

${\ displaystyle DSC = {\ frac {2TP} {2TP+FP+FN}}}$

• Index Fowlkes – Mallows

Index Fowlkes – Mallows vypočítává podobnost mezi klastry vrácenými algoritmem klastrování a srovnávacími klasifikacemi. Čím vyšší je hodnota Fowlkes -Mallowova indexu, tím jsou si klastry a srovnávací klasifikace podobnější. Lze jej vypočítat pomocí následujícího vzorce:

${\ displaystyle FM = {\ sqrt {{\ frac {TP} {TP+FP}} \ cdot {\ frac {TP} {TP+FN}}}}}}$

kde je počet skutečných pozitiv , počet falešných pozitiv a počet falešných negativů . Index je geometrický průměr přesnosti a odvolání a , a je proto také známá jako G-opatření, zatímco F-měření je jejich střední harmonické. Kromě toho, přesné a odvolání jsou také známé jako indexy Wallaceových a . Možnost normalizovány verze Připomeňme, přesnosti a G-opatření odpovídají na Informovanost , výraznost a Matthews korelace a silně se vztahují k Kappa .${\ displaystyle TP}$${\ displaystyle FP}$${\ displaystyle FN}$${\ displaystyle FM}$ ${\ displaystyle P}$${\ displaystyle R}$${\ displaystyle B^{I}}$${\ displaystyle B^{II}}$

• Vzájemná výměna informací je informační teoretická míra, kolik informací je sdílena mezi shlukování a klasifikace pozemní pravda, že dokáže detekovat nelineární podobnosti mezi dvěma clusterings. Normalizovaná vzájemná informace je rodina variant opravených pro náhodu, která má snížené zkreslení pro různé počty klastrů.
• Matice zmatku

Matici zmatek lze použít k rychlé vizualizaci výsledků klasifikačního (nebo klastrovacího) algoritmu. Ukazuje, jak se liší klastr od klastru zlatého standardu.

Klastrová tendence

Měření tendence klastru je měřit, do jaké míry klastry existují v datech, která mají být seskupena, a lze je provést jako počáteční test před pokusem o klastrování. Jedním ze způsobů, jak toho dosáhnout, je porovnat data s náhodnými daty. V průměru by náhodná data neměla mít shluky.

• Statistiky Hopkins

Existuje několik formulací statistiky Hopkins . Typický je následující. Nechť je množina datových bodů v dimenzionálním prostoru. Zvažte náhodný vzorek (bez nahrazení) datových bodů členy . Také generování souboru z rovnoměrně rozmístěných náhodným datových bodů. Nyní definujte dvě míry vzdálenosti, což je vzdálenost od jeho nejbližšího souseda v X a vzdálenost od jeho nejbližšího souseda v X. Poté definujeme Hopkinsovu statistiku jako: ${\ displaystyle X}$${\ displaystyle n}$${\ displaystyle d}$${\ Displaystyle m \ ll n}$${\ displaystyle x_ {i}}$${\ displaystyle Y}$${\ displaystyle m}$${\ displaystyle u_ {i}}$${\ displaystyle y_ {i} \ v Y}$${\ displaystyle w_ {i}}$${\ displaystyle x_ {i} \ v X}$

${\ Displaystyle H = {\ frac {\ sum _ {i = 1}^{m} {u_ {i}^{d}}} {\ sum _ {i = 1}^{m} {u_ {i} ^{d}}+\ suma _ {i = 1}^{m} {w_ {i}^{d}}}} \ ,,}$

S touto definicí by jednotná náhodná data měla mít hodnoty blízké 0,5 a seskupená data by měla mít hodnoty blíže 1.

Data obsahující pouze jeden Gaussian však také dosáhnou skóre blízkého 1, protože tato statistika měří odchylku od rovnoměrného rozdělení, nikoli multimodality , což činí tuto statistiku do značné míry nepoužitelnou (protože skutečná data nikdy nejsou vzdáleně jednotná).

Aplikace

Biologie, výpočetní biologie a bioinformatika

Ekologie rostlin a živočichů

Klastrová analýza se používá k popisu a prostorovému a časovému srovnání společenstev (asambláží) organismů v heterogenních prostředích. Používá se také v systematice rostlin ke generování umělých fylogenií nebo shluků organismů (jednotlivců) na úrovni druhu, rodu nebo vyšší, které sdílejí řadu atributů.

Transkriptomika

Shlukování se používá k vytváření skupin genů se souvisejícími expresními vzory (také známými jako koexprimované geny) jako v klastrovacím algoritmu HCS . Často takové skupiny obsahují funkčně příbuzné proteiny, jako jsou enzymy pro specifickou cestu , nebo geny, které jsou regulovány společně. Experimenty s vysokou propustností využívající expresní sekvenční tagy (EST) nebo DNA mikročipy mohou být silným nástrojem pro anotaci genomu - obecný aspekt genomiky .

Sekvenční analýza

Sekvenční shlukování se používá ke seskupení homologních sekvencí do genových rodin . Toto je velmi důležitý koncept v bioinformatice a evoluční biologii obecně. Podívejte se na evoluci genovou duplikací .

Vysoce výkonné platformy genotypování

Shlukovací algoritmy se používají k automatickému přiřazování genotypů.

Lidské genetické shlukování

Podobnost genetických dat se využívá při shlukování k odvození populačních struktur.

Lék

Lékařské zobrazování

U PET skenů lze k rozlišení různých typů tkání v trojrozměrném obrazu použít klastrovou analýzu pro mnoho různých účelů.

Analýza antimikrobiální aktivity

Klastrovou analýzu lze použít k analýze vzorců rezistence vůči antibiotikům, ke klasifikaci antimikrobiálních sloučenin podle jejich mechanismu účinku, ke klasifikaci antibiotik podle jejich antibakteriální aktivity.

Segmentace IMRT

Klastrování lze použít k rozdělení mapy fluence do odlišných oblastí pro převod do doručitelných polí v radiační terapii založené na MLC.

Obchod a marketing

Průzkum trhu

Clusterová analýza je široce používána v průzkumu trhu při práci s vícerozměrnými daty z průzkumů a testovacích panelů. Výzkumníci trhu pomocí analýzy clusteru rozdělit obecnou populaci a spotřebitelů do segmentů trhu a lépe porozumět vztahu mezi různými skupinami spotřebitelů / potenciálních zákazníků , a pro použití v segmentaci trhu , umístění výrobků , vývoj nových produktů a výběr zkušebních trhy.

Seskupení nákupních položek

Klastrování lze použít ke seskupení všech nákupních položek dostupných na webu do sady unikátních produktů. Například všechny položky na eBay lze seskupit do jedinečných produktů (eBay nemá koncept SKU ).

Celosvětová Síť

Analýza sociálních sítí

Při studiu sociálních sítí lze k rozpoznání komunit v rámci velkých skupin lidí použít klastrování .

Seskupení výsledků vyhledávání

V procesu inteligentního seskupování souborů a webů lze klastrování použít k vytvoření relevantnější sady výsledků vyhledávání ve srovnání s běžnými vyhledávači, jako je Google . V současné době existuje řada webových klastrových nástrojů, jako je Clusty . Lze jej také použít k vrácení komplexnější sady výsledků v případech, kdy by hledaný výraz mohl odkazovat na zcela odlišné věci. Každé odlišné použití výrazu odpovídá jedinečnému seskupení výsledků, což umožňuje hodnotícímu algoritmu vrátit komplexní výsledky výběrem nejlepšího výsledku z každého klastru.

Optimalizace kluzké mapy

Flickrova mapa fotografií a dalších mapových webů využívá klastrování ke snížení počtu značek na mapě. Díky tomu je rychlejší a snižuje množství vizuálního nepořádku.

Počítačová věda

Evoluce softwaru

Clustering je užitečný v evoluci softwaru, protože pomáhá redukovat starší vlastnosti v kódu reformováním funkcí, které se staly rozptýlenými. Je to forma restrukturalizace, a proto je to způsob přímé preventivní údržby.

Segmentace obrazu

Klastrování lze použít k rozdělení digitálního obrazu na odlišné oblasti pro detekci hranic nebo rozpoznávání objektů .

Evoluční algoritmy

Shlukování lze použít k identifikaci různých mezer v populaci evolučního algoritmu, aby bylo možné reprodukční příležitosti distribuovat rovnoměrněji mezi vyvíjející se druhy nebo poddruhy.

Doporučovací systémy

Systémy doporučení jsou navrženy tak, aby doporučovaly nové položky podle vkusu uživatele. Někdy používají klastrové algoritmy k předpovídání preferencí uživatele na základě preferencí ostatních uživatelů v uživatelském klastru.

Metody Markovského řetězce Monte Carlo

Klastrování se často používá k vyhledání a charakterizaci extrémů v cílové distribuci.

Detekce anomálií

Anomálie/odlehlé hodnoty jsou obvykle - ať už výslovně nebo implicitně - definovány s ohledem na strukturu shlukování v datech.

Zpracování přirozeného jazyka

Clustering lze použít k vyřešení lexikální nejednoznačnosti .

Společenské vědy

Sekvenční analýza v sociálních vědách

Klastrová analýza se používá například k identifikaci vzorů trajektorií rodinného života, profesionální kariéry a denního nebo týdenního využití času.

Analýza kriminality

Klastrovou analýzu lze použít k identifikaci oblastí, kde je vyšší výskyt konkrétních typů trestné činnosti. Identifikací těchto odlišných oblastí nebo „horkých míst“, kde se podobný zločin stal po určitou dobu, je možné efektivněji spravovat prostředky vymáhání práva.

Těžba vzdělávacích dat

Klastrová analýza se například používá k identifikaci skupin škol nebo studentů s podobnými vlastnostmi.

Typologie

Z údajů z průzkumů veřejného mínění projekty, jako jsou projekty prováděné Pew Research Center, používají klastrovou analýzu k rozpoznání typologií názorů, návyků a demografie, které mohou být užitečné v politice a marketingu.

Ostatní

Polní robotika

Shlukovací algoritmy se používají pro robotické situační povědomí ke sledování objektů a detekci odlehlých hodnot v datech senzorů.

Matematická chemie

Aby se zjistila strukturální podobnost atd., Bylo například seskupeno 3000 chemických sloučenin v prostoru 90 topologických indexů .

Klimatologie

Najít povětrnostní režimy nebo preferované atmosférické vzorce tlaku na hladině moře.

Finance

Klastrová populace byla použita k seskupení akcií do sektorů.

Geologie ropy

Klastrová analýza se používá k rekonstrukci chybějících dat jádra dna nebo chybějících logových křivek za účelem vyhodnocení vlastností nádrže.

Geochemie

Shlukování chemických vlastností na různých místech vzorku.

Viz také

Specializované typy klastrové analýzy

• Algoritmy automatického shlukování
• Vyvážené shlukování
• Shlukování vysoce dimenzionálních dat
• Koncepční shlukování
• Shlukování shody
• Omezené seskupování
• Komunitní detekce
• Shlukování datových proudů
• Klastrování HCS
• Sekvenční shlukování
• Spektrální shlukování

Techniky používané v klastrové analýze

• Umělá neurální síť (ANN)
• Hledání nejbližšího souseda
• Analýza sousedských komponent
• Latentní třídní analýza
• Propagace afinity

Projekce dat a předběžné zpracování

• Redukce rozměrů
• Analýza hlavních komponent
• Multidimenzionální škálování

jiný

• Clusterově vážené modelování
• Prokletí dimenzionality
• Určení počtu klastrů v datové sadě
• Souběžné souřadnice
• Analýza strukturovaných dat

Reference