Jak określić k, używając grupowania k-średnich?

142

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?

Jason Baker
źródło
34
Ah ah ... To naprawdę pytanie (o K-średniej).
mjv
czy możesz udostępnić kod funkcji L (prawdopodobieństwo logowania)? Biorąc pod uwagę środek w X, Y i punkty w (x (i = 1,2,3,4, ..., n), y (i = 1,2,3,4, .., n)), jak dostanę L?
7
link do artykułu w Wikipedii na ten temat: en.wikipedia.org/wiki/…
Amro
11
Odpowiedziałem na podobne pytanie z pół tuzina metod (używając R) tutaj: stackoverflow.com/a/15376462/1036500
Ben

Odpowiedzi:

142

Możesz zmaksymalizować Bayesowskie kryterium informacyjne (BIC):

BIC(C | X) = L(X | C) - (p / 2) * log n

gdzie L(X | C)jest logarytmem wiarygodności zbioru danych Xzgodnie z modelem C, pjest liczbą parametrów w modelu Ci njest 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 ki 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.

Vebjorn Ljosa
źródło
Świetna odpowiedź! Dla średnich X, czy wiesz, czy ogólny wynik BIC n: = k * 2 (k klastrów, każdy klaster modelowany metodą Gaussa z parametrami średniej / wariancji). Także jeśli określisz BIC „nadrzędny”> „2 dzieci” BIC, czy kiedykolwiek podzieliłbyś ten klaster ponownie w następnej iteracji?
Budric
2
@Budric, to prawdopodobnie powinny być osobne pytania, a może na stats.stackexchange.com.
Vebjorn Ljosa
37

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.

Jan Krüger
źródło
24

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.

#Dataset for Clustering
n = 150
g = 6 
set.seed(g)
d <- data.frame(x = unlist(lapply(1:g, function(i) rnorm(n/g, runif(1)*i^2))), 
                y = unlist(lapply(1:g, function(i) rnorm(n/g, runif(1)*i^2))))
mydata<-d
#Plot 3X2 plots
attach(mtcars)
par(mfrow=c(3,2))

#Plot the original dataset
plot(mydata$x,mydata$y,main="Original Dataset")

#Scree plot to deterine the number of clusters
wss <- (nrow(mydata)-1)*sum(apply(mydata,2,var))
  for (i in 2:15) {
    wss[i] <- sum(kmeans(mydata,centers=i)$withinss)
}   
plot(1:15, wss, type="b", xlab="Number of Clusters",ylab="Within groups sum of squares")

# Ward Hierarchical Clustering
d <- dist(mydata, method = "euclidean") # distance matrix
fit <- hclust(d, method="ward") 
plot(fit) # display dendogram
groups <- cutree(fit, k=5) # cut tree into 5 clusters
# draw dendogram with red borders around the 5 clusters 
rect.hclust(fit, k=5, border="red")

#Silhouette analysis for determining the number of clusters
library(fpc)
asw <- numeric(20)
for (k in 2:20)
  asw[[k]] <- pam(mydata, k) $ silinfo $ avg.width
k.best <- which.max(asw)

cat("silhouette-optimal number of clusters:", k.best, "\n")
plot(pam(d, k.best))

# K-Means Cluster Analysis
fit <- kmeans(mydata,k.best)
mydata 
# get cluster means 
aggregate(mydata,by=list(fit$cluster),FUN=mean)
# append cluster assignment
mydata <- data.frame(mydata, clusterid=fit$cluster)
plot(mydata$x,mydata$y, col = fit$cluster, main="K-means Clustering results")

Mam nadzieję, że to pomoże!!

Udeep Shakya
źródło
2
Wystarczy dodać link do samouczka Analiza sylwetki dla użytkowników Pythona scikit-learn.org/stable/auto_examples/cluster/…
Chaitanya Shivade
10

Może być kimś początkującym, takim jak ja, szukającym przykładu kodu. informacje na temat silhouette_score są dostępne tutaj.

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score

range_n_clusters = [2, 3, 4]            # clusters range you want to select
dataToFit = [[12,23],[112,46],[45,23]]  # sample data
best_clusters = 0                       # best cluster number which you will get
previous_silh_avg = 0.0

for n_clusters in range_n_clusters:
    clusterer = KMeans(n_clusters=n_clusters)
    cluster_labels = clusterer.fit_predict(dataToFit)
    silhouette_avg = silhouette_score(dataToFit, cluster_labels)
    if silhouette_avg > previous_silh_avg:
        previous_silh_avg = silhouette_avg
        best_clusters = n_clusters

# Final Kmeans for best_clusters
kmeans = KMeans(n_clusters=best_clusters, random_state=0).fit(dataToFit)
bhargav patel
źródło
9

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.

Autonomiczny
źródło
7

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!

Arthur Busqueiro
źródło
3

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 .

denis
źródło
3

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:

import breeze.linalg.DenseVector
import Kmeans.{Features, _}
import nak.cluster.{Kmeans => NakKmeans}

import scala.collection.immutable.IndexedSeq
import scala.collection.mutable.ListBuffer

/*
https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/
 */
class Kmeans(features: Features) {
  def fkAlphaDispersionCentroids(k: Int, dispersionOfKMinus1: Double = 0d, alphaOfKMinus1: Double = 1d): (Double, Double, Double, Features) = {
    if (1 == k || 0d == dispersionOfKMinus1) (1d, 1d, 1d, Vector.empty)
    else {
      val featureDimensions = features.headOption.map(_.size).getOrElse(1)
      val (dispersion, centroids: Features) = new NakKmeans[DenseVector[Double]](features).run(k)
      val alpha =
        if (2 == k) 1d - 3d / (4d * featureDimensions)
        else alphaOfKMinus1 + (1d - alphaOfKMinus1) / 6d
      val fk = dispersion / (alpha * dispersionOfKMinus1)
      (fk, alpha, dispersion, centroids)
    }
  }

  def fks(maxK: Int = maxK): List[(Double, Double, Double, Features)] = {
    val fadcs = ListBuffer[(Double, Double, Double, Features)](fkAlphaDispersionCentroids(1))
    var k = 2
    while (k <= maxK) {
      val (fk, alpha, dispersion, features) = fadcs(k - 2)
      fadcs += fkAlphaDispersionCentroids(k, dispersion, alpha)
      k += 1
    }
    fadcs.toList
  }

  def detK: (Double, Features) = {
    val vals = fks().minBy(_._1)
    (vals._3, vals._4)
  }
}

object Kmeans {
  val maxK = 10
  type Features = IndexedSeq[DenseVector[Double]]
}
eirirlar
źródło
Wdrożone w scali 2.11.7 z wiatrem 0.12 i nak 1.3
eirirlar
Cześć @eirirlar Próbuję zaimplementować ten sam kod w Pythonie - ale nie mogłem śledzić kodu na stronie. Zobacz mój post: stackoverflow.com/questions/36729826/python-k-means-clustering
piccolo
@ImranRashid Przepraszam, że testowałem tylko z dwoma wymiarami i nie jestem ekspertem w Pythonie.
eirirlar
3

Jeśli używasz MATLAB-a, dowolnej wersji od 2013b, czyli możesz skorzystać z funkcji, evalclustersaby dowiedzieć się, co powinno kbyć optymalne dla danego zbioru danych.

Funkcja ta pozwala wybrać spośród 3 klastrów - algorytmy kmeans, linkagei gmdistribution.

To także pozwala wybierać spośród kryteriów oceny 4 klastrów - CalinskiHarabasz, DaviesBouldin, gapi silhouette.

Kristada673
źródło
3

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

ciekawostka
źródło
2

Skorzystałem z rozwiązania, które znalazłem tutaj: http://efavdb.com/mean-shift/ i działało bardzo dobrze:

import numpy as np
from sklearn.cluster import MeanShift, estimate_bandwidth
from sklearn.datasets.samples_generator import make_blobs
import matplotlib.pyplot as plt
from itertools import cycle
from PIL import Image

#%% Generate sample data
centers = [[1, 1], [-.75, -1], [1, -1], [-3, 2]]
X, _ = make_blobs(n_samples=10000, centers=centers, cluster_std=0.6)

#%% Compute clustering with MeanShift

# The bandwidth can be automatically estimated
bandwidth = estimate_bandwidth(X, quantile=.1,
                               n_samples=500)
ms = MeanShift(bandwidth=bandwidth, bin_seeding=True)
ms.fit(X)
labels = ms.labels_
cluster_centers = ms.cluster_centers_

n_clusters_ = labels.max()+1

#%% Plot result
plt.figure(1)
plt.clf()

colors = cycle('bgrcmykbgrcmykbgrcmykbgrcmyk')
for k, col in zip(range(n_clusters_), colors):
    my_members = labels == k
    cluster_center = cluster_centers[k]
    plt.plot(X[my_members, 0], X[my_members, 1], col + '.')
    plt.plot(cluster_center[0], cluster_center[1],
             'o', markerfacecolor=col,
             markeredgecolor='k', markersize=14)
plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()

wprowadź opis obrazu tutaj

snoob dogg
źródło
1

Moim pomysłem jest użycie współczynnika sylwetki, aby znaleźć optymalny numer skupienia (K). Szczegółowe wyjaśnienie znajduje się tutaj .

qmaruf
źródło
1

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:

library(fpc)
maxk <- 20  # arbitrary here, you can set this to whatever you like
estimatedK <- pamk(dist(DATA), krange=1:maxk)$nc
Megatron
źródło
1

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)

Masoud
źródło
1
km=[]
for i in range(num_data.shape[1]):
    kmeans = KMeans(n_clusters=ncluster[i])#we take number of cluster bandwidth theory
    ndata=num_data[[i]].dropna()
    ndata['labels']=kmeans.fit_predict(ndata.values)
    cluster=ndata
    co=cluster.groupby(['labels'])[cluster.columns[0]].count()#count for frequency
    me=cluster.groupby(['labels'])[cluster.columns[0]].median()#median
    ma=cluster.groupby(['labels'])[cluster.columns[0]].max()#Maximum
    mi=cluster.groupby(['labels'])[cluster.columns[0]].min()#Minimum
    stat=pd.concat([mi,ma,me,co],axis=1)#Add all column
    stat['variable']=stat.columns[1]#Column name change
    stat.columns=['Minimum','Maximum','Median','count','variable']
    l=[]
    for j in range(ncluster[i]):
        n=[mi.loc[j],ma.loc[j]] 
        l.append(n)

    stat['Class']=l
    stat=stat.sort(['Minimum'])
    stat=stat[['variable','Class','Minimum','Maximum','Median','count']]
    if missing_num.iloc[i]>0:
        stat.loc[ncluster[i]]=0
        if stat.iloc[ncluster[i],5]==0:
            stat.iloc[ncluster[i],5]=missing_num.iloc[i]
            stat.iloc[ncluster[i],0]=stat.iloc[0,0]
    stat['Percentage']=(stat[[5]])*100/count_row#Freq PERCENTAGE
    stat['Cumulative Percentage']=stat['Percentage'].cumsum()
    km.append(stat)
cluster=pd.concat(km,axis=0)## see documentation for more info
cluster=cluster.round({'Minimum': 2, 'Maximum': 2,'Median':2,'Percentage':2,'Cumulative Percentage':2})
sumit
źródło
wybierasz dane i dodajesz bibliotekę i kopiujesz km = [] do Percentage ': 2}) na końcu i uruchamiasz Pythona i widzisz
sumit
Witamy w Stack Overflow! Chociaż ten kod może pomóc w rozwiązaniu problemu, nie wyjaśnia, dlaczego i / lub jak odpowiada na pytanie. Zapewnienie tego dodatkowego kontekstu znacznie poprawiłoby jego długoterminową wartość edukacyjną. Proszę edytować swoje odpowiedzi, aby dodać wyjaśnienie, w tym, co stosuje się ograniczenia i założenia.
Toby Speight
1

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

boyaronur
źródło
0

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

Rutvij
źródło
Zamiast dodawać link do github, czy możesz dodać kilka kluczowych linii kodu, które mogą pomóc innym, nawet jeśli Twój kod jest nieosiągalny?
Giulio Caccin
0

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:

wprowadź opis obrazu tutaj

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

Faisal Shahbaz
źródło
0

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)

madhuri M
źródło
Dodaj wyjaśnienie do swojej odpowiedzi, aby inni mogli się z niej nauczyć
Nico Haase