Zastanawiałem się nad napisaniem posta na blogu na temat tej ciekawej analizy Kleinberga (2002), która bada trudność tworzenia klastrów. Kleinberg przedstawia trzy pozornie intuicyjne desiderata funkcji klastrowania, a następnie udowadnia, że ​​taka funkcja nie istnieje. Istnieje wiele algorytmów grupowania, które spełniają dwa z trzech kryteriów; jednak żadna funkcja nie może spełnić wszystkich trzech warunków jednocześnie.

W skrócie i nieformalnie trzy zarysowane przez niego dezyderaty to:

• Niezmienność skali : jeśli przekształcimy dane, aby wszystko było równo rozłożone we wszystkich kierunkach, wynik grupowania nie powinien się zmienić.
• Spójność : jeśli rozciągniemy dane, aby zwiększyć odległości między klastrami i / lub zmniejszyć odległości w klastrach, wynik grupowania nie powinien się zmienić.
• Bogactwo : funkcja klastrowania powinna teoretycznie być w stanie wygenerować dowolną partycję / klastrowanie punktów danych (przy braku znajomości parowej odległości między dowolnymi dwoma punktami)

Pytania:

(1) Czy istnieje dobra intuicja, geometryczny obraz, który może wykazać niespójność między tymi trzema kryteriami?

(2) Odnosi się to do technicznych szczegółów dokumentu. Musisz przeczytać powyższy link, aby zrozumieć tę część pytania.

W artykule dowód na twierdzenie 3.1 jest nieco trudny do naśladowania w niektórych punktach. Utknąłem w: „Niech $f$ . Będzie funkcją klastrów, które spełnia Spójność Twierdzimy, że dla każdej partycji $\Gamma \in \text{Range}(f)$ istnieją dodatnich liczb rzeczywistych < b takie, że para ( , b ) jest Γ - zmuszanie ”.$a < b$$(a, b)$$\Gamma$

Nie rozumiem, jak to może być w przypadku ... Czy partycja poniżej kontrprzykładu gdzie $a > b$ (tj. Minimalna odległość między klastrami jest większa niż maksymalna odległość w klastrach)?

Edycja: to oczywiście nie jest kontrprzykład, myliłem się (patrz odpowiedzi).

• Ackerman i Ben-David (2009). Miary jakości klastrowania: zestaw roboczy aksjomatów do grupowania
  • Wskazuje pewne problemy z aksjomatem „spójności”

Tak czy inaczej, każdy algorytm grupowania opiera się na pewnym pojęciu „bliskości” punktów. Intuicyjnie wydaje się, że można albo użyć względnego (niezmiennego w skali) pojęcia, albo bezwzględnego (spójnego) pojęcia bliskości, ale nie obu .

Najpierw spróbuję to zilustrować przykładem, a następnie powiem, jak ta intuicja pasuje do twierdzenia Kleinberga.

Ilustrujący przykład

Załóżmy, że mamy dwa zestawy i S 2 po 270 punktów każdy, ułożone w płaszczyźnie w następujący sposób:$S_1$$S_2$$270$

$\hskip{6em}$

Na żadnym z tych zdjęć możesz nie zobaczyć punktów, ale to tylko dlatego, że wiele punktów jest bardzo blisko siebie. Po powiększeniu widzimy więcej punktów:$270$

$\hskip{3em}$

Prawdopodobnie spontanicznie zgodzisz się, że w obu zestawach danych punkty są ułożone w trzy klastry. Okazuje się jednak, że jeśli powiększysz którykolwiek z trzech klastrów , zobaczysz:$S_2$

$\hskip{3em}$

Jeśli wierzysz w absolutne pojęcie bliskości lub w spójność, nadal będziesz to utrzymywał, niezależnie od tego, co właśnie zobaczyłeś pod mikroskopem, składa się tylko z trzech skupisk. Rzeczywiście jedyna różnica między $S_2$ i S 2 jest to, że w obrębie każdej gromady niektóre punkty są teraz bliżej siebie. Jeśli natomiast wierzysz we względne pojęcie bliskości lub w niezmienność skali, będziesz skłonny argumentować, że S 2 nie składa się z 3, ale z 3 × 3 = 9 klastrów. Żaden z tych punktów widzenia nie jest zły, ale musisz dokonać wyboru w taki czy inny sposób.$S_1$$S_2$$S_2$$3$$3×3 = 9$

Przypadek niezmienności izometrii

Jeśli porównasz powyższą intuicję z twierdzeniem Kleinberga, przekonasz się, że są one nieco sprzeczne. Rzeczywiście, twierdzenie Kleinberga wydaje się mówić, że możesz osiągnąć niezmienność skali i spójność jednocześnie, o ile nie zależy ci na trzeciej własności zwanej bogactwem. Jednak bogactwo nie jest jedyną własnością, którą tracisz, jeśli jednocześnie nalegasz na niezmienność skali i spójność. Tracisz także inną, bardziej fundamentalną właściwość: niezmienność izometryczną. To własność, której nie chciałbym poświęcić. Ponieważ nie pojawia się w pracy Kleinberga, zastanowię się nad tym przez chwilę.

Krótko mówiąc, algorytm grupowania jest niezmienny w przypadku izometrii, jeśli jego wynik zależy tylko od odległości między punktami, a nie od niektórych dodatkowych informacji, takich jak etykiety, które dołączasz do punktów lub od kolejności, którą narzucasz punktom. Mam nadzieję, że to brzmi jak bardzo łagodny i bardzo naturalny stan. Wszystkie algorytmy omówione w pracy Kleinberga są niezmienne izometrycznie, z wyjątkiem algorytmu pojedynczego wiązania z warunkiem zatrzymania klastra. Zgodnie z opisem Kleinberga, algorytm ten wykorzystuje porządek leksykograficzny punktów, więc jego wynik może rzeczywiście zależeć od sposobu ich oznaczenia. Na przykład dla zestawu trzech równo odległych punktów wynik algorytmu pojedynczego połączenia z $k$$2$- warunek zatrzymania klastra da różne odpowiedzi w zależności od tego, czy oznaczysz swoje trzy punkty jako „kot”, „pies”, „mysz” (c <d <m) lub jako „Tom”, „Spike”, „Jerry” (J <S <T):

$\hskip{6em}$

To nienaturalne zachowanie można oczywiście łatwo naprawić, zastępując $k$ -cluster zatrzymanie stan z „ -cluster stan zatrzymania”. Chodzi o to, aby po prostu nie zerwać więzi między równo odległymi punktami i przestać scalać klastry, gdy tylko osiągniemy co najmniej k klastrów. Ten naprawiony algorytm nadal będzie generował $(≤ k)$ $k$$k$ klastrów i będzie niezmienny izometrycznie i niezmiennie w skali. W zgodzie z powyższą intuicją nie będzie ona jednak spójna.

Aby precyzyjnie zdefiniować niezmienność izometrii, pamiętaj, że Kleinberg definiuje algorytm grupowania na skończonym zestawie jako mapę, która przypisuje każdą metrykę na $S$$S$ partycję : Γ : { metryki na  S } → { partycje  S $S$ isometry i pomiędzy dwie metryki d i d ' w S jest permutacją i : S → S tak, że d ' ( I ( x ) , i ( Y ) ) = d ( x , y ) dla wszystkich punkty x i y w S .

Definicja: Algorytm grupowania jest niezmiennikiem izometrii, jeśli spełnia następujący warunek: dla każdej metryki d i d ′ i każdej izometrii i między nimi punkty i ( x ) i i ( y ) leżą w tej samej grupie Γ ( d ′$Γ$$d$$d'$$i$$i(x)$$i(y)$$Γ(d')$ , wtedy i tylko wtedy, gdy pierwotne punkty i y leżą w tym samym klastrze y ( d ) .$x$$y$$Γ(d)$

Myśląc o algorytmach grupowania, często identyfikujemy zestaw abstrakcyjny z konkretnym zestawem punktów na płaszczyźnie lub w innej przestrzeni otoczenia i wyobrażamy sobie różnicowanie metryki na S jako przesuwanie punktów S wokół. Rzeczywiście, jest to punkt widzenia, który przyjęliśmy w powyższym ilustracyjnym przykładzie. W tym kontekście niezmienność izometrii oznacza, że ​​nasz algorytm grupowania jest niewrażliwy na rotacje, odbicia i tłumaczenia.$S$$S$$S$

$\hskip{6em}$

Wariant twierdzenia Kleinberga

Podaną powyżej intuicję ujmuje następujący wariant twierdzenia Kleinberga.

Twierdzenie: Nie ma nietrywialnego algorytmu grupowania niezmiennego względem izometrii, który byłby jednocześnie spójny i niezmienny dla skali.

Tutaj przez trywialny algorytmu grupowania, mam na myśli jedną z dwóch następujących algorytmów:

1. algorytm, który przypisuje każdej metryki na dyskretnej partycji, w której każdy klaster składa się z jednego punktu,$S$

2. algorytm, który przypisuje każdą metrykę na partycji lump, składający się z jednego klastra.$S$

Twierdzenie jest takie, że te głupie algorytmy są jedynymi dwoma algorytmami niezmienniczymi w izometrii, które są zarówno spójne, jak i niezmienne w skali.

Dowód: Niech będzie skończonym zbiorem, na którym ma działać nasz algorytm Γ . Niech d ₁ będzie metryką na S, w której dowolna para różnych punktów ma odległość jednostkową (tj. D ₁ ( x , y ) = 1 dla wszystkich x ≠ y w S ). Ponieważ Γ jest niezmienną izometrią, istnieją tylko dwie możliwości dla Γ ( d ₁ ) : albo Γ ( d ₁ ) jest dyskretną partycją, albo$S$$Γ$$d₁$$S$$d₁(x,y) = 1$$x ≠ y$$S$$Γ$$Γ(d₁)$$Γ(d₁)$ to partycja ryczałtowa. Spójrzmy najpierw na przypadek, gdy Γ ( d ₁ ) jest partycją dyskretną. Biorąc pod uwagę dowolną metrykę d na S , możemy przeskalować ją tak, aby wszystkie pary punktów miały odległość ≥ 1 pod d . Następnie, zgodnie z konsekwencją, stwierdzamy, że Γ ( d ) = Γ ( d ₁ ) . Tak więc w tym przypadku Γ jest trywialnym algorytmem, który przypisuje dyskretną partycję do każdej metryki. Po drugie, rozważmy przypadek, w którym Γ$Γ(d₁)$$Γ(d₁)$$d$$S$$≥ 1$$d$$Γ(d) = Γ(d₁)$$Γ$ to partycja ryczałtowa. Możemy przeskalować dowolną metrykę d na S , aby wszystkie pary punktów miały odległość ≤ 1 , więc znowu spójność oznacza, że Γ ( d ) = Γ ( d ₁ ) . Więc Γ jest w tym przypadku również banalne. ∎$Γ(d₁)$$d$$S$$≤ 1$$Γ(d)=Γ(d₁)$$Γ$

Oczywiście, dowód ten jest bardzo bliski duchowi dowodu Margarety Ackerman na oryginalne twierdzenie Kleinberga, omówione w odpowiedzi Alexa Williamsa.

Oto intuicja, którą wymyśliłem (fragment z mojego posta na blogu tutaj ).

$d_1$$d_2$$d_3$$d_2$$d_3$$d_1$$d_1 \rightarrow d_3$$d_2 \rightarrow d_3$