Implementacja k-oznacza z niestandardową macierzą odległości na wejściu

14

Czy ktoś może mi wskazać implementację k-średnich (byłoby lepiej, gdyby w Matlabie), która może wprowadzić macierz odległości na wejściu? Standardowa implementacja Matlaba wymaga macierzy obserwacji na wejściu i nie jest możliwe niestandardowe zmienianie miary podobieństwa.

clustering matlab k-means Eugenio
źródło
2
Możesz spróbować wygenerować surowe dane odpowiadające macierzy odległości euklidesowych i wprowadzić je do K-średnich. Alternatywnym łatwym podejściem może być zastosowanie metody Warda hierarchicznego grupowania macierzy: K-średnie i Ward podzielają podobną ideologię dotyczącą tego, czym jest klaster.
ttnphns
oprócz ttnphns i Not Durrett może się okazać, czy można używać odległości Manhattanu z połączeniem między klastrami Warda w hierarchicznym klastrowaniu? ciekawe
steffen
Nie Matlab, ale strona Pythona pod hasłem „Możliwe jest określenie-własnej-funkcji-odległości-za pomocą-scikits-learn-k-średnich” może wykorzystywać dowolne z 20-nieparzystych wskaźników w scipy.spatial. dystans.
denis

Odpowiedzi:

13

Ponieważ k-średnich musi być w stanie znaleźć środki różnych podzbiorów punktów, które chcesz połączyć, tak naprawdę nie ma sensu prosić o wersję k-średnich, która przyjmuje macierz odległości jako dane wejściowe.

Zamiast tego możesz spróbować k-medoidów . Dostępnych jest kilka implementacji Matlaba .

NF
źródło
1
Cześć, dzięki za odpowiedź; zamiast bezpośrednio podać macierz odległości, czy byłoby możliwe podanie jako danych wejściowych niestandardowej miary odległości? Chodzi o to, że muszę porównać dwie metody klastrowania, a ponieważ w drugiej używam niestandardowej macierzy podobieństwa, chcę zastosować to samo podejście do kmeans, aby uzyskać rzetelne porównanie.
Eugenio
2
ELKI pozwala używać dowolnych funkcji odległości za pomocą k-średnich. Pamiętaj, że algorytm może się wtedy nie zbiegać. Środki K są naprawdę zaprojektowane dla kwadratowej odległości euklidesowej (suma kwadratów). W przypadku innych odległości średnia może już nie być zoptymalizowana, a algorytm ostatecznie się nie zbiegnie. Poważnie, rozważ użycie k-medoidów. W rzeczywistości został napisany, aby umożliwić użycie idei k-średnich z odległościami arbitralnymi .
Ma ZAKOŃCZENIE - Anony-Mousse
Istnieje również tworzenie klastrów w bibliotece Python / C ++, która umożliwia dostarczanie niestandardowych funkcji metrycznych: github.com/annoviko/pyclustering/issues/417
CpILL
8

Możesz zamienić macierz odległości w surowe dane i wprowadzić je do grupowania K-Means. Kroki byłyby następujące:

1) Odległości między twoimi punktami N muszą być równe kwadratowym wartościom euklidesowym. Wykonaj „ podwójne centrowanie ” macierzy: odejmij średnią rzędną z każdego elementu; w wyniku odejmij średnią kolumny od każdego elementu; w rezultacie dodaj średnią macierzy do każdego elementu; podziel przez minus 2. Macierz, którą macie teraz, to macierz SSCP (suma kwadratów i iloczynu) między punktami, w której początek jest umieszczony w geometrycznym środku chmury N punktów. (Przeczytaj wyjaśnienie podwójnego centrowania tutaj .)

2) Wykonaj PCA (Analiza głównego składnika) na tej macierzy i uzyskaj macierz obciążenia składnika NxN . Niektóre z ostatnich kolumn prawdopodobnie będą miały wartość 0, więc odetnij je. Pozostajesz teraz w rzeczywistości ocenami głównych składników, współrzędnymi twoich N punktów na głównych składnikach, które przechodzą, jak osie, przez chmurę. Dane te mogą być traktowane jako surowe dane odpowiednie do wprowadzania danych K-Means.

PS Jeśli twoje odległości nie są geometrycznie poprawne do kwadratu euklidesowego, możesz napotkać problem: macierz SSCP może nie być dodatnia (pół) określona. Problem ten można rozwiązać na kilka sposobów, ale z utratą precyzji.

ttnphns
źródło
Dziękuję za odpowiedź! W rzeczywistości nie mam rzeczywistej macierzy odległości, ale macierz podobieństwa (0 ... 1) między obiektami, a podobieństwa nie są obliczane dokładnie przy użyciu odległości euklidesowych, ale za pomocą niestandardowego algorytmu, który uwzględnia surowe dane, ale nie w standardowy sposób. Chyba w tym przypadku nie mogę zastosować twojej procedury, mam rację?
Eugenio
Nadal możesz to zrobić, po przeliczeniu podobieństw na odległości. Ten ostatni prawdopodobnie nie będzie prawdziwym euklidesem (a więc SSCP będzie miał pewne ujemne wartości własne); następnie spróbuj dodać małą stałą do odległości, aż SSCP straci wartość ujemną. eig. Istnieją również inne sposoby obejścia problemu. I pamiętajcie, że macie podwójną środkową macierz kwadratowych odległości.
ttnphns
PS A tak przy okazji. Jeśli twoja matryca ma podobieństwa, to jest jeszcze lepsza. Po prostu traktujesz to jak matrycę SSCP, o której mówiłem i robisz z nią PCA. Nadal jednak istnieje problem możliwych ujemnych wartości własnych.
ttnphns
@ttnphns, przykro mi brakuje swoje wyjaśnienia na etapie 1. macierz odległości X(powiedzmy N * N) będzie symetryczny, więc colMeans(X) =rowMeans(X) i raz odjąć wiersz lub col środków: Y=X-rowMeans(X), mean(Y)0.
Zhubarb
1
@Zububarb, kiedy mówię You could turn your matrix of distances into raw data(punkty 1 i 2), odnoszę się zasadniczo do wielowymiarowego skalowania Torgersona (MDS) , w którym podwójne centrowanie jest początkowym krokiem. Przeszukaj tę stronę (i Google również) w sprawie tej procedury. „Podwójne centrowanie” oznacza konwersję (do kwadratu) odległości w odpowiednią macierz iloczynu skalarnego zdefiniowaną nad początkiem umieszczoną w środku ciężkości chmury punktów.
ttnphns
3

Przeczytaj ten artykuł napisany przez jednego z moich znajomych;)

http://arxiv.org/abs/1304.6899

Chodzi o uogólnioną implementację k-średnich, która przyjmuje dowolną macierz odległości jako dane wejściowe. Może to być dowolna symetryczna nieujemna macierz o zerowej przekątnej. Pamiętaj, że może to nie dać rozsądnych wyników dla dziwnych matryc odległości. Program jest napisany w języku C #.

Kod źródłowy można uzyskać, odwiedzając powyższy link, a następnie klikając Inne formaty, a następnie klikając Pobierz źródło. Otrzymasz plik .tar.gz zawierający Program.cs. Alternatywnie kod źródłowy można również skopiować z pliku PDF.

szali
źródło
3

Możesz użyć biblioteki Java Machine Learning Library. Mają implementację K-Means. Jeden z konstruktorów przyjmuje trzy argumenty

  1. Wartość K.
  2. Obiektem tego jest instancja klasy DistanceMeasure .
  3. Liczba iteracji.

Można łatwo rozszerzyć klasę DistanceMeasure, aby osiągnąć pożądany wynik. Chodzi o to, aby zwracać wartości z niestandardowej macierzy odległości w metodzie miary (Instancja x, Instancja y) tej klasy.

K-Means jest uzgadniany w celu zbieżności przy założeniu pewnych właściwości metryki odległości. Odległość euklidesowa, odległość Manhattanu lub inne standardowe wskaźniki spełniają te założenia. Ponieważ niestandardowa metryka odległości może nie spełniać tych założeń, konstruktor ma trzeci parametr określający liczbę iteracji do uruchomienia w celu zbudowania klastra.

Chaitanya Shivade
źródło