Porównywanie klastrów: Indeks Rand a zmienność informacji

Zastanawiałem się, czy ktokolwiek miałby wgląd lub intuicję za różnicą między zmiennością informacji a indeksem Rand do porównywania klastrów.

Przeczytałem artykuł „ Porównywanie klastrów - odległość oparta na informacjach ” autorstwa Marii Melii (Journal of Multivariate Analysis, 2007), ale poza zauważeniem różnicy w definicjach, nie rozumiem, co to za odmiana informacji przechwytuje, że indeks rand nie przechwytuje.

Różnica między tymi dwiema metodami jest subtelna. Najlepszym sposobem, aby o tym pomyśleć, jest wzięcie pod uwagę sieci zdefiniowanej przez operację scalania-podziału w klastrach. Obie te miary można zrekonstruować, definiując funkcję w klastrowaniu, a następnie określając odległość między dwoma klastrami za pomocą wzoru:$f$

gdzie C ∧ C ′ jest połączeniem dwóch skupień w sieci.

Teraz niech i niech n i = | C i | . Ustawienie f ( C ) = ∑ n 2 i daje indeks rand, a ustawienie f ( C ) = ∑ n i log n i daje VI.$C = \{ C_1, C_2, \ldots, C_k\}$$n_i = |C_i|$$f(C) = \sum n_i^2$$f(C) = \sum n_i \log n_i$

Moim zdaniem istnieją ogromne różnice. Na wskaźnik Rand duży wpływ ma ziarnistość klastrów, na których działa. W dalszej części wykorzystam odległość Mirkina, która jest skorygowaną formą indeksu Rand (łatwa do zauważenia, ale patrz np. Meila). Wykorzystam również odległość podziału / łączenia, o której wspomniałem również w niektórych artykułach Meili (zastrzeżenie: zaproponowałem odległość podziału / łączenia). Załóżmy, że wszechświat składa się ze stu elementów. Użyję opcji Góra, aby oznaczyć klastrowanie za pomocą pojedynczego klastra zawierającego wszystkie elementy, Dolnej, aby oznaczyć klastrowanie, w której wszystkie węzły znajdują się w osobnych zestawach singletonów, Lewej, aby oznaczyć grupowanie {{1,2, .. 10}, {11, 12..20}, {21,22..30}, ..., {91,92, .. 100}} i prawo do oznaczenia grupowania {{1,11, .. 91}, {2, 12, .. 92}, {3,13, .. 93}, ..., {10,20, .. 100}} .

Moim zdaniem, Dół i Góra są spójnymi (zagnieżdżającymi się) klastrami, podczas gdy lewa i prawa są maksymalnie sprzecznymi klastrami. Odległości od wymienionych wskaźników dla tych dwóch porównań par są następujące:

               Top-Bottom     Left-Right 

Mirkin            9900          1800
VI                4.605         4.605
Split/join        99            180

Wynika z tego, że Mirkin / Rand rozważa spójną parę góra-dół znacznie dalej od siebie niż maksymalnie sprzeczna para lewa-prawa. Jest to skrajny przykład ilustrujący tę kwestię, ale na Mirkin / Rand na ogół bardzo duży wpływ ma ziarnistość klastrów, na których działa. Powodem tego jest kwadratowa zależność między tą metryką a rozmiarem klastra, wyjaśniona faktem, że bierze się pod uwagę liczenie par węzłów. W efekcie odległość Mirkina to odległość Hamminga między zestawami krawędziowymi złączy kompletnych wykresów wywołanych przez skupienia (myślę, że jest to odpowiedź na twoje pytanie).

Jeśli chodzi o różnice między zmiennością informacji a podziałem / łączeniem, pierwsza jest bardziej wrażliwa na pewne sytuacje konfliktowe, jak wykazała Meila. Oznacza to, że podział / łączenie uwzględnia tylko najlepsze dopasowanie dla każdego klastra i ignoruje fragmentację, która może wystąpić w pozostałej części tego klastra, podczas gdy zmienność informacji to wykryje. To powiedziawszy, Split / Join jest łatwo interpretowalny jako liczba węzłów, które należy przenieść, aby uzyskać jeden klaster od drugiego , i w tym sensie jego zasięg jest łatwiejszy do zrozumienia; w praktyce kwestia fragmentacji może również nie być tak powszechna.

Każda z tych miar może być utworzona jako suma dwóch odległości, a mianowicie odległości od każdego z dwóch klastrów do ich największej wspólnej podgrupowania. Uważam, że często korzystna jest praca z tymi oddzielnymi częściami, a nie tylko ich sumą. Powyższa tabela staje się następnie:

               Top-Bottom     Left-Right 

Mirkin          0,9900          900,900
VI              0,4.605       2.303,2.303
Split/join      0,99             90,90

Relacja subskrypcji między górą i dołem staje się natychmiast jasna. Często bardzo przydatna jest wiedza, czy dwa klastry są spójne (tj. Jedno (prawie) jest podgrupą drugiego), jako rozluźnienie pytania, czy są blisko . Grupowanie może być dość odległe od standardu złota, ale nadal być spójne lub prawie spójne. W takim przypadku może nie być żadnego powodu, aby uważać klastrowanie za złe w odniesieniu do tego standardu złota. Oczywiście, trywialne klastry Góra i Dół będą zgodne z każdym klastrowaniem, więc należy to wziąć pod uwagę.

Wreszcie uważam, że takie wskaźniki, jak Mirkin, Zmienność informacji i Podział / Dołącz to naturalne narzędzia do porównywania klastrów. W przypadku większości zastosowań metody, które próbują uwzględnić statystyczną niezależność i skorygować przypadek, są zbyt wymyślone i zaciemniają, a nie wyjaśniają.

Drugi przykład Rozważ następujące pary klastrów: C1 = {{1, 2, 3, 4, 5, 6, 7, 8}, {9, 10, 11, 12, 13, 14, 15, 16}} z C2 = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}}

i C3 = {{1, 2, 3, 4}, {5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}} z {{1, 2, 3 , 4}, {5, 6, 7, 8, 9, 10, 11, 12}, {13, 14, 15, 16}}

Tutaj C2 można utworzyć z C1 poprzez przesunięcie węzłów 9 i 10, a C3 można utworzyć z C3 poprzez przesunięcie węzłów 11 i 12. Obie zmiany są identyczne („przenieś dwa węzły”), z wyjątkiem tego, że rozmiary zaangażowanych klastrów różnią się . Tabela metryk klastrowania dla tych dwóch przykładów jest następująca:

            C1-C2         C3-C4

Mirkin       56            40 
VI            0.594         0.520
Split/Join    4             4

Można zauważyć, że na rozmiary klastra wpływ mają Mirkin / Rand i zmienność informacji (i w większym stopniu Mirkin; będzie to bardziej wyraźne, gdy rozmiary klastra będą się różnić), podczas gdy odległość podziału / łączenia nie jest (jego wartość wynosi 4 ponieważ „przenosi” węzły z jednego klastra do drugiego zawsze za pośrednictwem największej wspólnej podgrupowania). W zależności od okoliczności może to być pożądana cecha. Warto pamiętać o prostej interpretacji podziału / łączenia (liczby węzłów do przeniesienia) i jej niezależności od wielkości klastra. Pomiędzy Mirkinem a odmianą informacji myślę, że ta ostatnia jest zdecydowanie lepsza.