1 #!/usr/bin/python
  2 # -*- coding: utf-8 -*-
  3 
  4 from queue import PriorityQueue
  5 import math
  6 import codecs
  7 
  8 
  9 """
 10 层次聚类
 11 """
 12 class HCluster:
 13 
 14     #一列的中位数
 15     def getMedian(self,alist):
 16         tmp = list(alist)
 17         tmp.sort()
 18         alen = len(tmp)
 19         if alen % 2 == 1:
 20             return tmp[alen // 2]
 21         else:
 22             return (tmp[alen // 2] + tmp[(alen // 2) - 1]) / 2
 23 
 24     #对数值型数据进行归一化，使用绝对标准分[绝对标准差->asd=sum(x-u)/len(x),x的标准分->(x-u)/绝对标准差，u是中位数]
 25     def normalize(self,column):
 26         median = self.getMedian(column)
 27         asd = sum([abs(x - median) for x in column]) / len(column)
 28         result = [(x - median) / asd for x in column]
 29         return result
 30 
 31     def __init__(self,filepath):
 32         self.data=http://www.mamicode.com/{}
 33         self.counter=0
 34         self.queue=PriorityQueue()
 35         line_1=True#开头第一行
 36         with codecs.open(filepath,‘r‘,‘utf-8‘) as f:
 37             for line in f:
 38                 #第一行为描述信息
 39                 if line_1:
 40                     line_1=False
 41                     header=line.split(‘,‘)
 42                     self.cols=len(header)
 43                     self.data=http://www.mamicode.com/[[] for i in range(self.cols)]
 44                 else:
 45                     instances=line.split(‘,‘)
 46                     toggle=0
 47                     for instance in range(self.cols):
 48                         if toggle==0:
 49                             self.data[instance].append(instances[instance])
 50                             toggle=1
 51                         else:
 52                             self.data[instance].append(float(instances[instance]))
 53         #归一化数值列
 54         for i in range(1,self.cols):
 55             self.data[i]=self.normalize(self.data[i])
 56 
 57         #欧氏距离计算元素i到所有其它元素的距离，放到邻居字典中，比如i=1,j=2...，结构如i=1的邻居-》{2: ((1,2), 1.23),  3: ((1, 3), 2.3)... }
 58         #找到最近邻
 59         #基于最近邻将元素放到优先队列中
 60         #data[0]放的是label标签，data[1]和data[2]是数值型属性
 61         rows=len(self.data[0])
 62         for i in range(rows):
 63             minDistance=10000
 64             nearestNeighbor=0
 65             neighbors={}
 66             for j in range(rows):
 67                 if i!=j:
 68                     dist=self.distance(i,j)
 69                     if i<j:
 70                         pair=(i,j)
 71                     else:
 72                         pair=(j,i)
 73                     neighbors[j]=(pair,dist)
 74                     if dist<minDistance:
 75                         minDistance=dist
 76                         nearestNeighbor=j
 77             #创建最近邻对
 78             if i<nearestNeighbor:
 79                 nearestPair=(i,nearestNeighbor)
 80             else:
 81                 nearestPair=(nearestNeighbor,i)
 82             #放入优先对列中，(最近邻距离，counter,[label标签名，最近邻元组，所有邻居])
 83             self.queue.put((minDistance,self.counter,[[self.data[0][i]],nearestPair,neighbors]))
 84             self.counter+=1
 85 
 86     #欧氏距离,d(x,y)=math.sqrt(sum((x-y)*(x-y)))
 87     def distance(self,i,j):
 88         sumSquares=0
 89         for k in range(1,self.cols):
 90             sumSquares+=(self.data[k][i]-self.data[k][j])**2
 91         return math.sqrt(sumSquares)
 92 
 93     #聚类
 94     def cluster(self):
 95         done=False
 96         while not done:
 97             topOne=self.queue.get()
 98             nearestPair=topOne[2][1]
 99             if not self.queue.empty():
100                 nextOne=self.queue.get()
101                 nearPair=nextOne[2][1]
102                 tmp=[]
103                 #nextOne是否是topOne的最近邻，如不是继续找
104                 while nearPair!=nearestPair:
105                     tmp.append((nextOne[0],self.counter,nextOne[2]))
106                     self.counter+=1
107                     nextOne=self.queue.get()
108                     nearPair=nextOne[2][1]
109                 #重新加回Pop出的不相等最近邻的元素
110                 for item in tmp:
111                     self.queue.put(item)
112 
113                 if len(topOne[2][0])==1:
114                     item1=topOne[2][0][0]
115                 else:
116                     item1=topOne[2][0]
117                 if len(nextOne[2][0])==1:
118                     item2=nextOne[2][0][0]
119                 else:
120                     item2=nextOne[2][0]
121                 #联合两个最近邻族成一个新族
122                 curCluster=(item1,item2)
123                 #下面使用单连接方法建立新族中的邻居距离元素，一：计算上面新族的最近邻。二：建立新的邻居。如果 item1和item3距离是2，item2和item3距离是4，则在新族中的距离是2
124                 minDistance=10000
125                 nearestPair=()
126                 nearestNeighbor=‘‘
127                 merged={}
128                 nNeighbors=nextOne[2][2]
129                 for key,value in topOne[2][2].items():
130                     if key in nNeighbors:
131                         if nNeighbors[key][1]<value[1]:
132                             dist=nNeighbors[key]
133                         else:
134                             dist=value
135                         if dist[1]<minDistance:
136                             minDistance=dist[1]
137                             nearestPair=dist[0]
138                             nearestNeighbor=key
139                         merged[key]=dist
140                 if merged=={}:
141                     return curCluster
142                 else:
143                     self.queue.put((minDistance,self.counter,[curCluster,nearestPair,merged]))
144                     self.counter+=1
145 
146 if __name__==‘__main__‘:
147     hcluser=HCluster(‘filePath‘)
148     cluser=hcluser.cluster()
149     print(cluser)