k-均值聚类 k-Means Clustering

k-均值聚类 k-Means Clustering

k-均值聚类 算法假设给定一组向量值数据，目标是将 $m$ 个观测值划分为 $k$ 个 聚类 Clustering，聚类 也被称为 簇 cluster，每个观测值都被标记为属于最近的聚类，聚类 的 中心 mean 可以看作是该 聚类 的 代理 proxy 或 原型 prototype 通过反映簇内数据点的平均值来代表整个簇

由于每个数据点都分配给了最近的簇中心，这个过程实际上把整个数据空间划分成了多个区域，这些区域被称为 Voronoi 单元 Voronoi cells，每个 Voronoi 单元 代表一个簇，由与该簇中心最近的所有点组成

尽管观察值数量和系统的维度是已知的，但是聚类数量 $k$ 一般是未知的，是需要被确定的，并且 $k$ 的值由用户确定，也就是说用户希望从数据中提取出多少个聚类

k-means 算法是迭代的，首先假设每个簇的均值的初始值，然后更新均值，直到算法收敛，该算法的步骤如下

1. 给定 $k$ 个不同的初始均值，分别计算每个观测值 $x_j$ 到这 $k$ 个初始均值的距离
2. 将每个观测值 $x_j$ 标记为属于距离其最近的均值簇
3. 标记完成后，计算每个簇中所含数据点的质心 (均值)，这些新计算出的均值将用于新一轮的迭代

k-means 算法可以用优化问题的形式来表述，具体来说，以下最小化问题描述了这个过程

$$\operatorname*{argmin}_{\mu_j} \sum_{j=1}^{k}\sum_{\mathbf{x}_n \in \mathcal{D}_j^{'}} \|\mathbf{x}_n - \mu_j \|^2$$

• $\mu_j$ 表示第 $j$ 个簇的中心 (均值)
• $\mathcal{D}_j^{'}$ 表示第 $j$ 个簇相关的数据子域，即属于第 $j$ 个簇的所有数据点

从这个优化问题我们可知，k-Means 聚类 的目标就是最小化簇内平方误差和，该目标函数反映了每个数据点与其所在簇中心的距离，如果这个距离越小，说明数据点被更合理地分配到了其所属的簇中，意味着簇内部的数据点更加紧密地聚集在一起

通过不断地调整簇中心 $\mu_j$ 算法会逐渐收敛到一个局部最优解，使得总的平方误差和最小化，这就是 k-Means 算法的核心: 通过最小化簇内平方误差和来找到最优的簇划分，即通过不断地调整簇中心以最小化簇内的平方误差和，从而实现数据点的合理划分

在找到最优簇中心后，每个簇的 Voronoi cell 实际上是由簇中心 $\mu_j$ 所主导的区域，每个数据点被分配到最近的簇中心，从而形成了 Voronoi cells，而这个过程恰好是通过最小化每个数据点到其簇中心的距离来实现的，这与公式中的目标函数是一致的

一般来说，解决这个优化问题是 NP 困难 的，但是有许多启发式算法，虽然不能保证可以收敛到全局最优，仍能保证良好的性能

交叉验证 Cross-validation

在 k-Means 这样的无监督学习算法中，由于数据没有预定义的标签，因此无法像有监督学习那样直接比较模型预测的标签和真实标签，这使得交叉验证的过程更加微妙

簇内平方误差和 WCSS

我们首先需要定义 簇内平方误差和 Within-Cluster Sum of Squares,WCSS，它实际上就是我们优化问题的目标函数

$$\text{WCSS} = \sum_{j=1}^{k}\sum_{\mathbf{x}_n \in \mathcal{D}_j^{'}} \|\mathbf{x}_n - \mu_j \|^2$$

其中内层的累加操作

$$\sum_{\mathbf{x}_n \in \mathcal{D}_j^{'}} \|\mathbf{x}_n - \mu_j \|^2$$

计算每个簇的簇内平方误差和，这代表了每个簇的 Variation 变异性，在统计学中，Variation 变异性 通常用来描述一组数据的分散程度，即数据点如何围绕其均值（在 k-Means 中是簇中心）分布，也就是簇内数据点的离散程度

外层的累加操作

$$\sum_{j=1}^{k}\sum_{\mathbf{x}_n \in \mathcal{D}_j^{'}} \|\mathbf{x}_n - \mu_j \|^2$$

求和了所有簇的簇内平方误差和，得到总簇内平方误差和，也就是最终的 WCSS

• WCSS 较小：簇内的所有数据点都很接近簇中心，表示簇内的变异性较小，即簇内数据点之间的相似性较高
• WCSS 较大：簇内数据点之间的距离较远，表示簇内的变异性较大，即簇内数据点之间的相似性较低

因此，WCSS 可以被视为衡量每个簇的 Variation 的一个定量指标，通过最小化 WCSS，k-Means 聚类 试图使每个簇的变异性尽可能小，从而确保簇内的紧密度和数据点的相似性

使用 WCSS 优化 $k$ 值

在确定最优聚类数量 $k$ 时，常用的方法是绘制 肘部法 Elbow Method 图形，在图中 WCSS 随 $k$ 值增加而逐渐减小，但当 $k$ 达到某个值后，减少的幅度显著降低，形成一个肘部，此时的 $k$ 值被认为是较优的聚类数量

使用 WCSS 进行交叉验证

1. 在训练集上最小化 WCSS
   首先，在训练集上运行 k-Means 聚类，并通过迭代优化簇中心，使得训练集的 WCSS 降低到一个设定的阈值以下，这个过程与标准的 k-Means 聚类过程一致，即通过不断调整簇中心，最小化每个簇内的平方误差和（WCSS）
2. 在测试集上执行 k-Means 聚类
   一旦在训练集上达到了满意的 WCSS，则可以将这个模型应用到测试集上，即将测试集的数据点分配到已经确定好的簇中，这实际上相当于对测试集的每个点，找到其最近的训练集中的簇中心，然后标记为属于该簇
3. 计算测试集的 WCSS
   接下来，可以计算测试集的 WCSS，即测试集中每个数据点与其所属簇中心之间的距离平方和的总和，这个值可以用来评估模型在测试集上的表现
4. 交叉验证的逻辑
   这种方法实际上是一种简单的交叉验证思路，即在不同的训练-测试集划分下，验证模型的泛化能力，可以通过多次重复这个过程（即 k-fold 交叉验证）来评估 k-Means 模型的稳健性和在不同数据集上的表现

注意点

• 标准化: 在进行聚类之前，通常需要对数据进行标准化处理，以确保各特征对距离计算的影响一致
• 簇的数量 $k$: 需要在这个过程中选择一个合适的 $k$ 值，例如通过如肘部法则（Elbow Method）等方法来确定

判定收敛

在 k-Means 聚类 算法中，有多种方式可以判定收敛

1. 簇中心的变化
   这是 k-Means 中最常用的收敛判定标准，在每次迭代中，计算当前簇中心和上一次簇中心之间的移动距离 (通常使用欧氏距离)，如果所有簇中心的移动距离都小于某个预设的阈值，则认为算法已经收敛
2. 数据点的簇分配不再变化
   另一种判断收敛的方式是看数据点的簇分配是否稳定，在每次迭代中，数据点会被重新分配到离它们最近的簇中心，如果在一次完整的迭代后，所有数据点的簇分配与上一次迭代一致，则认为算法收敛
3. WCSS 不再显著降低
   还可以通过观察 WCSS 的变化来判断收敛，在每次迭代中，计算 WCSS 的值，如果 WCSS 的减少量低于某个预设的阈值，则认为算法已经收敛
4. 达到最大迭代次数
   通常还会设定一个最大迭代次数作为收敛条件的补充，如果在达到最大迭代次数时，算法仍未满足上述任何收敛条件，则停止迭代

在实际应用中，通常会结合上述多种标准来判断收敛，例如，可以设置一个最大迭代次数，同时结合簇中心的变化和 WCSS 的变化来决定何时停止迭代，这可以确保算法不会陷入无限循环，同时也能避免过早收敛导致聚类质量不佳

总的来说，k-Means 是一种无监督学习算法，这意味着在训练过程中不需要预先标注的数据，这对于数据集没有标签或标签难以获取的情况非常有用

并且它是一种快速且高效的 启发式算法 heuristic algorithm 尽管它可能不会找到全局最优解，但在许多实际应用中，它可以在合理的时间内找到一个较好的解

k-Means 可能不够准确，这是无监督学习算法的一个普遍问题，由于没有标签作为指导，算法对数据的了解是有限的，因此在某些情况下，聚类的效果可能并不理想，可以通过 k 折交叉验证等方法来改进无监督学习算法的性能，增强模型的准确性，这种方法通过多次划分和验证数据，帮助模型更好地泛化，减少过拟合的风险，但通常情况下，无监督学习的准确性仍然不如有监督学习算法，因为后者可以利用标签数据进行更精确的训练和优化