kmeans聚类算法matlab_KMeans聚类算法详解 “如果把⼈⼯智能⽐作⼀块⼤蛋糕，监督学习只是上⾯的⼀层奶油“。
⽇常⽣活中，从⼈脸识别、语⾳识别到搜索引擎，我们看到越来越多⼈⼯智能领域的算法逐渐⾛向落地。尽管全球每⽇新增数据量以PB或EB级别增长，但是⼤部分数据属于⽆标注甚⾄⾮结构化。所以相对于监督学习，不需要标注的⽆监督学习蕴含了巨⼤的潜⼒与价值。 聚类算法KMeans是⽆监督学习的杰出代表之⼀。本⽂是记录⾃⼰过去学习KMeans算法的系统⼩结，将从“KMeans简介，优缺点与优化策略，结合EM算法解释KMeans以及⼿推KMeans”⼏个⽅⾯来尽可能彻底、清晰地搞明⽩这个算法，希望对⼤家能有所帮助。
⼀、聚类与KMeans
与分类、序列标注等任务不同，聚类是在事先并不知道任何样本标签的情况下，通过数据之间的内在关系把样本划分为若⼲类别，使得同类别样本之间的相似度⾼，不同类别之间的样本相似度低（即增⼤类内聚，减少类间距）。
聚类属于⾮监督学习，K均值聚类是最基础常⽤的聚类算法。它的基本思想是，通过迭代寻K个簇（Cluster）的⼀种划分⽅案，使得聚类结果对应的损失函数最⼩。其中，损失函数可以定义为各个样本距离所属簇中⼼点的误差平⽅和：
其中
代表第
个样本，
是
所属的簇，
代表簇对应的中⼼点，
是样本总数。
⼆、具体步骤
KMeans的核⼼⽬标是将给定的数据集划分成K个簇（K是超参），并给出每个样本数据对应的中⼼点。具体步骤⾮常简单，可以分为4步：
（1）数据预处理。主要是标准化、异常点过滤。
（2）随机选取K个中⼼，记为
（3）定义损失函数：
（4）令t=0,1,2,... 为迭代步数，重复如下过程知道
收敛：
（4.1）对于每⼀个样本
实验室自动清洗机，将其分配到距离最近的中⼼
（4.2）对于每⼀个类中⼼k，重新计算该类的中⼼
KMeans最核⼼的部分就是先固定中⼼点，调整每个样本所属的类别来减少
；再固定每个样本的类别，调整中⼼点继续减⼩
。两个过程交替循环，
单调递减直到最（极）⼩值，中⼼点和样本划分的类别同时收敛。
KMeans迭代⽰意图
三、优缺点与优化⽅法
KMenas的优点：
⾼效可伸缩，计算复杂度 为
接近于线性（N是数据量，K是聚类总数，t是迭代轮数）。
收敛速度快，原理相对通俗易懂，可解释性强。
KMeans也有⼀些明显的缺点：
受初始值和异常点影响，聚类结果可能不是全局最优⽽是局部最优。
K是超参数，⼀般需要按经验选择
样本点只能划分到单⼀的类中
根据以上特点，我们可以从下⾯⼏个⾓度对算法做调优。
1. 数据预处理：归⼀化和异常点过滤
KMeans本质上是⼀种基于欧式距离度量的数据划分⽅法，均值和⽅差⼤的维度将对数据的聚类结果产⽣决定性影响。所以在聚类KMeans本质上是⼀种基于欧式距离度量的数据划分⽅法，均值和⽅差⼤的维度将对数据的聚类结果产⽣决定性影响。
中⼼偏移，这具体的说是每⼀个维度的特征）做归⼀化和单位统⼀⾄关重要。此外，异常值会对均值
计算产⽣较⼤影响，导致中⼼偏移
前对数据（具体的说是每⼀个维度的特征
些噪声点最好能提前过滤。
2.合理选择K值
拐点就是K的K值的选择⼀般基于实验和多次实验结果。例如采⽤⼿肘法
火麻仁胶囊
⼿肘法，尝试不同K值并将对应的损失函数画成折线。⼿肘法认为图上的拐点就是K的最佳值（上图对应K=3）。
最佳值
⼿肘法
Gap Statistic⽅法。它的有点是我们不再需要⾁眼判断，只需要到最⼤的Gap
为了将寻最佳K值的过程⾃动化，研究⼈员提出了Gap Statistic⽅法
Statistic对应的K即可。
沿⽤第⼀节中损失函数记为
，当分为K类时，Gap Statistic定义为：
。
是
的期望，⼀般由蒙特卡洛模拟产⽣。我们在样本所在的区域内按照均匀分布随机地产⽣和原始样本数⼀样多的随机样本，并对这个随机样
本做KMeans，得到⼀个
，重复多次就可以计算出
的近似值。
的物理含义是随机样本的损失与实际样本的损失之差。Gap越⼤说明聚类的效果越好
。⼀种极端情况是，随着K的变化
⼏乎维持⼀条直线保持不变。说明这些样本间没有明显的类别关系，数据分布⼏乎和均匀分布⼀致，近似随机。此时做聚类没有意义。
3.改进初始值的选择
让之前我们采取随机选择K个中⼼的做法，可能导致不同的中⼼点距离很近，就需要更多的迭代次数才能收敛。如果在选择初始中⼼点时能让不同的中⼼尽可能远离，效果往往更好。这类算法中，以K-Means++算法最具影响⼒。
不同的中⼼尽可能远离
4.采⽤核函数
主要思想是通过⼀个⾮线性映射，将输⼊空间中的数据点映射到⾼位的特征空间中，并在新的空间进
⾏聚类。⾮线性映射增加了数据点线性可分的概率（与SVM中使⽤核函数思想类似）对于⾮凸的数据分布可以达到更为准确的聚类结果。
四、从EM算法解释KMeans
EM（Expectation-Maximum）算法即期望最⼤化算法，是最常见的隐变量估计⽅法。EM算法是⼀种迭代优化策略，每⼀次迭代都分为两
EM算法的提出最初是为了解决数据缺失情况下的参数估计问题，基本思想是⾸先根据已有的观测数步：期望步（E）、极⼤步（M）。EM算法的提出最初是为了解决数据缺失情况下的参数估计问题
据，通过极⼤似然估计估计出模型的参数；再根据上⼀步估计出的参数值估计缺失数据的值；最后根据估计出的缺失数据和原有的观测数据重新对参数值进⾏估计，反复迭代直到收敛。
EM算法基础和收敛有效性等问题可以参考Dempster、Laird和Rubin三⼈于1977年所做的⽂章《Maximum likelihood from incomplete data via the EM algorithm》。
KMeans算法等价于⽤EM算法求解以下含隐变量的最⼤似然问题：
其中
是模型的隐变量，可以理解为当样本
离第
面包炉个类的中⼼点
距离最近是，概率正⽐于
，否则为0。
在E步骤，计算：
等同于在KMeans中对于每⼀个点
到离当前最近的类
。
在M步骤，到最优的参数
，使得似然函数最⼤（假设
对应的分布为
莫氏变径套，且满⾜
）：
经推导得：
这⼀步等价于到最优的中⼼点
，使得损失函数
伸缩式雨棚达到最⼩。此时每个样本
对应的类
已确定，每个类
对应的最优中⼼点
可以由该类所有点取平均值得到。这与KMeans算法中根据当前类的分配更新聚类中⼼的步骤等同。
五、⼿推KMeans
最后，为⼤家提供⼀个pyTorch⼿推实现KMeans的代码（通过sklearn包也能⽅便调⽤），结合理论梳理⼀遍具体实现，相信可以理解的更为扎实。
⼩结漏洞修复失败
KMeans作为⼀种⽆监督聚类算法，在⽇常⽣活中有⼤量应⽤。经过适当的预处理，可以对数据做初步分析，甚⾄挖掘出隐含的价值信息（例如对⽤户⽇志做聚类，得到⼀些⾼频⾼质量的新FAQ）。相⽐于SVM、GBDT等机器学习算法，理解起来相对通俗易懂，实乃实在⼜实⽤。
Reference：
1.《百⾯机器学习》5.1 K均值聚类：P92-P101
2.EM算法详解
3.⼿推KMeans
