随着社会的不断发展，为满足人们的日常生活需求，软件出现了更新速度快、开发周期短等现象，与此同时，软件测试人员也迎来了新的挑战。据统计，Eclipse^[1]、Firefox^[2]等大型项目每天会收到近100份新问题报告^[3]，测试人员需要对新提交的问题报告进行处理，判断其中是否含有新发现的问题。但事实是，在这些大型软件的缺陷报告库中，有近1/3的问题报告被测试人员标记为重复问题报告^[4]。特别是在众包测试平台等测试服务类平台的管理过程中，任务发布者需要根据用户提交的问题报告质量及数量支付相应的酬劳，所以问题报告的评判工作尤为重要。然而，人工评阅问题报告是个十分枯燥且低效的过程，如何对问题报告进行自动化评价成为值得研究的课题。

为了能够自动化判定用户提交的问题报告是否为重复问题报告或虚假问题报告，本文在Thomas等^[5]研究基础上，提出了一种基于BM25算法的问题报告自动化检测方法。BM25模型是二元独立模型BIM的一种扩展，相比较于传统的向量空间模型的相似度计算方法，BM25模型在计算相似度时考虑了单词在查询、文档中的权值以及多个可调节参数，在实际应用中效果明显高于BIM模型。

本文方法通过建模和分类实现对问题报告的自动化评价，通过在软件测试大赛的真实数据集上验证其有效性；另外在相同的数据集上与传统的向量空间模型方法进行对比，实验证明本文方法在查全率、查准率、F₁值(准确率和召回率的调和平均值)和平均准确率均值(mean average precision, MAP)等评价指标上都高于向量空间模型，同时自动化的评价方式提高了检测问题报告的效率。

1 相关研究及模型 1.1 相关研究

近年来，问题报告的研究热点主要集中在重复问题报告的检测上。Runeson等^[6]首次对重复问题报告检测进行了研究，他们将索尼爱立信移动通信公司的问题报告库作为其实验数据集，首先对问题报告的文本信息进行向量化及归一化等预处理，然后计算问题报告间的相似度，实验结果的准确率可达到30%左右。在Runeson等的研究基础上，Wang等^[7]结合软件的执行信息，给出了问题报告相似度的2种定义：自然语言相似度以及执行信息相似度。实验结果在查全率和查准率方面都取得了不错的效果，分别为93%和67%。

Kaushik等^[8]比较了基于向量空间模型和主题模型的检测重复问题报告的性能，选取了3种主题模型：LSI^[9-10]、LDA^[11]和Random Projections^[12]。对于向量空间模型，选用了余弦距离计算相似度，并尝试了多种方法计算词项权重，实验结果表明基于向量空间模型的方法效果更好。

Sun等^[13]针对BM25不适用于有重复词和长文本查询的特点，提出了BM25Ext(即扩展BM25)方法计算问题报告间的相似度，还计算了报告中模块和产品等元数据的相似度，计算结果线性结合得出总的相似度值。在3个大型软件上的实验结果证明了该方法与作者之前提出的模型相比召回率提高了10%~27%，平均准确度提高了17%~23%。Nguyen等^[14]提出将BM25Ext和LDA 2种模型相结合，并且最后的总相似度值也是由2个模型得到的相似度值线性结合而成，实验结果表明该方法与文^[13]的方法相比较，性能有所提升。

Wang等^[15]认为众包测试下跨领域的数据差异会对跨领域问题报告分类模型产生影响，不同于其他方法利用历史数据训练分类器，该文提出了一个跨领域分类模型，利用堆栈去噪自编码器从原始的文本中自动学习高级特性，并以此为依据对问题报告进行分类。该方法对百度众包测试平台上的10个领域的58个项目进行了实验，结果表明了该方法具有实用性和有效性。

1.2 信息检索模型

信息检索(informatica retrieval)是指用户根据需求从信息集合中查询、获取相关信息的方法^[16-17]。通常被分为广义信息检索和狭义信息检索。常用的信息检索模型有向量空间模型、概率检索模型和主题模型。

向量空间模型是由Salton等^[16]于20世纪70年代提出，并且首次在SMART文本检索系统中成功应用。作为经典的相似度计算模型，通过特征选取和权重计算将文档表示为文档空间的向量，再通过计算向量间的相似性来度量文档间的相似性。在处理文本时最常用的向量空间相似性度量方式是余弦距离。

主题模型是一种用无监督学习的方式对文档隐含语义结构进行聚类的统计模型^[18]，主要应用于语义分析和文本挖掘问题中，同时还在生物信息学研究中得以应用^[19]。主题模型是一种典型的词袋模型，如图 1所示^[20]，它认为一篇文档是由好多个主题构成，而每个主题是一组词组成的集合，词与词之间没有顺序关系。常见的主题模型为隐含Dirichlet分布(latent Dirichlet allocation, LDA)。

概率检索模型在当前信息检索领域中被认为是效果最好的模型之一。该模型与Bayes分类的思想相近，但本质上有所区别，其根本目的不在于对查询结果进行分类，而是根据相关度得分对与查询内容相关的文档进行排序。

BM25^[21]作为一种经典的用于结构化文档检索的概率模型计算公式，在商业搜索引擎领域已获得广泛应用。BM25在TF-IDF(term frequency-inverse document frequency)的基础上增加了2个可调参数k₁和b，分别代表“词语频率饱和度”和“字段长度规约”，用于调节词频和文档长度在权重计算中起到的作用，实验证明当k₁=1.2，b=0.75时, BM25算法得出的结果是最合理的。

2 基于BM25算法的问题报告检测方法

本节提出了一种基于BM25算法的问题报告质量检测方法，主要分为4步：1)对问题报告进行预处理；2)根据测试需求建立问题报告匹配库；3)采用BM25算法计算报告相关度；4)对问题报告进行分类。

2.1 问题报告预处理

问题报告的预处理包括2个工作：问题报告文本的提取和预处理。图 2展示了在Bugzilla中创建问题报告的页面，问题报告中的信息通常包括产品、组件、版本、摘要、描述等。测试人员将问题报告提交之后还会得到一个BugID。

首先，需要从问题报告中提取出BugID、问题描述等关键字段内容并存放到.txt文档中，然后对文档内容进行分词、提取词干和去停用词等预处理。停用词库通常需要根据软件的需求规格说明书内容进行调整。

例如，对于问题“The left turn signal is on all the time”，若使用常用的停用词库，“on”就会被去掉，那么这条问题描述的原义将会被改变，因此需要在实际的场景中建立恰当的停用词库。需要注意的是，在对中文描述的问题报告进行分词处理时，需要注意词语的完整性，例如“麻辣烫”，当该词语被作为一个整体时，它的词性为名词，但是当其被分成“麻” “辣” “烫”3个词时，其词性都变成了形容词，与文本原义不符。

2.2 建立匹配库

本文主要研究如何在已知软件部分缺陷的前提下，对新提交的问题报告去假和去重，研究过程中的相关度计算主要基于BM25算法，此算法的一个明显缺陷是只能针对待检索语素与目标文档有重合时进行处理，而无法从语义的角度计算相关度。因此为了使新提交问题的处理结果更加准确，在建立的问题报告匹配库中需要包含以下3类内容：已确认的问题描述、已确认问题描述的相似描述以及软件需求的逆向描述。

需求的逆向描述可以理解为需求的否命题。假设有一段需求描述为：“当速度V大于零时，数据输出接口‘速度方向’为‘右行’；当速度V小于零时，数据输出接口‘速度方向’为‘左行’；当速度V等于零时，数据输出接口‘速度方向’为‘停止’”。该段需求的逆向描述如表 1所示。

将需求的逆向描述添加到问题报告匹配库中的作用主要有：1)可以在计算相似度时去除掉一些和待测软件完全无关的虚假问题报告；2)有助于发现软件中的新问题。针对第2点，当多份问题报告都与某一条需求的逆向描述相似度较高时，但该条描述并未确认为软件问题，那么开发人员就会通过复现问题或查看代码的方式去评判它是否为新的问题。

由于每个测试人员对问题的描述习惯不同，表达时的措辞也是千差万别，因此针对每一个已确认的问题，人工添加多条同语义描述，在问题报告匹配库中添加与已确认问题描述的同语义描述，可以提高问题报告质量检测的查全率和查准率。

在建立匹配库时，对匹配库中所有的文档进行标签分类。针对每一个已确认问题，将其问题描述、同语义描述以及对应需求的逆向描述作为一个类别, 将其余未对应于确认问题的需求的逆向描述作为一个类别，为测试人员新提交的问题报告分类提供依据。

2.3 计算相关度

本文采用基于BM25算法和Lucene实现的搜索工具计算新提交问题报告与匹配库之间的相关度。Lucene是一个开源的全文检索引擎工具包，能够作为架构方便开发人员实现全文检索的功能。

对于待检索项(如关键字)，Lucene会按照一定的评分规则对检索库中的每份文档打分，并返回一个结果列表，列表按照得分对文档进行降序排列。早期的Lucene直接采用基于TF-IDF的方法作为评分机制。其中TF代表词频，对于已给定词语q_i，其在文本D_j中的TF值tf_{i, j}计算公式为

$ {\rm{t}}{{\rm{f}}_{i,j}} = \frac{{{n_{i,j}}}}{{\sum\limits_k {{n_{k,j}}} }}. $

(1)

其中：n_{i, j}表示词语q_i在文本D_j中出现的频数，$\sum\limits_k {{n_{k, j}}} $表示D_j中所包含单词的总数。

IDF代表逆向文本频率值，IDF值idf_i的计算公式为

$ {\rm{id}}{{\rm{f}}_i} = {\rm{lg}}\frac{{|D|}}{{|\{ d:{q_i} \in d\} | + 1}}. $

(2)

其中：|D|表示集合中包含的文档总数，|{d:q_i∈d}|表示集合中含有词语q_i的文档数量。由此可得词语q_i的TF-IDF值tf-idf_{i, j}的计算公式为

$ {\rm{tf}} - {\rm{id}}{{\rm{f}}_{i,j}} = {\rm{t}}{{\rm{f}}_{ij}} \cdot {\rm{id}}{{\rm{f}}_i}. $

(3)

Lucene中对TF-IDF进行了一定的调整，相应的相关度计算公式为

$ \begin{array}{*{20}{l}} {{\rm{similarity}} = {\rm{lg}}(|D|/(|\{ d:{q_i} \in d\} | + 1)) \times }\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{sqrt}} ({\rm{tf}}) \times (1/ {\mathop{\rm sqrt}\nolimits} ( {\rm{length}})).} \end{array} $

(4)

其中：tf表示词语q_i在文本D_j中出现的频率，1/sqrt(length)是对文本的总长度进行归一化。

后期经过改进，Lucene采用基于BM25算法的计算方法作为新的评分规则。BM25算法实际是二元独立模型的得分函数的一种拓展，在原得分函数的基础上加入单词在查询和文档中的权值, 其计算公式如下：

$ {\rm{Score}}\left( {Q,d} \right) = \sum\limits_i^n {{W_i}} \cdot R({q_i},d). $

(5)

其中：Q表示一条检索语句Query，q_i表示Q解析之后的一个语素(对中文而言，可以把对Q的分词作为语素分析，每个词看成语素q_i)；d表示一个搜索结果文档；R(q_i, d)表示语素q_i与文档d的相关性得分; W_i表示语素q_i的权重。计算一个词在一个文档相关性中的权重的方法有多种，较常用的是IDF。BM25算法中的IDF与式(2)的计算方法略有不同，其计算公式如下：

$ {\rm{IDF}} ({q_i}) = {\rm{lg}}\frac{{N - n({q_i}) + 0.5}}{{n({q_i}) + 0.5}}. $

(6)

其中: N为索引中的全部文档数，n(q_i)为包含了q_i的文档数。根据式(6)可以看出，对于给定的文档库，包含了q_i的文档数量越多，q_i的权重则越低。这种权重的计算方式可以理解为：当很多文档都包含了q_i时，q_i在检索时起到的区分作用就不再明显，因此使用q_i来判断相关性时的有效性就较低。

语素q_i与文档d的相关性得分R(q_i, d)在BM25算法中一般形式为

$ R({q_i},d) = \frac{{{f_i}({k_1} + 1)}}{{{f_i} + K}}\frac{{{\rm{q}}{{\rm{f}}_i} \cdot ({k_2} + 1)}}{{{\rm{q}}{{\rm{f}}_i} + {k_2}}}. $

(7)

其中，

$ K = {k_1}\left( {1 - b + b\frac{{{\rm{dl}}}}{{{\rm{avgdl}}}}} \right). $

(8)

其中: k₁、k₂、b为调节因子，通常根据经验设置，一般k₁=1.2，b=0.75；f_i为q_i在d中的出现频率，qf_i为q_i在Query中的出现频率；dl为文档d的长度，avgdl为所有文档的平均长度。由于绝大部分情况下，q_i在Query中只会出现一次，即qf_i=1，因此式(8)可以简化为

$ R({q_i},d) = \frac{{{f_i}({k_1} + 1)}}{{{f_i} + K}}. $

(9)

从K的定义中可以看到，参数b的作用是调整文档长度对相关性影响的大小。b越大，文档长度对相关性得分的影响越大，反之越小。而文档的相对长度越长，K值将越大，则相关性得分会越小。这可以理解为，当文档较长时，包含q_i的机会越大，因此，同等f_i的情况下，长文档与q_i的相关性应该比短文档与q_i的相关性弱。

综上，BM25算法的相关性得分公式可总结为

$ {\rm{Score}} (Q,d) = \sum\limits_i^n {{\rm{ IDF }}} ({q_i})\frac{{{f_i}({k_1} + 1)}}{{{f_i} + {k_1}\left( {1 - b + b\frac{{{\rm{dl}}}}{{{\rm{avgdl}}}}} \right)}}. $

(10)

2.4 问题报告分类

得到对问题报告进行相关度评分排序后，在优化k最近邻(k-nearest neighbor，KNN)分类算法的基础上对问题报告进行分类。

KNN分类算法在理论上相对成熟，同时也是最简单的机器学习算法之一。该方法的核心思想是：存在一个数据样本集合，并且该集合中的数据都有标签；输入一个未被标签的测试数据，将测试数据的特征和集合中对应的特征进行比较，提取出样本集中k个特征最相似数据(最近邻)的分类标签，那么该测试数据就属于这个类别。

本文方法对KNN分类算法进行优化，当一份问题报告与问题报告匹配库进行相关度评分后会得到一个相关度评分列表，同时每一个与问题报告相匹配的文档都存在标签，根据需求选取列表中的前几项，将相同类别的文档分数相加，得分最高的类别就是该问题报告最终的分类类别。以此来判断问题报告的真实性以及是否是重复报告。举例说明：假设当前测试人员需要对一份新提交的问题报告进行分类，将其进行预处理后与问题报告匹配库中的报告进行匹配，得出的相关度列表如表 2所示。

由于在匹配库中对同一个问题的3种表达方式进行统一标签，选取列表中前3名的结果，并对同一个标签的得分数进行累加操作，由表 2可知该份待分类报告与问题A的相关度得分为0.38，与问题B的相关度得分为0.47，因此该份问题报告最后被分类为问题B。

3 实验分析

本节实验主要分为2个部分：实验1为验证实验，通过在真实的软件测试大赛数据集上进行实验，验证本文所提出的方法的有效性；实验2为对比实验，在同样的实验配置下，将本文方法与传统的基于VSM的问题报告质量检测方法进行对比，并以查全率、查准率、F₁值和MAP等评价指标作为评判依据，评判2种方法的优劣。

3.1 实验数据

本文数据来源于某软件测试大赛嵌入式分项赛近3年选手提交的所有问题报告单。每一年的比赛分为夏季预选赛、秋季预选赛、省赛和总决赛，由于夏季预选赛和秋季预选赛采用相同的题目，因此共收集了9道试题和7 422份问题报告。比赛题目为一份软件设计需求文档和一个待测软件。选手根据需求文档设计测试用例以及编写测试脚本，通过运行测试脚本发现软件中预埋的问题，记录问题并提交问题报告。传统的人工评阅方式邀请多位软件测试领域专家，对选手提交的问题报告进行评阅。收集的数据如表 3所示。

3.2 实验设计 3.2.1 有效性实验

本节对表 2描述的9组数据进行实验，验证本文提出方法的有效性。实验步骤如下：首先采用中文分词工具IK Analyzer对问题报告进行预处理，在使用IK Analyzer时，需要根据实际需求修改停用词典stopwords.dic以及扩展词典ext.dic；其次将试题的需求文档进行逆向描述形成文档，并整合标准答案以及每个标准答案的5种相似描述建立问题报告的匹配库；再次采用节3.3介绍的方法计算问题报告相关度；最后根据相关度评分排名进行加权累加得到最后的相似度得分，以专家阅卷的结果为参考依据，判断该问题报告是否命中标准答案。

对问题报告的评判是二分类问题，可将问题的真实类别与本文方法预测的类别组合划分为以下4种情况：真正例(true positive，TP)、假正例(false positive, FP)、真反例(true negative, TN)、假反例(false negative, FN)，最终得到TP+FP+TN+FN=问题报告总数。分类结果的“混淆矩阵”(confusion matrix)如表 4所示。

本实验选取查全率、查准率、F₁值和MAP作为评价指标，具体定义和计算方式如下。

1) 查全率(Recall)：又称为召回率，用R来表示，该指标是为了计算利用本文所提出的方法查询到的真问题数量占问题报告单中实际存在的真问题数量的比例。

$ R = [{\rm{TP}}/({\rm{TP}} + {\rm{FN}})] \times 100\% . $

(11)

2) 查准率(Precision)：用P表示，该指标是为了计算本文方法查询到的真问题数占查询到的问题总数的比例。

$ P = [{\rm{TP}}/({\rm{TP}} + {\rm{FP}})] \times 100\% . $

(12)

3) F₁值：通常情况下，希望实验结果在R和P上都有不错的表现，可是这2个指标本就是一对矛盾体，当某一个指标值偏高时，另一个一定是偏低的，所以采用F₁值，即R和P的调和平均值来对实验结果进行综合考量。当对R和P没有比重要求时，

$ {F_1} = [2PR/(P + R)] \times 100\% . $

(13)

在实际场景中，如果需要特别关注R或P，那么就可以将F₁值写成加权调和平均值F_β，

$ {F_\beta } = [(1 + {\beta ^2})PR/({\beta ^2}P + R)] \times 100\% . $

(14)

4) MAP：该单值指标是每个相关文档检索结果的平均准确率的算术平均值，反映了系统在全部相关文档上的性能。MAP值越高，则系统检索出来的相关文档越靠前，当MAP值为0时，表示系统没有返回相关文档。举例说明，假设现有2个查询词M和N，M对应的相关文档有5篇，N对应的相关文档有6篇。经过某系统的检索，M检索出4篇相关文档，排序分别为1, 3, 5, 6；同时，N检索出3篇相关文档，排序分别为2, 4, 5。M的平均准确率为(1/1+2/3+3/5+4/6)/4=73%; N的平均准确率为(1/2+2/4+3/5)/3=53%; MAP值为(0.73+0.53)/2=63%。

3.2.2 对比实验

完成性能对比实验涉及到的系统和应用软件为：64位Win7系统、intel(R) Core(TM) i5-6200U CPU、版本为Mars.1 Release的Eclipse Java EE IDE for Web Developers、JDK1.8。

BM25模型在结构性文档的搜索排序上有不错的表现。为研究BM25模型与传统的信息检索模型在查全率、查准率等指标上的差异，本节选取了经典的向量空间模型作为实验对比对象，在相同的实验数据集及实验配置下进行了对比实验。

向量空间模型将对文本信息的处理简化为向量空间中向量间的运算，每一个文档都可以表示成一个n维向量，例如文档D可表示为D={d₁, d₂, …, d_n}，d_i则表示文档D中第i个词的权重，也就是该词项在整篇文档中的重要程度。不同的权重计算方法会对文本相似度计算产生影响，常用的权重计算方法为TF-IDF。

在对文档向量进行规约后，便可通过计算向量间的相似性来表示文档的相似度。常见的3种向量相似度计算方法为余弦相似度、Dice相似度和Jaccard相似度。本次实验的向量空间模型采用TF-IDF的特征提取方法对问题报告进行建模，利用余弦距离来计算文档相似度。具体计算方式如下：

$ {\rm{Si}}{{\rm{m}}_{{\rm{cos}}}}(\mathit{\boldsymbol{D}},\mathit{\boldsymbol{Q}}) = \frac{{\mathit{\boldsymbol{D}} \cdot \mathit{\boldsymbol{Q}}}}{{|\mathit{\boldsymbol{D}}|{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} |\mathit{\boldsymbol{Q}}|}}. $

(15)

3.3 实验结果及分析 3.3.1 有效性实验结果

3届软件测试大赛问题报告质量检测方法有效性实验结果如表 5所示。

针对3届软件测试大赛数据，采用本文提出的方法得出的4项评价指标的平均值分别为：R值49.66%，P值81.75%，F₁值61.79%以及MAP值52.21%。结果表明，本文提出的方法具有较高的查准率。

纵向观察3年的预选赛数据，可以发现R和P存在上升的趋势，原因是随着测试大赛及相关培训的逐年开展，参赛选手的总体水平渐渐提升，相应的问题发现能力以及对问题描述的准确度逐年提升，问题描述得越规范，该方法对问题报告的判定的准确度越高。但是2018年的决赛数据显示，R和P两项指标均不理想，分析原因发现2018年决赛题目较难，待测件需求不易理解，导致选手提交的问题报告质量下滑，故而影响了查全率和查准率。

3.3.2 对比实验结果

本文方法与基于VSM模型方法在相同数据集上的实验结果如表 6所示。

实验结果表明，本文提出的方法和传统的VSM模型相比R提高了5.80%，P提高了4.39%，F₁值提高了5.81%，MAP提高了4.11%。从数据上可以直观地看出本文方法在问题报告质量评价效果上要优于VSM模型。

4 结论

本文提出了一种基于BM25算法的问题报告自动化检测方法。首先，对问题报告进行分词、提取词干和去停用词等预处理；其次，根据测试需求和测试报告样本建立问题报告匹配库；然后，利用BM25算法对问题报告进行相关度评分；最后，依据优化的KNN算法对问题报告进行分类，从而对问题报告进行质量评估。通过在真实的软件测试大赛的数据集上进行实验证明了本文所提出的方法的可行性和有效性；同时还与传统的VSM模型进行对比实验，结果证明本文方法在查全率和查准率上分别提高了5.8%和4.39%。另外，本文提出的方法还存在着一定的局限性，本文针对的应用场景是在待测件已知问题的情况下，但实际应用场景中多数是无法提前已知待测系统存在的问题的。今后，需要在实际应用场景下进行深入研究，同时要优化算法进一步提高问题报告的查全率和查准率。