結(jié)合動(dòng)靜態(tài)分析實(shí)現(xiàn)架構(gòu)恢復(fù)的方法*

任 武

上海立信會(huì)計(jì)金融學(xué)院，上海 201620

1 引言

軟件架構(gòu)是系統(tǒng)設(shè)計(jì)、維護(hù)以及程序理解活動(dòng)的一項(xiàng)重要制品。對(duì)于大型遺留軟件系統(tǒng)而言，由于不斷的功能變遷和版本演化，原有的架構(gòu)文檔經(jīng)常缺乏必要的更新而變得過時(shí)。通過源代碼分析獲取系統(tǒng)的功能結(jié)構(gòu)成為程序理解的一種可靠來(lái)源[1-3]。在這種情況下，維護(hù)人員通常采用聚類的方法將系統(tǒng)劃分為更小和更易于控制的子系統(tǒng)，使得同一子系統(tǒng)中的對(duì)象比在不同子系統(tǒng)中的對(duì)象有更高的相似性，這種利用軟件聚類將程序元素作為組件結(jié)合在一起，是從底層源代碼中獲取高層結(jié)構(gòu)視圖的一項(xiàng)重要技術(shù)[4-6]。

傳統(tǒng)的聚類在軟件維護(hù)方面主要采用靜態(tài)分析技術(shù)。靜態(tài)技術(shù)使用的兩種主要信息類型是結(jié)構(gòu)（程序元素間依賴和繼承關(guān)系）和語(yǔ)義（代碼的注釋和標(biāo)識(shí)符）。使用靜態(tài)源代碼進(jìn)行軟件聚類的優(yōu)點(diǎn)是自動(dòng)化程度高，但局限性之一是靜態(tài)方法通常只使用程序元素的相似類型估算待聚類的程序元素之間的距離[7]。例如，僅使用從代碼注釋和標(biāo)識(shí)符提取的文本（詞法）的聚類方法[8-9]或者僅使用文件/類名稱[10-11]，或基于控制和數(shù)據(jù)流圖的依賴特征[12-14],條件是需要足夠的輸入來(lái)處理，且系統(tǒng)遵循“高內(nèi)聚、低耦合”的基本原則進(jìn)行良好設(shè)計(jì)[4]，以及代碼標(biāo)識(shí)符命名具有良好的質(zhì)量和規(guī)范等。另一方面，面向?qū)ο笙到y(tǒng)由于存在多態(tài)和動(dòng)態(tài)綁定等因素，使得在功能架構(gòu)的恢復(fù)中，需要考慮系統(tǒng)的運(yùn)行時(shí)特性。

為了理解行為系統(tǒng)屬性，動(dòng)態(tài)信息更具有相關(guān)性[15]。一些信息恢復(fù)方法使用單獨(dú)的動(dòng)態(tài)信息[16-17]，動(dòng)態(tài)分析通過執(zhí)行特征獲取系統(tǒng)的運(yùn)行時(shí)事件。功能特征是構(gòu)成實(shí)現(xiàn)其組件實(shí)體的自然聚類，根據(jù)系統(tǒng)的不同的特征，將各個(gè)系統(tǒng)組件聚合在一起實(shí)現(xiàn)各自的特定功能，反映了軟件系統(tǒng)構(gòu)件化組裝的思想，因此基于特征的聚類恢復(fù)架構(gòu)方法是可行的。而實(shí)現(xiàn)基于特征的聚類，首先需要建立特征和代碼實(shí)體的對(duì)應(yīng)關(guān)系，動(dòng)態(tài)分析成為解決這個(gè)問題的一種可靠方式。但動(dòng)態(tài)分析也有其局限性：第一，動(dòng)態(tài)執(zhí)行跡通常所含事件數(shù)量巨大。第二，動(dòng)態(tài)架構(gòu)恢復(fù)需要功能全面且平衡的測(cè)試用例或場(chǎng)景集來(lái)支持。因此，動(dòng)態(tài)和靜態(tài)分析各有其優(yōu)缺點(diǎn)。作為解決這個(gè)問題的一種方法，Pollet等人[12]強(qiáng)調(diào)需要使用多個(gè)輸入源來(lái)實(shí)現(xiàn)架構(gòu)恢復(fù)。Scanniello等人[13]使用詞法和結(jié)構(gòu)如依賴和繼承信息來(lái)解決源代碼中的概念定位問題。Mancoridis等人[14]使用結(jié)構(gòu)和詞法文本特征來(lái)提取應(yīng)用程序的分層體系結(jié)構(gòu)。Greevy等人[18]介紹了一個(gè)基于動(dòng)態(tài)分析的特征驅(qū)動(dòng)的方法，通過提取跟蹤來(lái)獲取特征和軟件實(shí)體的明確映射關(guān)系。Eisenbarth等人[19]表明確定代碼對(duì)應(yīng)關(guān)系的可靠的方式是通過運(yùn)行相關(guān)的特征和分析收集的事件執(zhí)行跡。由于動(dòng)態(tài)分析的前提是設(shè)置與特征有關(guān)的用例并運(yùn)行，因此動(dòng)態(tài)分析收集的事件概念容易與特征建立起關(guān)聯(lián)。在動(dòng)態(tài)分析方面，已經(jīng)有大量的研究工作[15,20-26]，但多集中在特征定位和軟件模式[27-28]方面，將動(dòng)態(tài)分析應(yīng)用到聚類的架構(gòu)恢復(fù)方面的研究目前還比較欠缺。

在上述研究的基礎(chǔ)上，本文提出將靜態(tài)和動(dòng)態(tài)分析結(jié)合起來(lái)的分階段聚類方法，以軟件特征作為聚類標(biāo)準(zhǔn)來(lái)構(gòu)建系統(tǒng)的框架劃分。為提高動(dòng)態(tài)分析的效率，利用語(yǔ)義信息在數(shù)據(jù)處理方面的優(yōu)勢(shì)，將動(dòng)態(tài)獲取的“實(shí)體-特征”矩陣作為“詞項(xiàng)-文檔”矩陣處理。通過TF-IDF（term frequency-inverse document frequency）方式設(shè)置關(guān)鍵詞項(xiàng)權(quán)重值，創(chuàng)建潛在語(yǔ)義索引（latent semantic indexing，LSI）空間，計(jì)算SVD（singular value decomposition）近似值以替換完整的“詞項(xiàng)-文檔”矩陣。結(jié)合動(dòng)態(tài)跟蹤與靜態(tài)結(jié)構(gòu)分析，使用系統(tǒng)依賴信息進(jìn)行軟件聚類。雖然現(xiàn)有多種聚類方法[4-5]是半自動(dòng)的或自動(dòng)化的，但仍需要與維護(hù)人員相互作用的改進(jìn)反饋過程才能達(dá)到令人滿意的最終結(jié)果[15,22,29]。為此，利用代碼的靜態(tài)依賴圖，以及動(dòng)態(tài)調(diào)用圖，構(gòu)建完整的類依賴關(guān)系，反饋到特征和場(chǎng)景設(shè)計(jì)步驟，補(bǔ)充完善已建立的框架，以達(dá)到結(jié)構(gòu)恢復(fù)的目的。

2 相關(guān)工作

軟件聚類和系統(tǒng)結(jié)構(gòu)的恢復(fù)作為軟件領(lǐng)域的研究熱點(diǎn)，已經(jīng)有大量的研究工作：Mancoridis等人[4]提出一種優(yōu)化目標(biāo)函數(shù)的圖聚類方法，其目標(biāo)是找到高內(nèi)聚和低耦合模塊化聚類。Corazza等人[30]在源代碼中定義了類名稱、屬性名稱、方法名稱、參數(shù)名稱、注釋等不同區(qū)域，然后利用區(qū)域的權(quán)重計(jì)算源代碼類之間的相似關(guān)系并聚類。該方法主要是通過語(yǔ)義詞匯建立實(shí)體的關(guān)聯(lián)。Kuhn等人[8]描述了一種基于潛在語(yǔ)義索引的方法。該方法是獨(dú)立于語(yǔ)言的，并對(duì)具有相似術(shù)語(yǔ)的源代碼實(shí)體進(jìn)行分組。但沒有考慮建立代碼實(shí)體之間的對(duì)應(yīng)關(guān)系。Dugerdil[31]提出使用執(zhí)行跡作為抽樣數(shù)據(jù)的依據(jù)進(jìn)行逆向架構(gòu)的恢復(fù)過程，這與本文動(dòng)態(tài)分析方法相類似，但抽樣數(shù)量對(duì)實(shí)驗(yàn)結(jié)果影響較大，且缺乏較高層的抽象概念如特征或模式等作為聚類標(biāo)準(zhǔn)。Tzerpos等人[32]提出一種增量聚類算法模擬工程構(gòu)建子系統(tǒng)的模式，與本文基于特征實(shí)現(xiàn)方法不同，該算法是基于模式的抽象概念來(lái)構(gòu)建框架，在實(shí)現(xiàn)上依賴于前期初始條件的輸入。

3 基于特征的聚類方法

本文的結(jié)構(gòu)恢復(fù)方法的流程如圖1所示。主要分為兩個(gè)階段：第一階段，執(zhí)行特征場(chǎng)景獲取動(dòng)態(tài)事件執(zhí)行跡，利用k-means聚類建立系統(tǒng)的核心架構(gòu)；第二階段，根據(jù)收集到的執(zhí)行跡，分析特征執(zhí)行跡中的各個(gè)實(shí)體間的動(dòng)態(tài)依賴關(guān)系。將與特征相關(guān)的未執(zhí)行的代碼實(shí)體（如類或方法等），比較語(yǔ)義相似度，確定是否需要?dú)w類到對(duì)應(yīng)的簇中。通過迭代補(bǔ)充場(chǎng)景和特征的方式，逐步恢復(fù)已建立的框架結(jié)構(gòu)。

Fig.1 Structure recovery approach圖1 結(jié)構(gòu)恢復(fù)方法

3.1 生成特征-實(shí)體矩陣

通過分析系統(tǒng)的源代碼結(jié)構(gòu)、系統(tǒng)的需求文檔和在線幫助，調(diào)查相關(guān)應(yīng)用領(lǐng)域中的類似系統(tǒng)等方式，可以確定軟件系統(tǒng)的特征。選擇具有軟件特征的任務(wù)執(zhí)行方案的場(chǎng)景描述稱為特征的特定場(chǎng)景。通過執(zhí)行特定場(chǎng)景，可以快速地獲取特征和代碼的映射關(guān)系。例如，有一項(xiàng)任務(wù)，需要修改應(yīng)用程序的“print”功能，但是對(duì)于許多軟件系統(tǒng)來(lái)說，依靠研究源代碼很難發(fā)現(xiàn)所有與“print”特征相關(guān)的代碼部分，因?yàn)閷?shí)現(xiàn)一個(gè)特征可能涉及多個(gè)類或模塊。而通過設(shè)置程序的代碼插裝并執(zhí)行該特征，就可以分析執(zhí)行跡確定出代碼的哪些部分由該特征執(zhí)行，從而降低了定位任務(wù)的復(fù)雜性。在特征執(zhí)行時(shí)，會(huì)產(chǎn)生一系列運(yùn)行事件稱為執(zhí)行跡，事件包括對(duì)象的建立和刪除、方法的調(diào)用等。執(zhí)行跡中的實(shí)體，可以選擇不同的粒度來(lái)表示（如方法或類）。本文選擇類實(shí)體作為分析的對(duì)象，因?yàn)轭惖牧６容^大，通常一個(gè)類用一個(gè)源文件表示，類的行為特征通過類中各方法的調(diào)用和依賴等關(guān)系表現(xiàn)出來(lái)。

通過設(shè)置標(biāo)記插裝代碼和收集調(diào)用實(shí)體來(lái)獲取特征執(zhí)行跡，會(huì)產(chǎn)生一系列方法調(diào)用的entry/exit列表，為了使生成的大量的跟蹤數(shù)據(jù)易于分析，在預(yù)處理步驟中，通常移除由程序循環(huán)引起的所有冗余調(diào)用。對(duì)于在執(zhí)行跡中大量的與特征無(wú)關(guān)的公共實(shí)體，使用類似TF/IDF的方法對(duì)收集的實(shí)體設(shè)置權(quán)重值加以區(qū)別[33]。其中，詞項(xiàng)（term）用于對(duì)應(yīng)執(zhí)行跡中的調(diào)用實(shí)體，詞頻（frequency）是該實(shí)體調(diào)用的次數(shù)，文檔（document）對(duì)應(yīng)每條執(zhí)行跡，預(yù)處理用于獲取“詞項(xiàng)-文檔”矩陣和詞頻率-逆文檔頻率，每對(duì)（詞項(xiàng)，文檔）值設(shè)置如下的相關(guān)的權(quán)重：

3.2 構(gòu)建基本框架

通常使用聚類的非極端分布（non-extreme distribution,NED）值作為評(píng)價(jià)一個(gè)聚類算法質(zhì)量的指標(biāo)。一般評(píng)價(jià)認(rèn)為當(dāng)聚類數(shù)小于5或大于20屬于極端值，都是不合理的。NED值越大，表示非極端的聚類分布越好。

式（2）中，c是劃分C中的一個(gè)簇，|c|表示c的基數(shù)，N是所分析系統(tǒng)的軟件實(shí)體的數(shù)量，NED的值大小介于（0，1）之間，越接近于1表示聚類的實(shí)體分布越合理。根據(jù)NED的聚類分布要求，輸入是動(dòng)態(tài)產(chǎn)生的特征-實(shí)體文檔集，輸出是按NED最大的實(shí)體集劃分。

算法1劃分算法（partitioning algorithm）

在算法1中，第1～3句是計(jì)算“詞項(xiàng)-文檔”矩陣，根據(jù)式（1）求出TF-IDF值，基于LSI計(jì)算“詞項(xiàng)-文檔”轉(zhuǎn)置矩陣的相異度。第5～10句執(zhí)行k-means算法，迭代移動(dòng)各個(gè)簇的記錄的均值中心點(diǎn)，直到收斂，并比較NED值的大小，返回最大的NED函數(shù)值的劃分。

3.3 依賴性分析

分析源代碼程序控制流程圖，可以建立代碼實(shí)體之間的調(diào)用依賴關(guān)系，而數(shù)據(jù)流程圖則反映出系統(tǒng)的業(yè)務(wù)關(guān)系。

定義1（調(diào)用依賴性） 設(shè)場(chǎng)景中包含的特征以及調(diào)用序列構(gòu)成二維矩陣，R2?S×(M×M)，(si,p,q)∈R2,?p,q∈si&&p→q，表示在場(chǎng)景Si實(shí)體p一次或多次調(diào)用另一個(gè)實(shí)體q。

定義2（系統(tǒng)類之間依賴關(guān)系） 設(shè)C(s)是系統(tǒng)類的集合，R(C)表示類的依賴關(guān)系，結(jié)構(gòu)類的依賴性包括類的繼承、聚合和類的方法調(diào)用集合等，則實(shí)體p與實(shí)體q的結(jié)構(gòu)類的依賴性定義為：

根據(jù)定義1，在動(dòng)態(tài)調(diào)用的實(shí)體間進(jìn)行擴(kuò)展，構(gòu)建類的動(dòng)態(tài)依賴圖，靜態(tài)依賴圖則需要通過源代碼分析獲取。根據(jù)定義2，需要考慮在兩個(gè)類之間各種可能的關(guān)系，如方法調(diào)用、泛化關(guān)系、實(shí)現(xiàn)關(guān)系等。在具體分析中，不是考慮所有的實(shí)體類型，而是只考慮在執(zhí)行跡中出現(xiàn)的與特征相關(guān)的實(shí)體，查找其對(duì)應(yīng)的依賴圖。依賴圖分析檢查與特征相關(guān)的實(shí)體未被調(diào)用的情況，同時(shí)，也用于反饋到場(chǎng)景設(shè)計(jì)過程[34-37]。通過迭代補(bǔ)充相關(guān)的場(chǎng)景和特征，完善已經(jīng)建立的框架結(jié)構(gòu)。系統(tǒng)類依賴圖用節(jié)點(diǎn)和邊表示，節(jié)點(diǎn)代表類，邊代表依賴關(guān)系，示例如圖2所示。

Fig.2 Dynamic and static class dependency graph圖2 動(dòng)態(tài)和靜態(tài)的類依賴圖

在圖2中，左圖表示執(zhí)行跡特征feature1獲得的類的動(dòng)態(tài)依賴圖，右圖為通過靜態(tài)分析得到的依賴關(guān)系圖。假設(shè)所有的動(dòng)態(tài)依賴關(guān)系在靜態(tài)依賴圖中都有對(duì)應(yīng)。如在特征feature1中，如果存在動(dòng)態(tài)依賴，并且經(jīng)過靜態(tài)結(jié)構(gòu)分析，各相關(guān)的類均包含在特征中，那么表示對(duì)應(yīng)特征和場(chǎng)景已經(jīng)設(shè)置，不再進(jìn)一步分析。如果在特征feature1中，類之間存在靜態(tài)依賴關(guān)系，同時(shí)存在沒有被該特征動(dòng)態(tài)調(diào)用的類，那么對(duì)應(yīng)如下三種情況：（1）類C3依賴類C5，但類C5不在特征feature1范圍中，這表明在feature1的特征實(shí)現(xiàn)集中缺少類C5的可能性，建議準(zhǔn)備一個(gè)額外的場(chǎng)景來(lái)包含類C5的調(diào)用S=S∪{Snew}。（2）類C6依賴類C1，但類C6不在特征feature1范圍中。這表明被調(diào)用者可能是feature1的入口點(diǎn)，如果類C6未被分類到任何特征中，則可能存在當(dāng)前場(chǎng)景中缺失的新特征F=F∪{Fnew}。（3）類C2和類C4都在特征feature1中，但并沒有動(dòng)態(tài)依賴，表明需要建立一個(gè)新的場(chǎng)景來(lái)觸發(fā)其依賴關(guān)系。

可見，通過類依賴圖的分析，可以獲取特征和場(chǎng)景補(bǔ)充的建議，如根據(jù)對(duì)應(yīng)的實(shí)體，重新設(shè)計(jì)場(chǎng)景或添加新的特征，這對(duì)于動(dòng)態(tài)分析獲取功能全面且平衡的測(cè)試用例或場(chǎng)景集有很大的幫助。需要說明的是，特征和場(chǎng)景的添加和執(zhí)行，修改了已建立的基本架構(gòu)，按照本文的圖1流程，需要重新進(jìn)行跡的收集和算法1的處理等工作。但如果依賴性分析只是根據(jù)依賴圖推薦沒有被動(dòng)態(tài)執(zhí)行到的代碼實(shí)體，可以根據(jù)如下的算法2，進(jìn)行相關(guān)實(shí)體與已形成簇的相似度比較，以確定候選實(shí)體與基本架構(gòu)是合并還是舍棄。

算法2歸類算法（merging algorithm）

算法2通過命名規(guī)格進(jìn)行相似度匹配。其中，第5句首先排除名稱相同的已有的實(shí)體，不再進(jìn)行比較。第5～10句目標(biāo)是基于依賴性，將各實(shí)體與算法1中已經(jīng)聚類的各個(gè)簇進(jìn)行循環(huán)比較，選擇相似度最高的簇，如果大于設(shè)定的閾值，則將實(shí)體合并到該簇，否則舍棄。其中，算法第6句通過計(jì)算特征向量的余弦相似度進(jìn)行比較。該定義描述如下：設(shè)有程序元素m和p，分別對(duì)應(yīng)n維向量，則m和p的余弦相似度值為：

以下說明提取包含在類名的概念詞的方法：比如有實(shí)體類A和簇B的名稱分別為{DrawingChange-Event}和{DrawingEditor，F(xiàn)igureChangeAdapter}，經(jīng)轉(zhuǎn)換后形成概念詞集合分別為{Draw,Change,Event}和{Draw，Editor，F(xiàn)igure，Change，Adapter}，共用詞項(xiàng){Draw,Change,Event,Editor,Figure,Adapter}，則類A和簇B詞頻向量分別為{1,1,1,0,0,0}和{1,1,0,1,1,1}，由式（3）得到A與B的余弦相似度為51.6%。

4 案例研究

本章通過對(duì)開源項(xiàng)目的案例研究，介紹研究的目標(biāo)系統(tǒng)，描述聚類方法的細(xì)節(jié)，與目標(biāo)系統(tǒng)的設(shè)計(jì)者提供的實(shí)際結(jié)果比較以評(píng)估聚類質(zhì)量。

4.1 目標(biāo)系統(tǒng)

以 JHotDraw（http：//www.JHotDraw.org/）和 JEdit（http：//www.jedit.org/）作為案例研究分析實(shí)驗(yàn)步驟和結(jié)果。JHotDraw項(xiàng)目是描述二維圖形的開源系統(tǒng)，主要用于支持編輯器開發(fā)，具有良好的框架結(jié)構(gòu)和命名規(guī)范，并且有相應(yīng)的功能需求文檔；JEdit是一個(gè)帶有可擴(kuò)展插件體系結(jié)構(gòu)的程序文本編輯器，具有良好維護(hù)過程和可擴(kuò)展性能。因此，包結(jié)構(gòu)可以作為實(shí)驗(yàn)方法的權(quán)威參考。實(shí)驗(yàn)的軟件系統(tǒng)如表1所示。

Table 1 Descriptive statistics of target systems表1 目標(biāo)系統(tǒng)的描述性統(tǒng)計(jì)

通過對(duì)待分析系統(tǒng)的需求文檔查詢，確定了對(duì)應(yīng)的特征和場(chǎng)景描述，用標(biāo)記的執(zhí)行跡來(lái)精確記錄對(duì)應(yīng)的特征場(chǎng)景。從而快速建立起特征和系統(tǒng)實(shí)體之間的對(duì)應(yīng)關(guān)系。圖3是收集的JEdit系統(tǒng)的部分執(zhí)行跡片段。

表2顯示了研究所選擇的特征。在特征選擇上，本文盡可能選擇覆蓋各個(gè)方面，以取得特征集的平衡。由于只分析蹤跡中特定類的活動(dòng)，只要保存每個(gè)蹤跡的不同類別的實(shí)體。執(zhí)行場(chǎng)景后，生成特征-實(shí)體的關(guān)聯(lián)矩陣，根據(jù)算法1后得到如表3所示的初步劃分。

Fig.3 Partial execution traces slice of JEdit system圖3 JEdit系統(tǒng)的部分執(zhí)行跡片段

Table 2 Partial features and scenarios used in this experiment表2 實(shí)驗(yàn)的部分特征和場(chǎng)景

Table 3 Clusters results generated by k-means algorithm表3 通過k-means算法產(chǎn)生的聚類結(jié)果

從表3可以看出，在所劃分的簇中，包含了系統(tǒng)的基本框架，但各個(gè)簇中包含的類數(shù)量較少，與實(shí)際的包結(jié)構(gòu)有較大差別，因此結(jié)合本文第3.3節(jié)所提出的方法，對(duì)特征-實(shí)體矩陣中的實(shí)體進(jìn)行依賴性分析，根據(jù)不同的特征，將系統(tǒng)類之間的依賴標(biāo)識(shí)出來(lái)，然后按照補(bǔ)充特征，推薦特征沒有執(zhí)行過的實(shí)體，根據(jù)算法2的方法補(bǔ)充到相關(guān)的簇中，例如：standard.CreationTool→ application.DrawApplication；figures.RectangleFigure → figures.ImageFigure；application.DrawApplication → contrib.CommandMenu；figures.AttributeFigure → figures.FigureChangeEvent；Viewframework.ConnectionFigure → framework.Handle；standard.StandardDrawingView→framework.Drawing。

4.2 基準(zhǔn)實(shí)驗(yàn)比較

本文對(duì)JHotDraw和JEdit兩個(gè)開源系統(tǒng)采用了分階段聚類的算法，為評(píng)估該算法的質(zhì)量，分別采用Tzerpos等人提供的ACDC（algorithm for comprehension driven clustering）算法[32]和 Bunch 聚類算法[4]作為基準(zhǔn)實(shí)驗(yàn)對(duì)相同的實(shí)驗(yàn)系統(tǒng)進(jìn)行測(cè)試后進(jìn)行初步比較。以下是兩種算法的描述：

（1）ACDC是一種基于程序理解模式的算法，是通過使用模式驅(qū)動(dòng)的方法識(shí)別子系統(tǒng)，根據(jù)所使用的模式創(chuàng)建最終分解的框架。

（2）Bunch提供如窮舉和爬山等算法的集成用戶界面，將節(jié)點(diǎn)視為程序單元或模塊（如文件或類），并將節(jié)點(diǎn)之間的邊界視為這些模塊之間的調(diào)用如函數(shù)調(diào)用或繼承等關(guān)系?？梢允褂妙A(yù)定義的聚類來(lái)評(píng)估或提高系統(tǒng)聚類的質(zhì)量。

在軟件體系結(jié)構(gòu)恢復(fù)和演化領(lǐng)域，聚類是一項(xiàng)基本的活動(dòng)。對(duì)基于聚類的過程的整體質(zhì)量的評(píng)估通常是一個(gè)關(guān)鍵問題?？紤]在這個(gè)領(lǐng)域廣泛采用的三個(gè)評(píng)估度量[24]：權(quán)威性、分布合理性和穩(wěn)定性。比較三種方法對(duì)軟件架構(gòu)恢復(fù)的影響。

4.3 實(shí)驗(yàn)評(píng)估

為了評(píng)估聚類的質(zhì)量，本文以MoJo距離（measure based on move and join distance）作為度量指標(biāo)，比較實(shí)驗(yàn)聚類結(jié)果同實(shí)際系統(tǒng)結(jié)構(gòu)的差異。MoJo距離表示將源分區(qū)轉(zhuǎn)換為目標(biāo)分區(qū)的最小“移動(dòng)”和“合并”操作數(shù)?！耙苿?dòng)”表示將實(shí)體從一個(gè)簇中移動(dòng)到另一個(gè)現(xiàn)有簇或新創(chuàng)建的簇，“合并”操作將兩個(gè)簇類合并成一個(gè)簇類。

其中，N是待聚類的實(shí)體的總數(shù)，MoJo(A,B)=min(mno(B,A),mno(A,B))。Mno(X,Y)是“移動(dòng)”或“合并”操作所需的最小數(shù)量。MoJoSim值越高表明越接近實(shí)際劃分。輸入文件格式之一是RSF（rigi standard format）文件格式，相比較對(duì)象應(yīng)當(dāng)包含依賴關(guān)系及對(duì)象集合具有相同的數(shù)量等條件。轉(zhuǎn)換的工作流程設(shè)計(jì)如圖4所示。

Fig.4 RSF generation approach圖4 RSF處理方法

4.3.1 權(quán)威性比較

評(píng)估的一個(gè)重要指標(biāo)是實(shí)驗(yàn)所產(chǎn)生的劃分與權(quán)威劃分的相似程度。比較由實(shí)驗(yàn)生成的劃分A與權(quán)威劃分B，采用公式MoJoSim(A,B)并使用實(shí)際項(xiàng)目中的Java包結(jié)構(gòu)作為權(quán)威劃分。權(quán)威性值比較結(jié)果如圖5所示。

Fig.5 Comparison results of authoritativeness scores圖5 權(quán)威性值比較結(jié)果

4.3.2 穩(wěn)定性比較

聚類方法不會(huì)因?yàn)榫垲悓?duì)象的細(xì)微變化而導(dǎo)致聚類結(jié)果的顯著差別。兩個(gè)連續(xù)版本的系統(tǒng)中由相同聚類生成的兩個(gè)劃分Pi和Pi+1之間的相似性來(lái)衡量算法的穩(wěn)定性。通過計(jì)算MoJoSim(Pi,Pi+1)值比較聚類算法的穩(wěn)定性。穩(wěn)定性值比較結(jié)果如圖6所示。

Fig.6 Comparison results of stability scores圖6 穩(wěn)定性值比較結(jié)果

4.3.3 分布合理性比較

分布合理性NED是指聚類結(jié)果應(yīng)該盡可能少地出現(xiàn)星云與黑洞[38]，NED計(jì)算參見式（2）。NED值比較結(jié)果如圖7所示。

Fig.7 Comparison results ofNEDscores圖7 NED值比較結(jié)果

4.3.4 分階段聚類的符合度比較

顯然MoJoSim度量指標(biāo)只是反映聚類的質(zhì)量，還需要將實(shí)驗(yàn)結(jié)果與實(shí)際設(shè)計(jì)的包結(jié)構(gòu)進(jìn)行對(duì)比分析。為此將實(shí)驗(yàn)的兩個(gè)階段的聚類結(jié)構(gòu)分別與開源系統(tǒng)的真實(shí)結(jié)構(gòu)進(jìn)行比較，以區(qū)分實(shí)驗(yàn)在第二階段的聚類效果，具體的方法是采用Jaccard相似度計(jì)算，以包結(jié)構(gòu)為單位，比較實(shí)驗(yàn)聚合的簇與實(shí)際的包中所包含的各類，設(shè)有clusterA和packetB分別是實(shí)體類的集合，則clusterA和packetB的符合度定義如下：

例如在JHotDraw 5.2設(shè)計(jì)的包結(jié)構(gòu)中，除了測(cè)試用例和示例代碼外，共有7個(gè)包，比如，在framework包中，共含有18個(gè)類，集合為{Drawing,figure,painter,tool,locator,connector…}，以JHotDraw和JEdit的各個(gè)版本的實(shí)驗(yàn)初期和實(shí)驗(yàn)后期形成的聚類分別考慮，選擇的原則是按照名稱最相似的簇中類分別與實(shí)際的各個(gè)包中類進(jìn)行比較，獲得的部分?jǐn)?shù)據(jù)如圖8所示。

Fig.8 Distribution of comparison conformance圖8 比較符合度分布

4.4 方法的有效性討論

從圖8可以看出，最初的聚類與實(shí)際的包結(jié)構(gòu)的符合度在50%以下，經(jīng)過后一階段的聚類后，達(dá)到50%以上的較好的符合度。分析主要有以下幾點(diǎn)原因：首先，在靜態(tài)分析過程中通過算法2，利用類的依賴、繼承和調(diào)用等關(guān)系，在形成的框架中添加實(shí)體，擴(kuò)充了核心簇類中的實(shí)體數(shù)量，總的簇?cái)?shù)目根據(jù)需要調(diào)整，這與使用的方法有關(guān)，如果把引入的實(shí)體與以往的核心簇重新聚類，可能會(huì)影響核心架構(gòu)的特征功能。而采用迭代的架構(gòu)恢復(fù)方法，當(dāng)需要特征和場(chǎng)景的添加和執(zhí)行時(shí)，需要重新運(yùn)行算法1，并構(gòu)建基本框架。因此，在方法的處理上具有靈活性。從代碼的架構(gòu)來(lái)看，設(shè)計(jì)者基本上是按照功能實(shí)現(xiàn)進(jìn)行命名和結(jié)構(gòu)劃分的，如JHotDraw 5.2中的standard包有47個(gè)類，application包和applet包都只有1個(gè)包等。因?yàn)閍pplet主要功能是針對(duì)網(wǎng)頁(yè)應(yīng)用，application包同樣是針對(duì)Samples包的應(yīng)用設(shè)計(jì)的，不是系統(tǒng)的核心功能，所以采用以NED最大值作為聚類算法的劃分是可行的。同時(shí)，恢復(fù)原始軟件包意味著可能識(shí)別出有重構(gòu)意義的程序元素，從低內(nèi)聚性軟件包開始，可以將軟件包分成更多具有更高內(nèi)聚性的模塊。

其次，本文以動(dòng)態(tài)特征分析為起點(diǎn)，盡管采用依賴性分析擴(kuò)充分析的范圍，但對(duì)結(jié)構(gòu)影響最大的是初期的特征和場(chǎng)景的選擇。在實(shí)驗(yàn)的初期，如果只選擇功能相類似的特征，聚類后的系統(tǒng)結(jié)構(gòu)很可能包含大部分實(shí)體的小部分簇，形成極端分布的現(xiàn)象。因此通過迭代和比較分析，擴(kuò)充特征和場(chǎng)景的方法取得結(jié)構(gòu)的平衡。本文首先建立起基本的功能框架，構(gòu)建特征層次的結(jié)構(gòu)恢復(fù)，這與靜態(tài)的聚類或面向模式的恢復(fù)方式相比，在恢復(fù)的結(jié)構(gòu)上可能存在著差異。

5 總結(jié)和展望

本文的中心是通過分階段的聚類算法，達(dá)到目標(biāo)系統(tǒng)結(jié)構(gòu)恢復(fù)的目的。在方法的實(shí)現(xiàn)上，采用特征作為聚類標(biāo)準(zhǔn)創(chuàng)建基本結(jié)構(gòu)，按照動(dòng)態(tài)調(diào)用的賦值權(quán)重分配給提取的信息以提高聚類的準(zhǔn)確性。根據(jù)合理性分布的聚類質(zhì)量要求，達(dá)到自動(dòng)確定聚類數(shù)量的效果。結(jié)合靜態(tài)依賴圖補(bǔ)充特征和程序元素，循環(huán)迭代是獲取特征和場(chǎng)景的平衡集，以恢復(fù)比較全面的框架結(jié)構(gòu)。

在實(shí)驗(yàn)效果的評(píng)估上，從權(quán)威性、穩(wěn)定性和分布合理性等方面，比較形成的結(jié)構(gòu)與設(shè)計(jì)的包結(jié)構(gòu)的差異以評(píng)估實(shí)驗(yàn)方法的質(zhì)量，為進(jìn)一步的程序理解和系統(tǒng)可能的重新模塊化提供幫助。此外，依賴關(guān)系作為恢復(fù)中的重要因素，如何提供更精確的權(quán)重度量以提高恢復(fù)的精確度是需要考慮的工作。從實(shí)驗(yàn)結(jié)果看，方法還受到主觀因素的制約，如特征和場(chǎng)景的構(gòu)建，度量指標(biāo)的選擇等，這些都需要更多的實(shí)驗(yàn)總結(jié)和完善。