Grupowanie oparte na wynikach podobieństwa

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

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 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.

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.

Analiza danych topologicznych to metoda specjalnie zaprojektowana dla opisywanego ustawienia. Zamiast globalnej metryki odległości, opiera się tylko na lokalnej metodzie bliskości lub sąsiedztwa. Zobacz: Topologia i dane oraz Wyodrębnianie spostrzeżeń z kształtu złożonych danych przy użyciu topologii . Możesz znaleźć dodatkowe zasoby na stronie internetowej dla Ayasdi.