项目地址：https://github.com/Daya-Jin/ML_for_learner/blob/master/cluster/KMeans.ipynb
原博客：https://daya-jin.github.io/2018/09/22/KMeans/
算法概述
K-Means算法是一种无监督分类算法，假设有无标签数据集：
该算法的任务是将数据集聚类成个簇
，最小化损失函数为：
其中为簇
的中心点：
要找到以上问题的最优解需要遍历所有可能的簇划分，K-Mmeans算法使用贪心策略求得一个近似解，具体步骤如下：
- 在样本中随机选取
个样本点充当各个簇的中心点
- 计算所有样本点与各个簇中心之间的距离
，然后把样本点划入最近的簇中
- 根据簇中已有的样本点，重新计算簇中心
- 重复2、3
改进
K-means算法得到的聚类结果严重依赖与初始簇中心的选择，如果初始簇中心选择不好，就会陷入局部最优解，如下图：
避免这种情况的简单方法是重复多次运行K-means算法，然后取一个平均结果。
另一种更精妙的方法是K-means++，它改进了K-means算法初始中心点的选取，改进后的选取流程如下：
- 在数据集中随机选取一个样本点作为第一个簇中心
- 计算剩余样本点与所有簇中心的最短距离，令为
，某样本点被选为下一个簇中心的概率为
- 重复2直到选出
个簇中心
可以看出K-means++算法的思想很简单明了，初始簇中心之间的距离应该越大越好。
标签数据
K-means算法还可用于带标签的数据，在这种情况下，K-means会对每一个类别做单独的聚类。如某数据集可分为个类别，那么K-means算法会将每一个类别看做是一个单独的数据集进行聚类操作。但是在不同类的数据有重叠的情况下，类内的聚类簇也会出现重叠现象，这是因为不同类之间的内部聚类是完全独立的，这样就造成类边界处的点极易被误分。下图就是对有三个类别(绿、黄、蓝)的数据做5-means聚类，黑圆点表示的是类内簇中心，紫色虚线表示的是贝叶斯分类边界。
为了改进K-means在有标签数据及上的表现，有一种算法叫学习矢量量化(Learning Vector Quantization)能够利用标签信息来辅助聚类。核心思想是同类别的样本点会吸引簇中心，而不同类别的样本点会排斥簇中心，具体算法如下所示：
- 在每一个类别中都随机选取
个簇中心：
,
,
,
，
- 在所有数据中有放回地随机选取一个样本点
，在所有簇中心中计算找出与
，按照如下规则来移动簇中心
- 如果
- 如果
- 如果
- 重复2直到各簇中心不再变化或满足某种条件
LVQ算法中的为学习率，它会随着迭代次数而衰减至0。在同样的数据上应用LVQ的聚类结果如下：
