2.1 基本算法

我们将定义在 d 维实空间上的 N 个对象分成 k 个簇，使得任意对象 x_i 属于且仅属于一个簇，这个簇的标号为记 。注意，在基本的 k-均值算法中，k 是给定的，不能从数据中得到。假设每个簇都可以用一个 d 维实空间上的一个数据点来代表，可以理解为一种能够代表很多用户偏好的新套餐方案。

再如，如果我们已知一段时间内一个城市发生火灾的地点，有修建 5 个消 防站的预算（暂时不考虑以前的消防站，假设它们都不可用了），就可以以这些 火灾发生的地点为数据点，做一个 k=5 的聚类；聚类后，每个簇的代表点就可以作为新消防站的选址。不失一般性，这k个簇的代表点我们记为y₁,y₂,...,y_k。

如果用 D ( x , y ) 表示点 x 和 y 的欧几里得距离，注意到对象 x_i 所在的簇的代 表节点是，则分类的总代价可以表示为

(2-1)

k-均值算法的思路就是，通过迭代的方式不停地优化代价 S，让它越来越小。

k-均值算法首先在 d 维实空间中随机选择 k 个点，作为 k 个簇的代表点，然 后反复执行下面的两个步骤。

步骤 1：为每个对象分配一个簇

将每个对象 分配到距离它最近的那个代表点所代表的簇中。

步骤 2：重新计算每个簇的代表点位置

根据步骤 1，每个簇的代表点的位置将更新为这个簇中所有对象的平均位置。也就是说，对于任意 的位置将更新为

(2-2)

其中，m_j 是当前簇 j 所辖的对象数目。

k-均值算法反复执行步骤 1 和步骤 2，直到收敛——在执行步骤 1 的时候，如果每个对象所分配的新簇标号和原来的簇一样，那就收敛了。可以证明，k-均值算法一定会在有限步内收敛，并且一般而言，k-均值的收敛速度是很快的。

认真的读者脑海里面可能冒出两个问题。

一是为什么每次把一个簇的代表点选为这个簇中所有数据对象的均值点？ 这个选择方法其实就是 k-均值名字的由来，如果不明白为什么这样选，就不能算懂得k-均值算法。

二是本章开头说了聚类的目的是让同一个簇中的数据点之间的相似性高（距离近），这个目的很直观，也很合理。那么，为什么 k-均值算法要选择公式 (2-1)作为目标函数而不计算数据点之间的距离？(2-1)是不是一个假的目标函 数呢？

其实，这两个问题拥有一个共同的答案，就是如果令 为簇 j 中所有数据 对象的均值，那么最小化公式(2-1)中的目标函数与最小化一个簇中两两数据对 象之间的距离的平方和是一致的。考虑 d=1 的情况（d>1 完全类似，大家可以作为练习题），如果有 N 个数据对象，记为 ，其均值为

则根据公式(2-1)，N 个数据对象组成的这个簇的代价为

(2-3)

而 N 个数据对象两两距离的平方和为

(2-4)

注意，两者只差一个因子 N，所以优化目标函数(2-3)和目标函数(2-4)是一 回事。换句话说，刚才的问题可以这样回答，k-均值算法把每次更新后簇的代表 点选为所辖数据对象的均值，并且定义公式(2-1)这样的目标函数，恰恰是为了使得一个簇内两两对象之间的相似性高。

至于相似性是不是要定义为欧几里得距离的平方，则不一定。当然， 如果定义成其他样子，就会得到其他的聚类结果，所使用的方法也不再是 k-均值的方法了。