どうして判定すk利用の場合k-meansクラスタリング?

https://stackoverflow.com/questions/1793532

22-09-2019
|

質問

私について研究してい k-meansクラスタリング, り、このなかを選択の値。もうかがわせるものとなっている試行錯誤がありますか？

解決

ベイジアン情報基準（BIC）を最大化できます。

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

どこ L(X | C) データセットのログリケリアフです X モデルによると C, p モデルのパラメーターの数です C, 、と n データセットのポイント数です。見る「X-Means：拡張 k- クラスターの数を効率的に推定した平均」 ICML 2000のDan PellegとAndrew Mooreによる。

別のアプローチは、の大きな価値から始めることです k そして、それがもはや説明の長さを減らすまで、重心（Kの減少）を除去し続けます。見る「堅牢なベクターの量子化のためのMDL原則」 Horst Bischof、Ales Leonardis、およびAlexanderSelb in パターン分析とアプリケーション Vol。 2、p。 59-72、1999。

最後に、1つのクラスターから始めて、各クラスターに割り当てられたポイントがガウス分布になるまでクラスターを分割し続けることができます。の「学ぶ k の k-意味" （NIPS 2003）、Greg HamerlyとCharles Elkanは、これがBICよりもうまく機能し、BICがモデルの複雑さを十分に強く罰していないという証拠をいくつか示しています。

他のヒント

基本的に、2つの変数間のバランスを見つけたいです。クラスターの数（k）およびクラスターの平均分散。前者を最小限に抑えながら、後者も最小限に抑えたいと考えています。もちろん、クラスターの数が増えると、平均分散が減少します（の些細な場合まで k=n および分散= 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)

見るこれ Paper、「K-MeansでKを学ぶ」グレッグ・ハマリー、チャールズ・エルカン。ガウステストを使用して、適切な数のクラスターを決定します。また、著者は、この方法は、受け入れられている答えで言及されている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-means.pdf

これが役立つことを願っています！

最初にビルドa 最小スパニングツリーあなたのデータの。 K-1を取り外す最も高価なエッジは、木をKクラスターに分割し、
したがって、MSTを1回構築し、さまざまなKのクラスター間隔 /メトリックを見て、曲線の膝を取ることができます。

これはのみ機能します single-linkage_clustering、しかしそのためには速くて簡単です。さらに、MSTSは良いビジュアルを作ります。
たとえば、MSTプロットの下を参照してくださいStats.StackexChange視覚化ソフトウェアクラスタリング用.

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-means-clustering-reloaded/

その後、Scalaに実装しました。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

考えられる答えの1つは、遺伝的アルゴリズムのようなメタヒューリスティックアルゴリズムを使用して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)適切な数のクラスターの自己組織化マップ)は、教師なし神経ネットワーク方法は、ニーズの入力を使用クラスタリング問題解決のための.このアプローチの使用について顧客セグメンテーション

を参考に論文

Abdellahアミンet al., 顧客セグメンテーションモデルのEコマースを使用クラスタリング技術LRFMモデル:の場合オンライン店舗モロッコ、世界の科学と技術国際論文誌コンピュータ情報工学専攻 Vol:9,No:8 2015年1999年-2010年

クラスターkの数がk-meansにパラメーターとして提供する数字がわからない場合、自動的に見つける4つの方法があります。

G-Means Algortithm：統計テストを使用してクラスターの数を自動的に発見し、K-Meansセンターを2つに分割するかどうかを決定します。このアルゴリズムは、データのサブセットがガウス分布（イベントの正確な二項分布に近似する連続関数）に従うという仮説の統計テストに基づいて、クラスターの数を検出するために階層的なアプローチを取ります。。少数の中心から始まり、たとえば1つのクラスターのみ（k = 1）を使用してから、アルゴリズムはそれを2つの中心に分割し（k = 2）、これら2つの中心のそれぞれを再び分割し（k = 4）、4つのセンターがあります。合計。 G-Meansがこれらの4つのセンターを受け入れない場合、答えは前のステップです。この場合の2つのセンター（k = 2）。これは、データセットが分割されるクラスターの数です。 G-Meansは、インスタンスをグループ化した後に得られるクラスターの数の推定がない場合に非常に便利です。「k」パラメーターの不便な選択が間違った結果が得られる場合があることに注意してください。 G-Meansの並列バージョンが呼び出されます p-means. 。 G-Meansソース：ソース1 ソース2 ソース3
X-means: ：効率的に、クラスターの位置とクラスターの数のスペースを検索して、ベイジアン情報基準（BIC）またはアカケ情報情報基準（AIC）測定を最適化する新しいアルゴリズム。 K-Meansのこのバージョンは、K数を見つけ、K-Meansも加速します。
オンラインk-meansまたはストリーミングk-means：データ全体を1回スキャンしてk-meansを実行することを許可すると、kの最適な数が自動的に見つかります。スパークはそれを実装します。
平均シフトアルゴリズム: ：これは、クラスターの数の事前知識を必要とせず、クラスターの形状を制約しないノンパラメトリッククラスタリング手法です。平均シフトクラスタリングは、サンプルの滑らかな密度で「ブロブ」を発見することを目的としています。これは、Centroidベースのアルゴリズムであり、Centroidsの候補者を特定の領域内のポイントの平均に更新することで機能します。次に、これらの候補者は、後処理段階でフィルター処理されて、近似に近い段階を排除して、最終的な重心セットを形成します。出典：ソース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