Grupowanie oparte na wynikach podobieństwa

18

Załóżmy, że mamy zbiór elementów E i podobieństwo ( nie odległość funkcja) sim (ei, ej) między dwoma elementami El, EJ ∈ E .

Jak moglibyśmy (skutecznie) grupować elementy E za pomocą karty SIM ?

k- oznacza, na przykład, wymaga określonego k , klastrowanie baldachimu wymaga dwóch wartości progowych. Co jeśli nie chcemy takich predefiniowanych parametrów?

Zauważ, że sim nie jest koniecznie metryką (tzn. Nierówność trójkąta może, ale nie musi). Co więcej, nie ma znaczenia, czy klastry są rozłączne (partycje E ).

clustering algorithms similarity vefthym
źródło
2
Zastanawiam się, dlaczego podkreśliłeś, że nie masz dystansu. Nie jestem tutaj ekspertem, ale zastanawiam się, czy nie powinno być możliwe przekształcenie takiego podobieństwa na odległość, jeśli jest to wymagane, po prostu biorąc pod uwagę jego odwrotność. Niezależnie od tego wątpię, aby istniały algorytmy grupowania, które są całkowicie wolne od parametrów, więc pewne strojenie najprawdopodobniej będzie konieczne we wszystkich przypadkach. Kiedy uważane k-średnich, można przypuszczać, że mają właściwości prawdziwych wartościach (zwłaszcza, że można wziąć „średnią” z kilku elementów)?
Marco13
4
Nie musisz znać k, aby wykonać k oznacza. Możesz skupiać ze zmienną k i sprawdzać wariancję skupienia, aby znaleźć optymalną. Alternatywnie możesz pomyśleć o wyborze modeli mieszanki Gaussa lub innych procesach naprawczych, takich jak rzeczy, które pomogą ci skupić.
cwharland
2
Zadałem pytania z konkretnego powodu: jeśli możesz zastosować k-Means, ale jedynym problemem było znalezienie początkowego „k”, to możesz rozważyć en.wikipedia.org/wiki/Self-organizing_map jako alternatywę. Ma kilka fajnych właściwości i zasadniczo zachowuje się „podobnie” do k-średnich, ale nie wymaga ustawienia początkowego „k”. Prawdopodobnie nie jest to gotowe rozwiązanie, ponieważ ma dodatkowe parametry dostrajania (a szkolenie może być drogie obliczeniowo), ale mimo to warto je sprawdzić.
Marco13
2
Początkowy wybór k ma wpływ na wyniki grupowania, ale możesz zdefiniować funkcję straty lub, bardziej prawdopodobne, funkcję dokładności, która powie ci dla każdej wartości k, której używasz do grupowania, względnego podobieństwa wszystkich podmiotów w tym klastrze. Wybierasz k, który minimalizuje wariancję tego podobieństwa. GMM i inne procesy dirichleta całkiem dobrze radzą sobie z problemem niewiedzy-k. Jednym z najlepszych zasobów, jakie kiedykolwiek widziałem na ten temat, jest samouczek Edwina Chena .
cwharland
4
Tylko myśl: jeśli twój wynik podobieństwa jest znormalizowany do 1 , niż 1-sim(ei, ej) = Distance. Za pomocą metryki odległości możesz na przykład zastosować hierarchiczne grupowanie. Schodząc od korzenia zobaczysz, na jakim poziomie klastrów ziarnistości ma sens dla twojego konkretnego problemu.
Olexandr Isayev

Odpowiedzi:

9

  1. Myślę, że wiele algorytmów klastrowych, które zwykle używają metryki, w rzeczywistości nie polegają na właściwości metryki (innej niż przemienność, ale myślę, że tutaj byś ją miał). Na przykład DBSCAN wykorzystuje sąsiedztwa epsilon wokół punktu; nic tam nie mówi, że nierówność trójkąta ma znaczenie. Prawdopodobnie możesz więc użyć DBSCAN, chociaż być może będziesz musiał zrobić jakiś niestandardowy indeks przestrzenny, aby wykonać efektywne wyszukiwanie w twoim przypadku. Twoja wersja epsilon-neighbour prawdopodobnie będzie miała SIM> 1 / epsilon, a nie na odwrót. Ta sama historia z k-średnich i powiązanymi algorytmami.

  2. Czy możesz zbudować metrykę ze swojego podobieństwa? Jedna możliwość: dist (ei, ej) = min (sim (ei, ek) + sim (ek, ej)) dla wszystkich k ... Alternatywnie, czy możesz podać górną granicę, że sim (ei, ej) <sim (ei, ek) + sim (ek, ej) + d, dla wszystkich k i pewnej dodatniej stałej d? Intuicyjnie, duże wartości sim oznaczają bliżej siebie: czy 1 / sim jest metryczny? Co z 1 / (sim + stała)? Co z min (1 / sim (ei, ek) + 1 / sim (ek, ej)) dla wszystkich k? (to ostatnie gwarantuje, że będzie to metryka, btw)

  3. Alternatywną konstrukcją metryki jest osadzanie. W pierwszym kroku możesz spróbować zmapować swoje punkty ei -> xi, tak aby xi zminimalizować sumę (abs (sim (ei, ej) - f (dist (xi, xj))), dla niektórych odpowiednich funkcji f i metrycznych dist. Funkcja f przekształca odległość w osadzaniu na wartość podobną do podobieństwa; trzeba by trochę poeksperymentować, ale 1 / dist lub exp ^ -ist są dobrymi punktami początkowymi. wymiar dla XI. Stamtąd można zastosować konwencjonalne grupowanie na XI. Pomysł polega na tym, że można prawie (w najlepszym sensie dopasować) przekonwertować odległości w osadzaniu na wartości podobieństwa, aby były poprawnie grupowane.

  4. Przy użyciu predefiniowanych parametrów wszystkie algorytmy mają pewne dostrojenie. DBSCAN może znaleźć liczbę klastrów, ale nadal musisz podać jej pewne parametry. Ogólnie rzecz biorąc, dostrajanie wymaga wielu uruchomień algorytmu z różnymi wartościami dostrajalnych parametrów, wraz z pewną funkcją oceniającą dobro klastrowania (albo obliczoną osobno, zapewnioną przez sam algorytm klastrowania, albo po prostu gałką oczną :) Jeśli charakter twoje dane się nie zmieniają, możesz nastroić raz, a następnie użyć tych stałych parametrów; jeśli to się zmieni, musisz nastroić dla każdego uruchomienia. Możesz się tego dowiedzieć, dostrajając dla każdego przebiegu, a następnie porównując, jak dobrze parametry z jednego przebiegu działają na drugim, w porównaniu do parametrów specjalnie do tego dostosowanych.

Alex I.
źródło
8

Alex przedstawił kilka dobrych argumentów, choć być może będę musiał nieco odsunąć od siebie sugestię, że DBSCAN jest najlepszym algorytmem klastrowania, jaki można tu zastosować. W zależności od implementacji i od tego, czy używasz indeksów przyspieszonych (wiele implementacji tego nie robi), zarówno złożoność czasu, jak i przestrzeni będzie O(n2)daleka od ideału.

Osobiście moimi algorytmami klastrowania przejścia są OpenOrd dla grupowania zwycięzca bierze wszystko i FLAME dla klastrowania rozmytego. Obie metody są obojętne na to, czy zastosowane wskaźniki to podobieństwo czy odległość (w szczególności FLAME jest prawie identyczny w obu konstrukcjach). Implementacja OpenOrd w Gephi jest O(nlogn)i wiadomo, że jest bardziej skalowalna niż jakikolwiek inny algorytm klastrowania obecny w pakiecie Gephi.

Z drugiej strony FLAME jest świetny, jeśli szukasz rozmytej metody klastrowania. Chociaż złożoność FLAME jest nieco trudniejsza do ustalenia, ponieważ jest to proces iteracyjny, wykazano, że jest subkwadratowy i podobny pod względem prędkości biegu do knn.

indico
źródło
5

DBSCAN (patrz też: Uogólniona DBSCAN) nie wymaga odległości. Wszystko czego potrzebuje to binarna decyzja . Zwykle używa się słowa „odległość <epsilon”, ale nic nie mówi, że nie można zamiast tego użyć „podobieństwa> epsilon”. Nierówności trójkątów itp. Nie są wymagane.

Propagacja powinowactwa, jak sama nazwa mówi, wykorzystuje podobieństwa.

Hierarchiczne grupowanie, z wyjątkiem może powiązania Totemów, nie przyjmuje żadnych założeń. W wielu implementacjach możesz użyć ujemnych odległości, gdy masz podobieństwa, i to będzie działać dobrze. Ponieważ wszystko, co jest potrzebne, to min, max i <.

K-średnie jądra mogą działać JEŻELI twoje podobieństwo jest dobrą funkcją jądra. Pomyśl o tym jak o obliczaniu k-średnich w innej przestrzeni wektorowej, gdzie odległość euklidesowa odpowiada twojej funkcji podobieństwa. Ale wtedy musisz znać K.

PAM (K-medoidy) powinny działać. Przypisz każdy obiekt do najbardziej podobnej medoidy, a następnie wybierz obiekt o najwyższym średnim podobieństwie jako nowy medoid ... nie potrzeba nierówności trójkąta.

... i prawdopodobnie o wiele więcej. Istnieją dosłownie setki algorytmów klastrowych. Większość powinna działać IMHO. Wydaje się, że niewielu faktycznie wymaga właściwości metrycznych. Środki K mają prawdopodobnie najsurowsze wymagania: minimalizują wariancję (nie odległość ani podobieństwo) i musisz być w stanie obliczyć środki.

Anony-Mus-Przywróć Monikę
źródło