> For the complete documentation index, see [llms.txt](https://lang-yu.gitbook.io/mi-ai/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lang-yu.gitbook.io/mi-ai/ke-cheng-xi-lie/00.index/09.cluster.md).

# 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. 相似度衡量

![](/files/zU1RsaHJrWCGUA4Ql22Z)

    **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. 层次聚类算法

![](/files/qkFAop3Kf5hji2it6NeY)

#### 2.1.1. Single Link

* 最小值
* `d(2,3) = 1`：先找距离最短的。
* `d(1,4) = 2`：然后找距离次短的。
* `d(2,5) = 3`：然后找距离比较短的，所以将5加入到`2,3`。
* `d(4,5) = 4`：最后，最终构成上图中的树形图。

![](/files/xaL5BlW8U3jNo7dBwx5E)

#### 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加入。

![](/files/yAD4S3NuaQVZYjtgCmLs)

#### 2.1.3. Average Linkage

* 平均值

![](/files/kcXsrYZhR5ZNTaCsO6Hv)

#### 2.1.4. Centroid Method

* 群中心

![](/files/O95iiXKMu2RJsD7lmz9G)

#### 2.1.5. Ward's

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

$$SS = \sum\limits\_{i=1}^p \sum\limits\_{j=1}^m ( x\_{ij} - \bar{x\_i})^2$$

![](/files/jLxV5jTjFyr1G4KnRlZL)

![](/files/K6sqvLa8wZZdAb2UNg2m)

> 通常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

![](/files/lUwluXWodWMigybye4no)

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

### 2.4. 密度聚类

#### 2.4.1. DBSCAN

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

![](/files/WUgarfufnGV228qHsi9t)

* 可以处理噪音和离群值
* 所有的离群值都会直接被标识出来
* 通常做异常侦测
* 需要设置的参数：
  * **Eps**：半径
  * **MinPts**：半径内的样本点的数量

![](/files/dLDRCLEYdWzD6mVYl6zh)

    三种点：

* 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$$

> 前三个需要人为参与。

    下图为轮廓系数图解：

![](/files/e8IrLo0on9ArX9OyjDSR)