如何实现K-Means++算法？

Question

我对K-Means++算法的完全理解有困难。 我对如何选择第一个k质心感兴趣，即初始化，因为其余部分与原始K-Means算法相似。

1. 概率函数是基于距离还是高斯分布？
2. 同时，最长距离点（从其他质心）被选为新质心。

我将感激一步一步的解释和示例。 Wikipedia上的解释不够清晰。 如果您使用6个数组，请告诉我们每个数组用于什么。

- Anton Andreev

---

可能是适合于 http://stats.stackexchange.com/ 的一个不错的候选。 - Chase

Answer 1

这是一个有趣的问题。感谢您让我注意到这篇论文 - K-Means++：小心选种的优势

简单来说，聚类中心最初是从输入观测向量集合中随机选择的，其中如果向量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

编辑并澄清：使用 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

- Steve Tjoa

---

对于X中的每个点，我们生成一个概率。然后cumsum应该对这些概率进行加权。我认为这个想法是给具有更高概率的点更多的权重，因此当我们进行“随机质心选择”时，我们在其中进行选择。但是我们如何知道应该给哪些点更多的权重（？）-我们还没有对probs数组进行排序，而cumsum函数使数组末尾的那些具有更大的权重（cumsum定义）。 - Anton Andreev

我的意思是cumsum具有特定的行为，可以向右累积（一个x1<x2的数组），这可能不是我们想要的 - 更多地将权重放在概率更高的点上。我们可能会在中间有更高概率的点（比在末尾的点获得更少的权重）。 - Anton Andreev

为了执行代码，我使用了“numpy”而不是“scipy”。此外，为了正确进行除法运算，我使用了“from future import division”，否则probs全部为[0,0，...]。 - Anton Andreev

如果您有大量的数据点会发生什么？您能否请检查我的问题http://stats.stackexchange.com/questions/144190/probability-for-selecting-centroids-k-means？谢谢。 - Kobe-Wan Kenobi

如果概率落在相同的值上怎么办，我的意思是如果c1 = [20,19,80]，并且碰巧c2也落在与c1相同的值上。代码应该被修复吗？并添加以下代码行 if X[i] not in C - Yoshua Joo Bin

Answer 2

一句话概括。

假设我们需要选择2个聚类中心，与简单的k均值不同的是我们不会随机选择它们。我们将随机选择第一个聚类中心，然后找到离第一个中心最远的点（这些点很可能不属于第一个聚类中心，因为它们距离它很远），并将第二个聚类中心分配给那些远离的点附近。

- pka32

Answer 3

我已经按照Toby Segaran的书籍《集体智慧》和这里提供的k-menas++初始化准备了完整的源代码实现。

实际上，这里有两个距离函数。对于初始质心，使用基于numpy.inner的标准函数，然后对于质心固定，使用Pearson函数。也许Pearson函数也可以用于初始质心。他们说这样更好。

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

这是一个数据文件，其中包含了一些数据点的坐标。每个数据点都有三个值，分别表示x、y和z坐标。

- Anton Andreev

---

代码在此处可用：a-algorithms，适用于CPython和IronPython。 - Anton Andreev