文章目录

简介
距离矩阵
最短距离法
最长距离法
类平均法
重心法
python应用

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。

简介

层次聚类（Hierarchical Clustreing）又称谱系聚类，通过在不同层次上对数据集进行划分，形成树形的聚类结构。很好体现类的层次关系，且不用预先制定聚类数，对大样本也有较好效果。

算法步骤：

计算类间距离矩阵
初始化n个类，将每个样本视为一类
在距离矩阵中选择最小的距离，合并这两个类为新类
计算新类到其他类的距离，得到新的距离矩阵
重复3-4步，直至最后合并为一个类

首先介绍距离矩阵的计算，然后第4步有不同的算法来定义新类到其他类的距离，包括：最短距离法、最长距离法、类平均法、重心法等。

距离矩阵

使用距离来作为样品间的相似性度量，往往常用欧氏距离。

比如给定数据：

x1	x2	x3
2	4	7
5	8	7
4	6	6

该数据包含特征x1、x2和x3，第一个样品[2,4,7]，第二个样品[5,8,7]，第三个样品[4,6,6]，将每个样品各看作一类， $G_i=\{i\},i=1,2,3,4$ 。
根据欧式距离：
$d(x_i,x_j)=[\sum^p_{k=1}(x_{ik}-x_{jk})^2]^{\frac{1}{2}}$

$D_{12}=D_{21}=\sqrt{(2-5)^2+(4-8)^2+(7-7)^2}=5$
$D_{13}=D_{31}=\sqrt{(2-4)^2+(4-6)^2+(7-6)^2}=3$
$D_{23}=D_{32}=\sqrt{(5-4)^2+(8-6)^2+(7-6)^2}=\sqrt{6}≈2.5$

也就是距离矩阵D为：

	$G_1$	$G_2$	$G_3$
$G_1$	0
$G_2$	5	0
$G_3$	3	2.5	0

由于是对称矩阵，给出下三角即可。

除了欧式距离，也可使用其他距离公式。或者使用相关系数来度量，越接近1表示越相关，计算相关系数矩阵。

最短距离法

设类 $G_r$ 由 $G_p,G_q$ 合并得来，包含 $n_r=n_p+n_q$ 个样品，最短距离法：
$D_{rk}=min\{D_{pd},D_{qk}\}$
在上述矩阵 $D$ 中， $D_{23}=2.5$ 最小，也就是合并 $G_2$ 和 $G_3$ 为新类 $G_4=\{2,3\}$

用最短距离法，计算新类到其他类距离：
$D_{41}=min\{D_{21},D_{3,1}\}=min\{5,3\}=3$

得到新的距离矩阵D’为：

	$G_1$	$G_4$
$G_1$	0
$G_4$	3	0

重复上述步骤，在D’中合并取 $D_{14}=3$ 最小，合并类 $G_1$ 和 $G_4$ 为新类，此时只有一个类，流程结束。

根据上述步骤绘制谱系图，横坐标就是每个类，纵坐标表示合并两个类时的值：
在这里插入图片描述
根据谱系图，如果要聚类为2类，从上往下看首次出现了2个分支的地方，即将样品0分为一类，样品1、2分为另一类。

最长距离法

设类 $G_r$ 由 $G_p,G_q$ 合并得来，包含 $n_r=n_p+n_q$ 个样品，最长距离法：
$D_{rk}=max\{D_{pd},D_{qk}\}$
在上述矩阵 $D$ 中， $D_{23}=2.5$ 最小，也就是合并 $G_2$ 和 $G_3$ 为新类 $G_4=\{2,3\}$

用最长距离法，计算新类到其他类距离：
$D_{41}=max\{D_{21},D_{3,1}\}=min\{5\}=5$

得到新的距离矩阵D’为：

	$G_1$	$G_4$
$G_1$	0
$G_4$	5	0

重复上述步骤，在D’中合并取 $D_{14}=5$ 最小，合并类 $G_1$ 和 $G_4$ 为新类，此时只有一个类，流程结束。

得到谱系图如下：
在这里插入图片描述

类平均法

设类 $G_r$ 由 $G_p,G_q$ 合并得来，包含 $n_r=n_p+n_q$ 个样品，类平均法：
$D_{rk}=\frac{n_p}{n_r}D_{pk}+\frac{n_q}{n_r}D_{qk}$
在上述矩阵 $D$ 中， $D_{23}=2.5$ 最小，也就是合并 $G_2$ 和 $G_3$ 为新类 $G_4=\{2,3\}$

用类平均法，计算新类到其他类距离：
$D_{41}=\frac{1}{2}×5+\frac{1}{2}×3=4$

得到新的距离矩阵D’为：

	$G_1$	$G_4$
$G_1$	0
$G_4$	4	0

重复上述步骤，在D’中合并取 $D_{14}=4$ 最小，合并类 $G_1$ 和 $G_4$ 为新类，此时只有一个类，流程结束。

得到谱系图如下：
在这里插入图片描述

（~~插播反爬信息~~ ）博主CSDN地址：https://wzlodq.blog.csdn.net/

重心法

设类 $G_r$ 由 $G_p,G_q$ 合并得来，包含 $n_r=n_p+n_q$ 个样品，重心法：
$D_{rk}=[\frac{n_p}{n_r}D_{pk}^2+\frac{n_q}{n_r}D_{qk}^2-\frac{n_p}{n_r}\frac{n_q}{n_r}D_{pq}^2]^{\frac{1}{2}}$
在上述矩阵 $D$ 中， $D_{23}=2.5$ 最小，也就是合并 $G_2$ 和 $G_3$ 为新类 $G_4=\{2,3\}$

用重心法，计算新类到其他类距离：
$D_{41}=[\frac{1}{2}5^2+\frac{1}{2}3^2-\frac{1}{2}\frac{1}{2}\sqrt{6}^2]^{\frac{1}{2}}=\sqrt{15.5}≈3.9$

得到新的距离矩阵D’为：

	$G_1$	$G_4$
$G_1$	0
$G_4$	3.9	0

重复上述步骤，在D’中合并取 $D_{14}=3.9$ 最小，合并类 $G_1$ 和 $G_4$ 为新类，此时只有一个类，流程结束。

得到谱系图如下：

在这里插入图片描述

python应用

使用scipy库中的linkage函数
linkage(y, method=‘single’, metric=‘euclidean’)
method取值single表示最短距离法、complete最长距离法、average类平均法、centroid重心法。

import pandas as pd
from matplotlib import pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkagedata = [[76.1, 74.33, 78.01],[74.91, 73.31, 76.63],[72.54, 70.68, 74.57],[71.65, 69.96, 73.57],[69.87, 68.29, 71.79],[73.34, 71.51, 75.36],[73.1, 71.38, 75.04],[72.37, 70.39, 74.66]]
data = pd.DataFrame(data, columns=['X1', 'X2', 'X3'],index=['北京', '天津', '河北', '山西', '内蒙古', '辽宁', '吉林', '黑龙江'])
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.figure(figsize=(6, 5))
#  用最短距离法
plt.subplot(2, 2, 1)
plt.tight_layout(pad=2.5)
plt.title('最短距离法')
z1 = linkage(data, 'single')
dendrogram(z1)#  用最长距离法
plt.subplot(2, 2, 2)
plt.title('最长距离法')
z2 = linkage(data, 'complete')
dendrogram(z2)#  用类平均法
plt.subplot(2, 2, 3)
plt.title('类平均法')
z3 = linkage(data, 'average')
dendrogram(z3)#  用重心法
plt.subplot(2, 2, 4)
plt.title('重心法')
z4 = linkage(data, 'centroid')
dendrogram(z4)
plt.show()

在这里插入图片描述

使用sklearn库中的AgglomerativeClustering函数
使用linkage参数定义合并算法。

import numpy as np
import pandas as pd
from matplotlib import pyplot as plt
from scipy.cluster.hierarchy import dendrogram
from sklearn.cluster import AgglomerativeClusteringdef plot_dendrogram(model, **kwargs):  # 可视化counts = np.zeros(model.children_.shape[0])n_samples = len(model.labels_)for i, merge in enumerate(model.children_):current_count = 0for child_idx in merge:if child_idx < n_samples:current_count += 1else:current_count += counts[child_idx - n_samples]counts[i] = current_countlinkage_matrix = np.column_stack([model.children_, model.distances_, counts]).astype(float)dendrogram(linkage_matrix, **kwargs)data = [[76.1, 74.33, 78.01],[74.91, 73.31, 76.63],[72.54, 70.68, 74.57],[71.65, 69.96, 73.57],[69.87, 68.29, 71.79],[73.34, 71.51, 75.36],[73.1, 71.38, 75.04],[72.37, 70.39, 74.66]]
data = pd.DataFrame(data, columns=['X1', 'X2', 'X3'],index=['北京', '天津', '河北', '山西', '内蒙古', '辽宁', '吉林', '黑龙江'])plt.rcParams['font.sans-serif'] = ['SimHei']
plt.figure(figsize=(6, 5))
#  用最短距离法
plt.subplot(2, 2, 1)
plt.tight_layout(pad=2.5)
plt.title('最短距离法')
model1 = AgglomerativeClustering(linkage='single', distance_threshold=0, n_clusters=None)
model1.fit(data)
plot_dendrogram(model1)
print("标签：", model1.labels_)
print("合并节点：", model1.children_)#  用最长距离法
plt.subplot(2, 2, 2)
plt.title('最长距离法')
model2 = AgglomerativeClustering(linkage='complete', distance_threshold=0, n_clusters=None)
model2.fit(data)
plot_dendrogram(model2)#  用类平均法
plt.subplot(2, 2, 3)
plt.title('类平均法')
model3 = AgglomerativeClustering(linkage='average', distance_threshold=0, n_clusters=None)
model3.fit(data)
plot_dendrogram(model3)#  用重心法
plt.subplot(2, 2, 4)
plt.title('重心法')
model4 = AgglomerativeClustering(linkage='ward', distance_threshold=0, n_clusters=None)
model4.fit(data)
plot_dendrogram(model4)
plt.show()