40

ウィキペディアのページ では、k-means でクラスターの数を決定するためのエルボ法が説明されています。scipy の組み込みメソッドは実装を提供しますが、彼らがそれを呼び出すときの歪みがどのように計算されるかを理解しているかどうかはわかりません。

より正確には、クラスターによって説明される分散のパーセンテージをクラスターの数に対してグラフ化すると、最初のクラスターは多くの情報を追加します (多くの分散を説明します) が、ある時点で限界ゲインが低下し、グラフ。

関連する重心を持つ次の点があると仮定すると、この尺度を計算する良い方法は何ですか?

points = numpy.array([[ 0,  0],
       [ 0,  1],
       [ 0, -1],
       [ 1,  0],
       [-1,  0],
       [ 9,  9],
       [ 9, 10],
       [ 9,  8],
       [10,  9],
       [10,  8]])

kmeans(pp,2)
(array([[9, 8],
   [0, 0]]), 0.9414213562373096)

私は特に、点と重心だけを指定して 0.94.. 測定値を計算することを検討しています。scipy の組み込みメソッドのいずれかを使用できるかどうか、または自分で作成する必要があるかどうかはわかりません。多数のポイントに対してこれを効率的に行う方法について何か提案はありますか?

要するに、私の質問（関連するすべて）は次のとおりです。

  • 距離行列と、どの点がどのクラスターに属しているかのマッピングが与えられた場合、エルボー プロットを描画するために使用できる尺度を計算する良い方法は何ですか?
  • コサイン類似度などの異なる距離関数を使用すると、方法論はどのように変化しますか?

編集 2: 歪み

from scipy.spatial.distance import cdist
D = cdist(points, centroids, 'euclidean')
sum(numpy.min(D, axis=1))

最初のポイント セットの出力は正確です。ただし、別のセットを試すと:

>>> pp = numpy.array([[1,2], [2,1], [2,2], [1,3], [6,7], [6,5], [7,8], [8,8]])
>>> kmeans(pp, 2)
(array([[6, 7],
       [1, 2]]), 1.1330618877807475)
>>> centroids = numpy.array([[6,7], [1,2]])
>>> D = cdist(points, centroids, 'euclidean')
>>> sum(numpy.min(D, axis=1))
9.0644951022459797

kmeansデータセット内のポイントの総数で値を割っているように見えるため、最後の値は一致しないと思います。

編集 1: パーセント分散

これまでの私のコード (Denis の K-means 実装に追加する必要があります):

centres, xtoc, dist = kmeanssample( points, 2, nsample=2,
        delta=kmdelta, maxiter=kmiter, metric=metric, verbose=0 )

print "Unique clusters: ", set(xtoc)
print ""
cluster_vars = []
for cluster in set(xtoc):
    print "Cluster: ", cluster

    truthcondition = ([x == cluster for x in xtoc])
    distances_inside_cluster = (truthcondition * dist)

    indices = [i for i,x in enumerate(truthcondition) if x == True]
    final_distances = [distances_inside_cluster[k] for k in indices]

    print final_distances
    print np.array(final_distances).var()
    cluster_vars.append(np.array(final_distances).var())
    print ""

print "Sum of variances: ", sum(cluster_vars)
print "Total Variance: ", points.var()
print "Percent: ", (100 * sum(cluster_vars) / points.var())

k=2 の場合の出力は次のとおりです。

Unique clusters:  set([0, 1])

Cluster:  0
[1.0, 2.0, 0.0, 1.4142135623730951, 1.0]
0.427451660041

Cluster:  1
[0.0, 1.0, 1.0, 1.0, 1.0]
0.16

Sum of variances:  0.587451660041
Total Variance:  21.1475
Percent:  2.77787757437

私の実際のデータセットで（私には正しく見えません！）：

Sum of variances:  0.0188124746402
Total Variance:  0.00313754329764
Percent:  599.592510943
Unique clusters:  set([0, 1, 2, 3])

Sum of variances:  0.0255808508714
Total Variance:  0.00313754329764
Percent:  815.314672809
Unique clusters:  set([0, 1, 2, 3, 4])

Sum of variances:  0.0588210052519
Total Variance:  0.00313754329764
Percent:  1874.74720416
Unique clusters:  set([0, 1, 2, 3, 4, 5])

Sum of variances:  0.0672406353655
Total Variance:  0.00313754329764
Percent:  2143.09824556
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6])

Sum of variances:  0.0646291452839
Total Variance:  0.00313754329764
Percent:  2059.86465055
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7])

Sum of variances:  0.0817517362176
Total Variance:  0.00313754329764
Percent:  2605.5970695
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8])

Sum of variances:  0.0912820650486
Total Variance:  0.00313754329764
Percent:  2909.34837831
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

Sum of variances:  0.102119601368
Total Variance:  0.00313754329764
Percent:  3254.76309585
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

Sum of variances:  0.125549475536
Total Variance:  0.00313754329764
Percent:  4001.52168834
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])

Sum of variances:  0.138469402779
Total Variance:  0.00313754329764
Percent:  4413.30651542
Unique clusters:  set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
4

2 に答える 2

55

Kmeansに関する限り、歪みは停止基準として使用されます (2 つの反復間の変化がしきい値よりも小さい場合、収束と見なされます)。

一連の点と重心から計算する場合は、次のようにします (コードはpdist2関数を使用して MATLAB にありますが、Python/Numpy/Scipy で簡単に書き直す必要があります)。

% data
X = [0 1 ; 0 -1 ; 1 0 ; -1 0 ; 9 9 ; 9 10 ; 9 8 ; 10 9 ; 10 8];

% centroids
C = [9 8 ; 0 0];

% euclidean distance from each point to each cluster centroid
D = pdist2(X, C, 'euclidean');

% find closest centroid to each point, and the corresponding distance
[distortions,idx] = min(D,[],2);

結果：

% total distortion
>> sum(distortions)
ans =
           9.4142135623731

編集＃1：

私はこれをいじる時間がありました..これは、 'Fisher Iris Dataset' (4 つの特徴、150 のインスタンス) に適用された KMeans クラスタリングの例です。を反復処理しk=1..10、エルボー カーブをプロットし、K=3クラスターの数として選択し、結果の散布図を表示します。

ポイントとセントロイドを考慮して、クラスター内の分散 (歪み) を計算する方法をいくつか含めたことに注意してください。このscipy.cluster.vq.kmeans関数は、デフォルトでこの測定値を返します (距離測定としてユークリッドで計算されます)。関数を使用してscipy.spatial.distance.cdist、選択した関数で距離を計算することもできます (同じ距離測定を使用してクラスターの重心を取得した場合: @Denisにはそのための解決策があります)、それから歪みを計算します。

import numpy as np
from scipy.cluster.vq import kmeans,vq
from scipy.spatial.distance import cdist
import matplotlib.pyplot as plt

# load the iris dataset
fName = 'C:\\Python27\\Lib\\site-packages\\scipy\\spatial\\tests\\data\\iris.txt'
fp = open(fName)
X = np.loadtxt(fp)
fp.close()

##### cluster data into K=1..10 clusters #####
K = range(1,10)

# scipy.cluster.vq.kmeans
KM = [kmeans(X,k) for k in K]
centroids = [cent for (cent,var) in KM]   # cluster centroids
#avgWithinSS = [var for (cent,var) in KM] # mean within-cluster sum of squares

# alternative: scipy.cluster.vq.vq
#Z = [vq(X,cent) for cent in centroids]
#avgWithinSS = [sum(dist)/X.shape[0] for (cIdx,dist) in Z]

# alternative: scipy.spatial.distance.cdist
D_k = [cdist(X, cent, 'euclidean') for cent in centroids]
cIdx = [np.argmin(D,axis=1) for D in D_k]
dist = [np.min(D,axis=1) for D in D_k]
avgWithinSS = [sum(d)/X.shape[0] for d in dist]

##### plot ###
kIdx = 2

# elbow curve
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(K, avgWithinSS, 'b*-')
ax.plot(K[kIdx], avgWithinSS[kIdx], marker='o', markersize=12, 
    markeredgewidth=2, markeredgecolor='r', markerfacecolor='None')
plt.grid(True)
plt.xlabel('Number of clusters')
plt.ylabel('Average within-cluster sum of squares')
plt.title('Elbow for KMeans clustering')

# scatter plot
fig = plt.figure()
ax = fig.add_subplot(111)
#ax.scatter(X[:,2],X[:,1], s=30, c=cIdx[k])
clr = ['b','g','r','c','m','y','k']
for i in range(K[kIdx]):
    ind = (cIdx[kIdx]==i)
    ax.scatter(X[ind,2],X[ind,1], s=30, c=clr[i], label='Cluster %d'%i)
plt.xlabel('Petal Length')
plt.ylabel('Sepal Width')
plt.title('Iris Dataset, KMeans clustering with K=%d' % K[kIdx])
plt.legend()

plt.show()

肘のカーブ 散布図

編集＃2：

コメントに応えて、NIST 手書きの数字データセットを使用した別の完全な例を以下に示します。これには、0 から 9 までの数字の 1797 の画像があり、それぞれのサイズは 8 x 8 ピクセルです。上記の実験を少し変更して繰り返します。主成分分析を適用して、次元を 64 から 2 に減らします。

import numpy as np
from scipy.cluster.vq import kmeans
from scipy.spatial.distance import cdist,pdist
from sklearn import datasets
from sklearn.decomposition import RandomizedPCA
from matplotlib import pyplot as plt
from matplotlib import cm

##### data #####
# load digits dataset
data = datasets.load_digits()
t = data['target']

# perform PCA dimensionality reduction
pca = RandomizedPCA(n_components=2).fit(data['data'])
X = pca.transform(data['data'])

##### cluster data into K=1..20 clusters #####
K_MAX = 20
KK = range(1,K_MAX+1)

KM = [kmeans(X,k) for k in KK]
centroids = [cent for (cent,var) in KM]
D_k = [cdist(X, cent, 'euclidean') for cent in centroids]
cIdx = [np.argmin(D,axis=1) for D in D_k]
dist = [np.min(D,axis=1) for D in D_k]

tot_withinss = [sum(d**2) for d in dist]  # Total within-cluster sum of squares
totss = sum(pdist(X)**2)/X.shape[0]       # The total sum of squares
betweenss = totss - tot_withinss          # The between-cluster sum of squares

##### plots #####
kIdx = 9        # K=10
clr = cm.spectral( np.linspace(0,1,10) ).tolist()
mrk = 'os^p<dvh8>+x.'

# elbow curve
fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(KK, betweenss/totss*100, 'b*-')
ax.plot(KK[kIdx], betweenss[kIdx]/totss*100, marker='o', markersize=12, 
    markeredgewidth=2, markeredgecolor='r', markerfacecolor='None')
ax.set_ylim((0,100))
plt.grid(True)
plt.xlabel('Number of clusters')
plt.ylabel('Percentage of variance explained (%)')
plt.title('Elbow for KMeans clustering')

# show centroids for K=10 clusters
plt.figure()
for i in range(kIdx+1):
    img = pca.inverse_transform(centroids[kIdx][i]).reshape(8,8)
    ax = plt.subplot(3,4,i+1)
    ax.set_xticks([])
    ax.set_yticks([])
    plt.imshow(img, cmap=cm.gray)
    plt.title( 'Cluster %d' % i )

# compare K=10 clustering vs. actual digits (PCA projections)
fig = plt.figure()
ax = fig.add_subplot(121)
for i in range(10):
    ind = (t==i)
    ax.scatter(X[ind,0],X[ind,1], s=35, c=clr[i], marker=mrk[i], label='%d'%i)
plt.legend()
plt.title('Actual Digits')
ax = fig.add_subplot(122)
for i in range(kIdx+1):
    ind = (cIdx[kIdx]==i)
    ax.scatter(X[ind,0],X[ind,1], s=35, c=clr[i], marker=mrk[i], label='C%d'%i)
plt.legend()
plt.title('K=%d clusters'%KK[kIdx])

plt.show()

肘のカーブ digits_centroids PCA_compare

一部のクラスターが実際に識別可能な数字に対応している様子を確認できますが、他のクラスターは単一の数字と一致していません。

注: K-meansscikit-learnの実装が(他の多くのクラスタリング アルゴリズムやさまざまなクラスタリング メトリクスと同様に) に含まれています。これは別の同様の例です。

于 2011-07-11T21:51:44.530 に答える
6

単純なクラスター測定:
1) 各ポイントから最も近いクラスター中心まで「サンバースト」光線を描画し、
2) すべての光線の長さ — 距離 (ポイント、中心、メトリック =... ) — を調べます。

および 1 クラスターの場合metric="sqeuclidean"、長さの 2 乗の平均は総分散X.var()です。2 つのクラスターの場合、それは少なくなります... N 個のクラスターまで、長さはすべて 0 です。「説明された分散の割合」は 100 % - この平均です。

is-it-possible-to-specify-your-own-distance-function-using-scikits-learn-k-means の下のコード:

def distancestocentres( X, centres, metric="euclidean", p=2 ):
    """ all distances X -> nearest centre, any metric
            euclidean2 (~ withinss) is more sensitive to outliers,
            cityblock (manhattan, L1) less sensitive
    """
    D = cdist( X, centres, metric=metric, p=p )  # |X| x |centres|
    return D.min(axis=1)  # all the distances

数値の長いリストと同様に、これらの距離はさまざまな方法で調べることができます: np.mean()、np.histogram() ... プロット、視覚化は簡単ではありません。stats.stackexchange.com/questions/tagged/clustering
も参照してください。特に、クラスター化アルゴリズムが意味のある結果を生成するのに十分なほどデータが「クラスター化」されているかどうかを確認する方法は?

于 2011-07-11T11:39:28.040 に答える