通過代碼模式改進基于IR的需求和代碼之間追蹤生成方法

杜天保,沈國華,2,黃志球,2,王 飛,吳德香

1(南京航空航天大學 計算機科學與技術(shù)學院,南京 211106)2(軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心,南京 210093)

1 引 言

軟件可追蹤性(software traceability)是指在軟件開發(fā)過程中建立和維護軟件制品(例如,需求文檔,源代碼,測試用例等)之間的關(guān)聯(lián)關(guān)系,并利用這些關(guān)系對軟件項目進行一系列分析的能力[1],追蹤信息支持變更影響分析、依賴影響分析、系統(tǒng)驗證以及安全認證等活動.手動創(chuàng)建和維護制品間的追蹤關(guān)系存在成本高、耗時長、易出錯的問題.因此,如何利用自動化分析來實現(xiàn)軟件可追蹤性的生成與維護就成了領(lǐng)域內(nèi)研究的熱點與重點.

信息檢索(Information Retrieval,IR)已被廣泛應(yīng)用于追蹤關(guān)系的自動生成,其基本思想是計算制品間(例如需求和代碼)的文本相似度,并最終為用戶提供一個按照文本相似度從高到低排序的候選追蹤鏈(trace link)列表.典型的IR追蹤生成方法包括向量空間模型(VSM)[2],潛在語義索引(LSI)[3]以及概率Jensen和Shannon模型(JS)[4].

然而,需求本身的非結(jié)構(gòu)化和“詞匯表失配”問題極大的影響了IR追蹤生成方法的準確性[5].為了解決這一問題,研究人員已經(jīng)在多個不同方面改進了IR追蹤生成方法,例如用戶的反饋[6],主題模型[7]等.此外,還有一部分工作關(guān)注引入代碼結(jié)構(gòu)來改進IR追蹤生成方法.這種利用源代碼的結(jié)構(gòu)信息的改進方法,被證明是非常有用的[6,8-11].

基于這個思路,本文提出IR技術(shù)和代碼模式相結(jié)合的新方法.我們的方法分三步進行:1)利用IR追蹤生成方法生成每個需求的候選列表;2)對于每個需求,選擇其候選列表中排名靠前的類(本文選擇候選列表中前3%的類)加入新候選列表(初始為空),根據(jù)已加入新的候選列表中的類以及類之間的依賴關(guān)系分析出剩余類(沒有加入新候選列表的類)的代碼模式,再由代碼模式獲得剩余類和給定需求之間的預(yù)期值;3)通過預(yù)期值,對剩余類重排序后加入新候選列表.最終,新候選列表實現(xiàn)對原候選列表的重排序.

2 相關(guān)工作

為了應(yīng)對IR追蹤生成方法的準確性低這一問題,當前的主流思想是從文本預(yù)處理[12]、IR模型[13]等詞法分析的角度出發(fā)來優(yōu)化IR追蹤生成方法.但是,這些方法需要豐富的需求描述和完善的代碼文檔,這在實際項目中是難以獲得的[14].為了克服IR追蹤生成方法對文本質(zhì)量的過于依賴,目前有一些工作開始結(jié)合代碼結(jié)構(gòu)改進IR追蹤生成方法.Scanniello等人[15]引入PageRank算法來計算代碼中每個函數(shù)在代碼結(jié)構(gòu)上的關(guān)聯(lián)重要性(relative importance),這個值隨后會與函數(shù)和給定特征之間的IR相似度相乘,得到的新值作為最終候選列表排序的依據(jù).McMillan等人[16]提出了同時基于代碼中調(diào)用依賴和數(shù)據(jù)依賴的自動化分析方法.Panichella等人[6]提出的方法則將用戶反饋(user feedback)和代碼依賴關(guān)系分析同時引入基于IR的需求到代碼可追蹤性生成.這一方法雖然能夠提升精度,但引入了額外的人力投入,降低了工具的自動化程度.針對需求到代碼可追蹤性的自動化驗證,CGhabi和Egyed[17]利用代碼元素之間的調(diào)用依賴提出了若干代碼模式,對于一組滿足了某個代碼模式的代碼元素,它們應(yīng)該具有類似的追蹤鏈,如果與其在已知的追蹤鏈集合中的追蹤鏈不一致,則認為這條追蹤鏈是有問題的.代碼模式在追蹤的自動驗證領(lǐng)域取得了良好的效果,我們把[18]提出的代碼模式的思想應(yīng)用到追蹤的自動生成中,實驗表明,引入代碼模式的IR追蹤生成方法明顯優(yōu)于純IR追蹤生成方法.

3 代碼模式和算法

本節(jié)主要討論代碼模式的原理、分類以及預(yù)期值求解算法.

3.1 類依賴和需求域

正如相關(guān)工作中提到的,我們使用代碼元素之間的依賴關(guān)系來提高追蹤關(guān)系生成的準確性.我們將軟件系統(tǒng)表示為有向圖G=(C,E).C表示系統(tǒng)中的類的集合,E表示邊的集合(即,C中元素的有序?qū)?.每條邊(ci,cj)∈E表示兩個類ci和cj之間存在依賴關(guān)系.軟件Understand[注]https://scitools.com/features/可以分析類之間的依賴關(guān)系.類與類依賴關(guān)系構(gòu)成類依賴圖,圖1描繪了eTour[注]http://www.cs.wm.edu/semeru/tefse2011/Challenge.htm.系統(tǒng)(電子導(dǎo)游系統(tǒng))類依賴圖的摘錄.類依賴圖中節(jié)點表示類,邊上的指示箭頭用于區(qū)分依賴者和被依賴者.例如,類GestionePuntiDiRistoroAgenzia對應(yīng)的節(jié)點指向類IGestionePuntiDiRistoroAgenzia對應(yīng)的節(jié)點.則類GestionePuntiDiRistoroAgenzia是類IGestionePuntiDiRistoroAgenzia的依賴者,而類IGestionePuntiDiRistoroAgenzia是類GestionePuntiDiRistoroAgenzia的被依賴者.研究發(fā)現(xiàn)給定需求通常在代碼的某塊聯(lián)通域內(nèi)被實現(xiàn),而不是隨機分布在代碼各處[18].這種代碼聯(lián)通域稱為需求域(requirement region).圖1顯示了一個需求域(灰色區(qū)域)的示例.需求域標識實現(xiàn)eTour系統(tǒng)的需求UC8的所有類(節(jié)點).

圖1 eTour系統(tǒng)的類依賴圖摘錄(灰色部分是UC8的需求域)Fig.1 Excerpt of class depend graph from the eTour system (UC8 Requirement region highlighted in gray)

3.2 代碼模式的基本原理

在類依賴圖中,一個類的鄰接類(存在直接依賴關(guān)系的類)都不追蹤到給定需求,表明這個類具有很高的可能性也不追蹤到給定需求.例如圖1中RicercaStandard遠離UC8的需求域,它的鄰接類都不追蹤到UC8.所以,RicercaStandard具有很高的可能性不追蹤到UC8.相反的,如果一個類的鄰接類都追蹤到給定需求,表明這個類具有很高可能性也追蹤到給定需求.在給定的需求下,由類鄰接的類可以獲得若干代碼模式,代碼模式可以幫我們確定任意一個類和給定需求間的預(yù)期值.預(yù)期值有三種:預(yù)期追蹤到給定需求(trace)、預(yù)期不追蹤到給定需求(no_trace)或者不能確定(uncertain).

接下來,我們將討論類的代碼模式,為了表示方便,我們用“t”來表示類追蹤到給定需求,“n”表示類不追蹤到給定需求.

3.3 類的不同的代碼模式

1)t→any→t和n→any→n模式

t→any→t模式(如圖2上半部分所示)適用于至少有一個依賴者類(any類被依賴者類依賴)和至少一個被依賴者類(any類依賴被依賴者類)的any類,其中依賴者類和被依賴者類都追蹤到相同的給定需求.請注意,any類表示任意一個類.模式n→any→n(如圖2下半部分所示)它適用于至少有一個依賴者類并且至少有一個被依賴者類都不追蹤給定需求的any類.圖1中我們可以在需求UC8上識別出類IGestionePuntiDiRistoroAgenzia是t→any→t模式,因為它被GestionePuntiDiRistoroAgenzia依賴并依賴BeanPuntoDiRistoro,而GestionePuntiDiRistoroAgenzia和BeanPuntoDiRistoro都追蹤到UC8.類似地,我們可以在需求UC8上識別出類DBPuntoDiRistoro是n→any→n模式,因為它的依賴者類GestionePuntiDiRistoroComune和被依賴者類IDBPuntoDiRistoro都不追蹤到UC8.

2)t→t→any,n→n→any,any→t→t和any→n →n模式

t→any→t和n→any→n模式只對既有依賴者又有被依賴者的類有用.但是,有些類不依賴其它的類,在沒有被依賴者的情況下,存在兩種模式:t→t→any模式(如圖3上半部分所示)適用于具有追蹤到給定需求的依賴者,并且該依賴者又具有追蹤到給定需求的依賴者的any類.n→n→any模式(如圖3下半部分所示)適用于具有不追蹤到給定需求的依賴者,并且該依賴者又具有不追蹤到給定需求的依賴者的any類.還有一些類有被依賴者而沒有依賴者,這些類也存在兩種模式:any→ t→t和any→n→n.

圖2 “t→any→t”和“n→any→n”模式Fig.2 “t→any→t” and “n→any→n” patterns

圖3 “t→t→any”和“n→n→any”模式Fig.3 “t→t→any” and “n→n→any” patterns

3)邊界模式

1)2)中提到的模式不適用于全部的類.例如,圖1中類IDBPuntoDiRistoro依賴實現(xiàn)了需求UC8的類BeanPuntoDiRistoro,并被沒有實現(xiàn)UC8的GestionePuntiDiRistoroComune依賴.因此,IDBPuntoDiRistoro的模式是n→any→t,n→any→t不屬于1)2)中提到的模式.我們可以看出IDBPuntoDiRistoro正好處于需求域的邊界上,處于需求域邊界上的類的模式是邊界模式.總共有六種邊界模式:

·有一個依賴者類追蹤到給定需求,而沒有被依賴者類追蹤到給定需求(t→any→n).

·有一個被依賴者類追蹤給定需求,而沒有依賴者類追蹤到給定需求(n→any→t).

·沒有依賴者類追蹤到給定需求,而至少有一個依賴的依賴者類追蹤到給定需求(t→n→any).

·有一個依賴者類追蹤到給定需求,而沒有依賴者的依賴者類追蹤到給定的需求(n→t→any).

·有一個被依賴者類追蹤到給定需求,而沒有被依賴者的被依賴者類追蹤到給定需求(any→t→n).

·沒有被依賴者類追蹤到給定需求,而至少有一個被依賴者的被依賴者類追蹤到給定需求(any→n→t).

3.4 代碼模式分類

我們通過實驗對類在不同的代碼模式下追蹤到給定需求的可能性進行了比較.根據(jù)可能性大小,我們將代碼模式分成了三類:TT模式、NN模式、邊界模式.其中,t→any→t,t→t→any,any→t→t屬于TT模式,n→any→n,n→n→any,any→n→n屬于NN模式,邊界模式已經(jīng)在3.3節(jié)做了介紹.實驗表明,類在TT模式(t→any→t,t→t→any,any→t→t)下追蹤到給定需求的可能性明顯高于在邊界模式(t→any→n,n→any→t,t→n→any,n→t→any,any→t→n,any→n→n)下追蹤的可能性.而在NN(n→any→n,n→n→any,any→n→n)模式下追蹤的可能性遠遠小于在TT模式和邊界模式下追蹤的可能性.

3.5 模式組合:純模式和混合模式

到目前為止,我們已經(jīng)討論了單一的模式.但是在實際中,這些模式經(jīng)常發(fā)生在一起.圖1可以發(fā)現(xiàn)多個模式的發(fā)生在一起的情況.在需求UC8的情況下,由DBPuntoDiRistoro、IDBPuntoDiRistoro(any)和BeanPuntoDiRistoro可知IDBPuntoDiRistoro的模式是t→any→t,由GestionePuntiDiRistoroComune、IDBPuntoDiRistoro(any)和BeanPuntoDiRistoro可知IDBPuntoDiRistoro的模式是n→any→t.IDBPuntoDiRistoro具有兩個不同的模式.如果給定的類(any)匹配多個模式,則適用以下兩種情況之一:

1)純模式(pure patterns):所有模式都是同一種.

2)混合模式(mixed patterns):模式有不同的種類.

對于純模式,我們很容易確定給定類的模式,因為所有的模式都是同一種.但是,對于混合模式我們需要在不同的模式中選一個作為給定類的模式.對于混合模式有如下定義:

·TT模式、邊界模式、NN模式同時出現(xiàn)的時候,TT模式占主導(dǎo)地位,我們忽略邊界模式和NN模式的存在,選擇TT模式作為給定類的模式.

·邊界模式和NN模式同時出現(xiàn)的時候,邊界模式占主導(dǎo)定位,我們忽略NN模式的存在.選擇邊界模式作為給定類的模式.

3.6 內(nèi)部類,葉子類和根類

在類依賴圖中既有入度又有出度的類稱為內(nèi)部類t→any→t,n→any→n,t→any→n,n→any→t中的any類都是內(nèi)部類,只有入度而沒有出度的類稱為葉子類,t→t→any,n→n→any,t→n→any,n→t→any中的any類都是葉子類.只有出度而沒有入度的類稱為根類,any→t→t,any→n→n,any→t→n,any→n→t中的any類都是根類.

3.7 計算預(yù)期值

any類在不同種類的代碼模式下具有不同預(yù)期值:TT模式的any類的預(yù)期值是追蹤到給定需求(trace),NN模式的any類的預(yù)期值是不追蹤到給定需求(no_trace),而邊界模式的any類預(yù)期值不確定(uncertain).算法1描述了計算內(nèi)部類預(yù)期值的算法:該算法使用四個變量:dependerT表示追蹤給定需求R的依賴者數(shù)量;dependerN表示不追蹤到R的依賴者的數(shù)量;dependeeT表示追蹤到R的被依賴者的數(shù)量;dependeeN表示不追蹤到R的被依賴者的數(shù)量.此算法僅針對內(nèi)部類,因為既需要依賴者又需要被依賴者.如果至少有一個依賴者類追蹤到給定需求(dependerT> 0)并且至少有一個被依賴類追蹤到給定需求(dependeeT>0),則給定類的模式是t→any→t∈TT,預(yù)期值是追蹤到給定需求(trace).TT模式和其他模式混合的時候,TT模式占主導(dǎo)地位.TT的主導(dǎo)地位是按照if的順序隱含的(TT模式在其他模式之前檢測).如果至少有一個依賴者類不追蹤到給定需求(dependerN>0)并且至少有一個被依賴類不追蹤到給定需求(dependeeN>0),而且沒有依賴者類和被依賴者類追蹤到給定需求(dependerT+dependeeT=0),則給定類代碼模式是n→any→n∈NN,預(yù)期值是不追蹤到給定需求(no_trace).如果存在依賴者類或者被依賴者類追蹤到給定需求(dependerT+dependeeT≠0),則給定類的代碼模式是邊界模式(邊界模式和NN模式混合,邊界模式占主導(dǎo)地位).剩余的情況是純的邊界模式.邊界模式的預(yù)期值不能確定(uncertain).我們不再介紹計算葉子類和根類代碼模式的算法,因為如果假設(shè)變量dependeeT代表追蹤到給定需求的依賴者的依賴者類的數(shù)量,并且dependeeN代表不追蹤給定需求依賴者的依賴者類的數(shù)量.算法1就變成了計算葉子類代碼模式的算法.同理,算法1也可以變成根類的預(yù)期值求解算法.

4 候選列表的生成和重排序

候選列表生成和重排序主要由三部分組成.第一,利用IR追蹤生成方法在需求和類之間生成候選列表.第二,初始化給定需求的需求域,通過域內(nèi)類(初始需求域內(nèi)的類)和類依賴圖獲取域外類(初始需求域外的類)的代碼模式,再由代碼模式獲取域外類的預(yù)期值.第三,域內(nèi)類直接加入新候選列表,域外類重排序后加入新候選列表.新候選列表是對原候選列表的重排序.整個過程如圖4所示.

4.1 通過IR追蹤生成方法在需求和類之間生成候選列表

我們利用IR追蹤生成方法在需求和類之間生成候選列表,總共包含四個步驟:

·創(chuàng)建文檔庫:對于代碼中的每個類,我們抽取一個包含類名、函數(shù)名、注釋的文檔.對于每條需求,我們抽取一個包含題目和內(nèi)容的文檔(對于有結(jié)構(gòu)的需求用例我們抽取其前置條件、主要流程、以及分支流程,對于無結(jié)構(gòu)的需求我們直接引入所有文本信息)

圖4 候選列表生成和重排序流程Fig.4 Candidate list generation and reordering process

·標準化文檔庫:所有類和需求的文檔都使用IR領(lǐng)域內(nèi)通用的手段進行預(yù)處理,包括標識符拆分、特殊字段與停用詞消除以及詞性還原和詞根獲取.

·通過IR計算文檔的相似度:本文使用了兩種不同類型的方法計算相似度,一種是基于向量空間的隱式語義索引(LSI)算法,另一種是基于詞匯重疊的二次分配問題(QAP)算法[19].

·生成候選列表:在生成的候選追蹤鏈列表中,我們按照每條追蹤鏈的需求和類之間的相似度值對該列表進行降序排列.

4.2 獲取初始需求域外類的預(yù)期值

4.2.1 初始化需求域

對于每個給定的需求,我們通過IR追蹤生成方法生成了該給定需求的候選列表,候選列表中類按照相似度值從高到低排序的.我們選擇候選類表中前3%的類構(gòu)成初始的需求域.

4.2.2 獲取類依賴圖

Understand是進行靜態(tài)代碼分析的集成開發(fā)環(huán)境(IDE),它可以分析項目中類的依賴關(guān)系.我們根據(jù)類的依賴關(guān)系獲取類依賴圖.

4.2.3 域外類的預(yù)期值的求解算法

我們已經(jīng)在第三節(jié)討論了類的預(yù)期值的求解算法,首先,由初始需求域內(nèi)的類和類依賴獲得域外類的代碼模式,再由代碼模式獲得域外類的預(yù)期值.算法2調(diào)用3.7節(jié)提到的預(yù)期值求解算法獲得域外類的預(yù)期值.該算法區(qū)分內(nèi)部類,葉子類和根類.需要注意的是,如果一個類既沒有依賴者也沒有被依賴者,我們無法分析其預(yù)期值,直接返回fail.

4.3 重排生成新的候選列表

算法3對每個給定需求的候選列表重排序.首先,初始化一個空的新候選列表,把初始需求域中的類直接加入新候選列表.然后,通過算法2計算域外類的預(yù)期值,如果給定類預(yù)期值是trace,直接將其加入新候選列表.如果給定類預(yù)期值是no_trace,則不加入.如果是unceratin,則將給定類加入不確定列表.最后,不確定列表中的類根據(jù)按照相似度從高到低依次加入新候選列表.而剩余的沒有加入新候選列表的類也按照相似度值從高到低依次加入新候選列表.新候選列表實現(xiàn)對原來的候選列表的重排序.

5 實 驗

在本節(jié)中,我們通過實驗驗證了本文提出的方法的有效性.5.1節(jié)介紹了數(shù)據(jù)集和實驗使用的IR追蹤生成方法.5.2節(jié)定義了實驗度量指標.5.3節(jié)實驗與結(jié)果分析.

5.1 數(shù)據(jù)集和實驗使用的IR技術(shù)

我們選擇兩個中等規(guī)模的軟件系統(tǒng):eTour(電子導(dǎo)游系統(tǒng))、iTrust3(在線醫(yī)療系統(tǒng))來驗證我們的方法.表1列舉了這兩個系統(tǒng)的基本信息.我們選擇這兩個系統(tǒng)的重要原因在于它們有可用的、高質(zhì)量的需求追蹤矩陣(RTM).每個需求追蹤矩陣(RTM)包含m x n個單元,其中m表示需求的數(shù)量,n表示代碼元素(本案例中是類)的數(shù)量.表2描述了etour系統(tǒng)的需求追蹤矩陣(RTM)的摘錄.單元格里的“X”表示需求和代碼元素之間存在一條追蹤鏈(trace link),單元格空白表示需求和代碼元素之間不存在追蹤鏈(trace link).實驗使用兩種不同類型的IR追蹤生成方法:基于向量空間的LSI和基于詞匯重疊的QAP.

表1 系統(tǒng)信息
Table 1 System information

eTouriTrustLanguagejavajavaKLOC2624#Executed class116226#Requirements58131Trace links in RTM308286

表2 eTour系統(tǒng)的RTM的摘錄
Table 2 Excerpt of RTM from eTour system

ClassRequirementR1:UC6R2:UC8GestionePuntiDiRistoroAgenziaXXGestionePuntiDiRistoroComuneIGestionePuntiDiRistoroAgenziaXXDBPuntoDiRistoroXXIGestionePuntiDiRistoroComuneIDBPuntoDiRistoroControlloDatiXBeanPuntoDiRistoroX

5.2 實驗度量指標

檢索工作中最常用的度量指標是查全率(recall)和查準率(precision)[20].本文的查全率(recall)是檢索到的正確追蹤鏈與RTM中所有追蹤鏈的比值,查準率是檢索到的正確追蹤鏈與所有檢索到的追蹤鏈的比值:

(1)

(2)

比較IR追蹤生成方法的一種常用的方式是在相同的查全率水平上比較不同IR追蹤生成方法的查準率,通常使用precision-recall曲線進行比較.為了進一步衡量實驗結(jié)果的整體質(zhì)量,我們選用了另外兩個常用的實驗度量指標:AP(average precision)與MAP(Mean Average Precision)[21],其中,AP用于度量每次查詢檢索到的相關(guān)文檔(類)的排序質(zhì)量.AP計算方法如下:

(3)

其中,r表示被查詢對象(類)在候選列表中的排序,precision(r)表示前r個類的準確率.isRelevant()是一個二值函數(shù),如果文檔相關(guān),則返回1,若無關(guān),則返回0.MAP是所有AP的平均值:

(4)

其中q是單次查詢,Q是查詢的總數(shù),MAP值越大,檢索到的相關(guān)文檔排序質(zhì)量越好.

5.3 實驗與結(jié)果分析

首先,我們對類在不同的代碼模式下追蹤到給定需求的可能性進行了比較.其次,為了驗證代碼模式的引入可以提高IR追蹤生成方法的準確性,實驗2使用改進前后的兩個原型工具分別對eTour和iTrust數(shù)據(jù)集進行分析并比較實驗結(jié)果,該實驗采用LSI作為向量相似度計算模型.最后,為了驗證不同類型的IR技術(shù)對實驗結(jié)果的影響,我們分別使用LSI和QAP對eTour數(shù)據(jù)集進行分析.

5.3.1 實驗1

本實驗對eTour和iTrust數(shù)據(jù)集中的內(nèi)部類和葉子類在不同的代碼模式下追蹤到給定需求的可能性進行了比較.根類和葉子類的實驗結(jié)果類似,因此根類不再贅述.

對于給定的需求,我們通過需求追蹤矩陣(RTM)和類依賴關(guān)系獲得每個類的代碼模式.已知每個類的代碼模式,可以進一步分析出每種代碼模式包含哪些類,以及這些類中追蹤到給定需求的類占的比例(由RTM可知類是否追蹤到給定需求).一種代碼模式在給定需求下求得的比例值越高,any類在該模式下追蹤給定需求的可能性越大.我們把每種代碼模式在數(shù)據(jù)集中每個需求下求得比例值取平均,來比較any類在不同模式下追蹤到給定需求的可能性.實驗結(jié)果如表3所示,表中的N/A表示代碼模式不存在,pure和mixed用于區(qū)分純模式和混合模式.從實驗結(jié)果可以看出,對于內(nèi)部類,TT模式比例值的平均值是60%～65%,邊界模式是5%～39%,NN模式0.5%～0.7%.iTrust數(shù)據(jù)集中沒有一個葉子類追蹤到需求.因此,我們不對iTrust數(shù)據(jù)集中的葉子類進行分析比較.對于葉子類,TT模式比例值的平均值是36%～83%,邊界模式是10%～34%.NN模式是0.9%.對于內(nèi)部類和葉子類,TT模式比例值的最低平均值比邊界模式比例值的最高平均值分別高21%和2%,NN模式比例值的平均值遠遠小于TT模式和邊界模式的比例值的平均值.因此,無論是內(nèi)部類還是葉子類(或者根類),在TT模式下追蹤的可能性都是最高的,其次是邊界模式,而在NN模式下追蹤的可能性遠遠小于在TT模式和邊界模式的追蹤的可能性.

表3 類在不同的模式下追蹤到給定需求的可能性
Table 3 Possibility of classes tracing a given requirement in different code patterns

模式分類模式不同代碼模式的比例值的平均值(eTour)不同代碼模式的比例值的平均值(iTrust)TT模式 t→any→t(pure)65%N/A t→any→t(mixed)61%60% t→t→any(pure)83%0% t→t→any(mixed)36%0%邊界模式 t→any→n(pure)36%38% t→any→n(mixed)16%33% n→any→t(pure)39%N/A n→any→t(mixed)21%5% t→n→any(pure)34%0% t→n→any(mixed)21%0% n→t→any(pure)10%0% n→t→any(mixed)12%0%NN模式 n→any→n0.5%0.7% n→n→any0.9%0%

5.3.2 實驗2

本實驗的主要目的驗證我們的方法是否優(yōu)于基線方法,我們選取僅使用LSI模型的方法(簡稱為LSI-ONLY)作為基線方法.而我們的方法是在LSI模型基礎(chǔ)上引入了代碼模式(簡稱為LSI-CP).對于相同的數(shù)據(jù)集,我們比較LSI-ONLY和LSI-CP的實驗結(jié)果.圖5是LSI-ONLY和LSI-CP的MAP值的比較.圖6是LSI-ONLY和LSI-CP的precision-recall曲線的比較.表4、表5顯示了相同的查全率點上LSI-CP相對于LSI-ONLY查準率的提高以及false positives(錯誤創(chuàng)建的追蹤鏈)的減少.從實驗結(jié)果可以得出以下結(jié)論:

圖5 LSI-ONLY和LSI-CP的MAP值比較Fig.5 MAP comparison between LSI-ONLY and LSI-CP

1)從圖5的MAP值來看,通過LSI-CP方法得到的類排序質(zhì)量要優(yōu)于LSI-ONLY.對eTour數(shù)據(jù)集使用LSI-CP比使用LSI-ONLY的MAP值提高了2.8%,對iTrust數(shù)據(jù)集使用LSI-CP比使用LSI-ONLY的MAP值提高了5%.

2)從圖6和表4、表5可以看出LSI-CP在查準率上的提升最高達到了9.74%(在iTrust數(shù)據(jù)集70%查全率處).也就是說,如果LSI-LONY想要在iTrust數(shù)據(jù)集上達到70%的查全率,需要否決掉1671條false positive來獲得200條正確的追蹤鏈.而LSI-CP只需要否決掉779條false positive來獲得200條正確的追蹤鏈.這種優(yōu)化在40%到80%的查全率區(qū)間上最明顯(eTour數(shù)據(jù)集查準率平均提升4.26%,iTrust數(shù)據(jù)集查準率平均提升6.16%).

3)從圖6和表4、表5還可以看出LSI-CP在查全率0%-40%的區(qū)間上幾乎沒有優(yōu)化.這是因為我們選擇候選列表的前3%類構(gòu)成初始需求域,初始需求域中的類不進行重排序直接加新候選列表.初始需求域可以根據(jù)不同的項目設(shè)置不同的大小,尋找最優(yōu)的初始需求域大小還需要進一步的研究.其次,LSI-CP在80%～100%區(qū)間上優(yōu)化效果較弱,這表明排名靠后的類與初始需求域內(nèi)的類存在較少的依賴關(guān)系, 代碼模式不能有效的提高排名靠后的正確的追蹤鏈中類的排名.目前,提升所有查全率區(qū)間上的查準率是業(yè)界公認的研究的難點[6,22],需要進一步的探索.

圖6 LSI-ONLY和LSI-CP的precision-recall曲線比較Fig.6 Comparison of precision-recall curves between LSI-ONLY and LSI-CP

表4 eTour數(shù)據(jù)集在相同的查全率點提升的查準率與減少的false positives(對比LSI-CP和LSI-ONLY)
Table 4 eTour dataset Improved precision and reduced false positives at the same recall point(Comparative LSI-CP and LSI-ONLY)

eTourPrecisionFPRecall(10%)+0%-0Recall(30%)+0%-0Recall(50%)+4.95%-42Recall(70%)+6.68%-203Recall(90%)+0.94%-240

表5 iTrust數(shù)據(jù)集在相同的查全率點提升的查準率與減少的false positives(對比LSI-CP和LSI-ONLY)
Table 5 iTrust dataset Improved precision and reduced false positives at the same recall point(Comparative LSI-CP and LSI-ONLY)

iTrustPrecisionFPRecall(10%)+0%-0Recall(30%)+0%-0Recall(50%)+5.01%-103Recall(70%)+9.74%-892Recall(90%)+2.17%-2018

5.3.3 實驗3

實驗2已經(jīng)證明在LSI模型基礎(chǔ)上引入代碼模式可以提高追蹤生成的準確度,那么使用不同的IR技術(shù)會對實驗結(jié)果造成什么影響？本實驗?zāi)康挠袃蓚€:第一,分析哪一種IR技術(shù)生成的追蹤準確度更高.第二,探索我們的方法是否適用于不同的IR技術(shù).我們使用LSI和QAP分別對數(shù)據(jù)集eTour進行分析,并比較試驗結(jié)果.圖7是QAP-ONLY(僅使用QAP)、QAP-CP(QAP引入代碼模式)、LSI-ONLY、LSI-CP的MAP值的比較.圖8是四種方法的precision-recall曲線的比較.從圖可以看出:

1)LSI-ONLY比QAP-ONLY的MAP值高20.7%,LSI-CP比QAP-CP的MAP值高19%.在整個查全率區(qū)間上LSI-ONLY比QAP-ONLY的查準率平均高10.6%,LSI-CP比QAP-CP的查準率平均高9.68%.在本實驗中,LSI的類的排序質(zhì)量以及查準率遠遠高于QAP.這也說明了為什么現(xiàn)在主流工作都選擇使用基于向量空間的模型進行追蹤的自動生成.

圖7 QAP-ONLY、QAP-CP、LSI-ONLY、LSI-CP的MAP值比較Fig.7 MAP Comparison of QAP-ONLY,QAP-CP,LSI-ONLY and LSI-CP

圖8 QAP-ONLY、QAP-CP、LSI-ONLY、LSI-CP的precision-recall曲線的比較Fig.8 Comparison of the precision-recall curves of QAP-ONLY,QAP-CP,LSI-ONLY and LSI-CP

2)從圖7和圖8可以看出QAP-CP的MAP的值和查準率都要高于QAP-ONLY,這說明我們的方法也適用于QAP.我們可以推測我們的方法是不受IR技術(shù)類型限制的,具有良好的適用性.

6 總結(jié)和展望

本文提出將代碼模式運用到追蹤自動生成的研究中.在選定給定需求初始需求域的情況下,代碼模式可以幫我們確定域外類與給定需求間的預(yù)期值,通過預(yù)期值對域外類進行重新排序.域內(nèi)類和重排后的域外類構(gòu)成新的候選列表并取代原來的候選列表.我們實現(xiàn)了一個原型工具進行驗證,實驗結(jié)果表明引入代碼模式的IR追蹤生成方法明顯優(yōu)于純IR追蹤生成方法,并且這種優(yōu)化不受IR技術(shù)類型的影響.

在未來的工作中,我們希望可以找到最優(yōu)的初始需求域大小.同時,我們也希望我們的方法和其它優(yōu)化策略結(jié)合(如用戶反饋),進一步提高IR追蹤生成方法的準確性.