云環(huán)境下軟件錯(cuò)誤報(bào)告自動(dòng)分類(lèi)算法改進(jìn)

黃偉 林劼 江育娥

摘要：用戶(hù)提交的軟件錯(cuò)誤報(bào)告隨意性大、主觀性強(qiáng)且內(nèi)容少導(dǎo)致自動(dòng)分類(lèi)正確率不高，需要花費(fèi)大量人工干預(yù)時(shí)間。隨著互聯(lián)網(wǎng)的快速發(fā)展用戶(hù)提交的錯(cuò)誤報(bào)告數(shù)量也不斷增加，如何在海量數(shù)據(jù)下提高其自動(dòng)分類(lèi)的精確度越來(lái)越受到關(guān)注。通過(guò)改進(jìn)詞頻逆文檔頻率（TFIDF），考慮到詞條在類(lèi)間和類(lèi)內(nèi)出現(xiàn)情況對(duì)文本分類(lèi)的影響，提出一種基于軟件錯(cuò)誤報(bào)告數(shù)據(jù)集的改進(jìn)多項(xiàng)式樸素貝葉斯算法，同時(shí)在Hadoop平臺(tái)下使用MapReduce計(jì)算模型實(shí)現(xiàn)該算法的分布式版本。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的多項(xiàng)式樸素貝葉斯算法將F1值提高到71%，比原算法提高了27個(gè)百分點(diǎn)，同時(shí)在海量數(shù)據(jù)下可以通過(guò)拓展節(jié)點(diǎn)的方式縮短運(yùn)行時(shí)間，有較好的執(zhí)行效率。

關(guān)鍵詞：多項(xiàng)式樸素貝葉斯；錯(cuò)誤報(bào)告；文本自動(dòng)分類(lèi)；詞頻逆文檔頻率；云計(jì)算

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A

Abstract：Usersubmitted bug reports are arbitrary and subjective. The accuracy of automatic classification of bug reports is not ideal. Hence it requires many human labors to intervention. With the bug reports database growing bigger and bigger， the problem of improving the accuracy of automatic classification of these reports is becoming urgent. A TFIDF （Term FrequencyInverse Document Freqency） based Naive Bayes （NB） algorithm was proposed. It not only considered the relationship of a term in different classes but also the relationship of a term inside a class. It was also implemented in distributed parallel environment of MapReduce model in Hadoop platform. The experimental results show that the proposed Naive Bayes algorithm improves the performance of F1 measument to 71%， which is 27 percentage points higher than the stateoftheart method. And it is able to deal with massive amounts of data in distributed way by addding computational node to offer shorter running time and has better effective performance.

Key words：Naive Bayes of polynomials； bug report； text automatic classification； Term FrequencyInverse Document Frequency （TFIDF）； cloud computing

0 引言

隨著大數(shù)據(jù)時(shí)代的到來(lái)，海量數(shù)據(jù)的處理速度越來(lái)越受到重視，傳統(tǒng)的單機(jī)處理已經(jīng)呈現(xiàn)出其弊端，如何在大量的數(shù)據(jù)情況下提高處理速度受到廣泛的關(guān)注。Hadoop作為一個(gè)分布式的框架，其在超大數(shù)據(jù)集下的表現(xiàn)令人滿(mǎn)意。開(kāi)源軟件的錯(cuò)誤報(bào)告隨著版本的更新收到用戶(hù)越來(lái)越多的反饋，如何在短時(shí)間內(nèi)將用戶(hù)的反饋分門(mén)別類(lèi)更快地進(jìn)行修復(fù)已經(jīng)成為各企業(yè)提升自我軟件競(jìng)爭(zhēng)力的重點(diǎn)。用戶(hù)提交軟件錯(cuò)誤報(bào)告有著很大的隨意性，即使事先給出類(lèi)別也無(wú)法保證用戶(hù)能夠正確地選對(duì)，因此將錯(cuò)誤報(bào)告進(jìn)行自動(dòng)分類(lèi)能夠節(jié)省時(shí)間并提高效率。目前對(duì)于軟件錯(cuò)誤報(bào)告的分析主要集中在錯(cuò)誤報(bào)告的質(zhì)量、錯(cuò)誤報(bào)告的最優(yōu)化、錯(cuò)誤報(bào)告的分類(lèi)和錯(cuò)誤報(bào)告的修復(fù)，機(jī)器學(xué)習(xí)算法和信息檢索技術(shù)已經(jīng)被廣泛應(yīng)用到其中[1]； 然而對(duì)于軟件錯(cuò)誤報(bào)告自動(dòng)分類(lèi)改進(jìn)方法的結(jié)果卻不理想[2]。Shokripour等[3]提出的基于時(shí)間算法的精確度可以提高到45.52%。Shokripour等[4]提出僅采用名詞和時(shí)間元數(shù)據(jù)的詞條權(quán)重的方法可以將準(zhǔn)確度提高到49%。Alenezi等[5]通過(guò)詞條選擇的方法將F1值提高到38.2%。Shokripour等[6]提出基于位置的錯(cuò)誤報(bào)告加權(quán)方法使得準(zhǔn)確度提高到50%左右；黃小亮等[7]提出的潛在Dirichlet分配（Latent Dirichlet Allocation， LDA）的軟件缺陷分派方法，將準(zhǔn)確度提高到37.54%。業(yè)界對(duì)此也進(jìn)行大量的研究，比如基于馬爾可夫鏈的方法[8]、基于詞匯知識(shí)模型的方法 [9]和Shokripour等[10]提出的信息提取的方法。以上提到的這些研究，都是為了提高軟件錯(cuò)誤報(bào)告自動(dòng)分類(lèi)的精確度。

文本自動(dòng)分類(lèi)的算法多種多樣，樸素貝葉斯算法以其簡(jiǎn)單高效的特點(diǎn)受到青睞，在其基礎(chǔ)上的改進(jìn)算法也層出不窮，比如，李文進(jìn)等[11]提出的基于改進(jìn)樸素貝葉斯的區(qū)間不確定性數(shù)據(jù)分類(lèi)方法，翟軍昌等[12]提出的基于增益比對(duì)特征詞的樸素貝葉斯改進(jìn)算法，羅凌等[13]提出的基于樹(shù)增強(qiáng)型貝葉斯網(wǎng)絡(luò)（Tree Augmented Bayes Network，TAN）的改進(jìn)等。在大數(shù)據(jù)環(huán)境下實(shí)現(xiàn)文本自動(dòng)分類(lèi)算法更加有意義，比如張紅蕊等[14]提出的基于關(guān)聯(lián)規(guī)則和置信度的樸素貝葉斯算法，衛(wèi)潔等[15]在云環(huán)境下實(shí)現(xiàn)別人改進(jìn)的樸素貝葉斯算法。盡管如此，對(duì)于軟件錯(cuò)誤報(bào)告的自動(dòng)分類(lèi)研究結(jié)果仍然不理想，同時(shí)在大數(shù)據(jù)環(huán)境下對(duì)其的關(guān)注也較少。本文在Hadoop框架下實(shí)現(xiàn)多項(xiàng)式樸素貝葉斯算法并對(duì)其進(jìn)行改進(jìn)，經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證了其在時(shí)間和精度上均有較好表現(xiàn)。

2 云環(huán)境下的改進(jìn)算法實(shí)現(xiàn)

在Hadoop平臺(tái)下使用MapReduce計(jì)算模型來(lái)實(shí)現(xiàn)改進(jìn)的多項(xiàng)式樸素貝葉斯算法。MapReduce模型主要采用對(duì)數(shù)據(jù)“分而治之”的方法，定義Map和Reduce兩個(gè)抽象的編程接口，用鍵值對(duì)（key，value）來(lái)表示數(shù)據(jù)。首先是各個(gè)Map節(jié)點(diǎn)對(duì)數(shù)據(jù)進(jìn)行并行計(jì)算，將中間結(jié)果輸出到各個(gè)Reduce節(jié)點(diǎn)，最后匯總所有Reduce節(jié)點(diǎn)的結(jié)果，以鍵值對(duì)的形式輸出結(jié)果。改進(jìn)算法的實(shí)現(xiàn)主要分訓(xùn)練和測(cè)試兩個(gè)階段，訓(xùn)練階段采用四個(gè)MapReduce，測(cè)試階段采用一個(gè)MapReduce。

2.1 訓(xùn)練階段

訓(xùn)練階段的輸入為一個(gè)預(yù)處理過(guò)的文件，每行均代表一個(gè)文件，第一個(gè)詞條為文檔所屬類(lèi)別名稱(chēng)，之后為特征屬性，以空格為間隔符。例如第1行為c、w1、w2w3、w4，c表示所屬類(lèi)別，w表示分詞后的詞條。如表1所示，Map函數(shù)中主要進(jìn)行詞頻的計(jì)算以及其他基本數(shù)據(jù)的計(jì)算，在Reduce中進(jìn)行合并統(tǒng)計(jì)，并將結(jié)果輸出到相應(yīng)文件中。在Reduce輸出過(guò)程中，利用setOutputFormat方法設(shè)置輸出格式，將每個(gè)key得到的結(jié)果輸出到單獨(dú)文件中去，以供后續(xù)計(jì)算。

經(jīng)過(guò)4個(gè)MapReduce之后，訓(xùn)練階段完成。在測(cè)試階段即可進(jìn)行預(yù)測(cè)新文本所屬的類(lèi)別。

2.2 測(cè)試階段

測(cè)試階段的輸入文件為測(cè)試文件，文件的格式和訓(xùn)練階段的格式一致。先對(duì)每一行所代表的文檔進(jìn)行詞頻統(tǒng)計(jì)。對(duì)于每一個(gè)類(lèi)cj，計(jì)算每個(gè)詞條wt的tf*lg P（wt|cj）值并進(jìn)行累加，其所屬類(lèi)別為 c=arg maxcj∈C P（cj|di），在Map階段將判斷結(jié)果和原始類(lèi)別進(jìn)行比較，相符不相符作出相應(yīng)輸出，Reduce階段對(duì)Map階段的結(jié)果進(jìn)行累加。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

本文的實(shí)驗(yàn)數(shù)據(jù)來(lái)自開(kāi)源軟件Eclipse 官網(wǎng)中2001—2013年用戶(hù)提交的部分錯(cuò)誤報(bào)告，涉及到Tools、 Modeling、 Technology、 SOA等11 個(gè)類(lèi)別，總共包含大概50000份錯(cuò)誤報(bào)告。由于每個(gè)類(lèi)別的錯(cuò)誤報(bào)告份數(shù)不同，考慮到樣本的均勻性，在抽取樣本時(shí)保證每個(gè)類(lèi)別的樣本份數(shù)一致，約為3000份每類(lèi)別，處理過(guò)程中遇到個(gè)別類(lèi)別總數(shù)不足3000份的，采取放回繼續(xù)抽取的隨機(jī)方式獲得。首先處理下載的Eclipse 錯(cuò)誤報(bào)告數(shù)據(jù)，留下錯(cuò)誤報(bào)告的類(lèi)別和錯(cuò)誤報(bào)告的內(nèi)容描述2個(gè)屬性。利用R語(yǔ)言的TM（TextMining）包對(duì)錯(cuò)誤報(bào)告的內(nèi)容描述進(jìn)行預(yù)處理。將其錯(cuò)誤報(bào)告的內(nèi)容描述小寫(xiě)化、去空格、去數(shù)字、去停用詞、詞干化、進(jìn)行分詞。采用10×10交叉驗(yàn)證方法。每一次打散數(shù)據(jù)，任意選擇70%數(shù)據(jù)為訓(xùn)練數(shù)據(jù)，余下的30%為驗(yàn)證數(shù)據(jù)。訓(xùn)練數(shù)據(jù)（70%）被用來(lái)建模，余下的數(shù)據(jù)（30%） 被用來(lái)匹配此模型以驗(yàn)證模型的有效性，記錄下相應(yīng)的性能指標(biāo)（精確度、召回率和F1值）。此訓(xùn)練和驗(yàn)證過(guò)程重復(fù)進(jìn)行10 次，對(duì)性能指標(biāo)取平均值作為每次的計(jì)算結(jié)果。本文采用分布式集群，每臺(tái)電腦配置一致，均為32位計(jì)算機(jī)，centos6.4系統(tǒng)，2GB內(nèi)存，Hadoop版本為2.2.0，Java版本1.7。搭建的集群為1個(gè)NameNode，6個(gè)DataNode。在運(yùn)行過(guò)程中，所有參數(shù)均為默認(rèn)值，暫時(shí)沒(méi)有進(jìn)行優(yōu)化。

3.2 評(píng)價(jià)指標(biāo)

實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)主要有精確率P（precision）、召回率R（recall）和F1值，如表5所示，A表示屬于某類(lèi)別的文本且預(yù)測(cè)結(jié)果也是屬于某類(lèi)別的，D表示不屬于某類(lèi)別的文本預(yù)測(cè)結(jié)果為屬于某類(lèi)別，C表示屬于某類(lèi)別的文本預(yù)測(cè)結(jié)果顯示不屬于某類(lèi)別。依據(jù)表5，幾個(gè)評(píng)估指標(biāo)的計(jì)算公式如式（8）～（10）。F1值綜合了精確率和召回率，能總體地反映出整體的指標(biāo)，因而本文主要采用F1值來(lái)評(píng)估算法在不同類(lèi)別上的分類(lèi)性能。

3.3 實(shí)驗(yàn)結(jié)果與分析

采用交叉驗(yàn)證方法，將結(jié)果取平均值得到F1結(jié)果對(duì)比表，第2列為采用原始TFIDF算法的多項(xiàng)式樸素貝葉斯方法[15]得到的結(jié)果，第3列為本文改進(jìn)TFIDF算法后的多項(xiàng)式樸素貝葉斯算法得到的結(jié)果，因?yàn)轭?lèi)別較多，所以?xún)H列出前幾個(gè)類(lèi)別，最后一行為所有類(lèi)別的平均值。從數(shù)據(jù)可以看出，改進(jìn)算法在各個(gè)小類(lèi)別上的F1值均有相當(dāng)幅度的提高，而且在所有類(lèi)別的平均值上，改進(jìn)的算法比原算法提高了27%，提高了原來(lái)結(jié)果的61%。而在精確度上（未在表中標(biāo)出），由原始算法的44%提高到改進(jìn)算法的69%。由此可見(jiàn)改進(jìn)的算法使得軟件錯(cuò)誤報(bào)告的自動(dòng)分類(lèi)結(jié)果得到了改善，同時(shí)使得海量數(shù)據(jù)在單機(jī)情況下的內(nèi)存不足瓶頸得以解決。由于業(yè)界并沒(méi)有將改進(jìn)的算法應(yīng)用于軟件錯(cuò)誤數(shù)據(jù)集上，基于數(shù)據(jù)集的特殊性，因而無(wú)法直觀比較結(jié)果，但是可以對(duì)比最近業(yè)界在eclipse軟件錯(cuò)誤報(bào)告數(shù)據(jù)集上做的實(shí)驗(yàn)，最好的結(jié)果也是將精確度提高到50%左右[6]，可見(jiàn)本文的改進(jìn)算法對(duì)比業(yè)界相關(guān)研究的結(jié)果具有一定的優(yōu)勢(shì)。

同時(shí)本文還對(duì)并行算法的性能進(jìn)行測(cè)試，分別在兩個(gè)節(jié)點(diǎn)的集群和6個(gè)節(jié)點(diǎn)的集群上對(duì)2GB，4GB，…，10GB數(shù)據(jù)集進(jìn)行測(cè)試，分別計(jì)算其運(yùn)行時(shí)間。而在單機(jī)運(yùn)行時(shí)，一旦數(shù)據(jù)量足夠大，則會(huì)出現(xiàn)內(nèi)存不足的情況而導(dǎo)致程序無(wú)法繼續(xù)執(zhí)行，因而并行計(jì)算解決了大數(shù)據(jù)下單機(jī)運(yùn)行的內(nèi)存瓶頸。從圖1中可以看出，隨著數(shù)據(jù)集大小的增加，其運(yùn)行時(shí)間趨于緩和，可見(jiàn)數(shù)據(jù)量越大越適合并行分布式改進(jìn)的算法。同時(shí)隨著節(jié)點(diǎn)的增加，運(yùn)行時(shí)間縮短，可見(jiàn)可以通過(guò)增加節(jié)點(diǎn)進(jìn)一步的縮短運(yùn)行時(shí)間。

4 結(jié)語(yǔ)

本文對(duì)多項(xiàng)式樸素貝葉斯算法進(jìn)行了改進(jìn)，在軟件錯(cuò)誤報(bào)告集上進(jìn)行自動(dòng)分類(lèi)，結(jié)果表明其在F1值指標(biāo)上相對(duì)原有算法有了較大的提高。同時(shí)在大數(shù)據(jù)環(huán)境下實(shí)現(xiàn)改進(jìn)的算法，表明在海量數(shù)據(jù)前其運(yùn)行時(shí)間縮短同時(shí)效率提高，使得原來(lái)在單機(jī)上的串行計(jì)算得以并行實(shí)現(xiàn)。改進(jìn)的算法除了適合于開(kāi)源軟件錯(cuò)誤報(bào)告的自動(dòng)分類(lèi)，也適合于大型企業(yè)收集客戶(hù)信息，通信運(yùn)行商對(duì)客戶(hù)投訴和建議的自動(dòng)分類(lèi)以及其他需要人工提交文本描述、隨意性比較強(qiáng)的數(shù)據(jù)的自動(dòng)分類(lèi)。

參考文獻(xiàn)：

[1]ZHANG J， WANG X Y， HAO D， et al. A survey on bugreport analysis[J]. Science China Information Sciences， 2015， 58（2）：1-24.

[2]STRATE J D， LAPLANTE P A. A literature review of research in software defect reporting[J]. IEEE Transactions on Reliability，2013， 62（2）： 444-454.

[3]SHOKRIPOUR R， ANVIK J， KASIRUN Z M， et al. A timebased approach to automatic bug report assignment[J]. Journal of Systems & Software， 2015，102：109-122.

[4]SHOKRIPOUR R， ANVIK J， KASIRUN Z M， et al. Improving automatic bug assignment using timemetadata in termweighting[J]. IET Software， 2014， 8（6）：269-278.

[5]ALENEZI M， MAGEL K， BANITAAN S. Efficient bug triaging using text mining[J]. Journal of Software， 2013， 8（9）：2185-2190.

[6]SHOKRIPOUR R， ANVIK J， KASIRUN Z M， et al. Why so complicated？ Simple term filtering and weighting for locationbased bug report assignment recommendation[C]// Proceedings of the 10th International Workshop on Mining Software Repositories. Piscataway， NJ： IEEE， 2013： 2-11.

[7]黃小亮， 郁抒思， 關(guān)佶紅. 基于 LDA 主題模型的軟件缺陷分派方法[J]. 計(jì)算機(jī)工程， 2011， 37（21）： 46-48.（HUANG X L，YU S S，GUAN J H. Software bug triage method based on LDA topic model[J]. Computer Engineering， 2011， 37（21）： 46-48）.

[8]JEONG G， KIM S， ZIMMERMANN T. Improving bug triage with bug tossing graphs[C]// Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. New York： ACM， 2009： 111-120.

[9]MATTER D， KUHN A， NIERSTRASZ O. Assigning bug reports using a vocabularybased expertise model of developers[C]// Proceedings of the 6th IEEE International Working Conference on Mining Software Repositories. Piscataway， NJ： IEEE， 2009： 131-140.

[10]SHOKRIPOUR R， KASIRUN Z M， ZAMANI S， et al. Automatic bug assignment using information extraction methods[C]// Proceedings of the 2012 International Conference on Computer Science Applications and Technologies. Piscataway， NJ： IEEE， 2012： 144-149.

[11]李文進(jìn)， 熊小峰， 毛伊敏. 基于改進(jìn)樸素貝葉斯的區(qū)間不確定性數(shù)據(jù)分類(lèi)方法[J]. 計(jì)算機(jī)應(yīng)用， 2014， 34（11）：3268-3272.（LI W J，XIONG X F，MAO Y M. Classification method for interval uncertain data based on improved naive Bayes[J]. Journal of Computer Applications， 2014， 34（11）：3268-3272.）

[12]翟軍昌， 秦玉平， 車(chē)偉偉. 垃圾郵件過(guò)濾中信息增益的改進(jìn)研究[J]. 計(jì)算機(jī)科學(xué)， 2014， 41（6）：214-216.（ZHAI J C，QIN Y P，CHE W W. Improvement of information gain in spam filtering[J]. Computer Science， 2014， 41（6）：214-216.）

[13]羅凌， 楊有， 馬燕. 基于TAN貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)風(fēng)格檢測(cè)研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2015，51（6）：48-54.（LUO L， YANG Y， MA Y. Research on detecting learning style based on TAN Bayesian network[J]. Computer Engineering and Applications， 2015，51（6）：48-54.）

[14]張紅蕊， 張永， 于靜雯. 云計(jì)算環(huán)境下基于樸素貝葉斯的數(shù)據(jù)分類(lèi)[J]. 計(jì)算機(jī)應(yīng)用與軟件， 2015， 32（3）：27-30.（ZHANG H R，ZHANG Y，YU J W. Data classification based on naive Bayes in cloud computing environment[J]. Computer Applications and Software， 2015， 32（3）：27-30.）

[15]衛(wèi)潔， 石洪波， 冀素琴. 基于Hadoop的分布式樸素貝葉斯文本分類(lèi)[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2012， 21（2）：210-213.（WEI J，SHI H B，JI S Q. Distributed naive Bayes text classification using Hadoop[J]. Computer Systems and Applications， 2012， 21（2）：210-213.）

[16]MCCALLUM A， NIGAM K. A comparison of event models for naive Bayes text classification[C]// Proceedings of the 25th International Symposium on Computer and Information Sciences. Berlin： Springer， 1998：41-48.

[17]JIANG S， SAYYADSHIRABAD J， MATWIN S. Large scale text classification using semisupervised multinomial naive Bayes[C]// Proceedings of the 28th International Conference on Machine Learning. Bellevue， WA： ICML， 2011： 97-104.

[18]SALTON G， BUCKLEY C. Termweighting approaches in automatic text retrieval[J]. Information Processing & Management， 1988， 24（5）： 513-523.