Wykonywanie grupowania K-średnich (lub jego bliskich krewnych) za pomocą macierzy odległości, a nie danych punkt po cechach

22

Chcę wykonać K-oznacza grupowanie obiektów, które mam, ale obiekty te nie są opisywane jako punkty w przestrzeni, tj. Przez objects x featureszestaw danych. Jestem jednak w stanie obliczyć odległość między dowolnymi dwoma obiektami (jest ona oparta na funkcji podobieństwa). Pozbywam się macierzy odległości objects x objects.

Wcześniej zaimplementowałem K-średnich, ale było to z danymi wejściowymi zestawu danych punktów; a przy wprowadzaniu macierzy odległości nie jest dla mnie jasne, jak zaktualizować klastry, aby były „centrami” klastra bez reprezentacji punktowej. Jak można to normalnie zrobić? Czy istnieją do tego wersje K-średnich lub metod?

mysz
źródło
Co masz na myśli, że nie są opisane jako punkty?
ciekawy
Zobacz także stats.stackexchange.com/q/12495/3277
ttnphns

Odpowiedzi:

24

Oczywiście, k-średnie musi być w stanie obliczyć środki .

Istnieje jednak dobrze znana jego odmiana znana jako k-medoidy lub PAM (partycjonowanie wokół medoidów), gdzie medoid jest istniejącym obiektem najbardziej centralnym dla gromady. K-medoidy potrzebują tylko par odległości.

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

Dokładnie opisujesz ustawienie problemu dla jądra -means; gdy nie możesz przedstawić punktu danych jako wektora euklidesowego, ale jeśli nadal możesz obliczyć (lub zdefiniować) iloczyn wewnętrzny między dwoma punktami danych, możesz jądro algorytmu. Poniższa strona internetowa zawiera krótki opis algorytmu:k

Jądro oznacza stronęk

Ta sztuczka jądra jest bardzo popularną i podstawową ideą w statystyce i uczeniu maszynowym.

Strona Wiki dotycząca sztuczki jądra

Jeśli jesteś zainteresowany, książka Learning with Kernels from Bernhard Schölkopf i Alexander J. Smola będzie bardzo miłym wprowadzeniem.

Ta notatka Maxa Wellinga wydaje się bardzo ładna; Ponadto, jeśli używasz R można zapoznać się z tym pakietem R .

MDS może być jednym ze sposobów rozwiązania problemu, ale nie atakuje bezpośrednio problemu, który chcesz rozwiązać; podczas gdy jądro oznacza k-średnich.

d_ijk_stra
źródło
Chciałem dodać więcej linków, ale nie mogłem tego zrobić z powodu niskiej reputacji. Ta notatka z Max Welling uwaga wydaje się bardzo ładny; jeśli używasz R, możesz
rzucić
(+1) Witamy na stronie. Dodałem linki w twoim komentarzu do treści postu, a także jeden do tekstu Schölkopf i Smola.
kardynał
9

@gung ma absolutną rację sugerując, że skalowanie wielowymiarowe (MDS) jest wstępnym narzędziem do tworzenia points X dimensions danych poza macierzą odległości. Dodam tylko kilka pociągnięć. K-means klastrów zakłada odległości euklidesowych . MDS poda współrzędne punktów w wymiarach, gwarantując tym samym odległości euklidesowe. Powinieneś użyć metrycznego MDS i zażądać jak największej liczby wymiarów, ponieważ Twoim celem jest zminimalizowanie błędu ponownego wyodrębniania danych, a nie odwzorowanie ich w 2D lub 3D.

Co jeśli nie masz pod ręką oprogramowania MDS, ale masz pewne funkcje macierzy, takie jak rozkład wartości własnych lub rozkład wartości pojedynczej? Następnie możesz samodzielnie wykonać prosty pomiar MDS - Torgerson MDS, znany również jako analiza głównych współrzędnych (PCoA). Jest to nieco „przekręcona” analiza głównych składników. Nie będę go tutaj opisywał, chociaż jest to dość proste. Możesz o tym przeczytać w wielu miejscach, np . Tutaj .

Wreszcie możliwe jest bezpośrednie zaprogramowanie „K-średnich dla matrycy odległości” - bez wywoływania lub pisania funkcji wykonujących PCoA lub innego metrycznego MDS. Wiemy, że (a) suma kwadratowych odchyleń od środka ciężkości jest równa sumie parowanych kwadratowych odległości euklidesowych podzielonych przez liczbę punktów; oraz (b) umie obliczyć odległości między centrami skupisk poza matrycą odległości ; (c) i dalej wiemy, w jaki sposób sumy kwadratów są powiązane w K-średnich. Wszystko razem sprawia, że ​​pisanie algorytmu, którego potrzebujesz, jest prostym, a nie złożonym przedsięwzięciem. Należy jednak pamiętać, że K-oznacza dotyczy tylko odległości euklidesowych / przestrzeni euklidesowej. Użyj K-medoidów lub innych metod dla odległości innych niż euklidesowe.

Podobne pytanie .

ttnphns
źródło
7

Z pewnością nie wiem, jak to się robi „normalnie”, a dla przypomnienia nie wiem zbyt wiele o analizie skupień. Czy znasz jednak skalowanie wielowymiarowe ? ( Oto kolejne odniesienie, wiki , i możesz przeszukiwać CV pod znacznikiem .) Skalowanie wielowymiarowe przyjmuje macierz odległości par, co brzmi jak twoja sytuacja. Z MDS można uzyskać lokalizacje obiektów w przestrzeni o najniższych wymiarach niezbędnych do odpowiedniego ich przedstawienia. Sądzę, że można użyć tych lokalizacji do przeprowadzenia późniejszej analizy skupień, takiej jak k-średnie; alternatywnie, po uzyskaniu danych wyjściowych możesz już nie potrzebować urzędu certyfikacji.

Nie wiem, czy używasz R, ale oto widok zadania dla Psychometrii, który zawiera sekcję dotyczącą MDS w R. Hope, która pomaga.

gung - Przywróć Monikę
źródło
4

k

W twoim przypadku musisz zasadniczo:

  1. D
  2. DijDji
  3. Dc
  4. Sc=12Dc
  5. ScScS~c
  6. S~c=VΛV
  7. n1X=VΛ1/2

n

blubb
źródło
Opisane kroki to nic innego jak analiza głównych współrzędnych, o której wspominam w mojej odpowiedzi.
ttnphns
Proszę zilustrować przykład kroku 5. Odejmowanie ostatniej (ujemnej) wartości własnej z elementów macierzy S wydaje się nie pomagać w uzyskaniu dodatniej półprodukty.
ttnphns
@ttnphns: Zasadniczo jest to PCA, tak, ale nie wymaga pomiaru odległości. Opis kroku 5 był niefortunny, dziękuję za wykrycie go. Czy to jest teraz jasne?
blubb
Odejmowanie sumy ujemnych wartości własnych od wszystkich wartości własnych, a następnie przywrócenie macierzy S jest równoważne odejmowaniu tej sumy od elementów diagonalnych S. To zakończenie czyni S dodatnią (pół) określoną, ale ...
ttnphns
... ale ten sposób jest bardzo zły w tym sensie, że wynikowe dane euklidesowe X wytwarzają odległości euklidesowe D_new, które są bardzo dalekie od oryginalnych różnic D. Nie polecałbym więc twojego kroku 5. Wydaje się, że lepiej jest po prostu ustawić wartość ujemną wartości własne na 0 i przejdź do kroku 7. Lub, nieco bardziej precyzyjne podejście: ustaw ujemne wartości własne na 0, przeskaluj dodatnie wartości własne, aby były sumy oryginalne (= ślad (S)), a następnie przejdź do kroku 7. Tak to wygląda Dla mnie.
ttnphns
2

Twoje dane mogą być również przeglądane jako sieć i możesz użyć jednego z wielu dostępnych algorytmów klastrowania sieci. W tym celu prawdopodobnie należy zastosować próg dla wag krawędzi i przekształcić odległości na podobieństwa. Nie jest to „statystyczny” sposób robienia rzeczy, ale analiza klastra jest na początku nieokreślonym problemem, a ponieważ narzędzia eksploracyjne algorytmy klastrowania sieci działają bardzo dobrze.

micans
źródło
2

Nie wiem, dlaczego jest to tak rzadkie w literaturze, jednak rozwiązanie sugerowane przez @gung i @ttnphns (najpierw rzutuj odległości parami na przestrzeń euklidesową za pomocą analizy głównych współrzędnych, na przykład poprzez ten pakiet, jeśli używasz R, a następnie robienie K-oznacza zwykły sposób) jest proste i nie wymaga specjalnych algorytmów. Osobiście użyłem go tutaj, osadzonego w ramach optymalizacji i działało dość dobrze.

Francesco Napolitano
źródło
1

W odniesieniu do klastrowania i MDS proponuję następujące zasoby:

Odnośniki te również ładnie obejmują tematy podobieństwa i funkcji odległości (miary bliskości) dla danych binarnych i ciągłych.

użytkownik1137731
źródło