黃偉 林劼 江育娥

摘要：用戶提交的軟件錯(cuò)誤報(bào)告隨意性大、主觀性強(qiáng)且內(nèi)容少導(dǎo)致自動(dòng)分類正確率不高，需要花費(fèi)大量人工干預(yù)時(shí)間。隨著互聯(lián)網(wǎng)的快速發(fā)展用戶提交的錯(cuò)誤報(bào)告數(shù)量也不斷增加，如何在海量數(shù)據(jù)下提高其自動(dòng)分類的精確度越來越受到關(guān)注。通過改進(jìn)詞頻逆文檔頻率（TFIDF），考慮到詞條在類間和類內(nèi)出現(xiàn)情況對(duì)文本分類的影響，提出一種基于軟件錯(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ù)下可以通過拓展節(jié)點(diǎn)的方式縮短運(yùn)行時(shí)間，有較好的執(zhí)行效率。

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

中圖分類號(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í)代的到來，海量數(shù)據(jù)的處理速度越來越受到重視，傳統(tǒng)的單機(jī)處理已經(jīng)呈現(xiàn)出其弊端，如何在大量的數(shù)據(jù)情況下提高處理速度受到廣泛的關(guān)注。Hadoop作為一個(gè)分布式的框架，其在超大數(shù)據(jù)集下的表現(xiàn)令人滿意。開源軟件的錯(cuò)誤報(bào)告隨著版本的更新收到用戶越來越多的反饋，如何在短時(shí)間內(nèi)將用戶的反饋分門別類更快地進(jìn)行修復(fù)已經(jīng)成為各企業(yè)提升自我軟件競(jìng)爭(zhēng)力的重點(diǎn)。用戶提交軟件錯(cuò)誤報(bào)告有著很大的隨意性，即使事先給出類別也無法保證用戶能夠正確地選對(duì)，因此將錯(cuò)誤報(bào)告進(jìn)行自動(dòng)分類能夠節(jié)省時(shí)間并提高效率。目前對(duì)于軟件錯(cuò)誤報(bào)告的分析主要集中在錯(cuò)誤報(bào)告的質(zhì)量、錯(cuò)誤報(bào)告的最優(yōu)化、錯(cuò)誤報(bào)告的分類和錯(cuò)誤報(bào)告的修復(fù)，機(jī)器學(xué)習(xí)算法和信息檢索技術(shù)已經(jīng)被廣泛應(yīng)用到其中[1]； 然而對(duì)于軟件錯(cuò)誤報(bào)告自動(dòng)分類改進(jìn)方法的結(jié)果卻不理想[2]。Shokripour等[3]提出的基于時(shí)間算法的精確度可以提高到45.52%。Shokripour等[4]提出僅采用名詞和時(shí)間元數(shù)據(jù)的詞條權(quán)重的方法可以將準(zhǔn)確度提高到49%。Alenezi等[5]通過詞條選擇的方法將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)分類的精確度。

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

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

在Hadoop平臺(tái)下使用MapReduce計(jì)算模型來實(shí)現(xiàn)改進(jìn)的多項(xiàng)式樸素貝葉斯算法。MapReduce模型主要采用對(duì)數(shù)據(jù)“分而治之”的方法，定義Map和Reduce兩個(gè)抽象的編程接口，用鍵值對(duì)（key，value）來表示數(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ù)處理過的文件，每行均代表一個(gè)文件，第一個(gè)詞條為文檔所屬類別名稱，之后為特征屬性，以空格為間隔符。例如第1行為c、w1、w2w3、w4，c表示所屬類別，w表示分詞后的詞條。如表1所示，Map函數(shù)中主要進(jìn)行詞頻的計(jì)算以及其他基本數(shù)據(jù)的計(jì)算，在Reduce中進(jìn)行合并統(tǒng)計(jì)，并將結(jié)果輸出到相應(yīng)文件中。在Reduce輸出過程中，利用setOutputFormat方法設(shè)置輸出格式，將每個(gè)key得到的結(jié)果輸出到單獨(dú)文件中去，以供后續(xù)計(jì)算。

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

2.2 測(cè)試階段

測(cè)試階段的輸入文件為測(cè)試文件，文件的格式和訓(xùn)練階段的格式一致。先對(duì)每一行所代表的文檔進(jìn)行詞頻統(tǒng)計(jì)。對(duì)于每一個(gè)類cj，計(jì)算每個(gè)詞條wt的tf*lg P（wt|cj）值并進(jìn)行累加，其所屬類別為 c=arg maxcj∈C P（cj|di），在Map階段將判斷結(jié)果和原始類別進(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ù)來自開源軟件Eclipse 官網(wǎng)中2001—2013年用戶提交的部分錯(cuò)誤報(bào)告，涉及到Tools、 Modeling、 Technology、 SOA等11 個(gè)類別，總共包含大概50000份錯(cuò)誤報(bào)告。由于每個(gè)類別的錯(cuò)誤報(bào)告份數(shù)不同，考慮到樣本的均勻性，在抽取樣本時(shí)保證每個(gè)類別的樣本份數(shù)一致，約為3000份每類別，處理過程中遇到個(gè)別類別總數(shù)不足3000份的，采取放回繼續(xù)抽取的隨機(jī)方式獲得。首先處理下載的Eclipse 錯(cuò)誤報(bào)告數(shù)據(jù)，留下錯(cuò)誤報(bào)告的類別和錯(cuò)誤報(bào)告的內(nèi)容描述2個(gè)屬性。利用R語言的TM（TextMining）包對(duì)錯(cuò)誤報(bào)告的內(nèi)容描述進(jìn)行預(yù)處理。將其錯(cuò)誤報(bào)告的內(nèi)容描述小寫化、去空格、去數(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%）被用來建模，余下的數(shù)據(jù)（30%） 被用來匹配此模型以驗(yàn)證模型的有效性，記錄下相應(yīng)的性能指標(biāo)（精確度、召回率和F1值）。此訓(xùn)練和驗(yàn)證過程重復(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)行過程中，所有參數(shù)均為默認(rèn)值，暫時(shí)沒有進(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表示屬于某類別的文本且預(yù)測(cè)結(jié)果也是屬于某類別的，D表示不屬于某類別的文本預(yù)測(cè)結(jié)果為屬于某類別，C表示屬于某類別的文本預(yù)測(cè)結(jié)果顯示不屬于某類別。依據(jù)表5，幾個(gè)評(píng)估指標(biāo)的計(jì)算公式如式（8）～（10）。F1值綜合了精確率和召回率，能總體地反映出整體的指標(biāo)，因而本文主要采用F1值來評(píng)估算法在不同類別上的分類性能。

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)轭悇e較多，所以僅列出前幾個(gè)類別，最后一行為所有類別的平均值。從數(shù)據(jù)可以看出，改進(jìn)算法在各個(gè)小類別上的F1值均有相當(dāng)幅度的提高，而且在所有類別的平均值上，改進(jìn)的算法比原算法提高了27%，提高了原來結(jié)果的61%。而在精確度上（未在表中標(biāo)出），由原始算法的44%提高到改進(jìn)算法的69%。由此可見改進(jìn)的算法使得軟件錯(cuò)誤報(bào)告的自動(dòng)分類結(jié)果得到了改善，同時(shí)使得海量數(shù)據(jù)在單機(jī)情況下的內(nèi)存不足瓶頸得以解決。由于業(yè)界并沒有將改進(jìn)的算法應(yīng)用于軟件錯(cuò)誤數(shù)據(jù)集上，基于數(shù)據(jù)集的特殊性，因而無法直觀比較結(jié)果，但是可以對(duì)比最近業(yè)界在eclipse軟件錯(cuò)誤報(bào)告數(shù)據(jù)集上做的實(shí)驗(yàn)，最好的結(jié)果也是將精確度提高到50%左右[6]，可見本文的改進(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)致程序無法繼續(xù)執(zhí)行，因而并行計(jì)算解決了大數(shù)據(jù)下單機(jī)運(yùn)行的內(nèi)存瓶頸。從圖1中可以看出，隨著數(shù)據(jù)集大小的增加，其運(yùn)行時(shí)間趨于緩和，可見數(shù)據(jù)量越大越適合并行分布式改進(jìn)的算法。同時(shí)隨著節(jié)點(diǎn)的增加，運(yùn)行時(shí)間縮短，可見可以通過增加節(jié)點(diǎn)進(jìn)一步的縮短運(yùn)行時(shí)間。

4 結(jié)語

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

參考文獻(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ù)分類方法[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]翟軍昌， 秦玉平， 車偉偉. 垃圾郵件過濾中信息增益的改進(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ù)分類[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的分布式樸素貝葉斯文本分類[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.