系列文章目录

第一章 Python 机器学习入门之线性回归

前言

学完K近邻算法，让我们再来看看和它有一定相似程度的K-Means聚类算法

一、K-Means简介

1、定义

wiki定义：
k-均值算法（英文：k-means clustering）源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-均值聚类的目的是：把n个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。

这里说下聚类和簇的概念，使用上述算法会把训练中的数据划分成若干个组，每个组就被称为簇，而这种学习方式或者说分类过程就被称为聚类；但是很多资料上往往也会把聚类视作簇，就如上述定义一样。

2、例子

简单来说，K聚类的核心点是找到K个中心点，以此为中心辐射开来，形成K个簇；

举个例子，有些大学在入学时会让学生填写一些个人作息和兴趣爱好来做宿舍分配，其中就可以使用K-Means聚类算法，假设要分配K个宿舍，我们可以先随机出K个学生，然后在此基础上分配剩下的学生，剩下的学生找到与自己个人作息和兴趣爱好相近的K个学生之一；最后我们就可以得到一个相对较好的宿舍环境，熬夜打游戏的可以一起组团开黑，早起学习的可以一起携手前去图书馆，大家都获得了美好的未来。

3、K-Means与KNN

前言里提到K-Means和KNN有一定相似程度，这是因为二者在运行过程中都用到了最近邻思想，都是找到离某个点最近的点；但是它们不能统一而论，这是它们的区别点

1. KNN是有监督学习，是有对应的类别输出的；K-Means是无监督学习，没有样本输出
2. KNN是找离当前点最近的K个点，K-Means是找离当前点最近的K个中心点之一

二、 K-Means实现

1、步骤

1. 选取初始化的k个样本设为聚类中心a=a1,a2,a3…ak;

2. 对于数据集的每个数据点Xi，计算它到k个聚类中心的距离（这里通常采用我们在上一篇k近邻中提到的欧式距离来计算），然后将它分到距离最小的聚类中心所对应的簇中；

3. 针对每个聚类中心aj,当有新的样本加入时，重新计算它的质心（中心点）
   

4. 重复上述2、3步直至达到终止条件

2、优化

2.1 初始化优化之K-Means++

传统K-Means是随机选择中心点，这样有很大概率会花费更多的时间，因此在选择初始点上我们可以使用更好的方法，那就是K-Means++;

相比于传统K-Means，K-Means在选择新的初始点时都会参考之前选取得初始点，因为我们知道最后得出的结果是K个簇，我们希望每个簇之间的距离越远越好，而这点就可以应用到初始点选择上，我们在选择新的初始点希望找到离之前的初始点越远越好；

步骤：

1. 随机选择一个初始点a1
2. 对于数据集中每一个点Xi，计算它到之前每个聚类中心aj的距离D(xi)，找到距离最大的那个，但是这只适用于单个距离中心的情况；当面对多个聚类中心，我们使用概率的方式（下式）来找到最可能距离前j个聚类中心最远的点
   
3. 重复第二步直至找到K个聚类中心

2.2 距离优化之elkan K-Means

传统K-Means中，每次迭代都需要计算机所有样本到所有质心的位置，这样运行时间过长；elkan K-Means算法则是对这一步进行改进，减少不必要的距离的计算；它主要的使用的思想是：利用两边之和大于等于第三边，两边之差小于第三边的三角形的性质，因此达到减少距离计算的目的。

1. 对于一个样本点x和两个质心a1,a2;我们先计算出这两个质心的距离D(a1,a2)，如果2D(a1,x)<=D(a1,a2)，那么D(a2,x)>=D(a1,x)，就可以不计算D(a2,x)，减少一步计算距离
2. 对于一个样本点x和两个质心a1,a2，我们可以得到D(a2,x)>=max(0,D(a1,x)-D(a1,a2))

第二条规律其实有点难懂，我查阅了下资料，大概是说利用两边之差小于第三边推导出来，然后在此基础上来利用该公式能判断是否可以不用计算D(a2,x)

该方法可以一定程度上提升传统K-Means聚类算法的迭代速度，但是如果样本的特征是稀疏的，并具有缺失值，由于有些距离无法计算，则无法使用该算法。

三、优缺点

1、优点

1. 简单易懂，算法收敛速度快
2. 算法的可解释性强

2、缺点

1. k值的选取一般需要先验经验（专家经验）
2. 采用迭代的方法，得到的结果只是局部最优
3. 由于需要计算质心到所有点的距离，对噪音和异常点比较敏感
4. 如果各隐含类别的数据量严重失衡，或者个各隐含类别的方差不同，则聚类效果不佳