Seskupování pomocí jednoho propojení - Single-linkage clustering - Wikipedia

v statistika, shlukování s jedním spojením je jednou z několika metod hierarchické shlukování. Je založen na seskupování klastrů způsobem zdola nahoru (aglomerativní klastrování), přičemž v každém kroku kombinuje dva klastry, které obsahují nejbližší dvojici prvků, které dosud nepatří do stejného klastru.

Nevýhodou této metody je, že má tendenci vyrábět dlouhé tenké shluky, ve kterých blízké prvky stejné shluku mají malé vzdálenosti, ale prvky na opačných koncích shluku mohou být od sebe mnohem dále než dva prvky jiných shluků. To může vést k potížím s definováním tříd, které by mohly užitečně rozdělit data.^[1]

Přehled metod shlukování aglomerací

Na začátku procesu shlukování aglomerací je každý prvek v klastru sám o sobě. Klastry jsou poté postupně kombinovány do větších klastrů, dokud všechny prvky neskončí ve stejném klastru. V každém kroku se spojí dva klastry oddělené nejkratší vzdáleností. Funkce použitá k určení vzdálenosti mezi dvěma klastry, známá jako funkce propojení, je to, co odlišuje aglomerativní metody shlukování.

V klastrování s jedním propojením je vzdálenost mezi dvěma klastry určena jedinou dvojicí prvků: těmito dvěma prvky (jeden v každém klastru), které jsou si navzájem nejblíže. Nejkratší z těchto párových vzdáleností, které zůstávají v kterémkoli kroku, způsobí sloučení dvou klastrů, jejichž prvky jsou zahrnuty. Tato metoda je také známá jako shlukování nejbližších sousedů. Výsledek shlukování lze vizualizovat jako dendrogram, který ukazuje sekvenci, ve které byly shluky sloučeny, a vzdálenost, ve které došlo ke každému sloučení.^[2]

Matematicky funkce propojení - vzdálenost D(X,Y) mezi klastry X a Y - je popsán výrazem

{ displaystyle D (X, Y) = min _ {x v X, y v Y} d (x, y),}

kde X a Y jsou libovolné dvě sady prvků považovaných za shluky a d(X,y) označuje vzdálenost mezi dvěma prvky X a y.

Naivní algoritmus

Následující algoritmus je aglomerativní schéma, které vymaže řádky a sloupce v blízké matici, protože staré shluky jsou sloučeny do nových. The ${ displaystyle N krát N}$ proximitní matice ${ displaystyle D}$ obsahuje všechny vzdálenosti ${ displaystyle d (i, j)}$ . Seskupením jsou přiřazena pořadová čísla ${ displaystyle 0,1, ldots, n-1}$ a ${ displaystyle L (k)}$ je úroveň ${ displaystyle k}$ -th shlukování. Shluk s pořadovým číslem m je označen (m) a blízkost mezi klastry ${ displaystyle (r)}$ a ${ displaystyle (s)}$ je označen ${ displaystyle d [(r), (s)]}$ .

Algoritmus jednoduché vazby se skládá z následujících kroků:

Začněte tím, že disjunktní klastrování má úroveň ${ displaystyle L (0) = 0}$ a pořadové číslo ${ displaystyle m = 0}$ .
Najděte nejpodobnější pár klastrů v aktuálním klastru, řekněme pár ${ displaystyle (r), (s)}$ , podle ${ displaystyle d [(r), (s)] = min d [(i), (j)]}$ kde je minimum nad všemi páry klastrů v aktuálním klastru.
Zvyšte pořadové číslo: ${ displaystyle m = m + 1}$ . Sloučit shluky ${ displaystyle (r)}$ a ${ displaystyle (s)}$ do jednoho klastru a vytvoří další klastrování ${ displaystyle m}$ . Nastavte úroveň tohoto shlukování na ${ displaystyle L (m) = d [(r), (s)]}$
Aktualizujte přibližovací matici, ${ displaystyle D}$ odstraněním řádků a sloupců odpovídajících klastrům ${ displaystyle (r)}$ a ${ displaystyle (s)}$ a přidání řádku a sloupce odpovídající nově vytvořenému klastru. Blízkost mezi novým klastrem, označená ${ displaystyle (r, s)}$ a starý shluk ${ displaystyle (k)}$ je definován jako ${ displaystyle d [(r, s), (k)] = min {d [(k), (r)], d [(k), (s)] }}$ .
Pokud jsou všechny objekty v jednom klastru, zastavte. Jinak přejděte na krok 2.

Pracovní příklad

Tento pracovní příklad je založen na a JC69 genetická matice vzdálenosti počítaná z 5S ribozomální RNA seřazení sekvencí pěti bakterií: Bacillus subtilis ( ${ displaystyle a}$ ), Bacillus stearothermophilus ( ${ displaystyle b}$ ), Lactobacillus viridescens ( ${ displaystyle c}$ ), Acholeplasma modicum ( ${ displaystyle d}$ ), a Micrococcus luteus ( ${ displaystyle e}$ ).^[3]^[4]

První krok

První shlukování

Předpokládejme, že máme pět prvků ${ displaystyle (a, b, c, d, e)}$ a následující matice ${ displaystyle D_ {1}}$ párových vzdáleností mezi nimi:

	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

V tomto příkladu ${ displaystyle D_ {1} (a, b) = 17}$ je nejnižší hodnota ${ displaystyle D_ {1}}$ , takže shlukujeme prvky ${ displaystyle a}$ a ${ displaystyle b}$ .

Odhad délky první větve

Nechat ${ displaystyle u}$ označte uzel, ke kterému ${ displaystyle a}$ a ${ displaystyle b}$ jsou nyní připojeni. Nastavení ${ displaystyle delta (a, u) = delta (b, u) = D_ {1} (a, b) / 2}$ zajišťuje, že prvky ${ displaystyle a}$ a ${ displaystyle b}$ jsou ve stejné vzdálenosti od ${ displaystyle u}$ . To odpovídá očekávání ultrametricita hypotéza. Spojení větví ${ displaystyle a}$ a ${ displaystyle b}$ na ${ displaystyle u}$ pak mají délky ${ displaystyle delta (a, u) = delta (b, u) = 17/2 = 8,5}$ (viz závěrečný dendrogram )

První aktualizace matice vzdálenosti

Poté pokračujeme v aktualizaci počáteční proximitní matice ${ displaystyle D_ {1}}$ do nové matice blízkosti ${ displaystyle D_ {2}}$ (viz níže), zmenšená o jeden řádek a jeden sloupec kvůli shlukování ${ displaystyle a}$ s ${ displaystyle b}$ Tučné hodnoty v ${ displaystyle D_ {2}}$ odpovídají novým vzdálenostem, vypočteným zachováním minimální vzdálenost mezi každým prvkem prvního klastru ${ displaystyle (a, b)}$ a každý ze zbývajících prvků:

${ displaystyle D_ {2} ((a, b), c) = min (D_ {1} (a, c), D_ {1} (b, c)) = min (21,30) = 21}$

${ displaystyle D_ {2} ((a, b), d) = min (D_ {1} (a, d), D_ {1} (b, d)) = min (31,34) = 31}$

${ displaystyle D_ {2} ((a, b), e) = min (D_ {1} (a, e), D_ {1} (b, e)) = min (23,21) = 21}$

Kurzíva hodnoty v ${ displaystyle D_ {2}}$ nejsou ovlivněny aktualizací matice, protože odpovídají vzdálenostem mezi prvky, které nejsou zahrnuty v prvním klastru.

Druhý krok

Druhé shlukování

Nyní zopakujeme tři předchozí akce, počínaje novou maticí vzdálenosti ${ displaystyle 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

Tady, ${ displaystyle D_ {2} ((a, b), c) = 21}$ a ${ displaystyle D_ {2} ((a, b), e) = 21}$ jsou nejnižší hodnoty ${ displaystyle D_ {2}}$ , takže se připojíme ke klastru ${ displaystyle (a, b)}$ s prvkem ${ displaystyle c}$ a s prvkem ${ displaystyle e}$ .

Odhad délky druhé větve

Nechat ${ displaystyle v}$ označte uzel, ke kterému ${ displaystyle (a, b)}$ , ${ displaystyle c}$ a ${ displaystyle e}$ jsou nyní připojeni. Z důvodu omezení ultrametricity se větve spojují ${ displaystyle a}$ nebo ${ displaystyle b}$ na ${ displaystyle v}$ , a ${ displaystyle c}$ na ${ displaystyle v}$ , a také ${ displaystyle e}$ na ${ displaystyle v}$ jsou stejné a mají následující celkovou délku: ${ Displaystyle delta (a, proti) = delta (b, v) = delta (c, v) = delta (e, v) = 21/2 = 10,5}$

Dedukujeme délku chybějící větve: ${ displaystyle delta (u, proti) = delta (c, v) - delta (a, u) = delta (c, v) - delta (b, u) = 10,5-8,5 = 2}$ (viz závěrečný dendrogram )

Aktualizace druhé matice vzdálenosti

Poté pokračujeme v aktualizaci ${ displaystyle D_ {2}}$ matice do nové matice vzdálenosti ${ displaystyle D_ {3}}$ (viz níže), zmenšená o dva řádky a dva sloupce kvůli shlukování ${ displaystyle (a, b)}$ s ${ displaystyle c}$ a s ${ displaystyle e}$ :

${ displaystyle 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}$

Poslední krok

Finále ${ displaystyle D_ {3}}$ matice je:

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

Takže se připojujeme ke klastrům ${ displaystyle ((a, b), c, e)}$ a ${ displaystyle d}$ .

Nechat ${ displaystyle r}$ označit (kořenový) uzel, ke kterému ${ displaystyle ((a, b), c, e)}$ a ${ displaystyle d}$ jsou nyní připojeny ${ displaystyle ((a, b), c, e)}$ a ${ displaystyle d}$ na ${ displaystyle r}$ pak mají délky:

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

Odvodíme zbývající délku větve:

${ Displaystyle delta (proti, r) = delta (a, r) - delta (a, proti) = delta (b, r) - delta (b, v) = delta (c, r) - delta (c, v) = delta (e, r) - delta (e, v) = 14-10,5 = 3,5}$

Dendrogram s jednou vazbou

Dendrogram je nyní dokončen. Je to ultrametrické, protože všechny tipy ( ${ displaystyle a}$ , ${ displaystyle b}$ , ${ displaystyle c}$ , ${ displaystyle e}$ , a ${ displaystyle d}$ ) jsou ve stejné vzdálenosti od ${ displaystyle r}$ :

${ displaystyle delta (a, r) = delta (b, r) = delta (c, r) = delta (e, r) = delta (d, r) = 14}$

Dendrogram je tedy zakořeněn pomocí ${ displaystyle r}$ , jeho nejhlubší uzel.

Další vazby

Naivní algoritmus pro shlukování s jedinou vazbou je v podstatě stejný jako Kruskalův algoritmus pro minimální kostry. V klastrování s jedinou vazbou je však důležité pořadí, ve kterém se shluky vytvářejí, zatímco pro minimální kostry je důležitá sada dvojic bodů, které tvoří vzdálenosti zvolené algoritmem.

Mezi alternativní schémata propojení patří kompletní shlukování vazeb, průměrné shlukování vazeb (UPGMA a WPGMA ), a Wardova metoda. V naivním algoritmu pro aglomerativní klastrování může být implementace jiného schématu propojení provedena jednoduše pomocí jiného vzorce pro výpočet meziklastrových vzdáleností v algoritmu. Vzorec, který by měl být upraven, byl zvýrazněn pomocí tučného textu ve výše uvedeném popisu algoritmu. Efektivnější algoritmy, jako je ten, který je popsán níže, se však nezobecňují na všechna schémata propojení stejným způsobem.

Porovnání dendrogramů získaných různými klastrovacími metodami ze stejného matice vzdálenosti.

Seskupování pomocí jednoho propojení.	Kompletní shlukování.	Průměrné shlukování vazeb: WPGMA.	Průměrné shlukování vazeb: UPGMA.

Rychlejší algoritmy

Naivní algoritmus pro klastrování s jedním spojením je snadno pochopitelný, ale pomalý s časovou složitostí ${ displaystyle O (n ^ {3})}$ .^[5] V roce 1973 R. Sibson navrhl algoritmus s časovou složitostí ${ displaystyle O (n ^ {2})}$ a prostorová složitost ${ displaystyle O (n)}$ (oba optimální) známé jako SLINK. Algoritmus slink představuje shlukování na množině ${ displaystyle n}$ číslované položky dvěma funkcemi. Tyto funkce jsou určeny vyhledáním nejmenšího klastru ${ displaystyle C}$ který obsahuje obě položky ${ displaystyle i}$ a alespoň jednu položku s větším číslem. ${ displaystyle pi}$ , mapuje položku ${ displaystyle i}$ na položku s největším číslem v klastru ${ displaystyle C}$ Druhá funkce, ${ displaystyle lambda}$ , mapuje položku ${ displaystyle i}$ na vzdálenost spojenou s vytvořením klastru ${ displaystyle C}$ Uložení těchto funkcí do dvou polí, která mapují každé číslo položky na hodnotu její funkce, zabírá místo ${ displaystyle O (n)}$ a tyto informace jsou dostatečné k určení samotného shlukování. Jak ukazuje Sibson, když je do sady položek přidána nová položka, lze aktualizované funkce představující nové seskupení s jednou vazbou pro rozšířenou sadu, představované stejným způsobem, ze starého seskupení vytvořit v čase ${ displaystyle O (n)}$ . Algoritmus SLINK se poté postupně přetahuje nad položkami a přidává je k reprezentaci shlukování.^[6]^[7]

Alternativní algoritmus, běžící ve stejných optimálních časových a prostorových mezích, je založen na ekvivalenci mezi naivním algoritmem a Kruskalovým algoritmem pro minimální kostry. Místo použití Kruskalova algoritmu lze použít Primův algoritmus, ve variantě bez binárních hromad, která vyžaduje čas ${ displaystyle O (n ^ {2})}$ a vesmír ${ displaystyle O (n)}$ zkonstruovat minimální kostru (ale ne shlukování) daných položek a vzdáleností. Poté aplikace Kruskalova algoritmu na řídký graf tvořený hranami minimálního kostry vytvoří vlastní shlukování v dalším čase ${ displaystyle O (n log n)}$ a vesmír ${ displaystyle O (n)}$ .^[8]

Viz také

Reference

^ Everitt B (2011). Shluková analýza. Chichester, West Sussex, Velká Británie: Wiley. ISBN 9780470749913.
^ Legendre P, Legendre L (1998). Numerická ekologie. Vývoj environmentálního modelování. 20 (Second English ed.). Amsterdam: Elsevier.
^ Erdmann VA, Wolters J (1986). "Sbírka publikovaných 5S, 5,8S a 4,5S ribosomálních RNA sekvencí". Výzkum nukleových kyselin. 14 Suppl (Suppl): r1-59. doi:10.1093 / nar / 14.suppl.r1. PMC 341310. PMID 2422630.
^ Olsen GJ (1988). "Fylogenetická analýza pomocí ribozomální RNA". Metody v enzymologii. 164: 793–812. doi:10.1016 / s0076-6879 (88) 64084-5. PMID 3241556.
^ Murtagh F, Contreras P (2012). Msgstr "Algoritmy pro hierarchické shlukování: přehled". Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. Wiley Online knihovna. 2 (1): 86–97. doi:10,1002 / šířka 53.
^ Sibson R (1973). „SLINK: optimálně efektivní algoritmus pro metodu clusteru s jedním odkazem“ (PDF). Počítačový deník. Britská počítačová společnost. 16 (1): 30–34. doi:10.1093 / comjnl / 16.1.30.
^ Gan G (2007). Shlukování dat: teorie, algoritmy a aplikace. Philadelphia, Pa. Alexandria, Va: SIAM, Americká statistická asociace pro společnost pro průmyslovou a aplikovanou matematiku. ISBN 9780898716238.
^ Gower JC, Ross GJ (1969). "Minimum spanning trees and single linkge cluster analysis". Journal of the Royal Statistical Society, Series C. 18 (1): 54–64. doi:10.2307/2346439. JSTOR 2346439. PAN 0242315..

externí odkazy

Propojení použitá v Matlabu

[Everitt-1] Everitt B (2011). Shluková analýza. Chichester, West Sussex, Velká Británie: Wiley. ISBN 9780470749913.

[2] Legendre P, Legendre L (1998). Numerická ekologie. Vývoj environmentálního modelování. 20 (Second English ed.). Amsterdam: Elsevier.

[Erdmann1986-3] Erdmann VA, Wolters J (1986). "Sbírka publikovaných 5S, 5,8S a 4,5S ribosomálních RNA sekvencí". Výzkum nukleových kyselin. 14 Suppl (Suppl): r1-59. doi:10.1093 / nar / 14.suppl.r1. PMC 341310. PMID 2422630.

[Olsen1988-4] Olsen GJ (1988). "Fylogenetická analýza pomocí ribozomální RNA". Metody v enzymologii. 164: 793–812. doi:10.1016 / s0076-6879 (88) 64084-5. PMID 3241556.

[5] Murtagh F, Contreras P (2012). Msgstr "Algoritmy pro hierarchické shlukování: přehled". Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. Wiley Online knihovna. 2 (1): 86–97. doi:10,1002 / šířka 53.

[6] Sibson R (1973). „SLINK: optimálně efektivní algoritmus pro metodu clusteru s jedním odkazem“ (PDF). Počítačový deník. Britská počítačová společnost. 16 (1): 30–34. doi:10.1093 / comjnl / 16.1.30.

[7] Gan G (2007). Shlukování dat: teorie, algoritmy a aplikace. Philadelphia, Pa. Alexandria, Va: SIAM, Americká statistická asociace pro společnost pro průmyslovou a aplikovanou matematiku. ISBN 9780898716238.

[8] Gower JC, Ross GJ (1969). "Minimum spanning trees and single linkge cluster analysis". Journal of the Royal Statistical Society, Series C. 18 (1): 54–64. doi:10.2307/2346439. JSTOR 2346439. PAN 0242315..

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]