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

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?

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.

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.

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

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

$k$

W twoim przypadku musisz zasadniczo:

1. $D$
2. $D_{ij}$$D_{ji}$
3. $D^c$
4. $S^c = -\frac{1}{2}D^c$
5. $S^c$$S^c$$\tilde S^c$
6. $\tilde S^c = V \Lambda V^\top$
7. $n-1$$X = V\Lambda^{1/2}$

$n$

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.

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.

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

• Ekologia numeryczna (Pierre Legendre i Louis Legendre): http://www.sciencedirect.com/science/bookseries/01678892/20 lub http://tinyurl.com/cgrdfqk (google books) - rozdział na temat „Podobieństwa ekologicznego”
• Analiza skupień (Brian S. Everitt, Sabine Landau, Morven Leese, Daniel Stahl): http://tinyurl.com/bld7k8h (google books) - rozdział „Pomiar odległości”
• Kurs „Biostatistics-II, Multivariate Methods” prof. Briana C. McCarthy na Ohio University: http://www.ohio.edu/plantbio/staff/mccarthy/multivariate/multivariate.htm

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.