Enlänkad klustring

Inom statistik är klustring med enkel länk en av flera metoder för hierarkisk klustring . Den är baserad på att gruppera kluster på ett bottom-up-sätt (agglomerativ kluster), vid varje steg kombinera två kluster som innehåller det närmaste paret av element som ännu inte tillhör samma kluster som varandra.

Denna metod tenderar att producera långa tunna kluster där närliggande element i samma kluster har små avstånd, men element i motsatta ändar av ett kluster kan vara mycket längre från varandra än två element i andra kluster. För vissa klasser av data kan detta leda till svårigheter att definiera klasser som med fördel kan dela upp data. Emellertid är det populärt inom astronomi för att analysera galaxhopar , som ofta kan involvera långa strängar av materia; i den här applikationen är den också känd som vänner-av-vänner-algoritmen.

Översikt över agglomerativa klustringsmetoder

I början av den agglomerativa klusterprocessen är varje element i ett eget kluster. Klustren kombineras sedan sekventiellt till större kluster, tills alla element hamnar i samma kluster. Vid varje steg kombineras de två klustren åtskilda av det kortaste avståndet. Funktionen som används för att bestämma avståndet mellan två kluster, känd som länkfunktionen , är det som skiljer de agglomerativa klustermetoderna.

I enkellänkningskluster bestäms avståndet mellan två kluster av ett enda par av element: de två element (en i varje kluster) som är närmast varandra. Det kortaste av dessa parvisa avstånd som återstår vid något steg gör att de två klustren vars element är inblandade slås samman. Metoden är också känd som närmaste granne klustring . Resultatet av klustringen kan visualiseras som ett dendrogram , som visar sekvensen i vilken kluster slogs samman och avståndet vid vilket varje sammanslagning ägde rum.

beskrivs länkfunktionen – avståndet D ( X , Y ) mellan kluster X och Y – med uttrycket

D(X,Y)=\min _{x\in X,y\in Y}d(x, y),

där X och Y är två valfria uppsättningar av element som betraktas som kluster, och d ( x , y ) anger avståndet mellan de två elementen x och y .

Naiv algoritm

Följande algoritm är ett agglomerativt schema som raderar rader och kolumner i en närhetsmatris när gamla kluster slås samman till nya. N $N\times N$ närhetsmatris $displaystyle D}$ innehåller alla avstånd $d(i,j)$ . Klustringarna tilldelas sekvensnummer $0,1,\ldots ,n-1$ och $L(k)$ är nivån för $k$ -th klustring. Ett kluster med sekvensnummer m betecknas ( m ) och närheten mellan kluster $(r)$ och $(s)$ betecknas $d[(r),(s)]$ .

Algoritmen för enkel länkning består av följande steg:

Börja med att den disjunkta klustringen har nivå $L(0)=0$ och sekvensnummer $m=0$ .
Hitta det mest lika klusterparet i den aktuella klustringen, säg par $(r),(s)$ , enligt $d[(r),(s)]=\min d[(i),(j)]$ där minimum är över alla par av kluster i den aktuella klustringen.
Öka sekvensnumret: $m=m+1$ . Slå samman kluster $(r)$ och $(s)$ till ett enda kluster för att bilda nästa kluster m $\displaystyle m}$ . Ställ in nivån för denna klustring till $L(m)=d[(r),(s)]$
Uppdatera närhetsmatrisen, $D$ , genom att ta bort de rader och kolumner som motsvarar kluster $(r)$ och $(s)$ och lägga till en rad och kolumn som motsvarar det nybildade klustret. Närheten mellan det nya klustret, betecknat $(r,s)$ och ett gammalt kluster $(k)$ definieras som $d[(r,s),(k)]=\min\{d[(k) ),(r)],d[(k),(s)]\}$ .
Om alla objekt finns i ett kluster, stoppa. Annars, gå till steg 2.

Arbetsexempel

Detta arbetsexempel är baserat på en JC69 genetisk distansmatris beräknad från 5S ribosomala RNA- sekvensinriktningen av fem bakterier: Bacillus subtilis ( $a$ ), Bacillus stearothermophilus ( $b$ ), Lactobacillus viridescens ( $c$ ), Acholeplasma modicum ( $d$ ) och Micrococcus luteus ( $e$ ).

Första steget

Första klustringen

Låt oss anta att vi har fem element $(a,b,c,d,e)$ och följande matris $D_{1}$ av parvis avstånd mellan dem:

	a	b	c	d	e
a	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	23	21	39	43	0

I det här exemplet är $D_{1}(a,b)=17$ det lägsta värdet på $D_{1}$ , så vi grupperar elementen $a$ och $b$ .

Uppskattning av första grenlängd

Låt $u$ beteckna den nod som $a$ och $b$ nu är anslutna till. Inställning $\delta (a,u)=\delta (b,u)=D_{1}(a, b)/2$ säkerställer att elementen $a$ och $b$ är lika långt från $u$ . Detta motsvarar förväntningarna på ultrametricityhypotesen . Grenarna som förenar $a$ och $b$ till $u$ har då längderna $\delta (a,u)=\delta (b,u)=17 /2=8.5$ ( se det sista dendrogrammet )

Första distansmatrisuppdateringen

Vi fortsätter sedan med att uppdatera den initiala närhetsmatrisen $D_{1}$ till en ny närhetsmatris $D_{2}$ (se nedan), reducerad i storlek med en rad och en kolumn pga. klustringen av $a$ med $b$ . Fetvärden i $D_{2}$ motsvarar de nya avstånden, beräknade genom att behålla minimiavståndet mellan varje element i det första klustret $(a,b)$ och var och en av återstående element:

{\begin{array}{lllllll}D_{2}((a,b),c)&=&\min(D_{ 1}(a,c),D_{1}(b,c))&=&\min(21,30)&=&21\\D_{2}((a,b),d)&=&\ min(D_{1}(a,d),D_{1}(b,d))&=&\min(31,34)&=&31\\D_{2}((a,b),e) &=&\min(D_{1}(a,e),D_{1}(b,e))&=&\min(23,21)&=&21\end{array}}

Kursiverade värden i $D_{2}$ påverkas inte av matrisuppdateringen eftersom de motsvarar avstånden mellan element som inte är involverade i det första klustret.

Andra steg

Andra klustringen

Vi upprepar nu de tre tidigare åtgärderna, med start från den nya distansmatrisen $D_{2}$ :

	(a,b)	c	d	e
(a,b)	0	21	31	21
c	21	0	28	39
d	31	28	0	43
e	21	39	43	0

Här är $D_{2}((a,b),c)=21$ och ${\ displaystyle D_{2}((a,b),e)=21}$ är de lägsta värdena för $D_{2}$ , så vi sammanfogar kluster $(a,b)$ med element $c$ och med element $e$ .

Andra grenlängdsuppskattning

Låt $v$ beteckna den nod som ${\displaystyle (a,b)} ,$ c $och$ e $nu$ är anslutna till. På grund av ultrametricitetsbegränsningen är grenarna som förenar $a$ eller $b$ till $v$ och $c$ till $v$ och även $e$ till $v$ lika stora och har följande totala längd:

\delta (a,v)=\delta (b,v )=\delta (c,v)=\delta (e,v)=21/2=10,5

Vi härleder den saknade grenlängden:

{\displaystyle \delta (u,v) =\delta (c,v)-\delta (a,u)=\delta (c,v)-\delta (b,u)=10,5-8,5=2} (se det sista dendrogrammet )

Uppdatering av andra

distansmatris

Vi fortsätter sedan med att uppdatera $D_{2}$ -matrisen till en ny distansmatris $D_{3}$ (se nedan), reducerad i storlek med två rader och två kolumner på grund av klustringen av $(a,b)$ med $c$ och med $e$ :

D_{3}(((a,b),c,e),d)=\min(D_{2}((a,b),d),D_ {2}(c,d),D_{2}(e,d))=\min(31,28,43)=28

Sista steget

Den slutliga $D_{3}$ matrisen är:

	((a,b),c,e)	d
((a,b),c,e)	0	28
d	28	0

Så vi sammanfogar kluster $((a,b),c,e)$ och $d$ .

Låt $r$ beteckna (rot)noden till vilken $((a,b),c,e)$ och $d$ är nu ansluten. Grenarna som förenar $((a,b),c,e)$ och $d$ till $r$ har sedan längder:

$\delta (((a,b),c,e),r)= \delta (d,r)=28/2=14$

Vi härleder den återstående grenlängden:

$\delta (v,r)=\delta (a,r)-\delta (a,v)=\delta (b, r)-\delta (b,v)=\delta (c,r)-\delta (c,v)=\delta (e,r)-\delta (e,v)=14-10.5=3.5$

Enkellänkad dendrogram

Dendrogrammet är nu klart. Det är ultrametriskt eftersom alla tips ( $a$ , $b$ , $c$ , $e$ och $d$ ) är lika långt från $r$ :

$\delta (a,r)=\delta ( b,r)=\delta (c,r)=\delta (e,r)=\delta (d,r)=14$

Dendrogrammet är därför rotat av ${\displaystyle r} ,$ dess djupaste nod.

Andra kopplingar

Den naiva algoritmen för klustring av en länk är i huvudsak densamma som Kruskals algoritm för minimumspännande träd . I enkla länkkluster är emellertid ordningen i vilken kluster bildas viktig, medan det för minsta spännande träd är det viktiga uppsättningen av punkter som bildar avstånd som väljs av algoritmen.

Alternativa kopplingsscheman inkluderar fullständig kopplingsklustring , genomsnittlig kopplingsklustring ( UPGMA och WPGMA ) och Wards metod . I den naiva algoritmen för agglomerativ klustring kan implementering av ett annat länkschema åstadkommas helt enkelt genom att använda en annan formel för att beräkna avstånd mellan kluster i algoritmen. Formeln som bör justeras har markerats med fet text i ovanstående algoritmbeskrivning. Mer effektiva algoritmer som den som beskrivs nedan generaliserar dock inte till alla länkscheman på samma sätt.

Jämförelse av dendrogram erhållna under olika klustringsmetoder från samma avståndsmatris .

Enlänkad klustring	Komplett kopplingsklustring	Genomsnittlig kopplingsklustring: WPGMA	Genomsnittlig kopplingsklustring: UPGMA

Snabbare algoritmer

Den naiva algoritmen för enkellänkningsklustring är lätt att förstå men långsam, med tidskomplexitet $O(n^{3})$ . 1973 föreslog R. Sibson en algoritm med tidskomplexitet $O(n^{2})$ och rymdkomplexitet $O(n)$ (båda optimala) känd som SLINKA. Slinkalgoritmen representerar en klustring på en uppsättning av $n$ numrerade objekt med två funktioner. Dessa funktioner bestäms båda genom att hitta det minsta klustret $C$ som innehåller både objekt $i$ och minst ett objekt med större numrering. Den första funktionen, $\pi$ , mappar objekt $i$ till det största numrerade objektet i kluster $C$ . Den andra funktionen, $\lambda$ , mappar objekt $i$ till avståndet som är associerat med skapandet av kluster $C$ . Att lagra dessa funktioner i två arrayer som mappar varje artikelnummer till dess funktionsvärde tar utrymme ${\displaystyle O(n)} ,$ och denna information är tillräcklig för att bestämma själva klustringen. Som Sibson visar, när ett nytt objekt läggs till i uppsättningen av objekt, kan de uppdaterade funktionerna som representerar den nya enkellänkningsklustringen för den utökade uppsättningen, representerad på samma sätt, konstrueras från den gamla klustringen i tiden $O(n)$ . SLINK-algoritmen går sedan över objekten, en efter en, och lägger till dem i representationen av klustringen.

En alternativ algoritm, som körs inom samma optimala tids- och rumsgränser, är baserad på ekvivalensen mellan den naiva algoritmen och Kruskals algoritm för minsta spännträd. Istället för att använda Kruskals algoritm kan man använda Prims algoritm , i en variant utan binära heaps som tar tid $O(n^{2})$ och mellanslag $O(n )$ för att konstruera det minsta spännträdet (men inte klustringen) för de givna objekten och avstånden. Sedan, att tillämpa Kruskals algoritm på den glesa grafen som bildas av kanterna på det minsta spännträdet producerar själva klustringen i en extra tid $O(n\log n)$ och mellanslag $O(n)$ .

Se även

externa länkar

Länkar som används i Matlab