Python-层次聚类-Hierarchical clustering

lomg

层次聚类关键方法
#coding:UTF-8
#Hierarchical clustering 层次聚类
from E_distance import Euclidean_distance
from yezi import yezi
class bicluster:
def __init__(self, vec, left=None,right=None,distance=0.0,id=None):
self.left = left
self.right = right  #每次聚类都是一对数据，left保存其中一个数据，right保存另一个
self.vec = vec      #保存两个数据聚类后形成新的中心
self.id = id     
self.distance = distance
def hcluster(blogwords,n) :
biclusters = [ bicluster(vec = blogwords, id = i ) for i in range(len(blogwords)) ]
distances = {}
flag = None;
currentclusted = -1
while(len(biclusters) > n) : #假设聚成n个类
min_val = 999999999999; #Python的无穷大应该是inf
biclusters_len = len(biclusters)
for i in range(biclusters_len-1) :
for j in range(i + 1, biclusters_len) :
if distances.get((biclusters.id,biclusters[j].id)) == None:
distances[(biclusters.id,biclusters[j].id)] = Euclidean_distance(biclusters.vec,biclusters[j].vec)
d = distances[(biclusters.id,biclusters[j].id)]
if d < min_val :
min_val = d
flag = (i,j)
bic1,bic2 = flag #解包bic1 = i , bic2 = j
newvec = [(biclusters[bic1].vec + biclusters[bic2].vec)/2 for i in range(len(biclusters[bic1].vec))] #形成新的类中心，平均
newbic = bicluster(newvec, left=biclusters[bic1], right=biclusters[bic2], distance=min_val, id = currentclusted) #二合一
currentclusted -= 1
del biclusters[bic2] #删除聚成一起的两个数据，由于这两个数据要聚成一起
del biclusters[bic1]
biclusters.append(newbic)#补回新聚类中心
clusters = [yezi(biclusters) for i in range(len(biclusters))] #深度优先搜索叶子节点，用于输出显示
return biclusters,clusters


深度优先显示：
def yezi(clust):
if clust.left == None and clust.right == None :
return [clust.id]
return yezi(clust.left) + yezi(clust.right)


欧氏距离：
#Euclidean_distance
from math import sqrt
def Euclidean_distance(vector1,vector2):
length = len(vector1)
TSum = sum([pow((vector1 - vector2),2) for i in range(len(vector1))])
SSum = sqrt(TSum)
return SSum
　　层次聚类算法：


给定要聚类的N的对象以及N*N的距离矩阵(或者是相似性矩阵), 层次式聚类方法的基本步骤(参看S.C. Johnson in 1967)如下:

• 
  
  将每个对象归为一类, 共得到N类, 每类仅包含一个对象. 类与类之间的距离就是它们所包含的对象之间的距离.
  
• 
  
  找到最接近的两个类并合并成一类, 于是总的类数少了一个.
  
• 
  
  重新计算新的类与所有旧类之间的距离.
  
• 
  
  重复第2步和第3步, 直到最后合并成一个类为止(此类包含了N个对象).
  

　　由于层次聚类计算量巨大，所以通常不用来计算大量的数据，不过可以用层次聚类来选取K-means算法的初始类中心。
　　例子（不规范，只是用来显示输入和输出的格式）：

　　参考：http://www.iyunv.com/coser/archive/2013/04/10/3013044.html