基本的聚类算法简介

Hierarchical clustering, k-means and DBSCAN

聚类是针对给定的样本, 依据它们特征的相似度或距离, 将其归并到若干个 "类" 或 "簇" 的数据分析问题.

假设有 \(n\) 个样本, 每个样本有 \(m\) 个属性, 样本集合用 \(m\times n\) 的矩阵 \(X\) 表示, 每一列表示一个样本.

聚类的基本概念

距离或相似度

本节的距离或相似度是针对两个样本而言的.

常见的距离可以取 \(l^p\) 范数, 或者把 Gram 矩阵取为 \(X\) 的协方差矩阵的逆的度量.

常见的相似度可以取样本相关系数, 夹角余弦.

类或簇

如果类之间的交集为空, 则称为硬聚类, 否则为软聚类. 本章只考虑硬聚类.

用 \(G\) 表示类, \(n_G\) 表示其中样本个数, \(d_{ij}\) 表示样本 \(x_i\) 与 \(x_j\) 的距离.

下面给出类的几种常见定义. 给定 \(T\), 样本 \(x_i\) 与 \(x_j\) 为 \(G\) 中样本,

• 对任意 \(x_i\), \(x_j\), 都有 \(d_{ij}\le T\).
• 对任意 \(x_i\), 存在另一个样本 \(x_j\), 使得 \(d_{ij} \le T\).
• \(\frac{1}{n_G - 1}\sum_{x_j\in G, j\ne i} d_{ij}\le T\).
• 给定 \(V\), \(\frac{1}{n_G(n_G - 1)}\sum_{x_i, x_j\in G, i\ne j} d_{ij}\le T\) 且 \(d_{ij}\le V\).

类的特征

• 类的均值 \(\bar x_G\).
• 类的直径.
• 类的样本散布 (scatter) 矩阵.

\[ A_G = \sum_{i=1}^{n_G}(x_i - \bar x_G)(x_i - \bar x_G)', \]

与样本协方差矩阵 \(\frac{1}{m-1}A_G\), 讲道理应该是 \(n_G - 1\), 但不知道为什么李航用的是 \(m\), 还特地说是特征维数.

类与类之间的距离

类 \(G_p\), \(G_q\) 的中心分别为 \(\bar x_p\), \(\bar x_q\), 常见的距离为

• Single linkage. \(\min\{ d_{ij} | x_i\in G_p, x_j\in G_q \}\).
• Complete linkage. \(\max\{ d_{ij} | x_i\in G_p, x_j\in G_q \}\).
• Centroid linkage, 中心距离. \(d_{\bar x_p, \bar x_q}\).
• Average linkage, 平均距离. \(\frac{1}{n_p n_q}\sum_{x_i\in G_p, x_j\in G_q}d_{ij}\).

层次聚类 (hierarchical clustering)

Bottom-up

1. 每个样本自己为一类, 共 \(n\) 类. 耗时 \(O(n^2 m)\).
2. 计算类间距离 (李航采用的是 single linkage, [2] 采用的是 average linkage).
3. 合并类间距离最小的类, 并回到 step 2 直到只剩下 1 个类 (反复进行 \(n-1\) 次).

可以看出这是一个贪心算法, 时间复杂度 \(O(n^3 m)\). 优点是不需要参数, 缺点是时间复杂度太高.

Top-down

略.

K-means

需要事先指定聚类为 \(k\) 个类, 这是一个缺点. 每个样本到其所属类的中心的距离最小 (也就是名称中的 means).

由于 \(n\) 个样本分为 \(k\) 类的分法数目是指数级的, 所以一般用迭代的办法求解.

1. 初始化 \(k\) 个类中心 (李航采用的是随机选择 \(k\) 个样本作为初始类的中心).
2. 将样本指派到与其最近的中心的类中 (李航采用的距离是欧氏距离).
3. 将每个类的样本均值作为类的新的中心, 并回到 step 2 直到收敛.

进行一次 step 2 的求距离时间复杂度是 \(O(mnk)\), 排序的复杂度大概是 \(O(nk\log k)\), step 3 为 \(O(mn)\). 因为 \(k\) 一般较小, 总得来说进行一轮迭代需要 \(O(mnk)\).

这是一个启发式算法, 结果受初值影响. 初始中心的选择, 比如可以用层次聚类出 \(k\) 类再选择其中心.

类别数 \(k\) 可以通过选取多个值之后通过观察类的质量 (比如用类的平均直径) 来决定.

DBSCAN (density-based spatial clustering of applications with noise)

1. 如果所有点都已经访问过, 则结束算法; 否则任取一个未访问过的点 \(x\), 考虑其 \(r\) 邻域, 即以 \(x\) 为球心, \(r\) 为半径的球 \(O(x, r)\). 球中的所有点标记为已访问, 若球中包含足够多的点 (点数不小于 MinPoints, 这就反应了簇的密度, density based) 则进入 step 2 聚类, 否则记为噪声 (之后这个噪声可能会成为簇中的一部分).
2. 开始聚类, \(O(x, r)\) 中的所有点都和 \(x\) 为一类, 并以这些点的 \(r\) 邻域重复这个步骤直到不能聚类则返回 step 1.

可以见 [2] 的动图. 第 2 步有点像在多维空间证明函数性质时 (比如复分析), 先对一个点的邻域证明, 然后在这个邻域中选一个点再对这个点的邻域证明, 一直这样一环套一环做下去.

参数有两个, 邻域半径 \(r\) 和最小点数 MinPoints.

优点是不需要事先指定簇的个数, 并且簇形状可以任意, 可以识别异常点为噪声.

缺点是若簇的密度不同时, 性能可能不好.

Mean-shift

见 [2].

References

[1] 李航. (2019). 统计学习方法 (第 2 版) (pp. 255-267). 清华大学出版社.
[2] 论智. (2018). 数据科学家需要了解的 5 种聚类算法 [知乎]. https://zhuanlan.zhihu.com/p/37381630

基本的聚类算法简介

原文：https://www.cnblogs.com/shiina922/p/11924884.html