一種基于DBSCAN算法的代碼包層次重構改進方法*

李文昊，李英梅，邊奕心

(哈爾濱師范大學計算機科學與信息工程學院，黑龍江 哈爾濱 150025)

1 引言

在現實世界中，進化是軟件的一個內在屬性。隨著軟件的增強、修改和適應新的需求，代碼變得越來越復雜，并逐漸偏離最初的設計，導致代碼的質量逐漸下降，而重構是解決該問題的一個有效辦法[1]。重構是一種在不改變代碼外在行為的前提下，對代碼作出修改，提升代碼質量的程序整理方法[2]。但是，尋找到需要重構的代碼以及確定使用何種重構策略都將會是一項復雜而繁瑣的任務[3]。

聚類作為一種可以將相似的數據聚集在相同簇中的技術，可以將軟件系統的實體(如類或源文件)分組為更加有意義的子系統，從而發現質量更好的軟件體系結構，為代碼重構提供指導性建議[4,5]。目前，已經有很多聚類算法被應用于代碼重構，但大多數都是在方法層次和類層次上的研究。Alkhalid[6]在包層次提出了一種基于K近鄰算法的層次聚類A-KNN(Adaptive K-Nearest Neighbor clustering)算法，其聚類效率比普通的層次聚類算法要高，在軟件的包層次上進行聚類可以得到“高內聚、低耦合”的軟件結構，但是算法的時間復雜度較高。基于密度聚類的DBSCAN(Density Based Spatial Clustering of Applications with Noise)算法是一種高效的聚類算法[7]，但是由于使用的是統一的全局變量，所以在處理分布不均勻的數據時，聚類精度較低。

鑒于以上研究，本文在包層次上提出一種基于DBSCAN的軟件層次聚類算法，將DBSCAN算法的高效性與A-KNN算法的高精度特點結合到一起，以此提高軟件層次聚類的效率，指導代碼重構。本文在5個不同領域的開源項目上進行了實驗，實驗結果表明，本文算法可以有效地將程序中關系緊密的類分到同一分組中，并且在保持層次聚類算法精度不變的同時可以有效提高層次聚類的效率，得到更加合理的軟件劃分結果。

2 相關研究

目前已有很多軟件劃分的方法被提出，通過將軟件劃分成功能集中且獨立的子系統的集合來得到合理的軟件結構，以此來指導代碼重構，提高代碼的可理解性與可維護性。軟件劃分方法一般可以分為基于聚類的方法和基于圖的方法。

2.1 基于聚類的方法

Alkhalid[6]以程序中的類作為實體，以類之間的繼承、聚合和關聯等關系作為屬性，使用層次聚類算法對程序進行聚類，以此得到質量更好的軟件包結構，并以包內的內聚度與包間的耦合度為度量，對SLINK(Single LINKage algorithm)、CLINK(Complete LINKage algorithm)、WPGMA(Weighted Pair-Group Method using Arithmetic averages)和A-KNN等層次聚類算法的重構效果進行了評估比較。Xiao[5]分析了幾種用于代碼重構的聚類算法的優缺點，并提出了一種基于K-means和CURD(Clustering Using References and Density)算法的改進的層次聚類算法用于代碼重構，該算法可以有效地處理大規模、高緯度的數據。Corazza等人[8]將類中的詞匯作為實體特征，并利用期望最大化算法設計了一個概率模型為詞匯所出現的不同位置分配權重，最后通過K-medoid算法來對程序中的類進行聚類。Wang等人[9]提出了一種系統級多重重構算法，該算法能根據“高內聚、低耦合”的原理自動識別移動方法、移動字段和提取類的重構機會。算法實現主要是通過將程序類中的方法和屬性作為實體進行聚類，把屬于同一簇的方法和屬性放到同一個類中，最后把新的類與初始的類作比較，從而得到移動方法、移動字段和提取類的重構機會，最后通過合并和分割相關類，從系統級獲得最優的功能分布。

2.2 基于圖的方法

Pan等人[10]利用軟件網絡圖表示程序中類和類之間的依賴關系，并提出了一種社區發現算法來得到軟件網絡圖中最優的社區結構，通過不斷計算每次劃分后的圖的質量指標，最終得到質量最好的圖劃分結果對應程序中類的分包結果。Hussain等人[11]提出了一種基于圖劃分的層次聚類算法用于軟件重構，該算法先用實體之間的相似度矩陣構造軟件網絡圖，圖中頂點表示實體，邊表示實體之間的依賴關系；然后根據頂點的度和邊的權重的大小順序依次找出圖中的(k,w)-核心子圖(頂點的度至少為k,邊的權重至少為w的子圖)；最后依據子圖之間的相關性，對所有子圖進行層次聚類。該算法相比普通的層次聚類算法能夠生成更加簡潔的樹狀圖，便于開發者分析使用。

在上述研究中，層次聚類算法的軟件劃分效果最好，但是層次聚類算法的時間復雜度太高，不利于處理大規模的軟件程序[11]。目前，該領域對聚類效率高的DBSCAN算法還沒有深入研究。基于以上研究基礎，本文提出一種基于DBSCAN的軟件層次聚類算法，以提高軟件聚類的效率。

3 相關概念

3.1 密度聚類算法DBSCAN

DBSCAN算法是一種基于密度的聚類算法，該算法能夠將足夠高密度的區域劃分成不同的簇[12]。密度就是樣本分布的緊密程度，在本文研究中，樣本之間的緊密程度就是類之間的方法調用頻度。利用DBSCAN算法可以高效地將互相調用頻繁的類聚到相同組中，以此找到“高內聚、低耦合”的軟件結構。

下面給出DBSCAN算法一些必要的定義：

定義1(Eps鄰域) 給定實體以Eps為半徑所確定的鄰域即為該實體的Eps鄰域。

定義2(核心點) 如果實體的Eps鄰域內包含至少MinPts個數目的實體，則稱該實體為一個核心點。

定義3(直接密度可達) 給定一個實體集合D，如果p在q的Eps鄰域內，而q是一個核心點，則稱實體p是從實體q出發直接密度可達的。

定義4(密度可達) 如果存在一個實體鏈P1，…，Pi，…，Pn，滿足P1=p和Pn=q，Pi是從Pi+1關于Eps和MinPts直接密度可達的，則稱實體p是從實體q關于Eps和MinPts密度可達的。

定義5(密度相連) 如果存在實體o∈D，使實體p和q都是從o關于Eps和MinPts密度可達的，那么實體p到q是關于Eps和MinPts密度相連的。

DBSCAN算法思想如下所示：

(1)根據實體的分布情況計算參數Eps和MinPts。

(2)從數據集中找出一個沒有被歸入任何簇的核心點，再將這個核心點和它所有的密度相連且未被歸入任何簇的實體聚集為一個聚類簇。

(3)重復過程(2)，直到沒有新的實體添加到任何簇時結束。

參數Eps和MinPts的選取依據如下所示：

對于MinPts，文獻[7]指出其值如果小于3，則DBSCAN算法與層次聚類算法結果相同，大于4則不會對結果有太大影響，本文在多個項目上通過多次實驗最終確定MinPts的值為3。

對于Eps，本文使用文獻[7]提出的繪制k-距離曲線法來獲得，k=MinPts，對于數據中的每個點，計算其對應的第k個最近點距離，并將數據中所有點的第k個最近點距離按照降序方式排序作圖，稱這幅圖為k距離曲線圖，選擇該圖中第1個突變點做為Eps。但是，如果處理的是分布不均勻的數據，利用此法獲得的Eps值會偏大，致使離得較近而密度較大的簇被合并，導致聚類精度低。因此，本文結合層次聚類算法來改進聚類結果。

3.2 層次聚類算法A-KNN

A-KNN算法是Alkhalid在文獻[6]中提出的一種基于K近鄰算法的層次聚類算法，它的聚類效率比普通的層次聚類算法高，效果更好。

A-KNN算法思想為：首先將每個實體視為一個集群。在第2次迭代中，設K=3，算法選擇待聚類實體的3個最近鄰居，然后檢查它們的標簽。如果3個實體中至少有2個具有相同的標記，則該算法標記目前的實體與這2個實體的標簽相同。如果這3個實體有不同的標簽，則算法將用最近實體的標簽標記當前實體。

A-KNN算法實現過程：

(1)將每個實體都單獨作為一個聚類簇，并賦予簇的唯一標識符。

(2)找出3組距離最近的實體(a,b)，(d,e)和(f,g)，它們滿足關系式Coeff(a,b)≥Coeff(d,e)≥Coeff(f,g),其中，Coeff(x,y)表示實體x與實體y之間的相似度系數。

(3)如果L(a)=L(d)=L(f)且L(e)=L(g)，那么就將a所在的簇與e所在的簇合并，否則就將a所在的簇與b所在的簇合并，其中，L(x)表示實體x所在簇的簇標記。

(4)重復步驟(2)和步驟(3)，直到所有實體屬于同一聚類簇，得到聚類的樹狀圖。

4 基于DBSCAN的軟件層次聚類算法

本文針對聚類算法在代碼重構上的應用，提出了一種基于DBSCAN的軟件層次聚類算法。聚類流程如圖1所示，首先從源程序中提取出類之間的調用關系，得到實體-屬性矩陣；然后通過擴展Jaccard系數計算得到實體之間的相似度矩陣；最后通過本文提出的基于DBSCAN的層次聚類算法得到聚類樹狀圖，分析樹狀圖得到類最終的分組結果來指導代碼重構。

Figure 1 Flow chart of software hierarchical clustering algorithm based on DBSCAN圖1 基于DBSCAN的軟件層次聚類流程圖

4.1 實體與屬性的定義

實體是需要被聚類分組的對象。在包層次的代碼重構研究中，程序中的類被選為實體。實體的特征稱為屬性。在本文中，程序里的所有方法被選作實體的屬性。

本文用只包含0和1的向量來表示實體，其中向量的每一維代表實體的一個屬性，屬性值可由式(1)計算得到：

(1)

其中，v(atti,entj)表示第j個實體的第i個屬性的值；atti∈entjoratti→entj表示第i個屬性代表的方法屬于第j個實體代表的類或被第i個實體代表的類所調用。

由式(1)可知，如果2個類之間互相調用的方法越多，那么它們的值都為1的相同屬性就越多，它們就越相似。

4.2 相似度計算

大多數軟件聚類研究采用相似度系數來計算2個實體之間的相似度，即2個實體之間的相關匹配越多，這2個實體就越相似[4]。

文獻[6,13]采用Jaccard系數來表示實體之間的相似度，計算公式如式(2)所示：

(2)

其中，分子表示實體X與實體Y的屬性值都為1的屬性個數，分母表示實體X或實體Y的屬性值為1的屬性個數的總和。

但是，Jaccard系數只能表示2個實體之間的相對相似度，不能用來衡量2個實體在全局范圍內的相似度，這就可能導致2個聯系緊密的實體最終并沒有被聚類到同一個簇中。針對這個問題，鐘林輝等人[14]提出了一種擴展的Jaccard系數來解決，并通過實驗證明了改進后的聚類效果更好。擴展的Jaccard系數計算如式(3)所示：

(3)

其中，分母表示程序中所有實體屬性值為1的屬性個數的總和(用|Ti|表示第i個實體屬性值為1的屬性個數)。

4.3 基于DBSCAN的層次聚類算法

DBSCAN算法的優點是高效且能有效處理噪聲點，缺點是在遇到分布不均勻的數據時，聚類精度低。A-KNN層次聚類算法的優點是可以生成聚類樹狀圖，從而可以根據需要得到不同粒度的多層次聚類結構，聚類精度高，缺點是算法的時間復雜度太高。因此，本文提出一種基于DBSCAN的層次聚類算法，其基本思想是使用DBSCAN算法生成的類來約束層次聚類的聚類空間，然后使用層次聚類得到實體最終的分組結果，以此將DBSCAN算法的高效性與層次聚類算法的高精度特點結合起來。

算法步驟如下所示：

(1)利用DBSCAN算法，將實體集合劃分成不固定的N個類，其中噪聲點集合為單獨一類。

(2)對這N個類分別使用A-KNN算法，生成N棵聚類樹。

(3)分析每棵聚類樹，得到對應的分組，最后匯總到一起，得到實體最終的分組結果。

具體算法如算法1和算法2所示：

算法1A-KNN層次聚類算法

輸入：實體相似度矩陣S。

輸出：實體的聚類樹狀圖。

步驟1將矩陣中的每一個實體單獨作為一個聚類簇并賦上唯一簇標識。

步驟2從相似度矩陣中找出3組相似度最大的實體對(a,b),(d,e)和(f,g)，其相似度滿足Coeff(a,b)≥Coeff(d,e)≥Coeff(f,g)。

步驟3如果實體a、d和f屬于同一聚類簇，且實體e和g也屬于同一聚類簇，則將實體a所在的簇與實體e所在的簇合并，否則將實體a所在的簇與實體b所在的簇合并。

步驟4重復步驟2和步驟3，直至所有實體屬于同一聚類簇，返回聚類樹狀圖。

算法2基于DBSCAN的層次聚類算法

輸入：實體-屬性矩陣A，核心點半徑Eps，核心點鄰域中最小點數目MinPts。

輸出：各個實體聚類簇的聚類樹狀圖。

步驟1根據實體-屬性矩陣A計算實體相似度矩陣S；

步驟2隨機選擇一個未被處理的實體，如果該實體的Eps鄰域內少于MinPts個點，則標記該實體為噪聲點，否則標記該實體為核心點。

步驟3如果步驟2標記實體為核心點，則創建一個新的聚類簇。遍歷該核心點鄰域內的所有核心點，將這些核心點密度相連且未被處理的點都合并到當前聚類簇中。

步驟4重復步驟2和步驟3，直至所有實體都被處理。

步驟5將所有噪聲點單獨合并到一個聚類簇中。

步驟6從實體相似度矩陣S中提取出每個聚類簇的子相似度矩陣，利用A-KNN算法生成聚類樹狀圖。

4.4 算法的時間復雜度分析

5 實驗與數據分析

為驗證本文提出的基于DBSCAN的軟件層次聚類算法的有效性，本節將其與文獻[6]中的4種聚類算法A-KNN、SLINK、CLINK和WPGMA在5個不同領域的開源項目上進行實驗。5.1節為本文算法在規模較大的Font4MySQL系統上的具體實驗結果分析和專家評判，5.2節為5種聚類算法在5個開源項目上的軟件劃分結果度量、專家評判和算法運行時間對比。

表1為所選開源項目的描述，其中，Trama、Font4MySQL項目來自文獻[6,10]，Meinvtu、Sumk-log、Sumk-codetool項目來自https://www.oschina.net/。實驗環境是個人PC機，操作系統為Windows 7，配置Intel Core i5 4200M，2.5 GHz，4 GB內存。算法實現均以Matlab為開發工具。

Table 1 Open Source projects in the experiment

5.1 Font4MySQL系統的實驗

Font4MySQL是開源數據庫服務器MySQL的一個可移植的前端，它提供了一個完整的前端操作界面，從而減少了使用SQL查詢語言所帶來的困難，該系統包含53個類、473個方法。使用基于DBSCAN的軟件層次聚類算法后，得到圖2～圖4所示的3個層次聚類樹狀圖，圖的橫坐標為實體編號，縱坐標為實體間的距離。表2～表4為分析得到的相應的聚類分組。

Figure 2 Cluster 1 hierarchical clustering tree in Font4MySQL圖2 Font4MySQL簇1層次聚類樹狀圖

Figure 3 Cluster 2 hierarchical clustering tree in Font4MySQL圖3 Font4MySQL簇2層次聚類樹狀圖

Figure 4 Cluster 3 hierarchical clustering tree in Font4MySQL圖4 Font4MySQL簇3層次聚類樹狀圖

Table 2 Cluster 1 grouping in Font4MySQL

Table 3 Cluster 2 grouping in Font4MySQL表3 Font4MySQL簇2分組情況

Table 4 Cluster 3 grouping in Font4MySQL表4 Font4MySQL簇3分組情況

如圖2～圖4的橫坐標所示，DBSCAN算法將實體集合分成了簇1、簇2和簇3共3個聚類簇，其中簇3是由DBSCAN算法篩選出來的噪聲點組成的，雖然效率高，但是聚類精度不夠。對這3個聚類簇分別使用A-KNN算法得到3個聚類樹狀圖，從而可以分析得到最終的分組結果。表5是Font4MySQL系統中所有聯系緊密的類的分組情況，其中聯系度由類之間互相調用的不同方法數來確定。

Table 5 Grouping of closely related classes in Font4MySQL

由表5中可以看出，使用基于DBSCAN的軟件層次聚類算法后，程序中所有聯系緊密的類都被分到了同一組中。除此之外，我們還發現很多互相聯系并不緊密的類被分到一組是因為它們調用了很多相同的方法，這樣的類往往是為了完成某一共同的任務而設計的，因此將它們分到一組也符合軟件的設計原則。

對分組結果進行具體分析發現，分組C1中的類都是用來完成程序后臺活動的創建和執行以及數據存儲、查詢功能的，分組C2中的類都是用來完成事務的創建、偵聽和觸發功能的，分組C3中的類都是用來完成獲取、管理一切驅動程序信息功能的，分組C4中的類都是用來完成數據庫連接功能的，分組C5中的類都是用來完成獲取、管理用戶功能的，分組C6中的類都是用來完成程序庫的加載功能的，由圖4可見，分組C7是一些與其他類毫無聯系的類，事實上，它們都是一些未用到的接口。

將重構前后的代碼包結構提供給軟件工程領域的專家進行評判，得到一致結論：與程序的初始設計相比，重構后的代碼包結構提高了程序包內的內聚性，降低了包間的耦合性。除此之外，包內的類功能更加集中，程序模塊更加獨立，增強了程序的可閱讀性、可擴展性和可維護性。

5.2 與其他聚類算法的比較

本文采用文獻[15]提出的模塊劃分質量MQ(Modularization Quality)來比較不同聚類算法對軟件的劃分質量。MQ取值為-1～1，值越大代表劃分質量越高，結構越符合“高內聚、低耦合”的設計原則。MQ計算公式如式(4)所示：

(4)

其中，m表示子圖數目，Ai表示第i個子圖的內部關聯度，Ei,j表示第i個子圖和第j個子圖之間的關聯度。Ai由第i個子圖的Ni個節點以及節點之間的邊關聯度ui決定，Ei,j由節點個數Ni、Nj和第i個子圖和第j個子圖的邊關聯度εi,j決定。本文把程序中的類看做節點，把類之間的方法調用數與所有調用數之和的比值作為邊關聯度。

表6是本文算法、A-KNN、SLINK、CLINK和WPGMA在5個開源項目上軟件劃分的MQ值比較。

從表6中可以看出，本文算法、A-KNN算法和SLINK算法的劃分效果要明顯優于CLINK算

Table 6 Comparison of MQ values of different clustering algorithms

法和WPGMA算法的。在Meinvtu、Sumk-log和Sumk-codetool小規模項目上，前3種算法的劃分效果是一樣的，而在Trama和Font4MySQL這種較復雜的項目上，本文提出的算法要優于A-KNN算法和SLINK算法。另外，經過人工分析判斷，前3種算法在小規模項目上的具體劃分結果沒有太大差別，而在方法較多、方法調用頻繁的項目上，基于DBSCAN的軟件層次聚類算法由于可以預先根據樣本的密度信息對樣本進行一個初步分類，使得趨向于局部最優的層次聚類算法的聚類分組更加準確。

為了進一步比較說明各種聚類算法的劃分結果，由專家對劃分后的不同代碼包結構進行評判，得到一致結論：基于DBSCAN的軟件層次聚類算法、A-KNN算法和SLINK算法的軟件劃分結果更加穩定合理，可以有效提高程序模塊內的內聚性，降低模塊間的耦合性，并且基于DBSCAN的軟件層次聚類算法在復雜的軟件系統上得到的代碼包結構的程序模塊功能更加集中，程序模塊的獨立性更強。

表7是本文算法、A-KNN、SLINK、CLINK和WPGMA聚類算法在5個開源項目上運行時間的比較。

Table 7 Comparison of running time of different clustering algorithms

由表7可以看出，SLINK、CLINK和WPGMA等算法的運行時間差別不大，A-KNN算法的聚類效率比上述3種算法有略微提升，而本文提出的算法運行時間最短，在規模較大的Font4MySQL項目上更加明顯。本文算法的運行時間比起其他4種聚類算法平均可以減少23.02%,28.43%,34.02%和42.68%。

上述實驗結果表明，本文提出的基于DBSCAN的軟件層次聚類算法，在保證層次聚類算法精度不變的前提下可以有效提升算法的聚類效率，并且得到了更好的軟件劃分結果。

6 結束語

在包層次的代碼重構研究中，本文針對DBSCAN算法聚類效率高、精度低，而層次聚類算法聚類精度高、時間復雜度高的特點，提出一種基于DBSCAN的軟件層次聚類算法，將DBSCAN算法的高效性與層次聚類的高精度特點結合起來。實驗表明，本文算法可以得到有效的軟件劃分結果，并且在保證層次聚類精度不變的同時可以有效減少層次聚類算法的運行時間。

目前本文的工作只在代碼的包層次進行重構研究，在未來的工作中，嘗試將該方法應用在代碼的其他層次上進行重構研究，例如，類層次、方法層次等。