机器学习之聚类算法的原理推导及相关知识总结

朱雀 2022-05-12 07:10 261阅读 0赞

### 文章目录 ###

*  1、知道几个关于"差"的概念
 *  2、理解相似度度量的各种方法和相互关系
 *   *  2.1、欧氏距离
     *  2.2、jaccard相似系数
     *  2.3、余弦相似度
     *  2.4、Pearson相似系数
     *  2.5、相对熵
 *  3、掌握掌握K-Means算法
 *   *  3.1、知道聚类的思想
     *  3.2、K-Means算法原理
     *  3.3、知道K-Mediods聚类
     *  3.4、如何选取K-means的初始值
     *  3.5、K-means的目标函数
 *  4、知道聚类的衡量效果的指标
 *  5、了解层次聚类的思路和方法
 *  6、理解密度聚类
 *  7、掌握谱聚类的算法
 *   *  7.1、了解谱（方阵的全体特征值称为方阵的谱）以及谱半径（最大的特征值称为谱半径）
     *  7.2、几个概念
     *  di代表行列式的第i行的累加值。 邻接矩阵W（又称为相似矩阵）又为对称矩阵（Wij与Wji的值相等即i、j的距离相等），主对角线的值取0 !\[这里写图片描述\](/images/20220512/613a969442854857a400e8b57feb89bf.png) 7.2、了解谱分析的整体的过程
     *  7.3、其他谱聚类算法
 *  8、知道拉布拉斯矩阵
 *  9、知道标签传递算法

# 1、知道几个关于"差"的概念 #

均值、方差、标准差、协方差：  
![这里写图片描述][70]  
协方差就是这样一种用来度量两个随机变量关系的统计量，我们可以仿照方差的定义：  
![这里写图片描述][70 1]

# 2、理解相似度度量的各种方法和相互关系 #

![这里写图片描述][70 2]

## 2.1、欧氏距离 ##

**欧氏距离**：p=2（又称为第二范式）。曼哈顿距离：p=1（又称为第一范式,p为多少也就为第几范式）。

## 2.2、jaccard相似系数 ##

用于比较有限样本集之间的相似性与差异性。Jaccard系数值越大，样本相似度越高。

## 2.3、余弦相似度 ##

![这里写图片描述][70 3]

## 2.4、Pearson相似系数 ##

两个变量之间的协方差和标准差的商。  
![这里写图片描述][70 4]

*  当两个变量的线性关系增强时，相关系数趋于1或-1；
 *  当一个变量增大，另一个变量也增大时，表明它们之间是正相关的，相关系数大于0；
 *  如果一个变量增大，另一个变量却减小，表明它们之间是负相关的，相关系数小于0；
 *  如果相关系数等于0，表明它们之间不存在线性相关关系。

## 2.5、相对熵 ##

又称为KL散度（Kullback–Leibler divergence，简称KLD）\[1\]，信息散度（information divergence），**信息增益（information gain）**。

**余弦相似度与Pearson相似系数之间的关系**  
![这里写图片描述][70 5]

# 3、掌握掌握K-Means算法 #

## 3.1、知道聚类的思想 ##

先做一个初始的划分之后通过迭代来改变样本和簇之间的隶属关系。  
![这里写图片描述][70 6]

## 3.2、K-Means算法原理 ##

1、选取初始的K个类别中心数据（可以自定义也可以随机选取K个样本）  
2、对于每个样本将其标记为距离类别中心最近的类别（对样本进行聚类处理）。  
3、将每个类别中心更新为隶属于该类别的所有样本的均值。  
4、重复2、3直到类别中心的变化小于某阈值（迭代次数/簇中心变化率/最小平方误差MSE）  
![这里写图片描述][70 7]

## 3.3、知道K-Mediods聚类 ##

类别中心的更新依据从数据的均值改为中位数。  
![这里写图片描述][70 8]

## 3.4、如何选取K-means的初始值 ##

首先，知道K-means是初值敏感的（K的输入很关键），也就是每个类别中初始值的选择是很关键的。那么如何有效的选取K-Means的初始值？  
得到第一个初始值后求其他点到该初始值的距离时将距离初始值较远的点作为簇点的概率大些，这样就可以得到较好的初始簇点。  
![这里写图片描述][70 9]

## 3.5、K-means的目标函数 ##

目标函数：求每个簇的样本点到每个簇中心的距离的加和；求导后就相当于将周围点的平均值付给μ作为新的簇中心。  
![这里写图片描述][70 10]

# 4、知道聚类的衡量效果的指标 #

均一性和完整性就类似于之前半监督中的准确率和召回率  
V-measure：均一性和完整性的加权平均  
![这里写图片描述][70 11]  
了解这个轮廓系数（衡量分类好坏的指标）：  
先了解上面的簇内不相似系数ai（越小越好）：簇内的样本点i到簇内其他样本点平均距离。  
![这里写图片描述][70 12]  
簇间不相似系数bi（越大越好）：样本i到某簇的所有样本的平均距离。  
轮廓系数含义见下图  
![这里写图片描述][70 13]

# 5、了解层次聚类的思路和方法 #

知道这两个算法AGNES和DIANA  
![这里写图片描述][70 14]  
![这里写图片描述][70 15]  
![这里写图片描述][70 16]

# 6、理解密度聚类 #

![这里写图片描述][70 17]  
了解DBSCAN算法：  
算法原理：  
1、如果点p的邻域包含多于m个对象，则创建一个p作为核心对象的新簇。  
2、寻找并合并核心对象周围直接密度可达的对象  
3、没有新点可以更新簇时，算法结束。  
![这里写图片描述][70 18]

# 7、掌握谱聚类的算法 #

## 7.1、了解谱（方阵的全体特征值称为方阵的谱）以及谱半径（最大的特征值称为谱半径） ##

![这里写图片描述][70 19]

## 7.2、几个概念 ##

## di代表行列式的第i行的累加值。   邻接矩阵W（又称为相似矩阵）又为对称矩阵（Wij与Wji的值相等即i、j的距离相等），主对角线的值取0   ![这里写图片描述][70 20]   7.2、了解谱分析的整体的过程 ##

任意两个点之间的相似度可以用径向量机函数来求（也就是两点之间的距离）  
![这里写图片描述][70 21]  
过程：  
1、由度矩阵D和邻接矩阵W得到对应的L（拉普拉斯矩阵）的特征值行列式。  
2、特征值值行列式中的每个λ代表的一个列向量  
3、分成K个类别也就是取前K个特征值，如下图所示。  
4、特征值行列式的行向量的第i行也就代表第i个样本的特征表示  
5、有了m个样本的特征表示就可以利用K-Means来进行聚类处理。

## 7.3、其他谱聚类算法 ##

不同的谱聚类算法只是对应的拉普拉斯矩阵改变了，其他的步骤都没变。  
![这里写图片描述][70 22]

# 8、知道拉布拉斯矩阵 #

![这里写图片描述][70 23]  
![这里写图片描述][70 24]

# 9、知道标签传递算法 #

![这里写图片描述][70 25]

[70]: /images/20220512/92e31b22777749b397136ea8f40a5967.png
[70 1]: /images/20220512/e7d9964487bc4605ab39c53954b31104.png
[70 2]: /images/20220512/30932a5cf9404bafbba74abda587d006.png
[70 3]: /images/20220512/20cf567caf9644608fe2d4db4ca71e85.png
[70 4]: /images/20220512/2bf481d8aee64c12b84c707cebb062c7.png
[70 5]: /images/20220512/518e37e8a6ab42a8b7706770412ee1a5.png
[70 6]: /images/20220512/e972df7f99cd4c25ae9c7ddc47ba2c6e.png
[70 7]: /images/20220512/463cb078b58146aa84b3c5f8e6494cc6.png
[70 8]: /images/20220512/fe146e1f54cf49bbb0b868191640a193.png
[70 9]: /images/20220512/7b87228ef92645d38d65f80ebcea63f5.png
[70 10]: /images/20220512/10851b15c38941dbb6a8d9f03c24836a.png
[70 11]: /images/20220512/28450fb3597c43398c48f6a3bc895bc0.png
[70 12]: /images/20220512/7001e78bf88f4a1080f7c115f7a92d9f.png
[70 13]: /images/20220512/39670e8220304f83ad524d1256e53733.png
[70 14]: /images/20220512/eae37175b59846d797f72b7dca618ea1.png
[70 15]: /images/20220512/66c4261ffbf945329506e674db3046a7.png
[70 16]: /images/20220512/4501ff1cb39f47e3af7e51ac1db93ce3.png
[70 17]: /images/20220512/009d7e54018c4dfa8cda8dce37ece935.png
[70 18]: /images/20220512/4fe69e1bc1c842ccb1b75ef1f55e2a6e.png
[70 19]: /images/20220512/543c9b1892ef4376b655fb6e9e4f673e.png
[70 20]: /images/20220512/613a969442854857a400e8b57feb89bf.png
[70 21]: /images/20220512/9932543b7de640708165a3a9119737e6.png
[70 22]: /images/20220512/1a98e745504b4f358afc8e6b8b09d983.png
[70 23]: /images/20220512/3b5e08aa64424e54a92d844469d34f09.png
[70 24]: /images/20220512/f2f9b9589e6b4535ba5b64d39a76e55d.png
[70 25]: /images/20220512/35b511ad368646e18b12e0301299a81b.png