
谢文波,博士,副教授,主要研究方向为数据挖掘、知识图谱.E-mail:wenboxie@swpu.edu.cn.
作者简介:
邓 涛,硕士研究生,主要研究方向为数据挖掘、机器学习.E-mail:dengtao209@163.com.
付 勋,硕士研究生,主要研究方向为数据挖掘、主动学习.E-mail:fuxun0529@163.com.
陈 斌,博士研究生,主要研究方向为数据挖掘、机器学习.E-mail:chenbin199817@gmail.com.
邹 甜,硕士研究生,主要研究方向为数据挖掘、机器学习.E-mail:tianz0520@gmail.com.
王 欣,博士,教授,主要研究方向为数据挖掘、数据库.E-mail:xinwang@swpu.edu.cn.
第二十七届中国科协年会学术论文
在现代数据分析与机器学习应用中,如何对新采样数据提取关键信息以进行高效分组、标注,是聚类算法面临的核心挑战之一.传统无监督聚类算法缺乏先验信息指导,难以满足复杂任务(如大模型预训练)对高质量数据的需求.主动学习方法可有效提升聚类精度,但高昂的人机交互成本和计算开销限制其实际应用.为此,文中提出基于改进最近邻图的主动聚类方法(Active Clustering with Tailored Nearest Neighbor Graph, ACNNG).ACNNG构造稀疏的最近邻图结构,刻画数据之间的关联.在该图的基础上,综合计算节点拓扑结构中心性和分组不确定性,有效识别关键数据点,并向用户寻求少量成对约束标注,显著提升聚类准确性.此外,ACNNG使用与最近邻图结构协作的高效标签传播机制,利用稀疏图结构实现低成本的标签扩展,大幅降低方法的时空复杂度,提升其在大规模数据处理中的可扩展性.在真实世界数据集与合成数据集上的实验表明,ACNNG不仅能利用较少的成对约束提高聚类准确性,而且运行时间较短,内存消耗较少,在实际场景中具有一定的应用潜力.
XIE Wenbo, Ph.D., associate professor. His research interests include data mining and knowledge graph.
About Author:
DENG Tao, Master student. His research interests include data mining and machine learning.
FU Xun, Master student. His research interests include data mining and active lear-ning.
CHEN Bin, Ph.D. candidate. His research interests include data mining and machine learning.
ZOU Tian, Master student. Her research interests include data mining and machine learning.
WANG Xin, Ph.D., professor. His research interests include data mining and databases.
Academic Papers of the 27th Annual Meeting of the China Association for Science and Technology
In modern data analysis and machine learning applications, how to extract critical information from newly acquired data for efficient grouping (clustering) and annotation remains a central challenge for clustering algorithms. Traditional unsupervised clustering algorithms struggle to meet the high-quality data requirements of complex tasks, such as pre-training large models due to the lack of prior information guidance. Active learning methods can effectively improve clustering accuracy, but their practical application is constrained by high human interaction costs and computational overhead. To address these issues, an algorithm of active clustering with tailored nearest neighbor graph(ACNNG) is proposed. A sparse nearest neighbor graph is constructed to model relationships between data points. Based on this graph, the topological centrality and uncertainty of data points are comprehensively computed to effectively identify key data points. A small number of pairwise constraints are collected from users to significantly enhance clustering accuracy. Furthermore, an efficient label propagation mechanism collaborating with the nearest neighbor graph structure is employed. By leveraging the sparse graph structure for low-cost label propagation, ACNNG substantially reduces the spatiotemporal complexity and improves scalability for large-scale data processing. Experiments on real-world and synthetic datasets demonstrate that ACNNG achieves higher clustering accuracy with fewer pairwise constraints, less runtime, and less memory consumption, showcasing its potential for practical applications.
近年来, 随着大数据和人工智能理论技术的快速发展, 聚类作为一种重要的无监督学习技术, 在挖掘和分析海量未标记数据中发挥着关键作用[1].聚类算法通过将相似数据自动划分为不同簇, 揭示数据的潜在模式.这一特性使得聚类广泛应用于数据挖掘[2]、图像处理[3]、生物信息学[4]等领域.
然而, 传统无监督聚类在缺乏领域专家指导的情况下, 通常难以获得高精度的聚类结果.为此, 研究者引入少量先验知识辅助聚类过程, 提出半监督聚类算法[5].半监督聚类通过部分人工标注数据, 指导算法更准确地捕捉数据内在结构[6, 7], 但随机选择样本进行标注往往导致标注效率低下, 并容易引入噪声或冗余信息[8].为了解决这一问题, 研究者将主动学习范式引入半监督聚类中, 提出主动聚类算法[9].主动聚类通过数据建模, 综合评估数据样本的分布中心性、代表性或不确定性等, 能大幅减少模型的不确定性, 提升聚类边界区分能力.向用户或专家问询后人工注解关键的未标记样本, 能以更少的先验知识 (用户约束) 获得更高的聚类精度.
在主动聚类中, 独立类标签[10]和成对约束是常见的用户约束形式[11].成对约束可分为必须连接约束(Must-Link)和不能连接约束(Cannot-Link), 分别表示数据实例应该或不能划分到同一簇中.在实际应用中, 成对约束以其标注便捷、专业性门槛较低、适用性较广而备受关注.例如:在人脸识别任务中, 判定两幅面孔是否属于同一人明显比标注具体姓名更容易[12].
尽管主动聚类在减少约束需求和降低人工成本方面具有显著优势, 但仍面临多重挑战.其中, 影响聚类效果的关键因素包括如何有效选取关键待询约束, 以及如何利用用户提供的约束信息优化聚类结果.目前, 待询约束的选取方法通常基于数据的中心性指标[13]和不确定性指标[8], 大多只依赖单一指标或简单的静态组合方式.如何设计更有效的新指标, 并动态融合多种指标, 实现更优的待询约束选取, 减少约束数量的需求, 这些尚需进一步探索.
另一方面, 虽然已有的聚类优化算法(如基于平面划分[14]、非负矩阵分解[15]和神经网络[16]等算法)能有效降低所需的标注数量, 但通常具有较高的计算复杂度.与传统半监督聚类的离线模式不同, 主动聚类是一个需要用户频繁参与的交互过程, 高计算复杂度必然导致响应时间过长, 用户等待时间延长, 人机交互体验受到严重影响, 制约主动聚类在实际大规模数据应用中的推广.此外, 现有算法中常见的辅助结构[14]内存开销较大, 这种额外的存储负担在处理大规模数据时尤其明显, 进一步制约算法的实际应用.因此, 如何在确保聚类准确性的同时提高算法的计算效率、降低存储开销, 实现算法的良好可扩展性, 成为主动聚类领域中亟待解决的重要问题之一.
针对上述挑战, 本文提出基于改进最近邻图的主动聚类方法(Active Clustering with Tailored Nearest Neighbor Graph, ACNNG), 利用数据最近邻关系改进最近邻图, 以较低空间开销解构数据之间的复杂关系, 并结合数据的中心性和不确定性从图中动态检测关键数据, 用于向用户请求成对约束标注.在聚类结果优化方面, 根据数据节点的中心性引入高效的标签传播方法, 保证标签分配的高准确度和低时空复杂度.在20个真实数据集和4个人工合成数据集上的系统性实验表明:ACNNG能在较少用户约束下显著提升聚类准确率, 具备良好的大规模数据适应能力, 同时具有较低的时空开销, 是一种可扩展的聚类工具.
主动聚类通过某种策略主动选择关键数据并向用户发起约束查询, 实现高效的聚类结果优化[17].其中, 如何选择查询数据是该类方法中关键问题之一.数据实例的中心性和不确定性是常用指标.
中心性实例能有效捕获数据模式, 并以此为依据指导聚类.Basu等[14]将数据进行预聚类, 划分初始聚类簇, 再通过人工标注细化调整簇信息.中心性方法虽然能探索数据的大致分布, 但仅凭高中心性难以达到理想效果[18].
相比之下, 不确定性方法通过检测簇间边界可提高算法准确性[19].Mallapragada等[20]提出Min-Max Strategy, 识别每个聚类中关键点的最小相似性, 检测高不确定性数据点.Xiong等[8]提出URASC(Uncertainty Reducing Active Spectral Clustering), 利用不确定性减少原则识别不确定点.Zhou等[21]提出SPACE(Self-Paced Active Clustering Ensemble), 结合自步学习和集成学习框架, 检测数据点的不确定性.
然而, 仅依赖中心性或不确定性的单一策略, 难以最大化主动聚类的性能.在此基础上, Shi等[22]提出ADP(Active Density Peak), 综合考虑中心性和不确定性, 使用一种静态两阶段策略:先使用高中心性数据点初步识别簇的分布, 再利用高不确定性点精细化处理簇间模糊区域.然而, ADP存在局限性:如果第一阶段的分布探索偏离实际分布, 后续细化处理可能无法达到预期效果, 甚至增加不必要的标注工作.
另一个制约主动聚类算法性能的关键问题是如何高效利用用户提供的约束信息优化聚类结果.该问题的核心在于在有限约束下实现对聚类结果的精细调整与增强.目前主要的聚类结果优化方法包括:基于邻域机制的方法、基于层次聚类的方法、基于向量空间优化的方法等.
基于邻域机制的方法使用邻域集合作为辅助结构, 通过用户标注, 将特定的数据点分配到相应邻域中.Xiong等[23]提出NPU(Normalized Point-Based Un- certainty), 在执行标签分配之前, 先选定一组约束以形成多个初始邻域, 再在已建立的邻域与不确定性较高的点之间构建成对约束.在迭代过程中利用用户标注约束更新邻域集合, 逐步提升聚类结果.在此基础上, Sousa等[24]利用成对约束的传递闭包特性改进NPU, 旨在聚类过程中自动调整最佳聚类簇的数量.然而, 为了达到理想的聚类效果, 上述方法通常需从邻域中生成近似于原始数据集平方数量级的成对约束, 大幅增加后续标签分配的计算和存储负担.为了支持聚类结果的动态调整与交互优化, Deng等[25]通过不确定性排序和数据点配对的策略, 选择不确定性较高的数据点, 并向用户发起询问后更新邻域.然而, 此方法往往依赖多轮迭代并涉及大量计算资源, 尤其是在标签分配与约束更新阶段, 频繁的距离计算会产生较高的时间开销, 严重限制算法扩展性.
基于层次聚类的方法在聚类树的各个层级进行系统性的精细调整, 提升聚类质量.van Craenen-donck等[26]提出COBRA(Constraint-Based Repeated Aggregation), 先通过k-means聚类生成多个超实例, 再采用自底向上的策略, 利用Must-Link聚合这些超实例, 优化聚类结果.van Craenendonck等[27]又提出COBRAS(Constraint-Based Repeated Aggregation and Splitting), 策略性地结合Must-Link和Cannot-Link, 利用超实例自顶向下分解和重组聚类.
基于向量空间优化的方法也是常见的聚类结果优化手段之一.Jia等[28]使用成对约束传播结合度量学习, 调整相似矩阵.Yin等[29]使用超图构建相似性矩阵, 利用成对约束调整超边的权重, 优化聚类结果.但上述方法在处理大规模数据集时也面临高内存消耗问题.其原因在于:方法需要存储数据点之间的成对关系, 通常占用O(n2)的空间开销, 限制其在大规模场景中的实用性.
定义1 改进最近邻图 给定数据集X={xi
E={(xi, xj), w(xi, xj)},
其中, w(xi, xj)表示边(xi, xj)的权重, 其值为xi、xj的欧氏距离.基于数据的多粒度最近邻关系构建改进最近邻图G, 可表示多粒度的嵌套聚类结果, 其中每个节点均可视为其子孙节点的代理节点.
定义2 成对约束 成对约束aij用于查询两个节点xi、xj是否属于同一个簇.如果xi、xj属于同一个簇, 定义
aij=(xi, xj, ML),
ML表示Must-Link; 如果 xi、xj不属于同一个簇, 定义
aij=(xi, xj, CL),
CL表示Cannot-Link.
定义3 邻域[22] 一个邻域包含一组已知属于同一类别的数据点.对于给定的数据集 X={xi
1)每个邻域Ni为数据集X的一个子集;
2)任意两个不同的邻域Ni、Nj(i≠ j)满足互斥性, 即Ni∩ Nj=Ø ;
3)如果数据点xa、xb属于同一邻域Ni, 即xa∈ Ni, xb∈ Ni, 则它们必定属于同一类别;
4)如果xc∈ Ni, xd∈ Nj, i≠ j, 则xc和xd一定不属于同一个类别.
定义4 不确定性[30] 给定数据点xi, 根据其在局部邻域内标签分布情况定义不确定性U(xi), 并结合信息熵[31]进行量化, 则
U(xi)=-
其中, η 表示xi前k个邻居节点中簇的数量,
U(xi)的值旨在量化数据点xi的不确定性程度:U(xi)值越大, 表明xi具有较高的不确定度, 指示其在局部区域内的类别归属呈现更大的模糊性.具体而言, 如果xi的k近邻集合中包含分属较多个不同预测类别的标签, 则xi的不确定性水平也相应较高.
定义5 中心性[32] 综合考虑节点度及与邻居节点关系紧密程度, 给定改进最近邻图G=(V, E), 节点xi的中心性如下所述:
C(xi)=D(xi)+∑xj∈Vi(wijW), (2)
其中, W表示改进最近邻图边集合E的权重之和, D(xi)表示节点xi的度, Vi表示节点xi在G中邻接点的集合, wij表示xi、xj之间边的权重.
中心性度量的核心策略是, 度数大的节点中心性高.当存在多个度数并列最高的节点时, 需要进一步细化中心性的度量.可结合节点连边的最大聚合权重决策, 这样不仅确保代表节点具有最多的连接, 还能保证这些连接在整体图结构中的重要性.
本文提出基于改进最近邻图的主动聚类方法(ACNNG), 整体框架如图1所示.ACNNG综合评估节点的中心性和不确定性, 旨在识别并改进最近邻图中的关键节点, 并有效利用成对约束标注提升聚类效果.
ACNNG具体工作流程包括如下步骤.
1)分析数据点之间的最近邻关系, 构建改进最近邻图(Tailored Nearest Neighbor Graph Construc-tion, TNNG-Construction).
2)基于改进最近邻图, 计算每个节点的中心性和不确定性, 检测关键节点(Essential Node Detec-tion, EN-Detection), 这些节点在后续的聚类任务中起到重要作用.
3)进入人机交互(Human Machine Interaction, HM-Interaction)环节, 通过人工标注, 使用邻域机制分类关键节点, 为数据提供先验知识支撑.
4)分类完成后, 采用标签传播(Label Propaga-tion, L-Propagation)更新节点标签, 扩散已有标签, 提高聚类的覆盖范围和准确性.
5)根据标签传播的结果重新计算节点的不确定性(Uncertainty Information Recalculation, UI-Recal-culation), 为下一轮关键节点检测提供更准确的参考信息, 从而不断优化聚类效果.
ACNNG整个流程旨在通过循环迭代, 逐步提升聚类的准确度与可靠性.
输入数据X={xi
算法1概述ACNNG的整个流程.
算法1 ACNNG
输入 原始数据集X, 迭代轮数Λ , k近邻参数k.
输出 聚类结果L
U← 0, N← Ø ;
G← TNNG-Construction(X);
for t← 1 to Λ do:
I← EN-Detection(U, G);
N← HM-Interaction(I, N, X);
L← L-Propagation(G, N);
U← UI-Recalculation(L, k);
end for
本文构建改进最近邻图的动机是探索数据内在结构和分布模式, 从而确保更准确、高效地定位聚类中需要正确分配的节点, 在人机交互开始之前, 减少潜在的节点对比较次数.
本文采用多粒度最近邻连接的方法构建稀疏、连通的最近邻图.首先将改进最近邻图进行初始化操作,
G← (V=X, E=Ø ).
节点集V≅X, 并将改进最近邻图的边集合初始化为空集, 即初始状态下, 节点之间不存在任何连接.再通过
E=
迭代更新改进最近邻图中边的集合E.
在每轮迭代中, Ri表示第i轮迭代中所有代表点的集合, Λ 表示迭代的总轮次.在首轮迭代中, 初始代表点集合设定为R0, 此时将集合X中的所有数据点视为初始代表点, 纳入代表点集合.随着改进最近邻图构建的迭代的进行, 在每轮迭代中, 各代表点xi寻找其最近邻代表点δ i, 连接后, 添加到边集合中, 逐步构建改进最近邻图的拓扑结构.在每轮迭代过程中, 会存在多个连通子图S={S1, S2, …}.在每个连通子图中, 依据式(2)从连通子图的所有节点中选出一个节点作为代表点.迭代过程持续进行, 直至|R|=1, 即改进最近邻图构建完成.
改进最近邻图构建步骤如算法2所示.
算法2 改进最近邻图构建
输入 原始数据X
输出 改进最近邻图G
G← (V=X, E=Ø );
while |R|> 1 do:
for each代表点xi in R do:
E← E∪ ((xi, δ i), w(xi, δ i));
end for
R← Ø ;
for each 连通子图 Sj in S do
R←R∪argmaxxi∈Sj(D(xi)+∑xj∈Vi(wijW));
end for
end while
return G
改进最近邻图构建过程如图2所示.在初始阶段, 所有节点均作为代表点, 如(a)所示.随后, 每个代表点与其最近的代表点建立连接, 这一步骤形成若干连通子图, 如(b)所示. 接下来, 在每个连通子图内部, 根据式(2)选择中心性最大的节点为新的代表点, 如(c)所示.随着循环进行, 代表点的数量规模不断缩小, 当图中仅剩一个代表点时标志改进最近邻图构建完成, 如(d)所示.
在主动学习中, 数据实例的选择主要受到最大化信息增益和最小化模型不确定性等双重目标驱动.一种常用策略是不确定性选择, 即模型在当前聚类结果下查询具有最高不确定性的数据.本文提出的关键节点检测以批次方式进行选择, 重点在于不确定性和中心性.中心性通过式(2)在改进最近邻图中进行评估, 不确定性由式(1)在每轮标签传播结果上进行更新.
在算法的初始(第一轮)迭代中, 由于尚未进行标签传播, 所有节点的不确定性均初始化为0.因此, 该阶段的关键节点选择仅依据其中心性, 旨在初步探明簇的基本结构.进入后续迭代后, 通过在每轮执行标签传播以动态更新节点的不确定性.此时, 关键节点的选择将综合考量中心性与更新后的不确定性, 可更聚焦于识别簇间模糊区域并优化对整体簇分布的探索.算法设定迭代次数为Λ , 每轮从节点集合X中按比例选择
Ω t=
个关键节点.迭代至第Λ 轮后结束, 确保考察所有节点.依据不确定性U(xi)和中心性C(xi)选择关键节点.当有足够数量节点的不确定性大于0时, 优先选择这些节点直至满足条件的节点数量为Ω t; 当不确定性大于0的节点数量不足Ω t时, 选择中心性大的节点作为补充节点.在每轮检测后, 将选定节点的不确定性和中心性设为固定值0, 防止后续重复选取.
关键点检测示例如图3所示.图中圈内节点的不确定性均大于0.在某一次关键节点检测操作中, 若不确定性大于0的节点数量小于Ω t, 则针对剩余节点将以中心性作为检测标准.
例如:对于位于核心区域的点A和位于边缘的点B, 尽管它们的不确定性均为0, 但是点A因其位于核心区域对探索聚类簇整体分布具有更高的价值.在簇间模糊区域的节点已被选择之后, 选择点A有助于在标签传播过程中更准确理解数据分布.因此, 将中心性较高的节点纳入选择能有效支持对簇整体分布的探索.
针对关键节点检测中识别的关键节点集I, 为了降低人工标注负担, 使用人机交互优化流程[22], 核心在于构建一个有序查询列表.该列表由每个邻域内距离目标实例最近的实例组成, 并按距离升序排列.用户依据此列表提供的优先级进行成对约束标注, 将关键节点分配至正确的邻域, 完成邻域更新.具体而言:人机交互的输入包括由关键节点检测生成的关键节点集合I、多组邻域N、原始数据集X.算法的输出是将集合I中的每个关键节点插入N中形成的新邻域.
具体步骤如算法3所示.
算法3 人机交互
输入 检测的关键点集合I, 邻域集合N,
原始数据集X
输出 插入关键点后的邻域N
1.for each 关键节点 xi in I:
2. Q← Ø ;
3. for each Ni in N:
4.
5. Q← Q∪
6. end for
7. Q← ascending(Q={
8. for xl in Q:
9. 标注xi、xl的成对约束关系;
10. If (xi, xl, ML) then Nl ← Nl∪ {xl}; break;
11. end for
12. If 没有出现must-link:
13. N← N∪ {xi};
14. end if
15.end for
16.return N
首先, 遍历每一个关键节点(第1行).对于每一个关键节点xi, 算法初始化一个空集Q, 用于存储每个邻域Ni中距离xi最近的点
标签传播旨在通过扩散邻域的标签信息, 发现未知的聚类并降低局部不确定性.同时本文基于扩散模型传播标签, 相比文献[14]方法, 避免重复计算成本较高的半监督聚类, 使聚类结果的更新更高效.
标签传播具体步骤如算法4所示.
算法4 标签传播
输入 改进最近邻图G=(V, E), 一组邻域N
输出 标签传播结果L
1.通过每个邻域各自的标签激活N中的节点;
2.for each邻域 Ni in N:
3. while |Ni|> 0 do:
4. 删除Ni中最后一个节点xj;
5. for each 未被激活的节点 xl in Vj do:
6. if C(xl)< C(xj) then:
7. 使用Ni的标签激活 xl;
8. Ni← Ni∪ xl;
9. end if
10. end for
11. end while
12.end for
13.抽取所有被激活节点的标签, 得到标签传播结果L;
14.return L
标签传播的输入由改进最近邻图G=(V, E)和一组邻域N构成, 输出是标签分配的结果集L.算法4首先通过每个邻域各自标签激活本邻域中的所有节点(第1行).然后, 算法遍历每个邻域Ni, 对每个邻域执行标签传播过程(第3~12行).具体到单个邻域Ni, 如果此邻域的规模大于0, 循环:首先删除邻域中最后一个节点xj(第4行), 再将xj的邻接点Vj中中心性小于C(xj)的节点激活, 并加入Ni中(第5~9行).这样依次循环迭代, 直至|Ni|=0.当遍历完所有的邻域后, 抽取所有节点的标签, 得到标签传播的结果(第13行).
标签传播过程示例如图4所示.初始时, 邻域
N={{A}, {G}, {K, F}}
的所有节点被激活, 如(a)所示.然后, 以邻域{xA}为源点的标签传播启动, 邻接节点xB、xD、xC、xG、xF成为传播的候选目标.已被激活的节点xG、xF不受标签传播的影响.由于xB、xD、xC未被激活, 且其中心性小于xA, 满足传播条件, 所以这3个节点接受此邻域的标签, 如(b)所示.在第二轮传播中, 传播源的邻接节点只有节点xE, 同样符合传播条件, 因此也接受此邻域的标签, 如(c)所示.至此, 以{xA}为源点的传播过程完成, 最终形成的标签传播结果如(d)所示.
在每轮主动聚类的迭代过程中, 为了确保聚类结果的准确性和稳定性, 需要重新评估未被检测点的不确定性.这是因为随着标签传播过程的不断推进, 每轮迭代后的标签分配结果会发生动态变化, 导致不确定区域的界定也呈现动态演化的特性.因此, 为了有效应对这一挑战, 必须在每次迭代后及时评估并更新不确定性区域.具体而言, 对于给定的节点xi, 在每次对数据标签进行重新分配后, 需要通过式(1)计算并更新节点xi的不确定度, 从而有效衡量局部区域内的混乱程度和精准界定不确定区域.这一过程不仅有助于提高聚类过程的精确性, 而且能进一步优化聚类结果的稳定性和可靠性.
改进最近邻图的构建是迭代进行的, 关键操作是利用ball-tree技术寻找每个代表点的最近代表点.由于每次迭代后, 代表点的数量最多为上轮迭代的一半(在最坏情况下, 每次迭代形成的连通子图仅由两个点构成).因此, 在给定数据集样本量为n时, 该部分的时间复杂度为
T1=n log n+
在人机交互循环中, 设迭代次数为Λ , 每轮循环检测n/Λ 个关键数据点.在将关键点插入邻域时, 需要进行距离计算, 找出每个邻域中与待插入点xi的最近点.若某邻域包含m个点, 此操作的时间复杂度为O(m log m).此外, 每个邻域选出的点还需根据与xi的距离进行排序, 时间复杂度为O(c log c).
以下为两个极端情况.
1)m=n, c=1.此时所有数据点都属于同类.在插入过程中, 邻域中找寻最近邻点的时间复杂度为O(m log m), 排序的时间复杂度为O(1).由于邻域的规模由0增至n,
T2=
可认为T2介于O(n log n)和O(n2)之间.
2)m=1, c=n.此时所有数据点都属于不同类别.每次迭代找寻最近邻的时间复杂度为O(1), 排序时间复杂度为O(m log m),
T2=nO(1)+
T2同样介于O(n log n)和O(n2)之间.所以, 人机交互循环的时间复杂度在最坏情况为T2=O(n2).
每轮人机交互循环会在改进最近邻图上执行一次标签传播.改进最近邻图由n个节点和n-1条边构成, 每个邻域会从内向外进行扩散, 所以每轮标签传播的时间复杂度为O(n).考虑在最坏情况下, T=|X|, 即每轮循环只会选取一个关键点, 则总的时间开销T3=O(n2).
由此, 在最坏情况下ACNNG时间复杂度描述如下:
T=T1+T2+T3=O(n log n)+O(n2)+O(n2)∈ O(n2).
ACNNG的内存占用集中在改进最近邻图和邻域存储上.改进最近邻图由n个节点和n-1条边构成, 空间复杂度为O(n).随着算法运行, 邻域规模逐渐增大.在最坏情况下, 邻域包含n个数据点, 即邻域的空间复杂度为O(n).所以, ACNNG的空间复杂度为O(n).
下面对比ACNNG与目前性能较优方法的时空复杂度, 具体对比方法如下:URASC[8]、文献[14]方法、文献[18]方法、文献[20]方法、SAPCE[21]、ADP[22]、NPU[23]、文献[25]方法、COBRA[26]、CO-BRAS[27]、文献[28]方法.各方法的时空复杂度如表1所示.在表中:n表示数据规模, Δ 表示成对约束标注次数; NPU和文献[25]方法中t表示随机森林数量; COBRA中Ns表示初始化超级点的数量; 在SAPCE中, m表示基本分区数量, c表示真实的簇数量, τ 1表示内循环次数, τ 2表示外循环次数.为了确保聚类准确率达到百分之百, 需要提供充足的成对约束标注.在这种情况下, 如本文所述, 当开展时间复杂度分析时, 在考虑标注数量的情况下, 为了与对比方法的时间复杂度进行统一对比, 使用Δ 表示约束标注数量, 且趋近于n.在SPACE中, 需要根据迭代收敛条件确定τ 1, 随着数据规模的增加, τ 2的增长呈现非多项式的特性.由表1可见, ACNNG的时空复杂度最小.
![]() | 表1 各方法的时空复杂度对比 Table 1 Comparison of time and space complexity among different methods |
本文选择在20个来自UCI仓库(
![]() | 表2 实验数据集基本信息 Table 2 Basic information of experimental datasets |
本文使用调整兰德指数(Adjusted Rand Index, ARI)[33]作为聚类准确性的评价指标.ARI衡量聚类结果与真实类别标签之间的相似性, 取值范围为[-1, 1], 值越大表示聚类效果越优, 与真实情况越接近.ARI计算公式如下:
ARI=
其中RI(Rand Index)表示兰德指数, E(RI)表示在随机模型下RI的期望值, max(RI)表示RI的最大可能值.
实验测试设备是一台操作系统为Windows11, 配备3.9 GHz CPU和32 GB RAM的标准个人计算机, 实验代码采用Python编写.
参数设置如下:ACNNG循环轮数Λ =100, k=14.对比方法使用原文献推荐参数.实验运行10次, 结果取平均值.
在不确定性计算时用于限定局部区域最近邻数量的参数k是ACNNG中一个重要参数.为了评估k, 设置k=2, 3, …, 31.
ai(k)表示在第i个数据集上并在特定参数k下聚类完全正确(ARI=1)所需的成对标注数量.当ACNNG在相同数据集上设置不同规模k的ARI达到1时, 基于此数据集总的标注结果为:
Ai={ai(k=2), ai(k=3), …, ai(k=31)}.
由于标注的数量不同, 计算ai(k)与
biasi(k)=
越小的标度偏差表明ACNNG在此k值下能达到最优聚类效果所需成对标注数量越少.
k不同时在16个小型数据集上的标度偏差如表3所示.表中黑体数字表示最优值.由表可见, ACNNG在k=14时达到最优效果.因此, 在后续实验中, k=14作为ACNNG的默认推荐参数.
![]() | 表3 k不同时标度偏差对比 Table 3 Comparison of scaled bias with different k |
4.3.1 对比方法
为了验证ACNNG的有效性, 选取如下方法.
1)基于不确定性的主动聚类算法.
(1)SPACE[21].结合自步学习和集成学习, 检测不确定性较高的点, 以此进行主动聚类.
(2)ADP[22].基于密度峰, 从决策图中检测点的中心性, 并选择不确定性较高的节点细化聚类.
(3)ADPE[22].是ADP的改进版本, 使用集成学习的方法, 增加不确定性估计的准确性.
(4)A3S(Adaptive Active Aggregation and Spli-tting)[34].通过自适应聚类算法获得初始的聚类结果, 在归一化互信息增益指导下迭代聚合和分裂簇, 优化聚类结果.
2)基于代表性的主动聚类算法.
(1)文献[14]方法(后文简记为FFQS).选择最远的点作为种子点, 确保每个聚类至少拥有一个代表点, 形成聚类的基础骨架.然后, 随机选择非骨架数据点, 并将其与骨架中的数据点进行对比查询.
(2)文献[20]方法(后文简记为MinMax).在FFQS的基础上, 通过最小最大准则优化查询选择过程, 最小化聚类错误, 提高聚类的准确度.
(3)COBRAS[27].基于层次结构分析, 采用自顶向下的策略, 从单个代表点开始, 不断通过连接和断开操作新增代表点, 细化聚类结果.
3)半监督聚类算法SSE(Semi-supervised Clus-tering via Structural Entropy)[35].整合来自不同来源的多种约束, 结合基于结构熵的目标函数, 提升半监督聚类准确性.
4.3.2 UCI数据集
在20个数据集上进行对比实验.在实验过程中, 对于方法的运行设定明确的终止条件:运行时间不超过48 h且内存使用不超过 32 GB.任何方法若在运行过程中超出上述限制, 将被判定为无法在该数据集规模下完成计算.
各方法聚类性能随着约束标注数量的增加而呈现的动态变化如图5所示, 由图可见, ACNNG在多个数据集上ARI值较高, 普遍领先于对比方法.随着标注数量的增加, ACNNG的ARI值持续稳定提升, 但是SSE、COBRAS和FFQS在部分数据集(如wine、breast、banknote)上出现波动, 这可能是由于某些约束标注对方法造成干扰.
![]() | 图5 各方法聚类性能随约束标注数量的变化曲线Fig.5 Curves of clustering performance for different methods with varying numbers of constraint annotations |
同时图5显示, MinMax和FFQS无法处理4个较大规模数据集, 而SSE、ADPE和SPACE在处理EEG数据集时也遇到性能瓶颈.在digits、har数据集上, 只有ACNNG在设定的运行时间和内存消耗限制下成功完成聚类任务, 表明其在处理大规模数据集时的优越性.
为了进一步量化评估各方法利用监督信息的效率, 对比各方法在给定约束标注数量下的聚类质量.相同约束标注数量下, ARI值越高说明方法越有效利用监督信息.
给定约束标注数量, 各方法ARI值对比如表4所示:N/A表示该方法运行时间或空间消耗超过实验限制, 黑体数字表示最优值.
![]() | 表4 各方法在给定约束标注数量下的ARI值对比 Table 4 ARI value comparison of different methods under varying constraint annotation quantities |
由表4可见, 在大多数情况下, ACNNG在相同约束标注数量下均能取得更高的ARI值, 持续优于对比方法.
同时, 如在各数据集上结果的最后一行所示, ACNNG利用更少的约束标注即可达到完美聚类效果(ARI=1), 这进一步验证ACNNG能有效利用监督信息优化聚类结果.
为了验证ACNNG是否在统计学意义上显著优于对比方法, 还对表4结果进行非参数统计检验.首先, 采用Friedman检验, 判断不同方法之间是否存在显著的统计学差异.为了保证实验的公平性, 选取16个小型数据集, 避免在大型数据集上可能存在的实验结果缺失值造成的偏差.零假设(H0)检验所有方法具有相同的平均性能, 而备择假设(Ha)表明至少有两种方法的性能存在差异.基于各方法的ARI值进行排序后, Friedman检验得到的检验统计量Q=208.067, 对应的p=2.105× 10-17, 这验证不同方法之间存在显著差异(p< 0.05).随后进行Nemenyi后续检验, 进一步区分各方法之间的差异.
各方法平均排名的临界差异图如图6所示, 由图可见, ACNNG的平均排名为1.367, 显著优于对比方法.
4.3.3 合成数据集
在广泛使用的Agg、blobs、Flame、moons二维合成数据集上对ACNNG、ADPE[22]和COBRAS[27]的聚类过程展开深入探究.具体可视化结果如图7所示, 在图中, 红色线段表示Cannot-Link, 黑色线段表示Must-Link.
由图7可见, ACNNG选取约束具有两个特点:1)利用源自簇骨架的约束获取形状信息:2)利用源自簇边界关键区域的约束明确聚类边界.所以进行相似规模的标注, ACNNG在多数情况下能使用较少标注, 取得较高的ARI值.在blobs、Flame数据集上, 随着标注次数的增加, ADPE性能并未得到显著提升, 这是因为ADPE在标签传播过程中, 不确定性区域的变化并不明显, 并且无法动态探索簇的分布.在moons数据集上, 仅增加10次成对标注时, COBRAS的ARI值从0.061提至0.947.这表明新增的10次成对标注对于分割簇起到关键作用.然而, 这也揭示COBRAS在某些情况下可能在初始阶段未能有效识别关键点.相比之下, ACNNG表现出更强的鲁棒性和准确性.
在增量人工数据集上验证ACNNG的计算效率.该增量数据由Python工具包sklearn生成, Agg、blobs、Flame、moons合成数据集的维度均为10, 数据样本数依次为1 000、2 000、5 000、10 000.各方法在不同数据规模下的响应时间对比如图8所示.在对数尺度下, 直线的斜率表示响应时间的增长率, 增长率越小, 方法的时间性能越优.
![]() | 图8 各方法在不同数据规模下的响应时间对比Fig.8 Comparison of response time among different methods with various data scales |
由图8可见, 除了SPACE呈现出非线性增长趋势以外, 其它方法的响应时间均遵循幂律函数, 并以直线形式呈现.ACNNG的增长率为1.75, 低于对比方法, 显示出其在计算效率方面的优势.
为了评估方法的可扩展性, 在不同规模的合成数据集上对内存占用与响应时间进行对比, 结果如图9所示.
由图9可见, ACNNG的数据点集中分布于图的左下区域, 表明其在响应时间和内存效率上均有优越性.此外, 如图5所示, 在waveform、digits、EEG、har这4个大型数据集上, ACNNG表现出稳定的性能提升, 验证其具备处理大规模数据的能力.
为了解决主动聚类算法中存在的人工标注需求量较大和处理大规模数据集时计算开销较高等问题, 本文提出基于改进最近邻图的主动聚类方法(ACNNG), 能有效减少人工标注需求且具有良好的可扩展性.理论分析和实验研究表明, ACNNG通过构建改进最近邻图的方式, 以低时空复杂度精准捕捉数据点间复杂关系, 同时结合中心性与不确定性对关键数据进行动态检测.在标签传播阶段, 利用数据点的中心性, 设计标签传播机制, 准确完成标签重分配, 高效优化聚类结果.最终, ACNNG可提升聚类准确度及优化算法的可扩展性, 为处理大规模数据集的主动聚类问题提供一种高效精准的解决方案.今后的研究将致力于解决更大规模数据的聚类问题, 并探索通过并行计算技术进一步提升ACNNG的运行效率.
本文责任编委 高阳
Recommended by Associate Editor GAO Yang
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|
[13] |
|
[14] |
|
[15] |
|
[16] |
|
[17] |
|
[18] |
|
[19] |
|
[20] |
|
[21] |
|
[22] |
|
[23] |
|
[24] |
|
[25] |
|
[26] |
|
[27] |
|
[28] |
|
[29] |
|
[30] |
|
[31] |
|
[32] |
|
[33] |
|
[34] |
|
[35] |
|