Grupowanie - intuicja stojąca za twierdzeniem Kleinberga o niemożliwości

17

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 ΓRange(f) istnieją dodatnich liczb rzeczywistych < b takie, że para ( , b ) jest Γ - zmuszanie ”.a<b(a,b)Γ

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)?

kontrprzykład?

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


Inne dokumenty:

Alex Williams
źródło
W odniesieniu do „spójności”: ta cecha jest intuicyjnie pożądana tylko wtedy, gdy klastry są już dobrze rozdzielone. Gdy nie są, istnieje problem z liczbą klastrów w danych - do analizy, ponieważ nie jest nadzorowana, jest to pytanie. Wówczas normalne jest oczekiwanie, że w miarę stopniowego zwiększania odległości między klastrami (tak jak zostały one przez Ciebie wygenerowane) analiza zmienia przypisania, które wykonuje podczas procesu klastrowania.
ttnphns
W odniesieniu do „bogactwa”: Przepraszam, że nie zrozumiałem, co to znaczy (przynajmniej tak jak to ująłeś). Algorytmów klastrowania jest wiele. Jak można oczekiwać, że wszystkie spełniają określone, wymyślne wymagania?
ttnphns
W odniesieniu do twojego obrazu: potrzebne są specjalne metody grupowania, aby rozpoznać taki wzór. Tradycyjne / oryginalne metody skupiania wynikają z biologii i socjologii, gdzie skupienia są mniej więcej kulistymi „wyspami”, a nie pierścieniami atoli. Te metody nie mogą wymagać radzenia sobie z danymi na zdjęciu.
ttnphns
Możesz być także zainteresowany: Estivill-Castro, Vladimir. „Dlaczego tak wiele algorytmów grupowania: dokument określający pozycję”. Biuletyn eksploracyjny ACM SIGKDD 4.1 (2002): 65-75.
Anony-Mus-Przywróć Monikę
Nie przeczytałem gazety. Ale w wielu algorytmach klastrowania masz pewien próg odległości (np. DBSCAN, hierarchiczne grupowanie). Jeśli skalujesz odległości, bo musisz również odpowiednio przeskalować swój próg. Dlatego nie zgadzam się z jego wymogiem niezmienności skali. Nie zgadzam się również z bogactwem. Nie każda partycja musi być poprawnym rozwiązaniem dla każdego algorytmu. Istnieją miliony losowych partycji.
Anony-Mus-Przywróć Monikę

Odpowiedzi:

11

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:S1S2270

dwa zestawy po 270 punktów

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

zestaw 1 z zoomem

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:S2

zestaw 2 z zoomem

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.S2 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.S1S2S233×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 2k2- 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):

grupowanie {kot, pies, mysz} kontra {Tom, Spike, Jerry}

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) kk 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 SSS 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 .

Γ:{metrics on S}{partitions of S}dΓ(d)
iddSi:SSd(i(x),i(y))=d(x,y)xyS

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 )Γddii(x)i(y)Γ(d) , wtedy i tylko wtedy, gdy pierwotne punkty i y leżą w tym samym klastrze y ( d ) .xyΓ(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.SSS

zestaw punktów na płaszczyźnie i dwa jego obroty

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ą, alboSΓdSd(x,y)=1xySΓΓ(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)dS1dΓ(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)dS1Γ(d)=Γ(d)Γ

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

Algebra komunikacyjna
źródło
7

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

enter image description here

d1d2d3d2d3d1d1d3d2d3

Alex Williams
źródło
Masz na myśli lewy dolny dla d2? Jedną fajną rzeczą w twoim diagramie jest to, że pokazuje, jak spójność nie jest ogólnie pożądaną właściwością (lub że jest zbyt luźno sformułowana).
xan
Tak, w lewym dolnym rogu, odpowiednio zredagowałem odpowiedź. Dzięki!
Alex Williams
Zanim w pełni zrozumiałem twoją odpowiedź, wpadłem na logikę, która okazuje się być twoją dualnością: zacznij od grupowania, w którym wszystkie punkty znajdują się w tej samej grupie. Przekształć go w dowolny inny układ, zmniejszając go do miniaturowej wersji dowolnego innego układu i skalując do pełnowymiarowej wersji innego układu.
xan