层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：
凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。
分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。 
层次凝聚的代表是AGNES(AGglomerative NESting)算法。AGNES 算法最初将每个对象作为一个簇，然后这些簇根据某些准则被一步步地合并。两个簇间的相似度有多种不同的计算方法。聚类的合并过程反复进行直到所有的对象最终满足簇数目。
层次聚类的合并算法AGNES（凝聚算法）
层次聚类的合并算法通过计算两类数据点间的相似性，对所有数据点中最为相似的两个数据点进行组合，并反复迭代这一过程。简单的说层次聚类的合并算法是通过计算每一个类别的数据点与所有数据点之间的距离来确定它们之间的相似性，距离越小，相似度越高。并将距离最近的两个数据点或类别进行组合，生成聚类树。
而当两个数据点进行组合成后，用一个新的代表点，替换原有的两个数据点，再进行下次组合。
其中距离的计算可以使用曼哈顿距离、欧几里得或者皮尔徐相似度进行计算。
距离的度量包含四种方式：
(1)最小距离（单链(MIN)）:定义簇的邻近度为不同两个簇的两个最近的点之间的距离。
(2)最大距离（全链(MAX)）:定义簇的邻近度为不同两个簇的两个最远的点之间的距离。
(3)平均距离（组平均）：定义簇的邻近度为取自两个不同簇的所有点对邻近度的平均值。
(4)均值距离（Ward 方法的接近函数）：质心方法通过计算集群的质心之间的距离来计算两个簇的接近度。对于 Ward 方法来说，两个簇的接近度指的是当两个簇合并时产生的平方误差的增量。
层次聚类树状图
将前面的每一步的计算结果以树状图的形式展现出来就是层次聚类树。最底层是原始A到G的7个数据点。依照7个数据点间的相似度组合为聚类树的第二层(A,F),(B,C),(D,E)和G。以此类推生成完整的层次聚类树状图。以下为简单的示意图。
#_*_coding:utf-8_*_
#作者 ：hjy
#创建时间 ：19-3-2 上午10:49
#文件 :AGNES.py
#IDE :PyCharm
from PIL import Image, ImageDraw
from math import sqrt
def readfile(filename):
"""
读取表格型数据，获取特征数据集
:param filename:
:return: rownames, colnames, data
"""
lines = [line for line in open(filename)]
#第一行是列标题
colnames = lines[0].strip().split('\t')[1:]
rownames = []
data = []
for line in lines[1:]:
p = line.strip().split('\t')
#每行的第一列是行名
rownames.append(p[0])
#剩余部分就是该行对应的数据
onerow = [float(x) for x in p[1:]]
data.append(onerow)
return rownames, colnames, data
def pearson(v1, v2):
"""
计算两个聚类中心点的皮尔逊相似度
:param v1:
:param v2:
:return:
"""
#简单求和
sum1 = sum(v1)
sum2 = sum(v2)
#求平方和
sum1Sq = sum([pow(v, 2) for v in v1])
sum2Sq = sum([pow(v, 2) for v in v2])
#求乘积之和
pSum =sum([v1[i] * v2[i] for i in range(len(v1))])
#计算距离
num = pSum-(sum1 * sum2/len(v1))
den = sqrt((sum1Sq - pow(sum1, 2)/len(v1)) * (sum2Sq - pow(sum2, 2)/len(v1)))
if den == 0:
return 0
return 1.0-num/den
class bicluster:
"""
定义一个聚类，包含左右子聚类
"""
def __init__(self, vec, left=None, right=None, distance=0.0, id=None):
self.left = left#左子聚类
self.right = right#右子聚类
self.vec = vec#聚类的中心
self.id = id#聚类的id
self.distance = distance#左右子聚类的距离（相似度）
def hcluster(rows, distance=pearson):
"""
根据数据集形成聚类树
:param rows:
:param distance:
:return:
"""
distance_set = {}
currentclustid = -1
#最开始聚类就是数据集中的行，每行一个聚类
clust = [bicluster(rows[i], id=i) for i in range(len(rows))]#原始集合中的聚类都设置了不同的正数id，（使用正数是为了标记这是一个叶节点）（使用不同的数是为了建立配对集合）
while len(clust) > 1:
lowestpair = (0, 1)#lowestpair用来存储距离最小的一对聚类的索引对
closest = distance(clust[0].vec, clust[1].vec)#closest用来存储最小距离
#遍历每一对聚类，寻找距离最小的一对聚类
for i in range(len(clust)):
for j in range(i+1, len(clust)):
#用distance_set来缓存距离最小的计算值
if (clust[i].id, clust[j].id) not in distance_set:
distance_set[(clust[i].id, clust[j].id)] = distance(clust[i].vec, clust[j].vec)
d = distance_set[(clust[i].id, clust[j].id)]
if d < closest:
closest = d
lowestpair = (i, j)
# 计算距离最近的两个聚类的平均值作为代表新聚类的中心点
mergevec = [(clust[lowestpair[0]].vec[i] + clust[lowestpair[1]].vec[i]) / 2.0 for i in
range(len(clust[0].vec))]
# 将距离最近的两个聚类合并成新的聚类
newcluster = bicluster(mergevec, left=clust[lowestpair[0]],
right=clust[lowestpair[1]],
distance=closest, id=currentclustid)
#不再原始集合中的聚类id设置为负数。为了标记这是一个枝节点
currentclustid -= 1
#删除旧的聚类。（因为旧的聚类已经添加为新的聚类的左右子聚类了）
del clust[lowestpair[1]]
del clust[lowestpair[0]]
clust.append(newcluster)
return clust[0] #返回聚类树
def printclust(clust, labels=None, n=0):
"""
将聚类树以类似文件系统层级结构的形式打印输出
:param clust:
:param labels:
:param n:
:return:
"""
#利用缩进来建立层级布局
for i in range(n):
print(' ', end='')
if clust.id < 0:
#负数标记代表这是一个分支
print('-')
else:
#正数标记代表这是一个叶节点
if labels == None:
print(clust.id)
else:
print(labels[clust.id])
#现在开始打印右侧分支和左侧分支
if clust.left != None:
printclust(clust.left, labels=labels, n=n+1)
if clust.right != None:
printclust(clust.right, labels=labels, n= n+1)
def getheight(clusttree):
"""
绘制树状图--获取聚类数要显示完整需要的高度
:param clusttree:
:return:
"""
#若是叶节点则高度为1
if clusttree.left == None and clusttree.left == None:
return 1
#否则，高度为左右分枝的高度之和
return getheight(clusttree.left) + getheight(clusttree.right)
def getdepth(clusttree):
"""
绘制树状图--获取聚类树要显示完整的深度（宽度）
:param clusttree:
:return:
"""
#一个叶节点的距离是0.0
if clusttree.left == None and clusttree.right == None:
return 0
#一个叶节点的距离=左右两侧分支中距离较大者+该支点自身的距离
return max(getdepth(clusttree.left), getdepth(clusttree.right)) + clusttree.distance
def drawnode(draw, clust, x, y, scaling, labels):
"""
画聚类节点以及子聚类节点
:param draw:
:param clust:
:param x:
:param y:
:param scaling:
:param labels:
:return:
"""
if clust.id<0:
h1=getheight(clust.left)*20
h2=getheight(clust.right)*20
top=y-(h1+h2)/2
bottom=y+(h1+h2)/2
# 线的长度
ll=clust.distance*scaling
# 聚类到其子节点的垂直线
draw.line((x, top+h1/2, x, bottom-h2/2), fill=(255,0,0))
# 连接左侧节点的水平线
draw.line((x, top+h1/2, x+ll, top+h1/2), fill=(255,0,0))
# 连接右侧节点的水平线
draw.line((x, bottom-h2/2, x+ll, bottom-h2/2), fill=(255,0,0))
# 调用函数绘制左右子节点
drawnode(draw, clust.left, x+ll, top+h1/2, scaling, labels)
drawnode(draw, clust.right, x+ll, bottom-h2/2, scaling, labels)
else:
# 如果这是一个叶节点，则绘制节点的标签文本
draw.text((x+5, y-7), labels[clust.id], (0, 0, 0))
def drawdendrogram(clusttree, labels, jpeg='clusters.jpg'):
"""
绘制树状图——为每一个最终生成的聚类创建一个高度为20像素，宽度固定的图片。其中缩放因子是由固定宽度除以总的深度得到的
:param clusttree:
:param labels:
:param jpeg:
:return:
"""
# 高度和宽度
h = getheight(clusttree) * 20
w = 1200
depth = getdepth(clusttree)
# 由于宽度是固定的，因此我们需要对距离值做相应的调整。（因为显示窗口宽度固定，高度可上下拖动）
scaling = float(w - 150) / depth
# 新建一个白色背景的图片
img = Image.new('RGB', (w, h), (255, 255, 255))
draw = ImageDraw.Draw(img)
draw.line((0, h / 2, 10, h / 2), fill=(255, 0, 0))
# 画根节点（会迭代调用画子节点）
drawnode(draw, clusttree, 10, (h / 2), scaling, labels)
img.save(jpeg, 'JPEG')
# 数据集转置，进行列聚类。
def rotatematrix(data):
newdata=[]
for i in range(len(data[0])):
newrow=[data[j][i] for j in range(len(data))]
newdata.append(newrow)
return newdata #一行表示一个单词在每篇博客中出现的次数
if __name__=='__main__':
blognames, words, data = readfile('blogdata.txt') #加载数据集
clust = hcluster(data) #构建层次聚类树
# printclust(clust,labels=blognames) # 打印聚类树
drawdendrogram(clust, blognames, jpeg='blogclust.jpg') # 绘制层次聚类树
rdata = rotatematrix(data) #旋转数据集矩阵，对特征属性进行聚类
wordclust = hcluster(rdata) #构建特征的聚类树
drawdendrogram(wordclust, labels=wo rds, jpeg='wordclust.jpg') # 绘制特征的层次聚类树参考博客：https://blog.csdn.net/luanpeng825485697/article/details/78993432