聚类（Cluster Analysis or Clustering）是一种无监督的机器学习算法，可根据相似性或距离将不同的对象、数据点或观察结果组织和分类为不同的簇（Cluster）或类。聚类的目的是通过得到的类或簇来发现数据的特点或对数据进行处理。

聚类的相关概念

相似度或距离

聚类的核心概念是相似度或距离，有多种相似度或距离的定义。

闵可夫斯基距离

给定样本集合 XX，XX 是 mm 维实数向量空间 RmR^m 中点的集合，其中 xi,xj∈Xx_i, x_j \in X，xi=(x1i,x2i,⋯ ,xmi)Tx_i = (x_{1i}, x_{2i}, \cdots, x_{mi})^T，xj=(x1j,x2j,⋯ ,xmj)Tx_j = (x_{1j}, x_{2j}, \cdots, x_{mj})^T，样本 xix_i 与样本 xjx_j 的闵可夫斯基距离（Minkowski Distance）定义为

dij=(∑k=1m∣xki−xkj∣p)1p\begin{align} d_{ij} = \left( \sum_{k=1}^m |x_{ki} - x_{kj}|^p \right)^{\frac{1}{p}} \end{align}

这里 p≥1p \geq 1。当 p=2p = 2 时称为欧氏距离（Euclidean Distance），即

dij=(∑k=1m∣xki−xkj∣2)12d_{ij} = \left( \sum_{k=1}^m |x_{ki} - x_{kj}|^2 \right)^{\frac{1}{2}}

当 p=1p = 1 时称为曼哈顿距离（Manhattan Distance），即

dij=∑k=1m∣xki−xkj∣d_{ij} = \sum_{k=1}^m |x_{ki} - x_{kj}|

当 p=∞p = \infty 时称为切比雪夫距离（Chebyshev Distance），取各个坐标数值差的绝对值的最大值，即

dij=max⁡k∣xki−xkj∣d_{ij} = \max_k |x_{ki} - x_{kj}|

马哈拉诺比斯距离

马哈拉诺比斯距离（Mahalanobis Distance）简称马氏距离，也是另一种常用的相似度，考虑各个分量（特征）之间的相关性并与各个分量的尺度无关。马哈拉诺比斯距离越大，相似度越小；距离越小，相似度越大。
给定一个样本集合 XX，X=[xij]m×nX = [x_{ij}]_{m \times n}，其协方差矩阵记作 SS。样本 xix_i 与样本 xjx_j 之间的马哈拉诺比斯距离 dijd_{ij} 定义为

dij=[(xi−xj)TS−1(xi−xj)]12\begin{align} d_{ij} = \left[ (x_i - x_j)^T S^{-1} (x_i - x_j) \right]^{\frac{1}{2}} \end{align}

其中，xi=(x11,x21,⋯ ,xm1)T,xj=(x1j,x2j,⋯ ,xmj)Tx_i = (x_{11}, x_{21}, \cdots, x_{m1})^T, \quad x_j = (x_{1j}, x_{2j}, \cdots, x_{mj})^T。
马氏距离是欧式距离的推广。

相关系数

样本之间的相似度也可以用相关系数（Correlation Coefficient）来表示。相关系数的绝对值越接近 1，表示样本越相似；越接近 0，表示样本越不相似。
样本 xix_i 与样本 xjx_j 之间的相关系数定义为

rij=∑k=1m(xki−xˉi)(xkj−xˉj)[∑k=1m(xki−xˉi)2∑k=1m(xkj−xˉj)2]12\begin{align} r_{ij} = \frac{\sum_{k=1}^{m}(x_{ki} - \bar{x}_i)(x_{kj} - \bar{x}_j)}{\left[\sum_{k=1}^{m}(x_{ki} - \bar{x}_i)^2\sum_{k=1}^{m}(x_{kj} - \bar{x}_j)^2\right]^{\frac{1}{2}}} \end{align}

其中，xˉi=1m∑k=1mxki,xˉj=1m∑k=1mxkj\bar{x}_i = \frac{1}{m}\sum_{k=1}^{m}x_{ki}, \quad \bar{x}_j = \frac{1}{m}\sum_{k=1}^{m}x_{kj}。

夹角余弦

样本之间的相似度也可以用夹角余弦来表示。夹角余弦越接近 1，表示样本越相似；越接近 0，表示样本越不相似。
样本 xix_i 与样本 xjx_j 之间的夹角余弦定义为

sij=∑k=1mxkixkj(∑k=1mxki2∑k=1mxkj2)12\begin{align} s_{ij} = \frac{\sum_{k=1}^{m}x_{ki}x_{kj}}{\left(\sum_{k=1}^{m}x_{ki}^2\sum_{k=1}^{m}x_{kj}^2\right)^{\frac{1}{2}}} \end{align}

类或簇

通过聚类得到的类或族本质是样本的子集。如果一个聚类方法假定一个样本只能属于一个类或类的交集为空集，那么该方法称为硬聚类方法。否则，如果一个样本可以属于多个类或类的交集不为空集，那么该方法称为软聚类方法。本章只考虑硬聚类方法。
用 GG 表示类或族，用 xi,xjx_i, x_j 表示类中的样本，用 nGn_G 表示 GG 中样本的个数，用 dijd_{ij} 表示样本 xix_i 与样本 xjx_j 之间的距离。类或族有多种定义，下面给出几个常见的定义。
设 TT 为给定的正数，若对于集合 GG 中任意两个样本 xi,xjx_i, x_j，有

dij≤T\begin{align} d_{ij} \leq T \end{align}

则称 GG 为一个类或族。
类的特征可以通过不同角度来刻画，常用的特征有下面三种：
(1) 类的均值 xˉG\bar{x}_G
类的均值 xˉG\bar{x}_G 定义为：

xˉG=1nG∑i=1nGxi\begin{align} \bar{x}_G = \frac{1}{n_G} \sum_{i=1}^{n_G} x_i \end{align}

式中 nGn_G 是类 GG 的样本个数。
(2) 类的直径 DGD_G
类的直径 DGD_G 是类中任意两个样本之间的最大距离，即：

DG=max⁡xi,xj∈Gdij\begin{align} D_G = \max_{x_i, x_j \in G} d_{ij} \end{align}

(3) 类的样本散布矩阵 AGA_G 与样本协方差矩阵 SGS_G
类的样本散布矩阵 AGA_G 定义为：

AG=∑i=1nG(xi−xˉG)(xi−xˉG)T\begin{align} A_G = \sum_{i=1}^{n_G} (x_i - \bar{x}_G)(x_i - \bar{x}_G)^T \end{align}

样本协方差矩阵 SGS_G 定义为：

SG=1nG−1AG=1nG−1∑i=1nG(xi−xˉG)(xi−xˉG)T\begin{align} S_G = \frac{1}{n_G - 1} A_G = \frac{1}{n_G - 1} \sum_{i=1}^{n_G} (x_i - \bar{x}_G)(x_i - \bar{x}_G)^T \end{align}

类与类之间的距离

下面考虑类 GpG_p 与类 GqG_q 之间的距离 D(p,q)D(p, q)，也称为连接（Linkage）。类与类之间的距离也有多种定义。
设类 GpG_p 包含 npn_p 个样本，GqG_q 包含 nqn_q 个样本，分别用 xˉp\bar{x}_p 和 xˉq\bar{x}_q 表示 GpG_p 和 GqG_q 的均值（即类的中心）。
(1) 最短距离或单连接（Single Linkage）
定义类 GpG_p 的样本与类 GqG_q 的样本之间的最短距离为两类之间的距离：

Dpq=min⁡{dij∣xi∈Gp,xj∈Gq}\begin{align} D_{pq} = \min \{ d_{ij} \mid x_i \in G_p, x_j \in G_q \} \end{align}

(2) 最长距离或完全连接（Complete Linkage）
定义类 GpG_p 的样本与类 GqG_q 的样本之间的最长距离为两类之间的距离：

Dpq=max⁡{dij∣xi∈Gp,xj∈Gq}\begin{align} D_{pq} = \max \{ d_{ij} \mid x_i \in G_p, x_j \in G_q \} \end{align}

(3) 中心距离
定义类 GpG_p 与类 GqG_q 的中心 xˉp\bar{x}_p 与 xˉq\bar{x}_q 之间的距离为两类之间的距离：

Dpq=dxˉpxˉq\begin{align} D_{pq} = d_{\bar{x}_p \bar{x}_q} \end{align}

这种连接在代码里面体现在合并簇时采用取平均的方式。
(4) 平均距离
定义类 GpG_p 与类 GqG_q 任意两个样本之间距离的平均值为两类之间的距离：

Dpq=1npnq∑xi∈Gp∑xj∈Gqdij\begin{align} D_{pq} = \frac{1}{n_p n_q} \sum_{x_i \in G_p} \sum_{x_j \in G_q} d_{ij} \end{align}

层次聚类

层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。层次聚类有：

  • 聚合式或自下而上的方法，这种方法反复将聚类合并成更大的聚类，直到形成一个单个聚类；
  • 分割式或自上而下的方法，这种方法从单个聚类中的所有数据开始，然后继续拆分连续的聚类，直到所有的聚类都是单一聚类。
\begin{algorithm}
\caption{层次聚类}
\begin{algorithmic}
\REQUIRE 样本集合 $X = \{ x_1, x_2, \cdots, x_n \}$，其中 $x_i \in \mathbb{R}^m$；样本间距离度量
\ENSURE 样本集合的层次化聚类结构

\STATE 计算所有样本两两之间的欧氏距离：$d_{ij} = \| x_i - x_j \|_2$，构建距离矩阵 $D = [d_{ij}]_{n \times n}$

\STATE 创建 $n$ 个初始类：$C_i = \{x_i\}, \quad i = 1, 2, \cdots, n$

\WHILE{类的个数 > 1}
    \STATE 找到距离最小的两个类：$(C_p, C_q) = \arg\min_{i < j} d(C_i, C_j)$
    \STATE 合并这两个类，形成新类：$C_{\text{new}} = C_p \cup C_q$
    \STATE 从当前类集合中移除 $C_p$ 和 $C_q$，加入 $C_{\text{new}}$
    \STATE 更新距离矩阵：计算 $C_{\text{new}}$ 与其余各类的距离（使用最短距离/单链法）
\ENDWHILE

\STATE \textbf{返回} 样本集合的层次化聚类
\end{algorithmic}
\end{algorithm}

层次聚类|利用水平线切割树枝图，以确定聚类数量

聚类方法实战#1：2022高教社杯全国大学生数学建模竞赛C题 古代玻璃制品的成分分析与鉴别

针对问题2：依据附件数据分析高钾玻璃、铅钡玻璃的分类规律；对于每个类别选择合适的化学成分对其进行亚类划分，给出具体的划分方法及划分结果，并对分类结果的合理性和敏感性进行分析。此题选用层次聚类方法进行亚类划分是合理的，因其天然具备的层次结构能满足亚类划分的需求。
使用scipy框架对数据进行层次聚类，结果如下图所示。其代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.preprocessing import StandardScaler
from scipy.cluster.hierarchy import dendrogram, linkage
plt.rcParams['font.sans-serif'] = ['FangSong']

# 读取Excel文件
file_path = 'C:\\...\\附件.xlsx'
sheet2 = pd.read_excel(file_path, sheet_name='表单2', header=0)

# 数据预处理
data = sheet2.set_index(sheet2.columns[0])
data = data.fillna(0)

# 数据标准化
scaler = StandardScaler()
scaled_data = scaler.fit_transform(data)

# 计算距离矩阵(此处使用最长距离或完全连接)
Z = linkage(scaled_data, method='complete')

# 绘制树状图
plt.figure(figsize=(16, 10))
dendrogram(Z, labels=data.index.tolist(),
           orientation='top', 
           leaf_rotation=90,
           leaf_font_size=10,
           color_threshold=25)
plt.title('亚类划分层次聚类树状图')
plt.xlabel('样本')
plt.ylabel('距离')
plt.tight_layout()
plt.show()

其中ZZ矩阵的定义如下：
返回一个 (n−1)×4(n - 1) \times 4 的矩阵 Z\mathbf{Z}。在第 ii 次迭代中，索引为 Z[i,0]\mathbf{Z}[i, 0] 和 Z[i,1]\mathbf{Z}[i, 1] 的聚类被合并，形成新聚类 n+in + i。 若聚类索引小于 nn，则对应 nn 个原始观测点中的一个。 聚类 Z[i,0]\mathbf{Z}[i, 0] 与 Z[i,1]\mathbf{Z}[i, 1] 之间的距离为 Z[i,2]\mathbf{Z}[i, 2]， 第四项 Z[i,3]\mathbf{Z}[i, 3] 表示新聚类中包含的原始观测点数量。
也就是

聚类n+i聚类j聚类k两个类的距离聚类n+i中包含的原始观测点数量聚类n+i \quad \boxed{聚类j \quad 聚类k \quad 两个类的距离 \quad 聚类n+i中包含的原始观测点数量}

得出来的结果如下：
国赛2022C-问题2层次聚类求解

k均值聚类

kk均值（kk-means）聚类是一种基于中心点的迭代式聚类算法，该算法通过计算聚类中心之间的距离，将数据集划分为若干相似组。聚类中心（即簇中心点）的计算方式可根据数据特性选择：既可采用簇内所有数据点的均值，亦可采用其中位数。kk均值聚类的模型是一个从样本到类的函数。

\begin{algorithm}
\caption{$k$-means Clustering}
\begin{algorithmic}
\REQUIRE 集合 $\boldsymbol{X}$，包含 $n$ 个样本
\ENSURE 聚类结果 $C^*$

\STATE 初始化：设迭代次数 $t = 0$，随机选择 $k$ 个样本作为初始类中心 $m^{(0)} = \left( m_1^{(0)}, m_2^{(0)}, \cdots, m_k^{(0)} \right)$

\REPEAT
    \STATE \textbf{样本聚类}：对当前中心 $m^{(t)} = \left( m_1^{(t)}, \cdots, m_k^{(t)} \right)$，其中 $m_l^{(t)}$ 为类 $G_l$ 的中心。计算每个样本到各类中心的距离，将样本分配到最近的类，形成聚类结果 $C^{(t)} = \{ G_1, \cdots, G_k \}$。
    
    \STATE \textbf{更新类中心}：对聚类结果 $C^{(t)}$，计算各类中样本的均值，作为新的类中心$m^{(t+1)} = \left( m_1^{(t+1)}, m_2^{(t+1)}, \cdots, m_k^{(t+1)} \right)$
    
    \STATE $t \gets t + 1$

\UNTIL{满足收敛条件或停止准则}

\STATE \textbf{输出}：$C^* = C^{(t)}$

\end{algorithmic}
\end{algorithm}

基于纽约市爱彼迎租房数据的均值聚类算法

类别数kk的选择

kk均值聚类中的类别数kk值需要预先指定，而在实际应用中最优的kk值是不知道的。找到最佳kk值的方法之一是肘部法(Elbow Method)。其原理是计算各数据点与其聚类中心的欧氏距离，并通过观察簇内平方和（Within Cluster Sum of Squares,WCSS）的变化拐点确定聚类数。具体而言：将WCSS值聚类数量绘制曲线，选择方差变化趋于平缓的转折点作为最优解。
类别数与簇内平方和之间的关系

聚类方法实战#2：爱荷华州埃姆斯市房屋的聚类分析

网址：Clustering With K-Means Exercise: Clustering With K-Means|Kaggle Notebook Editor
数据集名称：AmesHousing.txt
类型：总体数据集
规模：2930条观测记录，82个变量
文献标题：艾奥瓦州埃姆斯市：波士顿房价数据集的替代方案
描述性摘要：
本数据集包含埃姆斯市评估办公室提供的房产信息，用于计算2006至2010年间艾奥瓦州埃姆斯市单户住宅物业的评估价值。