Studiowałem na temat grupowania k-średnich i jedna rzecz, która nie jest jasna, to sposób wyboru wartości k. Czy to tylko kwestia prób i błędów, czy może to coś więcej?
cluster-analysis
k-means
Jason Baker
źródło
źródło
R
) tutaj: stackoverflow.com/a/15376462/1036500Odpowiedzi:
Możesz zmaksymalizować Bayesowskie kryterium informacyjne (BIC):
gdzie
L(X | C)
jest logarytmem wiarygodności zbioru danychX
zgodnie z modelemC
,p
jest liczbą parametrów w modeluC
in
jest liczbą punktów w zbiorze danych. Zobacz „X-oznacza: poszerzenie K -oznacza efektywne oszacowanie liczby klastrów” autorstwa Dana Pellega i Andrew Moore'a w ICML 2000.Innym podejściem jest rozpoczęcie od dużej wartości dla
k
i dalsze usuwanie centroid (zmniejszanie k), aż nie będzie już zmniejszać długości opisu. Zobacz „Zasada MDL dla niezawodnej kwantyzacji wektorów” Horsta Bischofa, Alesa Leonardisa i Alexandra Selba w Pattern Analysis and Applications, tom. 2, str. 59-72, 1999.Na koniec możesz zacząć od jednego klastra, a następnie dzielić klastry, aż punkty przypisane do każdego klastra będą miały rozkład Gaussa. W „Nauka k w k- oznacza” (NIPS 2003) Greg Hamerly i Charles Elkan pokazują pewne dowody na to, że działa to lepiej niż BIC i że BIC nie penalizuje złożoności modelu wystarczająco mocno.
źródło
Zasadniczo chcesz znaleźć równowagę między dwiema zmiennymi: liczbą skupień ( k ) i średnią wariancją skupień. Chcesz zminimalizować to pierwsze, jednocześnie minimalizując drugie. Oczywiście wraz ze wzrostem liczby klastrów średnia wariancja maleje (aż do trywialnego przypadku k = n i wariancji = 0).
Jak zawsze w analizie danych, nie ma jednego prawdziwego podejścia, które działa lepiej niż wszystkie inne we wszystkich przypadkach. Ostatecznie musisz kierować się własnym rozsądkiem. W tym celu pomaga wykreślić liczbę klastrów względem średniej wariancji (przy założeniu, że algorytm został już uruchomiony dla kilku wartości k ). Następnie możesz użyć liczby klastrów na kolanie krzywej.
źródło
Tak, najlepszą liczbę klastrów można znaleźć za pomocą metody Elbow, ale znalezienie wartości skupień na wykresie łokciowym za pomocą skryptu było dla mnie kłopotliwe. Możesz obserwować wykres łokcia i samodzielnie znaleźć punkt łokcia, ale znalezienie go ze skryptu było dużo pracy.
Więc inną opcją jest użycie metody Silhouette, aby ją znaleźć. Wynik z Silhouette jest całkowicie zgodny z wynikiem uzyskanym metodą Łokcia w R.
Oto co zrobiłem.
Mam nadzieję, że to pomoże!!
źródło
Może być kimś początkującym, takim jak ja, szukającym przykładu kodu. informacje na temat silhouette_score są dostępne tutaj.
źródło
Spójrz na ten artykuł „Nauka k w k-środków” Grega Hamerly'ego, Charlesa Elkana. Wykorzystuje test Gaussa do określenia właściwej liczby klastrów. Ponadto autorzy twierdzą, że ta metoda jest lepsza niż BIC, o którym mowa w przyjętej odpowiedzi.
źródło
Jest coś, co nazywa się „praktyczną zasadą”. Mówi, że liczbę klastrów można obliczyć według
k = (n/2)^0.5
gdzie n to całkowita liczba elementów z twojej próbki. Możesz sprawdzić prawdziwość tych informacji na następującym papierze:
http://www.ijarcsms.com/docs/paper/volume1/issue6/V1I6-0015.pdf
Istnieje również inna metoda zwana G-średnich, w której rozkład jest zgodny z rozkładem Gaussa lub rozkładem normalnym. Polega ona na zwiększaniu k, aż wszystkie twoje grupy k podążą za rozkładem Gaussa. Wymaga wielu statystyk, ale można to zrobić. Oto źródło:
http://papers.nips.cc/paper/2526-learning-the-k-in-k-means.pdf
Mam nadzieję, że to pomoże!
źródło
Najpierw utwórz minimalne drzewo opinające swoich danych. Usunięcie najdroższych krawędzi K-1 dzieli drzewo na klastry K,
dzięki czemu można raz zbudować MST, spojrzeć na odstępy / metryki klastrów dla różnych K i zająć kolano krzywej.
Działa to tylko dla Single-linkage_clustering , ale w tym celu jest szybkie i łatwe. Ponadto MST zapewniają dobre efekty wizualne.
Zobacz na przykład wykres MST w oprogramowaniu do wizualizacji stats.stackexchange do grupowania .
źródło
Dziwię się, że nikt nie wspomniał o tym doskonałym artykule: http://www.ee.columbia.edu/~dpwe/papers/PhamDN05-kmeans.pdf
Po wykonaniu kilku innych sugestii, w końcu natknąłem się na ten artykuł podczas czytania tego bloga: https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/
Potem zaimplementowałem go w Scali, implementacji, która w moich przypadkach użycia daje naprawdę dobre wyniki. Oto kod:
źródło
Jeśli używasz MATLAB-a, dowolnej wersji od 2013b, czyli możesz skorzystać z funkcji,
evalclusters
aby dowiedzieć się, co powinnok
być optymalne dla danego zbioru danych.Funkcja ta pozwala wybrać spośród 3 klastrów - algorytmy
kmeans
,linkage
igmdistribution
.To także pozwala wybierać spośród kryteriów oceny 4 klastrów -
CalinskiHarabasz
,DaviesBouldin
,gap
isilhouette
.źródło
Jeśli nie znasz liczb skupień k, które należy podać jako parametr k-średnich, istnieją cztery sposoby, aby je znaleźć automatycznie:
Algortithm średnich G: automatycznie wykrywa liczbę klastrów za pomocą testu statystycznego, aby zdecydować, czy podzielić środek k-średnich na dwie. Algorytm ten przyjmuje hierarchiczne podejście do wykrywania liczby klastrów, w oparciu o test statystyczny dla hipotezy, że podzbiór danych jest zgodny z rozkładem Gaussa (funkcja ciągła, która aproksymuje dokładny dwumianowy rozkład zdarzeń), a jeśli nie, dzieli klaster . Rozpoczyna się od małej liczby centrów, powiedzmy tylko jednego klastra (k = 1), następnie algorytm dzieli go na dwa centra (k = 2) i ponownie dzieli każde z tych dwóch centrów (k = 4), mając cztery centra w całkowity. Jeśli G-średnie nie akceptują tych czterech centrów, to odpowiedzią jest poprzedni krok: w tym przypadku dwa centra (k = 2). Jest to liczba klastrów, na które zostanie podzielony zbiór danych. G-średnie jest bardzo przydatne, gdy nie masz oszacowania liczby klastrów, które otrzymasz po zgrupowaniu swoich instancji. Zauważ, że niewygodny wybór parametru „k” może dać błędne wyniki. Nazywa się równoległa wersja g-średnichp-środki . G-średnie źródła: źródło 1 źródło 2 źródło 3
x-oznacza : nowy algorytm, który efektywnie przeszukuje przestrzeń lokalizacji klastrów i liczbę klastrów w celu optymalizacji miar Bayesian Information Criterion (BIC) lub Akaike Information Criterion (AIC). Ta wersja k-średnich znajduje liczbę k, a także przyspiesza k-średnich.
K-średnie online lub k-średnie strumieniowe: umożliwia wykonanie k-średnich poprzez jednokrotne skanowanie całych danych i automatycznie znajduje optymalną liczbę k. Spark to wdraża.
Algorytm MeanShift : jest to nieparametryczna technika grupowania, która nie wymaga wcześniejszej wiedzy o liczbie klastrów i nie ogranicza kształtu klastrów. Grupowanie z przesunięciem średnim ma na celu wykrycie „plamek” w płynnej gęstości próbek. Jest to algorytm oparty na centroidach, który działa poprzez aktualizację kandydatów na centroidy, aby były średnią z punktów w danym regionie. Ci kandydaci są następnie filtrowani na etapie przetwarzania końcowego, aby wyeliminować prawie duplikaty, tworząc ostateczny zestaw centroid. Źródła: źródło1 , źródło2 , źródło3
źródło
Skorzystałem z rozwiązania, które znalazłem tutaj: http://efavdb.com/mean-shift/ i działało bardzo dobrze:
źródło
Moim pomysłem jest użycie współczynnika sylwetki, aby znaleźć optymalny numer skupienia (K). Szczegółowe wyjaśnienie znajduje się tutaj .
źródło
Zakładając, że masz macierz danych o nazwie
DATA
, możesz wykonać podział wokół medoidów z oszacowaniem liczby skupień (przez analizę sylwetki) w następujący sposób:źródło
Jedną z możliwych odpowiedzi jest użycie Meta Heuristic Algorithm, takiego jak Genetic Algorithm, do znalezienia k. To proste. możesz użyć losowego K (w pewnym zakresie) i ocenić funkcję dopasowania algorytmu genetycznego za pomocą pewnych pomiarów, takich jak sylwetka i znajdź najlepszą bazę K na podstawie funkcji dopasowania.
https://en.wikipedia.org/wiki/Silhouette_(clustering)
źródło
źródło
Innym podejściem jest użycie map samoorganizujących się (SOP) w celu znalezienia optymalnej liczby klastrów. SOM (Self-Organizing Map) to nienadzorowana metodologia sieci neuronowych, która wymaga tylko danych wejściowych, jest wykorzystywana do grupowania w celu rozwiązywania problemów. Podejście to zastosowano w artykule o segmentacji klientów.
Odniesienie do artykułu to
Abdellah Amine et al., Customer Segmentation Model in E-commerce Using Clustering Techniques and LRFM Model: The Case of Online Stores in Morocco, World Academy of Science, Engineering and Technology International Journal of Computer and Information Engineering Vol: 9, No: 8 , 2015, 1999 - 2010
źródło
Cześć, zrobię to prosto i prosto do wyjaśnienia, lubię określać klastry za pomocą biblioteki „NbClust”.
Teraz, jak użyć funkcji „NbClust”, aby określić odpowiednią liczbę klastrów: Możesz sprawdzić rzeczywisty projekt na Githubie z aktualnymi danymi i klastrami - Rozszerzenie tego algorytmu `` kmeans '' również wykonano przy użyciu odpowiedniej liczby `` centrów ''.
Link do projektu Github: https://github.com/RutvijBhutaiya/Thailand-Customer-Engagement-Facebook
źródło
Możesz wybrać liczbę klastrów, wizualnie sprawdzając punkty danych, ale wkrótce zdasz sobie sprawę, że w tym procesie jest wiele niejednoznaczności dla wszystkich z wyjątkiem najprostszych zestawów danych. Nie zawsze jest to złe, ponieważ uczysz się bez nadzoru, a proces etykietowania ma nieodłączną subiektywność. Tutaj posiadanie wcześniejszych doświadczeń z tym konkretnym problemem lub czymś podobnym pomoże ci wybrać odpowiednią wartość.
Jeśli chcesz uzyskać wskazówkę dotyczącą liczby klastrów, których powinieneś użyć, możesz zastosować metodę Łokcia:
Przede wszystkim oblicz sumę kwadratów błędów (SSE) dla niektórych wartości k (na przykład 2, 4, 6, 8 itd.). SSE definiuje się jako sumę kwadratu odległości między każdym elementem klastra a jego środkiem ciężkości. Matematycznie:
SSE = ∑Ki = 1∑x∈cidist (x, ci) 2
Jeśli wykreślisz k względem SSE, zobaczysz, że błąd maleje wraz ze wzrostem k; Dzieje się tak dlatego, że gdy liczba klastrów rośnie, powinny one być mniejsze, więc zniekształcenie jest również mniejsze. Ideą metody łokcia jest wybranie k, przy którym SSE gwałtownie spada. Daje to „efekt kolanka” na wykresie, jak widać na poniższym obrazku:
W tym przypadku k = 6 jest wartością wybraną przez metodę Łokcia. Weź pod uwagę, że metoda Elbow jest metodą heurystyczną i jako taka może, ale nie musi, działać dobrze w twoim konkretnym przypadku. Czasami jest więcej niż jeden łokieć lub nie ma go wcale. W takich sytuacjach zwykle kończy się obliczeniem najlepszego k, oceniając, jak dobrze k-średnich działa w kontekście konkretnego problemu grupowania, który próbujesz rozwiązać.
źródło
Pracowałem nad pakietem Pythona kneed (algorytm Kneedle). Znajduje numer klastra dynamicznie jako punkt, w którym krzywa zaczyna się spłaszczać. Mając zestaw wartości x i y, kneed zwróci punkt kolana funkcji. Punkt kolanowy to punkt maksymalnej krzywizny. Oto przykładowy kod.
Y = [+7.342,1301373073857, +6.881,7109460930769, +6.531,1657905495022,
+6.356,2255554679778, +6.209,8382535595829, +6.094,9052166741121, +5.980,0191582610196, +5.880,1869867848218, +5.779,8957906367368, +5.691,1879324562778, +5.617,5153566271356, +5.532,2613232619951, +5.467,352265375117, +5.395,4493783888756, +5.345,3459908298091, +5.290,6769823693812, +5.243,5271656371888, +5.207,2501206569532, +5.164,9617535255456]
x = zakres (1, len (y) +1)
import z kolan KneeLocator kn = KneeLocator (x, y, krzywa = 'wypukła', kierunek = 'malejący')
nadruk (kn. kolano)
źródło