引用

Feng Y , Jones J , Chen Z , et al. An Empirical Study on Software Failure Classification with Multi-label and Problem-Transformation Techniques. IEEE Computer Society, 2018:320-330.

摘要

分类技术已用于软件工程研究，比如执行软件分类等任务。现有的工作已经提出了单标签故障分类技术，这项技术将训练结果以及后续的执行都标记为单一故障原因。单一故障原因的假设通常是不现实的：在实践中，固有的软件行为的特征，例如多个错误导致的故障和故障之间相互作用。为了进一步优化这不够实际的假设，在机器学习领域，研究人员已经提出了用于多标签分类的新方法。但是，根据应用领域的不同，这种方法的有效性和效率存在很大差异。在本文中，我们实证研究了这些新方法在不同应用程序设置下对故障分类任务的表现。我们使用八种分类技术对五个具有 8,000 多个错误版本的程序进行了实验，以研究每种技术如何解释软件行为的复杂性。我们的实验结果表明，多标签技术比单标签技术具有更高的准确性。我们还评估了每种技术的训练和预测阶段的效率，并针对每种技术在不同使用情况下的适用性提供了指导。

介绍

人们经常使用经典单标签机器学习分类器，例如 KNN，C45 和朴素贝叶斯来进行软件工程故障分类，这些技术旨在对崩溃和失败仅分类成一个标签。

近年来，机器学习研究已经产生了针对具有多个标签的分类问题的新技术，即多标签分类，这可能更适合实际的故障分类场景。此外，除了比较先进的多标签分类技术外，支持多分类的问题空间经过转换也可以使用单标签分类。这种利用单标签技术对问题空间进行转换的多标签分类称为问题转换。

我们在多标签学习中采用了两个最新成果：ML-KNN 和 BP-MLL。此外，在我们的研究中，我们还采用了最广泛使用的问题转换方法：Label Powerset（LP）和 Binary Relavance（BR）。

我们进行了一项实验，研究了三种类型的分类器的有效性和效率：（1）单标签，（2）问题转换和（3）多标签。为了进行这项研究，我们实施并评估了八种分类技术：两种单标签技术，四种使用问题转换的技术和两种多标签技术。我们使用了五个现有软件以及超过 8000 个有多个故障的版本。

本次工作的主要贡献如下：我们对多标签学习技术和问题转换方法在自动化软件工程任务中的应用进行了实证评估：故障分类。

我们对 5 个大型 C 程序进行了大规模研究，这些程序有 8000 多个错误版本，并对单标签，转换后的单标签和多标签分类的有效性和效率进行了详细的比较和分析。

分类

在本节中，我们概述了三种分类：单标签，问题转换和多标签。图 2 从概念上描述了四种主要的分类类型：一种单标签，两种问题转换和一种多标签分类技术，每种技术都显示为一行。在此图中，数据实例被描述为三元组-这些描述可以解释为软件执行的隐喻，其中的颜色代表故障是否影响了软件失效。例如的第一个数据实例表示由于绿色故障和蓝色故障而导致执行失败。“可能的分类”列表示可能的输出，给定所选的分类技术，这些描述可以解释为针对执行失败进行诊断的故障。在图的右侧“分类输出”列中，我们在给定输入数据实例的情况下，描绘了分类器最佳假设输出。这样的输出可以解释为描述每个失效执行的建议故障原因。现在，我们将描述每行中的分类技术。

A 单标签分类：在每个数据实例上放置一个单独的分类-也就是说，一个数据实例不可能被分类为多个标签。 在图 2 中，单标签分类具有三个可能的类别：“红色”，“绿色”或“蓝色”。 请注意，由于只有三个类（并且数据实例不可能属于多个类），因此当数据显示的特征不能完美地映射到类集中时，这种形式的单标签分类会导致分类错误。

B 带问题转换的单标签分类：为了解决涉及多个标签的分类问题，机器学习研究人员提出了一些将多标签问题转换为单标签问题的方法。两种常见的问题转换方法称为 Label Powerset 和 Binary Relevance。

Label Powerset 是一种将多标签问题转换为单标签问题的简单但有效的方法。它通过将所有标签组合枚举为原子标签来完成此任务，即，每个标签组合被视为一个标签问题中的一类。图 2 的第二行描述了分类问题的这种转换，以适应对多个标签的分类。Label Powerset 方法通过列举所有可能的组合来工作—在图中，产生了“红色”，“绿色”和“蓝色”的幂集，因此每个类别都用原子标签进行了标记，例如“绿色，蓝色” 。将概念图应用于软件故障分类问题，我们可以说，可能的类别集合包括由每个单独的故障（例如，红色，绿色或蓝色）或其每种可能的组合引起的故障。请注意，可能的组合集会随着大量标签的增加而迅速增长。

允许单标签分类的，且适用于多标签问题的另一种常见问题转换方法称为二进制相关性（Binary Relevance）。二进制相关分类独立地对待标签集的每个标签。通过为每个标签训练一个独立的分类器，二进制相关方法将产生组合的分类结果，即，BR 的最终输出包含每个标签的独立分类器的分类结果。图 2 的第三行描述了单标签分类到三个独立分类器的转换。在图中，使用分类器将每个数据分类为“红色”或“非红色”，“绿色”或“非绿色”和“蓝色”或“非蓝色”。最后，将这些结果汇总起来，为每个输入数据形成一个单一的，多标签的分类。请注意，每个标签的此类独立分类器无法利用共现信息（例如，红色和绿色经常共存，而绿色和蓝色很少共存）

C 多标签分类：近年来，通过直接针对多标签问题的分类技术已经实现了多标签分类。 Z 图 2 的第四行描述了一种可以将多标签分类概念化的方式。请注意，每个标签的分类都是独立的，以帮助其描述和理解。这些多标签技术不会将问题分解为多个独立的二进制分类问题。相反，他们确实的确考虑了标签之间的相关性。但是，这种概念化对于理解结果很有用：多个标签，每个标签可以独立地归属，而无需枚举所有可能的组合。

实验

为了实证调查现有软件工程研究的简化假设在多大程度上影响软件故障分类，我们进行了一项实验。对于该实验，我们有两个目标：（1）评估在多个故障的情况下，单标签分类技术在进行软件行为分类方面的有效程度。（2）在有效性（即分类的准确性）和效率（即分析所需的计算时间）方面评估纯单标签，问题转换方法和多标签分类技术的比较。

RQ1.单标签，问题转换和多标签分类技术对各种故障数量下的软件执行行为进行正确分类的准确度是多少？

RQ1.每个这些分类技术的运行时开销是多少？

软件主题程序。我们在表 I 中提供了程序的详细信息。我们使用了压缩工具 GZIP，正则表达式评估工具 GREP，两个版本的词法分析器 FLEX，文本解析器和转换器 SED 以及软件依赖项和构建工具 MAKE。我们使用 GCC（版本 4.7.2）对它们进行了编译和检测，以覆盖方法。

实验变量。我们使用两个自变量进行了实验：（1）分类技术，（2）导致失效的故障数量。

自变量 1：分类技术。对于第一个自变量，我们介绍了经典的分类方法，K 最近邻 K-Nearest Neighbors（KNN）和流行的技术多层感知器 Multilayer Perceptron（MP）。基于这两种技术，我们还介绍了两种最常见的问题转换方法，即 Label Powerset 和 Binary Relevance。对于多标签分类，我们选择了多标签 K 最近邻（ML-KNN）技术和 BP-MLL 。对于所有技术，我们都基于欧几里德距离测度的方法覆盖范围进行分类。

自变量 2：缺陷个数。对于第二个自变量，我们设置了五个故障量：0％，25％，50％，75％和 100％。 在 0％级别可能的故障版本数等于故障数| F |。 在 n = 25％，50％或 75％的级别上，每个级别均由随机选择的故障组合组成，这些故障组合最多包含 F 中的所有故障中的 n 个。在 100％的级别上，包含所有故障的单个多故障版本，在这个故障数量下，只能有一个组合版本。对于大于 0％的故障量，如果可能的组合数量超过 1000，则我们最多只能生成 1000 个随机选择的组合。

因变量 1：F 度量。为了评估分类器的准确性，我们使用 F 量度来评估关于软件行为的分类算法。经典 F 度量与精度 P 和召回率 R 相关。给定标签集 Y = {Yj | j = 1，2 ...，m}，以及测试多标签软件行为分类数据集 E'中的未知实例 ei' ，通过以下两个等式，可以基于输出标签集 yi 和确信事实标签集 gi 来计算 P 和 R。在我们的实验中，F-Measure 是精确度和查全率的谐波平均值。

因变量 2.训练和分类时间。为了评估分类技术的效率，我们测量了用所有训练数据训练每个分类器的时间，并使用 10 倍交叉验证评估了所有测评数据。

实验装置。在本实验中，我们在广泛使用的开源机器学习库 MULAN（1.5.0 版）和 WEKA（3.7.6 版）之上实施我们的技术以进行实验。

我们研究的每种分类技术都取决于某些参数。对于基于 KNN 的技术，关键参数是 k，它表示最近邻居的数量。对于基于 MP 的技术，epoch 参数表示要训练的轮数，学习率参数 learning-rate 表示神经网络的学习率。设置参数 k = 5，epoch= 10 和 learning-rate= 0.1。然后，我们通过抽样 5％的错误版本来验证这些参数。对于 Label Powerset，我们实现了随机 k 标签集（RAkEL）算法。 RAkEL 从标签集中随机选择 k 个不相交的子集，并在预测阶段使用整体方法投票方案。RAkEL 要求标签的数量大于子集的数量，因此不能应用于单标签（即单故障）版本。

为了调查这些技术的性能，我们对各种故障数量的故障版本进行了评估。对于每个主题程序，我们使用 F 中所有故障的组合生成了多个故障版本：0％（实际上表示单个故障），25％，50％，75％和 100％（表示全部错误版本的 F）。如果这些故障数量的组合数量超过 1000，则我们随机选择 1000 个故障版本以方便实验。否则，我们将详尽地生成所有可能的故障组合以产生故障版本。

在实验中，我们使用十倍交叉验证来评估模型的有效性。这些实验是在 8 位内核的 1600MHz CPU，64 位 Ubuntu 14.04 和 12GB RAM 上进行的。

实验结果

图 3 和表 II 显示了我们实验的准确性结果。图 3 中的方框图描绘了每个程序，每种技术和每种故障数量的 F-Measure 值，但 100％的故障数量除外，。表 II 中包括每个故障程序，技术和故障组合的平均 F 测量值的详细数值结果，包括 100％全故障版本。请注意，对于 1 故障版本（即 0％级别），使用 RAkEL 技术实现的 Label Powerset 不适用，因此，这些单元格留为空白。为了方便读者，我们在表格中突出显示了最准确的结果（最高分数和所有分数均在最高分数的 0.01 内）。

为了进行准确性评估，我们首先比较所有技术的整体准确性。无论使用 KNN 还是 MP 方法，Label Powerset，Binary Relevance 和多标签技术在准确性方面都大大优于单标签技术。对于问题转换方法，LP-KNN，BR-KNN，LP MP 和 BR-MP 提供了明显相似的结果。多标签 ML-KNN 技术也提供了类似的准确结果，而 ML-MP 技术提供了较不准确的结果，尤其是在版本几乎没有错误的情况下。

当考虑故障数量如何影响结果的准确性时，我们注意到随着故障数量的增加，单标签技术的准确性大大降低。随着故障数量的增加，问题转换技术和 ML-KNN 技术的准确性只会略有下降。这些技术（在准确性方面）比单标签技术要好多少。最后，ML-MP 是个例外，随着故障数量的增加，它具有更高的精度（和更稳定的精度）。

为了进行效率评估，我们在表 III 中列出了结果。对于每个程序，我们显示两行：一个用于训练阶段的标记为“ T”的行，另一个用于预测阶段的标记为“ P”的行。就训练和预测阶段的效率而言，单标签技术大大优于问题转换和多标签技术。对于问题转换方法，我们发现效率主要受基本分类算法的影响。我们发现，虽然 1-KNN，LP-KNN 和 BR-KNN 技术具有高效的训练阶段，但它们具有相对低效的预测阶段。相比之下，1-MP，LP-MP 和 BR-MP 技术在训练上花费的时间更多，而在预测上的时间则更少。

在相同的问题转换方法中，与基于 1-MP 的算法相比，基于 KNN 的算法在训练阶段花费的时间更少，而在预测阶段花费的时间更长。在各种问题转换方法中，对于相同的基本分类算法，我们发现 Binary Relevance 方法比 Label Powerset 更有效。

至于多标签技术，与 1-KNN 技术和相应的问题转换方法相反，ML-KNN 花费更多的训练时间，花费更少的预测时间。与 LP-MP 和 BR-MP 技术相比，ML-MP 在训练和预测方面均具有相对较高的效率。我们还获得了六个程序中每种算法的平均时间成本。 除单标签学习技术外，BR-KNN 技术在训练阶段的效率最高，而 ML-MP 技术在预测阶段的效率最高。

讨论

回顾第五节的所有结果时，我们观察到一些预料之中和预料之外的结果。

研究结果 1.对于单标签分类任务，单标签技术可提供可接受的 F 测量结果（0.6158–0.9216），并且在训练和测试阶段的时间成本都非常低。该经验结果表明，单标签分类技术对于具有高效率要求和单标签归因可能性的使用场景来说可能是一个不错的选择。

意义。对于被认为是稳定的程序，考虑到高效率和大量用户，单标签故障分类技术可以以较低的运行时开销成本提供足够的有效性。

图 3：箱形图，描绘了每个主题程序，每种技术和每种故障数量的 F 度量的中值（中心线）和方差。 黑框代表 1-KNN，红色代表 1-MP，绿色代表 LP-KNN，蓝色代表 LP-MP，洋红色代表 BR-KNN，青色代表 BR-MP，紫色代表 ML-KNN，棕色代表 ML-MP 。（100％故障数量被省略，因为它代表一个故障版本，因此可以从表 II 中的结果中完全解释出来。）

**研究结果 2.**多标签和问题转换技术获得了相对较高的准确性，并且在单标签和多标签任务中均优于单标签技术。当存在更多故障时，多标签和问题转换技术的性能也更好也就不足为奇了。 该结果表明，对于多标签分类任务（即许多软件工程任务的实际问题域），这些技术是更好的选择。

意义。对于相对不成熟的程序（例如，在 alpha 或 beta 测试版本中），鉴于多标签分类技术的高效性和相对较少的用户数量，多标签失败分类技术可能会提供更高的准确性，尤其是当这种精度是最需要的时候。

**研究结果 3.**尽管 ML-KNN 和问题转换技术对许多多故障版本同样有效，但 ML-KNN 技术在预测阶段更为有效。ML-KNN 在训练阶段呈现出相对较高的时间成本，但是它实现了较低的预测时间成本。

意义。与问题转换技术相比，在可能存在多种归因且训练对多种预测的要求较低的情况下，ML-KNN 是明智选择，对于许多软件工程任务（例如故障分类）来说，情况很可能如此。

**研究结果 4.**执行数据显示出一定程度的结构，使问题转换技术成为可行的选择。除了上面总结的三个发现之外，我们还对数据的这种特征进行了更深入的初步研究，以初步地解释问题转换方法的准确性成功，我们发现许多执行故障是由常见故障模式引起的。

意义。当现有的单标签技术的适应性太困难时，单标签技术的问题转换（例如标签功率集）在实践中可能是软件故障分类的可接受选择。我们有证据显示某种形式的多标签分类，无论是通过问题转换还是通过算法适应可以为可能包含多个故障的软件提供准确性优势。

对于研究问题 1，我们发现对于具有多个故障的主题程序，其中的许多故障确实会相互作用而导致故障，问题转换（即标签幂集和二进制相关性）和多标签分类技术都提供了更大的优势。其准确性通常超过单一标签。而且，当程序有很少（或单个）错误时，单标签技术可能是准确的。

对于研究问题 2，我们发现单一标签和问题转换后的 KNN 变体技术训练起来相对有效，但预测成本更高。我们还发现，多标签 KNN，ML-KNN 和所有基于 MP 的技术（单标签，问题转换和多标签）的训练成本相对较高，但预测效率也相对较高。

结论

与针对多标签条件的多标签和问题转换技术相比，单标签分类技术提供的准确性相对较差。软件工程数据会影响机器学习技术的有效性，例如问题转换技术可提供足够的有效性。未来的软件分类研究应特别注意可能应用多个标签的情况。在这种情况下，应该质疑传统的简化假设，即单标签分类可提供足够的准确性，并且应评估或使用某种形式的多标签分类，无论是通过问题转换的方式（例如，标签幂集还是二进制相关性）或专用的多标签分类技术。

将来，我们将进一步研究故障共现影响分类的方式，并设计分类器的专门变体，以潜在地定位故障及其影响共生的方式。我们还试图进一步探索这些发现如何影响软件工程研究领域中机器学习技术的使用。最后，我们将进一步研究已部署软件中的错误对于此类分类问题的行为方式可能会或可能不会有所不同。

致谢

本文由南京大学软件学院 2021 级硕士洪华翻译转述。