面向更精确的多标签软件行为学习

引用

Xin Xia, Yang Feng, David Lo, Zhenyu Chen, Xinyu Wang. "Towards more accurate multi-label software behavior learning." 2014 Software Evolution Week-IEEE Conference on Software Maintenance, Reengineering, and Reverse Engineering (CSMR-WCRE). IEEE, 2014

1.摘要

在现代软件系统中，当程序失败时，包含执行跟踪的崩溃报告将被发送到软件供应商进行诊断。与故障相对应的崩溃报告可能同时由多种类型的错误引起。诸如百度之类的许多大公司组织一个团队来分析这些故障，并将它们分类为多个标签（即多种类型的错误）。但是，开发人员手动分析这些故障并给出适当的错误标签将非常耗时且困难。在本文中，我们使用名为 MLL-GA 的复合算法将故障自动分类为多种类型的错误，MLL-G 通过利用遗传算法（GA）组合了各种多标签学习算法。为了评估 MLL-GA 的有效性，我们在 6 个开源程序上进行了实验，结果表明 MLL-GA 可以实现 0.6078 至 0.8665 的平均 F 度量值。我们还将算法与 Ml.KNN 进行了比较，结果表明，在 6 个数据集上，MLL-GA 将 Ml.KNN 的平均 F 度量值提高了 14.43％。

2.介绍

主要工作：

1）研究了多种多标签学习算法解决软件行为学习问题的性能，并且提出了一种名为 MLL-GA 的组合算法，该算法结合了多种多标签算法，可以利用遗传算法获得更好的性能。注意 MLL-GA 是一种可扩展算法，可以结合多种多标签学习算法。

2）我们在 6 个程序上对 MLL-GA 进行了评估，实验结果表明 MLL-GA 可以大幅度改善现有软件行为学习算法 Ml.KNN。

3.背景

A.问题背景

在实际中，有两种描述故障的方法。一种用户可以编写故障的文本描述，并提供故障的输入和输出，执行跟踪和运行时上下文。（如：_们从项目向导中派生出了新向导，插入新页面时会有异常。此外，尽管未选择任何内容，但启用了前几页中的编辑/删除按钮。_）开发人员阅读了这一故障描述后可以轻松地决定故障的错误划分，例如将故障分配给“插入页面故障”和“编辑/删除按钮故障”类别。另一种类型的故障描述，称为崩溃报告。崩溃报告仅包含执行跟踪和运行时上下文。在百度，每天都会收到成千上万的此类崩溃报告。由于只有执行跟踪和运行时上下文，开发人员很难确定适当的标签。因此，如果我们可以从带有已知标签的故障中训练模型并使用该模型预测仅包含执行跟踪的故障描述标签，则开发人员的工作量可以减少。

B.多标签学习

问题转换方法和算法适应方法是解决多标签学习问题的两种主要方法。我们的 MLL-GA 中使用了二进制相关性（BR）算法，标签功率集（LP）算法和 Ml.KNN。BR 和 LP 算法可以使用不同的基础分类算法，例如 KNN ，朴素贝叶斯多项式，C4.8 决策树和 SVM [10]。我们将这些算法（例如，BR 和 LP）称为元算法[12]。在本文中，我们将具有基本分类算法 c 的 BR 和 LP 表示为 BRc 和 LPc。例如，以 SVM 作为其基础分类器的随机 k 标签集表示为 RAKELSVM。

C.为何要使用复合模型

为了研究不同的多标签学习算法在不同的数据集上是否会有不同的表现，我们在 printtokens2 和 flex 程序上评估了 12 种多标签学习算法。选择了以下 12 种算法：我们选择 BR，ECC 和 RAKEL 作为元算法，并使用 KNN，朴素贝叶斯多项式，C4.5 和 SVM 作为它们对应的基础分类算法。然后，我们有了 11 种多标签学习算法。第十二种算法是 Ml.KNN。表 I 列出了 printtokens2 和 flex 上的 12 种算法的平均 F 度量分数。printtokens2 的最佳性能算法是使用 C4.5 的 RAKEL，而 flex 的最佳算法是使用 SVM 的 RAKEL。因此，对于不同的数据集，性能最佳的算法可能会有所不同，此现象被称为算法差异现象。为了解决这个问题，我们提出了一种将各种多标签学习算法相结合以实现更好性能的技术。

4.算法

A.总体框架

MLL-GA 有两个阶段：训练阶段和预测阶段。在训练阶段，我们的目标是建立一个从历史训练数据（即故障）中学到的综合模型。在预测阶段，我们使用此模型来为新的未标记数据（即新故障）预测适当的标记集（即错误类型）。

B．MLL-GA：一种复合算法

由于不同的多标签学习算法会在软件行为数据集上表现出不同的性能，因此 MLL-GA 的基本思想是我们为在数据集上表现良好的算法分配较高的权重，而为在相同数据集上表现较差的算法分配较低的权重。

算法 1 表示 MLL- GA 的训练阶段。

5.实验

A.实验设置

我们在来自 SIR 的 3 个 Siemens 测试程序和 3 个真实 C 程序即 tcas，printtokens，printtokens2，replace，flex 和 grep [11] 上评估了 MLL-GA。对于每个这样的程序，我们将多个错误注入其中[15]，每个错误代表一种错误类型（如标签）。

B.评估指标

给定标签集 L 中的标签 l，对于多标签软件行为学习数据集中的一个实例，有四个结果：一个实例真正属于 l 且将其分配给标签 l（真阳性，TPl）；实际上不属于 l 却被分配给标签 l（假阳性，FPl）；当它实际上属于 l 却没有分配给标签 l（假阴性，FNl）；或它实际上不属于 l 且未分配给标签 l（真阴性 TNl）。基于这些可能的结果，标签 l 的精度，召回率和 F 量度定义为：

l l 的精度：在那些被标记为 l 的实例中，被正确标记的实例比例。

(2)

l l 的召回率：被正确标记为 l 的实例比例。

(3)

l F 度量：结合了标签 l 的精度和召回率的融合度量-它评估精度（召回率）的提高是否大于召回率（精度）的降低。

(4)

给定 l 的精度，召回率和 F 度量，|L|个标签上的平均精度，召回率和 F 度量定义为：

C.研究问题

RQ1 MLL-GA 有多有效？与 Feng 和 Chen[3]提出的 Ml.KNN 相比，可以实现多少改进？我们将 MLL-GA 与 Feng 和 Yang 提出的 Ml.KNN 进行了比较。我们计算平均精度，召回率和 F 量度分数。

从上表可以看出，我们的方法相对于 M1.KNN 的改进是可观的。

RQ2 为解决软件行为学习问题而提出的 12 种多标签学习算法的性能是什么？我们在 6 个程序上运行了这 12 种多标签学习算法，并记录了它们的平均 F-measure 得分，并与 MLL-GA 进行比较。

MLL-GA 对其他算法的改进幅度从 2％（RAKELSVM）到 23.36％（BRNBM）。在 12 种算法中，MLL-GA 的平均 F 度量分数平均提高了 10.42％。

RQ3 MLL-GA 运行需要多少时间？我们将 MLL-GA 的训练和预测时间与 Ml.KNN 的训练和预测时间进行了比较。

MLL-GA 的训练和预测时间比 Ml.KNN 的训练和预测时间更昂贵。但是仍然处于合理范围。平均而言，我们需要大约 5 分钟（280 秒）来构建一个 MLL-GA 分类器，并分别需要 12 秒来预测测试集中实例的标签。

6.结论与未来工作

在本文中，我们解决了多标签软件行为学习问题，该问题将故障分为一种或多种错误类型（即标签）。由于算法差异现象，我们提出了一种名为 MLL-GA 的复合算法，该算法利用遗传算法结合了不同的多标签学习算法。我们在遗传算法中将适应性函数设置为平均 F 度量分数，以适应不同的算法，从而使 MLL-GA 获得更好的性能。总共，我们结合了 12 种多标签学习算法。我们对 SIR 上的 6 个程序进行了实验，而 MLL-GA 可以实现 0.6078 至 0.8665 的平均 F 度量值。我们还将我们的算法与 Feng 和 Chen 使用的 Ml.KNN 进行比较。实验结果表明，在 6 个数据集上，MLL-GA 将 M1.KNN 的 F 度量值平均提高了 14.43％。此外，我们将 MLL-GA 与 12 种不同的多标签学习算法中的每一种进行了比较，实验结果表明，在这 6 个程序上，MLL-GA 可以比这 12 种算法平均提高 F 度量值 10.42％。

未来，我们计划利用来自更多软件项目的数据集对 MLL-GA 进行评估，并开发出一种更好的算法，可以进一步提高预测性能（例如，平均 F 度量）。我们还计划调查各种训练数据的数量对我们的方法表现的影响。