K-Means++アルゴリズムを完全に理解するのに問題があります。k最初の重心がどのように選択されるか、つまり、残りが元のK-Meansアルゴリズムのように初期化されることに正確に興味があります。
ステップバイステップの説明と例をいただければ幸いです。ウィキペディアのものは十分に明確ではありません。また、非常によくコメントされたソースコードも役立ちます。6つのアレイを使用している場合は、どれが何のためのものかを教えてください。
興味深い質問です。この論文に注目していただきありがとうございます-K-Means++：注意深いシードの利点
簡単に言うと、クラスターの中心は、入力された観測ベクトルのセットからランダムに最初に選択されます。以前に選択された中心の近くにないx場合、ベクトルを選択する確率は高くなります。x
これが1次元の例です。私たちの観察は[0、1、2、3、4]です。最初の中心c1、、を0とします。次のクラスター中心、、がxである確率は、c2に比例し||c1-x||^2ます。したがって、P（c2 = 1）= 1a、P（c2 = 2）= 4a、P（c2 = 3）= 9a、P（c2 = 4）= 16a、ここでa = 1 /（1 + 4 + 9 + 16）。
c2=4と仮定します。次に、P（c3 = 1）= 1a、P（c3 = 2）= 4a、P（c3 = 3）= 1a、ここでa = 1 /（1 + 4 + 1）です。
初期化手順をPythonでコーディングしました。これがあなたに役立つかどうかはわかりません。
def initialize(X, K):
C = [X[0]]
for k in range(1, K):
D2 = scipy.array([min([scipy.inner(c-x,c-x) for c in C]) for x in X])
probs = D2/D2.sum()
cumprobs = probs.cumsum()
r = scipy.rand()
for j,p in enumerate(cumprobs):
if r < p:
i = j
break
C.append(X[i])
return C
明確化して編集：の出力はcumsum、区間[0,1]を分割するための境界を与えます。これらのパーティションの長さは、対応するポイントが中心として選択される確率に等しくなります。したがって、rは[0,1]の間で均一に選択されるため、これらの間隔の1つに正確に分類されます（のためbreak）。ループは、forどのパーティションがにあるかを確認しますr。
例：
probs = [0.1, 0.2, 0.3, 0.4]
cumprobs = [0.1, 0.3, 0.6, 1.0]
if r < cumprobs[0]:
# this event has probability 0.1
i = 0
elif r < cumprobs[1]:
# this event has probability 0.2
i = 1
elif r < cumprobs[2]:
# this event has probability 0.3
i = 2
elif r < cumprobs[3]:
# this event has probability 0.4
i = 3
一発ギャグ。
2つのクラスター中心を選択する必要があるとします。すべてをランダムに選択するのではなく{単純なk平均法のように}、最初のクラスター中心をランダムに選択してから、最初の中心から最も遠い点を見つけます{これらの点はおそらく最初のクラスター中心から離れているため、最初のクラスター中心に属していません}そして、それらの遠い点の近くに2番目のクラスター中心を割り当てます。
TobySegaranによる「CollectiveIntelligence」という本とここで提供されているk-menas++の初期化に基づいて、k-means++の完全なソース実装を準備しました。
実際、ここには2つの距離関数があります。最初の重心には、numpy.innerに基づいた標準の重心が使用され、次に重心の固定には、ピアソンのものが使用されます。たぶん、ピアソンのものは最初の重心にも使用できます。彼らはそれがより良いと言います。
from __future__ import division
def readfile(filename):
lines=[line for line in file(filename)]
rownames=[]
data=[]
for line in lines:
p=line.strip().split(' ') #single space as separator
#print p
# First column in each row is the rowname
rownames.append(p[0])
# The data for this row is the remainder of the row
data.append([float(x) for x in p[1:]])
#print [float(x) for x in p[1:]]
return rownames,data
from math import sqrt
def pearson(v1,v2):
# Simple sums
sum1=sum(v1)
sum2=sum(v2)
# Sums of the squares
sum1Sq=sum([pow(v,2) for v in v1])
sum2Sq=sum([pow(v,2) for v in v2])
# Sum of the products
pSum=sum([v1[i]*v2[i] for i in range(len(v1))])
# Calculate r (Pearson score)
num=pSum-(sum1*sum2/len(v1))
den=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))
if den==0: return 0
return 1.0-num/den
import numpy
from numpy.random import *
def initialize(X, K):
C = [X[0]]
for _ in range(1, K):
#D2 = numpy.array([min([numpy.inner(c-x,c-x) for c in C]) for x in X])
D2 = numpy.array([min([numpy.inner(numpy.array(c)-numpy.array(x),numpy.array(c)-numpy.array(x)) for c in C]) for x in X])
probs = D2/D2.sum()
cumprobs = probs.cumsum()
#print "cumprobs=",cumprobs
r = rand()
#print "r=",r
i=-1
for j,p in enumerate(cumprobs):
if r 0:
for rowid in bestmatches[i]:
for m in range(len(rows[rowid])):
avgs[m]+=rows[rowid][m]
for j in range(len(avgs)):
avgs[j]/=len(bestmatches[i])
clusters[i]=avgs
return bestmatches
rows,data=readfile('/home/toncho/Desktop/data.txt')
kclust = kcluster(data,k=4)
print "Result:"
for c in kclust:
out = ""
for r in c:
out+=rows[r] +' '
print "["+out[:-1]+"]"
print 'done'
data.txt：
p1 1 5 6
p2 9 4 3
p3 2 3 1
p4 4 5 6
p5 7 8 9
p6 4 5 4
p7 2 5 6
p8 3 4 5
p9 6 7 8