k-means ++究竟如何工作？

Question

我無法完全理解k-means ++算法。我對如何選取前k個質心有興趣（其餘部分與原始k-means相似）。

1. 是基於距離還是高斯使用的概率函數？
2. 在同一時間內，最長距離點（從其他質心）被挑選出一個新的質心。

我會欣賞一步一步的解釋和一個例子。維基百科中的那個不夠清楚。另外一個非常好的評論源代碼也會有所幫助。如果你正在使用6個陣列，那麼請告訴我們哪個是什麼。

Answer 1

有趣的問題。感謝您將本文引入我的視線。 PDF link here of the original paper.

簡單來說，聚類中心最初從一組輸入觀察矢量的，其中選擇載體x的概率爲高，如果x不靠近任何先前選擇的中心隨機選擇。

這裏是一個一維的例子。我們的觀察結果是[0,1,2,3,4]。讓第一個中心c1爲0.下一個聚類中心c2爲x的概率與||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 

EDIT與澄清：的cumsum輸出給我們的邊界來劃分區間[0,1]。這些分區的長度等於相應點被選爲中心的概率。那麼，因爲r在[0,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 

Answer 2

我已經準備的基礎上，書「集體智慧」由託比·西格倫和第k k均值++一個完整的源執行這裏提供的設置++初始化。

事實上，這裏有兩個距離函數。對於初始質心，使用基於numpy.inner的標準質心，然後使用Pearson 1的質心固定。也許Pearson one也可以用於初始質心。他們說這樣更好。

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 

Answer 3

一行。假設我們需要選擇2個聚類中心，而不是隨機選擇它們（就像我們用簡單的k意味着的那樣），我們將隨機選擇第一個聚類中心，然後找到離第一個中心最遠的點{這些點最有可能做到不屬於第一個聚類中心，因爲它們距離它很遠}，並將第二個聚類中心分配在這些遠點附近。