基于MCL与KNN的混合聚类算法

牛秦洲，陈艳(桂林理工大学信息科学与工程学院，广西桂林　541004)



基于MCL与KNN的混合聚类算法

牛秦洲，陈艳
(桂林理工大学信息科学与工程学院，广西桂林541004)

摘要:MCL是一种图聚类算法，针对MCL计算过程会产生小聚类及边缘节点从团中脱离出来的问题，提出了一种基于MCL与KNN相结合的混合聚类算法。该算法利用KNN的分类特点，以MCL聚类得到的聚类表为依据，通过KNN对小聚类中的元素进行再分类，以提高聚类的质量。实验证明此方法是可行的，改进后的算法能使聚类质量有所提高。

关键词:MCL;聚类; KNN;小聚类;再分类

聚类分析是数据挖掘领域中一种重要的数据处理方法，主要是对数据按某种相似性度量标准来进行聚类。

聚类操作中比较常用的几种算法有k-means聚类［1－2］、基于密度［3］的聚类和基于网格聚类［4］等，但这些算法都存在以下几个方面的缺陷: 1)它们都是以经典的相似性度量作为聚类的基础，聚类而成的概念不能完全反映该类概念抽象的实质，进而导致求解精度下降; 2)当样本属性较多时，往往很难通过简单计算得到的相似度值来全面地反映样本之间的相关或相似程度，从而导致样本聚类概念的区分度较低。

与传统的聚类算法相比，MCL ( Markov clustering，马尔可夫聚类)能够很好地避免以上问题的发生。MCL聚类是图聚类的一种，其核心思想是基于模拟随机流(使用图的转移概念矩阵)进行图聚类［5］。这种方法已被应用到很多领域并取得显著成功(如蛋白质的Tribe-MCL聚类)［6－7］。在MCL聚类的过程中，不是简单地求出样本之间的关系来进行聚类判断，而是在这种关系的基础上通过膨胀和扩展操作来获得关于样本之间的更深层的知识来进行聚类。因此在聚类的过程中从全局的角度出发，对样本间的关系分析的更全面、更彻底。但由于在MCL聚类过程中过度拟合使得容易产生小聚类(只有一两个节点的聚类)从而影响聚类质量，为了解决这个问题，笔者采用MCL结合KNN［8］的混合算法，对MCL进行改进以提高聚类质量。

1　MCL聚类算法介绍

1. 1 MCL聚类算法概述

马尔可夫聚类算法( MCL)是van Dongen［5］开发的用于图形聚类的算法，已成功应用于蛋白质家族分析等领域。MCL算法是基于随机流的一种方法，不需预先设定聚类数目，通过概率改变和反复修改矩阵以实现随机流模拟。

MCL聚类过程主要由在随机矩阵(马尔可夫矩阵)上的两个操作构成:膨胀操作和扩展操作。膨胀操作主要是对矩阵进行的幂操作;扩展操作是对随机矩阵中每个元素进行的幂操作，即Mij= ( Mij)r。

1. 2相关定义及操作介绍

图的相关矩阵:设G为一个有n个顶点的带有权值的图，则G的相关矩阵被定义为M'( G)，其中M'( G)中的元素Mij'的值与图G中相应边上的权值Wij相等。

图的马尔可夫矩阵:令M'是图G的相关矩阵，M为图的马尔可夫矩阵，则M的第j列是M'的第j列的归一化，即Mlj= Mlj'/∑iMij'。其中: l，j为常数。

令图G的相关矩阵表示为

则图G的马尔可夫矩阵可表示为

扩展操作:设图G为一个有n个顶点的图，图的马尔可夫矩阵可表示为M( G)。扩展操作的作用是通过对图的马尔可夫矩阵进行幂乘M = M·M，使两个顶点间的相似度转化为两个顶点与共同邻接点的相似度的乘积之和。当扩展值e = 2时，可表示为M = M·M，Mij可表示顶点i经过一步到达顶点j的概率;当e = 3时，M = M3，此时Mij表示顶点i经过两步流向顶点j的概率;当经历的步数越多，则流出所在簇而进入另外一个簇的可能性变大。所以扩展操作数e越大，会使同一个簇之间的紧密性作用优势减弱。

膨胀操作:膨胀操作通过膨胀参数R来对矩阵M中的每一列元素进行幂乘操作，然后对每一列进行归一化操作，这样可以拉大同一列元素之间的差距。膨胀操作是一个非线性操作，目的是增强类内的流，削弱类间的流。

MCL的聚类过程如图1所示。可以看出，MCL的聚类过程主要通过膨胀和扩展两个操作在马尔可夫矩阵上的交替使用来完成矩阵的修改，从而使马尔可夫矩阵达到稳定状态实现聚类。

由于上述聚类特点，经过一定步骤的操作后导致节点间关系的放大和缩小，从而使节点之间的关系出现偏差。由于偏差不断扩大，致使一些边缘节点从团中分离出来形成单个或只有两三个节点的小聚类。

图1　MCL聚类算法Fig. 61MCL clustering algorithm

为了减少小聚类的产生，提高聚类的质量，笔者提出了一种改进的MCL算法。考虑到在聚类过程中由于不断的膨胀和扩展操作导致节点关系的偏差放大，图中处在同一个团中的边缘节点容易被分离出来。然而即使被分离出来，边缘形成的小聚类与原来一个团体形成的聚类的联系依然是很紧密的。因此，提出了一种MCL与KNN相结合的混合聚类算法，算法的主要思想如下:在进行聚类后，对小聚类与其他聚类的类间距离关系进行判断，从而决定是否需要进一步合并。

当小聚类与其他聚类质心的最小距离小于某一阈值，可认为它们之间关系比较紧密，小聚类的存在不合理，需要进一步利用KNN对小聚类中的元素进行重新分配;当质心的距离大于阈值时，则认为小聚类与其他类存在明显的区别，其存在是合理的。

2　混合聚类算法

2. 1算法思想

采用MCL与KNN相结合的混合算法来避免上述问题的发生。KNN算法是一种分类算法，其基本思想是:给定一个待分类的数据，通过以一个已分类的样本空间为依据，计算离自己最近的K个样本来判断这个待分类数据的类别情况。因此，可以考虑利用KNN来对分离出来的小聚类进行再次的分类，从而解决小聚类产生的问题。

2. 2马尔可夫矩阵计算

在进行MCL聚类前，需要先求出数据之间的关系，得到一个关系矩阵。定义相似度函数

式中: simG( X，Y)表示实例X，Y之间的相似度; k表示样本的属性个数; dn( Xi，Yi)为两个实例的属性i的距离; wi为属性i的权值; Di表示属性i的取值范围; range( Di)为Di中的最大差值。利用上面的相似度计算模型来计算样本之间的关系，得到关系矩阵即马尔可夫矩阵。

2. 3质心判断

在对聚类进行质量评价时，类间距离常会被作为一个重要因素考虑。采用同样的思想，对于产生的小聚类，利用类间的距离来衡量两个类是否聚类合理。

由于同一个聚类中的样本相似程度高，因此可以利用质心来简化整个类。

质心代表的是聚类中各实例的平均化，通过质心间的距离从整体上判断聚类之间分布的合理性，这里引入阈值Td进行判断，若两个质心的距离小于Td，则认为它们属于同一个聚类，利用KNN对小聚类中的元素进行精确再分配;若两个质心的距离大于Td，则认为它们不属于同一个聚类，不需要对小聚类作任何处理。

2. 4改进算法描述

通过将MCL算法结合KNN算法的思想控制小聚类的生成，首先对MCL产生的聚类进行检测，若产生小聚类，判断是否需要对小聚类进行处理，若需要，则对小聚类中的对象采用KNN算法，利用原始的马尔可夫关系矩阵，找出小聚类中每个对象的K个最相似的对象，并计算所属类的权值，通过KNN将小聚类中的对象合并到权值最大的一类中去，这样可以有效地控制小聚类的形成，满足用户的需求，同时也提高了聚类的质量。K的取值涉及到再分类的精确性:当K取值过大，考虑的周围点多，影响因素多，分类的精度在一定程度上降低; K取值过小，则由于考虑的周围点太少，使得分类过于片面，如何选择一个合适的K值，需要根据具体情况而定，如聚类数量、规模、分类精度要求等。

定义K的取值其中: Ki表示小聚类i对应的K值; vsi表示小聚类i的元素个数; m是一个常数，主要用于调节分类精度，m = max( vsi，Nc) ; Nc为MCL聚类后得到的聚类数，m取vsi与Nc之间的最大值，这样的取值，既避免了小聚类本身元素的干扰，又充分考虑到了训练样本的分类信息，使待分类元素能够在一个合适的K值下更加合理、可靠地进行再分类。

算法具体过程如下。

需要建立一张辅助表Tbad，用于存放经过验证可以单独存在的小聚类。

输入R值、距离阈值Td。

①对所有训练样本求关系矩阵其中: G为关系矩阵，Gij是关系矩阵的第i行第j列的值，表示第i个样本与第j个样本的关系值。

②对数据进行MCL聚类，聚类结束，形成一张聚类信息表Tbinf。

③查看Tbinf中是否有小聚类产生，若Tbinf中有小聚类，则查看Tbad中是否有此聚类的信息:若Tbad中有此聚类的信息，则在Tbinf中继续往下寻找;若Tbad中没有此聚类的信息，则进入④;若Tbinf中没有小聚类存在，则输出。

④计算各聚类的质心，利用质心关系来判断小聚类的分布是否合理，即小聚类的质心与其他聚类的质心距离是否小于给定值Td:若小于Td则说明两个聚类很相似，小聚类产生不合理，需要进行再分配，进入⑤;若大于Td则说明小聚类与其他聚类区别比较明显，可以单独存在，将小聚类的信息写入Tbad表中，返回③。

⑤在基础关系表中找出与小聚类元素最接近的k个元素，以MCL聚类信息表Tbinf为基础，计算k个元素的类别信息，从而确定小聚类元素的最终类别信息，并更新Tbinf表，返回③。

计算公式如下:

C( x) = { Ci| max( W( x，Ci) ) }。( 9)其中: W( x，Ci)表示x属于类别i的权值; xj为x的K个最相似样本的第j个样本; C( x)表示待分类样本的类别信息，待分类样本的类别为W( x，Ci)最大时的类别。

输出:聚类得到的各个簇信息。

其中，Tbad结构如下:

3　算法检验

3. 1检验标准

3. 1. 1模块度指标模块度［9］指标是由Newman等提出来的一种聚类评价标准，也是最广泛被使用的度量聚类质量好坏的指标之一。

公式定义如下:

其中: E为一个k·k的矩阵; eij表示第i行第j列的一个值，也表示聚类i与聚类j的所有边占整个图中所有边的比例，表示矩阵的迹; ai为，即矩阵E中的第i行的所有值相加，表示聚类i与其他聚类相连的边之和占整个图中的边的比例。

3. 1. 2 DB Index指标DB Index［10］准则作为一种评判准则，同时使用了类间距离和类内离散度，基本内容如下。

类内平均离散度

其中: Zi是Ci类的类中心; | Ci|表示Ci类样本数。类间距离

即用两个类中心的距离表示类间距离。DB Index定义为其中:是分类数目。DB Index准则是DB的值越小，说明分类的效果越好。

3. 2实验分析

通过采用UCI机器学习数据库［11］中的Seeds数据集和Iris数据集对本文提出的算法与MCL算法、K均值算法、K调和均值( KHM)算法和模糊C均值算法分别进行聚类质量的比较。Seeds数据集和Iris数据集都是用于检验分类算法的标准数据，因此选用这些标准数据，对算法的验证具有一定的说服力。

首先以模块度指标对MCL聚类与本文提出的混合聚类算法进行比较。在Matlab下进行仿真，结果如图2所示。表1给出了仿真得到的具体数据。

当膨胀参数R值为4～6时，MCL和混合算法聚类效果是一样的，这是由于R的取值比较小没有产生小聚类所致。随着R值的增大，MCL算法产生的小聚类个数增多，由于这些小聚类与其他聚类间的联系比较密切，因此使类之间的区分度比改进后算法的聚类区分度低，由表1可以看出，在相同R值下改进后的算法能得到质量更好的聚类。

图2　Seeds数据集聚类的模块度仿真比较Fig. 62Module simulations comparison of Seeds data aggregation

R值的取值:当R取值太小，聚类粒度过大，整个数据集都被聚为一类，起不到区分的作用; 当R取值过大时，聚类粒度过细，可能导致整个数据集中的每个实例被单独作为一类。膨胀参数R值的选取标准，主要根据聚类评价标准及用户对数据的聚类规模的要求来选择R值。

时间复杂度:由于改进算法是在MCL基础上结合KNN的算法，因此，改进算法在时间复杂度上比MCL时间复杂度多出了KNN部分，即O( N)。其中N为聚类数据的规模，当N的数量只有几百个案例时，改进算法与原算法在时间消耗上没有太大差别;随着N的增大，改进算法与原算法在时间消耗上差距逐渐拉大。

利用DB Index准则对K均值聚类、K调和均值( KHM)算法、模糊C均值聚类算法和本文提出的MCL混合聚类算法进行聚类质量比较，DB Index准则利用对聚类后各聚类之间的距离和聚类内部的离散度来评定聚类的质量，在Matlab下的仿真结果如图3所示，表2为仿真得到的具体数据。

从表2可以看出，当聚类数为2、3时，本文算法与FCM算法比较接近，可能是由于聚类数过少所致。随着聚类数的加大，FCM算法与本文算法得到的聚类质量差距开始变大;随着聚类个数的增加，K均值算法、KHM算法、FCM算法和本文算法的DB Index值都呈上升趋势，即聚类质量都在下降，但其他算法与本文算法相比聚类质量下降速度快，聚类质量比本文算法的聚类质量差。这说明了本文提出的改进算法效果更好，可以得到质量更好的聚类结果。

表1　Seeds数据集聚类的模块度仿真数据Table 1　Module comparison of Seeds data aggregation

图3　4种聚类算法对Iris数据集的DB Index指标仿真Fig. 63Simulations of DB Index of Iris data aggregation with 4 clustering algorithms

表2　Iris数据集聚类的DB Index指标仿真结果Table 2　DB Index of Iris data aggregation

从以上实验看，基于MCL与KNN相结合的混合聚类算法，能够增强聚类的效果，提高类与类之间的区分度。与几种经典的聚类算法进行实验比较，通过对数据的聚类粒度的不断调整分析几种聚类算法在此过程中的聚类性能。对于同一数据样本集，随着聚类粒度的不断细化，聚类得到的数目变大，由于基于MCL与KNN的聚类算法，结合了MCL的全局判断性，即在进行聚类时，是在对全局数据之间的距离关系进行分析的基础上获得的知识为依据进行聚类的，避免了聚类过程中只考虑部分数据的距离关系而导致的片面性，通过膨胀因子拉大差距，从而使实例之间的区分度得到提高，另外通过结合KNN的分类特性，克服了因膨胀因子而导致的过度分离现象(小聚类)，在整个聚类过程中，基于MCL的聚类算法既保证了聚类结果的区分度，又防止了过度分离的现象，使聚类结果在保持实例的区分度和相似度上得到了较好的平衡。与其他算法在整个实验中进行比较，得到了较好的聚类结果，具有一定的典型性。

4　结束语

本文针对MCL自身存在的不足，考虑到KNN算法的分类特性，提出了一种MCL与KNN相结合的混合聚类算法。该混合聚类算法结合了MCL聚类和KNN算法自身的特点，以MCL聚类信息为指导，利用KNN对小聚类进行再分配，从而优化聚类结果，混合聚类算法很好地弥补了MCL聚类过程中容易产生小聚类的不足。与MCL算法相比，在产生小聚类时，混合算法能很好地将小聚类进行再分配，从而提高了聚类的质量。利用传统聚类算法与改进算法进行比较实验，结果证明此方法是有效的、可行的，具有较好的实际应用价值。由于本算法是在MCL基础上结合了KNN分类算法，改进算法的时间复杂度比MCL的时间复杂度多出O( N)，即KNN的时间复杂度。随着数据规模的增大或者小聚类数量的增多，改进算法所消耗的时间将逐渐增大。此算法比较适合数量中等的数据进行聚类，既能保持比MCL算法更好的聚类性能，又能避免消耗过多的时间。

参考文献:

［1］乔丽，姜慧霖，贾世杰．基于改进k-means聚类的案例检索策略［J］．计算机工程，2011，37 ( 5) : 193－195．

［2］乔丽，姜慧霖．一种k-means聚类的案例检索算法［J］．计算机工程与应用，2011，47 ( 4) : 185－187．

［3］Chen Y X，Tu L．Density-based clustering for real-time stream data［C］/ /Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2007: 133－142．

［4］赵慧，刘希玉，崔海青．网格聚类算法［J］．计算机技术与发展，2010，20 ( 9) : 83－85．

［5］van Dongen S．Performance criteria for graph clustering and Markov cluster experiments［R］．Amsterdam: National Research Institute for Mathematics and Computer Science in the Netherlands，2000．

［6］温菊屏，钟勇．图聚类的算法及其在社会关系网络中的应用［J］．计算机应用与软件，2012，29( 2) :161－163．

［7］Akama H，Miyake M，Jung J．How to take advantage of the limitations with Markov clustering—the foundations of branching Markov clustering ( BMCL)［C］/ /The Third International Joint Conference on Natural Language Processing．Hyderabad: the Asian Federation of Natural Language Processing，2008: 901－906．

［8］孙荣宗，苗夺谦，卫志华，等．基于粗糙集的快速KNN文本分类算法［J］．计算机工程，2010，36( 24) :175－177．

［9］Newman M E J，Girvan M．Finding and evaluating community structure in networks［J］．Physical Review E，2004，69 ( 2) : 026113．

［10］罗兰，曾斌．基于时序向量聚类的周期关联规则发现算法［J］．计算机工程，2010，36 ( 19) : 110－112．

［11］Frank A，Asunclon A．UCI machine learning repository ［EB/OL］．［2011－11－02］．http: / /archive．ics．uci．edu/ml．

Hybrid clustering algorithm based on KNN and MCL

NIU Qin-zhou，CHEN Yan
( College of Information Science and Engineering，Guilin University of Technology，Guilin 541004，China)

Abstract:MCL is a graph clustering algorithm．With the characteristics of MCL computational process，MCL is prone to producing small clustering and separating edge nodes from the groups．A hybrid clustering based on MCL combined with KNN algorithm is proposed．Hybrid algorithm improves the quality of clustering by reclassification of elements in small clustering by KNN classification characteristics and clustering tables required by MCL clustering．Experiments prove that this method is feasible and the improved algorithm can enhance the quality of clustering．

Key words:MCL; clustering; KNN; small clustering; reclassification

作者简介:牛秦洲( 1956—)，男，教授，研究方向:制造业信息化、人工智能。

基金项目:国家自然科学基金项目( 51365010) ;广西科学研究与技术开发计划项目(桂科合1346011－10)

收稿日期:2014－03－24

doi:10. 3969/j．issn. 1674－9057. 2015. 01. 029

文章编号:1674－9057( 2015) 01－0181－06

文献标志码:A

中图分类号:TP301. 6

引文格式:牛秦洲，陈艳．基于MCL与KNN的混合聚类算法［J］．桂林理工大学学报，2015，35 ( 1) : 181－186．