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

[b]（一）距离的计算[/b][br] 在聚类算法的距离计算中，不得不提到范数这一数学概念，在很多机器学习相关的著作和教材中，我们也经常看到各式各样的距离及范数，如[math]\parallel x\parallel[/math]，[math]\parallel X\parallel[/math]，其中[math]x[/math]，[math]X[/math]分别表示向量和矩阵。

为方便统一，一般将任意向量[math]x[/math]的[math]l_p[/math]范数定义为：[math]\parallel x\parallel_p=\sqrt[p]{\sum_i\mid x_i}\mid^p[/math]

由上式可知，则[math]l_0[/math]范数的定义为：[math]\parallel x\parallel_0=\sqrt[0]{\sum_i\mid x_i\mid^0}[/math]，它表示向量[math]x[/math]中的非0元素的个数。在诸多机器学习模型中，比如压缩感知（Compressive sensing），就是希望最小化向量的[math]l_0[/math]范数。[br] 同理，[math]l_1[/math]范数的定义为：[math]\parallel x\parallel_1=\sum_i\mid x_i\mid[/math]，由式中可以看出，[math]l_1[/math]范数等于向量中所有元素的绝对值之和。[math]l_1[/math]范数的优点是容易求解，借助现有凸优化算法（线性规划或是非线性规划），就能够找到我们想要的可行解。

[math]l_1[/math]范数应用于距离计算时，就是曼哈顿距离，其计算公式为[math]D\left(x,y\right)=\sum^k_{i=1}\mid x_i-y_i\mid[/math]。[url=https://chat.baidu.com/search?word=%E4%B8%BA%E4%BB%80%E4%B9%88%E5%8F%AB%E6%9B%BC%E5%93%88%E9%A1%BF%E8%B7%9D%E7%A6%BB&dyTabStr=MCwxMiwzLDEsMiwxMyw3LDYsNSw5&pd=csaitab&setype=csaitab&extParamsJson=%7B%22enter_type%22%3A%22search_a_tab%22%2C%22sa%22%3A%22vs_tab%22%2C%22apagelid%22%3A%2215761149350493580048%22%2C%22ori_lid%22%3A%2215761149350493580048%22%7D][b][color=#0000ff]曼哈顿距离[/color][/b][icon]/images/ggb/toolbar/mode_zoomin.png[/icon][/url]通常称为出租车距离或城市街区距离，用来计算实值向量之间的距离，如下图2-2-2。想象一下均匀网格棋盘上的物体，如果它们只能移动直角，曼哈顿距离是指两个向量之间的距离，在计算距离时不涉及对角线移动。[br][br][img]https://s21.ax1x.com/2025/02/01/pEZMCQA.jpg[/img] [img]https://s21.ax1x.com/2025/02/01/pEZMrTK.jpg[/img][br][center][br]图2-2-2 曼哈顿距离示意图[/center] 以下为曼哈顿距离的[color=#0000ff][b][url=https://www.geogebra.org/classic/u5b7kvkm]动态示意图[/url][icon]/images/ggb/toolbar/mode_zoomin.png[/icon][/b][/color]，请拖动点A、点B，感受曼哈顿距离在三维空间中[math]d\left(A,B\right)[/math]的计算过程，拖动点C、点D，感受曼哈顿距离在二维平面中[math]d\left(C,D\right)[/math]的计算过程。[br]

[math]l_2[/math]范数表示向量（或矩阵）的元素平方和开根号，即[math]\parallel X\parallel_2=\sqrt{\sum_i\mid x_i}\mid^2[/math]。[math]l_2[/math]范数应用于距离计算时，就是[b][color=#0000ff][url=https://chat.baidu.com/search?word=%E4%B8%BA%E4%BB%80%E4%B9%88%E5%8F%AB%E6%AC%A7%E5%BC%8F%E8%B7%9D%E7%A6%BB&dyTabStr=MCwxMiwzLDEsMiwxMyw3LDYsNSw5&pd=csaitab&setype=csaitab&extParamsJson=%7B%22enter_type%22%3A%22search_a_tab%22%2C%22sa%22%3A%22vs_tab%22%2C%22apagelid%22%3A%2215761149350493580048%22%2C%22ori_lid%22%3A%2215761149350493580048%22%7D]欧式距离[icon]/images/ggb/toolbar/mode_zoomin.png[/icon][/url][/color][/b]，其计算公式为：[math]D\left(x,y\right)=\sqrt{\sum^n_{i=1}\left(x_i-y_i\right)^2}[/math]。欧式距离可解释为连接两个点的线段的长度。欧式距离公式非常简单，使用勾股定理，从这些点的笛卡尔坐标计算距离，如图2-2-3为二维及三维欧式距离示意图。[br][img]https://s21.ax1x.com/2025/02/01/pEZMMyn.jpg[/img] [img]https://s21.ax1x.com/2025/02/02/pEZs9US.jpg[/img][br] 图2-2-3 欧式距离示意图[br][br] 以下是欧式距离的[color=#0000ff][b][url=https://www.geogebra.org/classic/jmh9hf58]动态示意图[/url][icon]/images/ggb/toolbar/mode_zoomin.png[/icon][/b][/color]，请拖动B点，感受欧式距离在三维空间中[math]d\left(A,B\right)[/math]的计算过程。[br]

以上两种距离计算方法是聚类算法中最为常用的，此外还有一些距离计算法，适合于某种特定应用场景的计算。比如[color=#0000ff][b][url=https://www.geogebra.org/m/snavyzdk]余弦相似度[/url][icon]/images/ggb/toolbar/mode_zoomin.png[/icon][/b][/color]，其计算公式为：[math]D\left(x,y\right)=cos\left(\theta\right)=\frac{x\cdot y}{\parallel x\parallel\parallel y\parallel}[/math]。余弦相似度主要应用于文本分析。其它还包括闵氏距离（[math]d_{ij}=\sqrt[\lambda]{\sum^n_{k=1}\mid x_{ik}}-x_{jk}\mid^{\lambda}[/math]），切比雪夫距离（[math]D\left(x,y\right)=max_i\left(\mid x_i-y_i\mid\right)[/math]）等。

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

[b]（三）几个聚类算法中的数学公式[/b][br] （1）质心的计算。如果用数据表达式表示，假设簇划分为([math]C_{1,}C_2,...C_k[/math])，设[math]\mu_i[/math]是[math]C_i[/math]的均值向量，也称为质心[color=#0000ff]，[/color]表达式为：[br][br] [math]\mu_i=\frac{1}{\mid C_i\mid}\sum_{x\in C_i}x[/math][br][br] （2）误差平方和（SSE，The Sum of Squares due to Error），是指簇内每一个点与其质心的距离平方和，体现的是质心位置的合适程度。其表达式为：[br][br] [math]SSE=\sum^k_{=1}\sum_{p\in C_i}\mid p-m_i\mid^2[/math]

设想这样一个问题，如果分簇不合理时，其簇内各点与其质心的距离平方和肯定大于合理分簇的距离平方和（示意图如下图2-2-4）。设[math]m_1[/math]、[math]m_2[/math]为当[math]k=2[/math]时的质心，[math]m_3[/math]为当[math]k=1[/math]时的质心，显然分为两簇更符合样本形态。不难推断，[math]k[/math]值越大，SSE越小，但也不是越小越好，因为如设每一点为一簇，则SSE为零，那么如此分簇将毫无意义。所以，误差平方和这一参数一般考察的是样本分为几簇更为合理，即[math]k[/math]的取值问题。至于SSE与[math]k[/math]值之间的映射关系，将在下一节结合用例详细说明。[br][br][table][tr][td][img]https://s21.ax1x.com/2025/02/03/pEZgWmn.jpg[/img][/td][td][img]https://s21.ax1x.com/2025/02/03/pEZg2Os.jpg[/img][/td][/tr][/table][br] 图2-2-4 SSE示意图[br][br]

（3）轮廓系数（Silhouette Coefficient）。是结合了聚类的凝聚度（Cohesion）和分离度（Separation）的一个参数，用于评估聚类的效果。其表达式为：[br] [br] [math]S=\frac{\left(B-A\right)}{max\left(A,B\right)},S\in\text{[-1，1}\text{]}[/math][br] [br] 这里[math]A[/math]是指样本[math]x_i[/math]到同一簇内其他点不相似程度的平均值，[math]B[/math]是指样本[math]x_i[/math]到其他簇的平均不相似程度的最小值。其示意图如图2-2-5。[br][img]https://s21.ax1x.com/2025/02/03/pEZg5kV.jpg[/img][br] 图2-2-5 轮廓系数示意图

轮廓系数的取值范围为[math]\left[-1,1\right][/math]，其值越大越好。其目的是使内部距离最小化，外部距离最大化。