寸_铁

这个屌丝很懒，什么也没留下！

热门标签

聚类算法 | Kmeans：肘方法、Kmeans++、轮廓系数 | DBSCAN_聚类肘部判别法

作者：寸_铁 | 2024-06-30 17:02:04

踩

聚类肘部判别法

本篇文章我们来讲机器学习篇章中的最后一个专题：聚类算法

那么，什么是聚类呢？

	聚类(Clustering)：
	按照某个特定标准(如距离)，把一个数据集分割成不同的类或簇
		使同一个簇内的数据对象相似性尽可能大
		不在同一个簇中的数据对象差异性也尽可能地大
	即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离
1
2
3
4
5

简单说，聚类算法就是物以类聚，人以群分

注意：聚类算法是机器学习篇中接触到的第二个无监督算法（前面讲过PCA）

一. 聚类算法划分方式

1. 划分式

K-Means算法（均值）
K-medoids算法（中值）
K-modes算法（众数）
K-prototypes算法
CLARANS（基于选择）
K-Means++
bi-KMeans

2. 层次式

BIRCH算法（平衡迭代规约）
CURE算法（点聚类）
CHAMELEON（动态模型）
Agglomerative(凝聚式）
Divisive(分裂式)

3. 基于密度

DBSCAN（基于密度连接区域）
DENCLUE（密度分布函数）
OPTICS（对象排序识别）

4. 基于网络

STING（统计信息网络）
CLIOUE（聚类高维空间）
WAVE-CLUSTER（小波变换）

5. 基于模型

统计学方法（比如GMM）
神经网络（比如SOM（Self Organized Maps））

二. K-means算法

牧师村民模型：

有四位牧师前往乡村布道。起初，他们随意选择了几个布道点，并向乡村所有村民公布了这些点的情况。于是，每位村民都前往离家最近的布道点听课

听完课后，大家觉得距离太远了。于是每位牧师统计了自己所有听课村民的地址，并搬到了这些地址的中心地带。他们在海报上更新了自己的布道点位置

每次移动后，牧师不可能让所有人都更近。有些人发现A牧师搬迁后，去B牧师那听课反而更近。于是每位村民又选择了离自己最近的布道点

牧师每周更新位置，村民根据情况选择布道点，最终实现了稳定

上述过程我们用图像描述如下：
在这里插入图片描述

这里补充：【Kmeans聚类的可视化演示】

1. K-means算法公式表达

算法评价：算法简单，聚类效果好，即使是在巨大的数据集上也非常容易部署实施

	K-Means算法有大量的变体
		包括：初始化优化K-Means++ 以及大数据应用背景下的 k-means|| 和 Mini Batch K-Mean
1
2

K-Means算法操作：按照样本之间的距离大小，将样本集划分为 K 个簇
目的：让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

用数学表达式表示，假设簇划分为 $\left(C_{1}, C_{2}, \ldots C_{k}\right)$ ，则我们的目标是最小化平方误差 $\mathrm{E}$ :

$E=\sum_{i=1}^{k} \sum_{x \in C_{i}}\left\|x-\mu_{i}\right\|_{2}^{2}$

其中 $\mu_{i}$ 是簇 $C_{i}$ 的均值向量，有时也称为质心，表达式为:

$\mu_{i}=\frac{1}{\left|C_{i}\right|} \sum_{x \in C_{i}} x$

2. K-means算法流程

输入：样本集 $D=\left\{x_{1}, x_{2}, \ldots . x_{N}\right\}$ ，聚类的簇数 $k$ ，最大迭代次数 $T$
输出：簇划分 $C=\left\{C_{1}, C_{2}, \ldots C_{k}\right\}$

具体操作：

从数据集 $\mathrm{D}$ 中随机选择 $\mathrm{k}$ 个样本作为初始的质心向量，即 $\left\{\mu_{1}, \mu_{2}, \ldots, \mu_{\mathrm{k}}\right\}$ ，将每个簇初始化为空集
当迭代次数 $\ldots, \mathrm{T} )$
a)：计算样本 $x_{i}$ 到各个质心向量 $\mu_{j}$ 的欧式距离
b)：将 $x_{i}$ 划分到最近的簇中，即更新 $C_{\mathrm{j}}=\mathrm{C}_{\mathrm{j}} \cup\left\{\mathrm{x}_{\mathrm{i}}\right\}$
c)：重新计算 $C_{j}$ 中所有样本点的质心
$\mu_{j}=\frac{1}{\left|C_{j}\right|} \sum_{x \in C_{j}} x$

d)：只有当 $\mathrm{k}$ 个质心向量都没有发生变化，则转到步骤3
输出簇划分 $C=\left\{C_{1}, C_{2}, \ldots C_{k}\right\}$

3. Kmeans算法缺点

聚类中心的个数K需要事先给定
但实际中K值的选定是非常困难的，很多时候我们并不知道给定的数据集应该聚成多少个类别才最合适
Kmeans算法需要随机地确定初始聚类中心
不同的初始聚类中心可能导致完全不同的聚类结果，有时会导致算法收敛很慢甚至出现聚类出错的情况

3.1 肘方法

针对第一个缺点，通常我们会根据先前的经验选择一个合适的k值，如果没有先验知识，则可以使用“肘方法”来选择一个合适的k值

	肘方法，也称为手肘法或Knee of SSE，是用于确定聚类算法中最优聚类数（K值）的一种启发式方法
	
		核心概念：在聚类分析中，特别是在K-means聚类算法中，我们需要预先指定簇的数量K。为了找到最佳的K值，通常会使用误差平方和（SSE）作为评估标准
		操作方式：随着聚类数量K的增加，样本会被划分得越来越精细，每个簇内的紧密程度提高，因此SSE会逐渐减小
		     		当K值小于实际的聚类数量时，增加K会显著降低SSE
		     		当K值达到实际聚类数量后，再增加K，SSE的下降速度会突然减慢
		实际应用：在实践中，通过计算不同K值对应的SSE，并将这些点绘制在图表上，寻找“肘部”出现的点
			 		即：SSE下降速度减缓的转折点，该点的K值通常被认为是数据集中真实的聚类数量
1
2
3
4
5
6
7
8

讲该方法抽象为数学公式：
$SSE=\sum_{i=1}^{k} \sum_{p \in C_{i}}\left|p-m_{i}\right|^{2}$

其中 $C_{i}$ 为第 $i$ 个簇， $m_{i}$ 为第 $i$ 个质心， $p$ 为属于 $C_{i}$ 的数据点，SSE代表了聚类效果

3.2 k-means++ 算法

针对第二个缺点：可以通过k-means++算法来解决，即对于初始化质心的优化策略

从输入的数据点集合中随机选择一个点作为第一个聚类中心 $μ 1$
对于数据集中的每一个点 $x_{i}$ ，计算到已选择中心点的最近聚类中心的距离D
选择一个新的数据点作为新的聚类中心，选择的原则是：
D较大的点，被选取作为聚类中心的概率较大
重复2和3，直到选择出k个聚类质心
利用这k个质心来作为初始化质心，运行标准的K-Means算法

这里对下一个聚类中心点的选举方式做解释：

对于距离最远的样本点，可能是离群点
对于单个最远距离的离群点，其概率或许很大；但整体看待一个簇的概率时，单个离群点的概率就很小

3.2.1 k-means|| 算法

k-means||是k-means++的变体，k-means||在初始化中心点时对kmeans++的缺点做了
规避，主要体现在：

	不需要根据k的个数严格地寻找k个点
	
	主要思路：
	改变每次遍历时的取样规则
	每次获取 K个样本，重复该取样操作O(logn)次
	将这些抽样出来的样本聚类出K个点
1
2
3
4
5
6

使用这K个点作为K-Means算法的初始聚簇中心点（实践证明：一般5次重复采用就可以保证一个比较好的聚簇中心点）

3.3 Mini Batch K-Means 算法

在传统的K-Means算法中，要计算所有的样本点到所有的质心的距离，如果样本量非常大，算法非常耗时；因此，在海量数据面前，Mini Batch K-Means应运而生

Mini Batch操作：
用样本集中的一部分的样本来做传统的K-Means，避免样本量太大时的计算难题，同时算法收敛速度也大大加快

 	选择一个合适的批样本大小batch size，用batch size个样本来做K-Means聚类
 	
 	对于batch size：一般是通过无放回的随机采样得到的
1
2
3

Mini Batch代价：
聚类的精确度会有一些降低，一般来说这个降低的幅度在可以接受的范围之内

4. 聚类评估

簇内不相似度：计算样本 $i$ 到同簇其它样本的平均距离为 $a_{i}$
$a_{i}$ 越小，表示样本 $i$ 越应该被聚类到该簇

簇 $C$ 中的所有样本的 $a_{i}$ 的均值被称为簇 $C$ 的凝聚度

簇间不相似度：计算样本 $i$ 到最近簇 $C_{j}$ (非自身所在簇)所有样本的平均距离 $b_{i}$
具体：计算所有簇中样本到样本 $i$ 的平均距离，取距离最小的簇

$b_{i}$ 越大，表示样本 $i$ 越不属于其它簇
轮廓系数： $s_{i}$ 取值范围为 $[- 1, 1]$
越接近1表示样本 $i$ 聚类越合理
越接近-1，表示样本 $i$ 应该分类到另外的簇中
近似为0，表示样本 $i$ 应该在边界上

所有样本 $s_{i}$ 的均值被称为聚类结果的轮廓系数

$s(i)=\frac{b(i)-a(i)}{\max \{a(i), b(i)\}}$

$s(i)=\left\{$

\begin{array}{ll} 1 - \frac{a (i)}{b (i)}, & a (i) < b (i) \\ 0, & a (i) = b (i) \\ \frac{b (i)}{a (i)} - 1, & a (i) > b (i) \end{array}

$\begin{array}{ll} 1-\frac{a(i)}{b(i)}, & a(i)<b(i) \\ \\ 0, & a(i)=b(i) \\ \\ \frac{b(i)}{a(i)}-1, & a(i)>b(i) \end{array}$ \right.

s (i) = ⎩ ⎨ ⎧ 1 - \frac{a ( i )}{b ( i )}, 0, \frac{b ( i )}{a ( i )} - 1, a (i) < b (i) a (i) = b (i) a (i) > b (i)

补充：当簇中存在异常点时，使用K-Mediods聚类（K中值聚类）的效果优于Kmeans

三. DBSCAN算法

基于距离的聚类算法对于球状簇的聚类效果并不好

而对于基于密度的聚类算法，聚类形状可以为任意形状：

	通过在数据集中寻找被低密度区域分离的高密度区域，将分离出的高密度区域作为一个独立的类别
1

在这里插入图片描述
DBSCAN，即Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法，是基于密度空间的聚类算法

	具体原理：
		每个簇类的密度高于该簇类周围的密度
		噪声的密度小于任一簇类的密度

		因此DBSCAN算法也能用于异常点检测
1
2
3
4
5

在这里插入图片描述

1. DBSCAN算法组成

DBSCAN算法处理后的聚类样本点分为：

核心点（core points）
边界点（border points）
噪声点（noise）

超参数：距离 $Ɛ$ 和邻居数目 $M in Pt s$

1.1 核心点

对某一数据集 $D$ ，若样本 $p$ 的 $\varepsilon$ - 邻域内至少包含MinPts个样本（包括样本 $p$ ），那么样本 $p$ 称核心点。即:

$N_{\varepsilon}(p) \geq \operatorname{MinPts}$

其中 $\varepsilon$ - 邻域 $N_{\varepsilon}(\mathrm{p})$ 的表达式为:

$N_{\varepsilon}(p)=\{q \in D \mid \operatorname{dist}(p, q) \leq \varepsilon\}$

1.2 边界点

若样本 $b$ 在任意核心点 $p$ 的 $Ɛ$ - 邻域内，但是它的 $Ɛ$ - 邻域内的样本数少于 $M in Pt s$ （包括样本p），那么样本b称为边界点

1.3 噪声点

如果样本n既不是核心点，也不是边界点，则称为噪声点