Clusterová analýza nebo clustering je běžná technika pro statistickou analýzu dat, která se používá v mnoha oblastech, včetně strojového učení, dolování dat, rozpoznávání vzorů, analýzy obrázků a bioinformatiky. Clustering je klasifikace podobných objektů do různých skupin, nebo přesněji rozdělení datové sady do podskupin (clusterů), takže data v každé podskupině (ideálně) sdílejí nějaký společný rys – často blízkost podle nějaké definované vzdálenosti.
Kromě termínu data clustering (nebo jen clustering) existuje řada termínů s podobným významem, včetně clusterové analýzy, automatické klasifikace, numerické taxonomie, botryologie a typologické analýzy.
Algoritmy sdružování dat mohou být hierarchické nebo partikulární. Hierarchické algoritmy nacházejí po sobě jdoucí clustery pomocí dříve vytvořených clusterů, zatímco partikulární algoritmy určují všechny clustery najednou. Hierarchické algoritmy mohou být aglomerační (zdola nahoru) nebo divizní (shora dolů). Aglomerarchické algoritmy začínají s každým prvkem jako samostatný cluster a slučují je do po sobě jdoucích větších clusterů. Divizní algoritmy začínají celou množinou a postupují k jejímu rozdělení do po sobě jdoucích menších clusterů.
Klíčovým krokem v hierarchickém shlukování je výběr míry vzdálenosti. Jednoduchá míra je vzdálenost manhattanu, rovnající se součtu absolutních vzdáleností pro každou proměnnou. Název vychází ze skutečnosti, že v případě dvou proměnných mohou být proměnné vyneseny do mřížky, kterou lze porovnat s ulicemi města, a vzdálenost mezi dvěma body je počet bloků, které by člověk ušel.
Častějším měřítkem je euklidovská vzdálenost, vypočítaná tak, že se najde druhá mocnina vzdálenosti mezi jednotlivými veličinami, sečtou se čtverce a najde se odmocnina z tohoto součtu. V případě dvou veličin je vzdálenost analogická s nalezením délky přepony v trojúhelníku; to znamená, že je to vzdálenost „vzdušnou čarou“. Přehled clusterové analýzy ve výzkumu psychologie zdraví zjistil, že nejčastějším měřítkem vzdálenosti v publikovaných studiích v této oblasti výzkumu je euklidovská vzdálenost nebo euklidovská vzdálenost na druhou.
Při měření vzdálenosti lze prvky kombinovat. Hierarchické shlukování vytváří (aglomerační) nebo rozděluje (rozděluje) hierarchii shluků. Tradiční reprezentace této hierarchie je stromová datová struktura (nazývaná dendrogram), s jednotlivými prvky na jednom konci a jedním shlukem s každým prvkem na druhém. Aglomerativní algoritmy začínají na vrcholu stromu, zatímco rozdělovací algoritmy začínají dole. (Na obrázku šipky označují aglomerativní shlukování.)
Vyjmutím stromu v dané výšce získáte shlukování s vybranou přesností. V následujícím příkladu vybráním za druhým řádkem získáte shluky {a} {b c} {d e} {f}. Vyjmutím za třetím řádkem získáte shluky {a} {b c} {d e f}, což je hrubší shlukování s menším počtem větších shluků.
Aglomerativní hierarchické seskupování
Například předpokládejme, že tato data mají být shlukována. Kde euklidovská vzdálenost je metrika vzdálenosti.
Hierarchické shlukování dendrogram by jako takový:
Tradiční zastoupení
Tato metoda sestavuje hierarchii z jednotlivých prvků postupným slučováním clusterů. Opět máme šest prvků {a} {b} {c} {d} {e} a {f}. Prvním krokem je určit, které prvky sloučit do clusteru. Obvykle chceme vzít dva nejbližší prvky, proto musíme definovat vzdálenost mezi prvky. V této fázi lze také sestrojit matici vzdálenosti.
Předpokládejme, že jsme sloučili dva nejbližší prvky b a c, nyní máme následující shluky {a}, {b, c}, {d}, {e} a {f}, a chceme je dále sloučit. Ale k tomu potřebujeme vzít vzdálenost mezi {a} a {b c}, a tedy definovat vzdálenost mezi dvěma shluky. Obvykle vzdálenost mezi dvěma shluky a je jedna z následujících:
Každá aglomerace se vyskytuje ve větší vzdálenosti mezi klastry než předchozí aglomerace a lze rozhodnout o zastavení shlukování buď tehdy, když jsou klastry od sebe příliš daleko na to, aby mohly být sloučeny (kritérium vzdálenosti), nebo když je dostatečně malý počet klastrů (kritérium počtu).
Algoritmus K-means přiřazuje každý bod clusteru, jehož střed (také nazývaný centroid) je nejbližší. Střed je průměr všech bodů v clusteru – to znamená, že jeho souřadnice jsou aritmetickým průměrem pro každý rozměr zvlášť pro všechny body v clusteru.
Algoritmus je zhruba (J. MacQueen, 1967):
Hlavními výhodami tohoto algoritmu jsou jeho jednoduchost a rychlost, která mu umožňuje běh na velkých datových sadách. Jeho nevýhodou je, že při každém běhu nepřináší stejný výsledek, protože výsledné clustery jsou závislé na počátečních náhodných přiřazeních. Maximalizuje rozptyl mezi clustery (nebo minimalizuje rozptyl uvnitř clusteru), ale nezajišťuje, že výsledek má globální minimum rozptylu.
QT (Quality Threshold) Clustering (Heyer et al, 1999) je alternativní metoda dělení dat, vynalezená pro shlukování genů. Vyžaduje větší výpočetní výkon než k-prostředky, ale nevyžaduje určení počtu shluků a priori a při opakovaném spuštění vždy vrací stejný výsledek.
Vzdálenost mezi bodem a skupinou bodů se vypočítá pomocí kompletního propojení, tj. jako maximální vzdálenost od bodu k jakémukoli členu skupiny (viz sekce „Agglomerativní hierarchické shlukování“ o vzdálenosti mezi shluky).
V fuzzy shlukování má každý bod určitý stupeň sounáležitosti se shluky, jako v fuzzy logice, spíše než úplnou sounáležitost jen s jedním shlukem. Tedy body na okraji shluku, mohou být ve shluku v menší míře než body ve středu shluku. Pro každý bod x máme koeficient udávající stupeň sounáležitosti v kth shluku . Obvykle je součet těchto koeficientů definován jako 1, takže to značí pravděpodobnost sounáležitosti s určitým shlukem:
U fuzzy c-means je těžiště shluku průměr všech bodů, vážený jejich stupněm sounáležitosti ke shluku:
Stupeň sounáležitosti souvisí s inverzní vzdáleností ke shluku
pak koeficienty jsou normalizovány a fuzzyfied s reálným parametrem tak, že jejich součet je 1. Takže
Pro m rovno 2 je to ekvivalentní normalizaci koeficientu lineárně, aby jejich součet byl 1. Když se m blíží 1, pak centru clusteru nejblíže bodu je dána mnohem větší váha než ostatním a algoritmus je podobný k-prostředkům.
Algoritmus fuzzy c-means je velmi podobný algoritmu k-means:
Algoritmus také minimalizuje rozptyl uvnitř clusteru, ale má stejné problémy jako k-means, minimum je lokální minimum a výsledky závisí na počáteční volbě váhy.
Kritérium elbow je obecné pravidlo, které určuje, jaký počet shluků by měl být zvolen, například pro k-means a aglomerační hierarchické shlukování.
Kritérium elbow říká, že byste měli zvolit určitý počet clusterů tak, aby přidání dalšího clusteru nepřidávalo dostatečné informace. Přesněji řečeno, pokud grafujete procento rozptylu vysvětlené clustery proti počtu clusterů, první clustery přidají mnoho informací (vysvětlí velký rozptyl), ale v určitém okamžiku marginální zisk klesne, což dává úhel v grafu (elbow).
Na následujícím grafu je loket označen červeným kruhem. Počet vybraných shluků by tedy měl být 4.
Vzhledem k množině datových bodů může být matice podobnosti definována jako matice, kde představuje míru podobnosti mezi bodem a . Techniky spektrálního shlukování využívají spektrum matice podobnosti dat ke shlukování bodů. Někdy se tyto techniky používají také k provedení redukce dimenzionality pro shlukování v méně dimenzích.
Jednou z takových technik je Shi-Malikův algoritmus, běžně používaný pro segmentaci obrazu. Rozděluje body do dvou množin na základě vlastního vektoru odpovídajícího druhému nejmenšímu vlastnímu číslu Laplaciána
na , Kde je diagonální matice
Toto dělení může být provedeno různými způsoby, například tím, že medián složek v , A umístění všech bodů, jejichž složka v je větší než v , A zbytek v . Algoritmus může být použit pro hierarchické shlukování, opakovaným dělení podskupin tímto způsobem.
Související algoritmus je Meila-Shi algoritmus, který vezme vlastní vektory odpovídající k největším vlastním číslům matice pro některé k a pak vyvolá další (např. k-means) pro clusterové body jejich příslušnými k součástmi v těchto vlastních vektorech.
V biologii má klastrování mnoho aplikací v oblasti výpočetní biologie a bioinformatiky, z nichž dvě jsou:
Klastrová analýza se široce používá ve výzkumu trhu při práci s vícerozměrnými daty z průzkumů a testovacích panelů. Výzkumníci trhu používají klastrovou analýzu k rozdělení obecné populace spotřebitelů do segmentů trhu a k lepšímu pochopení vztahů mezi různými skupinami spotřebitelů/potenciálních zákazníků.
Analýza sociálních sítí: Při studiu sociálních sítí může být shlukování použito k rozpoznání komunit v rámci velkých skupin lidí.
Segmentace obrazu: Shlukování může být použito k rozdělení digitálního obrazu do odlišných oblastí pro detekci hranic nebo rozpoznání objektu.
Vytěžování dat: Mnoho aplikací pro vytěžování dat zahrnuje rozdělení datových položek do souvisejících podskupin; výše popsané marketingové aplikace představují některé příklady. Další běžnou aplikací je rozdělení dokumentů, například webových stránek World Wide Web, do žánrů.
Srovnání mezi seskupeními údajů
Existuje několik návrhů na míru podobnosti mezi dvěma seskupeními. Takovou míru lze použít k porovnání toho, jak dobře fungují různé algoritmy seskupování dat na souboru dat.
Mnohé z těchto měr jsou odvozeny z matice shody (aka matice záměny), např. z míry Rand a z míry Fowlkes-Mallows Bk.
Pro spektrální shlukování:
Pro odhad počtu shluků: