一種基于DBSCAN算法的代碼包層次重構(gòu)改進(jìn)方法*

李文昊，李英梅，邊奕心

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

1 引言

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

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

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

2 相關(guān)研究

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

2.1 基于聚類的方法

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

2.2 基于圖的方法

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

在上述研究中，層次聚類算法的軟件劃分效果最好，但是層次聚類算法的時間復(fù)雜度太高，不利于處理大規(guī)模的軟件程序[11]。目前，該領(lǐng)域?qū)垲愋矢叩腄BSCAN算法還沒有深入研究?；谝陨涎芯炕A(chǔ)，本文提出一種基于DBSCAN的軟件層次聚類算法，以提高軟件聚類的效率。

3 相關(guān)概念

3.1 密度聚類算法DBSCAN

DBSCAN算法是一種基于密度的聚類算法，該算法能夠?qū)⒆銐蚋呙芏鹊膮^(qū)域劃分成不同的簇[12]。密度就是樣本分布的緊密程度，在本文研究中，樣本之間的緊密程度就是類之間的方法調(diào)用頻度。利用DBSCAN算法可以高效地將互相調(diào)用頻繁的類聚到相同組中，以此找到“高內(nèi)聚、低耦合”的軟件結(jié)構(gòu)。

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

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

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

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

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

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

DBSCAN算法思想如下所示：

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

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

(3)重復(fù)過程(2)，直到?jīng)]有新的實體添加到任何簇時結(jié)束。

參數(shù)Eps和MinPts的選取依據(jù)如下所示：

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

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

3.2 層次聚類算法A-KNN

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

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

A-KNN算法實現(xiàn)過程：

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

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

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

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

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

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

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

4.1 實體與屬性的定義

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

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

(1)

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

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

4.2 相似度計算

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

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

(2)

其中，分子表示實體X與實體Y的屬性值都為1的屬性個數(shù)，分母表示實體X或?qū)嶓wY的屬性值為1的屬性個數(shù)的總和。

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

(3)

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

4.3 基于DBSCAN的層次聚類算法

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

算法步驟如下所示：

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

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

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

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

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

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

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

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

步驟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重復(fù)步驟2和步驟3，直至所有實體屬于同一聚類簇，返回聚類樹狀圖。

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

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

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

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

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

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

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

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

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

4.4 算法的時間復(fù)雜度分析

5 實驗與數(shù)據(jù)分析

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

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

Table 1 Open Source projects in the experiment

5.1 Font4MySQL系統(tǒng)的實驗

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

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的橫坐標(biāo)所示，DBSCAN算法將實體集合分成了簇1、簇2和簇3共3個聚類簇，其中簇3是由DBSCAN算法篩選出來的噪聲點組成的，雖然效率高，但是聚類精度不夠。對這3個聚類簇分別使用A-KNN算法得到3個聚類樹狀圖，從而可以分析得到最終的分組結(jié)果。表5是Font4MySQL系統(tǒng)中所有聯(lián)系緊密的類的分組情況，其中聯(lián)系度由類之間互相調(diào)用的不同方法數(shù)來確定。

Table 5 Grouping of closely related classes in Font4MySQL

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

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

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

5.2 與其他聚類算法的比較

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

(4)

其中，m表示子圖數(shù)目，Ai表示第i個子圖的內(nèi)部關(guān)聯(lián)度，Ei,j表示第i個子圖和第j個子圖之間的關(guān)聯(lián)度。Ai由第i個子圖的Ni個節(jié)點以及節(jié)點之間的邊關(guān)聯(lián)度ui決定，Ei,j由節(jié)點個數(shù)Ni、Nj和第i個子圖和第j個子圖的邊關(guān)聯(lián)度εi,j決定。本文把程序中的類看做節(jié)點，把類之間的方法調(diào)用數(shù)與所有調(diào)用數(shù)之和的比值作為邊關(guān)聯(lián)度。

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

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

Table 6 Comparison of MQ values of different clustering algorithms

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

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

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

Table 7 Comparison of running time of different clustering algorithms

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

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

6 結(jié)束語

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

目前本文的工作只在代碼的包層次進(jìn)行重構(gòu)研究，在未來的工作中，嘗試將該方法應(yīng)用在代碼的其他層次上進(jìn)行重構(gòu)研究，例如，類層次、方法層次等。