衣俊艳,贺树辉

(北京建筑大学 电气与信息工程学院,北京 102612)

1 引 言

随着信息科技飞速发展以及“大数据”时代的到来,聚类分析作为数据挖掘的核心方法之一逐而备受研究者们的“青睐”.聚类是将对象进行分组的一项任务,使相似的对象归为一类,不相似的对象归为不同类.聚类是一个无监督的分类,它没有任何先验知识可用,因此在分类时只依赖对象自身所具有的属性来区分对象之间的相似程度[1].聚类广泛应用于语音识别、字符识别、图像分割、机器视觉、数据压缩、信息检索此外,聚类还应用于统计科学.值得一提的是,聚类分析对生物学、心理学、考古学、地质学、地理学以及市场营销等研究也都有重要作用[2].

根据聚类过程的动态特性的不同,聚类方法也划分出了较多的类别.大致可分为基于层次的聚类方法[3],基于划分的聚类方法[4,5],基于密度的聚类方法[6,7],基于网格的聚类方法[8],基于模型(神经网络)的聚类方法[9].而以上各种聚类方法中的大多数经典的算法都存在一些不足之处.例如基于划分的k-means算法以及k-medoids算法聚类结果不稳定,求解非凸数据聚类结果差[5,10];基于密度的DBSCAN算法聚类过程复杂繁琐并且不能很好地解决高维问题[11];基于网格的OPTICS算法[12]在求解高维大数据量问题时聚类质量差;基于神经网络的自组织特征映射(SOFM)算法的网络结构灵活性差,对数据输入要求较高,网络收敛过程容易受到系统的初始状态及参数的影响,导致运行结果不够稳定[13,14].弹性网络以其独特的网络结构以及灵活的求解方式,不仅能够处理高维大数据模式研究问题,而且求解过程具有更高的稳定性,网络拥有更高的性能.经过研究发现基于弹性网络改进的算法能够很好地继承这些优点,因此本文从弹性网络入手,通过对网络结构进行改进从而得到一种新的高性能的聚类算法.

弹性网络是在自组织映射网络的基础上发展而来的.原始弹性网络是由Durbin和Willshaw提出的,最初被表述为一种启发式方法并用于求解旅行商问题[15],原始弹性网络并不能用于求解聚类问题.而随着对弹性网络研究的深入,它被赋予了机械统计基础[16]并用于模式研究中的不同问题,弹性网络逐渐成为多维空间聚类中强有力的工具[17].近年来对弹性网络的改进也有很多,Salvini和Carvalho基于弹性网络中的两种受力方式提出了多维空间聚类方法[18],提高了算法求解维度,降低了参数敏感性,但是算法计算复杂,需要耗费大量时间与空间;Damper等人[19]将其应用于图像,提升了网络的抗噪能力,但是运算速度与精度不高;Yi等人在弹性网络中引入基于时间的动态参数,使得网络能够随时选取合适的参数进行求解TSP问题,加快了网络收敛速度[20],但是网络求解复杂度较高且抗噪能力较差.Shen等人通过在每次迭代中局部搜索最佳质心的方法,提出了用于求解聚类的弹性网络新算法[21],提升了网络性能及求解质量,但是该算法计算复杂,参数敏感性较高.目前大多数基于弹性网络的聚类算法大都存在计算复杂度高,参数敏感性高,求解精度不够高,求解速度慢的问题.

因此,为了改善传统聚类算法及以上弹性网络聚类算法存在的不足,本文提出了引入特征选择初始化策略的弹性网络聚类算法(FSENC).首先对于原始弹性网络不能用于求解聚类的问题,本文根据聚类中数据点与聚类中心的关系重新定义了一个聚类代价函数,并尝试将其替换弹性网络能量函数中的目标函数.其次,在聚类问题中,聚类中心的数量远远小于数据点的数量.因此本文改变了弹性网络能量函数的结构,即在求解过程中忽略了各弹性节点之间的吸引力,仅考虑弹性节点与数据点之间的力.这样能够使聚类过程中弹性节点能更快更好的向最佳聚类中心移动,并且降低了参数调整方面的难度.最后,由于大多数聚类算法中初始聚类中心的位置是随机设置的,不能根据数据进行动态改变,很大程度上影响着聚类质量.针对这点,文中提出了一种初始化聚类中心的方法,该方法能够针对不同数据动态地改变初始聚类中心的位置,并在以特征属性离散程度最小的二维子空间平面上进行初始化,能够有效提高聚类过程稳定性以及聚类质量.本文提出的弹性网络算法能够成功用于求解聚类问题,并且能够有效改善大部分传统和经典算法的不足,得到更高质量的聚类结果.

2 原始弹性网络

原始弹性网络最初用于求解旅行商问题(TSP).原始弹性网络由M个弹性节点U=[u1,u2,…,uM]T和N个城市节点P=[p1,p2,…,pN]T组成,城市节点即为二维空间下的城市坐标.算法最终使每个城市节点对应至少一个弹性节点.Durbin和Willshaw对于弹性节点和城市节点的数量建议使用M=2.5N,以解决图像中边缘点可能不均匀分布的问题[15].

弹性网络在求解TSP问题时通过求解能量函数的全局最小值而得到最终解,这是一个梯度下降算法.能量函数定义如下:

(1)

公式(1)的能量函数中α项为代价项,用于控制空间中城市节点对弹性节点的吸引力,作用是寻找有效解;而β项为限制项,用于控制相邻弹性结点间的吸引力,作用是寻找最优解.适当调整参数α、β则可以平衡这两种力量.原始弹性网络引入了温度参数K,K初始值设为0.2,并且每n次迭代将其降低1%.

原始弹性网络通过以下公式迭代更新弹性节点的位置:

(2)

在公式(2)的每n次迭代之后,K的值逐渐减小,并且这些弹性节点逐渐从被多个城市节点吸引变为被几个城市节点吸引.当K值很低时,保证了形成的每个弹性带轮廓都是有效的TSP行程[22].上式中ωij表示城市节点pi对弹性节点uj的影响程度,可通过极大熵原理求得.定义如下:

(3)

根据确定性退火技术[23,24],原始弹性网络求解时将整个系统看作是物理系统.当值在迭代过程中逐渐趋于0,能量函数达到全局最小值,系统逐渐趋于平衡.每个城市节点都能匹配到至少一个弹性节点,从而得出TSP问题的有效解.

3 引入特征选择初始化策略的弹性网络聚类算法

本文提出了引入特征选择初始化策略的弹性网络聚类算法(FSENC算法).通过改变能量函数与自由能函数的结构,使新算法更适用于求解聚类问题.而且,根据特征属性离散度的不同,提出了一种能根据数据动态生成弹性节点的方法.该方法有效地增强了算法灵活性,加快了聚类过程.通过分析可知FSENC算法能够有效提高聚类质量.

3.1 算法原理

对于聚类问题,在多元空间中定义一个含有n个数据点的集合X=[x1,x2,…,xn]T,每个数据点均含有m个特征属性Xi=[xi,1,xi,2,…,xi,m]T.并初始化一条含有k个弹性节点的弹性带y=[y1,y2,…,ym]T,其中k为最终聚类中心的数量.

根据聚类中数据点与聚类中心的关系,本文定义了新的聚类代价函数:

(4)

将代价函数替换进原始能量函数中,可得到新的能量函数为:

(5)

其中ωij为各数据点xi属于各个聚类中心yj的概率分布.由于ωij没有先验知识,是未知的概率分布,因此本文使用极大熵原理[16,23]来确定ωij的基本形式.根据能量函数,熵函数定义如下:

(6)

在能量函数与熵函数的约束下,通过以下公式求解变分问题:

(7)

可得到ωij的高斯概率分布:

(8)

公式(8)中T是常数参数,对应于原始弹性网络算法中的温度参数.ωij显示出以下概率分布特点:当T→∞时,每个数据点属于任一簇的概率相同;当T→0时,每个数据点以1的概率仅属于某一簇.Zt为数据点xi的分布函数,定义如下:

(9)

根据每个节点的独立概率可以得到关于数据点xi的总的分布函数,定义如下:

(10)

对应物理系统的Helmholtz自由能函数的一般形式[24,25]如下:

(11)

公式(11)中,后一项为限制项Enod,代表弹性节点之间的作用力.对于聚类问题,由于弹性节点的数量较少,并且远远少于数据点的数量,弹性节点之间的相互作用力在实际问题中非常小,因此可以忽略[17].因此,本文去掉了Enod项,旨在加快聚类过程.新的自由能函数定义如下:

(12)

为防止因自由能下降幅度过大导致弹性节点移动距离过大,从而偏离簇中心导致聚类失败的问题,本文引入了常数参数δ.该参数用来控制聚类中心神经元的移动距离的幅度.在模拟退火过程中,当自由能达到最小值时,系统趋于稳定达到平衡状态.

求解过程中需要更新每一次迭代后各弹性节点的位置从而达到实时追踪聚类过程,因此需要得到每次迭代中各弹性节点移动的增量.由弹性网络理论及极大熵原理可知最佳节点位置的非线性耦合方程为:

∑iωij(xi-yj)=0,∀j

(13)

使用最陡下降法求解以下方程:

(14)

即可得到每次迭代中各弹性节点移动增量Δyj,其中Δτ为每次迭代的步长,选择合适的Δτ可以使网络充分运行从而得到高质量解.

大多数经典聚类算法在对聚类中心初始化时都是随机选取聚类中心的位置,这导致初始聚类中心的位置无法根据输入数据进行动态改变,从而影响聚类质量.因此,寻找一种合适的聚类初始化方法对提高聚类质量有很大帮助.结合子空间聚类相关理论,本文提出了一种能动态地改变各弹性节点初始位置的初始化方法.

首先,根据以下公式:

(15)

然后,圆的半径由以下公式求得:

(16)

最后,根据聚类定义中各簇内相似度高、簇间相似度低的要求,本文提出了特征属性离散程度计算公式:

(17)

根据公式(17)可以得到所有特征属性的离散程度值D=[D1,D2,…,Dm]T.

文中提出的初始化方法会根据数据的重心计算得到圆心与半径,然后根据计算得到各特征属性离散程度值D,并在离散度最小的二维平面上根据所求得的圆心与半径生成一个圆,并在圆上均匀生成k个聚类中心神经元.本文提出的弹性带及聚类中心神经元初始化方法综合考虑了所有数据点的位置,并以重心为基础,能够根据不同数据点的分布情况动态调节聚类中心神经元的初始位置,从而适应求解不同问题的需要.

3.2 算法步骤描述

本文以弹性网络理论为基础提出了一种新的加入特征选择初始化方法的弹性网络聚类算法(FSENC).该算法首先针对聚类问题中数据点与聚类中心的关系定义了新的代价函数,并将新的代价函数替换原弹性网络中的能量函数,使得改进的弹性网络能够运用于求解聚类问题;其次,提出了一种能够根据数据内在结构自动选择合适的初始化方案方法.使得算法有更高的灵活性.所提出聚类算法求解步骤描述如下:

首先定义一个含有n个数据点的数据集X=[x1,x2,…,xn]T,每个数据点均具有m个特征属性xi=[xi,1,xi,2,…,xi,m]T.设置聚类数目k,并根据输入数据的规模设置合适的参数T和δ的值.

2)通过对能量函数以及对应熵函数变分处理可以得到各数据点属于各弹性节点的高斯概率分布ωij.根据极大熵原理求解最佳节点的非线性耦合方程可以得到动量公式(14),并根据公式求解可得到各弹性节点移动的增量Δyj.

3)根据当前一步求得的增量Δyj以及前一次迭代中各弹性节点的位置Yt-1可以得到当前迭代次数下各弹性节点的位置Yt.

5)将各数据点xi按照求得的概率分布ωij分配给各聚类中心,得到最终聚类结果C={c1,c2,…,ck}.

3.3 算法分析

这一节分别从弹性带初始化算法分析,新的能量函数分析,参数分析以及算法性能分析4个方面,通过在不同种类数据集上的实验结果来验证所提出算法的合理性以及性能.

3.3.1 弹性节点初始化算法分析

传统算法大都用随机选取初始聚类中心的方式进行初始化,这样的方法不能根据数据的结构灵活地变化初始聚类中心的位置,导致聚类过程不稳定,聚类时间过长的问题,从而影响聚类质量.本文提出的算法初始化方法能够有效改善这类问题,提高聚类质量.

图1(a)为分别使用两种不同初始化方法得到的SED值的迭代对比图.两种方法除了初始化方法不同,其余都相同.FSENC为本文提出的算法,而随机初始化方法是从所有数据点中随机选取k个点作为初始聚类中心的方法.从图中可以明显看出,FSENC算法在求解过程中非常稳定,能更快收敛;而随机的初始化方法聚类过程中会有小幅波动,不稳定,而且收敛速度慢.FSENC算法只需要迭代321次,而随机初始化方法迭代475次,FSENC算法的迭代次数比随机初始化算法减少32.42%.对于最终SED值,两种方法分别为40.11和41.29,FSENC算法比随机初始化算法的SED值减少2.86%.分析可知,虽然本文提出的初始化方法与随机初始化方法在聚类时SED值差距不大,但能很大程度地加快聚类过程,提高稳定性,帮助算法得到更聚类质量.

图1 初始化方法和限制项对聚类质量的影响Fig.1 Influence of initialization methods and constraints on cluster quality

3.3.2 新的能量函数分析

本文提出的FSENC算法首先根据聚类问题中数据点与各聚类中心的相互关系定义了一个新的代价函数,从而得到了一个适用于求解聚类问题的新型能量函数.其次,又根据弹性网络求解过程中数据点与各弹性节点之间的受力进行分析,去除了自由能函数中的Enod项.即在聚类过程中忽略各弹性节点之间的力,使各弹性节点更快地向着聚类中心移动,从而提高聚类速度.

为了证明去除Enod项有助于加快聚类收敛过程,本文记录了FSENC和FSENC算法加入Enod项两种方法聚类过程中SED值的变化,如图1(b)所示.对比结果可知,两种方法SED值在聚类过程中趋势大致相同,两种方法迭代次数分别为347和477次,SED值分别为28.21和28.53.FSENC算法在迭代次数与SED值分别降低27.25%和1.12%.证明去除Enod项能有效加快聚类收敛过程,并对提高聚类质量有一定程度的帮助.

FSENC算法中的能量函数针对于聚类问题做了相应的变化,使得弹性网络可以用于求解聚类问题.FSENC算法在聚类过程中使用了确定性退火技术,将整个系统类比为物理系统.随着温度逐渐降低,自由能逐渐降低,弹性节点逐渐向各簇中心移动,直到自由能达到全局最小时程序收敛.图2为FSENC算法在聚类退火过程中弹性节点与总能量变化示意图.如图2(a)为程序初始状态,为了更清晰的观察到聚类过程中弹性节点受温度及自由能变化逐渐移动的过程,实验假设初始状态下的3个聚类中心均处于整个集群的质心位置.

图2 FSENC算法聚类过程中的确定性退火技术Fig.2 Deterministic annealing technique in the clustering process of the FSENC algorithm

结合图2(d)看,在迭代次数小于20时,总能量值此时恒定,此时弹性节点尚未移动.随着温度逐渐降低,当迭代次数为20时,总能量突然下降到一个较低的恒定值.重叠的弹性节点开始移动并迅速分离,但是各节点未完全分离开,而是分离到了两个不同位置,此时右下有两个重叠的弹性节点,如图2(b)所示.在迭代次数处于20和50之间,能量值变化较小,各弹性节点处于缓慢移动状态.当迭代到70次左右时,总能量值再次大幅度下降,右下重叠的弹性节点由于数据点的吸引力作用再次分离.当迭代次数大于70时,可以看到总能量值逐渐下降并最终趋于一个较低的稳定值,在此过程中温度也逐渐下降到较低水平,各弹性节点逐渐向各簇最佳聚类中心移动.如图2(c)所示,当迭代次数为300时,总能量基本保持不变,弹性节点不再移动,最终形成3个簇并得到聚类结果.由以上聚类过程分析可知,FSENC算法中新能量函数的建立是合理的,能够很好地用于求解聚类问题.

3.3.3 相关参数分析

FSENC算法中共有两个参数会对聚类过程产生影响,对于不同种类,不同规模的数据,选取合适的参数组合能够有效提高聚类质量.通过实验可以得到适合的参数选取范围.分析可知,参数δ值越大,SED值越大,更容易聚类失败,而网络迭代次数会增加,不利于网络收敛,求解质量较差.通过分析可以看出参数δ最佳取值范围为[0.1,0.5].当δ值在合适范围内时,参数T值越小,SED值越小,迭代次数减少,聚类质量越高.

但是这并不意味着值越小越好,过小的T值会导致聚类过程中能量函数不能收敛于全局最小值而提前结束程序,无法得到最优的聚类结果.因此在选取参数T值时应当在合适的取值范围内,根据数据内在结构的不同,选取一个较大的初始值,随着程序的运行使T值逐渐减小,直到T值减小到较低水平,弹性节点均不再移动,此时程序收敛.这样设置参数可以使得整个系统在算法初始阶段有较高的活性,从而改变初期各弹性节点所受的力的大小,使各弹性节点能够更快地找到每个簇;随着参数越来越小,此时整个系统的活性降低,各弹性节点无法大幅度移动,避免了移动幅度过大导致的聚类失败.各弹性节点只能缓慢地朝着各簇最佳聚类中心移动,最终无限接近最佳聚类中心并停止移动.这样能够很好地保证整个系统以最佳方式运作,得到更好的聚类结果.通过分析可以得到温度参数的最佳取值范围为[1,4].

通过大量实验,可以发现不同数据规模的聚类问题在取得最佳聚类结果时所用的的参数不是固定的.根据数据量的不同应当在参数取值范围内做适当调整以取得最优解.根据经验,参数选取应当遵循以下规则:对于数据量大的聚类问题,应选取较大的值,对于较小数据量的聚类问题,应选取较小的T值,这样能使程序在不同数据量下均能够充分的运行以得到高质量解.参数δ的选取与聚类簇数相关,聚类簇数量越大,δ值应当越大.使聚类过程中各弹性节点能够更快更好地找到各簇并取得最优解.

3.3.4 算法性能分析

为了验证FSENC算法的有效性及合理性,本文选取了一个含有2000数据的10维随机生成数据集进行实验,簇数量为3簇.记录了实验数据并与未加入创新步骤的基础弹性网络聚类算法(ENC)做了对比,从而综合展示FSENC算法的性能.

图3(a)和图3(b)分别为聚类过程中总能量值与SED的迭代图.对比图3(a)中总能量值的变化可以看出FSENC算法比ENC算法更快达到较低水平并趋于收敛.FSENC需要387次迭代,而ENC算法需要594次迭代,FSENC算法比ENC算法迭代次数减少34.85%.对比图3(b)中两种算法的SED值,FSENC算法最终SED值为21.86,而ENC算法SED值为35.51.FSENC算法SED值比ENC算法降低38.44%,能够得到更高的聚类质量.

图3 FSENC算法和ENC算法的聚类过程迭代图Fig.3 Evolution of the clustering process of FSENC and ENC algorithm

FSENC算法在迭代过程中有更高的稳定性.如图4所示,实验追踪了迭代过程中3个聚类中心的其中一个神经元的移动.图4(a)为该弹性节点在水平方向(ΔX)的移动距离,图4(b)为该弹性节点在垂直方向(ΔY)的移动距离.从两张图中可以清晰地看到FSENC算法在聚类过程中弹性节点的移动非常稳定,虽然移动幅度较大但是能够很快地趋于平稳状态.而ENC算法在聚类过程中弹性节点移动波动较大,需要更长的迭代次数才能趋于稳定状态.FSENC算法聚类过程神经元的移动比ENC算法更稳定,更有助于算法更快地取得最优解.

图4 两种算法聚类中弹性节点位置变化演进图Fig.4 Elastic node position changes of FSENC and ENC algorithm in clustering process

由于弹性网络独特的网络结构以及求解方法,使得弹性网络聚类算法相比于其他传统聚类算法有着更高的稳定性,总能获得唯一解.本文分别选取了含有3000和10000个数据的随机数据集进行了对比试验,将FSENC算法与较传统的k-means、k-medoids与较新的FAKM[26]、ENC算法进行了比较,FAKM算法是基于k-means算法而改进的新算法.如图5所示为各算法在这两个数据集分别运行30次的SED值.通过分析可知,FSENC算法在两个数据量下的SED值均小于其他四种算法.而且,FSENC算法与ENC算法的SED值始终唯一,而k-means、k-medoids、FAKM算法每一次运行的SED值均有变化,且变化幅度较大.k-means算法的SED值最大,FSENC算法SED值最小.FSENC算法平均SED值比k-means、k-medoids,FAKM、ENC算法分别减小45.77%、42.83%、25.44%、16.98%.FSENC算法的聚类质量均高于其他4种算法,有更高的性能.

4 实验仿真

在这一部分中,本文在大量人工合成和真实数据集上进行了实验来评估FSENC算法的性能.与一些经典的和较新的聚类算法做了对比,例如k-means、 k-medoids、 DBSCAN、 BIRCH、 ENC、 FAKM[26]、 DEKM[27]等7种算法做了对比实验.

4.1 数据集

实验中使用的数据集包括4个人工合成数据集和10个真实数据集.这些数据集的数据规模(数据量、维度、簇数)以及内在结构(凹凸,密度差)均不相同.这些数据集的属性信息如表1所示.其中人工合成的数据集除Sy1外均可从开源数据集网站(http://cs.uef.fi/sipu/datasets/)获得.真实数据集可从UCI数据库(http://archive.ics.uci.edu/ml/index.php)获得.

表1 实验使用的数据集属性Table 1 Attribute information of the datasets used in the experiments

4.2 聚类质量评价标准及参数选取

实验部分使用SED[28]值和聚类精度(Accuracy)作为聚类评价指标.SED的定义如下:

(18)

其中,是第i个数据点,yj是第j个聚类中心,d(xi,yj)为欧几里得距离,Cj为第j簇.SED值代表各簇数据点到各个簇聚类中心的距离之和,SED值越小说明聚类质量越高.

聚类精度(Accuracy)定义如下:

(19)

其中ni为各簇被正确分类的数据点的个数,N为所有数据点的总数.ACC值越大代表聚类质量越高.

从章节3.3.3中可知参数选取规则与范围.对于实验部分的参数选取遵循以下规则:对于0～1000数据量的小规模问题,参数T取值为2,参数α取值为0.3;数据量为1000～10000的中等规模问题,参数T取值为3,参数α取值为0.15;数据量为10000以上的大等规模问题,参数取值为4,参数α取值为0.1.实验中对不同问题的参数可在参数取值范围内微调.

4.3 人工合成数据集上的实验结果

图6～图8为k-means、BIRCH和FSENC 3种算法分别在Jain、Uneven、R15人工合成数据集上的聚类结果.通常情况下数据内在结构例如凸形或非凸、密度差异、簇数目等因素会影响聚类算法的性能.分析图6可知,对于非凸数据Jain,FSENC算法的SED值比k-means和BIRCH算法分别减少34.41%、21.21%,聚类质量明显高于其余两种算法.图7中Uneven数据密度差异较大,其中实心矩形为聚类中心.从图中结果对比可知,FSENC算法的SED值比对比算法分别减少33.95%、20.95%.FSENC算法的聚类中心比其余两种算法的聚类中心更接近于高密度区域的最佳质心的位置,证明了FSENC算法在非均匀数据中准确找到簇结构方面更有优势.图8中的R15数据集含有较多的簇数,分析得知FSENC算法的SED值比其余算法分别减少22.03%、12.08%,聚类效果明显好于k-means、BIRCH算法.在不同种类数据集上的实验结果表明,FSENC算法能够很好地识别出不同大小、不同形状和不同密度的簇,得到较高的聚类质量.

图6 3种算法在数据集Jain上的聚类结果Fig.6 Clustering results of Jain by three algorithms

图7 3种算法在数据集Uneven上的聚类结果Fig.7 Clustering results of Uneven by three algorithms

图8 3种算法在数据集R15上的聚类结果Fig.8 Clustering results of R15 by three algorithms

为了进一步验证FSENC算法的性能,本文在随机生成的个人工合成数据集Sy1上做了对比实验,并与k-means,BIRCH,DEKM算法进行了比较.Sy1的属性信息如表2和表3所示.这部分实验使用SED作为聚类评价标准,表中SED值取20次实验的平均值.

表2 Sy1数据集中3维和7维数据的聚类结果Table 2 Clustering results of 3D and 7D data in Sy1 data set

表3 Sy1数据集中10维和13维数据的聚类结果Table 3 Clustering results of 10D and 13D data in Sy1 data set

通过分析表2和表3数据,k-means,BIRCH,DEKM,FSENC这4种算法平均SED分别为15968.14、15594.45、13878.52、11618.26.FSENC算法SED值比其余3种算法分别降低27.24%、25.50%、16.29%.对于数据量大于5000,维度为10、13的较大规模数据,FSENC算法SED值比其余3种算法分别降低28.90%、28.10%、18.68%.FSENC算法在求解时不仅稳定性高,而且能够适用于求解不同数据量下的聚类问题,尤其在求解大数据量问题时,FSENC算法比其他算法更具优势,能得到更高质量的聚类结果.

4.4 真实数据集上的实验结果

FSENC算法不仅在求解随机生成问题时能够得到高质量解,而且在求解真实聚类问题时同样可以得到高质量的聚类解.为了证明这一点,实验选取了10个真实数据做了对比实验.将FSENC算法与k-means等7种算法进行比较,这部分实验以SED值与Accuracy作为评价指标,N/A代表无解,标准数据均取20次结果的平均值,如表4和表5所示.分析表中数据可以得到以下结论:

表4 真实数据集的聚类SED值Table 4 Clustering SED on real datasets

表5 真实数据集的聚类准确率Table 5 Clustering accuracy on real datasets

1)k-medoids算法在HTRU2、Hand、Skin这3个大规模数据集上无法得到聚类结果,而其余算法均可得到聚类解.在有解的情况下,FSENC算法比其余7种算法平均SED分别减小27.98%、26.13%、26.75%、21.22%、15.05%、12.89%、19.73%.

2)FSENC算法平均聚类精度为76.07%,比其余7种算法平均聚类精度分别提高了18.09%、17.02%、21.77%、9.25%、6.07%、3.54%、8.26%.除FSENC算法外,DEKM算法平均聚类精度最高,DBSCAN算法平均聚类精度最低.FSENC算法平均聚类精度均高于其余7种算法,证明该算法能够在各类真实数据集上得到更高质量的解.FSENC平均聚类精度比ENC算法高8.26%,说明本文对算法的改进对提升聚类质量有很大帮助.

3)FSENC算法在Wine-white、HTRU2、Hand、Skin等较大规模数据集上平均聚类精度比其余算法分别提高了23.76%、30.18%、25.48%、10.06%、4.22%、3.32%、8.19%.而在其余小规模数据集上平均聚类精度比其余算法分别提高14.32%、12.50%、19.31%、8.72%、7.31%、3.68%、8.31%.FSENC算法聚类精度在大规模数据集上平均提高了15.03%,在小规模数据集上平均提高了10.59%.这也说明了FSENC算法更适合求解高维大数据量聚类问题.

5 结 论

本文提出了一种新的加入特征选择初始化方法的弹性网络聚类算法FSENC.该算法根据聚类中数据点与聚类中心的关系入手,首先重新定义了一个更有助于求解聚类问题的代价函数.并基于新的代价函数和极大熵原理,定义了一个新的聚类弹性网络能量函数,使FSENC算法比基础弹性网络聚类算法(ENC)更适合解决聚类问题.FSENC算法是一种无监督的优化方法,通过自学习解决聚类问题,无需人工训练或干预.求解时根据确定性退火技术,自动地最小化能量函数从而得到聚类问题的解.其次,该算法在求解时去掉了基础弹性网络自由能函数中的限制项,消除了聚类过程中弹性节点间的干扰,使弹性节点更快地移动,提高了聚类质量和效率.最后,本文提出了一种能够根据数据内在结构自动给出合适的初始化方案的方法.该方法可以有效提高算法灵活性,降低数据集内部结构的影响,从而提高聚类速度.

由于弹性网络特殊的网络结构及求解方式,FSENC算法在求解高维和大数据量的聚类问题时更具优势,并且可以直观地追踪聚类过程.在大量合成数据集和真实数据集上的实验结果直观地表明,FSENC算法比其他一些经典的聚类算法具有更高的稳定性,在求解聚类问题时有更好的聚类质量,尤其是在求解高维和大数据量的聚类问题方面更具优势.