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

https://stackoverflow.com/questions/1793532

22-09-2019
|

Вопрос

я изучал около кластеризация k-средних, и непонятно одно: как вы выбираете значение k.Это просто вопрос проб и ошибок или есть что-то большее?

Решение

Вы можете максимизировать байесовский информационный критерий (BIC):

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

куда L(X | C) это логарифмическая правдоподобность набора данных X Согласно модели C, p это количество параметров в модели C, а также n это количество точек в наборе данных. Видеть "X-Means: расширение K-Мицы с эффективной оценкой количества кластеров " Дэн Пеллег и Эндрю Мур в ICML 2000.

Другой подход - начать с большой ценности для k и продолжайте снимать центроиды (уменьшая K), пока он больше не уменьшит длину описания. Видеть «Принцип MDL для надежной квантовой векторов» Хорст Бишоф, Элес Леонардис и Александр Селб в Анализ и приложения тол. 2, с. 59-72, 1999.

Наконец, вы можете начать с одного кластера, а затем продолжать разделять кластеры, пока точки, назначенные каждому кластеру, не получит гауссового распределения. В "Изучение k в k-означает" (NIPS 2003), Грег Хамерли и Чарльз Элкан показывают некоторые доказательства того, что это работает лучше, чем BIC, и что BIC не наказывает сложность модели.

Другие советы

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

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

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

Итак, другой вариант - использовать Силуэт Метод Чтобы найти это. Результат из силуэта полностью соответствует результату метода локтя в 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")

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

Может быть, кто -то новичкам, как я, ищет пример кода. Информация для 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 в K-Means» Грега Хамерли, Чарльза Элкана. Он использует гауссовый тест для определения правильного количества кластеров. Кроме того, авторы утверждают, что этот метод лучше, чем BIC, который упоминается в принятом ответе.

Есть нечто, называемое эмпирическим правилом. В нем говорится, что количество кластеров может быть рассчитано как 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

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

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

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

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

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

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

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

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

После этого я реализовал его в 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_(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})

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

Ссылка на статью

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

Если вы не знаете номера кластеров k, которые необходимо указать в качестве параметра k-средних, есть четыре способа найти их автоматически:

Алгоритм G-средств:он автоматически определяет количество кластеров, используя статистический тест, чтобы решить, следует ли разделить центр k-средних на два.Этот алгоритм использует иерархический подход для определения количества кластеров, основанный на статистической проверке гипотезы о том, что подмножество данных соответствует распределению Гаусса (непрерывная функция, которая аппроксимирует точное биномиальное распределение событий), а в противном случае он разбивает кластер. .Он начинается с небольшого количества центров, скажем, только с одного кластера (k=1), затем алгоритм разбивает его на два центра (k=2) и снова разбивает каждый из этих двух центров (k=4), имея четыре центра в общий.Если G-средства не принимают эти четыре центра, то ответом будет предыдущий шаг:в этом случае два центра (k=2).Это количество кластеров, на которые будет разделен ваш набор данных.G-средние очень полезны, когда у вас нет оценки количества кластеров, которые вы получите после группировки экземпляров.Обратите внимание, что неудобный выбор параметра «k» может дать неправильные результаты.Параллельная версия g-средних называется р-значит.Источники G-средств:источник 1 источник 2 источник 3
Х-значит:новый алгоритм, который эффективно ищет пространство расположения кластеров и количество кластеров для оптимизации байесовского информационного критерия (BIC) или показателя информационного критерия Акаике (AIC).Эта версия k-средних находит число k, а также ускоряет k-средние.
Онлайн-средние или потоковые k-средства:он позволяет выполнять k-средние, сканируя все данные один раз, и автоматически находит оптимальное количество k.Spark реализует это.
Алгоритм среднего сдвига:это метод непараметрической кластеризации, который не требует предварительного знания количества кластеров и не ограничивает форму кластеров.Кластеризация среднего сдвига направлена на обнаружение «капель» в гладкой плотности выборок.Это алгоритм на основе центроидов, который работает путем обновления кандидатов на центроиды, чтобы они были средним значением точек в заданной области.Эти кандидаты затем фильтруются на этапе постобработки, чтобы исключить почти дубликаты и сформировать окончательный набор центроидов.Источники: источник1, источник2, источник3

Я использовал решение, которое я нашел здесь: 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()

Привет, я сделаю это простым и прямым, чтобы объяснить, мне нравится определять кластеры, используя библиотеку «NBClust».

Теперь, как использовать функцию «NBClust», чтобы определить правильное количество кластеров: вы можете проверить фактический проект в GitHub с фактическими данными и кластерами - расширение на этот алгоритм «Kmeans», также выполняемый с использованием правильного числа «центров».

Ссылка на проект GitHub: https://github.com/rutvijbhutaiya/thailand-customer-engagement-facebook

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow