第一节 K-means算法

作者:Woody

K-means算法是最基础和最常用聚类算法。其相关概念有： K值：希望得到的簇的个数。质心：即簇的中心值，是每个簇的均值向量，向量各维取平均即可。距离量度：常用欧几里得距离和余弦相似度，但在计算之前，先要将各维数据标准化。

一、距离的计算 在聚类算法的距离计算中，不得不提到范数这一数学概念，在很多机器学习相关的著作和教材中，我们也经常看到各式各样的距离及范数，如

，

，其中

分别表示向量和矩阵。

为方便统一，一般将任意向量

的

范数定义为：

由上式，则

范数的定义为：

，它表示向量中的非0元素的个数。在诸多机器学习模型中，比如压缩感知（Compressive sensing），就是希望最小化向量的

范数。同理，范数的定义为：

，由式中可以看出，

范数等于向量中所有元素的绝对值之和。

范数的优点是容易求解，借助现有凸优化算法（线性规划或是非线性规划），就能够找到我们想要的可行解。

范数应用于距离计算时，就是曼哈顿距离，其计算公式为

。曼哈顿距离通常称为出租车距离或城市街区距离，用来计算实值向量之间的距离，如下图4-2。想象一下均匀网格棋盘上的物体，如果它们只能移动直角，曼哈顿距离是指两个向量之间的距离，在计算距离时不涉及对角线移动。

图4-2 曼哈顿距离

范数表示向量（或矩阵）的元素平方和开根号，即

。

范数应用于距离计算时，就是欧式距离，其计算公式为：

。欧式距离可解释为连接两个点的线段的长度。欧式距离公式非常简单，使用勾股定理，从这些点的笛卡尔坐标计算距离，如下图（图4-3）二维及三维欧式距离示意图。动态三维欧式距离示意图下载链接为：https://www.geogebra.org/m/fahqcfjs，手机端查看可扫描右边二维码：

图4-3 欧式距离

以上两种距离计算方法是聚类算法中最为常用的，此外还有一些距离计算法，适合于某种特定应用场景的计算。比如余弦相似度，其计算公式为：

。余弦相似度主要应用于文本分析。其它还包括闵氏距离（

），切比雪夫距离（

）等。

二、算法流程 （1）首先确定一个k值，即我们希望将数据集经过聚类得到

集合。（2）从数据集中随机选择k个数据点作为质心。（3）对数据集中每一个点，计算其与每一个质心的距离（如欧式距离），离哪个质心近，就划分到那个质心所属的集合。（4）把所有数据归好集合后，一共有k个集合。然后重新计算每个集合的质心，计算均值，即向量各维取平均。（5）如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值（表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛），我们可以认为聚类已经达到期望的结果，算法终止。（6）如果新质心和原质心距离变化很大，需要迭代3~5步骤。

三、几个聚类算法中的数学公式 在聚类算法的流程中，读者可能会产生一种错觉，认为其聚类原理容易理解，符合所有人的一般认知。不就是找到几个相对中心，然后计算距离，以最小距离归类吗？况且计算过程也不复杂。这些错觉很容易让读者对聚类不屑一顾，而不愿深入研究。事实上，聚类算法也有自己的深度内容，这些内容将在以下部分有限度地展开，但在此之前，让我们先学习几个聚类算法中无法绕开的概念及它们的数学公式。（1）质心的计算。如果用数据表达式表示，假设簇划分为(

)，设

是

的均值向量，也称为质心，表达式为：

（2）误差平方和（SSE，The Sum of Squares due to Error）。是指簇内每一个点与其质心的距离平方和，体现的是质心位置的合适程度。其表达式为：

设想这样一个问题，如果分簇不合理时，其簇内各点与其质心的距离平方和肯定大于合理分簇的距离平方和（示意图如下图4-4）。设

、

为当

时的质心，

为当

时的质心，显然分为两簇更符合样本形态。不难推断，