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

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?

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.

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.

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!!

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)

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.

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!

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 .

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]]
}

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.

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

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

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

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

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)

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

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

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

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

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)