跳转至

Consistency and inconsistency in k-means clustering

作者: Moïse Blanchard, Adam Quinn Jaffe, Nikita Zhivotovskiy
来源: Electronic Journal of Statistics
主题: 数理统计 / 假设检验
相关性: 6/10
机构绿灯: Georgia Institute of Technology(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是:k-means 聚类作为一种非参数估计方法,其经验风险最小化(ERM)解在总体分布矩条件不足时,是否仍然具有统计一致性? 具体而言,经典理论(Pollard, 1981)要求总体分布具有有限二阶矩(E∥X∥² < ∞)才能保证经验聚类中心几乎必然收敛到总体聚类中心。本文探讨的是:当这个条件放宽到仅有一阶矩(E∥X∥ < ∞)时,一致性是否还能成立?如果不能,需要什么样的额外约束(如聚类平衡条件)才能恢复一致性?这个子方向处于"非参数估计的矩条件边界"与"聚类算法的统计基础"的交汇处,成熟度属于理论深化阶段——经典结果已确立,但边界条件尚未被系统探索。

发展脉络(history)

  1. 奠基工作:Pollard (1981) 的经典结果确立了 k-means 在有限方差条件下的强一致性,这是整个领域的基石。作者在引言中明确指出:"A celebrated result of Pollard proves asymptotic consistency for k-means clustering when the population distribution has finite variance." 这个结果奠定了"有限方差 → 一致性"的标准范式。

  2. 有限样本率的补充:Bartlett, Linder, Lugosi (1998) 和 Levrard (2014) 等给出了有限样本下的 distortion 收敛速率,但这些结果同样依赖有限方差条件。Levrard (2014) 的"margin condition"框架表明,在有限方差下可以做到 O(1/n) 的期望 distortion 率。

  3. 几何与自适应扩展:Jaffe (2022) 将 Pollard 的结果推广到 Riemannian 流形、自反 Banach 空间和 Wasserstein 空间等几何设定,并处理了自适应选择参数(如 k-medoids、肘部法则)的情形。Jaffe (2024) 进一步建立了无穷维空间中 Fréchet 均值的渐近理论。这些工作扩展了适用场景,但仍然保留有限方差假设。

  4. 鲁棒性与重尾分布:Klochkov, Kroshnin, Zhivotovskiy (2020) 在有限方差下给出了 sub-Gaussian 形式的非渐近 excess distortion 界,并指出聚类不平衡是控制 minimax 速率的关键因素。这为本文的"平衡约束"思路提供了直接铺垫。

  5. 当前 frontier 与本文位置:本文是第一个系统研究仅有一阶矩条件下 k-means 一致性的工作。作者在引言中明确指出:"we point out that the population-level k-means clustering problem is, in fact, well-posed under the weaker assumption of a finite expectation, and we investigate whether some form of asymptotic consistency holds in this setting." 本文的位置是:在经典结果(有限方差)与不可能性(无矩条件)之间,刻画出一致性成立的精确边界,并证明平衡约束是恢复一致性的充分条件。

子线索聚类

这些被引文献大致落在三条子线索上:

  • 线索 A:经典一致性理论(Pollard 1981; Pärna 1986; Jaffe 2022, 2024)—— 在有限方差或更一般的度量空间设定下,证明经验聚类中心/聚类划分的强一致性。这条线索的核心工具是经验过程理论和测度论方法。

  • 线索 B:有限样本速率与 minimax 理论(Bartlett et al. 1998; Levrard 2014; Klochkov et al. 2020; Appert & Catoni 2021)—— 给出 excess distortion 的非渐近界,识别出控制速率的几何量(如 margin 参数、聚类不平衡度)。这条线索的方法论是 empirical process + chaining。

  • 线索 C:鲁棒聚类与平衡约束(Cuesta-Albertos et al. 1997; Gallegos & Ritter 2005; Brécheteau et al. 2018; García-Escudero et al. 2017)—— 通过 trimming 或平衡约束来增强 k-means 对异常值的鲁棒性。本文的平衡约束方法直接继承自这条线索,但将其从"计算技巧"提升为"统计一致性恢复工具"。

这个方向在追问的核心问题

  1. 矩条件的必要性:有限方差是否是 k-means 一致性的必要条件?如果仅有一阶矩,一致性是否还能成立?(本文给出否定答案:不能,除非施加平衡约束。)
  2. 一致性的合适表述:当聚类中心不收敛时,是否还有其他有意义的一致性概念(如 excess distortion 的收敛)?在什么意义下可以恢复一致性?
  3. 平衡约束的统计角色:平衡约束是纯粹的计算正则化,还是具有深刻的统计含义?它如何与 minimax 速率交互?

⚠️ 作者的 framing(这是作者的说法)

作者将缺口 frame 成:"经典结果要求有限方差,但 k-means 的定义(即优化问题 (∗))在有限期望下就已经良定义,因此自然的问题是:在这个更弱的条件下,经验解是否仍然一致?" 这个 framing 将本文定位为"填补经典理论的最小矩条件缺口"。作者淡化的竞争路线包括:(i) 有限样本速率理论(认为非渐近结果不能回答"是否一致"这个定性问题);(ii) 鲁棒聚类方法(认为 trimming 等方法虽然鲁棒,但改变了原始优化问题,而本文的平衡约束保持了问题的结构)。值得注意的是,作者没有讨论计算复杂性——即平衡约束下的 k-means 是否仍然可高效求解,这可能是被回避的一个问题。

张力

未见明显对立引用。但存在一个微妙的张力:Klochkov et al. (2020) 的 sub-Gaussian 界暗示在有限方差下聚类不平衡是速率的主要控制因素,而本文表明在无限方差下,不平衡会导致不一致(而非仅仅是慢速率)。这两者之间的关系(从"慢速率"到"不一致"的转变如何发生)是一个值得注意的连续谱。


二、最核心、最简单的例子 / 数学内核

第一步:符号、模型、可观测数据

记号 含义 类型
X, X₁, ..., Xₙ i.i.d. 随机变量,取值于 ℝᵈ 可观测样本
k 聚类数(固定) 已知超参数
C ∈ 𝒞ₖ 至多 k 个点的集合(聚类中心) 决策变量
D_X(C | C′) 相对 excess distortion:E[min_{c∈C}‖X−c‖² − min_{c′∈C′}‖X−c′‖²] 目标函数(可正可负)
𝒞ₖ(X) 总体 k-means 聚类中心集合((∗) 的解) 目标 estimand
𝒞̄ₙ,ₖ 经验 k-means 聚类中心集合((1.1) 的解) 估计量
d_H Hausdorff 距离 度量
p_min(X, V) min_{V∈V} P(X∈V),聚类划分的最小概率质量 平衡度度量
γₙ 平衡约束的下界(每个经验聚类至少含 γₙ 个点) 正则化参数

模型:X 是 ℝᵈ 上的概率分布,满足 E‖X‖ < ∞(一阶矩)。关键点:E‖X‖² 可能为无穷。总体 k-means 问题 (∗) 通过"减去 ‖X‖²"的 renormalization 技巧良定义——即 D_X(C | {0}) = E[min_c ‖X−c‖² − ‖X‖²] 在 E‖X‖ < ∞ 下有限。可观测数据:n 个 i.i.d. 样本 X₁, ..., Xₙ。要估计的对象:𝒞ₖ(X),即 (∗) 的解集。

第二步:最小内核

最小例子(d=1, k=2, 对称 Pareto 分布):

设 X 的分布满足:X 对称,且 P(|X| ≥ t) = t⁻² 对所有 t ≥ 1 成立。则: - E|X| = 2 < ∞(一阶矩存在) - E|X|² = ∞(二阶矩不存在) - 总体最优聚类中心为 𝒞₂(X) = {−2, 2}(唯一)

为什么这个例子是内核? 因为所有负结果(不一致性)和正结果(平衡约束恢复一致性)都可以在这个一维、两聚类的设定中被完全显式地刻画。本文的证明策略是:先在这个最简设定中建立直觉和关键技术引理,然后推广到一般 d 和 k。

核心数学现象:尽管总体最优解是 {−2, 2},但经验最优解会以正概率(且无穷多次)选择形如 {−√n, 0} 或 {0, √n} 的聚类中心。原因在于:Pareto(2) 分布的最大样本值 X₍ₙ₎ 的量级为 n(因为 P(X ≥ t) = t⁻² 意味着 P(X₍ₙ₎ ≥ cn) ≈ 1 − e^{-1/c²}),这个极端值"吸走"了一个聚类中心,使其远离总体最优位置。

数学上证明的核心命题(Example 4.2 的简化版):

对上述对称 Pareto(2) 分布,存在常数 c > 0,使得几乎必然地,对无穷多个 n,任意经验 2-means 聚类中心 𝒞̄ₙ,₂ 都满足 max(𝒞̄ₙ,₂) ≥ c√n/log n 或 min(𝒞̄ₙ,₂) ≤ −c√n/log n。

证明的关键步骤(三步走):

  1. 极端值事件:证明 P(X₍ₙ₎ ≥ √n/log n) 以正概率发生且无穷多次。利用 Pareto 尾:P(X ≥ √n/log n) = (log n)²/n,因此期望次数 Σₙ (log n)²/n = ∞,由 Borel-Cantelli 的逆命题(结合独立性)得无穷多次。

  2. 单点吸走聚类中心:若 X₍ₙ₎ ≥ √n/log n,则将其单独作为一个聚类(中心为 X₍ₙ₎)比将其与任何其他点合并更优。计算表明,将 X₍ₙ₎ 单独成簇的 distortion 约为 0,而合并的 distortion 至少为 (X₍ₙ₎ − 其他中心)² 的量级,远大于前者。

  3. 剩余点形成退化聚类:剩余 n−1 个点中,正负样本大致平衡(由对称性),但它们的量级都远小于 X₍ₙ₎。因此最优解将剩余点聚为一类,中心接近 0,从而形成 {0, X₍ₙ₎} 或 {−X₍ₙ₎, 0} 的形态。

为什么平衡约束能恢复一致性:若要求每个经验聚类至少含 γₙ = αn 个点(α > 0 固定),则极端值 X₍ₙ₎ 不能单独成簇(因为只含 1 个点 < αn),必须与大量其他点合并。此时,极端值对聚类中心的影响被"稀释":中心变为 (X₍ₙ₎ + 其他点)/n 的量级,而由于 E‖X‖ < ∞,这个量级为 O(1),从而恢复一致性。

这个内核揭示了什么:k-means 的不一致性不是因为总体问题 (∗) 的良定义性失败,而是因为经验最优解对极端值的过度敏感——单个极端样本可以"劫持"一个聚类中心。平衡约束的本质是限制单个样本对聚类中心的杠杆效应。


三、这篇论文做了什么

三句话

① 研究了什么问题:在总体分布仅具有有限期望(E‖X‖ < ∞)而非有限方差的条件下,k-means 聚类的经验最优解是否具有渐近一致性?答案是否定的——即使总体最优聚类中心唯一存在,经验聚类中心也可能发散到无穷。

② 核心工具/方法:通过构造 Pareto 尾部分布的显式反例(对称和不对称两种),利用极值理论(Borel-Cantelli 引理、次序统计量的尾部分布)证明不一致性;然后引入 γ-平衡 k-means 聚类(每个经验聚类至少含 γₙ 个点),利用经验过程理论和截断技巧证明平衡约束下的一致性。

③ 主要结论:(a) 在有限期望条件下,无约束 k-means 的经验聚类中心不一致,且不一致性源于极端样本导致的聚类不平衡;(b) 若施加 γₙ ≫ (log n)² 的平衡约束,则经验聚类中心在 Hausdorff 度量下几乎必然收敛到总体最优聚类中心;(c) 若 γₙ ≫ (log n)⁴,则 excess distortion 也几乎必然收敛到最优值。

关键设定与假设

设定:X 是 ℝᵈ 上的概率分布,E‖X‖ < ∞。k ≥ 2 固定。总体问题 (∗) 通过 renormalization 良定义。

核心假设: - A1(矩条件):E‖X‖ < ∞。这是全文最弱的矩条件,比 Pollard (1981) 的 E‖X‖² < ∞ 弱。 - A2(密度存在性):X 关于 Lebesgue 测度有密度(Theorem 4.6 需要,用于排除边界退化情形)。 - A3(支撑条件):#supp(X) ≥ k,保证 k-means 问题非平凡。 - A4(平衡约束):γₙ 满足 γₙ ≫ (log n)²(几乎必然收敛)或 γₙ ≫ (log n)⁴(excess distortion 收敛)。

相比已有文献的放宽/强化: - 放宽:矩条件从 E‖X‖² < ∞ 放宽到 E‖X‖ < ∞。 - 强化:要求 X 有密度(Pollard 1981 不需要);要求平衡约束 γₙ 的下界(经典结果无此约束)。

主要结果

结果 1(负结果,Example 4.2):存在分布(对称 Pareto(2)),满足 E|X| < ∞ 且总体 2-means 聚类中心唯一为 {−2, 2},但经验 2-means 聚类中心几乎必然不收敛到 {−2, 2}。具体地,几乎必然地,对无穷多个 n,任意经验最优聚类中心都包含一个绝对值 ≥ c√n/log n 的中心点。

结果 2(正结果,Theorem 4.6):若 X 有密度、E‖X‖ < ∞、#supp(X) ≥ k,且 0 < α < α₀(X)(α₀ 为总体最优聚类的最小概率质量),则 γₙ = αn 平衡的经验 k-means 聚类中心几乎必然在 Hausdorff 度量下收敛到总体最优聚类中心集合 𝒞ₖ(X)。

结果 3(正结果,Theorem 5.4):若 E‖X‖ < ∞、#supp(X) ≥ k,且 γₙ ≥ (log n)⁴,则平衡经验 k-means 的 excess distortion 几乎必然收敛到总体最优 excess distortion。

结果 4(统一框架,Theorem 5.5):在 E‖X‖ < ∞ 且 inf 有限的前提下,γₙ ≥ (log n)⁴ 的平衡 k-means 聚类中心可以分解为 Aₙ ⊔ Bₙ,其中 Aₙ 收敛到某个 𝒞ₖ′(X)(k′ ≤ k),Bₙ 发散到无穷。

证明路线与技术技巧

整体路线(以 Theorem 4.6 为例):

  1. 紧致化:先证明平衡约束下的经验聚类中心几乎必然有界。利用 γₙ = αn 的约束,每个聚类至少含 αn 个点,因此聚类中心的范数被 α⁻¹ · (1/n)Σ‖Xᵢ‖ 控制,而后者由 SLLN 收敛到 E‖X‖ < ∞。

  2. 连续性:证明 excess distortion 函数 D_X(· | C₀) 在 𝒞ₖ 上关于 Hausdorff 度量连续。这需要 Lemma 4.5(W₁ 连续性),其证明使用了 renormalization 技巧和 Skorokhod 表示定理。

  3. 经验过程控制:利用 VC 维理论(引理 5.3),对 k-means 目标函数的经验过程建立一致收敛界。关键技巧是将目标函数分解为"有界部分"和"尾部部分",尾部部分用截断处理。

  4. 对角化论证:结合紧致性、连续性和一致收敛,用标准的"ε-网 + Borel-Cantelli"论证得到几乎必然收敛。

关键技术技巧:

  • Renormalization(引理 2.1):通过减去 ‖X‖² 使目标函数在 E‖X‖ < ∞ 下良定义。这是全文的基石。
  • 截断 + 尾部控制(引理 5.3 证明):将样本按范数截断为"主体"和"尾部",主体部分用 VC 一致收敛,尾部部分用 Markov 不等式和矩条件控制。
  • Borel-Cantelli 的逆命题(Example 4.2 证明):利用独立性和 Σₙ P(极端事件) = ∞ 证明极端事件无穷多次发生。
  • 次序统计量的比值技巧(Example 4.2 证明):利用 Pareto 分布的次序统计量比值 X₍ₙ₎/X₍ₙ₋₁₎ 的分布,精确计算聚类中心的位置。

真实例子与应用

本文没有真实数据应用,但有一个关键的模拟例子(Figure 1.1):对对称 Pareto(2) 分布生成 n = 1 到 3000 个样本,计算精确的经验 2-means 聚类中心。模拟显示聚类中心在 n 增长时不断跳跃,且跳跃幅度与 √n/log n 同阶,直观验证了不一致性。作者还提供了计算精确 k-means 聚类中心的算法(Algorithm 1),利用 d=1 时的动态规划,时间复杂度 O(n log n)。

🔎 结论是否比证明窄

是。具体地:

  1. Theorem 4.6 要求密度假设,但作者在 Remark 4.7 中承认,这个假设可能不是必要的,只是证明技术需要(用于排除边界退化)。作者没有给出无密度假设下的证明或反例。

  2. Theorem 5.4 的 excess distortion 收敛只证明了"概率收敛"而非"几乎必然收敛"(虽然 Lemma 5.3 的证明实际上给出了几乎必然的界,但定理陈述只写了概率收敛)。作者在证明后的评论中提到"almost sure convergence can be obtained under slightly stronger conditions",但没有给出具体条件。

  3. 平衡约束的 α₀(X) 依赖分布:Theorem 4.6 要求 α < α₀(X),其中 α₀(X) 是总体最优聚类的最小概率质量。这个量在实际中不可观测,作者没有讨论如何自适应选择 α。

  4. k′ 的确定:Theorem 5.5 只保证 Aₙ 收敛到某个 𝒞ₖ′(X),但没有给出如何确定 k′ 的方法。作者在结论部分提到"it would be interesting to understand when k′ = k",但没有进一步分析。


四、开放问题

  1. α₀(X) 的自适应估计:Theorem 4.6 中的平衡参数 α 需要小于 α₀(X),但 α₀(X) 依赖未知分布。能否从数据中自适应选择 α,使得一致性仍然成立?(扎根于 Remark 4.7 和 Theorem 4.6 的陈述条件)

  2. 平衡约束的锐性:Theorem 5.4 要求 γₙ ≥ (log n)⁴,而 Theorem 4.6 要求 γₙ = αn。这两个条件之间的巨大间隙(多项式 vs. 对数)是否本质?是否存在 γₙ = (log n)^c 的临界指数 c,使得 c > c 时一致、c < c* 时不一致?(扎根于 Theorem 5.4 和 Theorem 5.5 的陈述)

  3. 无密度假设下的一致性:Theorem 4.6 要求 X 有密度。对于离散分布或奇异分布,平衡 k-means 是否仍然一致?作者在 Remark 4.7 中承认这是技术假设,但没有给出反例或替代证明。(扎根于 Theorem 4.6 的假设和 Remark 4.7)

  4. k′ 的确定与解释:Theorem 5.5 中,发散聚类中心的数量 k − k′ 如何确定?它与分布的尾部行为有何关系?能否给出 k′ 的显式刻画?(扎根于 Theorem 5.5 的陈述和结论部分的讨论)

  5. 有限样本速率:在平衡约束下,能否得到 excess distortion 的有限样本收敛速率?该速率如何依赖 γₙ、k、d 和分布的尾部指数?(扎根于 Lemma 5.3 的界和 Klochkov et al. 2020 的有限样本结果)

  6. 计算复杂性:平衡 k-means 的优化问题(1.3)在 d ≥ 2 时是否多项式时间可解?作者提到计算可归约为最优传输子程序,但没有讨论复杂性下界。(扎根于第 1.2 节的方法论讨论)

提示:要确认上述问题是否为真 gap,建议去读近 5 年关于 k-means 一致性的文献(如 Jaffe 2022, 2024; Klochkov et al. 2020 的后续工作),看是否已有解决这些问题的论文。如果多个近期工作都指向同一问题,那很可能是共识性的开放问题。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论