Klastrowanie z pojedynczym powiązaniem

W statystyce klastrowanie z pojedynczym powiązaniem jest jedną z kilku metod hierarchicznego grupowania . Polega ona na grupowaniu klastrów w sposób oddolny (grupowanie aglomeracyjne), na każdym etapie łącząc dwa klastry, które zawierają najbliższą parę elementów nie należących jeszcze do tego samego klastra.

Ta metoda ma tendencję do tworzenia długich, cienkich klastrów, w których pobliskie elementy tej samej gromady mają niewielkie odległości, ale elementy na przeciwległych końcach gromady mogą być znacznie dalej od siebie niż dwa elementy innych gromad. W przypadku niektórych klas danych może to prowadzić do trudności w zdefiniowaniu klas, które mogłyby z pożytkiem podzielić dane. Jednak jest popularna w astronomii do analizy gromad galaktyk , które często mogą obejmować długie łańcuchy materii; w tej aplikacji jest również znany jako algorytm znajomych znajomych.

Przegląd metod grupowania aglomeracyjnego

Na początku procesu grupowania aglomeracyjnego każdy element jest we własnym klastrze. Klastry są następnie sekwencyjnie łączone w większe klastry, aż wszystkie elementy znajdą się w tym samym klastrze. Na każdym etapie dwa skupienia oddzielone najkrótszą odległością są łączone. Funkcja używana do określenia odległości między dwoma klastrami, znana jako funkcja łączenia , jest tym, co odróżnia aglomeracyjne metody grupowania.

W klastrach z pojedynczym powiązaniem odległość między dwoma klastrami jest określana przez pojedynczą parę elementów: te dwa elementy (po jednym w każdym klastrze), które są najbliżej siebie. Najkrótsza z tych odległości parami, które pozostają na dowolnym kroku, powoduje połączenie dwóch klastrów, których elementy są zaangażowane. Metoda ta jest również znana jako grupowanie najbliższego sąsiada . Wynik grupowania można zwizualizować jako dendrogram , który pokazuje kolejność łączenia klastrów oraz odległość, w jakiej miało miejsce każde łączenie.

Matematycznie funkcja sprzężenia – odległość D ( X , Y ) między skupieniami X i Y – jest opisana wyrażeniem

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

gdzie X i Y to dowolne dwa zestawy elementów uważane za klastry, a d ( x , y ) oznacza odległość między dwoma elementami x i y .

Algorytm naiwny

Poniższy algorytm jest schematem aglomeracyjnym , który usuwa wiersze i kolumny w macierzy bliskości, gdy stare klastry są łączone w nowe. Macierz bliskości $(i,$ wszystkie odległości $Displaystyle$ $jot$ } Skupieniom przypisuje się numery sekwencyjne ${\ Displaystyle 0,1, \ ldots, n-1}$ a $}$ k $k$ . Klaster o numerze kolejnym m $}$ oznaczony ( m ) $d[(r),(s)]$ a bliskość między klastrami i ${\ Displaystyle (s$ jest oznaczona .

Algorytm pojedynczego powiązania składa się z następujących kroków:

$L(0)=0$ grupowania mającego poziom kolejny ${\ displaystyle m =$ .
Znajdź najbardziej podobną parę klastrów w bieżącym skupieniu, powiedzmy para ${\ Displaystyle (r), (s)}$ , zgodnie z ${\ Displaystyle d [(r), (s)] = \ min d [(i), (j)]}$ gdzie minimum dotyczy wszystkich par klastrów w bieżącym grupowaniu.
Zwiększ numer kolejny: ${\ Displaystyle m = m + 1}$ . Połącz klastry ${\ displaystyle (r)}$ i ${\ displaystyle (s)}$ w jeden klaster, aby utworzyć następny klaster ${\ displaystyle m}$ . Ustaw poziom tego grupowania na ${\ Displaystyle L (m) = re [(r), (s)]}$
Zaktualizuj macierz bliskości , usuwając wiersze i kolumny odpowiadające klastrom $(r)}$ $Displaystyle$ i $Displaystyle (s)}$ i dodając wiersz i kolumnę odpowiadające nowo powstały klaster. Bliskość między nowym klastrem, oznaczonym jako ${\ Displaystyle (r, s)}$ i starym klastrem ${\ Displaystyle (k)}$ jest zdefiniowana jako ${\ Displaystyle d [(r, s), (k)] =\min\{d[(k),(r)],d[(k),(s)]\}}$ .
Jeśli wszystkie obiekty znajdują się w jednym skupieniu, zatrzymaj się. W przeciwnym razie przejdź do kroku 2.

Działający przykład

Ten przykład roboczy jest oparty na macierzy odległości genetycznej JC69 obliczonej na podstawie dopasowania sekwencji rybosomalnego RNA 5S pięciu bakterii: Bacillus subtilis ( za $\ displaystyle a}$ ), Bacillus stearothermophilus ( ${\ displaystyle b}$ ), Lactobacillus viridescens ( $a} \ displaystyle c}$ ), Acholeplasma modicum ( ${\ displaystyle d}$ ) i Micrococcus luteus ( ${\ displaystyle e}$ ).

Pierwszy krok

Pierwsze skupienie

Załóżmy, że mamy pięć elementów ${\ Displaystyle (a, b, c, d, e)}$ macierz parami re $\ displaystyle D_ {1}}$ odległości między nimi:

	A	B	C	D	mi
A	0	17	21	31	23
B	17	0	30	34	21
C	21	30	0	28	39
D	31	34	28	0	43
mi	23	21	39	43	0

W tym przykładzie ${\ Displaystyle D_ {1} (a, b) = 17}$ $najniższą$ , więc grupujemy elementy $a$ i $b$ .

Oszacowanie długości pierwszej gałęzi

Niech $u$ oznacza węzeł, z którym są teraz połączone $a$ i $b$ . δ ${1} (a, b)/2}$ zapewnia, że elementy $a$ i $b$ są jednakowo oddalone od $u$ . Odpowiada to oczekiwaniom tzw ultrametryczności . Gałęzie łączące $a$ i $b$ z $u$ mają wtedy długości ${\ Displaystyle \ delta (a, u) = \ delta (b, u) = 17 /2=8.5}$ ( zobacz końcowy dendrogram )

Aktualizacja pierwszej macierzy odległości

Następnie przystępujemy do aktualizacji początkowej macierzy bliskości $\$ nowej macierzy bliskości $D_ {2}$ patrz poniżej), zmniejszonej o jeden wiersz i jedną kolumnę z powodu re 2 { grupowanie $a$ z $b$ . Pogrubione wartości w odpowiadają nowym odległościom, obliczonym przy zachowaniu minimalnej odległości między każdym elementem pierwszego klastra ${\ displaystyle D_ {2}}$ ${\ Displaystyle (a, b)}$ i każdy z pozostałych elementów:

{\ Displaystyle {\ rozpocząć {tablica} {llllllll} 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{tablica}}}

Aktualizacja macierzy nie ma wpływu na wartości $zapisane kursywą,$

Drugi krok

Drugie skupienie

Powtarzamy teraz trzy poprzednie czynności, zaczynając od nowej macierzy odległości : ${\ displaystyle D_ {2}}$ :

	(a,b)	C	D	mi
(a,b)	0	21	31	21
C	21	0	28	39
D	31	28	0	43
mi	21	39	43	0

Tutaj ${\ Displaystyle D_ {2} ((a, b), c) = 21}$ i ${\ displaystyle D_ {2} ((a, b), e) = 21}$ to najniższe wartości $b) }$ więc dołączamy do klastra $($ z elementem $c$ iz elementem $e$ .

Oszacowanie długości drugiej gałęzi

Niech $v$ oznacza węzeł $,$ do teraz $c$ i $e$ Ze względu na ograniczenie ultrametryczne, gałęzie łączące $a$ lub $b$ z $v$ i $c$ z $v$ , a także $e$ z $v$ są równe i mają następującą całkowitą długość:

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

Wydedukujemy brakującą długość gałęzi:

{\ Displaystyle \ delta (u, v) =\delta (c,v)-\delta (a,u)=\delta (c,v)-\delta (b,u)=10.5-8.5=2} ( patrz

końcowy dendrogram )

Aktualizacja drugiej matrycy odległości

Następnie przystępujemy do aktualizacji macierzy do nowej macierzy odległości ${2}$ $}$ poniżej), zmniejszonej o dwa wiersze i dwie kolumny z powodu grupowania re 2 {\ z ${\ Displaystyle (a, b)}$ z $c$ iz $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}

Ostatni krok

Ostateczna macierz to: ${\ displaystyle D_ {3}}$

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

Łączymy więc klastry ${\ Displaystyle ((a, b), c, e)}$ re $\ Displaystyle d}$ .

Niech ${\ displaystyle r}$ oznacza węzeł (główny), do którego są teraz ${\ Displaystyle ((a, b), c,$ e $}$ połączony. Gałęzie łączące ${\ Displaystyle ((a, b), c, e)}$ re $\ Displaystyle d}$ do ${\ Displaystyle R}$ mają wtedy długości:

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

Dedukujemy pozostałą długość gałęzi:

${\ Displaystyle \ 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}$

Dendrogram pojedynczego wiązania

Dendrogram jest już gotowy. Jest ultrametryczny, ponieważ wszystkie wskazówki ( i ${\ displaystyle a}$ $r}$ b $\ displaystyle b}$ , ${\ displaystyle c}$ , $mi {\ displaystyle e}$ re $displaystyle d}$ $\$ ) są w równej odległości od :

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

Dendrogram jest zatem zakorzeniony w $węźle$ .

Inne powiązania

Algorytm naiwny dla grupowania pojedynczych wiązań jest zasadniczo taki sam jak algorytm Kruskala dla minimalnych drzew rozpinających . Jednak w klastrowaniu z pojedynczym powiązaniem ważna jest kolejność tworzenia klastrów, podczas gdy w przypadku minimalnych drzew rozpinających liczy się zbiór par punktów tworzących wybrane przez algorytm odległości.

Alternatywne schematy powiązań obejmują pełne klastrowanie powiązań , średnie klastrowanie powiązań ( UPGMA i WPGMA ) oraz metodę Warda . W naiwnym algorytmie grupowania aglomeracyjnego implementację innego schematu powiązań można osiągnąć po prostu za pomocą innego wzoru do obliczania odległości między klastrami w algorytmie. Formuła, którą należy dostosować, została wyróżniona pogrubioną czcionką w powyższym opisie algorytmu. Jednak bardziej wydajne algorytmy, takie jak opisany poniżej, nie uogólniają wszystkich schematów powiązań w ten sam sposób.

Porównanie dendrogramów uzyskanych różnymi metodami grupowania z tej samej macierzy odległości .

Klastrowanie z pojedynczym powiązaniem	Klastrowanie z pełnym powiązaniem	Średnie grupowanie powiązań: WPGMA	Średnie grupowanie powiązań: UPGMA

Szybsze algorytmy

Naiwny algorytm grupowania z pojedynczym powiązaniem jest łatwy do zrozumienia, ale powolny i ma złożoność czasową. ${\ Displaystyle O (n ^ {3})}$ . W 1973 $)}$ R. Sibson zaproponował algorytm ze złożonością czasową $($ złożonością przestrzenną (oba optymalne) znany jako PORONIONY PŁÓD. Algorytm slink reprezentuje grupowanie na zbiorze ${\ displaystyle n}$ ponumerowane elementy za pomocą dwóch funkcji. Obie te funkcje są określane przez znalezienie najmniejszego klastra $.$ $który$ zawiera zarówno element i co najmniej jeden element o większej liczbie Pierwsza funkcja, $odwzorowuje$ element element o największym numerze w klastrze do $pi}$ $\$ . Druga funkcja, $}$ element ${\ displaystyle \ lambda$ do odległości związanej z tworzeniem klastra do $\ displaystyle C}$ . Przechowywanie $,$ zajmuje miejsce , a ta jest wystarczająca do określenia samego klastrowania. Jak pokazuje Sibson, gdy nowy element jest dodawany do zbioru elementów, zaktualizowane funkcje reprezentujące nowe klastrowanie z pojedynczym powiązaniem dla zbioru rozszerzonego, reprezentowanego w ten sam sposób, można zbudować ze starego klastrowania w czasie ${\ Displaystyle O (n)}$ . Algorytm SLINK następnie przechodzi przez elementy, jeden po drugim, dodając je do reprezentacji grupowania.

Alternatywny algorytm, działający w tych samych optymalnych granicach czasowych i przestrzennych, opiera się na równoważności między algorytmem naiwnym a algorytmem Kruskala dla minimalnych drzew rozpinających. Zamiast używać algorytmu Kruskala, można użyć $Displaystyle O (n )}$ w bez stert binarnych, która wymaga czasu przestrzeni ${$ skonstruować minimalne drzewo rozpinające (ale nie grupowanie) danych elementów i odległości. Następnie zastosowanie algorytmu Kruskala do rzadkiego wykresu utworzonego przez krawędzie minimalnego drzewa rozpinającego powoduje samo skupienie w dodatkowym czasie i przestrzeni ${\ Displaystyle O (n)}$ $(n \ log n$ .

Zobacz też

Linki zewnętrzne

Powiązania używane w Matlabie