8 聚类分析

目录

• 概念
  • 距离度量
• 基于分割的聚类算法 K-Means&K-Medoids
  • K-Means 算法（K-均值算法）
  • K-Medoids 算法（K-中心点算法）
• 层次聚类算法
  • AGNES 算法
  • DIANA 算法
  • BIRCH 算法
  • 距离度量
• 密度聚类算法
  • 概念拓展
  • DBSCAN 算法
• 基于网格的聚类算法
• 基于模型的聚类算法

概念

聚类是无监督学习，分类&预测是有监督学习。

输入数据集，输出聚类结果。输出结果是 K 组簇，每个簇是一组相似的对象。

距离度量

距离度量有很多方法：

Minkowski 距离：

$D_{ij}=(\sum _{k=1}^d|x_{ik}-x_{jk}{|}^n{)}^{\frac{1}{n}}$ 当 n=1 时，就是曼哈顿距离/绝对值（City-block）

$D_{ij}=\sum _{k=1}^d|x_{ik}-x_{jk}|$

WARNING

考试请使用曼哈顿距离，不要使用欧式距离

当 n=2 时，就是欧氏距离（Euclidean）

$D_{ij}=(\sum _{k=1}^d|x_{ik}-x_{jk}{|}^2{)}^{\frac{1}{2}}$

当 n=∞ 时，就是切比雪夫距离（Chebyshev）

$D_{ij}=\underset{k=1}{\overset{d}{max}}|x_{ik}-x_{jk}|$

Mahalanobis 距离：

$D_{ij}=\sqrt{(x_i-x_j{)}^T{S}^{-1}(x_i-x_j)}$

其中 S 是协方差矩阵，$S_{ij}=\frac{1}{n-1}\sum _{k=1}^n(x_{ki}-{\mu }_i)(x_{kj}-{\mu }_j)$

点对称距离

基于分割的聚类算法 K-Means&K-Medoids

一般把 K 值作为输入，作为目标聚类数。

K-Means 算法（K-均值算法）

【机器学习】K-means（非常详细）| 知乎

机器学习系列（九）聚类之 AGNES | 知乎

1. 首先选取 K 个点作为初始聚类中心
2. 然后计算每个点到这 K 个点的距离，把每个点分配到距离最近的聚类中心
3. 然后重新计算每个簇的中心点

$a_i=\frac{1}{|C_i|}\sum _{x\in C_i}x$

4. 重复这个过程直到聚类中心不再变化或者平均误差收敛

平均误差：$E=\sum _{i=1}^K\sum _{x\in C_i}d(x,a_i)$

优点：

1. 算法的复杂度是 $O(tKn)$，t 是迭代次数，n 是数据集大小。

缺点：

1. K 值的选取不好确定
2. 对噪声和离群点敏感，有较大的离群点时，聚类中心会被拉偏
3. 对初始聚类中心的选择敏感，初始聚类中心不同，聚类结果也不同
4. 不能发现非凸形状的簇，比如环形簇

K-Medoids 算法（K-中心点算法）

数据挖掘入门笔记——K-Medoids（以一知万）| 知乎

k-mediods 每次选取的质心，必须是样本点，

而 k-means 每次选取的质心可以是样本点之外的点，

就好比中位数和平均值的区别

K-Medoids 和 K-Means 方法类似，在选取聚类中心时，K-Medoids 选取的是样本点，而 K-Means 选取的是样本点之外的点。

1. 首先选取 K 个点作为初始聚类中心
2. 然后计算每个点到这 K 个点的距离，把每个点分配到距离最近的聚类中心
3. 选取当前簇中所有其他点到该中心点的距离之和最小的点作为新的中心点
4. 重复这个过程直到聚类中心不再变化

优点：

1. 对噪声和离群点不敏感

缺点：

1. 算法的复杂度是 $O(tK{n}^2)$，t 是迭代次数，n 是数据集大小。复杂度偏大，难以处理大数据集

层次聚类算法

采用距离作为衡量标准，分为凝聚式（AGNES）和分裂式（DIANA）。

AGNES 算法

输入一个 K 值，作为目标聚类数。

把点和点集都视为簇，每次把距离最近的两个簇合并，直到聚类数为 K。

距离的计算方式有很多种，比如最短距离、最长距离、平均距离、中心距离等。

距离相同随便分，优先分离落单的点。

DIANA 算法

DIANA 算法 | 博客园

思想和 AGNES 相反，从一个簇开始，每次把距离最远的点分离出来，直到聚类数为 K。

首先把所有点作为一个簇

1. 寻找直径最大的簇，作为待分裂的簇

直径：$diam(C_i)=\underset{x,y\in C_i}{max}d(x,y)$

也可以选择相异度等其他标准来选择待分裂的簇

2. 寻找直径最大的簇中，距离簇中所有其他点距离之和最大的点，作为分裂出来的簇（分裂出来的簇只有一个点）
3. 在原来的簇中，寻找距离分裂出来的簇最近的点，如果这个点到新簇的距离小于到原来簇中任意点的距离，则把这个点加入新簇
4. 重复 3 直到原来的簇中没有点可以加入新簇
5. 重复 1-4 直到聚类数为 K

优点和缺点

优点：

1. 不需要预先指定聚类数
2. 可以发现任意形状的簇
3. 可以发现离群点
4. 对噪声和离群点不敏感

缺点：

1. 算法的复杂度是 $O(n^2)$，n 是数据集大小。复杂度偏大，难以处理大数据集
2. 过程不可逆，一旦分裂就无法合并

BIRCH 算法

作为 AGNES 和 DIANA 的改进，BIRCH 算法把数据集先聚类成 CF 树，然后再从 CF 树中选取聚类中心。

距离度量

距离度量有很多方法

1. 最短距离（单连接）

$d_{min}(C_i,C_j)=\underset{x\in C_i,y\in C_j}{min}d(x,y)$

2. 最长距离（完全连接）

$d_{max}(C_i,C_j)=\underset{x\in C_i,y\in C_j}{max}d(x,y)$

3. 平均距离

$d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum _{x\in C_i}\sum _{y\in C_j}d(x,y)$

4. 中心距离（均值距离）

用簇的中心点来代表簇

$d_{cen}(C_i,C_j)=d({\mu }_i,{\mu }_j)$

密度聚类算法

聚类（四）—— 基于密度的聚类 | CSDN

基于密度的聚类算法的主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就把它加到与之相近的聚类中。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。 基于密度的聚类算法代表算法有：DBSCAN 算法、OPTICS 算法及 DENCLUE 算法等。

概念拓展

邻域数、直接密度可达、密度可达、密度相连的概念 | CSDN

基于密度的聚类算法常见 2 个参数：

$ϵ$

邻域半径，表示一个点的邻域的大小

$MinPts$

邻域内最少点的个数，表示一个点的邻域内最少有多少个点

中心对象（核心对象）：如果一个点的邻域内至少有 MinPts 个点，则这个点是一个中心对象。

直接密度可达：如果 A 在 B 的 $ϵ$-邻域内，且 B 是一个中心对象，则 A 直接密度可达 B。

密度可达：A 虽然不在 B 的 $ϵ$-邻域内，在 C 的 $ϵ$-邻域内，且 C 是 B 的 $ϵ$-邻域内的点，且 B 是一个中心对象，则 A 密度可达 B。

（密度可达的传递性）

密度相连：如果 A 和 B 都密度可达 C，则 A 和 B 密度相连。

DBSCAN 算法

1. 首先选取一个点 P
2. 如果 P 是一个中心对象（即满足邻域内至少有 MinPts 个点），则把 P 以及所有密度可达的点加入一个簇
3. 如果 P 不是一个中心对象，则把 P 标记为噪声点
4. 重复 1-3 直到所有点都被访问过

基于网格的聚类算法

基于模型的聚类算法