Page 202 - 《软件学报》2026年第5期

潘伟丰 等: 基于动态分析和引力公式的关键类识别 2081

3 相关研究

在过去的 10 多年中, 研究者提出了大量的方法用于识别面向对象软件 (主要是 Java 软件) 中的关键类. 这些
方法大致可以分为两类: 无监督学习方法和有监督学习方法.
无监督学习方法通常通过构建类粒度的软件网络, 进而构建评价类重要性的度量指标, 并通过对类的排序和
过滤实现关键类的识别. Zaidman 等人 [6,7] 通过设计软件运行场景 (execution scenarios) 来收集软件的运行轨迹, 进
而构建类依赖图, 并使用 HITS 算法计算类的重要性. Perin 等人 [13] 通过静态分析构建类依赖图, 并应用 PageRank
算法识别软件中的关键类. 周毓明等人 [8] 和王木生等人 [14] 使用类依赖图抽象类和类之间的依赖关系, 进而采用
PageRank、h 指数、a 指数等指标度量类的重要性, 并通过阈值识别关键类. Steidl 等人 [15] 提出了软件的依赖图模
型, 并使用 HITS、PageRank 等多种指标度量依赖图中类节点的重要性. Meyer 等人 [16] 将软件抽象为无权无向网
络, 并用 k-core 分解方法计算节点的核数 (coreness), 进而识别候选关键类. 姜淑娟等人 [18] 采用有限状态机模型来
表示软件系统, 并采用“唯一的输入/输出序列”来量化类的重要性. Pan 等人 [19] 提出了一种识别关键类的 ICOOK
方法. 该方法构建了类级加权有向软件网络模型, 并提出了一种一般化 k-core 分解方法来计算节点的一般化核数
(generalized coreness), 进而以一般化核数为类的重要性, 识别候选关键类. Şora 等人 [17,20] 基于 PageRank 算法及其
变体 (PageRankBR) 识别关键类, 并开发了一套关键类推荐系统, 旨在帮助新开发人员更快地理解项目结构. Do
Nascimento Vale 等人 [21] 基于对软件系统执行路径的动态分析, 提出了一个名为 Keecle 的半自动方法, 用于识别系
统中的关键类. Pan 等人 [10] 提出了一种基于多层软件网络的关键类识别方法 ElementRank. 该方法构建软件类级的
多层软件网络, 并使用 PageRank 算法计算每一层网络中类节点的重要性, 进而通过聚合类在各层的重要性值, 得
到类最终的重要性值. Liu 等人 [23] 提出了一种关键类识别方法 PageRankIVOL. 该方法在 PageRank 的基础上进一
步考虑了边权和网络节点数对重要性传递的影响. Pan 等人 [5] 在 PageRankIVOL 的基础上提出了一种关键类识别
方法 Pride. 该方法在随机跳转部分进一步考虑了网络中节点的度、加权度、网络的总度及总加权度的影响. Li 等
人 [22] 提出了一种识别关键类的 MinClass 方法. 该方法将软件抽象为类依赖网络, 并基于熵的概念构建了一个评价
类重要性的指标 OSE. Pan 等人 [24] 提出了一种关键类识别方法 iFit. 该方法构建了类级的加权有向网络模型, 并基
于 PageRank 算法和物理中场的概念提出了一个度量类重要性的指标 CG.
有监督学习方法依赖于度量指标集和机器学习技术构建分类器以预测关键类. Osman 等人 [25] 使用一组设计
指标 (design metrics) 刻画类的特征, 并将这些指标作为机器学习分类器的特征来训练关键类预测模型. Thung 等
人 [26] 构建了一组无权网络指标, 并与 Osman 等人的设计指标结合, 作为机器学习分类器的特征以训练关键类预测
模型. Yang 等人 [27] 提出了一种基于机器学习的关键类识别方法 MCCondenser, 从而将逆向工程得到的类图压缩
得更加紧凑. 周纯英等人 [28] 提出了一种基于图神经网络的关键类识别方法. 然而, 有监督学习方法依赖于带有标
签的数据集. 若一个系统不存在带标签的数据集, 则现有方法都将无法使用. 同时, 现有的数据集存在严重的“类不
平衡问题”. 例如, 在 jEdit 中, 关键类的数量仅占系统总类数的 0.641 6%. 这使得如何划分“训练集”和“测试集”成为
一个难题, 同时也限制了这类方法的发展.
本文提出的 CDAG 方法不依赖于带标签的数据集和机器学习算法来构建分类器, 因而属于无监督学习方法.
但是, CDAG 与现有的无监督学习方法又存在一些区别, 主要包括: 1) 现有工作基本都是依赖于类之间的直接依
赖关系来构建类重要性度量指标. 例如, h 指数 [8,14] 、a 指数 [8,14] 、核数 [16] 、一般化核数 [19] 之类的指标主要考虑了
节点本身的度 (直接相连的节点数) 或加权度 (直接相连的边上的权值和), 基于 PageRank 算法的指标 [5,10,13,15,17,20,23,24]
主要考虑了直接相连的节点之间的“投票”关系. 这些方法均未考虑没有直接边相连的两个节点之间的相互影响,
也未考虑“某个节点的邻居节点的度存在差异”的事实. 我们提出的 GEN 指标综合考虑了类之间的间接耦合和邻
居节点度分布的多样性对类重要性的影响, 因而可以更加全面地刻画软件网络中类节点的结构特征及类的重要
性. 2) 目前基于动态分析的关键类识别方面的工作极少 [6,7,21] , 且均未提供可复用的测试用例集, 也未提供测试用
例的获取方法, 导致工作的可重复性较差. 此外, 现有工作也未对动态获取的类集进行扩充, 存在缺失关键类的风
险. 我们提出的测试用例获取方法具有一定的普适性, 可用于后续动态分析相关的工作. 同时, 本文提出的类集扩