快捷導(dǎo)航

Python聚類算法之凝聚層次聚類實(shí)例分析

更新時(shí)間：2015年11月20日 11:15:20 作者：intergret

這篇文章主要介紹了Python聚類算法之凝聚層次聚類的原理與具體使用技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下

本文實(shí)例講述了Python聚類算法之凝聚層次聚類。分享給大家供大家參考，具體如下：

凝聚層次聚類：所謂凝聚的，指的是該算法初始時(shí)，將每個(gè)點(diǎn)作為一個(gè)簇，每一步合并兩個(gè)最接近的簇。另外即使到最后，對(duì)于噪音點(diǎn)或是離群點(diǎn)也往往還是各占一簇的，除非過(guò)度合并。對(duì)于這里的“最接近”，有下面三種定義。我在實(shí)現(xiàn)是使用了MIN，該方法在合并時(shí)，只要依次取當(dāng)前最近的點(diǎn)對(duì)，如果這個(gè)點(diǎn)對(duì)當(dāng)前不在一個(gè)簇中，將所在的兩個(gè)簇合并就行：

單鏈(MIN):定義簇的鄰近度為不同兩個(gè)簇的兩個(gè)最近的點(diǎn)之間的距離。
全鏈(MAX):定義簇的鄰近度為不同兩個(gè)簇的兩個(gè)最遠(yuǎn)的點(diǎn)之間的距離。
組平均：定義簇的鄰近度為取自兩個(gè)不同簇的所有點(diǎn)對(duì)鄰近度的平均值。

# scoding=utf-8
# Agglomerative Hierarchical Clustering(AHC)
import pylab as pl
from operator import itemgetter
from collections import OrderedDict,Counter
points = [[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)
# 過(guò)分合并會(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 = 3
finalGroup = 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()

運(yùn)行效果截圖如下：