Weighted Conformal Clustering¶

会议: NeurIPS 2026
arXiv: 2606.00436
论文: arXiv OpenReview
领域: 优化/理论
关键词: 共形聚类、不确定性量化、加权共形预测、条件标签分布偏移、增强校准

一句话总结¶

针对传统聚类缺乏严谨不确定性度量以及校准标签由聚类算法生成导致可交换性被破坏的难题，本文提出加权共形聚类（Weighted Conformal Clustering），将聚类不确定性形式化为条件标签分布偏移问题，并通过单次拟合的增强校准机制消除留一法重计算开销，构建出具有有限样本统计覆盖保证且紧凑高效的置信集。

研究背景与动机¶

聚类分析是现代无监督学习中挖掘数据潜在分组结构的核心基础工具，在生物信息、图像处理以及社交网络等众多领域发挥着不可替代的作用。然而，当前几乎所有经典与现代聚类方法在执行完毕后，都仅仅输出每个样本属于某一簇的确定性硬划分（hard assignment），完全缺乏对其分配结果的严谨不确定性量化（uncertainty quantification）。在科研假说检验、医学诊断或高风险操作决策中，这种确定性输出极易掩盖处于聚类边界、重叠区域或低密度区域样本的固有模糊性。以往关于聚类不确定性的研究多局限于宏观结构层面，例如通过自助重抽样评估聚类中心方差、检验全局簇存在性与可分性、或是构建全局划分的贝叶斯可信集，却忽略了一个更为直接且关键的微观目标：针对任意单个观测样本的具体聚类分配给出统计有效的置信度量。

近期学者尝试将共形推断（conformal inference）引入聚类任务，旨在为测试样本构造具有有限样本、免分布假设覆盖保证的聚类标签置信集（置信集包含单个标签表示确定无误，包含多个标签则清晰标记模糊区域）。然而，分裂共形聚类（Split Conformal Clustering）面临一个根本性的理论困境：共形预测的标准有效性严格依赖校准数据与测试数据的可交换性（exchangeability），但在无监督聚类中，供校准使用的标签并非来自真实的潜在数据生成分布，而是由数据依赖的聚类算法人工合成的伪标签。这种合成标签机制不可避免地破坏了样本对之间的联合可交换性。现有方法只能将这种可交换性缺失视为不可控的误差源，强依赖聚类算法的替换稳定性（replace-one stability）和参数混合模型的光滑一致性假设来推导渐近覆盖界，不仅在有限样本下容易欠覆盖，而且在高维或复杂非线性流形下生成的置信集极度臃肿、信息量匮乏。

面对合成校准标签与真实潜在标签之间的本质脱节，本文的切入视角是跳出对可交换性的被动妥协，将无监督共形聚类重新概念化为一种非可交换设定下的「条件标签分布偏移」（conditional label-distribution shift）问题。核心 idea：通过引入基于似然比的加权共形预测框架纠正合成聚类标签与潜在真实标签的分布失配，并设计仅需单次聚类的「增强校准机制」消除昂贵的留一法重拟合开销，建立首个具有显式有限样本全变差误差界的实用加权共形聚类算法。

方法详解¶

整体框架¶

加权共形聚类的核心目标是为新输入的测试样本 $X_{n+1} = x$ 构建一个包含真实潜在聚类标签 $Y^*_{n+1} \in [K]$ 的紧凑置信集 $\hat{\mathcal{C}}(x) \subseteq [K]$，使其在预设显著性水平 $\alpha \in (0, 1)$ 下满足在最佳对齐排列 $\hat{\sigma}_o^*$ 意义下的边际覆盖保证 $\mathbb{P}(\hat{\sigma}_o^*(Y^*_{n+1}) \in \hat{\mathcal{C}}(X_{n+1})) \geq 1 - \alpha$。整个算法由训练划分拟合、测试点增强聚类、标签置换对齐、权重计算与加权分位数判别五个阶段构成：输入样本集被划分为训练集 $\mathcal{D}_{tr}$ 与校准集 $\mathcal{D}_{ca}$，在训练集上运行聚类并拟合软分类器估计真实条件标签概率；为了避免对校准集进行计算上不可行的留一法重复聚类，算法将测试点 $x$ 并入校准集构成增强集 $\mathcal{D}_{aug} = \mathcal{D}_{ca} \cup \{x\}$ 进行一次性聚类；随后通过最优化距离度量对齐增强聚类标签与训练分类器标签；最后利用真实条件密度估计与增强聚类软分配的似然比计算逐样本权重，根据相合性分数的加权经验分位数截断得到置信预测集。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入数据样本集与测试点 x"] --> B["训练/校准划分与软分类器拟合<br/>估计真实条件密度"]
    B --> C["增强校准机制<br/>并入测试点单次聚类"]
    C --> D["置换对齐与估计似然比权重构造<br/>校正条件标签分布偏移"]
    D --> E["加权相合性分数分位数计算"]
    E --> F["输出紧凑统计有效置信集 C(x)"]

关键设计¶

1. 条件标签分布偏移与理论预演：Oracle 加权共形预测

无监督聚类中用于校准的标签是由随机聚类算法 $\mathcal{A}_{\mathcal{D}}$ 生成的伪标签，其联合分布为 $\tilde{P}(dx, dy) = P_X^*(dx) \sum_{k=1}^K [\mathcal{A}_{\mathcal{D}}(x)]_k \delta_k(dy)$，而目标覆盖要求针对的是潜在真实数据联合分布 $P^*(dx, dy) = P_X^*(dx) \sum_{k=1}^K p^*_{Y|X}(k \mid x) \delta_k(dy)$。二者在协变量边缘分布上相同，但在条件标签概率上存在本质失配。若采用标准共形预测赋予每个校准点等权重，当合成标签与真实标签概率差距较大时必然发生严重欠覆盖。为在理论上达到精确覆盖，论文首先基于任意联合分布下的广义置换共形推断推导了 Oracle 权重。对于候选标签 $y \in [K]$，校准点与测试点的非归一化权重分别满足： $$ \tilde{w}i(y) \propto p^*}(Y_i \mid X_i) \left(\prod_{j \in \mathcal{I{ca} \setminus {i}} [\mathcal{A}{ca, {x}}^{-i}}(X_j)]}\right) [\mathcal{A{\mathcal{D}(x)]}^{-i}y, \quad \tilde{w}(y) \propto p^*}(y \mid x) \prod_{j \in \mathcal{I{ca}} [\mathcal{A}{ca}}(X_j)] $$ 归一化后的加权经验分布能够保证严格的有限样本覆盖 $\mathbb{P}(\hat{\sigma}_o^*(Y^*_{n+1}) \in \hat{\mathcal{C}}(X_{n+1})) \geq 1 - \alpha$（定理 1）。然而，该 Oracle 构造存在两大现实瓶颈：一是真实的条件标签密度 $p^*_{Y|X}$ 未知；二是每个校准样本 $i$ 的权重计算都要求在剔除 $X_i$ 并加入 $x$ 的留一集合 $\mathcal{D}_{ca, \{x\}}^{-i}$ 上重新运行一次聚类算法。这意味着评估单个测试样本就需要执行 $|\mathcal{I}_{ca}| + 1$ 次聚类拟合，这在大规模高维聚类中计算开销极其昂贵，且多次拟合还会引发不可控的簇标签随机漂移。

2. 增强校准机制（Augmented Calibration）：消除留一法重拟合负担

针对 Oracle 权重中留一法（leave-one-out）聚类带来的严重计算瓶颈，论文提出了极其巧妙的「增强校准机制」。该机制借鉴全共形（full-conformal）与分裂共形（split-conformal）的各自优势，将合成标签的生成过程直接定义在并入了测试点 $x$ 的增强协变量集合 $\mathcal{D}_{aug} := \mathcal{D}_{ca} \cup \{x\}$ 上。由于校准样本与测试样本在生成合成标签时均依赖相同的增强数据集 $\mathcal{D}_{aug}$，在置换联合似然的展开中，原本导致各样本相互耦合、需要留一拟合的复杂联合相乘项在分子分母归一化时作为公因子完全抵消！此时，原本复杂的 Oracle 权重神奇地简化为逐点的似然比形式： $$ \tilde{w}i(y) \propto \frac{p^*}(Y_i \mid X_i)}{[\mathcal{A{\mathcal{D}(X_i)]}{Y_i}}, \quad \forall i \in \mathcal{I}(y) \propto \frac{p^*}; \qquad \tilde{w{Y|X}(y \mid x)}{[\mathcal{A} $$ 增强校准机制将评估每个测试样本所需的聚类算法拟合次数从 }_{aug}}(x)]_y$|\mathcal{I}_{ca}| + 1$ 次骤降至仅需 1 次在 $\mathcal{D}_{aug}$ 上的聚类拟合，彻底打破了加权共形推断在聚类中落地的计算壁垒。同时，分子代表真实潜在标签的产生概率，分母代表增强聚类给出的软分配概率，直观清晰地表达了合成聚类对潜在标签的偏差校正系数。

3. 估计权重构造与软分类器标签对齐：有限样本覆盖误差界

在实际落地中，未知的真实标签条件密度 $p^*_{Y|X}$ 通过在独立训练集 $\mathcal{D}_{tr}$ 上拟合的软分类器 $\hat{\pi}: \mathbb{R}^p \to \Delta_K$ 进行估计，即令 $\hat{p}_{Y|X}(\cdot \mid x) = \hat{\pi}(x)$。由于 $\mathcal{D}_{aug}$ 上的聚类输出 $\mathcal{A}_{\mathcal{D}_{aug}}$ 与训练集分类器 $\hat{\pi}$ 之间存在无监督聚类固有的簇索引排列随机性，算法在校准阶段首先通过最小化概率单纯形上的距离度量 $\ell$ 来求解最优对齐置换 $\hat{\sigma}$： $$ \hat{\sigma} \in \arg\min_{\sigma \in \mathcal{S}K} \sum{ca} \cup {n+1}} \ell(\sigma(\hat{\pi}(X_i)), \mathcal{A}{aug}}(X_i)) $$ 该对齐仅利用协变量特征，严格杜绝了标签泄露。随后构建实际可计算的估计权重 $\hat{w}_i(y) \propto \frac{\hat{p}_{Y|X}(\hat{\sigma}(Y_i) \mid X_i)}{[\mathcal{A}_{\mathcal{D}_{aug}}(X_i)]_{Y_i}}$ 与 $\hat{w}(y) \propto \frac{\hat{p}_{Y|X}(\hat{\sigma}(y) \mid x)}{[\mathcal{A}_{\mathcal{D}_{aug}}(x)]_y}$。对于相合性分数 $S_i = s((X_i, \hat{\sigma}(Y_i)); \hat{\pi})$，置信集通过加权经验分位数截断得到。定理 2 建立了该实用算法的有限样本统计覆盖理论界： $$ \mathbb{P}\left(\hat{\sigma}o^(Y^(X}) \in \hat{\mathcal{C}})\right) \geq 1 - \alpha - \mathbb{E{tr}\mathbb{E}{X \sim P_X^}\left[ d_{\mathrm{TV}}\left(\widehat{P}{Y|X}(\cdot \mid X), P^(\cdot \mid X)\right) \right] $$ 这一理论界表明，算法的覆盖损失完全被软分类器在真实潜在条件分布上的全变差（Total Variation）估计误差所控制，既不需要强假设无监督聚类算法的替换稳定性，也不引入任何繁复的算法局部扰动项，当条件密度估计一致时即可渐近达到 $1-\alpha$ 的精确覆盖。

实验关键数据¶

主实验¶

论文在 5 成分高斯混合模型（GMM，$K=5$）的低维（$\mathbb{R}^2$）与高维（$\mathbb{R}^{50}$ 谱聚类）场景下进行了广泛的数值模拟，设定名义显著性水平 $\alpha=0.1$（目标覆盖率 $\geq 90.0\%$）。将本文 Algorithm 1（加权共形聚类）与前人提出的分裂共形聚类（Split CC）以及朴素截断法（Naive Cutoff）进行对比。

数据场景与设置	评估指标	本文 (Algorithm 1)	分裂共形聚类 (Split CC)	朴素截断 (Naive Cutoff)	表现差异分析
2D GMM ($\sigma^2=2.6, n=1200$)	经验覆盖率 (%)	90.4%	90.1%	90.0%	三者皆满足 90% 覆盖保证
2D GMM ($\sigma^2=2.6, n=1200$)	平均置信集大小	1.14	1.15	1.72	朴素截断法置信集显著冗余膨胀
50D GMM 谱聚类 ($\sigma^2=2.3, n=1200$)	经验覆盖率 (%)	90.2%	89.8%	89.5%	本文在小样本高维下即达标
50D GMM 谱聚类 ($\sigma^2=2.3, n=1200$)	平均置信集大小	1.52	3.68	4.25	本文置信集大小缩减 58.7%，信息量极高
50D GMM 谱聚类 ($\sigma^2=2.5, n=3000$)	经验覆盖率 (%)	89.9%	90.2%	90.1%	强噪声下均能保持名义覆盖率
50D GMM 谱聚类 ($\sigma^2=2.5, n=3000$)	平均置信集大小	1.94	4.12	4.70	Split CC 置信集过大失效，本文保持紧凑
50D GMM 谱聚类 ($\sigma^2=2.3, n=5000$)	平均置信集大小	1.21	1.34	2.85	大样本下 Split CC 才逐步逼近本文效率

消融实验¶

论文针对非线性流形（Three Moons 月牙集 $n=600$ 与 Concentric Circles 同心圆集 $n=400$）在图拉普拉斯谱聚类下的不确定性量化进行了深入消融分析，并展示了在 MNIST 深度聚类（10D 隐空间表征，$n_{test}=1000$）上的置信集结构分布。

实验任务与配置	噪声方差 $\sigma^2$	本文覆盖率 / 集合大小	Split CC 覆盖率 / 集合大小	机制表现与消融说明
三月牙 (Moons) 谱聚类	$\sigma^2 = 1.0$ (低散度)	91.2% / 1.02	91.0% / 1.03	两者在低噪声清晰流形下均给出单元素集
三月牙 (Moons) 谱聚类	$\sigma^2 = 1.8$ (中散度)	90.3% / 1.35	89.7% / 2.18	Split CC 置信集迅速变大，本文显著精简
三月牙 (Moons) 谱聚类	$\sigma^2 = 2.2$ (高散度)	88.6% / 1.81	81.4% / 2.75	跨流形高重叠下 Split CC 欠覆盖且集合发散
同心圆 (Circles) 谱聚类	$\sigma^2 = 0.75$ (低散度)	91.5% / 1.01	91.3% / 1.02	环状结构无缝分离，置信集几乎均为单点
同心圆 (Circles) 谱聚类	$\sigma^2 = 1.25$ (高散度)	89.8% / 1.64	84.1% / 2.46	本文通过似然比权重保持有效覆盖与高信息量
MNIST 深度自编码聚类	单元素集 (Size=1)	45.3% 占比	—	分布于簇核心腹地，无模糊的清晰手写数字
MNIST 深度自编码聚类	双元素集 (Size=2)	30.4% 占比	—	分布于簇交界带，多为 4 与 9、3 与 5 等易混淆数字
MNIST 深度自编码聚类	多元素集 (Size $\ge 3$)	24.3% 占比	—	位于流形重叠模糊区，人类肉眼亦极难分辨

关键发现¶

高维与非线性场景优势巨大：在 2D 线性混合模型等简单场景下，加权共形与 Split CC 表现相近；但一旦进入高维谱聚类或复杂非线性流形，聚类伪标签的失配被严重放大，Split CC 的置信集往往发散膨胀至接近全集（失去推断意义），而加权共形聚类通过精确的似然比校正，能够将置信集大小缩减 50% 以上。
收敛速率显著提升：在样本量消融中，本文算法在 $n=1200$ 时即可在高维谱聚类中实现严格名义覆盖与紧凑置信集，而 Split CC 需增大样本量至 $n=5000$ 以上才能逐渐达到可比紧凑度，大幅节约了标注前置样本的需求。
边界不确定性高度可解释：从 MNIST 与非线性热图分析可见，算法输出的置信集基数具有鲜明的几何与语义解释性——簇内部样本均为单元素集，边界及过渡区呈现双元素集，而书写极度畸变或结构破坏样本被稳健包络在 3+ 元素集中，极具实际质检与筛选价值。

亮点与洞察¶

将无监督可交换性破坏重塑为分布偏移问题：以往文献通常将聚类伪标签对可交换性的违背视作需极力压制的病态缺陷，本文打破这一思维定势，将其敏锐地抽象为统计学中成熟的「条件标签分布偏移」，并成功引入加权共形预测的强大工具箱，立意深远且理论闭环。
增强校准机制（Augmented Calibration）兼具理论与工程美感：通过在校准集内并入测试点进行单次拟合，化解了留一法联合似然展开中的跨样本依赖，使原本计算上不可行的组合权重神奇对消并退化为简单直观的单点似然比，这一技术创新可直接泛化至其他复杂的无监督或弱监督共形预测任务中。
理论覆盖界完全解耦算法稳定性：所推导的有限样本覆盖误差界仅由条件标签密度的全变差距离控制，不再夹杂令人头疼的聚类替换稳定性（replace-one stability）假设，极大拓宽了共形聚类对各类复杂聚类器（如深度聚类、核谱聚类）的适应边界。

局限与展望¶

依赖软分类器估计质量：定理 2 的覆盖界下界受全变差估计误差制约。如果数据潜在结构与基础分类器模型假设偏差极大（如严重模型误设定），导致训练集软分类器估计显著失真，置信集的实际覆盖率可能发生非微不足道的衰减。
硬聚类退化风险：若强行采用 k-means 等输出退化 one-hot 概率的硬聚类算法，分母软概率退化为狄拉克测度，无法平滑还原潜在的重叠边界分布，此时理论误差项不会自动渐近消除，因此方法强依赖具备概率输出能力的软聚类算法。
未来方向：探索在未知簇数量 $K$ 时的自适应共形聚类；进一步融合半监督少量先验约束以强化条件标签密度的估计精度；以及将增强校准思路扩展至因果聚类与图社区检测等更广泛的结构推断问题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将聚类伪标签的不确定性量化重塑为条件标签分布偏移，并首创单次拟合的增强校准机制，理论构思极具穿透力。
实验充分度: ⭐⭐⭐⭐☆ 涵盖 2D/50D GMM、非线性流形谱聚类及 MNIST 深度聚类，多维度覆盖率、置信集大小与定性热图对比翔实。
写作质量: ⭐⭐⭐⭐⭐ 逻辑演绎环环相扣，从 Oracle 困境自然推导至增强校准与估计权重，数学推导清晰优美。
价值: ⭐⭐⭐⭐⭐ 为无监督学习领域长期缺失的单点不确定性量化提供了真正可用、计算高效且兼具理论保证的里程碑式解决方案。

数据场景与设置	评估指标	本文 (Algorithm 1)	分裂共形聚类 (Split CC)	朴素截断 (Naive Cutoff)	表现差异分析
2D GMM (\(\sigma^2=2.6, n=1200\))	经验覆盖率 (%)	90.4%	90.1%	90.0%	三者皆满足 90% 覆盖保证
2D GMM (\(\sigma^2=2.6, n=1200\))	平均置信集大小	1.14	1.15	1.72	朴素截断法置信集显著冗余膨胀
50D GMM 谱聚类 (\(\sigma^2=2.3, n=1200\))	经验覆盖率 (%)	90.2%	89.8%	89.5%	本文在小样本高维下即达标
50D GMM 谱聚类 (\(\sigma^2=2.3, n=1200\))	平均置信集大小	1.52	3.68	4.25	本文置信集大小缩减 58.7%，信息量极高
50D GMM 谱聚类 (\(\sigma^2=2.5, n=3000\))	经验覆盖率 (%)	89.9%	90.2%	90.1%	强噪声下均能保持名义覆盖率
50D GMM 谱聚类 (\(\sigma^2=2.5, n=3000\))	平均置信集大小	1.94	4.12	4.70	Split CC 置信集过大失效，本文保持紧凑
50D GMM 谱聚类 (\(\sigma^2=2.3, n=5000\))	平均置信集大小	1.21	1.34	2.85	大样本下 Split CC 才逐步逼近本文效率

实验任务与配置	噪声方差 \(\sigma^2\)	本文覆盖率 / 集合大小	Split CC 覆盖率 / 集合大小	机制表现与消融说明
三月牙 (Moons) 谱聚类	\(\sigma^2 = 1.0\) (低散度)	91.2% / 1.02	91.0% / 1.03	两者在低噪声清晰流形下均给出单元素集
三月牙 (Moons) 谱聚类	\(\sigma^2 = 1.8\) (中散度)	90.3% / 1.35	89.7% / 2.18	Split CC 置信集迅速变大，本文显著精简
三月牙 (Moons) 谱聚类	\(\sigma^2 = 2.2\) (高散度)	88.6% / 1.81	81.4% / 2.75	跨流形高重叠下 Split CC 欠覆盖且集合发散
同心圆 (Circles) 谱聚类	\(\sigma^2 = 0.75\) (低散度)	91.5% / 1.01	91.3% / 1.02	环状结构无缝分离，置信集几乎均为单点
同心圆 (Circles) 谱聚类	\(\sigma^2 = 1.25\) (高散度)	89.8% / 1.64	84.1% / 2.46	本文通过似然比权重保持有效覆盖与高信息量
MNIST 深度自编码聚类	单元素集 (Size=1)	45.3% 占比	—	分布于簇核心腹地，无模糊的清晰手写数字
MNIST 深度自编码聚类	双元素集 (Size=2)	30.4% 占比	—	分布于簇交界带，多为 4 与 9、3 与 5 等易混淆数字
MNIST 深度自编码聚类	多元素集 (Size \(\ge 3\))	24.3% 占比	—	位于流形重叠模糊区，人类肉眼亦极难分辨