语义扩展连续查询的重复错误报告预测①

张骞月,赵瑞莲,王微微

(北京化工大学 信息科学与技术学院,北京 100029)

1 引言

为保证软件系统的质量与性能,软件系统在发布或上线之前,需要进行大量的测试[1].测试人员一旦检测出软件系统存在问题,则将提交错误报告(bug report),以供开发人员对错误进行修复.错误报告一般含有对错误的概要说明(title)、详细描述(description)、提交时间、提交人、错误表现截图、代码片段等相关信息.

由于软件项目规模的增大和复杂性的增加,导致参与测试工作的人员较多,不同测试人员可能会检测到同一个错误,这样就会造成针对同一错误,重复提交错误报告(duplicate bug report)的可能[2].而重复错误报告的存在,将降低开发人员修复错误的效率.因此,如何避免重复错误报告的提交已成为近年来软件工程领域新的研究热点.目前,与重复错误报告相关的研究主要集中在重复错误报告检索与重复错误报告预测两方面.

重复错误报告检索是指:针对错误报告库,采用自然语言处理和信息检索技术,检索出重复的错误报告.如Wang 等[3]将错误报告中的自然语言描述与执行信息作为查询依据,通过信息检索技术,检测错误报告库中是否存在重复的错误报告.该方法虽能通过对比错误报告中自然语言描述以及执行信息的相似度,检索得出重复错误报告,但该方法将错误报告的自然语言描述作为一个整体要素进行检索,未对错误报告的自然语言描述进行深入的语义挖掘,使得检索的准确率不高.范道远等[4]借鉴集成测试的思想,提出了一种将错误报告文本信息与分类信息结合的重复错误报告检索方法,该方法虽将分类信息与文本信息结合作为判定重复错误报告的依据,但也未对错误报告文本信息进行语义挖掘,其对重复错误报告检索准确率的提升仍然有限.Chaparro 等[5,6]基于文本检索的错误定位方法,通过对错误报告中的文本信息进行语义分析,以错误报告中的可观测行为OB (observed behavior)、错误复现步骤S2R (steps to reproduce)等作为查询要素,通过各种组合方式,进行重复错误报告检索,提高了检索准确度.但该方法中对于OB、S2R 等语句的识别主要依靠人为判定与标注,在引入人为偏差的同时,也降低了重复错误报告检索的自动化程度.为了更进一步地提高重复错误报告的检索效率,Sun 等[7]提出一种基于判别模型的重复错误报告检索方法,通过对错误报告的信息进行特征提取与对比,在错误报告库中检索相似的错误报告.该方法虽然较大程度提高了重复错误报告的检索准确率,但动态建模开销较大.

由于重复错误报告检索是基于完整的错误报告,无法避免重复错误报告的产生.因此,Hindle 等[8]借鉴搜索引擎的思想,给出了一种重复错误报告预测方法.重复错误报告预测是指:在错误报告提交前对错误报告进行预测,以避免重复错误报告的产生.Hindle 等提出的重复错误报告预测方法,可在错误报告编写过程中,对当前已输入的文本内容进行实时检索,依据检索结果判定当前撰写的报告是否已在错误报告库中,避免重复错误报告的提交.但由于其检索过程采用倒排表索引技术[9],仅通过查询词序列与错误报告的词法相关性进行检索,并未对错误报告进行深入的语义挖掘.因此,该方法在重复错误报告预测的准确度仍有很大的改进空间.此外,随着错误报告库的不断增大,索引文件所占的内存也在不断增大[10],导致索引空间过大,检索效率较低.

因此,本文提出一种基于语义扩展连续查询的重复错误报告预测方法,通过对错误报告进行主题语义挖掘,确定错误报告的主题词,构建基于主题模型的错误报告索引词库,以减小错误报告索引空间,建立主题词-错误报告之间的语义关系;在此基础上,对查询词序列进行同义词补充及基于语义的后续词组扩展,以提升查询准确度;同时,在检索过程中,利用语义扩展后的查询词序列对主题索引进行检索,以提升检索效果及效率.通过实验验证,相较于传统方法,本文方法减小了50% 以上的索引空间,在检索速度上提升了41%–73%,预测效果最高提升33.6%.

2 基于主题模型的错误报告索引词库构建

传统的倒排表索引技术依据词与错误报告的包含关系建立词与错误报告的索引联系[11,12],并且根据错误报告中包含的词全集建立错误报告的索引词库.一方面,仅靠包含关系建立起来的词与错误报告之间的语义关联可能导致检索的准确率低下;另一方面,以词全集作为错误报告索引词库也造成索引空间的不断增大,降低了检索效率.

基于此,本文提出一种基于主题模型的错误报告索引词库构建方法,通过对错误报告进行主题语义挖掘,深化词与错误报告之间的语义关联,确定错误报告主题词,建立错误报告主题词与错误报告之间的语义关系,构建错误报告主题索引词库;同时,为减小错误报告索引空间,在构建错误报告主题索引词库时,依据挖掘得到的错误报告主题,进行错误报告主题词确定,以缩小错误报告索引词库,从而减小索引空间.

2.1 错误报告主题挖掘

针对错误报告主题挖掘,本文借鉴自然语言处理中文档主题分类思想,利用常用的LDA (latent Dirichlet allocation)主题模型[13,14],对库中的错误报告进行主题挖掘,获取错误报告的主题分布与针对每个主题的词项分布,由此可计算每份错误报告的中心主题,以及与中心主题高度相关的若干关键词,这些关键词即为错误报告的主题词.

在LDA 主题模型中,假设错误报告主题与主题中词项的先验分布均为Dirichlet 分布,则对于任一错误报告,其主题分布为:

其中,α为分布的超参数,是一个k维向量;k代表主题个数.

对于任一主题,其词项分布为:

其中,η为分布的超参数,是一个v维向量.v代表词库中词的个数.

在利用LDA 主题模型对错误报告进行主题挖掘时,设定的主题数目越多,对错误报告的语义划分越细,后续建立的词-错误报告关系就越多;设定的主题数目越少,对错误报告的划分越粗,后续建立的词-错误报告关系就越少.因此,为了平衡检索的准确率与减小索引空间的需求,需要合理设定主题数目.

2.2 错误报告主题词确定

由于LDA 主题模型得到的词概率分布中所含的词全集作为错误报告的主题词,则错误报告主题索引空间太大.为了减小错误报告主题索引空间,本文依据挖掘得到的错误报告主题,确定错误报告的主题词,剔除与主题关联度不大的词,将与主题较为相关的词选入主题索引词库.但由于设置的主题个数的局限性,可能会遗漏一些在主题的词项分布中概率数值较低但对错误报告区分度很高的词,为避免遗漏此类主题词,本文在确定错误报告主题词的过程中,利用TF-IDF 进行词项权重判定,以保留词频较低但较为重要的词项,也可有效避免常用词对主题词的影响.

TF-IDF 公式计算如下:

其中,tf(t,d) 表示词t在错误报告d中出现的频率;N代表语料库中错误报告的总数;df(t)代表包含词t的错误报告数.ln(N/(df(t)+1))又可写作idf,即逆文档频率.

TF-IDF 代表的含义为:一个词的重要程度跟它在错误报告中出现的次数成正比[15],跟它在语料库出现的次数成反比,通过词频(tf)与逆文档频率(idf)的乘积计算,其值越大,则表明该词与错误报告的关联越大.因此,结合TF-IDF 权衡词项权重,可有效避免常用词对主题词的影响,也能避免漏选低频主题词的情况.

结合LDA的错误报告主题语义挖掘与TF-IDF 词项权重判定,可得出与主题相关性较高及与错误报告关联度较大的词,这些词可作为错误报告的主题词.错误报告主题词确定流程如图1所示.

图1 错误报告主题词确定流程

2.3 主题词-错误报告关系构建

为构建错误报告主题索引词库,在确定了错误报告主题词的基础上,还需要对错误报告主题词与错误报告本身建立关系.

在传统的错误报告索引词库构建中,词与错误报告之间的关系为包含关系[16],即若某词包含于若干错误报告中,则该词与这些错误报告形成关联关系.但这种包含关系不能体现词与错误报告更深层次的语义关系,所以检索效果不佳.

因此,本文通过建立错误报告主题词与错误报告的语义关系,深化错误报告主题词与错误报告之间的语义关联,以提升检索效果.

图2为主题词-错误报告关系示例图.在主题词与错误报告的语义关系中,主题是主题词与错误报告的关系媒介,即主题词与错误报告的关联是通过同属于某一主题形成的.

图2 主题词-错误报告关系示例图

3 基于语义扩展连续查询的重复错误报告预测

为提高重复错误报告预测的准确率与检索效率,本文提出一种基于语义扩展连续查询的重复错误报告预测方法,框架如图3所示,主要由错误报告主题索引词库构建、查询词序列扩展、基于连续查询的错误报告检索,以及预测结果排序4 个部分组成.

图3 基于语义扩展连续查询重复错误报告预测方法

对初始查询词序列进行基于语义上下文的扩展,可以得到初始查询词序列的同义词组及语义后续词组,形成当前查询词扩展序列.同时,由于库中错误报告数量庞大,为提升检索效率,本文通过基于连续查询的错误报告检索算法,对当前查询词扩展序列进行检索.为保证预测结果与查询词序列在语义上更具相关性,对检索得到的相关错误报告,依据文本相似度进行排序,以此为最终的预测结果.

3.1 查询词序列扩展

在重复错误报告连续查询时,为提高重复错误报告的查全率,本文通过当前词的同义词补充与后续词组预测,对初始查询词序列进行基于语义上下文的扩展,形成当前词的扩展序列.

(1)当前词同义词补充

对当前词进行同义词补充的目的有两个,一是若当前词在错误报告主题索引词库中不存在时,对当前词进行同义词补充,可以使补充的同义词在错误报告主题索引词库中;二是通过当前词同义词补充,扩大当前词关联的错误报告范围,可提升查全率.

(2)基于语义的后续词组预测

当查询词序列较短时,由于输入的词较少,查询信息难以完整,仅依靠同义词补充,并不能很好地将查询信息补充完整,查询检索的准确率无法提升.因此,可通过对当前词的同义词组,进行基于语义上下文的后续词组预测,得到<当前词,同义词,后续词>的若干三元组,作为当前词的扩展序列.通过基于语义的后续词组预测,得到当前词及其同义词组的语义下文词组,从语义上对查询信息进行了完善,有助于提升重复错误报告的查全率.

3.2 基于连续查询的错误报告检索算法

在传统的错误报告检索中,检索算法大多基于倒排表设计.倒排表索引词库中包含的词为语料库中所有的词;同时,倒排表索引结构的构建是基于词与错误报告的包含关系,这就使得无论对检索算法如何改进,由于索引空间是不变的,检索效率的提升也是有限的.因此,为进一步提升检索效率,本文提出一种基于错误报告主题索引词库的连续查询错误报告检索算法,利用基于语义预测的前项查询词扩展序列,在错误报告主题索引词库中进行检索时,可以缩小检索空间,大幅提升检索效率.

在查询词序列扩展时,对当前词的同义词组进行基于语义的后续词组预测,得到当前词的扩展序列<当前词,同义词,后续词>,后续词中有可能含有下一个要输入的词,由此可知,当前词也极有可能包含在其前项词扩展序列的后续词中.扩展序列后续词的数量显然小于错误报告主题索引词库中词的数量.所以,若在错误报告主题索引词库中对当前词的扩展序列进行检索时,先在其前项词的扩展序列中检索当前词,若当前词包含在其前项词的扩展序列中,借助前项词扩展序列的检索结果,可以快速得到当前词扩展序列的检索结果,较大程度地提升检索效率.因此,基于连续查询的错误报告检索算法如算法1.

算法1.基于连续查询的错误报告检索算法1) Buildsequence(input_word,synonym_word,conse-quent_word) //建立当前词扩展序列;2) Length(initial_sequence,input_word) //判断当前词在查询词序列中的位置;If(Length(initial_sequence,input_word)==0){Search index}//若当前词为第一个输入词,即不存在前项词,则在错误报告主题索引中进行检索;3) Else Search preceding_sequence//否则检索其前项词的扩展序列;If succeed{return index_report//若在其前项词扩展序列中检索到当前词,则返回相关错误报告;}Else Search index//否则继续在错误报告主题索引中检索.

3.3 重复错误报告预测结果排序

在错误报告主题索引中,主题词-错误报告关系是由主题词与错误报告的主题相关性构建起来的,因此,检索得到的错误报告是与查询词序列具有主题相关性的.但是由于主题数目的有限性,使得仅通过主题相关性,无法准确表征词在错误报告中的重要性.所以,仅以主题相关性作为预测结果是不全面的.

由于TF-IDF、BM25 等文本相似性算法比较简单,能够快速且较为准确地计算出查询语句与文档的相似性,在实时搜索中具有较强的实用性.因此,为了保证检索实时性与查询结果的准确性,本文采用文本相似性与主题相关性结合的方式对重复错误报告预测结果进行排序,即在基于连续查询的错误报告检索结果的基础上,对检索得到的错误报告与查询词序列进行文本相似性计算,将计算结果与错误报告主题相似度求和,以此作为重复错误报告预测结果的排序依据.

4 实验设计与结果分析

4.1 数据集

为验证方法的有效性,针对GoogleCode、LaunchPad、Bugzilla 三个错误报告管理系统,选取了12 个开源项目,并收集了错误报告254 883 份,进行实验分析.数据集信息如表1所示.

表1 实验数据集

4.2 实验设计

为验证本文提出方法的有效性,本文设计了多组对比实验,从索引空间、检索效率、预测效果3 个方面对本文方法进行验证.此外,在检索效率的对比实验中,单独设置消融实验,以验证本文方法各模块对整体方法检索效率提升的贡献.

Lucene 是目前常用的全文检索引擎架构,使用倒排表索引与全文检索算法.本文将其作为对照组方法进行对比实验.

(1)基于主题模型的错误报告索引空间分析

随着错误报告库的不断增大,错误报告的索引空间也在不断增大.过大的错误报告索引空间会降低错误报告检索效率.本文通过构建基于主题模型的错误报告索引词库,缩小错误报告索引空间.将基于主题模型的错误报告索引词库与倒排表索引词库进行词数对比,验证基于主题模型的错误报告索引词库在索引空间上的优越性.

本文使用LDA 主题模型对数据集建模,设置主题数120,分别得到该参数下基于主题的词与错误报告的概率分布,再利用TF-IDF 算法确定错误报告主题词,构建基于主题模型的错误报告索引词库.倒排表索引词库的构建方法为以Lucene 全文检索框架自带的Indexwriter 对数据集中的错误报告进行倒排表索引构建,得到倒排表索引词库.通过计算倒排表索引词库与基于主题模型的错误报告索引词库中的词数,进行索引空间对比.

(2)基于连续查询的错误报告检索效率分析

检索效率分析旨在验证本文提出的基于连续查询的错误报告检索算法的优越性与查询词序列扩展模块的必要性.在评价检索效率时,通用指标为查全率、查准率与检索速度,检索速度通常采用检索时间的长短表征.为了综合衡量查全率与查准率,本文采用F1-score作为评价指标.由于本文方法由多个模块组成,需要设置消融实验,进一步验证基于主题模型的错误报告索引词库、查询词序列扩展、基于连续查询的错误报告检索算法3 个模块对本文方法在检索效率方面的提升.

基于连续查询的错误报告检索算法中,需要使用查询词序列扩展模块中的变量,因此,将基于连续查询的错误报告检索算法与查询词序列扩展看作一个整体模块进行消融实验,设计如下:

使用Lucene 作为实验对照组.

将基于主题模型的错误报告索引词库替换为倒排表索引词库,并与本文基于连续查询的错误报告检索算法相结合,形成方法1;将基于主题模型的错误报告索引词库与Lucene的全文检索算法结合,形成方法2.再将方法1、方法2 与Lucene 方法进行对比实验,计算检索时间与F1-score,以检验各模块在提升检索效率方面的作用.

(3)基于语义扩展连续查询的重复错误报告预测效果分析

由于目前在重复错误报告预测研究领域,仅有Hindle 等 [8]的实证研究得出了研究成果,因此,本文基于文献[8]实验的数据集,构建基于语义扩展连续查询的重复错误报告预测实验,并将实验结果与文献[8]中的结果进行对比.

同时,为了实验的充分性,在上述实验的基础上,选取Firefox 与Mozilla 两个项目作为补充的数据集.在补充数据集上复现文献[8]的实验,将其实验结果与本文方法的实验结果进行对比.

4.3 实验结果与分析

(1)基于主题模型的错误报告索引空间实验结果分析

如图4所示为基于主题模型的错误报告索引词库与倒排表索引词库的词数对比,其中,主题索引词库表示基于主题模型的错误报告索引词库.可以看出,基于主题模型的错误报告索引词库的词数比倒排表索引词库的词数少50%以上.这是由于基于主题模型的错误报告索引词库,对错误报告中的词项进行主题相关性与词项重要性的筛选,得到的主题词远少于倒排表索引词库中的词,较大程度地减小了索引空间.

图4 索引空间对比图

(2)基于连续查询的错误报告检索效率结果分析

如图5所示为Lucene 检索方法与本文方法、方法1、方法2 在检索时间上的对比.其中,Lucene 检索代表Lucene 检索方法;连续查询检索代表本文方法.

检索时间计时起点为输入查询词序列,终点为检索出相关错误报告.索引的构建不纳入检索时间的考量.

从图5可以看出,由于减小了索引空间,并且在检索过程中采用了基于连续查询的错误报告检索算法,在检索当前词时,先检索前项词扩展序列,而不是检索整个错误报告主题索引词库,在检索的过程中减小了检索空间,因此,本文方法的检索时间较Lucene 检索算法缩短了41%–73%.

图5 检索时间对比图

同时,通过方法1 与方法2的比较,可以看出,方法1 与方法2的检索时间相较于Lucene 检索方法都有减小,且方法2的减小幅度更大,这是由于基于主题模型的错误报告索引词库的建立,较大幅度地缩小了错误报告的索引空间,在同等情况下,减少了检索时间.

表2为Lucene 检索方法与本文方法、方法1、方法2 在F1-score 上的对比.F1-score 数值越大说明其检索效率越高.由表2可得,本文方法(连续查询检索方法)相较于Lucene 检索方法,在F1-score 分数上提高了约20%,检索效率更高,这是由于查询词序列扩展补全了查询信息,使得检索的查全率与查准率得到提升.方法2的F1-score 分数最低,因为方法2 去除了查询词序列扩展模块,且使用基于主题模型的错误报告索引词库,索引词库中仅有数量较少的错误报告主题词,因此在进行检索时,其查准率较低,由此导致F1-score 分数低.

表2 F1-score 对比

(3)基于语义扩展连续查询的重复错误报告预测效果实验结果分析

文献[8]的实验通过MAP、MRR、TOP-k、AveP-TOPk、MRR-TOPk、MRR-TOPk-1 综合衡量重复错误报告的预测效果.MAP 代表平均精度,是一种有效衡量信息检索精度的分数,其值越高,代表预测效果越好;MRR 代表重复错误报告排名的倒数平均值,当重复错误报告排名越靠前,其MRR 分数越高;TOPk 代表重复错误报告出现在给定的排名域中的个数,数值越高表示预测效果越好.

但由于MAP、MRR、TOP-k 具有局限性,不能表征查询词序列长短对预测结果的影响,因此,Hindle 等[8]又提出了AveP-TOPk、MRR-TOPk、MRR-TOPk-1 指标作为补充,其数值越高表示预测效果越好.其中,AveP-TOPk 是MAP 与TOP-k的结合,AveP-TOPk 数值越高,代表在同样的预测结果情况下,使用的查询词数越少;MRR-TOPk 代表重复错误报告第一次出现在TOPk 排名中时,其MRR 分数,数值越大,表明预测效果越好;MRR-TOPk-1 则表示重复错误报告第一次出现在TOPk 排名中时,平均所需要的查询词数,数值越小表明预测效果越好.

基于文献[8]实验数据集的预测效果对比如表3.AC 代表文献[8]方法,SECQ (semantically extended continuous query)代表本文方法.由表3可以看出,本文方法在6 个评价指标上均优于文献[8]方法,其中,AveP-TOP5 提升了20%以上.表4所示为基于补充数据集,复现文献[8]方法实验,得到的实验结果与本文实验结果的对比.

表3 基于文献[8]实验数据集的预测效果对比

通过表4的对比可以看出,在改变数据集的情况下,本文方法仍在6 个评价指标上均优于文献[8]方法,最高提升33.6%.

表4 基于补充数据集的预测效果对比

由此可见,与传统方法相比,本文方法减小了索引空间,同时,在检索效率与预测效果上均有提升.

5 结束语

本文提出了一种基于语义扩展连续查询的重复错误报告预测方法.通过挖掘错误报告主题,以错误报告主题为媒介,确定错误报告的主题词,构建错误报告主题索引词库,建立错误报告主题词与错误报告的关系,减小了错误报告索引空间;在此基础上,对查询词序列进行语义扩展,提出基于连续查询的错误报告检索算法,缩小检索空间,在提高了预测准确率的同时,也提升了检索的效率.实验表明,本文方法在索引空间与检索时间上较传统方法有较大减小,同时与文献[8]实验结果的对比表明,在预测效果上,本文方法更好,提升了33.6%.