第 2 章 k-均值

基本算法

k-均值示例

k-均值算法的局限性

k-均值是最广为人知的用于聚类分析的方法，也是数据挖掘发展史上最成功的算法之一。在通常的教科书和文献中，它是以英文名字 k-means 出现的，老一辈的计算机学者往往称其为 Lloyd 算法或者 Lloyd-Forgy 算法——为了纪念提出 k-均值算法的科学家^[6][7] 。

因为 k-均值是处理聚类问题的，所以我们先在 1.4 节的基础上，把聚类问题是什么说得更清楚一些。

假设有 N 个对象，不妨记为，每个对象用 d 个特征（维度）来描述。正如第 1 章所举的例子，要做聚类分析的可能是运营商，对象就是手机的用户，特征有 3 个（d=3），分别是手机用户每个月平均语音时长、网络流量和付费订阅总费用。运营商的目的是，分析用户使用手机的行为是否与他们设计的套餐相匹配，是否自行聚集成若干有代表性的簇，有没有更好的套餐方案等。

当然，真实的情况要更复杂，数据的维度 d 一般远大于 3。考虑最简单也是 最常见的一种情况，就是这 d 维数据的每个维度都可以用一个实数来表示，所 以我们可以直接认为 是一个定义在实数域上的 d 维向量。

例如，用户 i 每月打了 12345 s 电话，用了 788.93 MB 流量，付费订阅花了12.50 元，那么这个用户可以表示为三维实空间中的一个数据点

聚类算法就是将上面 N 个对象划分成多个簇（或称多个组、多个类等），使得每个对象在且仅在一个簇中，并且每个簇的内部对象之间具有很高的相似性，但与其他簇中的对象很不相似。

这里， 相似性的定义不同，评价聚类效果的目标函数也会不同，聚类出来的 结果也不一样。对于现在讨论的简单情况，每个数据对象都可以表示为 d 维实空间中的一个点， 我们自然可以用欧几里得距离定义相似性：距离越小，相似性越大。k-均值算法也是基于这类定义的。

本章将先介绍 k-均值希望优化的目标函数和基本算法，再给出一个具体示例，帮助大家理解算法的过程，最后讨论 k-均值算法存在的局限性，以及可能 的改进。

特别说明一下，聚类的算法有很多，如划分法（partitioning method）、层次法（hierarchical method）、密度法（density-based method）等，k-均值算法只是其中最简单的，有兴趣的读者可以自行阅读相关资料^[8][9] 。