基于分級(jí)策略和聚類索引樹(shù)的構(gòu)件檢索方法

王文霞

(運(yùn)城學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，山西 運(yùn)城 044000)

基于分級(jí)策略和聚類索引樹(shù)的構(gòu)件檢索方法

王文霞

(運(yùn)城學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，山西 運(yùn)城 044000)

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

刻面分類；聚類分析；語(yǔ)義分析；索引樹(shù)；分級(jí)策略

0 引 言

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

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

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

1 相關(guān)概念

1.1 構(gòu)件的分類表示

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

圖1 構(gòu)件分類表示

1.2 構(gòu)件聚類索引樹(shù)

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

(1)有且僅有一個(gè)根節(jié)點(diǎn)(root)，代表構(gòu)件庫(kù)中的所有構(gòu)件。

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

(3)葉節(jié)點(diǎn)中包含著指向某個(gè)具體構(gòu)件的指針。

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

圖2 構(gòu)件聚類索引樹(shù)

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

2 構(gòu)件檢索方法

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

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

(1)

式中：WDk表示特征詞k在檢索文本中的權(quán)重值；WDik表示特征詞k在第i個(gè)類文本中的權(quán)重值。

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

Sij=αi(Sim+Smj)

(2)

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

(3)

基于分級(jí)策略的構(gòu)件檢索算法如下：

輸入：所要檢索的構(gòu)件文本；

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

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

Step2：i=1；

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

Step4：對(duì)Step3所得到的結(jié)果進(jìn)行排序，獲得刻面i下相似度較高的前m個(gè)類；

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

Step6：對(duì)Sij進(jìn)行排序，獲取刻面i下相似度較高的前P個(gè)構(gòu)件；

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

Step8：對(duì)每個(gè)刻面下所取得的前P個(gè)構(gòu)件求交集，獲取與檢索向量較高的構(gòu)件集；

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

Step10：排序，獲取最終相似度較高的前N個(gè)構(gòu)件，返回。

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

文中基于Matlab7仿真平臺(tái)和Eclipse開(kāi)發(fā)環(huán)境對(duì)算法進(jìn)行了實(shí)現(xiàn)；同時(shí)與沒(méi)有引入分級(jí)策略的構(gòu)件檢

索方法進(jìn)行比較，來(lái)驗(yàn)證基于分級(jí)策略和構(gòu)件聚類索引樹(shù)的檢索方法的有效性。

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

對(duì)于實(shí)驗(yàn)結(jié)果的評(píng)價(jià)采用查準(zhǔn)率和查全率兩個(gè)指標(biāo)，其定義如下：

查準(zhǔn)率=(Ns+Na)/M

(4)

查全率=(Ns+Na)/N

(5)

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

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

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

表1 實(shí)驗(yàn)結(jié)果

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

4 結(jié)束語(yǔ)

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

[1] 王淵峰，張 涌，任洪敏，等.基于刻面描述的構(gòu)件檢索[J].軟件學(xué)報(bào),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] 楊芙清.軟件復(fù)用及相關(guān)技術(shù)[J].計(jì)算機(jī)科學(xué),1999,26(5):1-4.

[5] 常繼傳,郭立峰,馬 黎.可復(fù)用軟件構(gòu)件的表示和檢索[J].計(jì)算機(jī)科學(xué),1999,26(5):45-49.

[6] 姚全珠，丁新村，冉占軍．基于XML的樹(shù)匹配構(gòu)件檢索算法的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，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] 王希辰.可復(fù)用軟件構(gòu)件的表示和檢索[J].計(jì)算機(jī)工程,2002,28(12):80-82.

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

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

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

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

[14] 張英俊，任姚鵬,陳立潮,等．基于語(yǔ)義相似度與優(yōu)化的構(gòu)件聚類算法[J].計(jì)算機(jī)工程與設(shè)計(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

時(shí)間：2016-03-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(11241005)；山西省高等學(xué)校教學(xué)改革研究項(xiàng)目(J2012098)；運(yùn)城學(xué)院教學(xué)改革研究項(xiàng)目(JG201418)

王文霞(1979-)，女，講師，碩士，研究方向?yàn)樾畔z索、數(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