FALCON：一种基于成对约束的主动聚类的有效且稳健方法

《TRENDS IN FOOD SCIENCE & TECHNOLOGY》：FALCON : An effective and robust method for active clustering with pairwise constraints

　　

提出了一种新颖的基于成对约束的聚类框架，能够对全局数据分布进行建模；利用基于最大均值差异（Maximum Mean Discrepancy, MMD）的原型来构造超级实例（super-instance），并从中选取具有代表性的样本进行查询；通过见证函数（witness function）识别代表性不足或模糊的区域，从而制定细化策略；与现有主动聚类方法相比，FALCON在减少所需用户查询次数的同时，提高了聚类质量与稳健性。

研究背景与问题：聚类是无监督学习的基本任务，但在数据分布复杂、类别重叠或高维噪声场景下，传统方法如k-means和层次聚类难以产生准确划分。半监督聚类利用有限标签指导聚类，但标注成本高；基于约束的聚类以成对约束，即必连（Must-Link, ML）和禁连（Cannot-Link, CL）作为弱监督信息，比类别标签更灵活，但获取大规模代表性约束依然昂贵。主动约束聚类（Active Constraint-based Clustering, ACC）通过迭代选择最具信息量的约束来减少用户交互，然而现有方法多依赖局部不确定性或欧氏距离代表性，未显式建模全局数据分布，导致查询冗余、稀疏区域覆盖不足，且超级实例划分常基于局部凸簇假设。为解决这些不足，研究人员提出FALCON（Functional Active Learning with Constraints based on criticisms and Neighborhood prototypes，基于批评点与邻域原型的约束功能主动学习），将分布匹配与批评点驱动的细化相结合，统一处理代表性与不确定性。

研究内容与意义：研究人员基于MMD框架选择原型，用批评点识别未被当前原型充分表示的区域，并按约束对超级实例进行合并。在31个UCI真实数据集上，与COBRAS、ACDM、SPACE、DBSSHC、MPCKMeans-NPU和Kmeans++等基线比较，FALCON在聚类质量、鲁棒性和查询效率上均取得更优结果，Wilcoxon符号秩检验显示改进具有统计显著性。该研究为查询预算有限的交互式聚类提供了更实用的策略，能够最大化每次用户交互的信息收益。该研究成果发表于《TRENDS IN FOOD SCIENCE 》。

主要技术方法：研究方法包含三个关键部分。第一，基于MMD的原型选择：使用高斯径向基核（Gaussian RBF kernel）度量经验分布差异，通过贪心优化子模目标函数选择原型，并以欧氏最近原型划分超级实例。第二，基于批评点的细化：利用MMD的见证函数计算各点对原型分布的失拟程度，加入log-det正则化增强批评点多样性；选择包含批评点最多的超级实例进行分裂，并在其局部空间重新计算原型。第三，约束合并：新增原型按与已有聚类均值原型的距离排序，通过用户提供的ML/CL约束决定归属，并利用约束传递性减少重复查询。实验数据来自31个UCI真实数据集，特征均缩放到[0,1]。

研究结果：RQ1有效性：通过平均调整兰德指数（Adjusted Rand Index, ARI）和排位对齐（Aligned Rank, AR）指标，FALCON在所有查询预算区间均优于基线，且早期查询阶段即表现出较高效率，Wilcoxon检验p<0.01。RQ2鲁棒性：基于第4位归一化折损累计增益（NDCG-4）的排名质量分析显示，FALCON持续获得最高分数；固定σ时，FALCON在30%的查询预算设置上取得最佳ARI，在66%的设置上排名第一或第二；在Dermatology、Ionosphere、Pima等未获最优的数据集上仍保持稳定。RQ3效率：小数据集（少于2000个实例）和中低查询预算下，FALCON运行时间快于COBRAS，并可与ACDM竞争；大数据集上计算成本上升，但所需用户查询明显减少。其核矩阵只计算一次，复杂度为O(n²d)，每轮批评点计算复杂度为O(rnm)+O(r³)，其中r为批评点数，m为原型数。RQ4参数敏感性：σ₁显著影响早期查询性能，推荐取0.25；σ₂无显著影响，故默认σ₁=σ₂=0.25。超级实例细化方法：基于批评点密度的细化策略在全部查询范围内优于COBRAS采用的“最大超级实例优先”策略，证明应根据数据分布而非几何大小决定细化位置。消融研究：去除原型选择或去除细化机制均导致性能下降，说明两者互补；高斯RBF核优于拉普拉斯核（Laplacian kernel）和有理二次核（Rational Quadratic kernel）。

讨论与结论：讨论部分指出，FALCON将查询选择与基于数据分布的自适应细化相结合，避免在已良好建模区域浪费查询，使计算开销与用户交互成本达到更优平衡。研究结论可翻译为：本文提出FALCON，一种新颖的基于约束的主动聚类方法，旨在优化查询效率并保持高聚类质量。通过利用批评点和原型邻域，FALCON根据数据集分布策略性地选择用户约束，以代表性与不确定性混合的方式细化数据集中最具信息量的区域。该方法能够在最小化查询次数的同时取得最佳性能，特别适用于查询预算有限的场景。在31个数据集上的广泛评估表明，FALCON不仅在聚类质量上持续优于现有方法，还能最大化每次用户交互的收益，为实际应用提供了稳定且可靠的解决方案。