Temat: Jakiej metody klasteryzacji użyć gdy odległości przyjmują...

Jakiej metody klasteryzacji użyć gdy odległości pomiędzy obserwacjami przyjmują wartości wyłącznie ze zbioru {0,1}, czy któraś z metod jest szczególnie przydatna w tym przypadku?

Macierz odległości składa się z samych zer i jedynek i nie chcę tego stanu rzeczy zmieniać. Słyszałem o metodach partycjonowania grafów, jednak, dotąd używałem wyłącznie aglomeracyjnych metod klasteryzacji.

Temat: Jakiej metody klasteryzacji użyć gdy odległości przyjmują...

Nie spotkałem się dotąd z tak skonstruowaną macierzą odległości, ale nasuwa mi się kilka refleksji, więc spróbuję poimprowizować. Jeśli macierz skonstruowana jest w oparciu o poprawną metrykę, to warto skoncentrować się na zależnościach D(a,b)=0.

Zaczynając od obserwacji a jako zalążka pierwszego klastra, można by włączać do niego wszystkie obserwacje x gdzie D(a,x) = 0, a korzystając z nierówności trójkąta, powtarzać ten zabieg rekurencyjnie, bo skoro D(a,X) = 0 i D(X,b) = 0 to musi zachodzić D(a,b) <= D(a,X) + D(X,b) = 0, czyli D(a,b) = 0, więc i b jest identyczne z a. Gdy nie będzie już żadnej obserwacji do włączenia, wybieramy kolejną nieprzyporządkowaną nigdzie obserwacje, jako zalążek kolejnego klastra. Jeśli nierówność trójkąta jest wszędzie spełniona, algorytm podzieli zbiór na skupienia, w ramach których obserwacje są od siebie nierozróżnialne...

Spodziewam się jednak, że tak dobrze nie będzie - ale włączając obserwację X do klastra możesz też sprawdzać, czy istnieje już jakieś b z bieżącego klastra, dla którego D(b,X) > 0 i wtedy ją pominąć. Co zrobić z takimi obserwacjami później? Jeśli będzie tego relatywnie mało, możesz pomyśleć o włączaniu ich na koniec do powstałych klastrów, korzystając z jakiejś funkcji oceniającej odległość obserwacji od całego skupienia - to będzie o tyle prostsze, że przy jej konstruowaniu nie będziesz już ograniczony do {0,1}. Natomiast jeśli wiele obserwacji będzie przeczyć założeniom o poprawności metryki, to będzie trzeba chyba uruchomić wyobraźnię...

Temat: Jakiej metody klasteryzacji użyć gdy odległości przyjmują...

Obawiam się, że nie ma takiej metody, a dokładniej: klasteryzacja nie bardzo tu pasuje....

Już tłumaczę w czym problem... Klasteryzacja ma za zadanie podzielić dane na grupy tak by w każdej grupie były podobne obiekty i aby obiekty między grupami były możliwie jak najbardziej "niepodobne".

My mamy tu tylko obiekty identyczne oraz skrajnie różne. Zatem gdzie odległość wynosi 0 możemy sklejać obiekty w jeden klaster. Być może takie rozwiązanie w tym konkretnym przypadku byłoby wystarczające.

Jeśli nasza odległość nie spełnia aksjomatów metryki to możliwe są różne dziwne zjawiska jak np: d(A,B)=0 oraz d(B,C)=0, zaś d(A,C)=1. Tym samym podział na grupy identycznych obiektów stanie się trudny lub wręcz niemożliwy.

Jeśli mamy zaś spełnione aksjomaty metryki to będziemy musieli poszukać swego rodzaju "klik", czyli zbioru obserwacji gdzie każde dwie spełniają własność: d(A,B)=0. Każda taka "klika" będzie swego rodzaju segmentem (klastrem). Niestety jest to czasochłonne zadanie.

Jest to jedyna droga jaką tutaj dostrzegam. Klasyczne techniki segmentacyjne nie poradzą sobie bowiem z tak skonstruowaną miarą.

powodzenia!

Temat: Jakiej metody klasteryzacji użyć gdy odległości przyjmują...

No to mamy 2:0 jeśli chodzi o pomysły - pozostaje wybranie skupisk, w których wszystkie obserwacje są takie same...

Natomiast jeśli liczba pozostałych segmentów jednoelementowych nie będzie duża, to proponuję zwrócić uwagę na możliwość włączenia ich do już istniejących - przyjmując za kryterium np. % obserwacji w istniejącym skupieniu, którą są D(a,b)=0 z takim satelitą. Wybaczy się w ten sposób pewne błędy (niekonsekwencje) w samej macierzy odległości.

Temat: Jakiej metody klasteryzacji użyć gdy odległości przyjmują...

A nie da się tego rozwiązać analizą klas latentnych zamiast klasteryzacją? Wydaje się, że to bardziej adekwatne do sytuacji rozwiązanie.

Temat: Jakiej metody klasteryzacji użyć gdy odległości przyjmują...

hmmm... jednak przy analizie klas letentnych napotkamy moim zdaniem dokładnie te same problemy...

skłaniałbym się raczej w kierunku analizy grafów i poszukiwaniu klik...

a może... można inaczej zdefiniować odległość :)