錢曉捷,杜勝浩

(鄭州大學(xué) 信息工程學(xué)院,鄭州 450001) (*通信作者電子郵箱iezzdxdsh@126.com)

基于刻面分類標(biāo)識(shí)和聚類樹的構(gòu)件檢索方法

錢曉捷,杜勝浩*

(鄭州大學(xué) 信息工程學(xué)院,鄭州 450001) (*通信作者電子郵箱iezzdxdsh@126.com)

針對(duì)如何從規(guī)模龐大的軟件構(gòu)件庫中快速且高效地檢索出目標(biāo)構(gòu)件的問題,提出一種基于刻面分類標(biāo)識(shí)和聚類樹的構(gòu)件檢索方法。使用構(gòu)件標(biāo)識(shí)集合對(duì)構(gòu)件進(jìn)行刻面分類標(biāo)識(shí)描述,克服了單純采用刻面分類法對(duì)構(gòu)件進(jìn)行分類描述和檢索時(shí)帶來的主觀因素的影響；引入聚類樹的思想,對(duì)構(gòu)件進(jìn)行基于語義相似度的聚類分析,建立構(gòu)件聚類樹,能有效地縮小檢索范圍,減少檢索構(gòu)件與構(gòu)件庫中構(gòu)件比較的次數(shù),提高檢索效率。最后在實(shí)驗(yàn)中與一般檢索方法對(duì)比,實(shí)驗(yàn)結(jié)果表明該方法的構(gòu)件查準(zhǔn)率為88.3%,查全率為93.1%;而且在大規(guī)模的構(gòu)件庫中使用時(shí)依然有良好的檢索效果。

軟件構(gòu)件;刻面分類;構(gòu)件標(biāo)識(shí);聚類樹;構(gòu)件檢索

0 引言

構(gòu)件是軟件的基本構(gòu)成成分,也是軟件體系結(jié)構(gòu)的基本構(gòu)成要素。目前,軟件構(gòu)件技術(shù)已經(jīng)比較成熟。如何從規(guī)模龐大的構(gòu)件庫中快速準(zhǔn)確地檢索到軟件開發(fā)者所需的軟件構(gòu)件仍是一個(gè)值得研究的問題。構(gòu)件的檢索與構(gòu)件的描述和分類有著非常密切的關(guān)系,對(duì)構(gòu)件進(jìn)行合理的描述和分類,在構(gòu)件檢索時(shí)能夠簡(jiǎn)化檢索過程、提高檢索效率。目前,大部分的構(gòu)件檢索方法都基于刻面分類方法。刻面分類法被廣泛應(yīng)用于歐洲和印度的圖書館[1],Prieto-Díaz[2]將其引入到軟件復(fù)用和構(gòu)件檢索領(lǐng)域[2]。國外系統(tǒng)工程領(lǐng)域的專家在其提出的3C(Concept, Content, Context)構(gòu)件模型中對(duì)構(gòu)件描述時(shí)采用了刻面分類表示方法，Srinivas等[3]采用聚類分析的方法提高構(gòu)件檢索的效率；Vodithala等[4]使用遺傳算法優(yōu)化構(gòu)件檢索；Dutta等[5]基于圖的方法在構(gòu)件庫中進(jìn)行構(gòu)件檢索。在國內(nèi),王淵峰等[6]基于刻面分類描述構(gòu)件并結(jié)合樹匹配思想進(jìn)行了構(gòu)件檢索的實(shí)驗(yàn)；陸敬筠等[7]針對(duì)刻面描述構(gòu)件檢索方法的不足,結(jié)合領(lǐng)域本體相關(guān)知識(shí),采用領(lǐng)域本體和刻面描述相結(jié)合的方法進(jìn)行了構(gòu)件檢索研究；張雷等[8]也針對(duì)構(gòu)件的描述提出了構(gòu)件的標(biāo)識(shí)表示與自動(dòng)提取算法,并采用功能倒排索引檢索構(gòu)件庫中的構(gòu)件；童浩等[9]在蟻群算法的基礎(chǔ)上提出了基于數(shù)據(jù)挖掘的構(gòu)件決策模型,輔助構(gòu)件的檢索工作；姚全珠等[10]基于樹匹配的思想,通過計(jì)算葉子節(jié)點(diǎn)親和度進(jìn)行構(gòu)件匹配,提出了云端構(gòu)件匹配模型。

本文結(jié)合刻面分類和構(gòu)件的標(biāo)識(shí)對(duì)構(gòu)件進(jìn)行描述,通過構(gòu)件標(biāo)識(shí)集合從構(gòu)件描述文本中提取功能術(shù)語,利用向量表示文本,構(gòu)建構(gòu)件的向量空間模型,使構(gòu)件檢索匹配問題轉(zhuǎn)化為向量空間中向量計(jì)算的問題,實(shí)現(xiàn)構(gòu)件間的松弛匹配。同時(shí)使用基于語義相似度的構(gòu)件聚類算法,建立一棵構(gòu)件聚類索引樹,從而增大了構(gòu)件檢索的查全率和查準(zhǔn)率,提高了構(gòu)件的檢索效率。

1 構(gòu)件的標(biāo)識(shí)表示與向量化

1.1 構(gòu)件的標(biāo)識(shí)表示

構(gòu)件的標(biāo)識(shí)用來表示構(gòu)件的主要信息?？紤]到構(gòu)件檢索的特點(diǎn)和詞頻權(quán)重等因素,構(gòu)件的標(biāo)識(shí)集合應(yīng)包括領(lǐng)域術(shù)語集合和刻面術(shù)語集合。本文對(duì)構(gòu)件的標(biāo)識(shí)表示基于刻面分類法,采用多面分類機(jī)制并結(jié)合Web服務(wù)需求,將構(gòu)件的屬性劃分為層次、應(yīng)用領(lǐng)域、 操作系統(tǒng)和形態(tài)四個(gè)主刻面,每個(gè)主刻面下包含若干子刻面。其中,每個(gè)刻面都由一組基本的術(shù)語構(gòu)成[11]。根據(jù)構(gòu)件標(biāo)識(shí)集合對(duì)構(gòu)件進(jìn)行特征詞提取,其提取過程如圖1所示。

圖1 特征詞提取過程示意圖

對(duì)構(gòu)件描述文本分詞時(shí),導(dǎo)入手工輸入的停用詞集,過濾停用詞;根據(jù)語義庫的內(nèi)容對(duì)分詞結(jié)果擴(kuò)展,結(jié)合構(gòu)件標(biāo)識(shí)集合得到構(gòu)件特征詞。采用特征詞集對(duì)構(gòu)件進(jìn)行標(biāo)識(shí)表示,能夠更加準(zhǔn)確地描述構(gòu)件的特征,方便了構(gòu)件向量模型的建立,從而簡(jiǎn)化了構(gòu)件相似度的計(jì)算。

1.2 構(gòu)件標(biāo)識(shí)向量化

對(duì)構(gòu)件進(jìn)行標(biāo)識(shí)表示時(shí),構(gòu)件的特征詞間相互獨(dú)立,利用向量來表示構(gòu)件標(biāo)識(shí)文本,構(gòu)造構(gòu)件向量,建立向量空間模型。在構(gòu)件向量空間模型中,構(gòu)件是由構(gòu)件標(biāo)識(shí)(特征詞)組成的集合,并且每個(gè)特征詞都有其相應(yīng)的權(quán)重,將權(quán)重值作為向量值構(gòu)成構(gòu)件向量。例如,構(gòu)件Comp表示為C={t1,t2,…,ti,…,tn},其中，ti(1≤i≤n)為第i個(gè)特征詞,n為特征詞的個(gè)數(shù);同時(shí),對(duì)ti給定其權(quán)重wi,即CW=(w1,w2,…,wi,…,wn)。特征詞權(quán)重的計(jì)算方法通常是使用詞頻-逆向文件頻率(Term Frequency-Inverse Document Frequency, TFIDF)算法,該算法最早由Salton等在文獻(xiàn)[12]中提出,并隨著不同研究人員的研究不斷改進(jìn)。本文對(duì)構(gòu)件進(jìn)行標(biāo)識(shí)表示時(shí),一個(gè)構(gòu)件可能沒有某些子刻面(構(gòu)件庫中存在構(gòu)件含有這些子刻面)。因此,本文中計(jì)算特征詞權(quán)重值的公式采用文獻(xiàn)[13]中使用的特征詞加權(quán)公式,公式形式如下:

(1)

其中:CWi為構(gòu)件的第i個(gè)特征詞ti的權(quán)重值；fi表示ti在構(gòu)件庫中出現(xiàn)的頻率；n為構(gòu)件庫中構(gòu)件總數(shù)；ni為構(gòu)件庫中含有ti的構(gòu)件數(shù)；m為采用刻面分類描述構(gòu)件標(biāo)識(shí)得到的特征值(子刻面)的總數(shù)；d為構(gòu)件Comp的標(biāo)識(shí)描述中含有的特征詞的個(gè)數(shù)。使用詞頻來代替?zhèn)鹘y(tǒng)用0和1表示向量,完成構(gòu)件的向量化表示,有利于體現(xiàn)特征詞在構(gòu)件描述中的作用程度。

2 構(gòu)件聚類樹

2.1 構(gòu)件聚類樹的結(jié)構(gòu)

聚類樹是一種數(shù)據(jù)集聚類分層表示的樹結(jié)構(gòu)[14-15]。聚類樹將數(shù)據(jù)劃分為層次結(jié)構(gòu),從而成為一個(gè)高效檢索的索引結(jié)構(gòu)。本文中的構(gòu)件聚類樹是一棵非空的5層結(jié)構(gòu)的聚類樹,其結(jié)構(gòu)如圖2所示。

圖2 構(gòu)件聚類樹結(jié)構(gòu)

該聚類樹有且只有一個(gè)根節(jié)點(diǎn),代表構(gòu)件庫中所有構(gòu)件組成的構(gòu)件集,根節(jié)點(diǎn)為聚類樹的第一層;第二層為主刻面層,粗略地對(duì)構(gòu)件進(jìn)行劃分;第三層為子刻面層,對(duì)主刻面下的構(gòu)件進(jìn)行細(xì)致的劃分,將構(gòu)件劃分到某個(gè)子刻面;第四層為類層,對(duì)屬于同一子刻面的構(gòu)件進(jìn)行聚類,得到若干聚類中心;第五層為構(gòu)件層即葉子節(jié)點(diǎn)層,該層的節(jié)點(diǎn)包含構(gòu)件的特征詞并指向具體的構(gòu)件。

2.2 構(gòu)件聚類樹的構(gòu)造過程

構(gòu)件庫中所有構(gòu)件組成的集合構(gòu)成了該聚類樹的根節(jié)點(diǎn),得到構(gòu)件聚類樹的第一層。按照刻面分類劃分的主刻面粗略地將構(gòu)件劃分到各個(gè)主刻面下,形成第二層。然后,根據(jù)主刻面下的子刻面對(duì)構(gòu)件進(jìn)行詳細(xì)劃分,同一主刻面下,構(gòu)件只屬于某一個(gè)子刻面,形成第三層。第四層為類層,是對(duì)子刻面下的構(gòu)件聚類得到的,本文采用K近鄰聚類算法對(duì)構(gòu)件進(jìn)行語義相似聚類。文中通過計(jì)算兩個(gè)構(gòu)件向量的余弦相似度來表示這兩個(gè)構(gòu)件的相似程度,計(jì)算公式如下:

(2)

其中:Sim(C1,C2)是構(gòu)件Comp1和構(gòu)件Comp2的余弦相似度；CW1i是構(gòu)件Comp1的第i個(gè)子刻面的向量權(quán)重；CW2i是構(gòu)件Comp2的第i個(gè)子刻面的向量權(quán)重；m是采用刻面分類描述構(gòu)件標(biāo)識(shí)得到的特征詞(子刻面)的總個(gè)數(shù)。子刻面下構(gòu)件聚類的步驟如下:

Step1 初始化聚類中心。將構(gòu)件庫中的構(gòu)件按照式(1)向量化,從子刻面下的構(gòu)件中選取k個(gè)構(gòu)件作為初始聚類中心,在選擇聚類中心時(shí)盡量使得k個(gè)作為中心的構(gòu)件的相似度很小,得初始聚類中心Cl=(Cl1,Cl2,…,Clk)。

Step2 根據(jù)式(2),分別計(jì)算當(dāng)前子刻面下其他構(gòu)件與這k個(gè)作為類中心的構(gòu)件的相似度,并歸類于與其相似度最大的那個(gè)聚類中心。

Step4 判斷新得到的聚類中心Cl′與原聚類中心Cl是否完全相同,若完全相同則結(jié)束聚類,跳到Step7;否則判斷count的值是否小于1 000,若不小于則跳到Step7,否則繼續(xù)向下執(zhí)行。

Step7 聚類完成,結(jié)束聚類算法。

對(duì)每個(gè)子刻面下的構(gòu)件都按照上述聚類算法進(jìn)行聚類,于是得到構(gòu)件聚類樹第四層的節(jié)點(diǎn)。聚類樹第五層為構(gòu)件層,屬于同一類的構(gòu)件被分在一個(gè)類下,構(gòu)件層的節(jié)點(diǎn)直接指向其對(duì)應(yīng)的具體的構(gòu)件。

3 基于刻面標(biāo)識(shí)和聚類樹的構(gòu)件檢索

3.1 構(gòu)件檢索機(jī)制

構(gòu)件檢索與構(gòu)件的分類和描述密切相關(guān),不同的分類方法對(duì)應(yīng)著不同的檢索機(jī)制。通過刻面分類標(biāo)識(shí)關(guān)聯(lián)的特征詞集合,多角度標(biāo)識(shí)待檢索構(gòu)件。另外,匹配松散度也是構(gòu)件檢索中得一個(gè)重要參數(shù)。檢索條件與檢索結(jié)果精確匹配是所有研究人員最為想要的,但在實(shí)際實(shí)驗(yàn)過程中,這種精準(zhǔn)匹配的機(jī)會(huì)并不多,大多數(shù)情況下還是尋找能夠最大相似匹配的構(gòu)件。目前,基于刻面描述的構(gòu)件的檢索主要采用的還是以傳統(tǒng)的數(shù)據(jù)庫檢索技術(shù)為主,并結(jié)合同義詞詞典和刻面術(shù)語間的層次結(jié)構(gòu)來實(shí)現(xiàn)構(gòu)件的松弛匹配[6]。

本文的檢索方法基于語義相似度,具備一定的模糊匹配功能;另外,用戶對(duì)要檢索的構(gòu)件的描述可能不完整,不能包含所有刻面分類標(biāo)識(shí)集合中的特征詞,本文的檢索方法為用戶設(shè)置默認(rèn)值,使其具備一定的張弛能力,從而使檢索結(jié)果具有良好的查準(zhǔn)率與查全率。

3.2 構(gòu)件檢索過程

經(jīng)過構(gòu)件的向量化處理,構(gòu)件檢索最終轉(zhuǎn)化為構(gòu)件相似度的計(jì)算。其基本思想如下:在建立了構(gòu)件聚類樹的基礎(chǔ)上,根據(jù)采用刻面分類法劃分得到的刻面分類標(biāo)識(shí)集合提取待檢索構(gòu)件(用戶的檢索條件QU)描述中的特征詞,根據(jù)構(gòu)件向量模型將待檢索構(gòu)件向量化。

(3)

待檢索構(gòu)件的特征詞的權(quán)重值計(jì)算公式與式(1)略有不同,采用式(3)進(jìn)行計(jì)算。其中,QWi為檢索構(gòu)件Query的第i個(gè)特征詞ti的權(quán)重值,fi為ti在構(gòu)件庫中出現(xiàn)的頻率,n為構(gòu)件庫中的構(gòu)件總數(shù),ni為構(gòu)件庫中含有ti的構(gòu)件數(shù),m為基于刻面分類描述構(gòu)件標(biāo)識(shí)得到的特征值(子刻面)的總個(gè)數(shù),d為檢索構(gòu)件Query的標(biāo)識(shí)描述中含有的特征詞的個(gè)數(shù)。依次計(jì)算檢索構(gòu)件與構(gòu)件聚類樹第四層的類層中的各個(gè)節(jié)點(diǎn)(表示聚類中心的構(gòu)件)的相似度,相似度計(jì)算公式類似于式(2),即

(4)

其中:Sim(C,QU)是作為聚類中心的構(gòu)件Comp與檢索構(gòu)件Query的余弦相似度；CWi是構(gòu)件Comp的第i個(gè)子刻面的向量權(quán)重；QWi是檢索構(gòu)件Query的第i個(gè)子刻面的向量權(quán)重；m是基于刻面分類描述構(gòu)件標(biāo)識(shí)得到的特征詞(子刻面)的總個(gè)數(shù)。在每個(gè)子刻面的多個(gè)聚類中心中選取與檢索構(gòu)件相似度最大的聚類中心,記錄該類中的所有構(gòu)件。根據(jù)刻面劃分原理,一個(gè)主刻面下不同子刻面包含的構(gòu)件不同,與檢索構(gòu)件擁有較高相似度的聚類中心下的所有構(gòu)件都可作為檢索結(jié)果候選構(gòu)件,于是對(duì)同一主刻面不同子刻面下被記錄的構(gòu)件求并集;由于一個(gè)構(gòu)件含有多個(gè)刻面值(特征詞),故同一個(gè)構(gòu)件會(huì)出現(xiàn)在不同主刻面下,因此再對(duì)不同主刻面下滿足條件的所有構(gòu)件求交集,使得到的檢索結(jié)果中的構(gòu)件不重復(fù)。計(jì)算所得構(gòu)件集合中的構(gòu)件與檢索構(gòu)件的相似度,滿足要求的構(gòu)件與檢索構(gòu)件的相似度記為S1(0≤S1≤1);上述構(gòu)件集合中的構(gòu)件在不同主刻面下都有其與所屬類的聚類中心的相似度,為了體現(xiàn)聚類中心在計(jì)算檢索構(gòu)件與檢索結(jié)果中的構(gòu)件的最終相似度的作用,將構(gòu)件在不同主刻面下的相似度求和取平均數(shù),記為S2(0≤S2≤1),于是可以得到檢索構(gòu)件與上述構(gòu)件集中構(gòu)件的最終相似度記為S(0≤S≤1),S=(S1+S2)/2。通過在不同閾值下進(jìn)行的實(shí)驗(yàn)測(cè)試,發(fā)現(xiàn)閾值取為0.7,即構(gòu)件相似度S≥0.7時(shí),檢索結(jié)果的查準(zhǔn)率和查全率較好,故在本文中閾值設(shè)為0.7,第5章的實(shí)驗(yàn)也是在此默認(rèn)值下進(jìn)行的。最后,對(duì)相似度S≥0.7的構(gòu)件進(jìn)行排序,得到最終檢索結(jié)果。

算法流程描述如下。

輸入 檢索構(gòu)件Query描述文本;構(gòu)件聚類樹T;構(gòu)件刻面標(biāo)識(shí)集合FT。

輸出 相似度從大到小的N個(gè)構(gòu)件。

1)

forFT中的所有特征詞

2)

if(FT的特征詞i在檢索構(gòu)件的描述中出現(xiàn))

3)

array_Qi=1;

4)

else

5)

array_Qi=0;

6)

array_QWi=QWi;

7)

end for;

8)

forT的類層中的所有節(jié)點(diǎn)

9)

Sim_QC=Sim(C,QU);

10)

end for;

11)

forT的子刻面層的所有節(jié)點(diǎn)

12)

maxSim=max(Sim_QC,k);

13)

相似度最大類中的所有構(gòu)件保存到maxSim_C;

14)

end for;

15)

forT的主刻面層的所有節(jié)點(diǎn)

16)

unionCQ=Union(maxSim_C,n);

17)

unionCQ中的構(gòu)件與聚類中心的相似度的值保存到unionCQ_Sim;

18)

end for;

19)

array_mixCQ=Mix(unionCQ,n);

20)

array_mixCQ_Sim記錄array_mixCQ中的構(gòu)件與所屬類中心的相似度;

21) forarray_mixCQ中的所有構(gòu)件

22)

S1=Sim(C,QU);

23)

S2=n個(gè)主刻面下的相似度的平均值;

24)

if((S1+S2)/2≥0.7)

25)

result=(array_mixCQi, (S1+S2)/2);

26)

end for

27)

sort(result);

算法說明:步驟1)～7)是將檢索構(gòu)件進(jìn)行向量化表示,步驟6)按式(3)進(jìn)行計(jì)算;步驟8)～10)用式(4)計(jì)算檢索構(gòu)件與聚類樹類層各節(jié)點(diǎn)(即作為聚類中心的構(gòu)件)的相似度;步驟11)～14)是選取與檢索構(gòu)件相似度最大的節(jié)點(diǎn)作為聚類中心,步驟12)中的k為聚類個(gè)數(shù);步驟15)～18)是對(duì)同一主刻面下不同子刻面中所有構(gòu)件求并集;步驟19)和步驟20)是對(duì)不同主刻面下得到的構(gòu)件集合求交集同時(shí)記錄構(gòu)件與所屬聚類中心的相似度;步驟21)～26)是計(jì)算檢索構(gòu)件與符合要求構(gòu)件的總相似度;步驟27)是將得到的檢索結(jié)果中的構(gòu)件排序呈現(xiàn)給用戶。該檢索算法的空間復(fù)雜度取決于構(gòu)件的個(gè)數(shù);由于構(gòu)件庫的刻面數(shù)一般不超過8個(gè),在本文算法中相對(duì)于構(gòu)件的個(gè)數(shù)可以忽略不計(jì),故算法的時(shí)間復(fù)雜度為O(n)。

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

為驗(yàn)證本文所提出的構(gòu)件檢索方法能提高檢索的效率,本文使用模擬構(gòu)件庫進(jìn)行構(gòu)件檢索實(shí)驗(yàn)。通過對(duì)開源中國(www.oschina.net)的開源軟件庫中的部分開源組件和控件(視為構(gòu)件)信息進(jìn)行采集處理得到實(shí)驗(yàn)數(shù)據(jù)集,構(gòu)建了一個(gè)包含Web應(yīng)用、程序開發(fā)、圖像處理、數(shù)據(jù)庫、手機(jī)/移動(dòng)開發(fā)等領(lǐng)域共2 559個(gè)構(gòu)件的本地構(gòu)件庫。

檢索效果通過評(píng)測(cè)查準(zhǔn)率P、查全率R和F-measure[16]三個(gè)指標(biāo)來體現(xiàn)。三個(gè)指標(biāo)的計(jì)算公式分別為P=nr/Nq,R=nr/Nr,F-measure=2PR/(P+R),其中:nr是檢索結(jié)果中滿足檢索條件的構(gòu)件個(gè)數(shù);Nq是檢索得到的構(gòu)件的總個(gè)數(shù);Nr是構(gòu)件庫中滿足檢索條件的構(gòu)件個(gè)數(shù)。F-measure是對(duì)檢索結(jié)果的查準(zhǔn)率和查全率的一個(gè)綜合評(píng)價(jià),能夠有效地評(píng)價(jià)檢索的查準(zhǔn)和查全效果。只有當(dāng)P和R相近且都較大時(shí),F-measure才會(huì)較高。

4.1 實(shí)驗(yàn)結(jié)果對(duì)比實(shí)驗(yàn)

分別根據(jù)文獻(xiàn)[8]和文獻(xiàn)[17]的思想實(shí)現(xiàn)了基于構(gòu)件標(biāo)識(shí)自動(dòng)提取的功能倒排索引構(gòu)件檢索方法和分級(jí)聚類索引構(gòu)件檢索方法,并與本文提出的檢索方法在相同的數(shù)據(jù)集和實(shí)驗(yàn)平臺(tái)上進(jìn)行對(duì)比實(shí)驗(yàn)。為突出聚類樹在本文所提出的檢索方法的作用,本文還實(shí)現(xiàn)了基于刻面分類標(biāo)識(shí)和聚類分析的構(gòu)件檢索方法,這種方法類似于文獻(xiàn)[13]中提出的檢索方法,不使用聚類樹思想,在構(gòu)件向量化表示之后直接對(duì)構(gòu)件庫中的構(gòu)件聚類,檢索時(shí)采用第3章中描述的檢索方法。因此,對(duì)比實(shí)驗(yàn)共分為4組,各組對(duì)應(yīng)檢索方法如表1所示。

表1 四組構(gòu)件檢索方法

通過Matlab 8.5實(shí)驗(yàn)仿真平臺(tái)和MyEclipse10對(duì)上述算法進(jìn)行實(shí)現(xiàn)。分別對(duì)這4組方法進(jìn)行10次檢索實(shí)驗(yàn),每次實(shí)驗(yàn)使用30個(gè)檢索構(gòu)件,計(jì)算得到查準(zhǔn)率和查全率的平均值,再計(jì)算F-measure的值。各組檢索結(jié)果如表2所示。

表2 檢索實(shí)驗(yàn)數(shù)據(jù)對(duì)比表

從表2中的4組實(shí)驗(yàn)檢索結(jié)果可以明顯看出D組的查準(zhǔn)率、查全率和F-measure的值都要比C組的高很多,說明在檢索方法中采用了聚類樹比單純使用聚類分析得到的效果較好。另外,也可看出相對(duì)于A組和B組的檢索方法,使用本文提出的檢索方法(D組)得到的查準(zhǔn)率和查全率有明顯提高,而且F-measure的值也比其他兩種方法得到的要大。

4.2 擴(kuò)大構(gòu)件庫規(guī)模實(shí)驗(yàn)

考慮到構(gòu)件庫的規(guī)模正逐漸擴(kuò)大,為驗(yàn)證本文方法在大規(guī)模構(gòu)件庫中檢索時(shí)的效果依然良好,采用隨機(jī)抽取本地構(gòu)件庫中的構(gòu)件重復(fù)入庫的方法[8],增加本地構(gòu)件庫中構(gòu)件的數(shù)量。分別在7 677個(gè)、12 795個(gè)、17 913個(gè)以及23 031個(gè)構(gòu)件的模擬構(gòu)件庫中重新進(jìn)行檢索實(shí)驗(yàn),依然進(jìn)行10次、每次30個(gè)檢索構(gòu)件的檢索實(shí)驗(yàn)。查準(zhǔn)率、查全率和F-measure值的實(shí)驗(yàn)結(jié)果分別如圖3～5所示。

圖3 不同構(gòu)件庫規(guī)模的查準(zhǔn)率比較

圖4 不同構(gòu)件庫規(guī)模的查全率比較

圖5 不同構(gòu)件庫規(guī)模的F-measure值比較

另外,為說明構(gòu)件庫規(guī)模增大后算法的檢索效率情況,給出不同算法查詢響應(yīng)時(shí)間,如圖6所示。

圖6 不同構(gòu)件庫規(guī)模的查詢響應(yīng)時(shí)間比較

實(shí)驗(yàn)結(jié)果表明，構(gòu)件庫的規(guī)模增大后,本文算法的查準(zhǔn)率和查全率仍在87%以上,F-measure值保持在0.90左右,比其他三種算法的檢索結(jié)果要好;而且查詢響應(yīng)時(shí)間的增加在對(duì)數(shù)級(jí)別以下。所以，本文方法是行之有效的,而且擁有較好的檢索效果,同時(shí)也可在規(guī)模較大的構(gòu)件庫中使用。

5 結(jié)語

本文提出的基于刻面分類標(biāo)識(shí)和聚類樹的構(gòu)件檢索方法對(duì)構(gòu)件進(jìn)行刻面分類標(biāo)識(shí)描述,并通過構(gòu)件向量模型將構(gòu)件向量化表示,建立構(gòu)件聚類樹,在檢索構(gòu)件時(shí)直接計(jì)算檢索構(gòu)件與聚類中心的語義相似度,將具有較高相似度的構(gòu)件提供給用戶供用戶選擇。實(shí)驗(yàn)結(jié)果表明，本文的檢索方法有著較高的查準(zhǔn)率與查全率,并且在構(gòu)件庫規(guī)模的擴(kuò)大后依然有較好的檢索效果。本文方法的檢索效果依賴于構(gòu)件的描述和構(gòu)件聚類,因此后續(xù)工作將對(duì)構(gòu)件的描述方法和構(gòu)件聚類算法進(jìn)行重點(diǎn)研究,結(jié)合Web服務(wù)發(fā)現(xiàn)領(lǐng)域的相關(guān)知識(shí),完善構(gòu)件描述方法、優(yōu)化構(gòu)件聚類,從而進(jìn)一步提高檢索效果。

References)

[1] RANGANATHAN S R, GOPINATH M A. Prolegomena to Library Classification [M]. 3rd ed. Madras: Madras Library Association, 1967.

[3] SRINIVAS C, RADHAKRISHNA V, RAO C. Clustering and classification of software component for efficient component retrieval and building component reuse libraries [J]. Procedia Computer Science, 2014, 31(1): 1044-1050.

[4] VODITHALA S, PABBOJU S. A dynamic approach for retrieval of software components using genetic algorithm[C]// Proceedings of the 2015 IEEE International Conference on Software Engineering and Service Science. Piscataway, NJ: IEEE, 2015: 406-410.

[5] DUTTA S, SENGUPTA S. Retrieval of software component version from a software version database: a graph based approach [C]// Proceedings of the 2015 International Conference on Advances in Computer Engineering and Applications. Piscataway, NJ: IEEE, 2015: 255-259.

[6] 王淵峰, 張涌, 任洪敏, 等.基于刻面描述的構(gòu)件檢索[J]. 軟件學(xué)報(bào), 2002, 13(8): 1546-1551. (WANG Y F, ZHANG Y, REN H M, et al. Retrieving components based on faceted classification [J]. Journal of Software, 2002, 13(8): 1546-1551.)

[7] 陸敬筠, 宋培鐘.領(lǐng)域本體和刻面描述相結(jié)合的構(gòu)件檢索研究[J]. 計(jì)算機(jī)應(yīng)用與軟件, 2013, 30(8): 36-38. (LU J Y, SONG P Z. On component retrieval method based on the combination of facets description and domain ontology [J]. Computer Applications and Software, 2013, 30(8): 36-38.)

[8] 張雷, 陳立潮, 潘理虎, 等.構(gòu)件的標(biāo)識(shí)表示與檢索方法研究[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2013, 34(5): 1076-1079. (ZHANG L, CHEN L C, PAN L H, et al. Study on tags representation of components and tags based components retrieval [J]. Journal of Chinese Computer Systems, 2013, 34(5): 1076-1079.)

[9] 童浩, 孫航, 李晶, 等.基于改進(jìn)蟻群算法的構(gòu)件檢索方法[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(7): 2057-2059, 2064. (TONG H, SUN H, LI J, et al. Method based on improved ant colony algorithm for component retrieving [J]. Application Research of Computers, 2015, 32(7): 2057-2059, 2064.)

[10] 姚全珠, 馮歡, 田琳, 等.基于云端的構(gòu)件庫檢索模型[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36 (增刊1): 262-264. (YAO Q Z, FENG H, TIAN L, et al. Retrieval model based on cloud component library [J]. Journal of Computer Applications, 2016, 36 (Supp1): 262-264.)

[11] 王映輝.構(gòu)件式軟件技術(shù)[M]. 北京: 機(jī)械工業(yè)出版社, 2012: 86. (WANG Y H. Component-Based Software Technology [M]. Beijing: China Machine Press, 2012: 86.)

[12] SALTON G, CLEMENT T Y. On the construction of effective vocabularies for information retrieval[C]// SIGPLAN 1973: Proceedings of the 1973 Meeting on Programming Languages and Information Retrieval. New York: ACM, 1973: 11.

[13] 劉大昕, 趙磊, 王卓, 等.一種基于刻面分類和聚類分析的構(gòu)件分類檢索方法[J]. 計(jì)算機(jī)應(yīng)用, 2004, 24 (增刊1): 89-90. (LIU D X, ZHAO L, WANG Z, et al. A method of component classification retrieval based on facet classification and cluster analysis [J]. Journal of Computer Applications, 2004, 24 (Supp1): 89-90.)

[14] YU D T, ZHANG A D. Cluster tree: integration of cluster representation and nearest neighbor search for large datasets with high dimensions [J]. IEEE Transections on Knowledge and Data Engineering, 2003, 15(5): 1316-1337.

[15] 田曉珍, 任姚鵬, 王春紅, 等.一種改進(jìn)的構(gòu)件聚類索引樹的研究[J]. 現(xiàn)代計(jì)算機(jī), 2014(8): 12-15, 25. (TIAN X Z, REN Y P, WANG C H, et al. Research on an improved component cluster index tree [J]. Modern Computer, 2014(8): 12-15, 25.)

[16] RIJSBERGEN C J. Information Retrieval [M]. London, UK: Butterworths Press, 1979: 120.

[17] 王文霞.基于分級(jí)策略和聚類索引樹的構(gòu)件檢索方法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2016, 26(4): 110-11. (WANG W X. A component retrieval method based on classified policy and cluster index tree [J]. Computer Technology and Development, 2016, 26(4): 110-11.)

Componentretrievalmethodbasedonidentificationoffacetedclassificationandclustertree

QIAN Xiaojie, DU Shenghao*

(SchoolofInformationEngineering,ZhengzhouUniversity,ZhengzhouHenan450001,China)

To quickly and efficiently retrieve the target component from a large software component library, a component retrieval method based on identification of faceted classification and cluster tree was proposed. The component with facet classification identification was described by using the set of component identification, which overcomes the impact of subjective factors when only using facets classification to describe and retrieve components. By introducing cluster tree, the component cluster tree was established by analysis clustering of components based on semantic similarity, thus narrowing the retrieval area, reducing the number of comparisons with component libary, and improving the search efficiency. Finally, the proposed method was experimented and compared with other common retrieval methods. The results show that the precision of the proposed method is 88.3% and the recall ratio is 93.1%; moreover, the proposed method also has a good retrieval effect when searching in a large-scale component library.

software component; faceted classification; component identification; cluster tree; component retrieval

2017- 05- 11;

2017- 06- 29。

國家社會(huì)科學(xué)基金資助項(xiàng)目(14BYY096)。

錢曉捷(1963—),男,江蘇無錫人,副教授,碩士,CCF會(huì)員,主要研究方向:嵌入式系統(tǒng)、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu); 杜勝浩(1990—),男,河南濮陽人,碩士研究生,主要研究方向:軟件體系結(jié)構(gòu)、數(shù)據(jù)挖掘。

1001- 9081(2017)10- 2973- 05

10.11772/j.issn.1001- 9081.2017.10.2973

TP311.131

A

This work is partially supported by the National Social Science Foundation of China (14BYY096).

QIANXiaojie, born in 1963, M. S., associate professor. His research interests include embedded system, computer system architecture.

DUShenghao, born in 1990, M. S. candidate. His research interests include software architecture, data mining.