王文霞

(運城學院 計算機科學與技術系，山西 運城 044000)

基于分級策略和聚類索引樹的構件檢索方法

王文霞

(運城學院 計算機科學與技術系，山西 運城 044000)

基于刻面的構件表示法，其術語空間需要人工建立和維護，具有較強的人為主觀性。針對此問題，文中采用刻面分類與全文檢索相結合的構件表示方法，提出了一種基于分級策略和聚類索引樹的構件檢索方法。該方法采用基于語義相似度與優(yōu)化的構件聚類算法構建構件聚類索引樹，并為每個刻面引入合理的權重因子。在真實構件庫上的實驗結果表明：基于分級策略和聚類索引樹的構件檢索方法是有效的，相比沒有引入分級策略的構件檢索方法具有較高的構件查全率和查準率。

刻面分類；聚類分析；語義分析；索引樹；分級策略

0 引 言

軟件復用是提高軟件生產(chǎn)率和質(zhì)量的有效途徑，其核心是軟件構件技術。而軟構件技術領域中，構件的分類與構件的檢索是亟待解決的兩大主要問題[1-4]。構件分類的合理性是實現(xiàn)構件高效檢索的有效途徑和關鍵因素，高效的構件檢索可以降低構件理解和查詢的成本[5-9]。因此，合理有效的構件分類和準確高效的構件檢索，將會大大促進軟件的復用，進而促進軟件產(chǎn)業(yè)的快速發(fā)展。

現(xiàn)有的構件分類有多種。W.Frakes將基于構件的表示劃分為信息科學方法、超文本方法和人工智能方法。其中，信息科學方法具有對構件多視角分類描述的特點，在實際中得到廣泛應用?？堂娣诸惙▽儆谛畔⒖茖W方法中的一種，其基本思想是將反映構件本質(zhì)特性的各個刻面及相關術語置于一定上下文中，實現(xiàn)對構件的精確分類。該表示法可表達豐富的構件信息，是檢索代價、檢索質(zhì)量和復雜性三者較均衡的方法，適合于大規(guī)模構件庫的管理[10]；但是，刻面分類方法中構件表示所依賴的術語空間需要人工建立和維護，帶有較強的人為主觀因素，其結果可能導致用戶無法檢索到真正所需的構件[11]。

針對此問題，文中基于刻面分類的構件表示法和全文檢索方法結合的方法描述構件，以達到降低刻面表示的主觀性問題；同時采用基于語義相似度與優(yōu)化的構件聚類算法構造構件聚類索引樹，并引入分級策略，提出一種基于分級策略和構件聚類索引樹的構件檢索方法，實現(xiàn)對構件更準確、更高效的檢索。

1 相關概念

1.1 構件的分類表示

文中對構件的描述采用刻面分類表示法與全文檢索相結合的方法。該方法首先依據(jù)某種刻面分類方案(如以刻面的完整性和獨立性定義的刻面分類方案——功能、操作對象、使用環(huán)境、構件形態(tài)和表示及性能共5個刻面[12])獲取構件的描述文本相對應的每個刻面值；然后采用全文檢索的方法對每個刻面下的構件進行聚類分析獲取構件的分類描述。這種構件表示法不僅實現(xiàn)了刻面值由受控詞到文本的轉變，減少了術語空間需人工建立和維護而存在的主觀因素，而且構件文本經(jīng)過刻面分類后內(nèi)容更為集中，更有利于構件相似度的計算，從而提高基于全文檢索的構件聚類精度，實現(xiàn)對構件更合理的分類描述。該構件分類表示法如圖1所示。

圖1 構件分類表示

1.2 構件聚類索引樹

構件聚類索引樹(Component Cluster Index Tree，CCIT)是一棵非空的4層結構的聚類索引樹[13]，它滿足：

(1)有且僅有一個根節(jié)點(root)，代表構件庫中的所有構件。

(2)父節(jié)點中包含著指向子節(jié)點的指針和子節(jié)點的信息。

(3)葉節(jié)點中包含著指向某個具體構件的指針。

(4)第一層為根節(jié)點，第二層為刻面層，第三層為類層，第四層為構件層。類層包含著指向該類中所有構件(葉節(jié)點)的指針，同時包含著類特征詞信息；構件層即葉節(jié)點層除了包含條件(3)中的內(nèi)容，還帶有構件特征詞信息。其結構如圖2所示。

圖2 構件聚類索引樹

該聚類索引樹構建的基本思想是首先基于刻面分類方案對所有構件進行初次分類，形成索引樹的第二層；然后針對每個刻面下的初次分類結果，采用相應的聚類算法進行聚類分析，形成索引樹的第三層(類層)和第四層(構件層)。文中第二層采用了基于上述刻面分類與全文檢索相結合的構件分類表示方法對構件進行初次分類；索引樹的第三、四層采用了基于語義相似度與優(yōu)化的構件聚類算法實現(xiàn)對構件的分類。其基本思想是：首先基于知網(wǎng)的語義相似度計算方法從語義角度獲取構件文本間的相似度；再采用最近鄰聚類和遺傳算法相結合的方法實現(xiàn)對構件的優(yōu)化聚類分析[14]。

2 構件檢索方法

基于分級策略和聚類索引樹的檢索方法的基本思想是:以基于語義的構件聚類索引樹為基礎，依次計算出不同刻面下檢索條件與類層中各節(jié)點的相似度；然后計算檢索條件與不同刻面下相似度最高的類中的各個構件的相似度；接著引入分級策略，為刻面層的各個節(jié)點(即不同刻面)設置不同的等級權重值，進而計算其不同刻面與檢索條件的最終相似度值，并獲得相應刻面下相似度較高的構件集合；再次，對各個刻面下所求的構件求交集，并對不同的刻面下同一構件的相似度求和，求其檢索條件與某個構件的總相似度值；最后，依據(jù)總相似度值，對獲取的構件進行排序，進而便于用戶獲取所需構件。

其中，(1)檢索條件與類層次節(jié)點間的相似度采用如下文本相似度計算公式：

(1)

式中：WDk表示特征詞k在檢索文本中的權重值；WDik表示特征詞k在第i個類文本中的權重值。

(2)檢索條件與構件庫中第i個刻面下第j個構件的相似度計算公式為：

Sij=αi(Sim+Smj)

(2)

(3)檢索條件與構件的總相似度計算公式為：

(3)

基于分級策略的構件檢索算法如下：

輸入：所要檢索的構件文本；

輸出：相似度從大到小的N個構件。

Step1：提取檢索構件文本的特征詞，形成檢索特征詞向量；

Step2：i=1；

Step3：采用式(1)，計算刻面i下檢索特征詞向量與每個類特征向量的相似度；

Step4：對Step3所得到的結果進行排序，獲得刻面i下相似度較高的前m個類；

Step5：采用式(2),計算檢索特征詞向量與刻面i下前m個類中每個構件的相似度值Sij；

Step6：對Sij進行排序，獲取刻面i下相似度較高的前P個構件；

Step7：i++；轉向Step3，直至i>刻面數(shù)；

Step8：對每個刻面下所取得的前P個構件求交集，獲取與檢索向量較高的構件集；

Step9：采用式(3)，求得檢索向量與所得的構件集中的最終相似度值；

Step10：排序，獲取最終相似度較高的前N個構件，返回。

3 實驗結果及分析

文中基于Matlab7仿真平臺和Eclipse開發(fā)環(huán)境對算法進行了實現(xiàn)；同時與沒有引入分級策略的構件檢

索方法進行比較，來驗證基于分級策略和構件聚類索引樹的檢索方法的有效性。

實驗數(shù)據(jù)來自于上海構件庫的構件數(shù)據(jù)，它包含了六個主題：加密解密(142個)、文本處理(213個)、編譯器(279個)、圖像處理(362個)以及數(shù)據(jù)轉換(42個)和防火墻(102個)；并采用刻面分類與全文檢索相結合的方法描述構件。其中,分級策略中為刻面層上各個節(jié)點權重值的設定是通過多次實驗并結合用戶的關注點(通常，用戶比較關心構件的功能刻面)來獲取的，這5個刻面的分級權重值分別為：α1=0.423，α2=0.218，α3=0.097，α4=0.125，α5=0.137。

對于實驗結果的評價采用查準率和查全率兩個指標，其定義如下：

查準率=(Ns+Na)/M

(4)

查全率=(Ns+Na)/N

(5)

式中：Ns表示構件檢索結果中相似的構件數(shù)量；Na表示構件檢索結果中正確的構件數(shù)量；M表示構件檢索結果的構件總數(shù)量；N表示構件庫中所有相似構件的總數(shù)量。

表1給出了三組數(shù)據(jù)情況下兩種算法的查全率和查準率。圖3給出了兩種方法下查準率和查全率的折線對比圖。

圖3 實驗結果對比

表1 實驗結果

從表1的三組實驗結果可以看出，基于分級策略和聚類索引樹的構件檢索方法其查全率均達到了80%以上，查準率也基本在80%左右，與無分級策略的構件檢索方法相比，文中方法提高了構件檢索的查全率和查準率，即提高了檢索質(zhì)量，從而驗證了該算法的有效性。同時，通過圖3中兩種方法查全率和查準率的折線對比，可以看出隨著數(shù)據(jù)量的不斷增加，文中算法基本處于平穩(wěn)的變化中，幅度在5%以內(nèi)；而無分級策略的構件檢索方法在第三組數(shù)據(jù)的測試中，查全率和查準率均出現(xiàn)了急劇的降低趨勢，降低幅度達到了10%，從而表明了文中算法是較為穩(wěn)定的。

4 結束語

文中為克服刻面分類所存在的主觀因素，采用了基于刻面分類與全文檢索相結合的構件表示方法以及分級策略，提出了一種基于分級策略和聚類索引樹的構件檢索方法。該方法具有較高的構件查全率和查準率，而且具有穩(wěn)定性，可以避免刻面分類的主觀性，便于普通用戶的查詢。但是，該構件檢索方法依賴于語義分析技術的發(fā)展，因此，將會在不斷發(fā)展的語義分析技術的基礎上，對基于語義的構件檢索進一步進行改進和完善，進而更好地滿足用戶的檢索需求。

[1] 王淵峰，張 涌，任洪敏，等.基于刻面描述的構件檢索[J].軟件學報,2002,13(8):1546-1551.

[2]MiliH,MiliF,MiliA.Reusingsoftware:issuesandresearchdirections[J].IEEETransactionsonSoftwareEngineering,1995,21(6):528-562.

[3]RineDC,SonnemannRM.Investmentsinreusablesoftware:astudyofsoftwarereuseinvestmentsuccessfactors[J].JournalofSystemandSoftware,1998,41(1):17-32.

[4] 楊芙清.軟件復用及相關技術[J].計算機科學,1999,26(5):1-4.

[5] 常繼傳,郭立峰,馬 黎.可復用軟件構件的表示和檢索[J].計算機科學,1999,26(5):45-49.

[6] 姚全珠，丁新村，冉占軍．基于XML的樹匹配構件檢索算法的研究與實現(xiàn)[J].計算機應用研究，2008,25(4)：1013-1015.

[7]EmmerichW,KavehN.Componenttechnologies:JavaBeans,COM,CORBA,RMI,EJBandtheCORBAcomponentmodel[C]//Procofthe24thinternationalconferenceonsoftwareengineering.[s.l.]:[s.n.],2002.

[8]MiliA,MiliR,MittermeirR.Storingandretrievingsoftwarecomponents:arefinementbasedsystem[C]//Procof16thICSE.[s.l.]:IEEEComputerSocietyPress,1994:91-100.

[9] 王希辰.可復用軟件構件的表示和檢索[J].計算機工程,2002,28(12):80-82.

[10] 付青華，林 寧，馮 惠，等．基于刻面分類的構件檢索系統(tǒng)的設計與實現(xiàn)[J]．計算機應用與軟件，2010,27(6)：57-59.

[11] 任姚鵬，陳立潮，張英俊，等．基于潛在語義分析的構件聚類改進方法[J]．計算機工程，2011,37(4)：67-69．

[12]XieBinhong,RenYaopeng,ZhangYingjun,etal.Researchontheclusteringalgorithmofcomponentbasedonthegradestrategy[C]//Procofinternationalconferenceoncomputerapplicationandsystemmodeling.[s.l.]:[s.n.],2010.

[13] 田曉珍，任姚鵬，王春紅．一種改進的構件聚類索引樹研究的研究[J]．現(xiàn)代計算機，2014(23):12-15．

[14] 張英俊，任姚鵬,陳立潮,等．基于語義相似度與優(yōu)化的構件聚類算法[J].計算機工程與設計,2010,31(11):2531-2535.

A Component Retrieval Method Based on Classified Policy and Cluster Index Tree

WANG Wen-xia

(Department of Computer Science and Technology,Yuncheng University, Yuncheng 044000,China)

In the component representation method based on faceted classification,the term-space needs human to build and maintain so as to have strong subjectivity.Therefore,a component representation method combined faceted classification with full-text retrieval has been adopted in this paper.Meanwhile,a component retrieval method based on classified policy and cluster index tree has been proposed.In this method,the component cluster index tree is built by use of a component clustering algorithm based on semantic similarity and optimization,and the reasonable weight factors are introduced for each facet.On the foundation of the real component library,the experiment shows that by the comparison of the component retrieval method without weigh factors,the component retrieval method proposed has higher precision ratio and recall ratio,and to some extent,achieves component semantic retrieval.

faceted classification；cluster analysis；semantic analysis；index tree；classified policy

2015-09-05

2015-12-10

時間：2016-03-22

國家自然科學基金資助項目(11241005)；山西省高等學校教學改革研究項目(J2012098)；運城學院教學改革研究項目(JG201418)

王文霞(1979-)，女，講師，碩士，研究方向為信息檢索、數(shù)據(jù)挖掘、算法分析與研究。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1522.102.html

TP311

A

1673-629X(2016)04-0110-04

10.3969/j.issn.1673-629X.2016.04.024