K-Means

K-Means 聚类 (K-Means Clustering)

K-Means（K-均值聚类）是一种基于划分的无监督学习算法，广泛应用于聚类分析、数据挖掘和模式识别领域。其核心目标是将 $n$ 个观测点划分到 $k$ 个簇中，使得每个点归属于离其最近的质心（Centroid）所在的簇，从而最小化簇内平方和（Within-Cluster Sum of Squares, WCSS），亦称惯性（Inertia）。该算法由Hugo Steinhaus于1956年首次提出，后由James MacQueen于1967年正式命名并系统阐述，Stuart Lloyd于1957年在贝尔实验室独立发展出类似方法（Lloyd算法），已成为工业界和学术界最广泛采用的聚类方法之一。

算法原理与步骤

K-Means遵循期望最大化（Expectation-Maximization, EM）的迭代优化框架。标准的Lloyd算法包含以下步骤：

1. 初始化：随机选择 $k$ 个数据点作为初始质心 $\mu_1, \mu_2, \dots, \mu_k$。常见的初始化策略包括随机抽样和K-Means++——后者以概率与距离平方成正比的方式分散初始质心，显著改善收敛质量。
2. 分配步骤（Assignment Step）：将每个数据点 $x_i$ 分配到距离最近的质心所代表的簇。距离度量通常采用欧几里得距离： \[ C_j = \{ x_i : \|x_i - \mu_j\|^2 \leq \|x_i - \mu_t\|^2 \text{ 对所有 } t \neq j \} \]
3. 更新步骤（Update Step）：重新计算每个簇的质心为其成员点的算术平均： \[ \mu_j = \frac{1}{|C_j|} \sum_{x_i \in C_j} x_i \]
4. 收敛判断：重复分配与更新步骤，直至质心不再显著移动或达到预设的最大迭代次数。算法保证WCSS单调递减并收敛至局部最优解。

选择最优簇数 $k$

$k$ 的选择是K-Means应用中最关键的决策。常用的启发式方法包括：

1. 肘部法则（Elbow Method）：绘制不同 $k$ 值对应的WCSS曲线，寻找下降速率急剧减缓的"肘点"。该方法直观但主观性强，当曲线呈平滑渐降时难以判定。
2. 轮廓系数（Silhouette Score）：衡量数据点与自身簇的紧密度相对于与最近邻簇的分离度，取值在 $[-1, 1]$ 之间，越接近1表示聚类质量越高。通过在候选 $k$ 值上最大化平均轮廓系数来选择最优簇数。
3. Gap统计量：将实际数据的WCSS与参照分布（均匀分布）下的期望WCSS比较，选择使Gap值最大的 $k$，提供更正式的统计推断框架。

局限性与变体

K-Means尽管高效，但存在若干内在局限：（1）对初始质心敏感，劣质的初始化可导致收敛至差局部最优；（2）假设簇是各向同性的球形，对非凸形状或大小悬殊的簇表现不佳；（3）对离群值敏感，极端值会显著拉动质心位置；（4）要求预先指定 $k$，而在实际场景中簇数往往未知。

针对上述局限，衍生出多种变体与替代方法：K-Means++ 通过智能初始化缓解局部最优问题；K-Medoids（PAM算法）使用实际数据点作为簇中心，对离群值更具鲁棒性；模糊C-Means允许数据点以隶属度属于多个簇；DBSCAN和层次聚类则能处理任意形状的簇且无需预指定簇数。在实际应用中，K-Means因其 $O(n \cdot k \cdot d \cdot t)$ 的线性时间复杂度——其中 $n$ 为样本数、$d$ 为特征维度、$t$ 为迭代次数——在大规模数据集上具有显著的效率优势，常作为探索性数据分析的首选工具。

经济学与社会科学应用

在经济学及相关社会科学领域，K-Means被广泛用于市场细分（根据消费者行为特征将客户分组，以制定差异化营销策略）、区域经济分类（按多项经济指标将城市或地区聚类，识别发展模式的同质群体）、收入分配研究（分析家庭收支调查数据，划分社会经济阶层）以及金融风险管理中识别具有相似风险特征的投资组合或借款人群体。在政策评估中，K-Means也常被用作构建反事实对照组的前置步骤——通过聚类匹配处理组与控制组的协变量特征，以降低选择偏误。