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

论文：Xia, X., Feng, Y., Lo, D., Chen, Z., & Wang, X. (2014). Towards more accurate multi-label software behavior learning. Software Maintenance, Reengineering and Reverse Engineering (Vol.8543, pp.134-143). IEEE.

https://ieeexplore.ieee.org/document/6747163/

论文摘要：在现代软件系统中，当程序失败时，包含执行轨迹的崩溃报告将被发送到软件供应商进行诊断。与失败对应的崩溃报告可能同时由多种类型的故障引起。许多大公司如百度组织一个团队来分析这些失败，并将它们分类为多个标签(即多种类型的故障）。然而，对于开发人员来说，手工分析这些失败并给出适当的故障标签是非常耗时和困难的。本文采用一种混合算法MLL-GA，利用遗传算法(GA)结合多种多标签学习算法，将失败自动分类为多种故障类型。为了评估MLL-GA的有效性，我们对6个开源程序进行了实验，结果表明，MLL-GA可以实现0.6078到0.8665的平均F值。我们还将我们的算法与Ml.KNN进行了比较，结果表明，在6个数据集中，MLL-GA将Ml.KNN的平均F值提高了14.43%。

技术介绍：

软件开发生命周期的所有阶段都会出现软件故障，为了提高软件系统的可靠性，许多供应商采用了自动崩溃报告系统。当程序失败时，这些系统生成一个与失败对应的崩溃报告，其中包含执行轨迹，并将其发送给软件供应商进行诊断。执行轨迹对应于一个程序从开始执行到终止执行时所采取的路径，并且一个失败可能由多个类型的故障同时引起。目前很多公司都会组织项目团队来分析他们收到的崩溃报告，并将它们归类为不同的标签(即故障类型)。但是，崩溃报告仅包含执行轨迹，并且人工分析大量的奔溃报告十分低效。此外，一次失败执行可能是由多种类型的故障同时引起的。因此，一个失败通常被分配的标签不止一个，这使得工作更加困难。

为了解决多标签学习问题，人们开发了多种方法。这些方法可以分为两大类:问题转换方法和算法适应方法。问题转换方法将多标签分类任务转换为多个单标签分类任务;它们通常基于二值相关算法(BR)或标签幂集算法(LP)。算法适应方法扩展特定的学习算法，直接处理多标签数据。

不同的多标签学习算法对于不同数据集的性能是不同的。有些算法在某些数据集上的性能比其他算法要好得多，但在其他数据集中却输给了其他算法。本文提出了一种混合算法MLL-GA，利用遗传算法结合多种多标签学习算法。总的来说，MLL-GA结合了12种多标签学习算法，这12种算法选择如下：我们选择BR，ECC和RAKEL作为元算法，并使用KNN，朴素贝叶斯多项式，C4.5和SVM作为其相应的基础分类算法。然后，我们有11个多标签学习算法。第12个算法是Ml.KNN。

MLL-GA的总体框架如图1所示。MLL-GA有两个阶段:训练阶段和预测阶段。在训练阶段，我们的目标是通过学习历史训练数据(即，失败的执行)建立一个复合模型。在预测阶段，我们应用这个模型来为新的未标签数据（即，一个新的失败执行）预测合适的标签集(即，故障的类型)。

图1 MLL-GA的总体框架

在建立模型之后，在预测阶段，它被用来预测新的失败的一组标签。我们将新失败的执行轨迹输入到MLL-GA分类器中，然后输出一组标签的预测结果。

为了检验MLL-GA的好处，我们在软件工件基础设施库（SIR）（即tcas，printtokens，printtokens2，replace，flex和grep）上对3个真实C程序和3个Siemens测试程序进行了实验。我们证明了MLL-GA可以达到0.8665的平均F值。我们还将我们的算法与Ml.KNN算法进行了比较。实验结果表明，在6个数据集中，MLL-GA的平均F值比Ml.KNN高了14.43%。 此外，由于我们结合了12种不同的多标签学习算法，并将MLL-GA与它们中的每一种进行了比较，实验结果显示，在6个程序中，MLL-GA平均可以比这12种算法高出10.42％。

表1 MLL-GA与ML.KNN比较的实验结果

表2 MLL-GA与其他12种多标签学习算法的平均F1值。

其中，一个基础分类算法为c,元分类算法为BR和LP的复合模型记作BR^c和LP^c。

本文的主要贡献如下:

1. 我们研究了许多多标签学习算法的性能，以解决软件行为学习问题。并提出了一种混合算法MLL-GA，它结合了多种多标签算法，利用遗传算法提高了性能。值得注意的是，MLL-GA是一种可扩展的算法，它可以结合各种多标签学习算法。
2. 我们对6个程序进行MLL-GA评估，实验结果表明，MLL-GA能够大幅改善最先进的软件行为学习算法M1.KNN。

来源：慕测科技