如何实现K-Means ++算法?
cluster-analysis
k-means
language-agnostic
machine-learning
5
0

我无法完全理解K-Means ++算法 。我很感兴趣如何挑选第一个k重心,即初始化,其余的就像原始的K-Means算法一样

  1. 使用的概率函数是基于距离还是高斯?
  2. 同时,为新的质心选取了最远的距离点(与其他质心相对)。

我将逐步解释并举例说明。 维基百科中的那个还不够清楚。同样,注释良好的源代码也将有所帮助。如果您使用的是6个数组,请告诉我们哪个数组适合什么。

参考资料:
Stack Overflow
收藏
评论
共 3 个回答
高赞 时间 活跃

一线。

假设我们需要选择2个聚类中心,而不是像随机选择所有聚类中心那样(就像我们用简单的k均值所做的那样),我们将随机选择第一个聚类中心,然后找到离第一个中心最远的点{这些点很可能会不属于第一个聚类中心,因为它们离它很远},并在这些远点附近分配第二个聚类中心。

收藏
评论

我已经根据Toby Segaran撰写的《 Collective Intelligence》一书和此处提供的k-menas ++初始化,准备了k-means ++的完整源代码实现。

实际上,这里有两个距离函数。对于最初的质心,使用基于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

收藏
评论

有趣的问题。感谢您使本文引起我的注意-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
收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号