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

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.

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.

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

$\alpha$$\alpha$

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.

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.

Można również sprawdzić Nienadzorowany Optimal Fuzzy Clustering który czynienia z problemem już wspomniano (stwierdzającego liczbę klastrów), który realizowany jest zmodyfikowaną wersją nim tutaj

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.

$k$

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

$k$$k$

$k$

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.

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 .

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.