袁中臣，馬宗民

1.東北大學 軟件學院，沈陽110819

2.沈陽工業(yè)大學 化工過程自動化學院，遼寧 遼陽111004

軟件重用能節(jié)省開發(fā)費用和時間。隨著軟件復雜性的增加，軟件重用開始出現(xiàn)在軟件生命周期的每個階段[1-2]。軟件設計發(fā)生在軟件生命周期的早期，對接下來的開發(fā)工作產(chǎn)生重要的影響。所以，軟件設計的重用受到關(guān)注[3]。UML（Unified Modeling Language）類圖由類和類之間的關(guān)系構(gòu)成，用于系統(tǒng)的靜態(tài)建模。UML類圖被廣泛應用于軟件設計，已成為軟件設計事實上的標準[4]。所以UML類圖重用成為軟件設計重用研究的重點[5-6]。隨著可重用的UML類圖數(shù)量的增加，分類成為一項基礎(chǔ)性工作。

服務于軟件重用的組件的分類在一些文獻中被提出[7-10]。這里的組件是指程序代碼、設計模型和規(guī)范等。所有提出的方法能被歸于同一類，即，通過預先定義的屬性（如開發(fā)平臺和功能等）去描述每個組件，組件被表示為一個屬性向量，向量差異（歐式或者余弦距離）用來度量組件相似性，然后應用分類算法實現(xiàn)組件的分類。

人為屬性的定義不能完全表達一個UML類圖的語義，并且屬性的定義需要領(lǐng)域知識的支持。相似性度量是進行分類的重要一步，現(xiàn)有關(guān)于相似性度量的研究主要集中在語義[11-16]。文獻[11]結(jié)合領(lǐng)域本體和應用本體計算類圖之間的語義相似性，以增加準確性。文獻[11]和[16]在匹配中考慮了關(guān)系的特征。文獻[13]提出類圖的相似性分為淺層（命名）相似性和深層（語義）相似性，并使用鄰居類的信息實現(xiàn)關(guān)系的相似性度量。在文獻[14]中，除去類之外，還將屬性和操作列入語義度量范疇。所有以上這些方法都考慮到概念名稱，并應用了本體的概念語義相似性。在語義相似性度量中，除了概念語義之外，還包括屬性（操作）類型和訪問權(quán)限等限制。即使是相同類的相同屬性在不同項目中也可能被定義成不同的類型。如類“Student”的學號屬性“num”在不同項目中可能被定義為“integer”和“String”兩個不同的類型。而這些差別在接下來的編碼階段會體現(xiàn)出更多的差異。所以，本文定義的語義相似性度量將把這些因素考慮在內(nèi)。

在UML類圖中，把每個關(guān)系稱為一個語義單元，即R=[端點類1，關(guān)系類型，端點類2]，語義單元之間的相似性計算從端點類和關(guān)系類型進行。類圖之間的語義相似性即為所有語義單元的相似性均值。同時，在進行類的相似性度量時，除了考慮概念語義名稱，把屬性、操作及其類型和訪問限制等也考慮在內(nèi)。類圖之間的語義相似性被定義如下：

分類在很多領(lǐng)域得到應用，如模式識別和機器學習等[17]。很多分類算法被提出，如決策樹（DT）、遺傳算法（GA）、邏輯回歸（LR）、支持向量機（SVM）、K臨近（KNN）和樸素貝葉斯（NB）等。除了這些單個的分類算法還出現(xiàn)了集成分類算法[18]，如隨機森林等。由于集成分類能夠克服單個分類算法的缺點，本文構(gòu)建了一個基于KNN的二級分類的集成分類器E-KNN。這里實現(xiàn)的是單標簽分類，即，一個UML類圖僅能被分類到唯一的類別目錄。

本文正是從語義方面提出對UML類圖的分類。定義了類圖之間的語義相似性度量，提出算法獲取中心類圖，基于中心類圖和改進的KNN算法分別構(gòu)建E1-KNN和E2-KNN分類器，并組成二級集成分類器E-KNN。實驗驗證了所構(gòu)建分類器的有效性。

1 語義相似性度量

現(xiàn)有的基于本體的概念語義相似性計算分為兩種方法：語義距離和包含內(nèi)容[19]。本文選擇被廣泛使用的基于路徑的語義距離來計算概念之間的語義相似性，表示如下：

c1和c2分別表示兩個概念，lso(c1,c2)表示概念c1和c2在本體（如WordNet）層級結(jié)構(gòu)中的最低公共祖先；len(c1,c2)表示概念c1和c2的最短路徑；depth(c)標識概念c在本體層級結(jié)構(gòu)中的深度。

cd1和cd2是兩個類圖，|cd i|表示類圖cd i中包含的關(guān)系的數(shù)目。類Ci來自類圖cd1,A i和O i分別是類Ci的屬性集合和操作集合，|A i|和|O i|分別表示包含屬性和操作的數(shù)目。同理，類C j來自類圖cd2,A j和O j分別是類C j的屬性集合和操作集合。SimC、SimR、SimA和SimO分別表示類相似性、關(guān)系相似性、屬性相似性和操作相似性。λ、α、β(β1,β2,β3)、γ(γ1,γ2,γ3,γ4)是權(quán)重因子。Root(c)標識一個概念名稱c的詞根，因為在屬性和操作的表達中經(jīng)常包含很多縮寫，如屬性“ID”實際上表示的是“i dentity”。SimT標識類型（返回值類型）相似性；SimP標識訪問權(quán)限相似性。操作有時還包含參數(shù)，并且參數(shù)的定義和屬性是一致的，所以參數(shù)的相似性度量(SimQ)采取和屬性相同的度量方法。

考慮到建模相同項目可能會出現(xiàn)異構(gòu)的類圖，關(guān)系相似性度量SimR被總結(jié)為三種情況。當被匹配的兩個關(guān)系類型相同時，相似性值為SimR=1.0；當匹配的兩個關(guān)系類型不同時，引入文獻[13]的關(guān)系相似性矩陣SM R獲取相似性值。對于第三種情況，當一個關(guān)系被匹配到UML類圖中的一條路徑而不是一個關(guān)系時，定義公式來標識相似性。R i標識路徑上每個關(guān)系的類型，n表示關(guān)系路徑的長度。

為了度量屬性（操作）訪問權(quán)限和類型的相似性值，通過邀請軟件工程領(lǐng)域?qū)＜乙栽L問權(quán)限的限定范圍差異和類型之間的轉(zhuǎn)換復雜度為基準分別給出相似性值的評分，如表1和表2所示。

表1 訪問權(quán)限相似性

表2 類型相似性

在表2中，U表示兩個類的相似性。如果匹配的兩個類是相同或者存在繼承關(guān)系，則U=1，否則U=0。這種相似性度量經(jīng)常會出現(xiàn)在一些“依賴”關(guān)系的類圖匹配中。

2 集成分類

2.1 中心類圖

每個類別的類圖都表現(xiàn)出相似或者相同的特征，找出這些特征是分類的首要一步。這里定義中心類圖標識每個類別目錄中類圖的特征。

定義1中心類圖在目錄C i中，如果類圖cd j和所有其他類圖之間的平均相似性值高于其他類圖，則cd j被稱為中心類圖。

取一組中心類圖來表示一個目錄的特征。接下來的問題變成了如何去獲取中心類圖集合，這里提出一個行最大值捕捉的算法。假定一個目錄Ci中包含的類圖的數(shù)量是n，那么就會存在一個n×n階相似性矩陣SM,SMij表示類圖cd i和cd j之間的相似性值。行最大值捕捉算法被描述為算法1，描述如下：

算法1獲取目錄中心類圖集合

輸入：相似性矩陣SM和中心類圖數(shù)目center Num

輸出：中心類圖集合center CDs

其中，中心類圖集合centerCDs初始化為空。計算SM每一行的平均值(row SimAVG)，從中找到最大值，該行對應的類圖即為一個中心類圖cd p，如果中心類圖集centerCDs中不存在cd p（有時候目錄中會出現(xiàn)兩個完全相同的類圖），則插入，然后從SM中刪除這個類圖對應的行和列，繼續(xù)在SM中查找下一個中心類圖，直到找到指定數(shù)目center Num為止。

假定一個目錄的類圖數(shù)量為n1，則獲取目錄中類圖的相似性矩陣的時間復雜度為；要尋找中心類圖數(shù)量為m1，則在目錄中查找特征類圖的復雜度是O(m1×n1)。所以，總的時間復雜度為

2.2 分類流程

本文構(gòu)建了一個2級分類的集成分類器E-KNN，如圖1所示。

圖1 集成分類器E-KNN

分類過程分為兩個階段。UML類圖首先進入分類器E1-KNN進行初級分類，產(chǎn)生可能分類的目錄。然后，由分類器E2-KNN決定最終分類目錄。很多情況下，分類結(jié)果也能由E1-KNN直接決定，而不需要進入E2-KNN。E1-KNN和E2-KNN都是基于KNN算法。在KNN中，所有樣例參與相似性計算，所以存在分類效率低問題[20]。同時，K的設置和樣例分布也影響分類的準確性。這些問題需要在E-KNN中考慮。

2.2.1 E1-KNN分類器

E1-KNN的分類計算是基于中心類圖集合，而不是所有訓練樣例，相似性計算次數(shù)明顯減少。E1-KNN分類器的分類可能產(chǎn)生3種結(jié)果：

（1）類圖不能被分類到現(xiàn)有的目錄。

（2）類圖被分類到一個確定的目錄。

（3）輸出初級分類目錄。

針對結(jié)果（1），標記不屬于現(xiàn)有分類目錄為C0。當在最高的的K個相似性中，屬于分類目錄的平均相似性值μ＜μ0時，類圖不能被分類到現(xiàn)有目錄，即分類到C0，分類過程終止。

針對結(jié)果（2），這里規(guī)定，當在最高的K個相似性值中屬于分類目錄的類圖的數(shù)量w≥w0，分類目錄確定，分類結(jié)束。

表3 訓練樣例的特征

參數(shù)μ0和w0能通過訓練獲得，訓練過程如下：

步驟1獲取目錄中心類圖集合，將所有訓練樣例分為中心類圖(m)和測試類圖(n-m)兩個集合。

步驟2計算每個測試類圖和每個中心類圖的相似性，并基于KNN進行分類。

步驟3計算每個測試類圖的μ和w。

步驟4統(tǒng)計所有測試類圖正確分類的比率λ1，如果λ1＜λ0(λ0為預先設定，一般λ0≥0.90)，重新設定每個目錄中心類圖的數(shù)量（如m0=m0+1），并返回步驟1。否則，獲得

訓練參數(shù)的時間復雜度為O(r×m×(n-m)),r為迭代次數(shù)，一般在3～7次可以完成參數(shù)訓練。

針對結(jié)果（3），取最高的平均相似性值對應的目錄（通常不會超過3個）作為分類器E1-KNN的輸出。

E1-KNN的具體分類流程如圖2所示。

圖2 E1-KNN分類流程

在E1-KNN中，類圖被分類到現(xiàn)有目錄的必要條件是分類目錄唯一，充分條件是μx≥μ0和w x≥w0。同時，C0的標識可以為將來擴展未知類別類圖的分類提供支持。

2.2.2 E2-KNN分類器

E2-KNN分類計算是基于E1-KNN輸出目錄的樣例而不是所有樣例，所以效率明顯提高。同時，在處理K（高于E1-KNN中的K值）個最高相似性值中屬于不同目錄的類圖數(shù)量相等的問題時，針對訓練數(shù)據(jù)分布情況分別給出解決方案。

（1）K+X。即，擴大K的范圍，然后獲取分類目錄。通常，X=K/2。這種解決方案的前提是不同目錄的樣例分布均勻。

（2）目錄平均值。分別統(tǒng)計屬于不同目錄的樣例對應的相似性平均值μ，類圖被分類到平均值高的對應的目錄，此方案適用于樣例分布不均勻的情況。

E2-KNN主要針對建模交叉領(lǐng)域項目的類圖的分類。這些項目的類圖包含來自不同領(lǐng)域的語義信息，經(jīng)常不能通過基于有限的中心類圖的分類器E1-KNN給出確定的分類目錄。

3 實驗結(jié)果分析

3.1 實驗數(shù)據(jù)

實驗中使用的UML類圖來自Google（Searchcode）的Java代碼的反向工程[21]。訓練樣例分為五個領(lǐng)域，分別為教育(C1)、醫(yī)療(C2)、金融(C3)、房地產(chǎn)(C4)和電子商務(C5)等。為了驗證樣例分布和尺寸均勻與否對分類的影響，樣例被分成4個組，每組500個，細節(jié)如表3所示。此外，200個類圖被用于測試，其中，20個測試樣例來自非上述領(lǐng)域(C0)。同時，包含交叉領(lǐng)域信息的類圖的數(shù)目也是20。使用Java語言實現(xiàn)了本文所提出的分類方法，并且在PC機（Win 10，Intel Core i7，RAM 8 GB）上執(zhí)行。語義相似性計算權(quán)重參數(shù)設置：λ=0.3,α=0.5,β=0.3,γ=0.2,β1=0.5,β2=0.3,β3=0.2,γ1=0.4,γ2=0.3,γ3=0.2,γ4=0.1。通過訓練獲得分類器E1-KNN中參數(shù)設置，如表4所示。

表4 參數(shù)設定

3.2 結(jié)果分析

分類質(zhì)量可以從準確率P、完成率R和二者調(diào)和平均值F三個指標來度量。這里設定A表示正確地分類的測試樣例的數(shù)量；B表示錯誤地分類的測試樣例的數(shù)量；C表示應該分類但是沒有分類的測試樣例數(shù)量。P、R和F公式為：

測試樣例在4個訓練樣例組上執(zhí)行分類獲得的分類質(zhì)量如圖3所示。

圖3 E-KNN分類質(zhì)量

可以看出，g1獲得分類質(zhì)量最高，g4最低，總體差別不大。無論哪個樣例組，分類的完成率要高于準確率。這是因為，經(jīng)過兩級分類不能最終決定分類目錄的樣例數(shù)量很少。

從分布上看，分類質(zhì)量受樣例分布的影響不大。如由g1和g3獲得的分類質(zhì)量差異很小，同樣的事情也發(fā)生在g2和g4上。這是因為，在E1-KNN中使用了中心類圖，而中心類圖在分布均勻和不均勻的樣例中的數(shù)量差異不大，這也屏蔽了分布差異對分類的影響；在E2-KNN中，提出的平均相似性的計算也避免了分類受分布影響的問題。

樣例尺寸差異還是使得分類質(zhì)量表現(xiàn)出不同，盡管不大。由均勻尺寸的訓練樣例獲得的分類質(zhì)量要高于不均勻尺寸獲得的分類質(zhì)量，如g1和g3分別高于g2和g4。這是因為，大尺寸的類圖就包含了更多的語義信息，而小尺寸的類圖包含的信息較少。當一個小尺寸的類圖進行分類時偶爾會被分類到錯誤的大尺寸類圖的目錄，特別是對于交叉領(lǐng)域的測試樣例。如測試樣例中關(guān)于“醫(yī)療學?！钡腢ML類圖，有時會被錯誤地分類到“醫(yī)療”領(lǐng)域，盡管它應該被分類到“教育”領(lǐng)域。

接下來，將上述集成分類（E-KNN）獲得的分類質(zhì)量（F值）和分別由一級（E1-KNN）和二級（E2-KNN）分類獲得的分類質(zhì)量進行對比，結(jié)果如圖4所示。

可以看出，由E-KNN獲得的分類質(zhì)量明顯高于僅由分類器E1-KNN和E2-KNN獲得的分類質(zhì)量。E1-KNN在分類交叉領(lǐng)域類圖時有時不能決定最終目錄，而E2-KNN不能處理C0的問題，且受訓練樣例分布影響較大。由E1-KNN和E2-KNN結(jié)合組成的E-KNN恰好有效地解決了這些問題。

圖4 一級和二級分類質(zhì)量對比

最后，將獲得的分類質(zhì)量（F值）和（平均）效率與由常用分類算法KNN、NB、LR、SVM、EN（KNN（4）和NB（3））獲得的結(jié)果比較。因為LR和SVM被用于二分類，這里訓練樣例為5個類別目錄，所以，分別訓練了5個分類器（一對多）實現(xiàn)多分類，以函數(shù)值決定分類目錄。分類器EN是分別由基分類器KNN和NB構(gòu)成的集成分類器，分類結(jié)果通過舉手表決。中心類圖中的類組成NB、LR和SVM的特征。所有分類方法均使用提出的相似性度量。分類質(zhì)量和效率比較如圖5和圖6所示。

圖5 分類質(zhì)量比較

圖6 分類效率比較

從分類質(zhì)量上看，幾種分類器在樣例組g1獲得的分類質(zhì)量最高，而由樣例組g4獲得的分類質(zhì)量最低。提出的分類方法獲得的分類質(zhì)量要優(yōu)于其他分類器。同時，也能看到，單分類器的分類質(zhì)量受到分布的影響。集成分類器EN的分類質(zhì)量要優(yōu)于單分類器。在單分類器中，KNN分類質(zhì)量最高。從分類效率上看，提出分類器的分類效率要優(yōu)于其他幾種分類器，尤其是KNN分類效率最低，每次分類都需要大量的相似性計算。中心類圖的引入減少了大量的計算。同時，兩級分類使得很多測試樣例的分類直接由分類器E1-KNN給出結(jié)果，而沒有進入分類器E2-KNN。所以，無論從分類質(zhì)量還是從分類效率上比較，本文提出的分類方法都要優(yōu)于其他分類器。

4 結(jié)束語

本文以UML類圖的重用為背景，從語義上提出UML類圖的分類。定義了類圖的語義相似性，提出算法獲取中心類圖標識目錄特征，基于改進的KNN分別構(gòu)建了E1-KNN和E2-KNN，并組建了集成分類器E-KNN。實驗結(jié)果表明，本文提出的兩級集成分類器解決了其他分類器受計算量影響而產(chǎn)生的效率問題，也解決了受分布和尺寸影響而產(chǎn)生的分類質(zhì)量問題，和其他幾種分類器相比具有顯著優(yōu)勢。在接下來的工作中，嘗試結(jié)合其他算法提高效率是一個主要方向。此外，將語義分類和結(jié)構(gòu)分類相結(jié)合以實現(xiàn)類圖的混合分類是另一個將要開展的工作。