通过边界点筛选实现 k-Means 的两点局部最优性

基于摘要分析。本文针对 k-Means 解对初始化敏感、现有局部优化保证较弱的问题，提出 r 点局部最优性：重新分配至多 r 个样本均不能降低目标函数，并重点研究 r=2。核心贡献是利用可改进样本对的结构筛选候选点，提出 Boundary-Point-Screened Two-Point Local Search（BPS-2PLS），作者称其终止于两点局部最优解；这不等同于全局最优保证。 机制与理论：对 n 个 d 维样本、k 个簇，穷举两点最优性认证的成本为 O(n²(k²+d))。作者证明，在 D-local 最优解上，任何能改进目标的两点移动，其两次重新分配必须涉及一个共同簇，且参与改进的样本必须属于证书定义的边界点。作者进一步给出概率阶结论：在 k、d 固定、簇占用不趋于零，且样本独立同分布地来自有界支撑且密度有界的分布或 Gaussian mixture 时，保留候选数 m=O_P(log n)。该结论不能直接推广为任意数据或高维设置下的整体运行时间保证。 结果与复现：作者报告，在十二个基准中，BPS-2PLS 在十个上取得所比较方法中的最低平均 WCSS；在子采样研究的最大测试规模下，筛选平均保留 0.10%–2.81% 的样本。摘要提供代码地址，但基准名称、初始化与重复运行设置、具体对照、运行时间、消融及统计信息尚未验证，不能据此判断收益的稳定性。 平台推测（待验证）：迁移假设是将该方法用于 EEG 特征或嵌入的无监督聚类，以检验更强局部搜索能否缓解初始化敏感性。可复用边界筛选与两点搜索模块，但需核对特征距离、归一化和簇占用条件；低信噪比、跨被试差异、通道变化及小样本可能使 WCSS 改善不对应生理结构改善，EEG 时序相关性也可能不满足理论采样前提。一个可证伪的小实验是在固定 EEG 特征、相同 k 与初始化下，对照 Lloyd、D-local 和 BPS-2PLS，记录 WCSS、耗时、候选比例及重复运行稳定性；已有 EEG 相关工作尚未检索确认。