田 帥 汪海濤 姜 瑛 陳 星
(昆明理工大學(xué)信息工程與自動化學(xué)院 昆明 650500)
結(jié)合聚類分析與信息熵賦權(quán)的構(gòu)件選擇方法?
田 帥 汪海濤 姜 瑛 陳 星
(昆明理工大學(xué)信息工程與自動化學(xué)院 昆明 650500)
為解決多位專家從構(gòu)件庫系統(tǒng)檢索結(jié)果中選出最適合用戶需求的構(gòu)件這一問題,論文提出了一種結(jié)合聚類分析與信息熵賦權(quán)的構(gòu)件選擇方法。首先由業(yè)內(nèi)專家對系統(tǒng)自動檢索出的構(gòu)件進(jìn)行再次評估選擇,然后通過論文提出的構(gòu)件選擇方法給出一個綜合的構(gòu)件選擇結(jié)果,把系統(tǒng)自動檢索與人工經(jīng)驗(yàn)選擇結(jié)合起來,多角度全面地評估選擇構(gòu)件,以利于得到最優(yōu)和最適合用戶需求的構(gòu)件。該方法不但結(jié)合了專家們對用戶需求及構(gòu)件的整體把握,更通過科學(xué)有效的方法計(jì)算選出最優(yōu)構(gòu)件,選出的構(gòu)件能更好地發(fā)揮軟件復(fù)用的優(yōu)勢。并給出了一個實(shí)例,通過實(shí)驗(yàn)對該構(gòu)件選擇方法進(jìn)行了分析說明,為進(jìn)一步的研究工作奠定了基礎(chǔ)。
構(gòu)件選擇;最優(yōu)選擇;聚類分析;信息熵;賦權(quán)
1968年,Mcllroy在北大西洋公約組織(NATO)會議上提交的《大量生產(chǎn)的軟件構(gòu)件》一文中,首次提出了軟件復(fù)用和構(gòu)件庫概念。至此構(gòu)件開發(fā)思想便應(yīng)運(yùn)而生。隨著時間的推移,涌現(xiàn)出大量的構(gòu)件評估方式和方法,可復(fù)用構(gòu)件的規(guī)模也不斷擴(kuò)大,由此構(gòu)件的分類檢索便成為一個亟待解決的問題?;诖耍瑖鴥?nèi)外專家結(jié)合現(xiàn)有的知識理論,構(gòu)建了各種分類及檢索模型[1],如基于刻面分類的檢索、基于關(guān)鍵詞的分類檢索等等,隨著互聯(lián)網(wǎng)大數(shù)據(jù)時代的到來,數(shù)據(jù)信息量急劇增長,在這個大環(huán)境背景下構(gòu)件的開發(fā)及復(fù)用也獲得了前所未有的發(fā)展,并且構(gòu)件開發(fā)技術(shù)愈發(fā)純熟,可信度明顯提高,分類及檢索方法顯著改善,軟件開發(fā)人員在選擇構(gòu)件時也有了更多的余地,目前大部分評估分類模型的重點(diǎn)為:
1)構(gòu)件檢索中,大部分只關(guān)注提高檢索的效率——查全率跟查準(zhǔn)率。
2)構(gòu)件選擇中,大部分關(guān)注點(diǎn)在選擇的標(biāo)準(zhǔn)計(jì)算上,如可信構(gòu)件的選擇[2],然后根據(jù)相應(yīng)標(biāo)準(zhǔn)進(jìn)行構(gòu)件選擇[3]。
然而在大量的實(shí)際工作應(yīng)用中發(fā)現(xiàn),經(jīng)過檢索后大于閾值的構(gòu)件往往不止一個,此時有太多選擇往往會導(dǎo)致效率低下,并且我們不能僅依賴匹配度去決定一個構(gòu)件的使用與否,檢索到的構(gòu)件往往是局部最優(yōu)構(gòu)件,此構(gòu)件只對所需功能提供較為完美的實(shí)現(xiàn),但對于整個系統(tǒng)卻不盡然,由于檢測出的構(gòu)件功能具有相似性,選出一個最優(yōu)構(gòu)件的理由可能會變得模棱兩可。此外不同的軟件開發(fā)人員由于專業(yè)知識背景的偏差,以及對所開發(fā)系統(tǒng)的了解程度不同,在選擇構(gòu)件時極有可能造成各執(zhí)己見的場景。全局最優(yōu)構(gòu)件直接關(guān)系到后期系統(tǒng)的開發(fā)的進(jìn)度和質(zhì)量,如果選擇的構(gòu)件與系統(tǒng)要求的切合度不高,不僅會導(dǎo)致后期修改工作量巨大,而且可能會推遲開發(fā)進(jìn)度,造成大量人力和財(cái)力的損失,使開發(fā)陷入困境導(dǎo)致項(xiàng)目失敗??紤]到現(xiàn)有的模型幾乎只關(guān)注構(gòu)件的評估、分類及檢索,對此問題帶來的嚴(yán)重危害沒有提出有效的解決方法。目前國內(nèi)外專家僅僅是對該問題可能會導(dǎo)致嚴(yán)重影響有過簡單概述,也并未提出一種得到廣泛認(rèn)可的有效處理辦法。文獻(xiàn)[4]提出了一種針對多構(gòu)件進(jìn)行評估和選擇的模型,但未給出一種詳細(xì)的選擇方法;文獻(xiàn)[5]提出了基于非線性模糊的質(zhì)量功能展開模型,建立一種基于NF-QFD的可復(fù)用選擇構(gòu)件模型,但此模型僅把滿足用戶的需求和系統(tǒng)的可維護(hù)性作為考慮的重點(diǎn),對于構(gòu)件的全局最優(yōu)與科學(xué)選擇閾值問題則未加考慮;文獻(xiàn)[6]提出的用法示例代碼的構(gòu)件選擇方法雖能幫助用戶去了解構(gòu)件的相關(guān)用法,但用戶對構(gòu)件的最終選擇仍具有相當(dāng)大的主觀性。
基于上述問題,本文提出了一種結(jié)合聚類分析與信息熵進(jìn)行賦權(quán)[7]的構(gòu)件選擇方法:選取多位專家對構(gòu)件庫系統(tǒng)檢索出的構(gòu)件進(jìn)行共同判斷決策,多位專家結(jié)合自己的專業(yè)背景知識,在對用戶需求進(jìn)行深入研究了解以后,對每個構(gòu)件做出評價并得出判斷矩陣,憑借每個專家的判斷矩陣獲得排序向量,使用相關(guān)系數(shù)法來構(gòu)造構(gòu)件相關(guān)矩陣,再對聚類閾值變化率進(jìn)行系統(tǒng)分析,從而選出最優(yōu)的聚類閾值,對相似程度較高的專家給出合理的聚類,并賦予類間權(quán)重(類內(nèi)權(quán)重、類間權(quán)重的概念在后文有相關(guān)詳細(xì)定義),數(shù)目相對較多的專家所聚得的類分配較大的權(quán)重;然后結(jié)合信息熵理論分別為類內(nèi)的專家分配權(quán)重,使得同類中認(rèn)識思維清晰、評價相對準(zhǔn)確的分配比較大的權(quán)重,最后結(jié)合類間權(quán)重和類內(nèi)權(quán)重來決定專家的總權(quán)重,并通過總權(quán)重與構(gòu)件排序向量計(jì)算得出最優(yōu)構(gòu)件,此構(gòu)件才是真正既符合局部需求,又滿足整體要求的構(gòu)件。
所謂聚類分析[8]是一組將研究對象經(jīng)過統(tǒng)計(jì)計(jì)算分為相對同質(zhì)群組的一種統(tǒng)計(jì)分析技術(shù),在聚類的過程中,我們不必給出一個確定分類的標(biāo)準(zhǔn),聚類分析能夠從樣本數(shù)據(jù)出發(fā),通過相關(guān)信息自動進(jìn)行分類,分得的同一個類對象有很大的相似性,不同類對象有較大的差異性。
2.2.1 1-9標(biāo)度法構(gòu)造構(gòu)件判斷矩陣
假設(shè)在某一準(zhǔn)則下第i個專家對n個功能相似的構(gòu)件進(jìn)行評價,根據(jù)1~9標(biāo)度法[9]做出構(gòu)件判斷矩陣:
2.2.2 層次分析法構(gòu)造構(gòu)件排序向量矩陣
通過層次分析法[10]中幾何平均法的使用對構(gòu)件的判斷矩陣Ai進(jìn)行一致性判斷、歸一化處理后求出其排序向量ui=(u1u2u3… un)T,其中:
則由m個專家組成的構(gòu)件排序向量矩陣為U:
2.2.3 相關(guān)系數(shù)法構(gòu)造相關(guān)矩陣
由于以上所做分析都是基于相同的量綱,因此所得構(gòu)件矩陣為標(biāo)準(zhǔn)化矩陣。
接下來確定ui=(u1iu2iu3i… uni)T與uj=(u1ju2ju3j… unj)T之間的相似程度rij,
根據(jù)皮爾森相關(guān)系數(shù)法求得rij:
由此便可構(gòu)造一個構(gòu)件和構(gòu)件間比較的相關(guān)矩陣R:
2.2.4 基于變化率確定閾值的聚類分析
本文采用聚類分析中的直接聚類法,把R中除去對角線以外的元素?cái)?shù)據(jù)從大到小進(jìn)行排列,去除重復(fù)值得到:
假設(shè)聚類閾值為θ=θk∈[ ]0,1 ,當(dāng) rij>θk(i≠k)時,我們便認(rèn)定文ui與uj有高度相似特性,然后將它們劃分成同類。由此可以看出,聚類閾值θ的取值不同,分類結(jié)果可能會大相徑庭,而且θ越接近1,分類就越細(xì)。如果S1與S2為通過某一閾值θ得出的兩個類,若:
便認(rèn)定它們是具有相似性,將全部相似的類歸并成同類,最終獲得的分類便是聚類閥值為θk時的一種聚類結(jié)果,接下來通過變化率選取聚類閾值。
在現(xiàn)實(shí)的專家對構(gòu)件進(jìn)評價選取中,結(jié)果間可能有微小差別,也就是說從專家處獲得的構(gòu)件排序向量的類似程度也許較高,此時我們把閾值θ的變化率Ci來作為參考進(jìn)而確定最優(yōu)閾值:
公式中:i為θ由大到小聚類的次數(shù),ni和ni-1分別是第i次與第i-1次聚類的類數(shù)量,θi和θi-1是第i次與第i-1次的聚類閾值,如果:
我們就認(rèn)定第i次的聚類閾值為最優(yōu)閾值。
在實(shí)際的軟件選擇中,由于每位專家有不同的專業(yè)背景知識,不同的履歷及偏好,對系統(tǒng)的認(rèn)識深淺不一,他們的評價結(jié)果對評價對象的反映不同,因此我們科學(xué)地分配每個專家的權(quán)重是十分必要的,
現(xiàn)階段有兩方面的問題需要我們確定:第一是類間權(quán)重,類和類之間相比較得出的權(quán)重。主要反映每個分得的類里專家的數(shù)量,對于有較多專家的類,我們應(yīng)該給予較大權(quán)重;第二是類內(nèi)權(quán)重,即在某個類內(nèi),專家間相比較得出的權(quán)重。主要根據(jù)某個專家分析的邏輯性,清晰度,提供消息的準(zhǔn)確性來賦予權(quán)值,此時我們需要用信息熵的知識幫助我們更加準(zhǔn)確地確定類內(nèi)的權(quán)重。下面分別對類間權(quán)重及類內(nèi)權(quán)重提供計(jì)算方法。
如果m位專家被分成了t類(t<n),第i類中包含 φi(φi≤m)位專家,λi為類間權(quán)重,則有:
由此我們可以得出每個類的類間權(quán)重。
信息熵[11]一詞是C.E.香農(nóng)從熱力學(xué)里借用的,在熱力學(xué)中,熱熵用來呈現(xiàn)分子狀態(tài)的混亂水平,香農(nóng)把信息熵來描述信源的不確定度。對于給定的信源,信息熵應(yīng)該是一個相應(yīng)確定的值。在此我們把某位專家對所有可選構(gòu)件進(jìn)行評價后的構(gòu)件排序向量作為一個離散信源,則概率空間為
m個專家在既定準(zhǔn)則下對n個構(gòu)件進(jìn)行評價,第i位專家通過構(gòu)件排序向量計(jì)算出信息熵為(單位是BIT):
根據(jù)信息熵的表征,我們可以知道,計(jì)算出的某位專家的信息熵值越小,信息的不肯定度與隨機(jī)性就越小,信息確定性越大,表明該專家所做的評估更可信,應(yīng)該給予更大的權(quán)重。因此類內(nèi)權(quán)重可以用信息熵的大小進(jìn)行度量。
設(shè)Iik為第i類中第k位專家類內(nèi)權(quán)重,則:
此時n代表第i類內(nèi)專家的人數(shù),當(dāng)專家自成一類時,類內(nèi)權(quán)值定為1。
到現(xiàn)在,我們已經(jīng)求得了類間權(quán)重與類內(nèi)權(quán)重,接下來對類間權(quán)重λi,類內(nèi)權(quán)重Iik相乘,得到第k位專家的總權(quán)重 βk,由此可求出每位專家的總權(quán)重。
最后,結(jié)合每個專家的總權(quán)重和構(gòu)件排序向量得到最終的構(gòu)件排序向量P:
通過max(Pi)選出最優(yōu)構(gòu)件[12]矩陣。
本節(jié)給出一個構(gòu)件選擇的實(shí)際應(yīng)用案例,選擇對象為從上海構(gòu)件庫中選擇一個B/S端、java語言開發(fā)的商城系統(tǒng)中文章發(fā)布功能模塊。該模塊包括四個基本功能,查看已發(fā)表文章,發(fā)表新文章,修改已發(fā)表文章,刪除已發(fā)表文章。經(jīng)基于刻面檢索匹配查找后,大于閾值的構(gòu)件有四個,由低到高分別為83%、88%、89%、91%。此時四個構(gòu)件均能較為完善的實(shí)現(xiàn)本模塊功能,但匹配度為83%的構(gòu)件與其他三個構(gòu)件有明顯的架構(gòu)區(qū)別,該構(gòu)件運(yùn)用了java中的ssh框架和maven進(jìn)行管理,而其他三個基于spring mvc開發(fā)。于此,公司技術(shù)部門選出10位工程開發(fā)專家對四個構(gòu)件按匹配度由低到高編號進(jìn)行評價打分后進(jìn)行選擇,具體步驟如下:
由式(1)~(2)計(jì)算每個專家的構(gòu)件排序向量,則m個專家組成的構(gòu)件排序向量矩陣為U:
因?yàn)榇司仃囀窃谙嗤烤V和數(shù)量級下構(gòu)造,所以此構(gòu)件排序向量矩陣為標(biāo)準(zhǔn)化矩陣,接了來求相關(guān)程度rij。根據(jù)式(3)我們可以求得某兩位專家構(gòu)造的構(gòu)件排序向量的相關(guān)程度,從而構(gòu)造出形如(5)的相關(guān)矩陣R:
根據(jù)式(6)遍歷θ值并進(jìn)行聚類,聚類結(jié)果如圖1~2所示,圖1為凝聚計(jì)劃圖,圖2為聚類譜系圖。
根據(jù)式(7)可求得每次聚類的變化率:
圖1 凝聚計(jì)劃圖
當(dāng)Ci無解、每個專家自成一類或者全部分為一類時沒有實(shí)際意義,所以剔除C4、C8。根據(jù)式(8)可求得C3為最大值,此時θ=0.996683,為最優(yōu)閾值,θ取此值時,所得聚類為
由此我們便可知分為6類最佳,按上述聚類順序分別標(biāo)為
根據(jù)式(9)可算出類間權(quán)重,分別為t1=0.2,t2=0.2,t3=0.45,t4=0.05,t5=0.05,t6=0.05。
通過式(11)可計(jì)算出各個專家信息熵值,其信息熵值向量表示為
根據(jù)式(12)可計(jì)算出每位專家的類內(nèi)權(quán)重,向量表示為
根據(jù)式(13)計(jì)算出每位專家的總權(quán)重,向量表示為
最后,結(jié)合類位專家的總權(quán)重與構(gòu)件排序向量,根據(jù)式(14)得出最終的構(gòu)件排序向量P:
P1=max(Pi),據(jù)此我們便能得出,構(gòu)件1為最優(yōu)構(gòu)件,由上述匹配度我們得知,構(gòu)件1的匹配度相對最低,然而專家中大多數(shù)對此構(gòu)件更加青睞,于是該公司最終選擇構(gòu)件1。后期開發(fā)中,基于SSH框架開發(fā)的此構(gòu)件不但簡化了開發(fā)中業(yè)務(wù)邏輯處理與數(shù)據(jù)交互的流程,后期客戶又增加的其他功能的編譯、依賴問題,maven也能輕松應(yīng)對,大大節(jié)省了開發(fā)周期,并避免了不必要的邏輯錯誤。而如果僅僅按照匹配度選擇構(gòu)件4,則后期必定會出現(xiàn)二次開發(fā)的問題。所以,我們可以說,經(jīng)過此方法選出的構(gòu)件,不但結(jié)合了專家組們對系統(tǒng)及構(gòu)件的整體把握,更通過科學(xué)有效方法計(jì)算出最優(yōu),選出的構(gòu)件能更好地發(fā)揮軟件復(fù)用的優(yōu)勢。
本文通過對在構(gòu)件庫中檢索出匹配度大于閾值的構(gòu)件后,從檢索結(jié)果里再次選擇最優(yōu)構(gòu)件的研究,提出在實(shí)際應(yīng)用中出現(xiàn)且必須面對的問題,即如何從構(gòu)件庫系統(tǒng)自動檢索結(jié)果中選出最適合用戶需求的構(gòu)件,并給出結(jié)合聚類分析與信息熵進(jìn)行賦權(quán)的一種構(gòu)件選擇方法,此方法不但結(jié)合了每位專家的能力水平、經(jīng)驗(yàn)、客觀準(zhǔn)確性以及對系統(tǒng)的整體把握等因素,而且結(jié)合聚類分析和信息熵理論,達(dá)到選出最佳構(gòu)件的目的。接下來的研究重點(diǎn)在:如何挑選更專業(yè)的專家進(jìn)行構(gòu)件評價及選擇;如何引入其他知識和算法更加科學(xué)合理地選擇出最佳構(gòu)件;由于構(gòu)件為外部人員開發(fā),使用構(gòu)件便會存在一定的風(fēng)險,如何在評估選擇構(gòu)件時加入風(fēng)險評估機(jī)制也是一個需要考慮的問題。
[1]汪海濤,劉帥,姜瑛,等.一種基于模糊物元評價法的構(gòu)件質(zhì)量度量模型研究[J].云南大學(xué)學(xué)報(自然科學(xué)版),2015,37(1):31-42.WANG Haitao,LIU Shuai,JIANG Ying,et al.Study on a component quality metrics model based on the fuzzy mat?ter-elenent evaluation method[J].Iournal of Yunnan Uni?versity,2015,37(1):31-42.
[2]Ding X L,Wang H M,Wang Y Y.Verification oriented trustworthiness evidence and trustworthiness evaluation of software[J].Journal of Frontiers of Computer Science and Technology,2010,4(1):46-48.
[3]Lang B,Liu X D,Wang H M,et al.A classification model for software trustworthiness[J].Journal of Frontiers of Computer Science and Technology,2010,4(3):231-239.
[4]盛津芳,王斌.基于FCD擴(kuò)展的多構(gòu)件選擇過程[J].計(jì)算機(jī)應(yīng)用,2007,27(4):860-863.SHENG Jinfang,WANG Bin.Multi-component Selection Process Based on FCD Extension[J].Journal of Computer Applications,2007,27(4):860-863.
[5]孫劍,徐瑩.基于NF-QFD的構(gòu)件選擇方法[J].高師理科學(xué)刊,2013,33(5):24-28.SUN Jian,XU Ying.Component selection method based on NF-QFD[J].Science Journal of Higher Education,2013,33(5):24-28.
[6]楊秀榮,任姚鵬.一種基于用法示例的構(gòu)件選擇方法[J].運(yùn)城學(xué)院學(xué)報,2013(5):83-85.YANG Xiurong,REN Yaopeng.A component-based selec?tion method based on usage[J].Journal of Yuncheng Uni?versity,2013(5):83-85.
[7]傅祖蕓.信息論[M].第三版,北京:電子工業(yè)出版社,2011:132-212.FU Zuyun.Information Theory[M].Third Edition,Bei?jing:Publishing House of Electronics Industry,2011:132-212.
[8]Bolloju N.Aggregation of analytic hierarchy process mod?els based on similarities in decision makers'preferences[J].European Journal of Operational Research,2011,128(3):499-508.
[9]葛世倫.用1—9標(biāo)度法確定功能評價系數(shù)[J].價值工程,1989(1):33-34.GE Shilun.With 1-9 scale method to determine the func?tion evaluation coefficient[J].Value Engineering,1989(1):33-34.
[10]向東進(jìn).實(shí)用多元統(tǒng)計(jì)分析[M].武漢:中國地質(zhì)大學(xué)出版社,2005:232-256.XIANG Dongjin.Practical multivariate statistical analysis[M].Wuhan:China University of Geosciences Press,2005:232-256.
[11]陳云翔,董驍雄,項(xiàng)華春,等.基于信息熵的群組聚類組合賦權(quán)法[J].中國管理科學(xué),2015,23(6):142-146.CHEN Yunxiang,DONG Xiongxiong,XIANG Huachun,et al.Composition Entropy Weighting Method Based on Information Entropy[J].Chinese Journal of Management Science,2015,23(6):142-146.
[12]楊芙清,梅宏.構(gòu)件化軟件設(shè)計(jì)與實(shí)現(xiàn)[M].北京:清華大學(xué)出版社,2008:86-145.YANG Fuqing,MEI Hong.Component-based software design and implementation[M].Beijing:Tsinghua Uni?versity Press,2008:86-145.
A New Software Component Selection Method Based on Clustering and Information Entropy Weighting
TIAN ShuaiWANG HaitaoJIANG YingCHEN Xing
(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500)
In order to solve the problem of selecting the most suitable components which meet the needs of users from the search results of component library system by experts,this paper proposes a component selection method based on clustering and in?formation entropy weighting.Firstly,industry experts evaluate and select components again from which automatically retrieved by the system,then the component selection method which proposed in this paper gives a comprehensive component selection result,combining the system automatic retrievals with artificial experience choice,comprehensively evaluating and selecting components from multi-angle so as to select the most optimal and appropriate components to meet the users'needs.This method not only com?bines the overall grasp of the experts on the needs of users and components,but also computes and selects the optimal components through scientific and effective method,so that the selected components can better play to the advantages of software reuse.And this paper also gives an example to analyze and explain the components selection method by the way of experiments,which lays the foun?dation for the further research.Research work in this paper has some theoretical research value and practical significance.
component selection,optimal choice,clustering analys,information entropy,weighting
Class Number TP18
TP18
10.3969/j.issn.1672-9722.2017.12.024
2017年6月6日,
2017年7月7日
國家自然科學(xué)基金項(xiàng)目(編號:61462049)資助。
田帥,男,碩士研究生,研究方向:軟件工程。汪海濤,女,副教授,碩士生導(dǎo)師,研究方向:軟件工程。姜瑛,女,博士,教授,碩士生導(dǎo)師,研究方向:軟件工程。陳星,男,碩士,講師,研究方向:軟件工程。