密度敏感模糊核最大熵聚类算法

李烨桐,郭 洁,祁 霖,刘 璇,阮鹏宇,陶新民

（东北林业大学工程技术学院,黑龙江哈尔滨 150040）

1 引言

聚类,即将数据集划分为多个组的过程[1—2].作为一个有用的数据分析工具,聚类在模式识别[3—5]、数据挖掘[6—8]、图像分割[9—10]等方面应用广泛.聚类的主要目标是将给定的多属性数据样本集划分成若干组,使得同一组中的样本彼此相似,不同组中的样本彼此相异[11].聚类分析能发现隐含在数据中的分布特征,为进一步充分有效地利用数据获取有用信息奠定基础.现阶段常用的聚类方法主要有[12]:划分方法[13]、层次方法[14]、基于密度的方法[15]、基于网格的方法[16]以及基于模型的方法[17]等.

作为一种常用的基于划分方法的聚类算法,模糊C均值聚类算法[18]（fuzzy C-means clustering algorithm,FCM）已经在模式分类、医学图像分割等领域得到了广泛的应用.虽然FCM能够在聚类过程中较好地提取原始数据的结构信息,但其要求数据满足凸集假设,因此对非线性非高斯的数据聚类效果通常不理想[19].近年来,学者们相继提出了各种基于模糊C均值聚类算法的改进算法.在文献[20]中,康家银等人提出了一种核模糊C均值聚类算法.该算法变欧式距离为核距离,将低维输入空间的非线性问题转化为高维输入空间的线性问题,从而提高了算法的性能.然而,该算法在使用核模糊C均值聚类算法进行聚类分析时,并未考虑到各个属性的重要程度.于是Jin zhou等人提出了最大熵规范化权重核模糊C均值聚类算法,该算法能够在聚类过程中按照数据属性的重要程度进行不同属性权重的设置,使得聚类结果更加合理[21].

尽管改进后的模糊C均值聚类算法取得了较好的聚类性能,但因C均值聚类算法本身易受初始化聚类中心、不完全数据以及噪声敏感等问题的影响导致聚类结果在部分应用场合产生偏差,因而聚类准确性下降[22].与模糊C均值聚类算法相比,最大熵聚类算法因不受初始聚类中心影响,且能抵消不完全数据和噪声敏感问题的影响,同时具有清晰的物理意义和明确的数学特征,近年来受到了学者们的广泛关注[23].为了克服最大熵聚类算法对初始聚类中心选取敏感性的缺点,文献[24]提出了一种初始聚类中心优化的加权最大熵核模糊聚类算法（weighted kernel maximum entropy fuzzy C-means clustering algorithm,WKMEFCM）.为提升最大熵聚类算法面对变化数据时的鲁棒性,文献[25]通过引入最大中心间隔项以及缩放因子η,构造出了新的η型最大中心间隔极大熵聚类（ηmaximum center interval maximum entropy clustering,ηMCSMEC）算法.尽管改进算法较好地提升了算法聚类性能,然而,最大熵聚类算法本身在聚类过程中易受正则化系数的影响而出现趋同现象,即部分聚类中心趋向同一点甚至重叠,导致聚类结果失真,准确性下降.同时,该算法对数据内在形状依赖性强,聚类中心易受样本数据分布差异的影响,且在处理非线性非高斯的数据时存在局限性,使其无法准确地进行聚类.

鉴于此,本文提出一种密度敏感模糊核最大熵聚类算法.该算法首先通过核函数将原始非线性非高斯的数据转化为核空间数据集,然后利用核函数的相似性抵消聚类过程中不属于该聚类样本数据对聚类中心求解的影响,同时解决了算法在聚类过程中因受正则化系数的影响而出现趋同现象的问题.最后引入相对密度的概念,消除样本数据在特征空间的分布差异对聚类中心求解的影响.最终实现对非线性非高斯的数据准确聚类.实验部分将本文提出的聚类算法与其他算法进行比较分析,结果表明本文提出的聚类算法具有更好的准确性和稳定性.

2 最大熵聚类算法

最大熵原理[23]由E.T.Jaynes于1957年提出.其主要思想是:在只掌握部分关于未知分布知识的条件下,应选取符合这些知识但熵值[26—27]最大的概率分布.最大熵方法在根本上解决的是条件约束问题,即在所有满足约束条件的模型中选择熵值最大的模型.最大熵聚类算法的流程如下.

首先定义聚类模糊集熵,对于某个具体的聚类c,其聚类模糊集熵E(c)为

其中:xj是样本,uc(xj)是xj ∈c的隶属度,n是样本个数.

然后确定总的聚类模糊集熵,假定一个数据集为X,如果把这些数据划分成C类,那么对应有C个聚类c,样本j属于某一类i的隶属度为uij,其总的聚类模糊集熵为

令已知的约束条件为损失函数,并令其等于k,即

由熵的表达式可知,熵为凹函数,取反后是凸函数,要求熵的最大值就是求取反后函数的最小值.因此利用拉格朗日数乘法构造拉格朗日函数,其式如下:

分别对α,λ,uij求导得式（7）—（9）

由式（9）求得uij的表达式

将式（12）代回至uij表达式中,得到uij的迭代式（13）

将式（6）对ci求导得到类中心的迭代式（15）

由上述分析可知,最大熵聚类算法最终的迭代式与Li等人提出的高斯聚类方法（Gaussian-clustering method,GCM）[28—29]的公式相似.其中GCM的目标函数为

可见最大熵聚类算法与GCM具有一致性.因此可以说最大熵聚类算法不仅具有清晰的物理意义,而且有定义明确的数学特征.

最大熵聚类算法是在满足所有约束的条件下,取熵值最大的情况进行聚类的算法.根据熵集中原理,大多数可能出现的情况都集中在最大熵值的附近.因此,最大熵聚类算法的聚类结果比较准确.并且对于数据集来说,并非所有待聚类的样本数据都具有理想化的特征,其中不完全数据或者噪声数据会影响聚类结果的准确性.而使用最大熵聚类算法时,得到的聚类结果不仅与已知数据相吻合,还对不完全数据和噪声数据做出了最精确的估计,使得聚类结果偏差最小,从而有效消除了不完全数据和噪声敏感问题对算法性能的影响,提高了聚类准确性.

虽然最大熵聚类方法具有诸多优点,但依旧存在不足.根据上述分析可知,最大熵聚类算法当采用欧氏距离时在本质上与高斯聚类算法相似,因此该算法只能对高斯分布的数据集进行聚类,而对于非线性非高斯的数据集而言,通过该算法通常无法得到合理的聚类结果.另外,该算法的聚类结果易受正则化系数α的影响而出现趋同的现象,即多个聚类中心容易聚集在同一点上,因此会严重影响聚类的准确性.

3 密度敏感模糊核最大熵聚类算法

为解决以上问题,本文对最大熵聚类算法做出改进,提出了密度敏感模糊核最大熵聚类算法（density sensitive kernel maximum entropy clustering algorithm,DSKME）.该算法通过引入核函数,即通过一个非线性映射Φ:x →F(x ∈Rp →Φ(x)∈Rq,q ＞p)将输入空间x变换至高维甚至无限维特征空间,从而将原始非线性非高斯分布的数据转化为核空间数据,核函数的引入,不仅解决了最大熵聚类算法依赖数据内在形状的问题,而且消除了正则化系数对聚类中心求解的影响,进而抑制了算法的趋同性.同时,考虑到样本数据在特征空间的分布差异对聚类中心点求解的影响,本文引入相对密度的概念,通过相对密度项弱化样本数据分布差异对聚类中心求解的影响,从而提高聚类的准确性.

3.1 密度敏感模糊核最大熵聚类算法

首先定义密度敏感模糊核最大熵聚类算法的目标函数为

其中:C为聚类个数,n为样本个数,uij为样本j在第i类中的隶属度,α为正则化权重系数,ci为i类的聚类中心,ρj为样本xj的相对密度.

其次通过构造拉格朗日函数求得其迭代式.构造拉格朗日函数

对式（20）中的uij求导得到uij表达式

将式（23）代入式（19）得

将式（26）代回至式（23）中得到uij的迭代式

接下来,求解类中心的迭代式.将式（20）中L(U,C,α,λ)对ci求导,得

已知

将式（29）代入式（28）中得

由于核函数使用的类别不同,所以导致该算法的结果没有进行显示表达.因此本文以一种常见的核函数,即高斯核函数进行进一步推导.

由此推得

所以将式（33）代入式（31）中求得

3.2 相对密度估计方法

本文所采用的相对密度ρj的估计方法是Parzen window算法[30].

设X=[x1x2··· xn]为目标训练样本集,其中n为训练样本的个数.对于其中的任意一个训练样本xj,其相对密度ρj的定义如下:

其中:

为进一步说明样本数据在特征空间的分布差异对聚类中心点求解造成的影响,本文进行了对比试验,采用了125个均值为[0,0],方差为[1,1]和25个均值为[1,2],方差为[3,3]的高斯分布数据集,其中ω=5,s=1.利用密度敏感模糊核最大熵聚类算法与模糊核最大熵聚类算法分别计算聚类中心点,其位置的比较如图1所示.

由图1可以看出,传统的模糊核最大熵聚类算法由于只考虑距离因素,因此得到的中心点会偏向样本点分散的一方.而本文提出的算法通过引入相对密度项,使得样本数据分布密集的相对密度高,对聚类中心点的决定作用大;样本数据分布稀疏的相对密度低,对聚类中心点的决定作用小.因此,本文提出的密度敏感模糊核最大熵聚类算法,在解决最大熵聚类算法对数据内在形状的依赖问题的同时,也弱化了样本数据分布差异对聚类中心求解的影响.

图1 不同算法聚类中心点位置的比较图（方形为密度敏感模糊核最大熵聚类算法的聚类中心;圆形为模糊核最大熵聚类算法的聚类中心）Fig.1 Comparison diagram of the location of clustering center point by different algorithms（Square is the clustering center of the DSKME algorithm;Circle is the clustering center of the fuzzy kernel maximum entropy clustering algorithm）

3.3 算法流程

由上述分析可知,密度敏感模糊核最大熵聚类算法流程如下:

步骤1设置算法参数:核函数和核参数、正则化系数α以及密度确定算法参数:权重ω和平滑参数s;

步骤2根据数据特征确定聚类个数C和最大迭代次数Itexmax,2＜C≤Itexmax,最大U变化停止条件阈值ε;

步骤3通过密度估计算法求出相对密度ρj,并随机初始化一个隶属度U,其中uij ∈[0,1];

步骤4根据隶属度U,利用类中心的迭代式（39）计算类中心C;

步骤5由步骤3—4得出隶属度U和类中心C,根据算法的目标函数式（18）计算J的值;

步骤6再根据类中心C,利用隶属度的迭代式（27）更新隶属度U,并回到步骤4更新聚类中心C,一直循环直到达到停止条件.

3.4 参数的理论分析

本文所提出的密度敏感模糊核最大熵聚类算法（DSKME）的3个参数分别为正则化系数α、相对密度ρj和核参数σ.其中正则化系数α是影响算法性能最重要的因素,因此本文重点讨论正则化系数对算法性能的影响.

由上节式（27）,得

令式（41）中,

则当i=mj时,隶属度uij的迭代公式可以写成

其中

根据上述分析可得,当i=mj时,隶属度uij随着α增大而单调递增.下面讨论当i/=mj时,隶属度uij随参数α的变化趋势.

当i/=mj时,由式（42）推得

其中:

根据式（43）可以得到以下不等式关系:

式中:

l为满足

的聚类个数.根据不等式关系式（44）和uij表达式（43）可以写出以下新的不等式关系:

其中

如k=mj,则当α增大时,exp(αρj ·D)的值也随之增大,隶属度uij的值随着α值的增大而减小.可得,当i/=mj时,uij随着α增大而单调递减.

由上述分析总结得:随着α的值增大,当i=mj时,隶属度uij随α递增;当i/=mj时,隶属度uij随α递减.因此聚类区域会随着α值的增大而增大,等位线会向远离聚类中心点的方向移动,使得聚类结果不够精确,样本彼此间的聚类隶属度区分能力下降.极端情况下,若α取足够大,根据上述公式可知:当i=mj时,归属i聚类的样本隶属度均为uij=1.相反,随着α的值减小,当i=mj时,隶属度uij随α递减;当i/=mj时,隶属度uij随α递增.因此聚类区域会随着α值的减小而相应的减小,等位线会向靠近聚类中心点的方向移动,使得聚类结果更加精确,样本间聚类隶属度区分能力提升.

为解决上述矛盾,避免原最大熵聚类算法因α取值较小而导致聚类中心趋同的现象,本文利用的相似性抵消不属于mj聚类的样本对聚类中心更新的影响.根据式（39）,取高斯核函数时

由上述高斯核函数公式可知,当xj不属于时,距离会增大,会减小,从而抵消了样本xj对不属于该聚类的聚类中心更新的影响.

另外,由于σ与成反比例关系,当σ增大时会减小.在极端情况下若参数σ取值趋近于无穷大时,的值趋近于0,此时高斯核函数失去了对参数α的制约效果.因此,在使用高斯核函数时,为了能有效消除正则化系数α对算法趋同性的影响,参数σ的设置不能过高.

为了详细地说明上述分析结果,本文在α取值分别为0和0.1的条件下,对最大熵聚类算法和密度敏感模糊核最大熵聚类算法的聚类结果进行了对比.实验对均值为[0,0],方差为[1,1]和均值为[-5,-5],方差为的各125个高斯分布的样本数据进行聚类,聚类个数为2.经过标准化处理后的数据聚类结果如图2—4所示.由聚类结果图可以看出,在α取值较小的条件下,如取值为0.1时,最大熵聚类算法的聚类结果趋同性明显,两个聚类中心点几乎重叠,如图2所示.

图2 α=0.1时最大熵聚类算法聚类结果Fig.2 The clustering result of the ME when α=0.1

而在同样的参数设置条件下,使用本文提出的DSKME聚类算法进行聚类,聚类结果并没有出现趋同现象,如图3所示.特别地,当α取值更小甚至取0时,受的影响,DSKME算法的聚类结果仍没有出现趋同现象.该实验结果进一步说明本文提出的密度敏感模糊核最大熵聚类算法能有效解决原最大熵聚类算法因受参数α的取值影响而导致的聚类中心趋同问题.

图3 α=0.1时密度敏感模糊核最大熵聚类结果Fig.3 The clustering result of DSKME when α=0.1

图4 α=0时密度敏感模糊核最大熵聚类结果Fig.4 The clustering result of DSKME when α=0

4 实验分析

本文通过4个实验来测试密度敏感模糊核最大熵聚类算法（DSKME）的聚类效果和算法性能.首先分析和讨论算法参数对聚类结果及算法性能的影响,通过比较不同参数设置条件下的聚类结果,得出参数间关系.其次,实验选取7个人工数据集和9个UCI数据集分别用本文提出的DSKME算法与模糊C均值聚类算法（FCM）、核模糊C均值聚类算法（kernel-based fuzzy C-means clustering algorithm,KFCM）、最大熵规范化权重核模糊C均值聚类算法（maximum entropy normalized weight kernel fuzzy C-means clustering algorithm,KEWFCM）、最大熵聚类算法（maximum entropy algorithm,ME）、改进的初始聚类中心优化的加权最大熵核模糊聚类算法（WKMEFCM）和η型最大中心间隔极大熵聚类（ηMCSMEC）算法进行聚类,并比较不同算法下的聚类结果,最后对7种算法的鲁棒性进行比较分析.实验环境:Windows 7操作系统,CPU:Intel i7,3.4 G处理器,仿真软件为MATLAB 2010b.不同算法的参数设置统一为σ2=1.25,α=2,ε=1×e-6,Itexmax=2000.

4.1 参数对聚类结果和算法性能的影响

为了直观地说明参数设置对聚类结果和算法性能的影响,本实验随机选择了均值为[0,0],方差为[1,1]和均值为[-5,-5],方差为[1,1]的各125个高斯分布的样本数据进行聚类.经过标准化处理后的数据聚类结果分布如图5—10所示.其中,α的取值分别为[0,0.001,0.01,0.1,1,10,100],核函数取高斯核函数,核参数为1,相对密度的参数设置如下:权重ω=5,平滑参数s=1.

图5 α=0高斯核参数为1时聚类结果Fig.5 Clustering result of DSKME when α=0 and the Gaussian kernel parameter is 1

图6 α=0.001高斯核参数为1时聚类结果Fig.6 Clustering result of DSKME when α=0.001 and the Gaussian kernel parameter is 1

图中红色圆圈表示聚类中心,等位线分布在样本点周围.通过聚类效果图5—10可以看出,随着α值增大,等位线向远离聚类中心的方向移动.这是由于等位线的位置与数据样本点的隶属度uij有关.根据上节参数的理论分析,再结合聚类效果图可知,在α取值较大的条件下,属于该聚类样本数据的uij随α增大而增大,而不属于该聚类样本数据的uij随α值增大而减小.所以等位线会向远离该聚类中心点的方向移动,即会出现图10—11中等位线聚集在两聚类中间的现象.这说明此时的样本隶属度的区分能力下降.相反,在α取值较小的条件下,属于该聚类样本数据的uij随α值减小而减小,而不属于该聚类样本数据的uij随α值减小而增大,所以等位线会向靠近聚类中心点的方向移动,即会出现图5—7中等位线聚集在聚类中心周围的现象.这也说明样本间的隶属度区分能力提升,聚类结果清晰.其次,通过图5—10的聚类效果图可以看出,随着α值的增大,两个聚类中心向两点距离增大的方向移动.这是由于聚类中心点的位置与样本点的隶属度有关.由上节参数的理论分析,并观察图5—8可以发现,在α取值较小的条件下,甚至取α=0时（如图5）,本文提出的DSKME算法在聚类过程中并没有出现原算法的趋同现象.这是由于在高斯核函数的影响下,不属于该聚类的样本数据对更新计算聚类中心ci的影响变小,从而减少了正则化系数α过小对聚类中心求解的影响,使得聚类中心ci不会出现过度偏移的现象.

图7 α=0.01高斯核参数为1时聚类结果Fig.7 Clustering result of DSKME when α=0.01 and the Gaussian kernel parameter is 1

图8 α=0.1高斯核参数为1时聚类结果Fig.8 Clustering result of DSKME when α=0.1,and the Gaussian kernel parameter is 1

图9 α=1高斯核参数为1时聚类结果Fig.9 Clustering result of DSKME when α=1 and the Gaussian kernel parameter is 1

图10 α=10高斯核参数为1时聚类结果Fig.10 Clustering result of DSKME when α=10 and the Gaussian kernel parameter is 1

图11 α=100高斯核参数为1时聚类结果Fig.11 Clustering result of DSKME when α=100 and the Gaussian kernel parameter is 1

综上所述,在参数α和高斯核函数的相互影响下,本文提出的密度敏感模糊核最大熵聚类算法解决了原来最大熵聚类算法聚类中心趋同问题,使聚类结果更准确.

4.2 仿真数据集的聚类结果及参数对性能影响

4.2.1 实验评价指标

为了对聚类效果进行对比分析,实验中使用两种评价指标:CE（classification entropy）和XB（Xie and Beni’s index）指标[31]来评价聚类结果的好坏,两种指标的值越小,表明聚类效果越好.

其中:n为样本数,C为聚类个数,uij为样本隶属度.

XB是聚类内部数据到中心点的距离之和与不同聚类中心点之间距离之和的比值.聚类内部数据到中心点的距离越小,聚类之间中心点的距离越大,则聚类效果越好.即XB的值越小,聚类效果越好.

其中:n为样本数,C为聚类数,uij为样本的隶属度,vi,vj为i,j的聚类中心.

4.2.2 实验分析

实验选取了7个人工合成数据集[32]:Motortype数据集、Eyes数据集、LineBlobs数据集、Size5数据集、Twenty数据集、Square4数据集和Long1数据集,并对7个数据集分别使用不同的算法进行聚类.初始聚类个数分别为3,3,3,4,20,4,2,算法的迭代次数均为100次.核函数取高斯核函数,核参数为1,相对密度的参数设置为:权重ω=5,平滑参数s=1.实验将本文算法与模糊C均值（FCM）、核模糊C均值（KFCM）、最大熵规范化权重核模糊C均值（KEWFCM）、最大熵聚类算法（ME）、改进的初始聚类中心优化的加权最大熵核模糊聚类算法（WKMEFCM）和η型最大中心间隔极大熵聚类（ηMCSMEC）算法的聚类结果进行比较,并分别计算出评价指标CE和XB的值,如表1所示.

表1 不同聚类算法对7个合成数据集关于CE和XB的统计结果Table 1 Statistics of different clustering algorithms on seven synthetic dataset in terms of CE and XB

由表1可以看出,除了Twenty数据集的CE指标外,最大熵聚类算法其余数据集的评价指标均优于FCM算法.这说明最大熵聚类算法能有效解决传统FCM算法因受不完全数据和噪声敏感的影响而导致的聚类准确性下降的问题.同时,本文提出的DSKME算法除了Sizes5、Twenty和Square4数据集的CE指标外,其余数据集聚类结果的CE和XB性能评价指标均优于其他算法.这说明本文提出的DSKME聚类算法能有效消除正则化系数对聚类结果的影响,进而抑制了最大熵聚类算法的趋同性,提高了算法聚类的性能.

为了更直观地理解数据分布的相对密度对聚类结果的影响,本实验分别使用最大熵聚类算法和密度敏感模糊核最大熵聚类算法对7个人工数据集进行聚类,聚类结果如图12—18所示.

图12 Motortype数据集Fig.12 Motortype dataset

图13 Eyes数据集Fig.13 Eyes dataset

图14 LineBlobs数据集Fig.14 LineBlobs dataset

其中,图12、图15和图17中两种算法的聚类结果没有明显差别,这是因为原数据分布的相对密度差别很小,所以对聚类结果的影响不明显.然而,图13—14、图16和图18中显示两种算法的聚类结果差异明显,这是因为原数据分布的相对密度差别很大,所以密度敏感模糊核最大熵聚类算法的聚类中心明显偏向数据分布相对密度大的区域.该现象说明本文提出的算法通过引入相对密度项,能有效消除样本数据在特征空间的分布差异对求解聚类中心问题造成的影响,大大提高了聚类中心求解的准确性.通过观察图16可发现,聚类个数同样为20,但最大熵聚类算法趋同性的作用使得聚类中心出现了重叠的现象,部分聚类结果被消除.而本文提出的DSKME聚类算法通过利用高斯核函数的相似性,抵消了正则化系数α对计算聚类中心点的影响,使得聚类结果没有出现趋同的现象,聚类的个数没有发生变化.另外,观察图中的等位线分布可以发现,本文提出的算法得到的隶属度值更符合数据的聚类分布特征,区分能力更加明显,聚类效果更加清晰.

图15 Size5数据集Fig.15 Size5 dataset

图16 Twenty数据集Fig.16 Twenty dataset

图17 Square4数据集Fig.17 Square4 dataset

图18 Long1数据集Fig.18 Long1 dataset

综合上述分析可知,本文提出的DSKME聚类算法通过引入相对密度项和高斯核函数,不仅消除了样本在特征空间的分布差异对聚类中心求解的影响,提高了聚类结果的准确性.而且通过核函数的相似性抵消了正则化系数α对计算聚类中心点的影响,避免了原最大熵聚类算法趋同的现象,使算法更加稳定.

4.2.3 参数对算法性能的影响

为了研究不同平滑参数s和密度权重ω对该方法聚类性能的影响,本文在人工数据集Eyes,Twenty和Square4上分别进行了聚类实验.一是分析了该方法在不同平滑参数s（0.1～30）下的聚类性能.另一个是通过将密度权重ω从0增加到10,间隔为1来分析密度权重对算法聚类性能的影响.所有选定的数据集的高斯核宽度都设置为1,其他参数的设置同上.两个聚类实验的结果如图19—20所示.结果表明,除了密度权重为0时聚类性能有所下降外,平滑参数和密度权重在其他参数设置下CE值变化不明显.这主要是因为当密度权重为0时,所有的样本相对密度值为1,相对密度项在算法中没有解决因样本数据分布差异导致的聚类中心求解偏差问题,因此性能有所下降.相比而言,在其他参数设置下,因平滑参数（放大次数）和密度权重都只是用于放大不同样本的相对密度之间的比率,因此对聚类性能没有特别大的影响.

图19 不同平滑参数对算法性能的影响Fig.19 The effect of different smoothing parameters on the performance of the proposed algorithm

图20 不同密度权重对算法性能的影响Fig.20 The effect of different density weights on the performance of the proposed algorithm

4.3 在UCI数据的聚类结果及分析

4.3.1 实验评价指标

实验采用UCI数据集对算法聚类结果进行对比分析,并使用有监督的样本聚类性能评测指标:标准交互信息和准确率.

交互信息（mutual information,MI）是用来衡量两个数据分布吻合程度的指标.假设U与V是对N个样本标签的分配情况,则两种分布的熵分别为

如果样本标签分类正确,则dk=1,否则dk=0.对聚类效果进行评价时,标准交互信息和准确率的值越大,表明聚类的效果越好.

4.3.2 实验分析

为表明密度敏感模糊核最大熵聚类算法在对不同数据集进行聚类时的优势,实验选择了来源于国际机器学习标准数据库UCI[33]中的9个不同的数据集,分别为WINE,IRIS,BREAST CANCER,HABERMAN,IONOSPHERE,GLASS,HEART,SONAR和CAR,数据集的特征信息见表2.

表2 实验数据集描述Table 2 Description of experimental datasets

将本文提出的DSKME聚类算法同模糊C均值（FCM）、核模糊C均值（KFCM）、最大熵规范化权重核模糊C均值（KEWFCM）、最大熵聚类算法（ME）、改进的初始聚类中心优化的加权最大熵核模糊聚类算法（WKMEFCM）和η型最大中心间隔极大熵聚类（ηMCSMEC）算法6种聚类算法进行对比,参数设置同上.根据7种算法的聚类结果,计算评价指标NMI和CR的值,结果如表3所示.

表3 不同聚类算法对9个UCI数据集关于NMI和CR的统计结果Table 3 Statistics of different clustering algorithms on nine UCI datasets in terms of NMI and CR

通过表3可以看出,本文提出的DSKME算法除了在GLASS数据集上的NMI指标值略小于KEWFCM算法所取得的最大值、在HEART数据集上的两个评价指标值略小于FCM所取得的最大值、在CAR数据集上的CR指标值略小于KFCM算法取得的最大值外,其在WINE,IRIS,BREAST CANCER,HABERMAN,IONOSPHERE和SONAR数据集上的NMI和CR聚类性能评价指标值均达到最优.特别地,DSKME算法在CAR数据集上的NMI指标值为7种算法中的最大值.综合对比分析可知,本文提出的DSKME算法在UCI所选9个数据集上的聚类效果最好.

4.4 算法的鲁棒性分析

为比较本文提出的密度敏感模糊核最大熵聚类算法与其他6种算法的鲁棒性,实验借鉴文献[34]中的鲁棒性分析方法对7种算法在解决仿真数据和UCI数据集聚类问题时的鲁棒性进行比较.

首先,在仿真数据的聚类问题中,用7种算法分别求解7种人工数据无监督聚类问题的鲁棒性,并进行比较.具体地,算法m（m是指7种算法中的某一个算法）在某一特定人工数据集上的相对性能用如下比值来衡量:

因此,在某个人工数据集上表现最好的算法m*（m*是指性能最好的算法）的相对性能=2,而其他算法的相对性能bm≤2.bm值越大,表明算法m在所有算法中的相对性能越好.因此,算法m在所有数据集上bm值的总和可以用来客观评价算法的鲁棒性.其总和越大,表明算法鲁棒性越好.

根据上述分析,本文对仿真数据的聚类问题中7种算法的bm值进行计算并比较.图21为用7种算法分别求解7种人工数据无监督聚类问题鲁棒性的比较结果柱状图,每一种算法对应的柱状图顶部所标数值为对应算法在7种人工数据聚类问题上bm值的总和.从图21中可以看出,本文提出的DSKME算法的总和值最高,达到了13.59.KEWFCM次之,达到了10.61.其中,DSKME算法的bm值在测试的7种人工数据聚类问题的Motortype,Eyes,LineBlobs和Long1中均为2.这充分说明本文提出的DSKME算法在不同空间结构数据聚类问题中均表现出良好的性能,且在7种算法中具有最好的鲁棒性.

图21 7种算法针对7种人工数据无监督聚类问题鲁棒性能比较Fig.21 Comparison of seven algorithms for robust performance of seven unsupervised clustering problem with artificial data

其次,在UCI数据的聚类问题中,用7种算法分别求解9种UCI数据有监督聚类问题的鲁棒性,并进行比较.算法m（m是指7种算法中的某一个算法）在某一特定UCI数据集上的相对性能用如下比值来衡量:

因此,在某个UCI数据集上表现最好的算法m*（m*是指性能最好的算法）的相对性能=2,而其他算法的相对性能bm≤2.bm值越大,表明算法m在所有算法中的相对性能越好.因此,算法m在所有数据集上的bm值的总和可以用来客观评价算法的鲁棒性,其总和越大,表明算法鲁棒性越好.

根据上述分析,本文对UCI数据的聚类问题中7种算法的bm值进行计算并比较.图22为用7种算法分别求解9种UCI数据有监督聚类问题鲁棒性的比较结果柱状图,每一种算法对应的柱状图顶部所标数值为对应算法在9种UCI有监督聚类问题上的bm值的总和.从图22中可以看出,本文提出的DSKME算法总和值最高,达到了17.36.KEWFCM次之,达到了16.54.其中,DSKME算法的bm值在测试的9种UCI数据聚类问题的WINE,IRIS,BREAST CANCER,HABERMAN,IONOSHPERE和SONAR中均为2.这充分说明了本文提出的DSKME算法在不同空间结构以及不同维度数据的聚类问题中均表现出很好的性能,且在7种算法中具有最好的鲁棒性.

图22 7种算法针对9种UCI数据有监督聚类问题鲁棒性能比较Fig.22 Comparison seven algorithms for robust performance of nine supervised clustering problem with UCI data

综上所述,由于DSKME算法引入了相对密度项,使得数据的分布差异不会对聚类中心的求解产生影响,同时高斯核函数的引入抑制了原最大熵聚类算法的趋同性,显著提高了聚类结果的准确性和算法的稳定性.并且算法对不同类型的数据具有包容性,在处理不同类型数据的聚类问题时均表现出良好的性能.

5 结论

本文提出一种密度敏感模糊核最大熵聚类算法.通过实验分析得到如下结论:

1）为消除最大熵聚类算法的趋同性对聚类结果的影响,本文利用核函数的相似性抵消聚类过程中不属于该聚类的样本数据对聚类中心更新的影响.实验部分通过对比ME算法和DSKME算法的聚类结果表明:DSKME算法有效解决了最大熵聚类算法参数设置会影响聚类中心求解的问题,具有较好的稳定性.

2）为消除样本数据在特征空间的分布差异对聚类中心的求解造成的影响,本文通过引入相对密度的概念来增强相对密度大的样本数据对聚类中心求解的影响程度.实验部分通过对比ME算法和DSKME算法的聚类结果表明:DSKME算法有效消除了数据分布差异对聚类结果的影响,提升了高密度区数据对聚类中心求解的影响力,使得聚类结果更加准确.

3）为比较DSKME算法和其他6种算法的性能以及解决聚类问题时的鲁棒性,本文将DSKME算法与其他6种算法对不同数据集进行聚类,并利用不同的评价指标对聚类的结果进行比较分析.实验结果表明:在7种算法中,DSKME算法的聚类效果最好,具有最好的鲁棒性.这说明核函数和相对密度项的引入,不仅提高了算法的稳定性和聚类的准确性,而且使算法对不同类型的数据具有包容性,在处理不同类型数据的聚类问题时均表现出良好的性能.需要说明的是,本文若采用几何距离的方法,有望进一步提升算法对流行结构数据聚类的性能,这将是本课题下一阶段研究的重点.