K-均值聚类算法（集体智慧编程）

上篇博客中讲到的分级聚类算法为我们返回了一棵形象直观的树，但是这个方法有两个缺点。

1.在没有额外的投入的情况下，树形视图是不会真正将数据拆分成不同组的。

2.该算法的计算量非常惊人，因为我们必须计算每两个配对项之间的关系，并且在合并项之后，这些关系还得重新再计算，所以在处理很大规模的数据集时，该算法的运行速度会非常缓慢。

 

K-均值聚类完全不同于分级聚类，因为我们会预先告诉算法希望生成的聚类数量，然后算法会根据数据的结构状况来确定聚类的大小。

 

K-均值聚类算法首先会随机确定k个中心位置，然后将各个数据项分配给最临近的中心点。待分配完成之后，聚类中心就会移到分配给该聚类的所有节点的平均位置处，然后整个分配过程重新开始。这一过程会一直重复下去，直到分配过程不再产出变化为止。

 如图所示，有A,B,C,D,E五个数据项，随机生成两个数据项（黑点处），将距离最近的的数据合为一类，取平均后生成新的两个数据项（黑点处），再次将距离最近的数据合为一类，如此重复，直到数据固定。

 

mark

import random

def kcluster(rows,distance=pearson,k=4):
  # 确定每个点的最大值和最小值，给随机数定个范围
  ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows])) 
  for i in range(len(rows[0]))]

  # 随机建立k个中心点
  clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0] 
  for i in range(len(rows[0]))] for j in range(k)]
  
  lastmatches=None
  # 设定循环100次，看你的数据大小，次数自定义
  for t in range(100):
    print 'Iteration %d' % t
    bestmatches=[[] for i in range(k)]
    
    # 在每一行中寻找距离最近的中心点
    for j in range(len(rows)):
      row=rows[j]
      bestmatch=0
      for i in range(k):
        d=distance(clusters[i],row)
        if d<distance(clusters[bestmatch],row): bestmatch=i
      bestmatches[bestmatch].append(j)

    # 如果结果与上一次的相同，则整个过程结束
    if bestmatches==lastmatches: break
    lastmatches=bestmatches
    
    # 将中心点移到其所有成员的平均位置处
    for i in range(k):
      avgs=[0.0]*len(rows[0])
      if len(bestmatches[i])>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

使用分级聚类算法的数据

blognames,words,data = clusters.readfile('blogdata1.txt')

kclust = clusters.kcluster(data,k=10)

print [blognames[r] for r in kclust[1]]

 

此算法的关键在于k值的大小，不同的k值会有不同的结果，因为多尝试几个k值，选用最合适的为恬！