聚类

数据分簇

聚类算法(Clustering)是一种常见的无监督学习算法。在本系列的第一篇日志中提到，无监督学习算法就是不给定训练数据的标签。监督学习中的训练样本通常被描述为 $(\boldsymbol{x}^{(i)},y^{(i)})$ ，而无监督学习的样本只保留特征量 $\boldsymbol{x}^{(i)}$ 。

聚类算法可以通常描述为：算法会将数据点划分为多个互不相交的簇(Cluster)，使得同一簇内的数据点相似度高，而不同簇间的数据点相似度低。其核心在于寻找数据对象的相似性。

聚类得到的簇可以用聚类中心、簇大小、簇密度和簇描述等来表示

聚类中心是一个簇中所有样本点的均值
簇大小表示簇中所含样本的数量
簇密度表示簇中样本点的紧密程度
簇描述是簇中样本的业务特征

K-means算法

$K$ 平均算法(K-means)是一种常用的聚类算法，其中 $K$ 代表聚类得到的簇的个数。 $K$ 平均算法主要通过构造不断迭代的聚类中心，实现聚类的效果。设样本特征空间的维度为 $\mathbb{R}^n$ ，算法的具体流程如下

随机选取 $K$ 个聚类中心 $\mu_1,\mu_2,\cdots,\mu_K\in\mathbb{R}^n$
对于所有的数据 $\boldsymbol{x}^{(1)},\boldsymbol{x}^{(2)},\cdots,\boldsymbol{x}^{(m)}$ ，设 $c^{(i)}$ 表示距离 $\boldsymbol{x}^{(i)}$ 最近的聚类中心的下标索引，并把该数据纳入该聚类中心代表的簇

$c^{(i)}=\arg\min_{1\leqslant k\leqslant K}\|\boldsymbol{x}^{(i)}-\mu_k\|^2$

对于每一个簇，令新的聚类中心为所有内部数据的平均值，即

$\mu_k:=\text{mean of } \boldsymbol{x}^{(i)}\text{ in cluster k},\quad k=1,2\cdots,K$

不断重复过程 (2,3)，直到满足聚类要求

过程(2)中的 $\arg\min$ 表示取得最小值对应的自变量值。需要指出的是，聚类的簇个数 $K$ 一般需要小于样本数量 $m$ ，否则无法有效起到聚类效果。

可以看出， $K$ 平均算法是一种相当简单的聚类算法，并且有多种优化方式。一种方式是类比监督学习算法中的代价函数，定义目标优化函数

$J(c^{(1)},c^{(2)},\cdots,c^{(m)},\mu_1,\mu_2,\cdots,m_K)=\frac1m\sum_{i=1}^m\|\boldsymbol{x}^{(i)}-\mu_{c^{(i)}}\|^2$

可以看出，上式描述了所有数据点到其聚类中心的密集度。函数值越大，代表数据点越分散；函数值越小，代表数据点越密集，因此我们有最小化优化目标

$\min J(c^{(1)},c^{(2)},\cdots,c^{(m)},\mu_1,\mu_2,\cdots,m_K)$

当优化函数趋于收敛时，聚类算法就可以终止。

注意到， $K$ 平均算法对于不同的初值条件可能得到不同的聚类结果，同时也容易导致局部最优化。因此需要选取合适的方式进行随机初始化，多次随机的选取聚类中心，并选取使得目标优化函数 $J$ 最小的那种情况。

[{"url":"/img/mlearning/m8f1.png","alt":"局部最优化","title":""}]

最后，我们来看如何选取合适的 $K$ 值。一般而言，随着簇数量 $K$ 的增加，目标函数 $J$ 的最小值会下降。具体可以描述为

当 $K$ 小于某一值时，增加 $K$ 会大幅降低 $\min J$
当 $K$ 超过这个值时，增加 $K$ 时 $\min J$ 降低的幅度大大减小

上述现象通常被描述为肘部法则(Elbow Method)，下图直观地展示了这一法则。当我们选取这个肘部点对应的 $K$ 值时，通常是一个兼顾正确性和效率的优秀选择。

[{"url":"/img/mlearning/m8f2.png","alt":"肘部法则","title":""}]

代码实现

随机创建一些有聚类趋势的数据，使用 Python 实现 $K$ 平均算法聚类算法。

# 导入必要的库
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

# 绘图设置
plt.rcParams['font.sans-serif'] = ['SimHei', 'Microsoft YaHei',]
plt.rcParams['axes.unicode_minus'] = False

# 1. 创建一个人工数据集
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# 2. 可视化原始数据
plt.scatter(X[:, 0], X[:, 1], s=50) # s 是点的大小
plt.title("原始未标记数据")
plt.show()

# 3. 应用 K-Means 聚类
kmeans = KMeans(n_clusters=4, random_state=0, n_init='auto')
y_kmeans = kmeans.fit_predict(X)

# 4. 获取质心坐标
centroids = kmeans.cluster_centers_

# 5. 可视化聚类结果
plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')
plt.scatter(centroids[:, 0], centroids[:, 1], c='red', s=200, alpha=0.8, marker='X')
plt.title("K-Means 聚类结果 (K=4)")
plt.show()
print("四个簇的质心坐标:\n", centroids)

主成分分析PCA

数据降维

降维(Dimensionality Reduction)就是一种对高维度特征数据预处理方法。降维将高维度的数据保留下最重要的一些特征，去除噪声和不重要的特征，从而实现提升数据处理速度的目的。

在实际的生产和应用中，降维在一定的信息损失范围内，可以为我们节省大量的时间和成本。例如，图像压缩就是一种数据降维的应用，可以保证图像基本清晰的同时大幅减少内存占用。

数据降维通常有以下优点

使得数据集更易使用
降低算法的计算开销
去除噪声
使得结果容易理解

PCA的概念

PCA(Principal Component Analysis)，即主成分分析方法，是一种使用最广泛的数据降维算法。PCA的主要思想是将 $n$ 维特征映射到 $k$ 维上，这 $k$ 维是全新的正交特征，也称作主成分。

PCA算法通常可以由特征值分解或奇异值分解(SVD)实现。但是在介绍其数学原理之前，我们先用低维度的例子进行说明。

对于两个特征 $x_1,x_2$ ，现在想要把其降维变成一个特征。首先需要进行均值归一化，即设 $m$ 个样本的均值为

$\mu=\frac1m\sum_{i=1}^m\boldsymbol{x}^{(i)}$

此时，把每个样本减去均值 $\mu$ ，就可以保证新样本的均值为 $\boldsymbol{0}$ 。接下来，尝试寻找一条过原点的有向直线 $L$ ，其方向向量为 $\boldsymbol{u}$ ，并把每个样本投影到该直线上，得到直线上的一个点 $P_i$ 和其在该直线上的坐标 $p_i$ 。

如何寻找一条合适的直线进行投影呢？PCA要求最小化投影方向的误差，也就是使得每个数据到直线 $L$ 的投影误差尽可能的小，这一点我们将在数学原理部分进一步说明。

注意，线性回归和PCA是两个不同的模型

线性回归中包含样本标签，误差表示为垂直距离
PCA只对数据特征进行处理，误差表示为投影误差

[{"url":"/img/mlearning/m8f3.png","alt":"线性回归和PCA的区别","title":""}]

对于 $n$ 维的PCA算法，对数据进行均值归一化处理后，我们需要寻找一个 $k$ 维超平面，使得新数据投影到该超平面的投影误差最小，并且投影后的新样本最为降维处理的结果。

特征值分解

对于一个 $n$ 阶实对称矩阵 $\boldsymbol{A}$ ，可以对其进行特征值分解

$\boldsymbol{A}=\boldsymbol{Q}\boldsymbol{\Lambda}\boldsymbol{Q}^T$

其中， $n$ 阶矩阵 $\boldsymbol{Q},\boldsymbol{\Lambda}$ 可以如下求得

$\boldsymbol{\Lambda}$ ：对角矩阵 $\mathrm{diag(\lambda_1,\lambda_2,\cdots,\lambda_n)}$ ，其中 $\lambda_i$ 为 $\boldsymbol{A}$ 的特征值，并且规定 $\lambda_1\geqslant\lambda_2\geqslant\cdots\geqslant\lambda_n\geqslant0$
$\boldsymbol{Q}$ ：正交矩阵 $[\boldsymbol{x}_1,\boldsymbol{x}_2,,\cdots\boldsymbol{x}_n]$ ，其中 $\boldsymbol{x}_i$ 为 $\boldsymbol{A}$ 的特征值 $\lambda_i$ 对应的单位特征向量，且 $\boldsymbol{x}_i$ 相互正交

一个高维矩阵本质上就是高维空间中的一个线性变换，该矩阵的各特征值反映该矩阵各个方向变换的程度，我们取从大到小特征值中的前 $k$ 个特征值，也就是提取了该矩阵变化程度最大的 $k$ 个方向，其它方向进行舍弃，也就提取了该矩阵中最重要的 $k$ 个特征，以此来近似原矩阵的线性变换。这就是基于特征值分解的降维原理。

因此，我们需要找到一个基于样本特征量构造的矩阵 $S$ ，使得 $S$ 的特征值分解能够体现不同特征量的重要性，从而实现PCA降维。

对于两个随机变量 $X,Y$ ，其协方差(Covariance)定义为

$\text{Cov}=\frac{1}{m-1}\sum_{i=1}^{m-1}(x_i-\bar{x})(y_i-\bar{y})$

其中 $m$ 为样本量， $x_i,y_i$ 是特征 $X,Y$ 的第 $i$ 个样本值， $\bar{x},\bar{y}$ 是特征 $X,Y$ 的样本均值。协方差刻画了两组特征的样本值的协同变化趋势，其绝对值越大，两个变量的相关性越强。

对于 $n$ 个经过均值归一化的特征变量 $X_1,X_2,\cdots,X_n$ ，其协方差矩阵定义为

$\boldsymbol{S}=(s_{ij})_{n\times n},\quad s_{ij}=\text{Cov}(X_i,X_j)$

由于 $\text{Cov}(X_i,X_j)=\text{Cov}(X_j,X_i)\in\mathbb{R}$ ，所以 $\boldsymbol{S}$ 是一个实对称矩阵，因此可以进行特征值分解。

$\boldsymbol{S}=\boldsymbol{Q}\boldsymbol{\Lambda}\boldsymbol{Q}^T$

把 $X_1,X_2,\cdots,X_n\in\mathbb{R}^m$ 整合成一个样本数据矩阵

$\boldsymbol{X}=[X_1,X_2,\cdots,X_n]\in\mathbb{R}^{m\times n}$

此时协方差矩阵还可以等价写作

$\boldsymbol{S}=\frac{1}{m-1}\boldsymbol{X}^T\boldsymbol{X}$

由于前面提到，一个矩阵本质上表示一个线性变换，即投影。我们用特征向量组成的矩阵 $\boldsymbol{Q}$ 对原数据 $\boldsymbol{X}$ 进行线性变换(投影)，得到新数据 $\boldsymbol{Y}$ 表示为

$\boldsymbol{Y}=\boldsymbol{XQ}\in\mathbb{R}^{m\times n}$

PCA希望线性变换(投影)后的数据满足两点：

数据尽可能分散，即方差尽可能大(这由信号处理学保证)
不同特征互不相关，即协方差为0

我们来计算新数据 $\boldsymbol{Y}$ 的协方差矩阵 $\boldsymbol{S}_Y$

$\begin{aligned} \boldsymbol{S}_Y&=\frac{1}{m-1}\boldsymbol{Y}^T\boldsymbol{Y}=\frac{1}{m-1}(\boldsymbol{XQ})^T\boldsymbol{XQ}\\&=\frac{1}{m-1}\boldsymbol{Q}^T\boldsymbol{X}^T\boldsymbol{XQ}\\&=\boldsymbol{Q}^T\boldsymbol{SQ}\\&=\boldsymbol{Q}^T\boldsymbol{Q}\boldsymbol{\Lambda Q}^T\boldsymbol{Q}\\&=\boldsymbol{\Lambda}\in \mathbb{R}^{n\times n} \end{aligned}$

由于 $\boldsymbol{\Lambda}$ 是一个对角矩阵，因此不同的新特征之间协方差为0，也就是相互正交；同时，由于协方差矩阵的主对角线元素为该数据的方差，因此每个新数据的方差即为 $\boldsymbol{S}$ 的特征值，且降序排列，那么选取前 $k$ 大的特征值对应的新特征量，就实现了降维的操作。

使用特征值分解的PCA算法流程如下

去中心化处理：每个特征下的各个样本值减去各自均值
计算协方差矩阵： $\boldsymbol{S}=\dfrac{1}{m-1}\boldsymbol{X}^T\boldsymbol{X}$
对 $\boldsymbol{S}$ 进行特征值分解： $\boldsymbol{S}=\boldsymbol{Q}\boldsymbol{\Lambda}\boldsymbol{Q}^T$
对特征值从大到小排序，选择前 $k$ 大的特征值
将这 $k$ 个特征向量分别作为行向量组成新的特征向量矩阵 $\boldsymbol{P}\in\mathbb{R}^{n\times k}$
将原数据映射新空间中： $\boldsymbol{Y}=\boldsymbol{XP}\in\mathbb{R}^{m\times k}$

SVD分解

对于任意维度的矩阵 $\boldsymbol{A}\in\mathbb{R}^{m\times n}$ ，其可以分解为如下形式

$\boldsymbol{A}=\boldsymbol{U\Sigma V}^T$

称该式子为矩阵 $\boldsymbol{A}$ 的奇异值分解(Singular Value Decomposition, SVD)。其中 $\boldsymbol{U}\in\mathbb{R}^{m\times m},\boldsymbol{V}\in\mathbb{R}^{n\times n}$ 称作左、右奇异矩阵，同时是半正交矩阵； $\boldsymbol{\Sigma}\in\mathbb{R}^{m\times n}$ 称作对角奇异矩阵，其一般形式为

$\boldsymbol{\Sigma}=\begin{bmatrix}\sigma_1&&&&\\&\sigma_2&&&\\&&\ddots&&\\&&&\sigma_{\min(m,n)}&\\&&&&\ddots\end{bmatrix}$

其中 $\sigma_i,i=1,2\cdots,\min(m,n)$ 是矩阵 $\boldsymbol{A}$ 的奇异值。下面简单介绍如何求这个分解形式。

设矩阵 $\boldsymbol{X}=\boldsymbol{A}^T\boldsymbol{A}\in\mathbb{R}^{n\times n},\boldsymbol{Y}=\boldsymbol{AA}^T\in\mathbb{R}^{m\times m}$ ，不难证明他们都是实对称矩阵，并且具有相同的非零特征值，因此应用特征值分解方法，首先可以得到

$\boldsymbol{A}^T\boldsymbol{A}=\boldsymbol{Q}\boldsymbol{\Lambda}\boldsymbol{Q}^T$

代入 $\boldsymbol{A}=\boldsymbol{U\Sigma V}^T$ 有以下对应关系

$\boldsymbol{Q}=\boldsymbol{V}$
$\boldsymbol{X}=\boldsymbol{A}^T\boldsymbol{A}$ 的特征值 $\lambda_i=\sigma_i^2$

此时考虑原SVD分解式的展开，即按列展开有

$\boldsymbol{A}[v_1,v_2,\cdots,v_n]=[u_1,u_2,\cdots,u_m]\begin{bmatrix}\sigma_1&&&&\\&\sigma_2&&&\\&&\ddots&&\\&&&\sigma_{\min(m,n)}&\\&&&&\ddots\end{bmatrix}\Leftrightarrow u_i=\frac{1}{\sigma_i}\boldsymbol{A}v_i$

上述步骤只对非零奇异值对应的向量计算，剩下的通过正交补齐即可。这样就得到了矩阵 $\boldsymbol{A}$ 的奇异值分解。这里简单指出：奇异值分解反映了任意一个矩阵进行线性变换时的三个步骤，旋转、伸缩、逆旋转。越大的奇异值对应的向量，其在线性变换的作用幅度越大。因此，我们可以把特征值分解的PCA方法套用在SVD分解上，但只需要对原数据矩阵 $\boldsymbol{X}$ 进行SVD分解即可。下表展现了两种方法的区别。

比较维度	PCA的特征值分解法	PCA的SVD分解法
计算对象	协方差矩阵 $\boldsymbol{S} = \dfrac{1}{m-1}\boldsymbol{X}^T\boldsymbol{X}$	均值归一化后的原数据矩阵 $\boldsymbol{X}$
数学分解形式	$\boldsymbol{S} = \boldsymbol{Q}\boldsymbol{\Lambda}\boldsymbol{Q}^T$	$\boldsymbol{X} = \boldsymbol{U\Sigma V}^T$
主成分	协方差矩阵的特征向量	右奇异矩阵的列向量
数值稳定性	较差	现代算法优化能力强
高维数据适应性	极差	极好
工程实现首选	仅用于理论推导或小规模数据集	主流库底层均采用SVD实现

平方映射误差

接下来的讲解以 SVD 分解法为主。将原来的 $n$ 维数据降维到 $k$ 维数据，我们的降维公式为

$\boldsymbol{Y}=\boldsymbol{XP}\in\mathbb{R}^{m\times k}$

其中 $\boldsymbol{P}\in\mathbb{R}^{n\times k}$ 是前 $k$ 大奇异值对应的，右奇异矩阵的特征向量组成的矩阵。现在考虑逆转降维过程，也就是有逆转公式

$\boldsymbol{X}_{inv}=\boldsymbol{YP}^T\in\mathbb{R}^{m\times n}$

由于在降维过程中，有数据已经发生丢失，因此 $\boldsymbol{X}_{inv}$ 与 $\boldsymbol{X}$ 并不会完全相同，而这之间的误差就似乎我们之前提到的投影误差。定义平均平方映射误差为

$d=\frac1m\sum_{i=1}^{m}\|\boldsymbol{x}^{(i)}-\boldsymbol{x}_{inv}^{(i)}\|^2$

PCA算法的目的就是尽可能选取合适的超参数 $k$ ，使得上述误差尽可能小。由于原数据经过了均值归一化处理，因此原数据的总方差为

$D=\frac1m\sum_{i=1}^{m}\|\boldsymbol{x}^{(i)}\|^2$

一般而言，应当尝试不同的 $k$ 值，在最小化平均平方误差的同时，满足经验条件

$\frac{d}{D}=\sum_{i=1}^m\frac{\|\boldsymbol{x}^{(i)}-\boldsymbol{x}_{inv}^{(i)}\|^2}{\|\boldsymbol{x}^{(i)}\|}\leqslant 1\%$

也就是说，该经验条件保证PCA降维保留了原始数据99%的有效信息。

结语

至此，吴恩达Andrew Ng机器学习篇已经结束ヾ(✿ﾟ▽ﾟ)ノ

本系列通过八篇日志，大致总结了机器学习方向的主流算法，介绍了监督学习和无监督学习的多种回归、分类算法。这些内容只是机器学习领域的开场白，而如今更常用的AI模型，比如计算机视觉CV，大语言模型LLM，具身智能等更加依赖于深度神经网络等算法模型。这些内容涉及更深层次的数理基础和模型算法，属于深度学习(Deep Learning)的范畴，后续也会更新相关日志。

希望本系列学习日志能够对您有所帮助，如有错误欢迎大佬在评论区指出，感谢观看。

参考网站