Jak zdecydować o właściwej liczbie klastrów?

54

Znajdujemy centra klastrów i przypisujemy punkty do k różnych pojemników klastra w klastrowaniu k-średnich, który jest bardzo dobrze znanym algorytmem i znajduje się prawie w każdym pakiecie uczenia maszynowego w sieci. Ale brakującą i najważniejszą częścią moim zdaniem jest wybór poprawnego k. Jaka jest jego najlepsza wartość? Co rozumiemy przez najlepsze ?

Używam MATLAB-a do obliczeń naukowych, gdzie patrząc na wykresy sylwetki podano jako sposób na decyzję o omawianej tutaj k . Byłbym jednak bardziej zainteresowany podejściami bayesowskimi. Wszelkie sugestie są mile widziane.

petrichor
źródło
2
Ładne pytanie ...
Pod wizualizacją do grupowania istnieje (ahem) sposób obrazowania klastrów k i zobaczenia efektu różnych k w jednym ujęciu za pomocą MST.
den
I już odpowiedział na to pytanie z pół tuzina sposobów w Rciągu tutaj
Ben
1
Wybór „najlepszej” liczby k klastrów oznacza porównanie rozwiązań klastrowych z różnymi k - które rozwiązanie jest „lepsze”. Pod tym względem zadanie wydaje się podobne do porównania metod grupowania - co jest „lepsze” dla danych. Ogólne wytyczne są tutaj .
ttnphns

Odpowiedzi:

28

To pytanie zostało zadane kilka razy podczas stackoverflow: tutaj , tutaj i tutaj . Możesz spojrzeć na to, co tłum myśli o tym pytaniu (lub jego niewielkim wariancie).

Pozwól mi również skopiować własną odpowiedź na to pytanie, na stackoverflow.com:

Niestety nie ma sposobu na automatyczne ustawienie „właściwego” K, ani nie ma definicji tego, co jest „właściwe”. Nie ma opartej na zasadach metody statystycznej, prostej lub złożonej, która mogłaby ustawić „właściwe K”. Istnieją heurystyki, praktyczne zasady, które czasem działają, a czasem nie.

Sytuacja jest bardziej ogólna, ponieważ wiele metod grupowania ma takie parametry, i myślę, że jest to duży otwarty problem w społeczności zajmującej się badaniami klastrowymi / bez nadzoru.

carlosdc
źródło
+1 Po przeczytaniu - wydaje mi się to takie intuicyjne ... ale muszę powiedzieć, że nigdy wcześniej o tym nie myślałem. że tak naprawdę problem wyboru liczby komputerów w PCA jest równoważny problemowi wyboru liczby klastrów w K-średnich ...
Dow
2
@Dov te dwie rzeczy nie są do końca równoważne. Istnieją specyficzne miary, które można zastosować do zbadania jakości rozwiązania PCA (przede wszystkim błąd rekonstrukcji, ale także% uchwyconej wariancji itp.), I są one (głównie) spójne. Jednak w klastrowaniu często nie ma jednej „poprawnej odpowiedzi” - jedno grupowanie może być lepsze od drugiego o jedną metrykę, a odwrotność może być prawdziwa przy użyciu innej metryki. W niektórych sytuacjach dwa różne skupienia mogą być jednakowo prawdopodobne w ramach tej samej miary.
tdc
@tdc ale nie to en.wikipedia.org/wiki/... jest mniej więcej jak to improvedoutcomes.com/docs/WebSiteDocs/PCA/... ?
Dow
2
@Dov Tak, są „mniej więcej” do siebie podobni, ale mówiłem po prostu, że problem wyboru liczby klastrów jest znacznie bardziej obciążony niż wybór liczby komputerów - tzn. Nie są one „równoważne”.
tdc
1
+1 Masz rację. W pewnym
sensie
19

Po pierwsze zastrzeżenie. W klastrowaniu często nie ma jednej „poprawnej odpowiedzi” - jedno grupowanie może być lepsze od drugiego o jedną metrykę, a odwrotność może być prawdziwa przy użyciu innej metryki. W niektórych sytuacjach dwa różne skupienia mogą być jednakowo prawdopodobne w ramach tej samej miary.

Powiedziawszy to, możesz rzucić okiem na Procesy Dirichleta . Zobacz także ten samouczek .

Jeśli zaczynasz od modelu mieszanki Gaussa, masz taki sam problem jak w przypadku k-średnich - musisz wybrać liczbę klastrów. Możesz użyć dowodów modelowych, ale w tym przypadku nie będą one solidne. Tak więc sztuczka polega na użyciu procesu Dirichleta przed składnikami mieszanki, co następnie pozwala na uzyskanie potencjalnie nieskończonej liczby składników mieszanki, ale model (zwykle) automatycznie znajdzie „prawidłową” liczbę składników (przy założeniu model).

αα

tdc
źródło
1
Proces Dirichleta przy jakim parametrze stężenia? Jest to swego rodzaju odpowiednik tego samego oryginalnego pytania, k-oznacza pod jakim k? Chociaż zgadzam się, że lepiej rozumiemy rozkład Direchleta niż zachowanie złożonego algorytmu na niektórych rzeczywistych danych.
carlosdc
@carlosdc dobry punkt, zaktualizowałem odpowiedź, aby uwzględnić trochę dyskusji na temat parametru stężenia
tdc
1
Z mojego doświadczenia wynika, że ​​o wiele łatwiej jest nauczyć się parametru stężenia o ciągłej wartości, takiego jak alfa, niż ustalić liczbę skupień w modelu mieszanki skończonej. Jeśli chcesz, aby trzymać z modelu mieszaniny skończonych, i podjąć Bayesa przyczepność, nie jest odwracalny skok MCMC ( onlinelibrary.wiley.com/doi/10.1111/1467-9868.00095/abstract )
1
Świetna odpowiedź. Dodałbym artykuł Zrewidowanie K-średnich: nowe algorytmy za pomocą Bayesian Nonparametrics . Co daje proste „ciągłe” podejście do K-średnich. Dzięki optymalizacji można łatwo znaleźć optymalną wartość.
Royi
9

Używam metody Elbow :

  • Zacznij od K = 2 i zwiększaj go na każdym kroku o 1, obliczając klastry i koszty związane ze szkoleniem. Przy pewnej wartości dla K koszt dramatycznie spada, a następnie osiąga plateau, gdy go jeszcze zwiększysz. To jest wartość K, którą chcesz.

Uzasadnieniem jest to, że po tym zwiększasz liczbę klastrów, ale nowy klaster jest bardzo bliski niektórym z istniejących.

vonPetrushev
źródło
Brzmi to tak, jakby to była zasada, którą ocenia Metoda L (patrz moja odpowiedź).
wygrał
6

Rozmiary klastrów zależą w dużym stopniu zarówno od twoich danych, jak i od tego, do czego będziesz używać wyników. Jeśli używasz danych do dzielenia rzeczy na kategorie, spróbuj wyobrazić sobie, ile kategorii chcesz najpierw. Jeśli jest to wizualizacja danych, skonfiguruj ją, aby ludzie widzieli zarówno duże, jak i mniejsze klastry.

Jeśli chcesz to zautomatyzować, możesz dodać karę do zwiększenia k i obliczyć w ten sposób optymalny klaster. A potem po prostu ważysz k w zależności od tego, czy chcesz tonę klastrów, czy bardzo mało.

neuron
źródło
5

Udało mi się użyć „metody L” do określenia liczby klastrów w aplikacji geograficznej (tj. Zasadniczo problem 2d, chociaż technicznie nie euklidesowy).

Metodę L opisano tutaj: Określanie liczby klastrów / segmentów w hierarchicznych algorytmach klastrowania / segmentacji Stan Salvador i Philip Chan

Zasadniczo ocenia to dopasowanie do różnych wartości k. Wykres w kształcie litery „L” jest widoczny z optymalną wartością k reprezentowaną przez kolano na wykresie. Do obliczenia punktu kolanowego stosuje się proste obliczenie dopasowania do najmniejszych kwadratów w dwóch liniach.

Znalazłem metodę bardzo powolną, ponieważ iteracyjne k-średnie należy obliczyć dla każdej wartości k. Odkryłem również, że k-średnich działa najlepiej z wieloma przebiegami i na końcu wybranie najlepszego. Chociaż każdy punkt danych miał tylko dwa wymiary, nie można było zastosować prostej odległości pitagorejskiej. To dużo kalkulacji.

Jedną z myśli jest pominięcie każdej innej wartości k (powiedzmy) do połowy obliczeń i / lub zmniejszenie liczby iteracji k-średnich, a następnie nieznaczne wygładzenie powstałej krzywej w celu uzyskania dokładniejszego dopasowania. Zapytałem o to w StackOverflow - IMHO, pytanie wygładzające pozostaje otwartym pytaniem badawczym.

winwaed
źródło
4

k

Ale co, jeśli twój zestaw danych nie pasuje do schematu Voronoi?

kk

k

Anony-Mus
źródło
3
Chociaż opis K-średnich w pierwszym akapicie nie jest zły, może wprowadzić w błąd niektórych ludzi, którzy utożsamiają tę metodę z partycjonowaniem Voronoi na podstawie oryginalnych danych. Tak nie jest: partycja jest oparta na lokalizacjach środków klastra, które mogą nie (i zwykle nie będą) pokrywać się z żadnymi oryginalnymi danymi.
whuber
3

Ogólnie rzecz biorąc, możesz wybrać liczbę klastrów w dwóch różnych ścieżkach.

  1. oparte na wiedzy: powinieneś mieć pomysły, ile klastrów potrzebujesz z biznesowego punktu widzenia. Na przykład, jeśli jesteś klientem grupującym, powinieneś zadać sobie pytanie, po otrzymaniu tych klientów, co powinienem zrobić dalej? Może będziesz miał inne traktowanie różnych klastrów? (np. reklama przez e-mail lub telefon). Ile planujesz możliwych zabiegów? W tym przykładzie wybierzesz, że 100 klastrów nie będzie miało zbyt dużego sensu.

  2. Sterowane danymi: większa liczba klastrów jest nadmiernie dopasowana, a mniejsza liczba klastrów jest niedopasowana. Zawsze możesz podzielić dane na pół i uruchomić weryfikację krzyżową, aby zobaczyć, ile klastrów jest dobrych. Uwaga: w klastrowaniu nadal masz funkcję utraty, podobną do ustawienia nadzorowanego.

Wreszcie, zawsze powinieneś łączyć rzeczywistą wiedzę opartą na wiedzy i danych.

Haitao Du
źródło
2

Jak nikt jeszcze tego nie wskazał, pomyślałem, że podzielę się tym. Istnieje metoda zwana X-średnich, ( patrz ten link ), która szacuje odpowiednią liczbę klastrów przy użyciu kryterium informacji bayesowskiej (BIC). Zasadniczo byłoby to jak wypróbowanie środków K z różnymi K, obliczenie BIC dla każdego K i wybranie najlepszego K. Ten algorytm robi to skutecznie.

Istnieje również implementacja weka , której szczegóły można znaleźć tutaj .

rivu
źródło
0

Innym podejściem jest zastosowanie algorytmu ewolucyjnego, którego osobniki mają chromosomy o różnej długości. Każda osoba jest rozwiązaniem kandydującym: każda nosi współrzędne centroidów. Liczba centroidów i ich współrzędne są ewoluowane, aby osiągnąć rozwiązanie, które daje najlepszy wynik oceny skupień.

Ten artykuł wyjaśnia algorytm.

felipeduque
źródło