首页 > Python机器学习 阅读数:27

k均值聚类算法的工作流程

k 均值聚类算法的工作流程是这样的:首先选取 k 个点,作为初始 k 个簇的中心(这个 k 是人为设定的超参数),然后将其余的数据对象分配到距离自己最近的簇中心所在的簇中。假设样本集中有 l 个样本,每个样本都是一个具备 n 个特征,用向量 xi 表示第 i 个样本。现在我们假设要把所有样本划分为 k 个簇,即:

S={S1, S2, ......, SK}

这里 Sl(1≤l≤k) 表示第 l 个簇,S 是由若干簇构成的簇集合。

那么,最优的分配方案就是优化如下目标函数的解:


其中,μi 簇中的均值向量,有的文献也称之为质心(centroid),共有 k 个,因此这个算法叫作 k 均值聚类算法。由于以上公式所示的组合优化问题是一个 NP 难题,通常难以求得最优解,只能求得近似解。因此在实现过程中,通常采用循环迭代的方式,逐步收敛到局部最优解处。

当所有的点均被划分到某一个簇后,要再对各个簇中心(μi)进行更新。更新的依据是,根据每个聚类对象的均值,计算每个对象到簇中心的距离最小值,直到满足一定的条件才停止计算。这个条件一般为函数收敛(比如前后两次迭代的簇中心足够接近)或计算达到一定的迭代次数。

k 均值聚类算法的过程如图 1 所示。

k均值聚类算法的过程
图 1:k 均值聚类算法的过程

在 k 均值聚类算法中,我们主要需要考虑两个关键问题:初始簇中心(也称质心)的选取及距离的度量。常见的选取初始簇中心的方法是随机挑选 k 个点,但这样形成的簇质量往往很差。

因此,我们采用其他常用方法挑选初始簇中心,具体如下:
  • 多次运行调优。每次使用一组不同的随机初始簇中心,最后从中选取具有最小平方误差的簇集。这种方法简单,但效果难料,主要取决于数据集的大小和簇的个数k;
  • 根据先验知识(即历史经验)来决定 k 值。

对于另一个因素—如何确定对象之间的距离,根据问题场景不同,度量方式也是不同的。在欧式空间中,我们可以通过欧氏距离来度量两个样本之间的距离,而对于非欧式空间,可以选择 Jaccard 距离、Cosine 距离或 Edit 距离等度量方式。