文章目录
- 一、聚类
- 二、K-Means算法
* - 1、基本概念
- 2、工作流程
- 3、优缺点
- 三、DBSCAN算法
* - 1、基本概念
- 2、工作流程
- 3、参数选择
- 4、优缺点
- 四、可视化展示
* - 1、K-Means算法
- 2、DBSCAN算法
- 五、参考文献
一、聚类
聚类是根据在数据中发现的描述对象及其关系的信息，将数据对象分簇。其目的是使簇内的对象相互之间是相似的(相关的)，而不同簇中的对象是不同的(不相关的)。簇内相似性越大，簇间差距越大，说明聚类效果越好。
聚类是一种无监督学习的方法，是许多领域中常用的机器学习技术。其难点在于如何评估和调参。
二、K-Means算法
1、基本概念
- 要得到簇的个数，需要指定K K K值
- 质心：均值，即向量各维取平均即可
- 距离的度量：常用欧几里得距离和余弦相似度(先标准化)
- 优化目标：min ∑ i = 1 K ∑ x ∈ C i d i s t ( c i , x ) 2 \min\displaystyle\sum_{i=1}^K\displaystyle\sum_{x\in C_i}dist(c_i,x)^2 min i =1 ∑K x ∈C i ∑d i s t (c i ,x )2
2、工作流程
（1）数据预处理：主要是标准化、异常点过滤。
（2）设置参数K K K，其含义是将数据集聚合成K K K类。
（3）随机选取K K K个质心，记为μ 1 ( 0 ) , μ 2 ( 0 ) , ⋯ , μ K ( 0 ) \mu_1^{(0)},\mu_2^{(0)},\cdots,\mu_K^{(0)}μ1 (0 ),μ2 (0 ),⋯,μK (0 )。
（4）定义损失函数：J ( c , μ ) = min ∑ i = 1 M ∣ ∣ x i − μ c i ∣ ∣ 2 (1) J(c,\mu)=\min\sum_{i=1}^M||x_i-\mu_{c_i}||^2\tag{1}J (c ,μ)=min i =1 ∑M ∣∣x i −μc i ∣∣2 (1 )（5）重复下述过程，直到J J J收敛：
（5.1）对于每一个样本x i x_i x i ，将其分配到距离最近的质心，即：x i ∈ arg min k ∣ ∣ x i − μ k ( t ) ∣ ∣ (2) x_i\in\argmin_k||x_i-\mu_k^{(t)}||\tag{2}x i ∈k a r g m i n ∣∣x i −μk (t )∣∣(2 )（5.2）对于每一个类质心μ k \mu_{k}μk ，重新计算该类的质心，即：μ k ( t + 1 ) = 1 ∣ C k ∣ ∑ x ∈ C k x (3) \mu_k^{(t+1)}=\frac{1}{|C_k|}\sum_{x\in C_k}x\tag{3}μk (t +1 )=∣C k ∣1 x ∈C k ∑x (3 )
3、优缺点
优点：简单快速，适合常规数据集
缺点：
① K K K值难确定；② 受初始值影响较大；③ 复杂度与样本规模呈线性关系；④ 很难发现任意形状的簇。
三、DBSCAN算法
1、基本概念
DBSCAN全名为Density-Based Spatial Clustering of Applications with Noise。
- 核心对象：若某个点的密度达到算法设定的阈值则其为核心点(即r r r邻域内点的数量不小于m i n P t s minPts m i n P t s)
- ε \varepsilon ε-邻域的距离阈值：设定的半径r r r
- 直接密度可达：若某点p p p在点q q q的r r r邻域内，且q q q是核心点，则p − q p-q p −q直接密度可达
- 密度可达：若有一个点的序列q 0 q_0 q 0 、q 1 q_1 q 1 、⋯ \cdots ⋯、q k q_k q k ，对任意q i − q i − 1 q_i-q_{i-1}q i −q i −1 是直接密度可达的，则称从q 0 q_0 q 0 到q k q_k q k 密度可达，这实际上是直接密度可达的”传播”
- 密度相连：若从某核心点p p p出发，点q q q和点k k k都是密度可达的，则称点q q q和点k k k是密度相连的
- 边界点：属于某一个类的非核心点，不能往下发展了
- 噪声点：不属于任何一个类簇的点，从任何一个核心点出发都是密度不可达的
如图1所示，点A为核心对象，B和C为边界点，N是离群点。
图1 DBSCAN算法划分点集示意图
; 2、工作流程
准备数据集(参数D)，输入指定半径(参数r r r)和密度阈值(M i n P t s MinPts M i n P t s)。其伪代码如下所示：
标记所有对象为unvisited;
Do
随机选择一个unvisited对象p;
标记p为visited;
If p的r-邻域至少有MinPts个对象
创建一个新簇C，并把p添加到C;
令N为p的r-邻域中的对象集合;
For N中每一个点p'
If p'是unvisited;
标记p'为visited;
If p'的r-邻域至少有MinPts个对象
把这些对象添加到N中;
If p'还不是任何簇的成员
把p'添加到C;
End for;
输出C;
Else
标记p为噪声点;
Until 没有标记为unvisited的对象;
3、参数选择
- 半径r r r，可以根据K K K距离来设定，找突变点。
K K K距离：给定数据集P = { p ( i ) ; i = 0 , 1 , ⋯ , n } P={p(i); i=0,1,\cdots,n}P ={p (i );i =0 ,1 ,⋯,n }，计算点p ( i ) p(i)p (i )到集合D D D的子集S S S中所有点之间的距离，距离按照从小到大的顺序排序，d ( k ) d(k)d (k )就被称为K K K距离。 - M i n P t s MinPts M i n P t s：K K K距离中K K K的值，一般取的小一些，多次尝试。
4、优缺点
优点：
① 不需要指定簇个数；② 可以发现任意形状的簇；③ 擅长找到离群点(检测任务)；④ 只需要设置两个参数(半径r r r和距离阈值M i n P t s MinPts M i n P t s)。
缺点：
① 高维数据聚类有些困难(可以做降维)；② 参数难以选择(参数对结果的影响非常大)；③ Sklearn中效率很慢(数据削减策略)。
四、可视化展示
1、K-Means算法
; 2、DBSCAN算法
五、参考文献
[1] 唐宇迪. 跟着迪哥学Python数据分析与机器学习实战[M]. 北京: 人民邮电出版社, 2019: 346-363.
Original: https://blog.csdn.net/weixin_43821559/article/details/122845540
Author: 心️升明月
Title: K-Means算法和DBSCAN算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/550938/
转载文章受原作者版权保护。转载请注明原作者出处！