聚类K-means算法

概述 机器学习里面的聚类是无监督的学习问题，它的目标是为了感知样本间的相似度进行类别归纳。它可以用于潜在类别的预测以及数据压缩上去。潜在类别预测，比如说可以基于通过某些常听的音乐而将用户进行不同的分类。数据压缩则是指将样本进行归类后，就可以用比较少的的One-hot向量来代替原来的特别长的向量。

聚类，既可以作为一个单独的过程，也可以作为其他机器学习任务的预处理模块。 其实，在深度学习里面就十分流行这种先给样本聚类 压缩数据，然后把在压缩后的特征向量丢到网络去训练，这其实就是深度学习里面的“表示学习”的最初想法。基于这类的深度学习模型如 受限的玻尔兹曼机等。 当然，本章我们介绍的都是传统机器学习使用的聚类方法。

聚类算法的种类 聚类算法主要有：

1. 序贯法
2. 层次分析法
3. 基于损失函数最优化的：K-means,概率聚类
4. 基于密度的聚类
5. 其他特殊聚类方法：基因聚类算法，分治限界聚类算法；子空间聚类算法；基于核的聚类方法。

聚类问题的表述 给定一个包含n个样本的样本集X = { x1 , x2 , … , xn } ,要给对这n个样本给定一个划分方式，将这些样本划分为m类C1 , C2 , C3 , … , Cm，这里每一个类可以称为簇。使得满足

在这里插入图片描述

虽然 聚类看起来是很棒的，可以进行“物以类分，人以类聚”，但是聚类确守很多方面的影响。 例如： 1.特征选择不同，导致不同的结果 2.相似度度量不同，导致不同的结果 3.聚类的方法不同，导致不同的结果 更要命的是，聚类其实没有啥好的评判标准的，尤其是对于那些本来就没有正确结果的数据来说。这是为什么呢？ 因为就算是人给样本聚类，也是基于某个方面的聚类，而机器学习得到的聚类可能是基于另外一种角度来聚类，咋一眼看上去 机器聚类的结果很差，其实很有可能是它关注了某个人类不去关注的方面。例如说把左边的图形进行聚类：

在这里插入图片描述

人类可能给出，右边第一种聚类是正确的聚类，那是因为人类关注的是形状。可是机器给出的第二类，第三类 也是合理的，并不能一棒子打死。

相似度度量 既然，聚类是为了感知样本间的相似度，把相似的样本聚类在一起，那么我们首先就得定义好样本之间的相似度。 注意，这里的样本相似度其实就是指样本和样本之间的距离，而样本是以特征向量的形式给出的，所以其实我们是需要定义样本特征向量之间的距离、样本与类别之间的距离、类别与类别之间的距离、类别内部的距离。

样本与样本之间的距离

给定两个样本的特征向量：

，这里

表示n维空间，常用的样本间的距离有：

1. p范数：

这里指的是明可夫斯基距离

1. cos范数:

这里指的是向量空间余弦相似度

1. 皮尔森范数：

，其中

都是各个元素减去它们的均值。

样本到类别之间的距离

样本到类别之间的距离，其实就是样本到集合的距离。 一般当集合为离散点集的时候： 样本到类别之间的距离可以定义为：

1. 到集合最远点的距离

1. 到集合最近点的距离

1. 到集合平均点的距离

当集合为连续区域的时候，也可以定义类似的最近距离以及平均距离，但是一般不定义最远距离，除非区域是封闭的，否则最远距离无意义。

类别之间的距离

类别之间的距离，就是集合到集合的距离，衡量一个集合到另外一个集合的距离程度。 一般有如下定义：

1. 集合间最远点距离：

1. 集合间最近点距离：

1. 集合间所有点的平均距离：

1. 表征点距离:

其中的u uu表示各类的表征点，可以是类的平均点。

类内距离

这个距离，主要是衡量一个类别内的样本的离散程度。一般有如下定义： 类内的平均距离：所有样本点之间的距离的和的平均

,其实就是遍历所有的组合，共

种组合，然后计算各个组合下的距离,求和再求平均。 类别最大样本距离：所有样本点之间距离的最大值

K-means算法

K-means算法是一种无监督的聚类算法，核心目标：将给定的数据划分成K个簇，并且给出每个簇的中心点，即质心。

这里的有监督、无监督指的是数据是否有无标签，有标签的就是有监督学习，无标签的就是无监督学习。这里的质心可以理解成图中的这些红点

而图中的左上角的label0、label1、label2是我们完成了整个K-means算法后得到的一个标签，我们事先是不知道的。在未进行K-means前这些数据是没有颜色区分的。这里K-means算法把这些数据分成了三个簇。

假设我们这里有8个数据点，先随便选三个点作为质心，然后计算其他点到三个质心点的距离，我们这里使用的是明可夫斯基的欧拉距离，根据每个点到三个质心的距离最近的原则，将这些点分成三个簇。

K-means算法的具体步骤

1. 数据预处理：剔除离群点、数据归一化、数据标准化
2. 初始化：随机选择K个中心点

，这里μ右上角的0表示迭代次数，因为是初始化，所以为0

1. 定义损失函数：

，这里就是求每一个样本点到各个中心点的最小欧拉距离。第一个求和

指的是每一个样本点到第i个质心的距离，第二个求和

指的是一共有K个簇，样本点到所有簇的质心的距离都要求和。

1. t为迭代步数，重复下面两步过程，至J收敛
   1. 对于每个样本点，将其分配到距离最近的簇

   

   1. 对于每一个簇，重新计算聚类质心

   

   ，这里x为每一个簇的所有样本点，

   

   表示该簇内样本点的个数。

   

   为新质心。

实际上损失函数

是和第4步的两个步骤交替迭代所对应的。

K-means算法性能分析

• K-means算法的缺点

1. 需要人工选择K值，未必符合真实数据分布。当我们拿到数据点后需要我们自己来决定需要分成几个类别。
2. 受初始值和离群点的影响较为严重，稳定性较差。如果我们选择的初始值正好就选择了聚类中心上，那么迭代一次就可以收敛了；但如果我们选择的初始值离聚类中心非常的远，就需要多次迭代，每次迭代都往最后真实的聚类中心上拉近，所以说不同的初始值对应着不同的迭代轮数。这就是不稳定的原因。
3. 通常结果并非全局最优，而是局部最优。

• K-means算法的优点

1. 对于大数据集，算法时间复杂度为线性O(NKT)，这里N为样本点个数；K为聚类中心个数；T为迭代轮数。
2. 局部最优解通常可以满足问题需要。

K-means算法调优过程

• K值选择(手肘法)

这张图的横坐标表示聚类个数K,纵坐标表示均方误差和J。对这条曲线来说，假设我们有10个样本点，那么我们如果分成10个类的话，那么很明显J=0，这是我们把所有的样本都各自分成了一个类，每一个样本到各自的聚类中心的距离为0，那么全部的0加和依然为0。我们如果只分成1个类的话，那么很明显J为最大值，表示所有样本点都到一个聚类中心距离的平方和。我们知道这是一个递降的曲线，在这个时候，我们该如何选择K，这个曲线就像我们的胳膊肘一样，这个曲线的拐点，就像我们胳膊的拐点，也就是胳膊肘这个地方，在这张图上K=4，在K=4的时候，我们认为这是一个比较合适，比较恰当的一个选择。

K-means算法的改进

1. 改进点：对初始值的选择进行优化，采用K-means++算法
2. 改进思想：选择第n+1个聚类中心时，距离其他聚类中心越远，被选中的概率越大。

假如我们要把样本数据聚成5个类别，那么第一个聚类中心是可以随便选的。当选择第二个聚类中心的时候，就要离第一个聚类中心尽可能的远。当选择第三个聚类中心的时候，要保证离前两个聚类中心尽可能的远。之后以此类推。