كيف يمكنني تحديد k عند استخدام تجميع الوسائل k؟

https://stackoverflow.com/questions/1793532

22-09-2019
|

سؤال

لقد كنت أدرس حول ك-يعني التجميع, ، والشيء الوحيد غير الواضح هو كيفية اختيار قيمة k.هل الأمر مجرد مسألة تجربة وخطأ، أم أن هناك ما هو أكثر من ذلك؟

المحلول

يمكنك زيادة معيار المعلومات البايزي (BIC):

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

أين L(X | C) هو احتمالية سجل مجموعة البيانات X وفقا للنموذج C, p هو عدد المعلمات في النموذج C, ، و n هو عدد النقاط في مجموعة البيانات. نرى "X-Means: تمتد ك-أوالي مع تقدير فعال لعدد المجموعات " بقلم دان بيليج وأندرو مور في ICML 2000.

نهج آخر هو أن تبدأ بقيمة كبيرة ل k والحفاظ على إزالة المناطق الوسطى (تقليل K) حتى لم يعد يقلل من طول الوصف. نرى "مبدأ MDL لكميات ناقلات قوية" بقلم هورست بيشوف ، أليس ليونارديس ، وألكساندر سيلب في تحليل الأنماط والتطبيقات المجلد. 2 ، ص. 59-72 ، 1999.

أخيرًا ، يمكنك البدء بمجموعة واحدة ، ثم استمر في تقسيم المجموعات حتى يكون للنقاط المخصصة لكل مجموعة توزيع غاوسي. في "تعلم ك في ك-يعني" (NIPS 2003) ، يظهر جريج هامرلي وتشارلز إلكان بعض الأدلة على أن هذا يعمل بشكل أفضل من BIC ، وأن BIC لا يعاقب تعقيد النموذج بقوة كافية.

نصائح أخرى

في الأساس، تريد إيجاد توازن بين متغيرين:عدد المجموعات (ك) ومتوسط التباين للمجموعات.تريد تقليل الأول مع تقليل الأخير أيضًا.وبطبيعة الحال، مع زيادة عدد المجموعات، ينخفض متوسط التباين (حتى الحالة التافهة ك=ن والتباين = 0).

كما هو الحال دائمًا في تحليل البيانات، لا يوجد نهج حقيقي واحد يعمل بشكل أفضل من جميع الأساليب الأخرى في جميع الحالات.في النهاية، عليك أن تستخدم أفضل حكم لديك.لذلك، من المفيد رسم عدد المجموعات مقابل متوسط التباين (والذي يفترض أنك قمت بالفعل بتشغيل الخوارزمية لعدة قيم من ك).ثم يمكنك استخدام عدد المجموعات عند ركبة المنحنى.

نعم ، يمكنك العثور على أفضل عدد من المجموعات التي تستخدم طريقة الكوع ، لكنني وجدت أنه من المقلق العثور على قيمة المجموعات من الرسم البياني الكوع باستخدام البرنامج النصي. يمكنك مراقبة الرسم البياني للكوع والعثور على نقطة الكوع بنفسك ، ولكن كان الكثير من العمل يجدها من البرنامج النصي.

لذلك خيار آخر هو الاستخدام طريقة صورة ظلية للعثور عليه. النتيجة من صورة ظلية تتوافق تمامًا مع النتيجة من طريقة الكوع في 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 ، حيث يتبع توزيعك توزيع Gaussian ، أو التوزيع الطبيعي. وهو يتكون من زيادة K حتى تتبع جميع مجموعات K الخاص بك توزيع غاوسي. يتطلب الكثير من الإحصائيات ، ولكن يمكن القيام به. هذا هو المصدر:

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

آمل أن يساعد هذا!

أول بناء أ الحد الأدنى الشجرة الممتدة من بياناتك. إن إزالة الحواف الأكثر تكلفة من K-1 تقسيم الشجرة إلى مجموعات K ،
حتى تتمكن من بناء MST مرة واحدة ، انظر إلى Spacings / Metrics العنقودية لمختلف K ، واستقل ركبة المنحنى.

هذا يعمل فقط ل واحد الارتباط واحد، ولكن لذلك فهو سريع وسهل. بالإضافة إلى ذلك ، MSTS تصنع صورًا جيدة.
انظر على سبيل المثال مؤامرة MST تحتSTATS.STACKEXCHANGE POSTIONICASION.

إذا كنت تستخدم MATLAB ، أي إصدار منذ عام 2013 ب ، يمكنك الاستفادة من الوظيفة 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-

بعد ذلك قمت بتطبيقه في 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, ، يمكنك إجراء التقسيم حول medoids مع تقدير عدد المجموعات (عن طريق تحليل صورة ظلية) مثل هذا:

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 (خريطة التنظيم الذاتي) هي منهجية الشبكة العصبية غير الخاضعة للإشراف ، والتي تحتاج فقط إلى استخدام المدخلات لتجميع لحل المشكلات. هذا النهج المستخدم في ورقة حول تجزئة العملاء.

مرجع الورقة

عبد الله أمين وآخرون ، نموذج تجزئة العملاء في التجارة الإلكترونية باستخدام تقنيات التجميع ونموذج LRFM: حالة المتاجر عبر الإنترنت في المغرب ، الأكاديمية العالمية للعلوم والهندسة والتكنولوجيا المجلة الهندسية للكمبيوتر والمعلومات المجلد: 9 ، لا: 8 ، 2015 ، 1999 - 2010

إذا كنت لا تعرف أرقام المجموعات k التي يجب توفيرها كمعلمة لـ k-means، فهناك أربع طرق للعثور عليها تلقائيًا:

G-يعني خوارزمية:يكتشف عدد المجموعات تلقائيًا باستخدام اختبار إحصائي لتحديد ما إذا كان سيتم تقسيم مركز k-means إلى قسمين.تتبع هذه الخوارزمية نهجًا هرميًا للكشف عن عدد المجموعات، بناءً على اختبار إحصائي لفرضية أن مجموعة فرعية من البيانات تتبع توزيع غاوسي (دالة مستمرة تقارب التوزيع الدقيق ذي الحدين للأحداث)، وإذا لم يكن الأمر كذلك فإنها تقسم المجموعة .يبدأ بعدد صغير من المراكز، على سبيل المثال مجموعة واحدة فقط (k=1)، ثم تقوم الخوارزمية بتقسيمها إلى مركزين (k=2) وتقسم كل مركز من هذين المركزين مرة أخرى (k=4)، بحيث يكون هناك أربعة مراكز في المجموع.إذا كانت G-means لا تقبل هذه المراكز الأربعة فالإجابة هي الخطوة السابقة:مركزين في هذه الحالة ( ك = 2).هذا هو عدد المجموعات التي سيتم تقسيم مجموعة البيانات الخاصة بك إليها.تعد وسائل G مفيدة جدًا عندما لا يكون لديك تقدير لعدد المجموعات التي ستحصل عليها بعد تجميع المثيلات الخاصة بك.لاحظ أن الاختيار غير المناسب للمعلمة "k" قد يعطيك نتائج خاطئة.النسخة الموازية من g-means تسمى ع يعني.G- يعني المصادر:المصدر 1 المصدر 2 المصدر 3
يعني س:خوارزمية جديدة تبحث بكفاءة في مساحة مواقع المجموعات وعدد المجموعات لتحسين مقياس المعلومات الافتراضية (BIC) أو معيار المعلومات Akaike (AIC).هذا الإصدار من k-means يعثر على الرقم k ويسرع أيضًا k-means.
وسائل k عبر الإنترنت أو وسائل k المتدفقة:يسمح بتنفيذ وسائل k عن طريق مسح البيانات بأكملها مرة واحدة ويجد تلقائيًا العدد الأمثل لـ k.سبارك تنفذه.
خوارزمية MeanShift:إنها تقنية تجميع غير بارامترية لا تتطلب معرفة مسبقة بعدد المجموعات، ولا تقيد شكل المجموعات.يهدف تجميع التحول المتوسط إلى اكتشاف "النقط" في كثافة سلسة من العينات.إنها خوارزمية تعتمد على النقط الوسطى، والتي تعمل عن طريق تحديث المرشحين للنقط الوسطى ليكون متوسط النقاط داخل منطقة معينة.يتم بعد ذلك تصفية هؤلاء المرشحين في مرحلة ما بعد المعالجة لإزالة التكرارات القريبة لتشكيل المجموعة النهائية من النقط الوسطى.مصادر: المصدر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" التي يتم أيضًا القيام بها باستخدام العدد الصحيح من "المراكز".

رابط مشروع جيثب: https://github.com/rutvijbhutaiya/thailand-customer-enging-facebook

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow