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

錢曉捷,杜勝浩

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

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

錢曉捷,杜勝浩*

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

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

軟件構(gòu)件;刻面分類;構(gòu)件標識;聚類樹;構(gòu)件檢索

0 引言

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

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

1 構(gòu)件的標識表示與向量化

1.1 構(gòu)件的標識表示

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

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

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

1.2 構(gòu)件標識向量化

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

(1)

其中:CWi為構(gòu)件的第i個特征詞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)件標識得到的特征值(子刻面)的總數(shù)；d為構(gòu)件Comp的標識描述中含有的特征詞的個數(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),從而成為一個高效檢索的索引結(jié)構(gòu)。本文中的構(gòu)件聚類樹是一棵非空的5層結(jié)構(gòu)的聚類樹,其結(jié)構(gòu)如圖2所示。

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

(3)

待檢索構(gòu)件的特征詞的權(quán)重值計算公式與式(1)略有不同,采用式(3)進行計算。其中,QWi為檢索構(gòu)件Query的第i個特征詞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)件標識得到的特征值(子刻面)的總個數(shù),d為檢索構(gòu)件Query的標識描述中含有的特征詞的個數(shù)。依次計算檢索構(gòu)件與構(gòu)件聚類樹第四層的類層中的各個節(jié)點(表示聚類中心的構(gòu)件)的相似度,相似度計算公式類似于式(2),即

(4)

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

算法流程描述如下。

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

輸出 相似度從大到小的N個構(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é)點

9)

Sim_QC=Sim(C,QU);

10)

end for;

11)

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

12)

maxSim=max(Sim_QC,k);

13)

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

14)

end for;

15)

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

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個主刻面下的相似度的平均值;

24)

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

25)

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

26)

end for

27)

sort(result);

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

4 實驗結(jié)果及分析

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

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

4.1 實驗結(jié)果對比實驗

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

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

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

表2 檢索實驗數(shù)據(jù)對比表

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

4.2 擴大構(gòu)件庫規(guī)模實驗

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

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

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

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

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

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

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

5 結(jié)語

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

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]. 軟件學報, 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] 陸敬筠, 宋培鐘.領域本體和刻面描述相結(jié)合的構(gòu)件檢索研究[J]. 計算機應用與軟件, 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)件的標識表示與檢索方法研究[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] 童浩, 孫航, 李晶, 等.基于改進蟻群算法的構(gòu)件檢索方法[J]. 計算機應用研究, 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]. 計算機應用, 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]. 北京: 機械工業(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]. 計算機應用, 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] 田曉珍, 任姚鵬, 王春紅, 等.一種改進的構(gòu)件聚類索引樹的研究[J]. 現(xiàn)代計算機, 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] 王文霞.基于分級策略和聚類索引樹的構(gòu)件檢索方法[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。

國家社會科學基金資助項目(14BYY096)。

錢曉捷(1963—),男,江蘇無錫人,副教授,碩士,CCF會員,主要研究方向:嵌入式系統(tǒng)、計算機系統(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.