本发明涉及一种软件缺陷关联规则网络剪枝方法及系统，属于软件缺陷预测技术领域，解决了现有关联规则网络未考虑有无缺陷的双目标且关联规则存在冗余的问题。包括读取软件缺陷数据集，基于关联规则算法生成初始关联规则集合；基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷字典和无缺陷字典；获取同时存在于两个字典的节点，在反向超图中去除节点的冗余边，更新字典中节点层级，得到关联规则网络；基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区；分别根据社区中的缺陷标签和节点所属字典，从多个社区中提取出用于软件缺陷预测的关联规则。实现了软件缺陷关联规则的准确提取。
1.一种软件缺陷关联规则网络剪枝方法，其特征在于，包括如下步骤：
读取软件缺陷数据集，基于关联规则算法生成初始关联规则集合；
基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷字典和无缺陷字典；获取同时存在于两个字典的节点，在反向超图中去除所述节点的冗余边，更新字典中节点层级，得到关联规则网络；
基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区；分别根据社区中的缺陷标签和社区中节点所属字典，从多个社区中提取出用于软件缺陷预测的关联规则；
所述基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区，包括：S31、以关联规则网络中每个节点作为独立的社区；
S32、按照两个字典中节点层级，从小到大对节点进行排序；
S33、按顺序依次对每个节点执行如下步骤：以当前节点与各相邻节点对应的关联规则的相关性作为边权重，依次将当前节点分配到各相邻节点所属社区，根据边权重计算对应的模块度增益值，并根据模块度增益值确定当前节点最终所要分配的社区；
S34、重复步骤S33，直至每个节点所属社区不再变化；
S35、将属于同一个社区的节点压缩成一个新节点，以相邻新节点中所有关联规则的相关性之和作为新节点间的边权重，重复步骤S33至步骤S34，直至各社区的模块度不再变化，得到多个社区。
2.根据权利要求1所述的软件缺陷关联规则网络剪枝方法，其特征在于，所述读取软件缺陷数据集，基于关联规则算法生成初始关联规则集合，包括：以软件缺陷数据集中每条数据进行离散化处理并转换为一条事务性数据，将每条数据中的软件缺陷度量元和缺陷标签作为项，基于Apriori算法生成频繁2项集，根据预置的最小支持度和最小置信度，从频繁2项集中生成不带有缺陷标签的关联规则，及后件是缺陷标签的关联规则，放入初始关联规则集合中；所述缺陷标签包括有缺陷标签和无缺陷标签。
3.根据权利要求2所述的软件缺陷关联规则网络剪枝方法，其特征在于，所述基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷字典和无缺陷字典，包括：从初始关联规则集合中获取不带有缺陷标签的关联规则作为第一规则集合；
从初始关联规则集合中，将所有后件是有缺陷标签的关联规则的后件作为第一目标节点，将所有后件是无缺陷标签的关联规则的后件作为第二目标节点，对每一目标节点执行如下操作：S21、取出目标节点对应的前件作为下一层级节点；
S22、以下一层级节点作为关联规则的后件，从第一规则集合中获取对应的前件作为下一层级节点，重复步骤S22，直至无法从第一规则集合中获取到前件；
S23、从目标节点开始按照关联规则逐层在后件和对应的前件之间添加超边，层级从0开始逐层递增1；根据各层级节点所流向的目标节点，将各层级节点及其层级存储在对应的有缺陷字典和/或无缺陷字典中。
4.根据权利要求3所述的软件缺陷关联规则网络剪枝方法，其特征在于，所述获取同时存在于两个字典的节点，在反向超图中去除所述节点的冗余边，包括：依次取出同时存在于两个字典中的节点，如果当前节点在两个字典中的层级不同，则在最大层级对应的字典中，去除当前节点数据及其层级，并在反向超图中从当前节点流向最大层级对应的目标节点的路径上，去除当前节点与相邻节点间的边；如果当前节点在两个字典中的层级相同，则在两个字典中删除当前节点数据及其层级，并在反向超图中删除当前节点及其相邻边。
5.根据权利要求4所述的软件缺陷关联规则网络剪枝方法，其特征在于，所述更新字典中节点层级，包括：依次从反向超图中两个目标节点开始遍历，获取反向超图中各节点到对应的目标节点的最短距离，并识别各节点的最短距离与其在对应的字典中的层级是否一致，如果不一致，以节点的最短距离作为新的层级更新至对应字典中。
6.根据权利要求1所述的软件缺陷关联规则网络剪枝方法，其特征在于，所述关联规则的相关性采用皮尔逊相关系数计算得到，所述社区发现算法采用Louvain算法。
7.根据权利要求1所述的软件缺陷关联规则网络剪枝方法，其特征在于，所述分别根据社区中的缺陷标签和社区中节点所属字典，从多个社区中提取出用于软件缺陷预测的关联规则，包括：如果社区中存在有缺陷标签/无缺陷标签，则将社区中所有边对应的关联规则，加入与缺陷标签对应的用于预测软件有缺陷/无缺陷的关联规则中；
如果社区中所有节点仅存在于有缺陷字典/无缺陷字典，则将社区中所有边对应的关联规则，加入与字典类型对应的用于预测软件有缺陷/无缺陷的关联规则中；
8.根据权利要求7所述的软件缺陷关联规则网络剪枝方法，其特征在于，使用所述用于软件缺陷预测的关联规则时，根据待预测的软件模块中软件缺陷度量元数据，分别与用于预测软件有缺陷的关联规则和用于预测软件无缺陷的关联规则进行匹配，将被匹配的关联规则的提升度累加入对应的预测有缺陷或无缺陷决策器；根据最大值对应的决策器，得到待预测的软件模块的缺陷预测结果。
9.一种软件缺陷关联规则网络剪枝系统，其特征在于，包括：
初始规则生成模块，用于读取软件缺陷数据集，基于关联规则算法生成初始关联规则集合；
规则网络构建模块，用于基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷字典和无缺陷字典；获取同时存在于两个字典的节点，在反向超图中去除所述节点的冗余边，更新字典中节点层级，得到关联规则网络；
规则网络剪枝模块，用于基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区；分别根据社区中的缺陷标签和社区中节点所属字典，从多个社区中提取出用于软件缺陷预测的关联规则；
所述基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区，包括：S31、以关联规则网络中每个节点作为独立的社区；
S32、按照两个字典中节点层级，从小到大对节点进行排序；
S33、按顺序依次对每个节点执行如下步骤：以当前节点与各相邻节点对应的关联规则的相关性作为边权重，依次将当前节点分配到各相邻节点所属社区，根据边权重计算对应的模块度增益值，并根据模块度增益值确定当前节点最终所要分配的社区；
S34、重复步骤S33，直至每个节点所属社区不再变化；
S35、将属于同一个社区的节点压缩成一个新节点，以相邻新节点中所有关联规则的相关性之和作为新节点间的边权重，重复步骤S33至步骤S34，直至各社区的模块度不再变化，得到多个社区。
一种软件缺陷关联规则网络剪枝方法及系统
技术领域
[0001] 本发明涉及软件缺陷预测技术领域，尤其涉及一种软件缺陷关联规则网络剪枝方法及系统。
背景技术
[0002] 随着人们对软件系统的依赖程度的增加，软件缺陷所带来的危害也越来越频繁、越来越严重。尽早发现软件缺陷并及时将其修复才能把缺陷造成的危害和损失降低到最小程度。
[0003] 关联规则技术在软件缺陷预测领域近年来的研究越来越多，关联规则发现旨在提取大型数据库中的特征、隐藏的关联模式和项目（属性）之间的相关性。然而，不平衡数据的出现给关联分类算法带来了挑战。类不平衡问题指分类任务中不同类别的训练样例数目差别很大的情况，各个类别的样本量分布不均——某些类别的样本数量极多，有些类别的样本数量极少。在现实生活中存在很多不平衡数据集的应用，因此在实际应用中非常有必要提高不平衡数据的分类精度，尤其是少数类的分类精度。
[0004] 另外，现代网络在规模、多样性和复杂性上呈指数增长，缺陷数据集中往往存在不相关或冗余特征，冗余特征的存在使得在关联规则领域中会带来过多的冗余关联规则，这些冗余规则会干扰分类过程，降低分类性能。
发明内容
[0005] 鉴于上述的分析，本发明实施例旨在提供一种软件缺陷关联规则网络剪枝方法及系统，用以解决现有关联规则网络未考虑有无缺陷的双目标且关联规则存在冗余的问题。
[0006] 一方面，本发明实施例提供了一种软件缺陷关联规则网络剪枝方法，包括如下步骤：
[0007] 读取软件缺陷数据集，基于关联规则算法生成初始关联规则集合；
[0008] 基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷字典和无缺陷字典；获取同时存在于两个字典的节点，在反向超图中去除节点的冗余边，更新字典中节点层级，得到关联规则网络；
[0009] 基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区；分别根据社区中的缺陷标签和社区中节点所属字典，从多个社区中提取出用于软件缺陷预测的关联规则。
[0010] 基于上述方法的进一步改进，读取软件缺陷数据集，基于关联规则算法生成初始关联规则集合，包括：以软件缺陷数据集中每条数据进行离散化处理并转换为一条事务性数据，将每条数据中的软件缺陷度量元和缺陷标签作为项，基于Apriori算法生成频繁2项集，根据预置的最小支持度和最小置信度，从频繁2项集中生成不带有缺陷标签的关联规则，及后件是缺陷标签的关联规则，放入初始关联规则集合中；缺陷标签包括有缺陷标签和无缺陷标签。
[0011] 基于上述方法的进一步改进，基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷字典和无缺陷字典，包括：
[0012] 从初始关联规则集合中获取不带有缺陷标签的关联规则作为第一规则集合；
[0013] 从初始关联规则集合中，将所有后件是有缺陷标签的关联规则的后件作为第一目标节点，将所有后件是无缺陷标签的关联规则的后件作为第二目标节点，对每一目标节点执行如下操作：
[0014] S21、取出目标节点对应的前件作为下一层级节点；
[0015] S22、以下一层级节点作为关联规则的后件，从第一规则集合中获取对应的前件作为下一层级节点，重复步骤S22，直至无法从第一规则集合中获取到前件；
[0016] S23、从目标节点开始按照关联规则逐层在后件和对应的前件之间添加超边，层级从0开始逐层递增1；根据各层级节点所流向的目标节点，将各层级节点及其层级存储在对应的有缺陷字典和/或无缺陷字典中。
[0017] 基于上述方法的进一步改进，获取同时存在于两个字典的节点，在反向超图中去除节点的冗余边，包括：
[0018] 依次取出同时存在于两个字典中的节点，如果当前节点在两个字典中的层级不同，则在最大层级对应的字典中，去除当前节点数据及其层级，并在反向超图中从当前节点流向最大层级对应的目标节点的路径上，去除当前节点与相邻节点间的边；如果当前节点在两个字典中的层级相同，则在两个字典中删除当前节点数据及其层级，并在反向超图中删除当前节点及其相邻边。
[0019] 基于上述方法的进一步改进，更新字典中节点层级，包括：
[0020] 依次从反向超图中两个目标节点开始遍历，获取反向超图中各节点到对应的目标节点的最短距离，并识别各节点的最短距离与其在对应的字典中的层级是否一致，如果不一致，以节点的最短距离作为新的层级更新至对应字典中。
[0021] 基于上述方法的进一步改进，基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区，包括：
[0022] S31、以关联规则网络中每个节点作为独立的社区；
[0023] S32、按照两个字典中节点层级，从小到大对节点进行排序；
[0024] S33、按顺序依次对每个节点执行如下步骤：以当前节点与各相邻节点对应的关联规则的相关性作为边权重，依次将当前节点分配到各相邻节点所属社区，根据边权重计算对应的模块度增益值，并根据模块度增益值确定当前节点最终所要分配的社区；
[0025] S34、重复步骤S33，直至每个节点所属社区不再变化；
[0026] S35、将属于同一个社区的节点压缩成一个新节点，以相邻新节点中所有关联规则的相关性之和作为新节点间的边权重，重复步骤S33至步骤S34，直至各社区的模块度不再变化，得到多个社区。
[0027] 基于上述方法的进一步改进，关联规则的相关性采用皮尔逊相关系数计算得到，社区发现算法采用Louvain算法。
[0028] 基于上述方法的进一步改进，分别根据社区中的缺陷标签和社区中节点所属字典，从多个社区中提取出用于软件缺陷预测的关联规则，包括：
[0029] 如果社区中存在有缺陷标签/无缺陷标签，则将社区中所有边对应的关联规则，加入与缺陷标签对应的用于预测软件有缺陷/无缺陷的关联规则中；
[0030] 如果社区中所有节点仅存在于有缺陷字典/无缺陷字典，则将社区中所有边对应的关联规则，加入与字典类型对应的用于预测软件有缺陷/无缺陷的关联规则中；
[0031] 去除剩余社区及其中所有边对应的关联规则。
[0032] 基于上述方法的进一步改进，使用用于软件缺陷预测的关联规则时，根据待预测的软件模块中软件缺陷度量元数据，分别与用于预测软件有缺陷的关联规则和用于预测软件无缺陷的关联规则进行匹配，将被匹配的关联规则的提升度累加入对应的预测有缺陷或无缺陷决策器；根据最大值对应的决策器，得到待预测的软件模块的缺陷预测结果。
[0033] 另一方面，本发明实施例提供了一种软件缺陷关联规则网络剪枝系统，包括：
[0034] 初始规则生成模块，用于读取软件缺陷数据集，基于关联规则算法生成初始关联规则集合；
[0035] 规则网络构建模块，用于基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷字典和无缺陷字典；获取同时存在于两个字典的节点，在反向超图中去除节点的冗余边，更新字典中节点层级，得到关联规则网络；
[0036] 规则网络剪枝模块，用于基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区；分别根据社区中的缺陷标签和社区中节点所属字典，从多个社区中提取出用于软件缺陷预测的关联规则。
[0037] 与现有技术相比，本发明至少可实现如下有益效果之一：
[0038] 1、通过构建有缺陷标签和无缺陷标签的双目标关联规则网络，更好更直观地分析出混淆规则和矛盾规则，减少推理错误，实现同时对有缺陷标签预测准确又对无缺陷标签预测准确；
[0039] 2、考虑双目标节点与整体关联规则网络之间的互动，通过对关联规则网络整体进行社区划分以进行关联规则网络剪枝方法，从中选取出性能最佳的关联规则并剔除掉影响分类性能的冗余规则，提高关联规则模型的训练速度和预测性能。
[0040] 本发明中，上述各技术方案之间还可以相互组合，以实现更多的优选组合方案。本发明的其他特征和优点将在随后的说明书中阐述，并且，部分优点可从说明书中变得显而易见，或者通过实施本发明而了解。本发明的目的和其他优点可通过说明书以及附图中所特别指出的内容中来实现和获得。
附图说明
[0041] 附图仅用于示出具体实施例的目的，而并不认为是对本发明的限制，在整个附图中，相同的参考符号表示相同的部件；
[0042] 图1为本发明实施例1中一种软件缺陷关联规则网络剪枝方法流程图。
具体实施方式
[0043] 下面结合附图来具体描述本发明的优选实施例，其中，附图构成本申请一部分，并与本发明的实施例一起用于阐释本发明的原理，并非用于限定本发明的范围。
[0044] 实施例1
[0045] 本发明的一个具体实施例，公开了一种软件缺陷关联规则网络剪枝方法，如图1所示，包括如下步骤：
[0046] S1、读取软件缺陷数据集，基于关联规则算法生成初始关联规则集合。
[0047] 需要说明的是，历史软件缺陷数据可以根据定义的软件缺陷的度量指标，使用现有静态软件代码分析工具对各软件模块扫描来获取各度量指标值，并根据实际软件模块是否存在缺陷，打上缺陷标签，从而将各度量指标值（即软件缺陷度量元）和缺陷标签作为软件缺陷数据；也可以直接使用开源软件缺陷领域的公开数据集，比如Promise库的ANT项目的软件缺陷数据集，其中软件缺陷的度量指标包括：代码行数（loc）、类的加权方法数（wmc）、继承树的深度（dit）、缺陷数量等，根据缺陷数量可以获取有无缺陷标签。
[0048] 根据缺陷标签将软件缺陷数据划分为有缺陷数据集和无缺陷数据集，通过M次K折交叉验证的方法，进行M×K次迭代训练和测试，每次分别将有缺陷数据集和无缺陷数据集划分为K折，将K‑1折有缺陷数据集和K‑1折无缺陷数据集构建为软件缺陷训练集，得到软件缺陷数据集，将1折有缺陷数据集和1折无缺陷数据集构建为软件缺陷测试集。通过软件缺陷数据集构建剪枝后用于软件缺陷预测的关联规则，通过软件缺陷测试集验证预测规则的准确率。
[0049] 示例性地，采用10次5折交叉验证的方法，进行50次迭代。
[0050] 基于关联规则算法生成初始关联规则集合，包括：对软件缺陷数据集中每条数据进行离散化处理并转换为一条事务性数据，将每条数据中的软件缺陷度量元和缺陷标签作为项，基于Apriori算法生成频繁2项集，根据预置的最小支持度和最小置信度，从频繁2项集中生成不带有缺陷标签的关联规则，及后件是缺陷标签的关联规则，放入初始关联规则集合中；其中，缺陷标签包括有缺陷标签和无缺陷标签。
[0051] 优选地，通过python pandas库中的qcut等频划分函数对软件缺陷数据集中的每条数据进行五阶等频离散化，使用基于Apriori算法的双支持度关联规则挖掘算法CBA2，设定最小支持度阈值与最小置信度阈值提取关联规则集合。其中，对带有缺陷标签的频繁2项集设置一个支持度，对不带有缺陷标签的频繁2项集设置另一个支持度；支持度和置信度的阈值通过从0到1进行遍历然后根据实验结果从而确定最佳的支持度与置信度值。对带有缺陷标签的频繁2项集中生成的关联规则中只保留后件是缺陷标签的关联规则，不带有缺陷标签的频繁2项集生成的关联规则即前件和后件均是软件缺陷度量元的规则。
[0052] 示例性地，初始关联规则['ca=(0.6, 1.0]'] => ['defects=true']中后件defects是缺陷标签，该规则表示如果软件模块出现传出耦合度（ca）在(0.6, 1.0]这个范围时，软件模块将发生缺陷；初始关联规则['dam=(0.1, 1.0]'] => ['ca=(0.6, 1.0]']中前件和后件均是软件缺陷度量元，该规则表示如果软件模块出现数据存取（dam）在(0.1, 1.0]这个范围时，软件模块将出现传出耦合度（ca）在(0.6, 1.0]这个范围。
[0053] S2、基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷字典和无缺陷字典；获取同时存在于两个字典的节点，在反向超图中去除节点的冗余边，更新字典中节点层级，得到关联规则网络。
[0054] 需要说明的是，基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷节点字典和无缺陷字典，包括：
[0055] ①从初始关联规则集合中获取不带有缺陷标签的关联规则作为第一规则集合；
[0056] ②从初始关联规则集合中，将所有后件是有缺陷标签的关联规则的后件作为第一目标节点，将所有后件是无缺陷标签的关联规则的后件作为第二目标节点，对每一目标节点执行如下操作：
[0057] S21、取出目标节点对应的前件作为下一层级节点；
[0058] S22、以下一层级节点作为关联规则的后件，从第一规则集合中获取对应的前件作为下一层级节点，重复步骤S22，直至无法从第一规则集合中获取到前件；即：利用递归算法，从关联规则的后件反向找前件，获取各层级节点。
[0059] S23、从目标节点开始按照关联规则逐层在后件和对应的前件之间添加超边，层级从0开始逐层递增1；根据各层级节点所流向的目标节点，将各层级节点及其层级存储在对应的有缺陷字典和/或无缺陷字典中。
[0060] 示例性地，有缺陷字典的存储内容为：{'defects=true': 0,'ca=(0.6, 1.0]': 1, 'dam=(0.1, 1.0]': 2,'dit=(2.0, 3.0]':3, 'wmc=(12.0, inf]': 3,…}，其中，defects=true表示有缺陷，mfa、ic、dit和wmc表示软件缺陷度量元，等号后的数值范围表示各度量元的值等频离散化后所属范围，冒号后的数值表示各度量元的层级。
[0061] 需要说明的是，步骤S23与步骤S22可以并行处理，即：在步骤S22中找到节点的同时添加超边和存储信息至对应字典中。各节点层级也表示节点到达目标节点的最短距离。
[0062] 考虑到初始关联规则中可能存在从同一节点经过不同数量的节点到达不同的目标节点，比如X=>Y1，X=>T=>Y2，或者存在矛盾规则，比如Z=>Y1，Z=>Y2的两个规则中前件相同，但后件Y1和Y2表示两个不同的缺陷标签，这些情况都导致推理错误。因此，本实施例根据同时存在于两个字典的节点，分析出其中存在的混淆规则和矛盾规则，去除对应的反向超图中的冗余边，提高预测的准确度。
[0063] 具体来说，依次取出同时存在于两个字典中的节点，如果当前节点在两个字典中的层级不同，则在最大层级对应的字典中，去除当前节点数据及其层级，并在反向超图中从当前节点流向最大层级对应的目标节点的路径上，去除当前节点与相邻节点间的边；如果当前节点在两个字典中的层级相同，则在两个字典中删除当前节点数据及其层级，并在反向超图中删除当前节点及其相邻边。
[0064] 示例性地，某节点A以有缺陷标签为目标的层级为2（A=>B=>Y1），以无缺陷标签为目标的层级为1（A=>Y2），则在有缺陷字典中去掉该节点A，在双目标反向超图中去除A=>B之间的边，使得从节点A无法到达Y1，该节点在双目标反向超图中以无缺陷标签为目标，层级为1。某节点Q以有缺陷标签为目标的层级为2（Q=>C=>Y1），以无缺陷标签为目标的层级也为2（Q=>D=>Y2），则节点Q为矛盾节点，将节点Q从两个字典中删除，并在双目标反向超图中删除节点Q及其相邻边，相邻边包括Q=>C的边、Q=>D的边，以及节点Q与其相邻前件之间的边，确保无法达到矛盾节点，以及无法从矛盾节点到达目标节点。
[0065] 优选地，冗余边删除后，通过遍历更新字典中节点层级，实现双目标反向超图中每一个节点到达目标节点的距离最短且与字典中的层级一致，包括：依次从反向超图中两个目标节点开始遍历，获取反向超图中各节点到对应的目标节点的最短距离，并识别各节点的最短距离与其在对应的字典中的层级是否一致，如果不一致，以节点的最短距离作为新的层级更新至对应字典中。
[0066] 与现有技术相比，本实施例通过建立双目标的反向超图，可以更好更直观地分析出混淆规则和矛盾规则，减少推理错误，实现同时对有缺陷标签预测准确又对无缺陷标签预测准确。
[0067] S3、基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区；分别根据社区中的缺陷标签和社区中节点所属字典，从多个社区中提取出用于软件缺陷预测的关联规则。
[0068] 需要说明的是，本实施例中社区发现算法采用Louvain算法，对关联规则网络聚类得到多个社区，包括：
[0069] S31、以关联规则网络中每个节点作为独立的社区；
[0070] S32、按照两个字典中节点层级，从小到大对节点进行排序；
[0071] 需要说明的是，传统的Louvain算法由于遍历节点的顺序为随机的，会给社区划分带来不确定性，引起最终划分的社区不准确。因此，针对此问题，本实施例中通过层级表示节点的重要性，层级越小，节点重要性越高，因此，按照两个字典中节点层级从小到大排序节点，在Louvain算法中优先遍历重要性较高的节点。
[0072] S33、按顺序依次对每个节点执行如下步骤：以当前节点与各相邻节点对应的关联规则的相关性作为边权重，依次将当前节点分配到各相邻节点所属社区，根据边权重计算对应的模块度增益值，并根据模块度增益值确定当前节点最终所要分配的社区；
[0073] S34、重复步骤S33，直至每个节点所属社区不再变化；
[0074] 由于本实施例中关联规则网络中的边就是关联规则，因此以关联规则的相关性作为边权重。
[0075] 优选地，采用皮尔逊相关系数计算每个关联规则的相关性。皮尔逊相关系数用以反映关联规则中软件缺陷度量元与缺陷标签之间相关关系的密切程度，定义如下：
[0076]
[0077] 其中，P(XY)表示关联规则的前件X和后件Y同时发生的概率，P(X)表示关联规则的前件发生的概率，P(Y)表示关联规则的后件发生的概率。
[0078] 需要说明的是，仅当模块度增益值为正时，将节点分配至模块度增益值最大的社区；当模块度增益值为负，节点会留在原来的社区。
[0079] S35、将属于同一个社区的节点压缩成一个新节点，以相邻新节点中所有关联规则的相关性之和作为新节点间的边权重，重复步骤S33至步骤S34，直至各社区的模块度不再变化时，得到多个社区。
[0080] 然后，分别根据社区中的缺陷标签和社区中节点所属字典，判断划分后的社区是否保留，并在保留下社区中提取用于软件缺陷预测的关联规则，包括：
[0081] 如果社区中存在有缺陷标签/无缺陷标签，则将社区中所有边对应的关联规则，加入与缺陷标签对应的用于预测软件有缺陷/无缺陷的关联规则中。即：如果社区中存在有缺陷标签，则将社区中所有边对应的关联规则，加入用于预测软件有缺陷的关联规则中；如果社区中存在无缺陷标签，则将社区中所有边对应的关联规则，加入用于预测软件无缺陷的关联规则中。
[0082] 如果社区中所有节点仅存在于有缺陷字典/无缺陷字典，则将社区中所有边对应的关联规则，加入与字典类型对应的用于预测软件有缺陷/无缺陷的关联规则中。即：如果社区中所有节点均仅存在于有缺陷字典中，并不存在于无缺陷字典之中，此时社区中所有节点都存在于有缺陷标签的环境中，那么将社区中所有边对应的关联规则，加入用于预测软件有缺陷的关联规则中；如果社区中所有节点均仅存在于无缺陷字典中，并不存在于有缺陷字典之中，此时社区中所有节点都存在于无缺陷标签的环境中，那么将社区中所有边对应的关联规则，加入用于预测软件无缺陷的关联规则中。
[0083] 去除剩余社区及其中所有边对应的关联规则，即：针对社区中的节点同时存在于有缺陷字典和无缺陷字典，容易产生矛盾推理，因此去除剩余的社区。
[0084] 最终，得到用于预测软件有缺陷的关联规则和预测软件无缺陷的关联规则，作为关联规则模型。
[0085] 与现有技术相比，传统关联规则网络的规则剪枝仅仅通过去除反向超图的超循环和逆超边，并未考虑双目标节点与整体关联规则网络之间的互动，因此通过对关联规则网络整体进行社区划分以进行关联规则网络剪枝方法更加有效，从中选取性能最佳的关联规则并剔除掉影响分类性能的冗余规则，不仅能够提高关联规则模型的训练速度，更重要的是能够提高预测性能。
[0086] 基于最终得到的关联规则模型，使用软件缺陷测试集进行验证，或者获取同项目下软件模块缺陷数据进行预测时，根据待预测的软件模块中软件缺陷度量元数据，分别与用于预测软件有缺陷的关联规则和用于预测软件无缺陷的关联规则进行匹配，将被匹配的关联规则的提升度累加入对应的预测有缺陷或无缺陷决策器；根据最大值对应的决策器，得到待预测的软件模块的缺陷预测结果。
[0087] 需要说明的是，对于关联规则A=>B，提升度表示“包含A的事务中同时包含B事务的比例”与“包含B事务的比例”的比值。当提升度>1，说明A和B之间有正相关关系，且数值越大正相关程度越高；当提升度<1，说明A和B之间有负相关关系，且数值越小负相关程度越高（提升度定义大于等于零）；当提升度=1，说明A和B之间没有相关关系。
[0088] 当度量元数据可以匹配用于预测有缺陷的关联规则，则将被匹配关联规则的提升度累加入预测有缺陷决策器，当度量元数据可以匹配用于预测无缺陷的关联规则，则将被匹配关联规则的提升度累加入预测无缺陷决策器，最终判断预测有缺陷决策器与预测无缺陷决策器的值哪个更大，从而预测出软件模块是否有缺陷。也就是说，最终判断预测有缺陷决策器与预测无缺陷决策器中累加的提升度值哪个最大，如果有缺陷决策器的值最大，则预测结果是有缺陷，否则预测结果是无缺陷。
[0089] 与现有技术相比，本实施例提供的一种软件缺陷关联规则网络剪枝方法，通过构建有缺陷标签和无缺陷标签的双目标关联规则网络，更好更直观地分析出混淆规则和矛盾规则，减少推理错误，实现同时对有缺陷标签预测准确又对无缺陷标签预测准确；考虑双目标节点与整体关联规则网络之间的互动，通过对关联规则网络整体进行社区划分以进行关联规则网络剪枝方法，从中选取性能最佳的关联规则并剔除掉影响分类性能的冗余规则，提高关联规则模型的训练速度和预测性能。
[0090] 实施例2
[0091] 本发明的另一个实施例，公开了一种软件缺陷关联规则网络剪枝系统，从而实现实施例1中的软件缺陷关联规则网络剪枝方法。各模块的具体实现方式参照实施例1中的相应描述，包括：
[0092] 初始规则生成模块，用于读取软件缺陷数据集，基于关联规则算法生成初始关联规则集合；
[0093] 规则网络构建模块，用于基于初始关联规则集合，构建以有缺陷标签和无缺陷标签作为目标节点的反向超图，以及有缺陷字典和无缺陷字典；获取同时存在于两个字典的节点，在反向超图中去除节点的冗余边，更新字典中节点层级，得到关联规则网络；
[0094] 规则网络剪枝模块，用于基于社区发现算法，根据字典中节点层级，对关联规则网络聚类得到多个社区；分别根据社区中的缺陷标签和社区中节点所属字典，从多个社区中提取出用于软件缺陷预测的关联规则。
[0095] 由于本实施例软件缺陷关联规则网络剪枝系统与前述软件缺陷关联规则网络剪枝方法相关之处可相互借鉴，此处为重复描述，故这里不再赘述。由于本系统实施例与上述方法实施例原理相同，所以本系统实施例也具有上述方法实施例相应的技术效果。
[0096] 本领域技术人员可以理解，实现上述实施例方法的全部或部分流程，可以通过计算机程序来指令相关的硬件来完成，所述的程序可存储于计算机可读存储介质中。其中，所述计算机可读存储介质为磁盘、光盘、只读存储记忆体或随机存储记忆体等。
[0097] 以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。
