Optimized Algorithms for Text Clustering with LLM-Generated Constraints¶

会议: AAAI 2026
arXiv: 2601.11118
代码: https://github.com/weihong-wu/LSCK-HC
领域: AIGC检测 / 文本聚类
关键词: 文本聚类, LLM约束生成, k-means, 半监督聚类, 局部搜索

一句话总结¶

提出 LSCK-HC 框架，利用 LLM 生成集合形式的 must-link/cannot-link 约束（而非传统成对约束），配合带惩罚项的局部搜索聚类算法，在5个短文本数据集上实现与 SOTA 可比的聚类精度，同时将 LLM 查询次数减少 20 倍以上。

研究背景与动机¶

领域现状：短文本聚类 (STC) 是 NLP 的基础任务，k-means 及其变体被广泛使用。为提高聚类质量，半监督方法引入 must-link (ML) 和 cannot-link (CL) 成对约束作为背景知识。近年来 LLM 被用于通过 In-Context Learning 自动生成这些约束。
现有痛点：(1) 传统约束生成依赖专家手工标注或现有标签，成本高昂；(2) 用 LLM 生成成对约束（如 FSC 方法）需要大量查询（数万次），成本高且改善有限；(3) LLM 生成的约束可能含有错误，现有聚类算法未专门针对 LLM 约束的特性进行设计。
核心矛盾：成对约束的查询效率极低——每次 LLM 调用只判断两个点的关系，要覆盖足够的数据点需要指数级的查询量。同时约束中含有错误关系，硬约束满足和软约束惩罚的平衡尚未针对 LLM 输出特性做优化。
本文要解决什么？ (1) 降低 LLM 约束生成的查询成本；(2) 提高生成约束的准确性；(3) 设计容忍错误约束的聚类算法。
切入角度：将约束格式从成对扩展为集合——一次 LLM 查询可生成多个关系，并通过置信度阈值区分硬/软约束。
核心 idea 一句话：用集合形式约束替代成对约束以提升查询效率，用惩罚局部搜索容忍 LLM 生成的错误约束。

方法详解¶

整体框架¶

输入短文本集用嵌入模型（Instructor-large/E5）编码为向量。框架分两阶段：(1) 约束生成：选择候选点集，用 LLM 判断关系，生成 ML/CL 约束集合；(2) 约束聚类：用硬 ML 约束初始化聚类中心，软 ML 约束通过惩罚合并，CL 约束通过最大权匹配+局部搜索处理。

关键设计¶

集合形式的 Must-Link 约束生成:
做什么：一次 LLM 查询生成多个 ML 关系，而非逐对判断
核心思路：基于 coreset 技术将数据划分为代表性子集，每个子集内的点互相相似。将子集对应文本送入 LLM，LLM 返回分组结果（如 \(\{t_1, t_2, t_3\}, \{t_4\}\)），每个包含 2+ 文本的组构成一个 ML 集合约束
设计动机：coreset 保证选出的候选点不会在单一维度上差异过大，提高 LLM 判断的准确率；集合形式使单次查询覆盖多个约束关系
硬/软 ML 约束的置信度区分:
做什么：根据 LLM 反馈的一致性将 ML 约束分为高置信度（硬）和低置信度（软）
核心思路：在不同网格宽度级别 \(r_j = (1+\varepsilon)^j \cdot \sqrt{cost_{kc}/10n\delta}\) 上计算约束集合内的成对距离/直径，通过二分搜索找距离阈值 \(\psi\)。对每个候选阈值查询 LLM 多次（成对 5 次，集合 10 次），若所有响应一致），则低于该直径的 ML 约束为硬约束
设计动机：硬约束用于初始化阶段（影响 k-means++ 的种子选择），错误约束的危害更大，因此需要高置信过滤
Cannot-Link 约束生成:
做什么：生成集合形式的 CL 约束，大小不超过 \(k\)
核心思路：从距离当前 CL 集超过阈值 \(r = cost_{kc}\) 的未覆盖点中均匀随机采样候选点 \(q\)，由 LLM 判断 \(q\) 是否应加入当前 CL 集。若 LLM 返回 "None" 则加入，否则继续寻找下一个点，直到 CL 集大小达到 \(k\) 或无法找到新点
设计动机：距离阈值保证候选点确实来自不同簇，简化 LLM 的判断任务
带惩罚的 ML 聚类（Alg. 1）:
做什么：处理软 ML 约束的分配
核心思路：对每个软 ML 集合 \(X\)，先将点分配到最近中心，形成子分区。迭代选择最大直径的两个分区 \(P_i, P_j\)，比较合并成本与保持原分配+惩罚的成本——若 \((w_m + d(\bar{P_j}, c_j)) \cdot |P_j| + (w_m + d(\bar{P_i}, c_i)) \cdot |P_i| > \sum_{p \in P_i \cup P_j} d(p, c_{ij})\) 则合并。运行时间 \(O(nk^2)\)
带惩罚的 CL 聚类（Alg. 2）:
做什么：通过最大权匹配+局部搜索处理 CL 约束
核心思路：对每个 CL 集合 \(Y\)，构建辅助二部图 \(G(C, Y; E)\)，计算中心集与 CL 点间的最大权匹配。对匹配中的每个点计算其移除后的匹配变化量 \(g_y\)，若最大变化量低于阈值则接受当前匹配，否则移除该点分配到最近中心

损失函数 / 训练策略¶

本文是聚类算法而非深度学习训练。核心指标为 k-means 目标函数加上约束违反惩罚：\(\sum_{i=1}^{k} \sum_{x \in A_i} \|x - c(A_i)\|^2 + w_m \cdot (\text{ML violations}) + w_{cl} \cdot (\text{CL violations})\)。

实验关键数据¶

主实验¶

在 5 个文本数据集（Tweet, Banking77, CLINC-I, CLINC-D, GoEmo）上使用 Instructor-large 嵌入和 GPT-4o 生成约束。

数据集	约束比例	LSCK-HC ACC	PCK ACC	k-means++ ACC	提升(vs k-means++)
Tweet	40%	~68%	~65%	~62%	+6%
CLINC-D	40%	~78%	~75%	~74%	+4%
Banking77	20%	最佳	-	-	20% 约束比最优

查询效率对比（约束生成）¶

数据集	约束比例	FSC #Query	Ours #Query	倍数减少	FSC ML-RI	Ours ML-RI
Banking77-ML	2%	5260	91	57x	9.92%	96.42%
Banking77-ML	20%	26580	480	55x	11.40%	85.83%
CLINC-ML	2%	25095	91	275x	42.05%	96.25%
Tweet-ML	2%	13070	99	132x	50.00%	100.00%
Tweet-CL	20%	31485	821	38x	99.17%	99.56%

关键发现¶

查询次数减少 20-275 倍：集合约束格式是关键——单次查询覆盖多个关系
ML 约束质量大幅提升：FSC 的 ML 准确率在低比例时极低（Banking77 仅 9.92%），因其 ML 约束是从 CL 推理间接得到的；本文直接基于距离选择候选集，ML 准确率达 85-100%
20% 约束比为最佳甜区：更高比例导致错误约束增多且改善趋于饱和
较弱的嵌入模型（E5）从约束聚类中获益更大（ARI 提升近 10%），因为更低的基线留有更多纠正空间

亮点与洞察¶

从成对约束到集合约束是核心创新：不仅减少查询次数，还因为集合内点的相互验证提高了约束准确率。这个思路可迁移到任何需要 LLM 判断关系的半监督任务
硬/软约束分离策略：高置信约束指导初始化（k-means++ 对种子敏感），低置信约束通过惩罚柔性处理。这种分层信任策略适用于所有 LLM 生成标注的下游任务
局部搜索比 PCK 更鲁棒：PCK 在约束比超过 10% 后性能下降，而局部搜索通过惩罚-合并迭代保持稳健

局限性 / 可改进方向¶

仅在短文本聚类上验证，对长文档或多模态数据的效果未知
约束生成依赖嵌入空间的距离结构，若嵌入质量差则候选选择会退化
惩罚权重 \(w_m, w_{cl}\) 的设置缺乏自动调优机制
仅使用 GPT-4o 和 DeepSeek 两个 LLM，不同模型的约束质量差异未充分探索
固定 \(k\) 值假设——实际应用中簇数未知的情况更常见

评分¶

新颖性: ⭐⭐⭐⭐ 集合约束替代成对约束的思路简洁有效，硬/软约束分离匹配 LLM 特性
实验充分度: ⭐⭐⭐⭐ 5 个数据集、多个嵌入和 LLM 对比、查询效率和约束质量分析全面
写作质量: ⭐⭐⭐⭐ 形式化表述清晰，算法伪代码规范，但部分符号较密
价值: ⭐⭐⭐⭐ 对 LLM 辅助半监督学习的查询效率优化有普遍参考价值