Как определить k при использовании кластеризации k-средних?

в принципе, вы хотите, чтобы найти баланс между двумя переменными: количество кластеров (k) и средняя дисперсия кластеров. Вы хотите минимизировать первое, а также минимизировать второе. Конечно, по мере увеличения числа кластеров средняя дисперсия уменьшается (вплоть до тривиального случая k=n и дисперсия=0).

Как всегда в анализе данных, нет ни одного истинного подхода, который работает лучше, чем все остальные во всех случаи. В конце концов, вы должны использовать свой собственный здравый смысл. Для этого он помогает построить количество кластеров против средней дисперсии (что предполагает, что вы уже запустили алгоритм для нескольких значений k). Затем вы можете использовать количество кластеров в колене кривой.

Да, вы можете найти лучшее количество кластеров с помощью метода Elbow, но мне было трудно найти значение кластеров из графика elbow с помощью скрипта. Вы можете наблюдать график локтя и найти точку локтя самостоятельно, но это было много работы, находя его из сценария.

другой вариант-использовать Метод Силуэт, чтобы найти его. Результат от силуэта полностью соответствует результату от локтевого метода в R.

вот что я делавший.

#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")

надеюсь, что это помогает!!

посмотреть этой бумага," изучение k в k-означает " Грег Хэмерли, Чарльз Элкан. Он использует тест Гаусса для определения правильного количества кластеров. Кроме того, авторы утверждают, что этот метод лучше, чем BIC, который упоминается в принятом ответе.

может быть кто-то новичок, как я ищу пример кода. информация для silhouette_score доступно здесь.

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)

сначала построить минимальное остовное дерево ваши данные. Удаление самых дорогих ребер K-1 разбивает дерево на K кластеров,
таким образом, вы можете построить MST один раз, посмотрите на кластерные расстояния / метрики для различных K, и возьмите колено кривой.

Это работает только для Single-linkage_clustering, но для этого это быстро и легко. Кроме того, MSTs делают хорошие визуальные эффекты.
См., например, участок MST под статистика.визуализация stackexchange программное обеспечение для кластеризации.

есть что-то под названием эмпирическое правило. Он говорит, что количество кластеров может быть вычислено по k = (n/2)^0,5, где n-общее количество элементов из вашей выборки. Вы можете проверить достоверность этой информации на следующем документе:

http://www.ijarcsms.com/docs/paper/volume1/issue6/V1I6-0015.pdf

существует также другой метод, называемый G-means, где ваше распределение следует за гауссовым распределением или нормальным распределением. Оно состоит в увеличении k до тех пор, пока все ваши K групп не будут следовать Гауссовскому распределению. Это требует много статистики, но может быть сделано. Вот источник:

http://papers.nips.cc/paper/2526-learning-the-k-in-k-means.pdf

надеюсь, это поможет!

если вы используете MATLAB, любую версию с 2013b, то есть, вы можете использовать функцию evalclusters чтобы узнать, что должно быть оптимальным k для данного набора данных.

эта функция позволяет выбрать один из 3 алгоритмов кластеризации - kmeans,linkage и gmdistribution.

он также позволяет выбрать один из 4 Критериев оценки кластеризации -CalinskiHarabasz,DaviesBouldin,gap и silhouette.

Я удивлен, что никто не упомянул эту прекрасную статью: http://www.ee.columbia.edu / ~dpwe / документы / PhamDN05-kmeans.pdf

после нескольких других предложений, я, наконец, наткнулся на эту статью, читая этот блог: https://datasciencelab.wordpress.com/2014/01/21/selection-of-k-in-k-means-clustering-reloaded/

после этого я реализовал его в Scala, реализация, которая для моих случаев использования обеспечивает действительно хорошее результаты. Вот код:

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

моя идея заключается в использовании Коэффициент Силуэт найти оптимальное число кластеров (K). Объяснение деталей составляет здесь.

предполагая, что у вас есть матрица данных под названием DATA, вы можете выполнить разбиение вокруг медоидов с оценкой количества кластеров (путем анализа силуэта) следующим образом:

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

один из возможных ответов-использовать Метаэвристический алгоритм, такой как генетический алгоритм, чтобы найти k. Это просто. вы можете использовать случайный K (в некотором диапазоне) и оценить функцию подгонки генетического алгоритма с некоторой мерой, такой как силуэт И найти лучшее основание K на функции подгонки.

https://en.wikipedia.org/wiki/Silhouette_ (кластеризация)

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

другой подход заключается в использовании самоорганизующихся карт (SOP) для поиска оптимального количества кластеров. Сом (самоорганизующаяся карта) - это неконтролируемый нейрон сетевая методология, которая требует только ввода используется для кластеризация для решения задач. Этот подход используется в статье о сегментации клиентов.

ссылка на документ

Abdellah Amine et al., Модель сегментации клиентов в электронной коммерции с использованием Методы кластеризации и модель LRFM: Случай интернет-магазинов в Марокко, Всемирная Академия наук, техники и технологий Международный журнал компьютерной и информационной инженерии Vol: 9, Нет:8, 2015, 1999 - 2010

Я использовал решение, которое я нашел здесь:http://efavdb.com/mean-shift/ и это сработало очень хорошо для меня:

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