机器学习——层次聚类

层次聚类（Hierarchical Clustering）是一类算法的总称，分为两种方式：凝聚法：从下往上不断合并簇，将小类进行聚合分裂法：从上往下不断分离簇，将大类分割成小类。

小老弟来喽

3126人浏览 · 2023-08-02 12:03:05

小老弟来喽 · 2023-08-02 12:03:05 发布

1.1 过程和原理

1.1.1 层次聚类介绍

层次聚类（Hierarchical Clustering）是一类算法的总称，分为两种方式：

凝聚法：从下往上不断合并簇，将小类进行聚合

分裂法：从上往下不断分离簇，将大类分割成小类

1.1.2 AgglomerativeClustering 算法

原理：开始时将所有数据点本身作为簇，然后找出距离最近的两个簇将他们合并为一个，不断重复，直到达到预设的簇的个数

4个步骤实现聚类分析法分析用户 - 知乎

具体步骤如下：

第 1 步：将每个样本点当作一个类簇，原始类簇大小等于样本点的个数

第 2 步：计算各簇之间的距离，然后合并距离最近的两个簇

第 3 步：重复第 2 步，直到达到某种条件或者达到设定的聚类数目

原理很简单，关键点在于计算簇间距离后合并相临近的簇

常用的三种距离度量方式：

$\bullet$ 最小距离：由两个簇的最近样本决定

$\bullet$ 最大距离：由两个簇的最远样本决定

$\bullet$ 平均距离：由两个簇的所有样本共同决定，即各类簇中心之间的距离

以下图所示为例，假设现在所有样本已经被划分为了三类，而我们的目标是将所有样本聚为两类，所以还需再进行一次合并

（1）按照最小距离，则应该是蓝色和绿色两类进行合并

（2）按照平均距离，则应该是蓝色和红色两类进行合并，因为红色和蓝色两类的簇中心距离更近

实际上，这些聚类方式各有利弊

若采用最小距离或最大距离，则聚类结果可能受噪声点的影响较大，但计算量小

若采用平均距离，则抗噪能力较强，但计算量会大大增加

1.1.3 DivisiveClustering算法

原理与 AgglomerativeClustering 算法相反：先将所有数据样本当作一整个簇，然后找出簇中距离最远的两个簇进行分裂，不断重复到预期或者其他终止条件

具体步骤如下：

第 1 步：将所有样本点归为一个簇

第 2 步：在同一个簇中，计算任意两个样本之间的距离，找到距离最远的两个样本点 $a$ 和 $b$ ，将 $a,b$ 作为两个聚类中心

第 3 步：计算原来簇中剩余样本点距离 $a,b$ 的距离，并将各样本点归入离其最近的一个聚类中心

第 4 步：重复第 2 步和第 3 步，直到达到某种条件或者达到设定的聚类数目

1.2 优点和缺点

1.2.1 优点

（1）能够展现数据层次结构，易于理解

（2）可以先基于层次，然后再选择类的个数（先将样本点凝聚成一棵树，然后聚类的时候从根节点出发选择；比如需要聚成K类，那么选择子节点个数为K的那一层即可）

（3）可以聚类成其他形状

1.2.2 缺点

（1）计算量较大（需要计算所有样本点相互之间的距离），不适合样本量大的情况

（2）奇异值也能产生很大影响

（3）算法很可能聚类成链状

1.3 层次聚类应用实例

1.3.1 scikit-learn 实现

AgglomerativeClustering 算法的 scikit-learn 实现：

from sklearn.cluster import AgglomerativeClustering
agnes = AgglomerativeClustering(n_clusters=2,
                                affinity='euclidean',
                                compute_full_tree='auto',
                                linkage='ward'，
                                distance_threshold=None)

参数

$\bullet$ n_clusters：指定聚类簇的数量

$\bullet$ affinity：选择用于计算距离的方式，可选项：euclidean(欧几里得距离)、11、12、mantattan(曼哈顿距离)、cosine(余弦距离)和precomputed

如果设置为None，则为默认euclidean

如果linkage是‘ward’，则只有euclidean

如果是‘precomputed’，则需提供一个距离矩阵

$\bullet$ linkage：选择用于度量距离的方式，选项如下

ward：采用最小距离 dmin，也是默认选项

complete：采用最大距离 dmax

average：采用平均距离 davg

$\bullet$ compute_full_tree：默认情况是 auto

如果distance_threshold 不是None，那么compute_full_tree是True

如果n_clusters比max(100,0.02*n_samples)小，那么compute_full_tree是True

其他情况下，compute_full_tree是False

$\bullet$ distance_threshold：如果两个簇之间的距离大于这个值时，cluster不再合并；如果distance_threshold不是None，那么n_cluster必须是None，compute_full_tree必须是True

属性

$\bullet$ n_clusters_：簇的数量（若distance_threshold是None，则等于给定的n_clusters）

$\bullet$ labels：每个样本的簇标记

$\bullet$ n_leaves_：分层树的叶子节点数量

$\bullet$ children_：每个非叶子节点包含的子节点数量

方法

$\bullet$ fit(X)：在X上执行数据集，可以配和labels属性使用

$\bullet$ fit(X)：在X上执行数据集并返回样本X的簇标记

1.3.2 应用实例

程序如下：

import numpy as np
import matplotlib.pyplot as plt
import mpl_toolkits.mplot3d as Axes3D
from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets._samples_generator import make_swiss_roll


#生成样本点
X, y = make_swiss_roll(n_samples=1500,noise=0.05)
X[:, 1] *= .5
print(X)
print(y)

#训练
agnes = AgglomerativeClustering(n_clusters=3,linkage='ward').fit(X)
y_pred = agnes.fit_predict(X)
label = agnes.labels_
print("簇的数量",agnes.n_clusters_)
print("每个样本的簇标记：",agnes.labels_)
print("分层树的叶子节点数量：",agnes.n_leaves_)
print("每个非叶子节点包含的子节点的数量",agnes.children_)

#可视化结果
fig = plt.figure()
ax = plt.axes(projection='3d')
ax.view_init(7,-80)
for v in np.unique(label):
    ax.scatter(X[label==v,0],X[label==v,1],X[label==v,2],
               color=plt.cm.jet(np.float64(v)/np.max(label+1)),s=20,edgecolor='k')
plt.show()

结果：