# scoding=utf-8# Agglomerative Hierarchical Clustering(AHC)import pylab as plfrom operator import itemgetterfrom collections import OrderedDict,Counterpoints = [[int(eachpoint.split('#')[0]), int(eachpoint.split('#')[1])] for eachpoint in open("points","r")]# 初始時(shí)每個(gè)點(diǎn)指派為單獨(dú)一簇groups = [idx for idx in range(len(points))]# 計(jì)算每個(gè)點(diǎn)對(duì)之間的距離disP2P = {}for idx1,point1 in enumerate(points):  for idx2,point2 in enumerate(points):    if (idx1 < idx2):      distance = pow(abs(point1[0]-point2[0]),2) + pow(abs(point1[1]-point2[1]),2)      disP2P[str(idx1)+"#"+str(idx2)] = distance# 按距離降序?qū)⒏鱾€(gè)點(diǎn)對(duì)排序disP2P = OrderedDict(sorted(disP2P.iteritems(), key=itemgetter(1), reverse=True))# 當(dāng)前有的簇個(gè)數(shù)groupNum = len(groups)# 過分合并會(huì)帶入噪音點(diǎn)的影響，當(dāng)簇?cái)?shù)減為finalGroupNum時(shí)，停止合并finalGroupNum = int(groupNum*0.1)while groupNum > finalGroupNum:  # 選取下一個(gè)距離最近的點(diǎn)對(duì)  twopoins,distance = disP2P.popitem()  pointA = int(twopoins.split('#')[0])  pointB = int(twopoins.split('#')[1])  pointAGroup = groups[pointA]  pointBGroup = groups[pointB]  # 當(dāng)前距離最近兩點(diǎn)若不在同一簇中，將點(diǎn)B所在的簇中的所有點(diǎn)合并到點(diǎn)A所在的簇中，此時(shí)當(dāng)前簇?cái)?shù)減1  if(pointAGroup != pointBGroup):    for idx in range(len(groups)):      if groups[idx] == pointBGroup:        groups[idx] = pointAGroup    groupNum -= 1# 選取規(guī)模最大的3個(gè)簇，其他簇歸為噪音點(diǎn)wantGroupNum = 3finalGroup = Counter(groups).most_common(wantGroupNum)finalGroup = [onecount[0] for onecount in finalGroup]dropPoints = [points[idx] for idx in range(len(points)) if groups[idx] not in finalGroup]# 打印規(guī)模最大的3個(gè)簇中的點(diǎn)group1 = [points[idx] for idx in xrange(len(points)) if groups[idx]==finalGroup[0]]group2 = [points[idx] for idx in xrange(len(points)) if groups[idx]==finalGroup[1]]group3 = [points[idx] for idx in xrange(len(points)) if groups[idx]==finalGroup[2]]pl.plot([eachpoint[0] for eachpoint in group1], [eachpoint[1] for eachpoint in group1], 'or')pl.plot([eachpoint[0] for eachpoint in group2], [eachpoint[1] for eachpoint in group2], 'oy')pl.plot([eachpoint[0] for eachpoint in group3], [eachpoint[1] for eachpoint in group3], 'og')  # 打印噪音點(diǎn)，黑色pl.plot([eachpoint[0] for eachpoint in dropPoints], [eachpoint[1] for eachpoint in dropPoints], 'ok')  pl.show()