聚类算法原理
2018-05-19 本文已影响23人
Thinkando
7月算法学习笔记
前言
- 与回归与分类不同，聚类是无监督学习算法，无监督指的是只需要数据，不需要标记结果，自己给自己分类。
- 在现实生活中，很少直接用聚类算法，因为聚类效果的好坏不容易衡量（因为没有标记，就没有标准答案），有时候会用做监督学习中稀疏特征的预处理，把混乱的数据先分分看，看看大类如何~
- 本文会重点介绍K-means聚类、层次聚类和混合高斯模型。
1 聚类算法思想
- 聚类算法的思想：给定N个训练样本(未标记的)x1,x2,...,xN，目标是把比较“接近” 的样本放到一个cluster里， 总共得到K个cluster。没有给定标记，聚类唯一会使用到的信息是样本与样本之间的相似度，聚类就是根据样本相互之间的相似度“抱团” 的。那么怎么评定聚类的好坏呢？-----高类间距，低类内距 （抱团紧不紧，异族远不远）。
-
通常我们用“距离” 衡量样本远近。那距离怎么表示呢？
核函数映射用于线性分不开的聚类
image.png
2 K-means聚类
2.1 K-means聚类算法
-
提出非常早，使用非常频繁的聚类算法
image.png
- 迭代收敛怎么定义呢？
- 是聚类中心不再有变化
-
是每个样本到对应聚类中心的距离之和不再有很大变化。
比如这个样本点要聚成2类，先随机初始化两个中心点。
计算距离，分类：对原始数据中的每个样本点，分别计算到两个中心点的距离，样本点离哪个中心的距离近，就分到相应的类别中
重新计算中心点：把蓝色点的位置的平均值作为蓝色的中心点，同理红色。
迭代：重新计算距离分类，重新计算中心点，直到达到了收敛条件。
2.2 初始化中心的选择
- 初始化中心点没选好，可能掉到局部最优解，那么怎么优化初始化中心呢？
- 初始第一个聚类中心为某个样本点，初始第二个聚类中心为离它最远的点，第三个为离它俩最远的…
-
多初始化几遍，选所有这些聚类中损失函数(到聚类中心和)最小的。
损失函数越低，说明混乱度越低，分类的越好
- 使用优化的初始化聚类方法。例如Arthur 和 Vassilvitskii 提出的Kmeans++，会找最远的一些点初始化。
2.3 K值的选择
-
k-means的输入需要知道聚类个数，对于大量的数据，我们如何知道应该分为几类合理呢？而且k值选的不好确实会出现下面的状况，例如数据实际上划分为2类比较合理，如果硬性的划分为1类，或者3类，就没有很好的效果。
image.png
-
选择方法：“肘点” 法。选取不同的K值，画出损失函数曲线。 这里分析之后可以取k=2，因为2之后的损失函数变化不大。
image.png
2.4 K-means局限性
- 属于“硬聚类” ， 每个样本只能有一个类别。 其他的一些聚类方法(GMM或者模糊K-means允许“软聚类”)。
- K-means对异常点的“免疫力” 很差， 我们可以通过一些调整，比如中心不直接取均值， 而是找均值最近的样本点代替——k-medoids算法。
-
对于团状的数据点集区分度好， 对于带状(环绕)等“非凸”形状不太好。 (用谱聚类或者做特征映射)
image.png
3 层次聚类 （生物信息学常用）
- K-means里面的K太难确定了，有没有不需要指定k的聚类呢？ ---层次聚类
- 层次聚类就是通过对数据集按照某种方法进行层次分解，直到满足某种条件为止。
- 按照分类原理的不同，可以分为凝聚和分裂两种方法。
-
凝聚型：比如有五个样本，先把每一个样本看做一簇，然后选择最近的两个样本归为一簇，得到4个簇，然后4个簇中选两个最近的簇作为一簇，直到所有的样本聚在一起就停止。可以想象整个过程会很慢。 但可以看到每一个基因的聚类细节
image.png
-
那么如何计算cluster 和cluster 的距离呢
image.png
4 K-means VS 层次聚类？
- K-means这种扁平聚类产出一个聚类结果(都是独立的)
- 层次聚类能够根据你的聚类程度不同，有不同的结果
- K-means需要指定聚类个数K，层次聚类不用
- K-means比层次聚类要快一些(通常说来)
5 混高斯模型 （GMM）
- 高斯模型，给定均值和方差，将一个事物分解为基于高斯概率密度函数（正态分布曲线）形成的模型。
-
-但是有时候不是只有一个密集区域，而是多个密集区域，需要多个高斯模型线性加权而成。高斯混合模型就是用高斯概率密度函数（正态分布曲线）精确地量化事物，它是一个将事物分解为若干的基于高斯概率密度函数形成的模型。
image.png
-
那么如何用 GMM 来做 clustering 呢？其实很简单，现在我们有了数据，假定它们是由 GMM 生成出来的，那么我们只要根据数据推出 GMM 的概率分布来就可以了，然后 GMM 的 K 个 Component 实际上就对应了 K 个 cluster 了。根据数据来推算概率密度通常被称作 density estimation，特别地，当我们在已知（或假定）了概率密度函数的形式，而要估计其中的参数的过程被称作“参数估计”。
image.png
比如说要区分这张图
随机指定3个cluster
image.png
image.png
image.png
- GMM的优势：
1. 可理解性好，可看做多个分布的组合
2. 速度快，因为EM这种高效的算法在， 时间复杂度O(tkn)
3. 学术上比较直观，最大数据似然概率
4. 其实可以拓展到多个其他分布的混合，多个多项式分布做类别判定 - GMM的劣势：
1. 初始化要慎重， 不然可能掉到局部最优里去
2. 需要手工指定K(高斯分布)的个数
3. 对于我们提到的“非凸” 分布数据集， 也无能为力
一句话总结GMM：根据当前的参数指定概率分布，根据概率分布重新估计参数。
6. 总结对比
image.png
