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值，選用最合适的為恬！