基于 Chameleon算法和谱平分法的聚类新方法

张 友,赵凤霞

(1.大连民族学院理学院,辽宁大连 116605;

2.秦皇岛职业技术学院信息工程系,河北秦皇岛 066100)

基于 Chameleon算法和谱平分法的聚类新方法

张 友1,赵凤霞2

(1.大连民族学院理学院,辽宁大连 116605;

2.秦皇岛职业技术学院信息工程系,河北秦皇岛 066100)

在分析传统的聚类算法优越性和存在不足的基础上,基于 Chameleon算法和谱平分法的思想提出了一种新的聚类方法。相比传统聚类算法而言此算法克服了如 k-means算法、E M算法等传统聚类算法在聚类不为凸的样本空间时容易陷入局部最优的缺点,能在任意形状的样本空间上聚类,且收敛于全局最优解,并且可以降低噪声和离群点的影响,提高了算法的有效性。在 UCI数据集和 5个特殊的二维数据点组成的数据集上进行了实验,证明了本方法的有效性。

聚类算法;Chameleon算法;谱平分法;k-mean算法;EM算法;不为凸的样本空间

聚类分析是机器学习领域中的一个重要分支,是人们认识和探索事物之间内在联系的有效手段。所谓聚类(clustering)就是将数据对象分组成为多个类或簇 (cluster),使得在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。聚类算法有很多种,需要根据应用所涉及的数据类型、聚类的目的以及具体应用要求来选择合适的聚类算法。如果利用聚类分析作为描述性或探索性的工具,那么就可以使用若干聚类算法对同一个数据集进行处理以观察可能获得的有关 (数据特征)描述[1]。传统的聚类算法,如k-means算法、EM算法等都是建立在凸球形的样本空间上,但当样本空间不为凸时,算法会陷入局部最优。为了能在任意形状的样本空间上聚类,且收敛于全局最优解,本文结合 Chameleon算法和谱平分法提出了一类新型的聚类算法 (以下简称 C-谱平算法)。该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,然后构造稀疏图矩阵 (K-最近邻图矩阵),并计算该稀疏矩阵的特征值和特征向量,然后选择合适的特征向量聚类不同的数据点。此算法能够有效地聚类存在噪声和离群点的空间数据,而且对簇的大小、形状和密度没有要求,能在任意形状的样本空间上聚类,且收敛于全局最优解。

1 Chameleon算法与谱平分法

通常聚类分析算法可以划分为以下几类:划分方法 (partitioning method)、层次方法 (hierarchical method)、基于密度的方法 (density-based method)、基于网格的方法 (grid-based method)、基于模型的方法(model-based memod)。

Chameleon算法[2]是使用动态建模的层次聚类方法,Chameleon力求合并这样的一对簇,合并后产生的簇,用接近性和互连性度量,与原来的一对簇最相似。因为这种方法依赖簇对而不是全局模型,Chameleon能够处理包含具有各种不同特性簇的数据。

谱平分法[3]建立在图论中的谱图理论基础上,其基本思想是一个有 n个节点的无向图 G的Laplace矩阵是一个 n×n维的对称矩阵 L。L的对角线上的元素 Lii是节点 i的度,而其他非对角线上的元素Lij则表示节点 i和节点 j的连接关系。如果这两个节点之间有边连接,则 Lij值为 -1,否则为 0。我们可以将矩阵 L表示成 L=K-A,其中 K是一个对角矩阵。矩阵 L有一个特征值为0,且其对应的特征向量为 l=(1,1,...,1)。可以从理论上证明,不为零的特征值所对应的特征向量的各元素中,同一个社团内的节点对应的元素是近似相等的。

2 C-谱平算法步骤

步骤流程如图 1。

图 1 算法步骤图

步骤1:将数据集按照给定的相似度公式构造相似度矩阵 Sn×n(其中 n为数据集中数据的个数,Lij表示第 i个数据与第 j个数据的相似度)。

步骤2:根据相似度矩阵构造稀疏图,从而产生 k-最近邻图。把相似度矩阵中每个数据和它的 k个最近邻 (即最相似的数据)用 1表示,其余用 0表示。产生的 k-最近邻图的邻接矩阵用 SK表示。

步骤3:求 k-最近邻图的 Laplace矩阵 L。

步骤4:用谱平分法进行聚类。计算矩阵 L的前 x个最大特征值对应的特征向量,使其在 Rx空间中构成与原数据一一对应的表述,然后在 Rz空间中进行聚类。具体步骤如下:

(1)计算矩阵 L的前x个最大特征值所对应的特征向量x1,...,xx(必要时需作正交化处理),构造矩阵 X=[x1,…,xx]∈Rn×k;选取矩阵 L的前x个最大的特征值所对应的特征向量的原因在于:对于存在 k个理想的彼此分离簇的有限数据集,可以证明矩阵 L的前x个最大特征值为 1,第x+1个特征值则严格小于 1,二者之间的差距取决于这x个聚类的分布情况。当聚类内部分布得越密,各聚类间分布得越开时,第x+1个特征值就越小,此时,以矩阵 X中的每行作为 x维空间中的一个点所形成的 x聚类。它们将彼此正交地分布于x维空间中的单位球上,并且在单位球上形成这x聚类对应着原空间中所有点形成的x个聚类。

(2)将矩阵 X的行向量转变为单位向量,得到矩阵 Y,即

(3)将矩阵 Y的每一行看作是 Rx空间中的一个点,对其使用 k均值算法或任意其他经典聚类算法,得到 k个聚类。

(4)将数据点yi划分到聚类 j中,当且仅当Y的第 i行被划分到聚类 j中。

3 实验结果

3.1 UCI数据集实验结果

为了证明 C-谱平算法的有效性,本文首先在UCI上选取了若干数据集,并通过与其他方法比较,证明了 C-谱平算法的有效性。数据集的说明见表 1。与其他 3种方法在聚类精度上的比较如图 2。

表 1 数据说明

图 2 各种算法在表 1所列数据集上的聚类精度比较

3.2 二维数据点组成的数据集实验结果

为了进一步说明 C-谱平算法能在任意形状的样本空间上聚类,且收敛于全局最优解,在 5个由二维数据点组成的数据集上进行了实验,数据集的几何形状如图 3。DS1包含 5个大小、形状、密度各不相同的聚类,此外还包含有异常点;DS2由两个相邻的聚类组成,每个聚类中不同区域的密度各不相同;DS3由 6个形状、大小、方向各不相同的聚类组成,与此同时这些聚类还包含了异常点,彼此交错在一起;DS4,由 8个不同形状、大小、方向的聚类组成,从空间上看有的聚类包含在另一个聚类中间,DS4同样包含一些随机点和人为的异常点 (如一些汇集成垂直条纹的点);DS5包括了 8个不同形状、不同大小、不同密度和不同方向的聚类,同时也含有噪声数据点。这些数据集有一个挑战性的特征,即聚类之间彼此距离太近,而且聚类密度彼此不同。数据集的大小从6 000到 10 000数据点,精确的大小如图 3。图 4为某些经典传统聚类算法与 C-谱平算法在这些数据集上的聚类精度比较,从结果可以看出 C-谱平算法的聚类精度远远高于传统的聚类方法,从而证明了 C-谱平算法的有效性。

图 3 实验数据集

图 4 不同方法的聚类精度比较

4 结 语

本文结合 Chameleon算法和谱平分法的优点,提出了一种新的聚类算法,即 C-谱平算法。相比其他聚类算法而言本文算法克服了如 kmeans算法、EM算法等传统聚类算法在聚类不为凸的样本空间时容易陷入局部最优的缺点,能在任意形状的样本空间上聚类,且收敛于全局最优解。并且可以降低噪声和离群点的影响,提高了计算的有效性。这种聚类算法可以用于图像处理、数据挖掘等领域。

尽管 C-谱平算法在实验中取得了很好的效果,但仍有许多还需研究和解决的问题。接下来的工作主要包括 3个方面:(1)如何构造相似矩阵S:相似矩阵的构造都依赖于领域知识,而没有给出通用的规则,系统地研究本文聚类中相似矩阵的构造问题将是未来研究的一个方向。(2)如何处理特征向量:用多少个特征向量进行聚类,如何选取、计算及使用这些特征向量等问题均没有得到很好的理论解释,这些都是未来急需解决的问题。(3)如何选取 Laplacian矩阵:如何根据具体环境选择合适的Laplace矩阵,还需要进行大量的理论研究和实验工作。

[1]JA IN A,MURTY M,FLYNN P.Data clustering:A Review[J].ACM Computing Survey,1999,31(3):264-323.

[2]KARYPIS G,HAN E-H,KUMAR V.Chameleon:A hierarchical clustering algorithm using dynamic modeling[J].IEEE Computer,1999,32(8):68-75.

[3]ZHANG Shihua,WANG Ruisheng,ZHANG Xiangsun.Indentification of overlapping community structure in complex networks using fuzzy c-means clustering[J].Physica A,2007(374):483-490.

[4]H IGHAM D J,KALNAA G,M ILLA K.Spectral clustering and its use in bioinformaties[J].Journalof Computational and Applied mathematics,2007,20(4):25-27.

[5]KANUNGO T,MOUNTD M,NETANYAHU N,et al.An efficient k-means clustering algorithm.Analysis and implementation[J].IEEE Trans Pattern Analysis and Machine Intelligence,2002(24):881-892.

[6]KANUNGO T,MOUNT D M,NETANYAHU N,et al.A local search approximation algorithm for k-means clustering[J].Computational Geometry:Theory and Applications,2004(28):89-112.

[7]杨久俊,邓辉文,滕姿.基于混合粒子群优化算法的聚类分析[J].计算机工程与设计,2008,29(22):5820-5823.

[8]郭维维,韩萌.基于最小描述长度和遗传算法的属性选择方法[J].大连民族学院学报,2009,11(1):85-87.

A New ClusteringM ethod Based on the Chameleon Algorithm and the Spectral Bisection M ethod

ZHANG You1,ZHAO Feng-x ia2
(1.College of Science,Dalian NationalitiesUniversity,Dalian Liaoning 116605,China;2.Department of Infor mation Engineering,Qinhuangdao Institute of Technology,Qinhuangdao Hebei 066100,China)

W ith analysis of advantages and disadvantages of traditional clustering algorithms,we proposed a new clusteringmethod based on the Chameleon algorithm and the spectral bisection method.Unlike traditional clustering algorithms,this algorithm overcomes a disadvantage of some traditional clustering algorithms such as the k-means algorithm and the EM algorithm,that is,they are prone to local optimum when clustering on a nonconvex sample space.It is capable of clustering on a sample space of any shape and converging to the globaloptimal solution.It also reduces the influence of the noise and outliers,increasing its effectiveness.We carried out exper iments on the UCI data sets and five data sets of special two-dimensional data points and proved the effectiveness of the method.

clustering algorithm;the Chameleon algorithm;the spectral bisectionmethod;the k-means algorithm;the EM algorithm;nonconvex sample space

TP311

A

1009-315X(2010)01-0061-04

2009-07-08

张友 (1960-),男,吉林四平人,教授,主要从事粗糙集、代数学研究。

(责任编辑 刘敏)