cluster-analysis - k-means クラスタリングを使用する場合、k を決定するにはどうすればよいですか?

Question

私はk-means clusteringについて研究してきましたが、明確でないことの 1 つは、k の値をどのように選択するかです。それは単なる試行錯誤の問題ですか、それともそれ以上のことはありますか?

score 146 · Accepted Answer

ベイズ情報量基準（BIC）を最大化できます。

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

ここで、はモデルによるL(X | C)データセットの対数尤度、はモデル内のパラメーターの数、はデータセット内のポイントの数です。ICML2000のDanPellegとAndrewMooreによる「X-means：クラスター数の効率的な推定による K -meansの拡張」を参照してください。XCpCn

もう1つのアプローチは、の大きな値から始めてk、説明の長さが短くならないまで重心を削除し続ける（kを減らす）ことです。パターン分析とアプリケーションvol。のHorstBischof、Ales Leonardis、AlexanderSelbによる「ロバストなベクトル量子化のためのMDL原理」を参照してください。2、p。59-72、1999。

最後に、1つのクラスターから始めて、各クラスターに割り当てられたポイントがガウス分布になるまでクラスターを分割し続けることができます。「k -meansの学習」（ NIPS 2003）で、GregHamerlyとCharlesElkanは、これがBICよりもうまく機能し、BICがモデルの複雑さに十分なペナルティを課さないという証拠を示しています。

score 37 · Accepted Answer

基本的に、クラスターの数 ( k ) とクラスターの平均分散という2 つの変数の間のバランスを見つけたいと考えています。前者を最小限に抑えながら、後者も最小限に抑える必要があります。もちろん、クラスターの数が増えると、平均分散は減少します ( k = nおよび分散 = 0 の自明なケースまで)。

データ分析では常にそうであるように、すべてのケースで他のすべてよりもうまく機能する真のアプローチはありません。最終的には、自分の最善の判断を使用する必要があります。そのためには、平均分散に対してクラスターの数をプロットすると役立ちます (これは、 kのいくつかの値に対してアルゴリズムを既に実行していることを前提としています)。次に、曲線の膝にあるクラスターの数を使用できます。

score 9 · Accepted Answer

Greg Hamerly、Charles Elkan によるこの論文「k-means での k の学習」を見てください。ガウス検定を使用して、適切なクラスター数を決定します。また、著者は、この方法は、受け入れられた回答で言及されている BIC よりも優れていると主張しています。

score 3 · Accepted Answer

2013b 以降のバージョンの MATLAB を使用している場合、関数を使用して、特定のデータセットevalclustersに最適なものを見つけることができますk。

kmeansこの関数では、、、linkageおよびの 3 つのクラスタリングアルゴリズムから選択できますgmdistribution。

CalinskiHarabaszまた、、DaviesBouldin、gapおよびの 4 つのクラスタリング評価基準から選択することもできますsilhouette。

score 3 · Accepted Answer

まず、データの最小スパニングツリーを構築します。K-1 個の最も高価なエッジを削除すると、ツリーが K 個のクラスターに分割される
ため、MST を一度構築し、さまざまな K のクラスター間隔/メトリックを調べて、曲線の屈曲点を取ることができます。

これはSingle-linkage_clusteringでのみ機能しますが、その場合は高速で簡単です。さらに、MST は優れたビジュアルを作成します。
たとえば、クラスタリング用の stats.stackexchange 視覚化ソフトウェアの下にある MST プロットを参照してください。

score 3 · Accepted Answer

誰もこの素晴らしい記事に言及していないことに驚いています: http://www.ee.columbia.edu/~dpwe/papers/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]]
}

score 2 · Accepted Answer

ここで見つけたソリューションを使用しました：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()

score 1 · Accepted Answer

私の考えは、シルエット係数を使用して最適なクラスター数 (K) を見つけることです。詳細説明はこちら。

score 1 · Accepted Answer

考えられる答えの 1 つは、遺伝的アルゴリズムのようなメタヒューリスティックアルゴリズムを使用して k を見つけることです。それは簡単です。ランダムK（ある範囲内）を使用して、遺伝的アルゴリズムのフィット関数をシルエットのような測定値で評価し、フィット関数に基づいて最適なKベースを見つけることができます。

https://en.wikipedia.org/wiki/Silhouette_(クラスタリング)

score 1 · Accepted Answer

と呼ばれるデータの行列があると仮定すると、次のDATAように (シルエット分析による) クラスター数の推定を使用して medoid の周囲で分割を実行できます。

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

cluster-analysis - k-means クラスタリングを使用する場合、k を決定するにはどうすればよいですか?

20 に答える 20

Related

Reference