牛秦洲，陈艳(桂林理工大学信息科学与工程学院，广西桂林　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聚类的过程中，不是简单地求出样本之间的关系来进行聚类判断，而是在这种关系的基础上通过膨胀和扩展操作来获得关于样本之间的更深层的知识来进行聚类。……