Grupowanie za pomocą K-Means i EM: w jaki sposób są one powiązane?

50

Studiowałem algorytmy dla grupowania danych (uczenie bez nadzoru): EM i k-średnich. Cały czas czytam:

k-średnich jest wariantem EM, przy założeniu, że klastry są kuliste.

Czy ktoś może wyjaśnić powyższe zdanie? Nie rozumiem, co oznaczają sfery i jak kmeany i EM są powiązane, ponieważ jeden wykonuje przyporządkowanie probabilistyczne, a drugi w sposób deterministyczny.

Ponadto, w jakiej sytuacji lepiej jest używać klastrowania k-średnich? lub użyć klastrowania EM?

Mój na
źródło
Sferyczny oznacza identyczne macierze wariancji-kowariancji dla każdego skupienia (przy założeniu rozkładu gaussowskiego), co jest również znane jako grupowanie oparte na modelach. Jakie podejście uważasz za deterministyczne?
chl
2
Byłoby miło, gdybyś podał źródło cytowania.
ttnphns,
1
k-oznacza „zakłada”, że gromady są mniej więcej okrągłe i stałe (nie mocno wydłużone, zakrzywione lub po prostu pierścieniowe) chmury w przestrzeni euklidesowej. Nie muszą pochodzić z normalnych dystrybucji. EM tego wymaga (lub przynajmniej znany konkretny rodzaj dystrybucji).
ttnphns,

Odpowiedzi:

38

K oznacza

  1. Twarde przypisanie punktu danych do jednego konkretnego klastra przy konwergencji.
  2. Wykorzystuje normę L2 podczas optymalizacji (punkt normalny L2 Min {Theta} i jej współrzędne środka ciężkości).

EM

  1. Soft przypisuje punkt do klastrów (więc daje prawdopodobieństwo dowolnego punktu należącego do dowolnego środka ciężkości).
  2. Nie zależy to od normy L2, ale opiera się na Oczekiwaniu, tj. Prawdopodobieństwie punktu należącego do określonego klastra. To powoduje, że środki K są tendencyjne w stosunku do kulistych skupisk.
Sharan Srinivasan
źródło
57

Nie ma „algorytmu k-średnich”. Istnieje algorytm MacQueensa dla k-średnich, algorytm Lloyda / Forgy'ego dla k-średnich, metoda Hartigan-Wong, ...

Nie ma też „algorytmu” EM. Jest to ogólny schemat wielokrotnego przewidywania prawdopodobieństw, a następnie maksymalizacji modelu. Najpopularniejszy wariant EM jest również znany jako „Modelowanie mieszanki Gaussa” (GMM), gdzie modelem są wielowymiarowe rozkłady Gaussa.

Można rozważyć algorytm Lloyds składa się z dwóch kroków:

  • krok E, w którym każdy obiekt jest przypisany do środka ciężkości, tak że jest przypisany do najbardziej prawdopodobnego skupienia.
  • krok M, w którym model (= centroidy) jest ponownie obliczany (= optymalizacja najmniejszych kwadratów).

... iteracja tych dwóch kroków, tak jak zrobiła to Lloyd, sprawia, że ​​jest to efektywny przykład ogólnego schematu EM. Różni się od GMM, że:

  • używa twardego partycjonowania, tzn. każdy obiekt jest przypisany do dokładnie jednego klastra
  • model jest tylko centroidami, nie uwzględnia się kowariancji ani wariancji
Anony-Mus
źródło
Czy potrafisz trochę rozwinąć warianty średnich? Rzuciłem okiem na elementy uczenia statystycznego (Hastie, Tibshirani, Friedman), rozdział 14 ... popierają one ideę istnienia „ algorytmu średnich”. kk
Elvis
10
Wiele książek jest równych k-średnich z algorytmem Lloydsa, ale nigdy nie nazwał go k-średnich. MacQueen wprowadził nazwę k-średnich. Niestety: wiele książek używa tutaj niepoprawnych nazw . K-średnich jest problemem, tylko jedno popularne rozwiązanie. W rzeczywistości R domyślnie uruchomi Hartigan-Wong, aby rozwiązać kilometry.
Anony-Mousse,
4

Oto przykład, gdybym robił to w mplusie, co może być pomocne i uzupełnić bardziej wyczerpujące odpowiedzi:

Powiedzmy, że mam 3 ciągłe zmienne i chcę na ich podstawie zidentyfikować klastry. Określiłbym model mieszany (bardziej konkretnie w tym przypadku model profilu utajonego), zakładając niezależność warunkową (obserwowane zmienne są niezależne, biorąc pod uwagę członkostwo w klastrze) jako:

Model: 
%Overall%
v1* v2* v3*;  ! Freely estimated variances
[v1 v2 v3];   ! Freely estimated means

Uruchomiłbym ten model wiele razy, za każdym razem określając inną liczbę klastrów, i wybrałem rozwiązanie, które najbardziej mi się podoba (sam w sobie jest to rozległy temat).

Aby następnie uruchomić k-średnich, określiłbym następujący model:

Model: 
%Overall%
v1@0 v2@0 v3@0;  ! Variances constrained as zero
[v1 v2 v3];      ! Freely estimated means

Przynależność do klasy opiera się zatem na odległości od średnich obserwowanych zmiennych. Jak stwierdzono w innych odpowiedziach, wariancje nie mają z tym nic wspólnego.

Zaletą robienia tego w mplus jest to, że są to modele zagnieżdżone, dzięki czemu można bezpośrednio przetestować, czy ograniczenia powodują gorsze dopasowanie, czy nie, oprócz możliwości porównania niezgodności w klasyfikacji między dwiema metodami. Oba te modele, nawiasem mówiąc, można oszacować za pomocą algorytmu EM, więc różnica dotyczy naprawdę więcej modelu.

Jeśli myślisz w przestrzeni 3-D, to 3 oznacza punkt ... a wariancje trzy osie elipsoidy biegną przez ten punkt. Jeśli wszystkie trzy wariancje są takie same, otrzymasz kulę.

DL Dahly
źródło
Dziękuję za ten przykład. Bardzo pomaga naprawić niektóre pomysły.
Myna