9.聚类

1.基本概念

    聚类分类大纲

• 层次聚类

  • 单一链结法

  • 完全链结法

  • 平均链结法

  • 中心法

  • Ward's法

• 划分聚类法

  • K-Means法

  • K-Medoids法

  • Kohonen Self-Organizing Maps（SOM）

  • 两步法

• 模糊聚类

  • EM算法

• 密度聚类

  • 密度聚类算法（DBSCAN）

• 群数的判断

  • R-Squared（R2）

  • Semi-Partial R-Squared

  • Root-Mean-Square Standard Deviation（RMSSTD）

  • Silhouette Coefficient（轮廓系数）

    没有目标变量（非监督），将相似的内容聚合在一起，其中心思想是：同一群内成员的相似性要越高越好，而不同群间成员的相异性则要越高越好。

虽然没有明确的目标变量，但实际操作中你需要有一个分类的目标维度，如按XX分类：颜色、大小、透明度、纹理等。

    聚类重点

• 如何使用数字来表示成员之间的相似性（相异性）？

• 如何根据这些相似性将类似的成员分在同一群？

• 所有成员分群完后，对每一群的特征应如何描述？

1.1. 相似度衡量

    Jaccard（杰卡德系数）：

$d(i,j) = \frac{r + s}{q + r + s}$

    Simple Matching：

$d(i,j) = \frac{r + s}{q + r + s + t}$

    距离计算

• 曼哈顿距离（直角距离）

• 欧式距离

2. 算法分类

    分类维度：

• Exclusive / Non-Exclusive

  • Exclusive：排他性聚类法（一个数据只属于一个群），如K-Means。

  • Non-Exclusive：非排他性聚类法（一个数据可以属于多个群），如EM。

    排他性再分类

• Hierarchical（层次聚类法）：

  • Single Linkage, Complete Linkage

  • Average Linkage, Controid

  • Ward's

• Partioning（划分聚类法）：

  • K-Means

  • K-Medoids（PAM）

  • Kohonen Self-Organizing Maps（SOM）

  • Two Step

    非排他性（模糊聚类EM算法）     密度聚类算法

2.1. 层次聚类算法

2.1.1. Single Link

• 最小值

• d(2,3) = 1：先找距离最短的。

• d(1,4) = 2：然后找距离次短的。

• d(2,5) = 3：然后找距离比较短的，所以将5加入到2,3。

• d(4,5) = 4：最后，最终构成上图中的树形图。

2.1.2. Complete Link

• 最大值（要计算两两之间的完全图，都存在链接）

• d(2,3) = 1：先找距离最短的。

• d(1,4) = 2：然后找距离次短的。

• d(2,5) = 3：5想加入2,3，由于没有5,3，所以暂时不加入。

• d(4,5) = 4：5想加入1,4，由于没有1,4，所以暂时不加入。

• d(2,4) = 5：两个群由于没有1,2、1,3，所以不加入。

• d(1,2) = 6：由于没有1,3，所以不加入。

• d(1,5) = 7：由于出现了完全图，所以5加入。

2.1.3. Average Linkage

• 平均值

2.1.4. Centroid Method

• 群中心

2.1.5. Ward's

• 直接使用上述评估指标，运算更复杂（略）。

$SS = \sum\limits_{i=1}^p \sum\limits_{j=1}^m ( x_{ij} - \bar{x_i})^2$

通常Ward's最好，Linkage最差，而划分聚类又比层次聚类更好。

两步法：

• 先将数据切分成许多小群。

• 然后使用层次聚类，决定群数。

群数判断

    如果使用阶层聚类分析法，集结完成后，就需要判断应分成几群合适，一般使用陡坡图来判断。

2.2. 划分聚类算法

• 效果更好，事先指定需要划分成几个群。

2.2.1. K-Means

    K表示最终需要聚类的群数量，每次运行结果可能不一样。

• 优点

  • 计算速度快

• 缺点

  • 对离群值十分敏感

  • 并不是一个最优方案（不一定能找到最佳解）

  • 只能处理数值型数据

    初始中心点的选取会影响结果：

• 随机选取K个样本点作初始类群中心点

• （更好的）选择第一个样本点，其次选择第一个忠县距离超过标准的下一个样本点，然后选和第1、2个群中心距离更远的第三个群中心。

2.2.2. Algorithem PAM

• 优点

  • 可以得到全局最佳解

  • 可以处理非数值型数据

• 缺点

  • 计算速度慢

    将K-Means的虚拟群中心改成真实样本点，并且求SS值找到最小的。

2.2.3. SOM

    （神经网络）自我组织映射法。

2.3. 模糊聚类

• 排他性：硬聚类，K-Means

• 非排他性：软聚类，EM

2.3.1. EM

估计时使用高斯分布估计属于每个群的概率值，可以将K-Means理解成一种特殊的EM算法。

2.4. 密度聚类

2.4.1. DBSCAN

    根据数据的形状进行聚类，可以找到任何形状的聚类，全称：Density-Based Spatial Clustering of Applications with Noise。

• 可以处理噪音和离群值

• 所有的离群值都会直接被标识出来

• 通常做异常侦测

• 需要设置的参数：

  • Eps：半径

  • MinPts：半径内的样本点的数量

    三种点：

• Core Point：核心点

• Border Point：边界点

• Outlier Point：离群点（噪音）

• 优点：

  • 不需要事先指定集群数

  • 可轻松处理噪声，不受离群值影响

  • 没有严格形状，可以正确容纳许多数据点

• 缺点

  • 无法使用不同密度的数据集

  • 对聚类超参数敏感：Eps和MinPts

  • 如果数据过于稀疏，则表现不佳

  • 密度测量（可达/相连）可能受到抽样的影响

3. 群数判断

• Sum of Square, SS

• R-Sqaured, R2（SS的变型）：$R^2 = \frac{SS_B}{SS_T}$，距离是否有突然间缩小。
• Semi-Partial R-Squared（SS的拓展）：群和群之间SS的增加程度，如果突然增加，则表示集结过程就应该停止。

• Silhouette Coefficient（轮廓系数）：$s(i) = \frac{b(i) - a(i)}{\max{\{a(i),b(i)\}}}, -1 \le s(i) \le 1$

前三个需要人为参与。

    下图为轮廓系数图解：