`

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值,选用最合适的为恬!

 

  • 大小: 35.7 KB
1
0
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics