Jak zmierzyć kształt klastra?


14

Wiem, że to pytanie nie jest dobrze zdefiniowane, ale niektóre gromady mają tendencję do bycia eliptycznymi lub leżą w przestrzeni o mniejszych wymiarach, podczas gdy inne mają kształty nieliniowe (w przykładach 2D lub 3D).

Czy istnieje jakakolwiek miara nieliniowości (lub „kształtu”) klastrów?

Zauważ, że w przestrzeni 2D i 3D nie jest problemem zobaczyć kształt dowolnej gromady, ale w przestrzeniach o wyższych wymiarach problem polega na powiedzeniu o kształcie. W szczególności, czy istnieją jakieś mierniki tego, jak wypukły jest klaster?

Inspiracją do tego pytania było wiele innych pytań grupujących, w których ludzie mówią o klastrach, ale nikt ich nie widzi (w przestrzeniach o wyższych wymiarach). Ponadto wiem, że istnieją pewne miary nieliniowości dla krzywych 2D.


1
en.wikipedia.org/wiki/Topological_data_analysis może pomóc, jeśli kształt nie jest dokładnie taki, jak masz na myśli.
ziyuang

1
Być może mógłbyś dostosować koncepcję zwartości do swojego celu.
user12719

Odpowiedzi:


4

Lubię modele Gaussian Mixture (GMM).

Jedną z ich cech jest to, że w domenie probit działają one jak częściowe interpolatory. Jedną z konsekwencji tego jest to, że mogą działać jak podstawa zastępcza, uniwersalny aproksymator. Oznacza to, że dla rozkładów niegaussowskich, takich jak logarytmiczne, Weibulla lub bardziej szalone, nieanalityczne, o ile spełnione są pewne kryteria - GMM może aproksymować rozkład.

Więc jeśli znasz parametry aproksymacji AICc lub BIC za pomocą GMM, możesz rzutować to na mniejsze wymiary. Możesz go obrócić i spojrzeć na główne osie komponentów zbliżonego GMM.

Konsekwencją tego byłby pouczający i dostępny wizualnie sposób patrzenia na najważniejsze części danych o wyższych wymiarach przy użyciu naszej percepcji wizualnej podczas oglądania w 3D.

EDYCJA: (pewnie, whuber)

Istnieje kilka sposobów patrzenia na kształt.

  • Możesz spojrzeć na trendy w środkach. Logarytm normalny jest aproksymowany przez szereg Gaussów, którzy oznaczają stopniowe zbliżanie się i których waga maleje wraz z postępem. Suma ta zbliża się do cięższego ogona. W n-wymiarach sekwencja takich elementów tworzy płat. Możesz także śledzić odległości między średnimi (konwertować do wysokich wymiarów) i cosinusy kierunkowe między nimi. To przekształciłoby się w znacznie bardziej dostępne wymiary.
  • Możesz stworzyć system 3d, którego osiami są ciężar, wielkość średniej i wielkość wariancji / kowariancji. Jeśli masz bardzo dużą liczbę klastrów, jest to sposób na porównanie ich ze sobą. Jest to cenny sposób na konwersję 50 tys. Części za pomocą 2k taktów na kilka chmur w przestrzeni 3D. Jeśli mogę, mogę wykonać kontrolę procesu w tej przestrzeni. Podoba mi się rekurencja polegająca na stosowaniu kontroli opartej na modelu mieszanki gaussowskiej na komponentach modelu mieszanki gaussowskiej, która pasuje do parametrów części.
  • Jeśli chodzi o zagracenie, możesz wyrzucić je bardzo małą wagą lub wagowo według kowariancji lub tym podobne.
  • Możesz wykreślić chmurę GMM pod kątem BIC, R2), Odległość Mahalanobisa do składników lub ogólnie, prawdopodobieństwo członkostwa lub ogólnie.
  • Można na to spojrzeć jak przecinające się bąbelki . Lokalizacja równego prawdopodobieństwa (zerowa dywergencja Kullbacka-Leiblera) istnieje między każdą parą klastrów GMM. Jeśli śledzisz tę pozycję, możesz filtrować według prawdopodobieństwa członkostwa w tej lokalizacji. Dadzą ci punkty granic klasyfikacji. Pomoże ci to wyodrębnić „samotników”. Możesz policzyć liczbę takich granic powyżej progu na członka i uzyskać listę „połączeń” na komponent. Możesz także spojrzeć na kąty i odległości między lokalizacjami.
  • Możesz ponownie próbkować przestrzeń za pomocą liczb losowych z danymi PDF Gaussa, a następnie przeprowadzić na niej analizę podstawowych składników i spojrzeć na kształty własne i związane z nimi wartości własne.

EDYTOWAĆ:

Co oznacza kształt? Mówią, że specyfika jest duszą wszelkiej dobrej komunikacji. Co masz na myśli przez „pomiar”?

Pomysły na temat tego, co może to oznaczać:

  • Gałka oczna norma sens / odczucia ogólnej formy. (bardzo jakościowy, wizualnie dostępny)
  • miara kształtu GD&T (współpłaszczyznowość, koncentryczność itp.) (skrajnie ilościowa)
  • coś liczbowego (wartości własne, kowariancje itp.)
  • przydatna współrzędna zredukowanego wymiaru (np. parametry GMM stają się wymiarami)
  • zredukowany system hałasu (w jakiś sposób wygładzony, a następnie przedstawiony)

Większość z „kilku sposobów” jest ich odmianą.


3

Może to być dość uproszczone, ale możesz uzyskać wgląd, wykonując analizę wartości własnych dla każdego z twoich klastrów.

Chciałbym wziąć wszystkie punkty przypisane do klastra i dopasować je do wielowymiarowego Gaussa. Następnie możesz obliczyć wartości własne dopasowanej macierzy kowariancji i wykreślić je. Istnieje wiele sposobów, aby to zrobić ; być może najbardziej znana i powszechnie stosowana nazywa się analizą głównych składników lub PCA .

Po uzyskaniu wartości własnych (zwanych również widmem) możesz zbadać ich względne rozmiary, aby ustalić, jak „rozciągnięta” jest klaster w określonych wymiarach. Im mniej jednolite widmo, tym bardziej „cygaro” jest gromada, a im bardziej jednolite widmo, tym bardziej kulista jest gromada. Można nawet zdefiniować jakąś metrykę wskazującą, jak nierównomierne są wartości własne (entropia spektralna?); patrz http://en.wikipedia.org/wiki/Spectral_flatness .

Dodatkową korzyścią jest zbadanie głównych składników (wektorów własnych powiązanych z dużymi wartościami własnymi), aby zobaczyć, „gdzie” klastry „w kształcie cygara” wskazują w przestrzeni danych.

Oczywiście jest to przybliżone przybliżenie dowolnego gromady, ponieważ modeluje punkty w gromadzie jako pojedynczą elipsoidę. Ale, jak powiedziałem, może dać ci pewien wgląd.


+1 Być może uproszczony; ale wygląda to na skuteczne i praktyczne. Wydaje się, że wielowymiarowe dopasowanie gaussowskie nie ma żadnej korzyści: wystarczy użyć SVD wyśrodkowanych danych wewnątrz klastra (co w gruncie rzeczy jest PCA).
whuber

@ whuber tak, myślę, że robią to samo! Dopasowanie jest bardziej, jak mówi teoria, dzieje się za kulisami, podczas gdy PCA jest konkretną implementacją tego procesu. Zmodyfikuję moją odpowiedź, aby było to bardziej jasne.
lmjohns3

2

Algorytmy grupowania korelacji, takie jak 4C, ERiC lub LMCLUS, zwykle uważają klastry za rozmaite liniowe. Tj. Hiperpłaszczyzny k-wymiarowe w przestrzeni d-wymiarowej. Cóż, dla 4C i ERiC tylko lokalnie liniowo, więc mogą w rzeczywistości nie być wypukłe. Ale nadal próbują wykryć skupiska o zmniejszonej lokalnej wymiarowości.

Znalezienie klastrów o dowolnym kształcie w danych wielowymiarowych jest dość trudnym problemem. W szczególności z powodu klątwy wymiarowej, która pozwala eksplodować przestrzeni wyszukiwania, a jednocześnie wymaga posiadania znacznie większych danych wejściowych, jeśli nadal chcesz znaczących wyników. Zbyt wiele algorytmów nie zwraca uwagi na to, czy znalezione przez nich dane są nadal znaczące, czy też mogą być losowe.

Tak więc wierzę, że istnieją inne problemy do rozwiązania, zanim pomyślimy o wypukłości niewypukłości złożonych skupień w przestrzeni wielowymiarowej.

Zobacz także złożoność obliczeń wypukłego kadłuba w wyższych wymiarach ...

Czy masz też prawdziwy przypadek użycia tego poza ciekawością?


2

Jeśli twoje wymiary nie są dużo wyższe niż 2 lub 3, może być możliwe wielokrotne rzutowanie interesującego klastra w przestrzeń 2D i wizualizacja wyników lub użycie pomiaru 2D nieliniowości. Pomyślałem o tym z powodu metody Random Projections http://users.ics.aalto.fi/ella/publications/randproj_kdd.pdf .

Rzutów losowych można użyć do zmniejszenia wymiarów w celu zbudowania indeksu. Teoria polega na tym, że jeśli dwa punkty są bliskie wymiarom D, a za pomocą d bierze się losową projekcję na wymiary d

Jeśli chodzi o konkretność, możesz pomyśleć o rzutowaniu kuli ziemskiej na płaską powierzchnię. Bez względu na to, jak to zaplanujesz, Nowy Jork i New Jersey będą razem, ale tylko w rzadkich przypadkach uda ci się połączyć Nowy Jork i Londyn.

Nie wiem, czy to może ci pomóc, ale może to być szybki sposób na wizualizację klastrów.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.