2.2　k-均值算法

将观测值进行聚类分析时，我们需要进行距离衡量。首先假设有两个特征取值x和y，将两个特征的散点分布图显示在二维坐标图上。假设其中有两个观测值A和B，如图2-1所示，则两点之间的距离计算为欧氏距离（Euclidean distance），即图中直线AB的长度。假设对于观测值A，x=x_A且y=y_A，同样对于观测值B，x=x_B且y=y_B，则A与B两点间的欧式距离为（利用毕达哥拉斯定理，即勾股定理）：

该距离的计算方法可以被延伸到更多的维度上。假设我们的一组观测值中有m个特征，对于第i个观测值的第j列特征，我们称之为v_ij，则第p个观测值与第q个观测值之间的距离为：

图2-1　A与B之间的距离，通过（x_A，y_A）和（x_B，y_B）两点坐标，计算出直线AB的长度

将两个特征扩展到三个很容易理解，即通过衡量三个而不是两个维度去计算距离；如果假设需要衡量的距离超过三个（m>3）就变得不那么容易了，但公式依然是由一个、两个、三个维度延展而来的。

另外一个在k-均值算法中需要了解的定义是一个聚类的中心（center），又被称为聚类的矩心（centroid）。假设一部分观测值被归为同个聚类，则中心为这个聚类中每个特征的所有观测值的平均数；如表2-1所示，假设某个聚类中有4个特征和5个观测值，则这个聚类的中心0.914、0.990、0.316和0.330依次为特征1、2、3、4的中心（例如，0.914为1.00、0.80、0.82、1.10和0.85的平均数）。所以，每个观测值与聚类中心之间的距离（表2-1的最后一列）的计算方式与A和B点的距离（见图2-1）的计算方式一致。第一个观测值与聚类中心的距离计算如下：

计算结果等于0.145。

表2-1　5个观测值和4个特征的聚类中心计算

图2-2阐述了k-均值算法是如何运行的。第一步是要选择k，即聚类的个数（后续将更详细地讲解）。作为第一步，我们通常随机选择k个点作为每个子聚类的中心。每个观测值与每个子聚类中心的距离由上面介绍的方法计算而得，然后观测值被分配到最近的一个聚类中。这样就产生了由所有样本第一次分割而成的k个聚类。然后，我们为每个聚类计算新的子聚类中心，如图2-2所示。每个观测值与这个新的中心的距离可以被计算出来，然后按照距离大小重新将每个观测值分配到最邻近的聚类中心。依此类推，我们不停地迭代产生新的中心，直到子聚类的分配不再产生变化为止。

一种衡量上述算法效果的指标为聚类内的平方和，也就是“惯性矩”（inertia），设d_i为第i个观测值与其子聚类中心的距离：

图2-2　k-均值算法

式中，n为观测值的数量，在已设置k值的条件下，聚类算法的目的是使惯性矩最小化。在k-均值算法中，最终的结果可能会受初始设置子聚类个数的影响（k值），所以我们必须尝试设置不同的个数，以确保惯性矩最小化，即聚类的最优结果。

在通常情况下，惯性矩随着k值上升而下降，当k值数量达到极限，即k值等于观测值的数量时，每个观测值都有一个聚类，此时惯性矩为零。