K-means算法原理与Python实现

简介

K-means算法又叫K-均值算法，是非监督学习中的聚类算法。

基本思想

在K-means算法中，用cluster来表示簇，K-means算法收敛等同于所有质心不再发生变化。基本的k-means算法流程如下：

选取k个初始质心（作为初始cluster，每个初始cluster只包含一个点）；
repeat:
 对每个样本点，计算得到距离其最近的质心，将其类别标为该质心所对应的cluster；
 重新计算k个cluster对应的质心（质心是cluster中样本点的均值）；
util 质心不再发生变化 或 到达最大迭代次数

K-means的本质是移动中心点，使其逐渐靠近数据“中心”，即最小化目标函数，目标函数为每个点到其簇质心的距离平方和：

目标函数

其中，N是元素个数，x表示元素，c(j)表示第j簇的质心。

优缺点

优点

• 简单、快速；
• 对大数据集有较高的效率并且是可伸缩性的；
• 时间复杂度接近于线性，适合挖掘大规模数据集。

缺点

• 只是局部最优，因而对初始质心的选取很敏感；
• 选择能达到目标函数最优的K值是非常困难的。

Python实现

首先，我们需要编写几个辅助函数：

• 加载测试数据集

加载测试数据集

• 计算欧拉距离（这里选取欧拉距离作为距离计算公式）

计算欧拉距离

• 初始化k个随机簇心

初始化k个随机簇心

有了以上辅助函数后，我们就可以根据K-means的基本思想与算法步骤实现K-means算法了。

K-means核心算法

至此，K-means算法的Python实现就已经完成了。我们可以加载一组测试数据，指定簇心个数，使用K-means算法进行聚类。

随机初始化

由于初始化的中心点对于最后的分类结果影响很大，因而很容易出现：当初始化的中心点不同时，其结果可能千差万别。因此为了分类结果更加合理，我们可以多次初始化中心点，即多次运行K-means算法，然后取Cost最小的分类结果。

二分K-means

为了克服K-means算法收敛域局部最小值的问题（对初始簇心的位置敏感），二分K-means出现了。该算法首先将所有点归于一个簇，然后将其一分为二。之后选择其中一个簇继续一分为二。选择的依据就是：该簇的划分是否可以最大程度降低SSE（误差平方和）的值。上述基于SSE的划分过程不断重复，直至簇数达到k为止。

将所有点看成一个簇
当簇数目小于k时:
 对于每一个簇:
 计算总误差
 在给定的簇上面进行K-means聚类（k=2）
 计算将该簇一分为二之后的总误差
 选择使得误差最小的那个簇进行划分操作

K的选择

• Elbow method

假设随着K的增大，cost function j的大小呈现以下形状：

cost function j

可以看到，当K=3时，J已经很小了，再增大K并不能大大减小J。说明此时K=3比较合适。

但是，以上情况并不常见，更一般的情况是：

更一般的cost function j

此时根本看不出哪里才是”手肘“，所以对此只能实践调研，按实际需求而定。