一种基于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算法的高效性与层次聚类的高精度特点结合起来。实验表明，本文算法可以得到有效的软件划分结果，并且在保证层次聚类精度不变的同时可以有效减少层次聚类算法的运行时间。

目前本文的工作只在代码的包层次进行重构研究，在未来的工作中，尝试将该方法应用在代码的其他层次上进行重构研究，例如，类层次、方法层次等。