聚类方法
约 4612 个字 预计阅读时间 31 分钟
聚类的基本概念
假设有 \(n\) 个样本，每个样本由 \(m\) 个属性的特征向量组成，用矩阵 \(X\) 表示为：
聚类的核心概念是相似度（similarity）或距离（distance）。衡量标准有：
- 闵可夫斯基距离
- 马氏距离
- 相关系数
- 夹角余弦
马哈拉诺比斯距离 ，简称为马氏距离，用于表示数据的协方差距离，这是一种有效的计算两个未知样本集的相似度的方法，他考虑到各种特性之间的联系，比如说一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的，而且独立于测量尺度，对于一个矩阵为 \(\mu=\left( \mu_{1} ,\mu_{2},\mu_{3},\dots,\mu_{p}\right)^{T}\) ，协方差矩阵为 \(\Sigma\) 的多变量向量 \(x= (x_{1},x_{2},x_{3},\dots,x_{n})^{T}\) ，其马氏距离：
马氏距离也可以定义为两个服从同一分布且协方差矩阵 \(\Sigma\) 的随机变量 \(\vec{x}\) 与 \(\vec{y}\) 的差异程度：
马哈拉诺比斯距离是基于样本分布的一种距离。物理意义就是在规范化的主成分空间中的欧氏距离。所谓规范化的主成分空间就是利用主成分分析对一些数据进行主成分分解。再对所有主成分分解轴做归一化，形成新的坐标轴。由这些坐标轴张成的空间就是规范化的主成分空间。
可以采用马氏距离学一个合适的夹角余弦：
为了方便优化过程，一般会做一个归一化处理，使得分母为常数。
- 用距离度量相似度时，距离越小样本越相似
- 用相关系数时，相关系数越大样本越相似
Tip
不同相似度度量得到的结果并不一定一致
通过聚类得到的类或簇，本质是样本的子集。
- 硬聚类方法：如果一个聚类方法假定一个样本只能属于一个类，或类的交集为空集。
- 软聚类方法：如果一个样本可以属于多个类，或类的交集不为空集。
类的特征可以通过不同的角度来刻画，常用的特征有：类的中心、类的直径、类的样本散布矩阵和样本协方差矩阵。
- 类的矩阵：
- 类的直径：
- 类的样本散布矩阵和样本协方差矩阵
考虑类 \(G_{p}\) 与类 \(G_{q}\) 之间的距离 \(D(p,q)\) ，也称为连接（linkage）。设类 \(G_{p}\) 包含 \(n_{p}\) 个样本，\(G_{q}\) 包含 \(n_{q}\) 个样本，分别用 \(\bar{x}_{p}\) 和 \(\bar{x}_{q}\) 表示 \(G_{p}\) 和 \(G_{q}\) 的均值，即类的中心。
- 最短距离或单连接：定义类的样本与的样本之间的最短距离为两类之间的距离
- 最长距离或完全连接：定义类的样本与的样本之间的最长距离为两类之间的距离
- 中心距离：定义类与类的中心之间的距离为两类之间的距离：
- 平均距离：定义类与类任意两个样本之间距离的平均值为两类之间的距离
层次聚类
聚合聚类的具体过程：对于给定的样本集合，开始将每个样本分到一个类，然后按照一定规则，例如类间距离最小，将最满足规则条件的两个类进行合并，如此反复进行，每次减少一个类，直到满足停止条件，如所有样本聚为一类。
聚合聚类算法
输入： \(n\) 个样本组成的样本集合及样本之间的距离
输出：对样本集合的一个层次化聚类
- 计算 \(n\) 个样本两两之间的欧式距离 \(\left\{ d_{ij} \right\}\) ，记作矩阵 \(D = [d_{ij}]_{n\times n}\)
- 构造 \(n\) 个类，每个类只包含一个样本
- 合并类间距离最小的两个类，其中最短距离为类间距离，构建一个新类
- 计算新类与当前各类的距离，若类的个数为 \(1\) ，终止计算，否则回到步 \(3\)
聚合层次聚类算法的复杂度是 \(\mathcal{O}(n^{3}m)\) ，其中 \(m\) 是样本的维数， \(n\) 是样本个数。
k-均值聚类
\(k\) 均值聚类将 \(n\) 个样本集合 \(X = \left\{ x_{1},x_{2},\dots,x_{n} \right\}\) 分为 \(k\) 个子集，构成 \(k\) 个类 \(G_{1},G_{2},\dots,G_{k}\) ，每个样本到其所属类的中心距离最小，每个样本只能属于一个类，也就是 \(G_{i}\cap G_{j}= \emptyset\) ，用 \(C\) 表示划分，一个划分对应一个聚类结果。
划分 \(C\) 是一个多对一的函数，如果把每个样本用一个整数 \(i\in \left\{ 1,2,\dots,n \right\}\) 表示，每个类也用一个整数 \(l \in \left\{ 1,2,\dots,k \right\}\) 表示，那么划分或者聚类可以用函数 \(l = C(i)\) 表示，实际上 \(k\) 均值聚类的模型是一个从样本到类的函数。
用特征向量表示样本，特征向量的维度为 \(m\) 。用欧式距离平方作为样本之间的距离 \(d(x_{i},x_{j})= \lVert x_{i}-x_{j} \rVert^{2}\)，定义样本与其所属类的中心之间的距离的总和为损失函数，即：
\(\bar{x}_{l}=(\bar{x}_{1l},\bar{x}_{2l},\dots,\bar{x}_{ml})^{T}\) 是第 \(l\) 个类的均值或中心，\(n_l = \sum_{i=1}^{n}I(C(i)=l),I(C(i)=l)\) 是指数函数，取值为 \(1\) 或 \(0\) ，函数 \(W(C)\) 称为能量，表示相同类中的样本相似程度。
\(k\) 均值聚类就是求解最优化问题：
相似的样本被聚到同类时，损失函数值最小，这个目标函数的最优化能达到聚类的目的。但这是一个组合优化的问题，\(n\) 个样本分到 \(k\) 类，可能的分法（第二斯特林数）为
实际上，\(k\) 均值聚类的最优化求解问题是 \(NP\) 难问题，显示采用迭代方法求解。
Note
输入：\(n\) 个样本的集合 \(X\)
输出：样本集合的聚类 \(C^{*}\)
- 初始化，令 \(t =0\) ，随机选择 \(k\) 个样本点作为初始聚类中心 \(m^{(0)} = (m_{1}^{(0)},\dots,m_{l}^{(0)},\dots,m_{k}^{(0)} )\) 。
- 对样本进行聚类，对固定的类中心 \(m^{(t)} = (m_{1}^{(t)},\dots,m_{l}^{(t)},\dots,m_{k}^{(t)} )\) ，计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果。
- 计算新的类中心，对聚类结果，计算当前各个类中的样本的均值，作为新的类中心 \(m^{(t+1)} = (m_{1}^{(t+1)},\dots,m_{l}^{(t+1)},\dots,m_{k}^{(t+1)} )\)
- 如果迭代收敛或符合停止条件，输出最优聚类结果，否则取 \(t=t+1\) ，转 \(2\)
\(k\) 均值聚类算法的复杂度是 \(\mathcal{O}(mnk)\) ，其中 \(m\) 是样本维数，\(n\) 是样本个数，\(k\) 是类别个数。
\(k\) 均值算法高度依赖初始聚类中心的选择，选取不同的初始中心，可能会得到不同的聚类结果。但是我们没有办法像聚合聚类那样将每个样本点都设为一个类。一种选取方法是：首先随机选取一个点作为首个中心，后续每个中心的选择概率与其到已有中心的最短距离平方成正比。这是 k-means++算法的做法，其核心思想是让初始中心尽可能分散，这种策略降低了随机初始化导致的局部最优风险，使聚类结果更稳定。也可以先用层次聚类计算 \(k\) 个类，取每个类的质心作为初始中心。
\(k\) 均值聚类中的类别数 \(k\) 值需要预先指定，而在实际应用中最优的 \(k\) 值是不知道的。可以尝试用不同的 \(k\) 值聚类，检验得到聚类结果的质量，推测最优的 \(k\) 。聚类结果的质量可以用类的平均直径来衡量：一般来说，类别数变小时，平均直径会增加，而到类别数变大超过某个值以后，平均直径不变，这个值是最优的 \(k\) 值。
谱聚类
图论
-
图G ：由顶点集 \(V\) 和边集 \(E\) 构成的，记为 \(G(V,E)\)
-
邻接矩阵 \(W\) : 行数和列数等于矩阵顶点的个数，矩阵元素为 \(0\) 或 \(1\) ， \(1\) 表示对应的对顶点有边相连， \(0\) 表示没有边相连。
-
顶点的度：等于与顶点相连接的边的条数。
-
度矩阵：为一个对角矩阵。将邻接矩阵各行元素累加至 对应的主对角元素，可得到度矩阵 \(D\)
-
Laplace 矩阵：度矩阵减去邻接矩阵得到 Laplace 矩阵 \(L\)
基于数据集的图构造：将每一个数据点视为图的一个顶点，顶点之间可以有边相连。每条边上加上一些权重用于反映点对亲和性（相似性）。根据我们所选的权重可以构建对应的点对相似度矩阵 \(W\) ，此时顶点的度可以表示为所有与该顶点相连接的边的权重之和，对应度矩阵 \(D\)，Laplace 矩阵依旧描述为：
关于图构造，既可以构造全连接，也可以构造局部连接，局部连接中有 \(k\) -近邻和 \(\varepsilon\) -半径两种方式，为了确保 \(W\) 的对称性，可以取 \(W = (W^{T}+W) /2\)
考虑子图 \(A \subset V\) ，定义势 \(\lvert A \rvert\) 等于其包含的顶点个数，定义体积 \(\mathrm{vol}(A)\) 等于其中所有顶点的度之和。将 \(V\) 中去掉 \(A\) 的顶点所构成的子图 \(\bar{A}=V-A\) 称为子图 \(A\) 的补图。
边割：指边 \(E\) 的一个子集，去掉该子集的边，图就变成两个连通子图
设 \(A_{1},A_{2},\dots,A_{k}\) 为顶点集合 \(A\) 的非空连通子集，如果 \(A_{i}\cap A_{j} = \emptyset\) 且 \(A_{1}\cup A_{2}\cup\dots \cup A_{k}= V\)，则称其为图 \(G\) 的一个分割。
子图相似度：两个子图的相似度定义为连接两个子图所有边的权重之和：
也称为子图之间的切割 \(\mathrm{cut}(A,B)\) 。
最小二分切割：在所有的图切割中，找一个最小代价的切割，将图分 为两个不连通的子图。也就是说，切开之后，两个子图之间的相似性要最小，即如下最优化问题：
在实践中，上述目标函数通常将一个点(比如野点)从其余各点中分离出来。从聚类的角度看，这并不是我们所期望的。出现上述问题的原因在于对子图的规模没有加以限制。一个基本的假设是希望两个子图的规模不要相差太大，采用子图的势或者体积来对切割进 行归一化，即定义如下目标函数：
- 子图的势：
- 子图的体积：
Laplace 矩阵
性质：
- \(L\) 的行和为零
- \(L\) 有一个特征值为零，其对应的特征向量为一个元素全为 \(1\) 的向量
- \(L\) 有 \(n\) 个非负的特征值，\(n\) 为图的顶点个数。
- \(L\) 是一个半正定矩阵
- 图的连通子图与拉普拉斯矩阵L的特征值的关系：设 \(G\) 为一个具有非负连接权重的无向图，由图 \(G\) 导出的拉普拉斯矩阵 \(L\) 的零特征值的重数等于图 \(G\) 的连通子图的个数 \(k\) 。
最后一个性质证明如下：
考虑图 \(G\) 是连通的，此时 Laplace 矩阵只有一个特征值为零，且对应的特征向量由元素全为 \(1\) 的向量构成。取 \(f\) 时特征值 \(0\) 对应的特征向量，于是有：
上式推出 \(w_{ij}(f_{i}-f_{j})^{2}\) 必须等于零，此时由于图是连通的，根据图论相关知识，一定存在一条路径将所有的顶点连接起来，向量 \(f\) 的所有分量均相等。
如果此时有多个子图，假定样本点按连通顺序逐个排序，由于连通子图之间不存在边相连，所以图 \(G\) 的 Laplace 矩阵具有分块连通的结构：
且每个 \(L_{i}\) 均为一个 Laplace 矩阵，对应一个连通的子图。所以一个可以构造 \(k\) 个非零特征向量（\(k\) 是子图个数，特征向量为每个子图特征值 \(0\) 对应的全 \(1\) 向量）。而且不可能构造多于 \(k\) 个非零特征向量使特征向量空间的基大于 \(k\) 证毕。
如果图 \(G\) 具有 \(k\) 个连通子图，若每个连通子图为一个聚类，那么采用其拉普拉斯矩阵的零特征值对应的特征向量可以将这些子图分离开来，这是因为这些特征值对应的特征向量具有分块非零等值的结构。因此可以自然地将数据点分开。因此，求解 \(L\) 矩阵零特征值对应的特征向量，这正是我们所期待的。
但是，实际应用中，数据簇之间并非是完全分离的。这就是说，图可能仍然是连通的。在此情形下，自然地，可以考察拉普拉斯矩阵最小的特征值对应的特征向量，并由这些特征向量组成新的特征空间。
谱聚类
Tip
广义上讲，任何在学习过程中应用到矩阵特征值分解的方法均叫谱学习方法
谱聚类算法建立在图论中的谱图理论基础之上，其本质是将聚类问题转化为一个图上的关于顶点划分的最优问题。
设 \(G\) 为一个具有非负连接权重的无向图，由图 \(G\) 导出的拉普拉斯矩阵 \(L\) 的零特征值的重数等于图 \(G\) 的连通子图的个数。实际中，数据簇之间可能相互混杂、重叠，所以 \(L\) 矩阵通常并不具有分块形状（无论怎样调整样本顺序）。因此，可以考察其最小的几个特征值对应的 特征向量。一旦拉普拉斯矩阵得到构造，由其最小的几个特征对应 的特征向量所构成的空间就得到确定。因此，构造拉普 拉斯矩阵是至关重要的一步。构造拉普拉斯矩阵本质上取决于对数据图的描述，即图构造。
两种构造归一化图 Laplace 矩阵的方法：
- 对称型：
- 随机游走型：
对于上述两种归一化矩阵，有如下性质：
- 对任意 \(f = \begin{bmatrix}f_{1},f_{2},\dots,f_{n} \end{bmatrix}^{T}\in \mathbb{R}^{n}\) 有：
- 若 \(\lambda\) 为 \(L_{\mathrm{rw}}\) 的特征值，且与其对应的特征向量为 \(u\) ，当且仅当 \(\lambda\) 为 \(L_{\mathrm{sym}}\) 的一个特征值， \(D^{1/2}u\) 为其对应的特征向量。
- 若 \(\lambda\) 为 \(L_{\mathrm{rw}}\) 的特征值，且与其对应的特征向量 \(u\) ，当且仅当 \(Lu =\lambda Du\)
- \(L_{\mathrm{rw}}\) 有一个零特征值且对应的特征向量全为 \(1\) ，\(L_{\mathrm{sym}}\) 也有一个零特征值且对应的特征向量为 \(D^{1/2}e\) ，\(e\) 为全量全为 \(1\) 的 \(n\) 维向量。
- \(L_{\mathrm{sym}}\) 和 \(L_{\mathrm{rw}}\) 维半正定矩阵，特征值维正实数，且至少有一个为零。
- 设 \(G\) 为一个具有非负连接权重的无向图，由图 \(G\) 导出的 \(L_{\mathrm{sym}}\) 和 \(L_{\mathrm{ew}}\) 的零特征值的重数等于图 \(G\) 的连通子图个数。
- 设 \(A_{1},A_{2},\dots,A_{k}\) 为 \(G\) 的 \(k\) 个连通成分，设 \(e_{A_{i}}\) 为对应于子图 \(A_{i}\) 为的指示向量，则 \(e_{A_{i}}\) 为对应的特征向量，\(D^{1/2}e_{A_{i}}\) 为 \(L_{\mathrm{sym}}\) 的一个特征向量。
Tip
根据不同的图拉普拉斯构造方法，可以得到不同的谱聚类算法形式。
- 算法(classical)
- 算法(Ncut)
- 算法 （Ng's Algorithm）