Hierarkisk klustring

Inom datautvinning och statistik är hierarkisk kluster (även kallad hierarkisk klusteranalys eller HCA ) en metod för klusteranalys som försöker bygga en hierarki av kluster. Strategier för hierarkisk klustring delas i allmänhet in i två kategorier:

Agglomerativ : Detta är ett " nedifrån-och-upp " tillvägagångssätt: Varje observation börjar i sitt eget kluster, och par av kluster slås samman när man flyttar uppåt i hierarkin.
Divisive : Detta är ett " top-down " tillvägagångssätt: Alla observationer börjar i ett kluster, och uppdelningar utförs rekursivt när man flyttar ner i hierarkin.

I allmänhet bestäms sammanslagningarna och splittringarna på ett girigt sätt. Resultaten av hierarkisk klustring presenteras vanligtvis i ett dendrogram .

Standardalgoritmen för hierarkisk agglomerativ klustring (HAC) har en tidskomplexitet på ${\mathcal {O}}(n^{3})$ och kräver $\Omega (n^{2})$ minne, vilket gör det för långsamt för även medelstora datamängder. För vissa speciella fall är dock optimala effektiva agglomerativa metoder (med komplexitet ${\displaystyle {\mathcal {O}}(n^{2})} )$ kända: SLINK för enkellänkning och CLINK för fullständig -kopplingsklustring . Med en heap kan körtiden för det allmänna fallet reduceras till ${\displaystyle {\mathcal {O}}(n^{2}\log n)} ,$ en förbättring av den tidigare nämnda gränsen av ${\displaystyle {\mathcal {O}}(n^{3})} ,$ på bekostnad av att ytterligare öka minneskraven. I många fall är minneskostnaderna för detta tillvägagångssätt för stora för att göra det praktiskt användbart.

Förutom det speciella fallet med enkellänkning, kan ingen av algoritmerna (förutom uttömmande sökning i ${\displaystyle {\mathcal {O}}(2^{n})})$ garanteras att hitta det optimala lösning.

Delande klustring med en uttömmande sökning är ${\displaystyle {\mathcal {O}}(2^{n})} ,$ men det är vanligt att använda snabbare heuristik för att välja splittringar, såsom k -medel .

Hierarkisk klustring har den distinkta fördelen att vilket giltigt mått på avstånd som helst kan användas. Faktum är att själva observationerna inte krävs: allt som används är en matris av avstånd .

Klusterkoppling

För att bestämma vilka kluster som ska kombineras (för agglomerativa), eller var ett kluster ska delas (för delning), krävs ett mått på olikhet mellan uppsättningar av observationer. I de flesta metoder för hierarkisk klustring uppnås detta genom att använda ett lämpligt avstånd d , såsom det euklidiska avståndet, mellan enskilda observationer av datamängden, och ett länkkriterium, som specificerar olikheten mellan mängder som en funktion av de parvisa avstånden. av observationer i uppsättningarna. Valet av metrik såväl som länkning kan ha stor inverkan på resultatet av klustringen, där den lägre nivån bestämmer vilka objekt som är mest lika, medan länkningskriteriet påverkar formen på klustren. Till exempel tenderar fullständig länkning att producera fler sfäriska kluster än enkellänkning.

Kopplingskriteriet bestämmer avståndet mellan uppsättningar observationer som en funktion av de parvisa avstånden mellan observationer.

Några vanligt använda kopplingskriterier mellan två uppsättningar observationer A och B och ett avstånd d är:

Namn	Formel
Maximal eller fullständig kopplingsklustring	$\max _{a\in A,\,b\in B}d(a,b)$
Minsta eller enkellänkade klustring	$\min _{a\in A,\,b\in B}d(a,b)$
Oviktad genomsnittlig länkningsklustring (eller UPGMA )	${\frac {1}{\|A\|\cdot \|B\|}}\summa _{a\in A}\summa _{b\in B}d(a,b).$
Viktad genomsnittlig länkningsklustring (eller WPGMA )	$d(i\cup j,k)={\frac {d(i,k)+d(j,k)}{2}}.$
Centroid linkage clustering, eller UPGMC	$\lVert \mu _{A}-\mu _{B}\rVert ^{2}$ där $\mu _{A}$ och $\mu _{B}$ är tyngdpunkterna för A resp. B .
Mediankopplingsklustring, eller WPGMC	$d(i\cup j,k)=d(m_{i\cup j},m_{k})$ där $m_{i\cup j}={\tfrac {1}{2}}\left(m_{i}+m_{j}\right)$
Mångsidig kopplingsklustring	${\sqrt[{p}]{{\frac {1}{\|A\|\cdot \|B\|}}\summa _{a\in A}\summa _{b\in B}d(a,b)^{p}}},p\neq 0$
Avdelningskoppling , minsta ökning av summan av kvadrater (MISSQ)	$2$
Minsta felsumma av kvadrater (MNSSQ)	$\sum _{x\in A\cup B}\lVert x-\mu _{A\cup B}\rVert ^{2}$
Minsta ökning av varians (MIVAR)	${\frac {1}{\|A\cup B\|}}\summa _{x\in A\cup B}\lVert x-\mu _{A \cup B}\rVert ^{2}-{\frac {1}{\|A\|}}\summa _{x\in A}\lVert x-\mu _{A}\rVert ^{2}-{ \frac {1}{\|B\|}}\summa _{x\in B}\lVert x-\mu _{B}\rVert ^{2}$ $={\text{Var}}(A\cup B)-{\text{Var}}(A)-{\text{Var}}(AB)$
Minsta avvikelse (MNVAR)	${\frac {1}{\|A\cup B\|}}\summa _{x\in A\cup B}\lVert x-\mu _{A\cup B}\rVert ^{2}={\text{Var}}(A\cup B)$
Mini-Max länkage	$\min _{x\in A\cup B}\max _{y\in A\cup B}d(x,y )$
Hausdorff koppling	$\max _{x\in A\cup B}\min _{y\in A\cup B}d(x,y )$
Minsta summa Medoid-koppling	$\min _{m\in A\cup B}\summa _{y\in A\cup B}d(m,y )$ så att m är medoiden för det resulterande klustret
Minsta Summa Ökning Medoid koppling	${\ displaystyle \min _{m\in A\cup B}\summa _{y\in A\cup B}d(m,y)-\min _{m\in A}\summa _{y\in A} d(m,y)-\min _{m\in B}\summa _{y\in B}d(m,y)}$
Medoid koppling	$d(m_{A},m_{B})$ där $m_{A}$ , $m_{B}$ är medoiderna för de tidigare klustren
Minsta energiklustring	${\frac {2}{nm}}\sum _{i,j=1}^{n,m}\\|a_{i}-b_{j}\\| _{2}-{\frac {1}{n^{2}}}\sum _{i,j=1}^{n}\\|a_{i}-a_{j}\\|_{2} -{\frac {1}{m^{2}}}\sum _{i,j=1}^{m}\\|b_{i}-b_{j}\\|_{2}$

Vissa av dessa kan bara beräknas om rekursivt (WPGMA, WPGMC), för många är en rekursiv beräkning med Lance-Williams-ekvationer mer effektiv, medan för andra (Mini-Max, Hausdorff, Medoid) måste avstånden beräknas med den långsammare fullständig formel. Andra kopplingskriterier inkluderar:

Sannolikheten att kandidatkluster kommer från samma distributionsfunktion (V-länkning).
Produkten av in-grad och ut-grad på en k-närmaste-granne-graf (grafgradskoppling).
Ökningen av någon klusterdeskriptor (dvs. en kvantitet definierad för att mäta kvaliteten på ett kluster) efter sammanslagning av två kluster.

Exempel på agglomerativ klustring

Rådata

Anta till exempel att dessa data ska klustras och det euklidiska avståndet är avståndsmåttet .

Det hierarkiska klustringsdendrogrammet skulle vara:

Traditionell representation

Att kapa trädet på en given höjd kommer att ge en partitioneringskluster med en vald precision. I det här exemplet kommer skärning efter den andra raden (uppifrån) i dendrogrammet att ge kluster {a} {bc} {de} {f}. Skärning efter den tredje raden kommer att ge kluster {a} {bc} {def}, vilket är en grövre kluster, med ett mindre antal men större kluster.

Denna metod bygger hierarkin från de individuella elementen genom att successivt slå samman kluster. I vårt exempel har vi sex element {a} {b} {c} {d} {e} och {f}. Det första steget är att bestämma vilka element som ska slås samman i ett kluster. Vanligtvis vill vi ta de två närmaste elementen, enligt det valda avståndet.

Eventuellt kan man även konstruera en avståndsmatris i detta skede, där numret i den i -:e raden j -:e kolumnen är avståndet mellan de i -:te och j -te elementen. Sedan, allt eftersom klustringen fortskrider, slås rader och kolumner samman när klustren slås samman och avstånden uppdateras. Detta är ett vanligt sätt att implementera den här typen av kluster och har fördelen av att cache avstånd mellan kluster. En enkel agglomerativ klustringsalgoritm beskrivs på klustringssidan med enkel länk ; den kan enkelt anpassas till olika typer av kopplingar (se nedan).

Anta att vi har slagit samman de två närmaste elementen b och c , vi har nu följande kluster { a }, { b , c }, { d }, { e } och { f } och vill slå samman dem ytterligare. För att göra det måste vi ta avståndet mellan {a} och {bc} och därför definiera avståndet mellan två kluster. Vanligtvis är avståndet mellan två kluster ${\mathcal {A}}$ och ${\mathcal {B}}$ ett av följande:

Det maximala avståndet mellan element i varje kluster (även kallat komplett-länkning kluster ):

{\displaystyle \max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.} Minsta avstånd mellan

element av varje kluster (även kallad enkellänkning kluster ):

{\displaystyle \min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.} Medelavståndet mellan

elementen för varje kluster (även kallad genomsnittlig länkklustring, används t.ex. i UPGMA ):

{1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\summa _{x\in {\mathcal {A}}}\summa _{y \in {\mathcal {B}}}d(x,y).

Summan av all varians inom kluster.
Ökningen i varians för klustret som slås samman ( Wards metod )
Sannolikheten att kandidatkluster kommer från samma distributionsfunktion (V-länkning).

Vid bundna minimiavstånd väljs ett par slumpmässigt, vilket kan generera flera strukturellt olika dendrogram. Alternativt kan alla bundna par sammanfogas samtidigt, vilket skapar ett unikt dendrogram.

Man kan alltid bestämma sig för att sluta klustera när det finns ett tillräckligt litet antal kluster (antalkriterium). Vissa kopplingar kan också garantera att agglomeration sker på ett större avstånd mellan kluster än föregående agglomeration, och då kan man sluta kluster när klustren är för långt ifrån varandra för att slås samman (avståndskriterium). Detta är dock inte fallet med t.ex. tyngdpunktskopplingen där de så kallade reverseringarna (inversioner, avvikelser från ultrametricitet) kan inträffa.

Delande klustring

Grundprincipen för delande klustring publicerades som DIANA (DIvisive ANAlysis Clustering)-algoritmen. Inledningsvis finns all data i samma kluster och det största klustret delas tills varje objekt är separat. Eftersom det finns $O(2^{n})$ sätt att dela upp varje kluster, behövs heuristik. DIANA väljer objektet med den maximala genomsnittliga olikheten och flyttar sedan alla objekt till detta kluster som är mer lika det nya klustret än resten.

programvara

Implementeringar med öppen källkod

Hierarkiskt klustringsdendrogram för Iris -datauppsättningen (med R ). Källa

Hierarkisk klustring och interaktiv dendrogramvisualisering i Orange data mining suite .

ALGLIB implementerar flera hierarkiska klustringsalgoritmer (single-link, complete-link, Ward) i C++ och C# med O(n²)-minne och O(n³) körtid.
ELKI inkluderar flera hierarkiska klusteralgoritmer, olika länkstrategier och inkluderar även de effektiva SLINK-, CLINK- och Anderberg-algoritmerna, flexibel klusterextraktion från dendrogram och olika andra klusteranalysalgoritmer .
Julia har en implementering i Clustering.jl-paketet.
Octave , GNU analog till MATLAB implementerar hierarkisk klustring i funktion "länkning".
Orange , en programvara för datautvinning, inkluderar hierarkisk klustring med interaktiv dendrogramvisualisering.
R har inbyggda funktioner och paket som tillhandahåller funktioner för hierarkisk klustring.
SciPy implementerar hierarkisk klustring i Python, inklusive den effektiva SLINK-algoritmen.
scikit-learn implementerar även hierarkisk klustring i Python.
Weka inkluderar hierarkisk klusteranalys.

Kommersiella implementeringar

MATLAB inkluderar hierarkisk klusteranalys.
SAS inkluderar hierarkisk klusteranalys i PROC CLUSTER.
Mathematica inkluderar ett hierarkiskt klusterpaket.
NCSS inkluderar hierarkisk klusteranalys.
SPSS inkluderar hierarkisk klusteranalys.
Qlucore Omics Explorer inkluderar hierarkisk klusteranalys.
Stata inkluderar hierarkisk klusteranalys.
CrimeStat inkluderar en hierarkisk klusteralgoritm för närmaste granne med en grafisk utdata för ett geografiskt informationssystem.

Se även

Vidare läsning

Kaufman, L.; Rousseeuw, PJ (1990). Hitta grupper i data: En introduktion till klusteranalys (1 upplaga). New York: John Wiley. ISBN 0-471-87876-6 .
Hastie, Trevor ; Tibshirani, Robert ; Friedman, Jerome (2009). "14.3.12 Hierarkisk klustring" . The Elements of Statistical Learning (2nd ed.). New York: Springer. s. 520–8. ISBN 978-0-387-84857-0 . Arkiverad från originalet (PDF) 2009-11-10 . Hämtad 2009-10-20 .