中性游走驱动的进化子空间聚类算法

林鑫涛,何振峰

(福州大学 数学与计算机科学学院,福州 350108)

1 引 言

聚类是把数据对象集划分为多个数据簇,使得处于同一簇中的对象具有高相似性,处于不同簇中的对象具有高相异性的过程,聚类可以帮助人们更好地理解数据的内在结构,在诸多领域都发挥着巨大的作用[1].近年来,信息技术的高速发展使得数据呈现出高维化的趋势,“维度灾难[2]”让传统聚类算法的聚类效果大打折扣.子空间聚类是进行高维数据聚类的有效方法之一,其利用特征选择的思想从数据集所处的特征空间中抽取出一个或多个子空间,并在各个子空间内搜索数据簇.现有子空间聚类算法虽然在一定程度上解决了“维度灾难”的影响,但还存在可使用性差、效率低、可伸缩性差、鲁棒性低、启发信息不足等诸多问题[3].

Peignier等人于2015年提出进化子空间聚类算法Chamleoclust[4],算法利用可演化的染色体结构来搜索子空间和聚集数据,将遗传算法[5]的优点融入子空间聚类过程中,取得了很好的效果.Chameleoclust已经被运用于化学分子研究、音乐的自动产生等领域[6].但由于启发信息不足的原因,其仍然存在搜索效率不高;容易陷入局部最优等问题.

传统进化算法思想源于达尔文的自然选择学说,将自然选择对有利突变的固定作为进化的主要驱动力[7].1968年由木村资生提出的“中性理论(neutral theory)[8]”认为:在生物遗传进化过程中发生的大部分突变是对生物体生存既无好处也无坏处的“中性突变(neutral mutations)”,而生物进化的主要驱动力是中性突变的随机固定而不是自然选择引起的有利突变的固定.本文以中性理论的思想为基础提出一种“中性游走(neutral walks)[9]”驱动的进化子空间聚类算法.以进化潜力为启发信息对染色体进一步评价,并利用中性游走来引导中性突变,在提高算法效率的同时,也能适时地将搜索引导到搜索空间的其它部位,较好地解决了原算法的搜索陷入局部最优的问题.

2 研究背景

2.1 子空间聚类简介

子空间聚类是为解决高维数据聚类而产生的一种新的聚类分支,与传统聚类相比,子空间聚类面临的主要挑战是如何有效地搜索一系列子空间并在其中聚类.目前的子空间聚类算法主要有自底向上和自顶向下两种搜索策略,自底向上的子空间聚类算法从低维子空间开始开始,向上增加子空间的维度,直到遍历所有可能的子空间,寻找所有可能的簇.自顶向下的子空间聚类算法从数据集的全维度数据空间开始,递归地搜索越来越小的子空间.目前子空间聚类的主要问题有:搜索空间过大导致效率不高;对启发信息依赖性很强;鲁棒性差;可伸缩性差等[3].

2.2 进化子空间聚类算法Chameleoclust

Chameleoclust算法将进化算法的可操作性、并行性、全局搜索性、鲁棒性等优点融合到子空间聚类求解过程中,算法染色体结构具有的可变的染色体长度、显隐性基因等仿生特征给搜索过程带来了极大的自由度,且算法只有一个与子空间聚类相关的输入参数:数据簇数量上限,这很好地解决了大部分子空间聚类算法对输入参数的依赖性问题.Chameleoclust过程如图1所示(详见文献[4]).

图1 Chameleoclust流程图Fig.1 Flow chart of Chameleoclust

编码策略:算法采用变长整数编码,将簇中心信息编码成染色体.其染色体Γ由大量基因四元组γ=构成,其中g∈{0,1}决定了γ是否表达;c为簇编号;d为维度编号;m∈{-1000,…,1000}表示贡献度.每个染色体对应一个由子空间中心点pc(表示数据簇和该簇所处的子空间)组成的集合Φ,簇i对应子空间中心点在维度j的值计算过程如公式(1)所示,其中xmax=max(abs(S)),S为数据集标准化(x=(x′-μ)/σ)后所有特征值集合.

(1)

适应值函数:算法的适应值函数如公式(2)所示,其中Spc表示所有分配到簇c的数据;ε(x,pc)表示数据x(经过标准化后)与簇c的不匹配程度(基于曼哈顿距离dD,计算过程如公式(3)),当ε(x,pc)的值最小时数据x被分配到簇c,其中‖表示空间的维数,D表示全维度空间,DDpc表示Dpc的补空间,O为0向量.

(2)

(3)

选择:在新种群的产生阶段,将排在最后的个体作为精英直接保留到新种群中后(elitist selection),再通过选择变异产生N-1个新个体.选择父代时,个体α被选择概率pα(公式(4),s为选择压力参数)根据其在种群中的排位rα∈{1,…,N}呈指数级增长.因此排序策略是十分重要的,Chameleoclust采用基于单一适应值的简单排序(从小到大),由于在实际搜索过程中每一代种群中都有大量适应值相同的个体,这种简单排序显然无法提供足够的启发信息.

(4)

变异:算法有两种突变形式:染色体重排(包含子段删除、移位、复制,如图2所示)、点突变(随机替换任意位置四元组中的元件值),其中子段删除与子段复制是变长突变,子段移位和点突变是定长突变.这些灵活的突变形式为算法的搜索过程带来了极大的自由度.

图2 三种染色体重排策略Fig.2 Three chromosome rearrangement strategies

Chameleoclust的不足之处:

简单排序策略使得算法无法对适应值相同但染色体不同的个体进行优劣评价,因此缺乏足够的启发信息来引导搜索,这也使得在拥有极大自由度的情况下,算法搜索空间过大以及容易陷入局部最优等问题进一步加剧.因此算法的搜索效率不高,且搜索过程中容易出现连续多轮遗传迭代聚类质量没有提高的局面.

3 中性游走驱动的Chameleoclust算法

与自然选择理论不同,中性理论从分子层面阐述生物遗传进化的原因.因此以中性理论视角出发能够从染色体层面对Chameleoclust存在的问题进行合理的解释,并更容易找出合适的解决方案.

3.1 中性概念简介

生物体的基因型(编码形式)与表现型(具体作用)之间存在多对一的映射关系,即生物的遗传编码存在着大量冗余(中性冗余).中性冗余的存在使得一些基因型的变化并不会造成表现型的改变(中性突变).中性突变作为生物遗传进化过程中占比最高的突变类型,对生物遗传材料中发生的有害突变起到了缓冲作用的同时;也让生物体有了能应对不断变化的环境的能力,对生物遗传进化起着积极作用.

中性突变是用中性近邻(单轮突变可达且表现型相同的基因)替换原基因的过程,因此可以使用中性近邻的进化潜力来对中性突变进行评价,以解决无法通过表现型变化评价中性突变的问题.Marie等人指出:潜力大的中性近邻能够将当前搜索引导到搜索空间的其他部位以带来多样性[10].

中性突变将具有相同表现型的基因相连接组成了中性网络.中性游走[9]通常被用来探索中性网络,其一般步骤如下:1.选取初始起点;2.找出当前起点的所有中性近邻;3.从中性近邻中选出与起点相比有距离增长(游走的步长)的个体替换原起点;4.重复2～3步直到游走结束.2.中的步长概念依具体问题而定,在启发信息充足的情况下,可以在中性游走时控制步长来对进化搜索过程进行引导.

中性相关理论一直是进化计算领域的研究热点[11,12],研究者们在进化算法中加入中性元素来解决各类优化问题:Marmion等人利用含有中性冗余的进化算法解决流水作业调度问题,并利用中性游走主动地对搜索进行引导[13].Vassilev等人在数字电路进化算法中,以中性突变作为主要驱动力来演化[14].大量实验表明:中性的存在能为进化系统带来以下好处:(1)能够对有害突变进行限制,使得即使在高突变率下种群依然可以保持健康;(2)能在一定程度上避免搜索过程中出现过早聚合的问题;(3)能够提高搜索可靠性.

3.2 中性游走驱动的Chameleoclust算法

由于隐性基因等因素的影响,Chameleoclust编码结构存在大量中性冗余,遗传过程中发生的绝大部分突变都是对当前适应值(表现型)没有直接影响的中性突变,再加上其选择机制的影响,新种群个体大多是原种群中排位靠后个体的中性近邻,这导致同一代种群中存在大量适应值相同的个体.但Chameleoclust无法对适应值相同的个体进行优劣评价,因此启发信息不足,无法对中性突变进行正确的引导,从而引发算法搜索效率不高且极易陷入局部最优等问题.

为解决上述问题,我们以对中性突变的引导为搜索过程的重心,提出中性游走驱动的Chameleoclust算法(简称Chameleoclust NW).算法以进化潜力为启发信息,并结合中性游走对排序策略进行改进(见图3),使得在适应值相同时,进化潜力越高的个体被选择成为父代的概率越大.

进化潜力定义:

由中性近邻的潜力特性(3.1部分)可知,潜力大的个体能将当前搜索引导到远离当前搜索空间的部位以带来更多的多样性,因此使用父代染色体到子代染色体的变化量来衡量一个染色体的进化潜力,由于表现型无法体现这种变化,因此在定义进化潜力函数时主要考虑的是突变可能对基因型所带来的改变.

图3 排序策略的改进Fig.3 Improvement of sorting strategy

与算法用子空间中心点集合Φ来表示染色体的表现型相对应,提出“潜在子空间中心点集合”Φ′来表示染色体的基因型.与子空间中心点集合不同的是,在构建潜在子空间中心点集合时同时考虑了染色体中显性基因和隐性基因的影响,因此Φ′代表了Γ可能对应的所有数据簇(包含现有的和潜在的),而对于其中任一数据簇,潜在子空间中心点表示其可能产生的子空间(包含现有的和潜在的维度)以及其对应的潜在的中心点值.簇i所对应潜在子空间中心点在维度j的值计算过程如公式(5)所示.

(5)

(6)

(7)

中性游走驱动的进化子空间聚类:

Begin

Step1.初始化(图1:1.初始化);

Step2.中性游走起点Γ0=初代种群中排在最后的个体;

Step3.产生新一代种群(图1:2.新种群的产生);

Step4.将新种群按适应值(公式(2))排序(图1:3.排序);

Step6.Γ0=新种群中排在最后的个体;

Step7.判断预设遗传代数是否结束,若未结束则跳回Step 3;

Step8.return Γ0;

End

3.3 算法复杂度分析

算法涉及到的主要参数为:T表示总遗传迭代次数,N表示种群中的个体数,C表示设定的簇数量上限,D表示数据的维度,R表示数据对象的数量.

算法过程中占据主要时间开销的步骤包括:适应值计算(公式(2));进化潜力计算(公式(6));排序(Step 4～5).在一轮迭代中,计算适应值过程中的时间复杂度为O(NCRD);计算进化潜力过程中的时间复杂度为O(NC2D);排序时采用快速排序策略,因此时间复杂度为O(Nlog2N).将上述过程的时间复杂度结合可得到算法一轮迭代的时间复杂度O(NCRD+NC2D+Nlog2N).由于log2N<

可以看出,虽然Chameleoclust NW比Chameleoclust多了计算和比较进化潜力的时间开销,但是两者的时间复杂度相同,都为O(TNCRD).

4 实验分析

实验环境及数据集:本文在5组UCI数据集上进行对照试验,表1给出这些数据集的信息.实验算法采用R语言编写,运行在一台配置Intel(R)Core(TM)i7 CPU 3.40GHz,RAM 8GB的计算机上,操作系统是Windows7.

评价指标:采用熵指标[15](Entropy)进行算法的性能分析,其计算过程如公式(8)所示.其中H表示数据集的类标签数,C表示生成的簇数量,Spc表示簇c中的数据对象,E(c)表示单个簇c的熵值,其计算过程如公式(9)所示,其中p(h|c)表示簇c中数据类标签为h的概率.熵指标的取值范围为[0,1],数值越大,表明算法聚类性能越优越.

(8)

(9)

表1 UCI数据集
Table 1 UCI datasets

数据集维数类数数据量Breast332198Liver62345Shape179160Glass96214Diabetes82768

实验对比:分别对各个数据集执行10次Chameleoclust和Chameleoclust NW,实验参数设置如下:种群规模N=100,初代种群染色体长度(四元组个数)设为100,其中显性基因与隐形基因的比例设为1∶2,突变率um=0.005,选择压力参数s=0.5,遗传迭代次数T=5000,数据簇数量上限cmax=100.表2给出了10次实验得到的平均值(最优值)结果对照.图4给出在聚类数据集breast时相同代数Chameleoclust和Chameleoclust NW最佳适应值增长情况.

表2 实验结果对照(Entropy)
Table 2 Comparison of results(Entropy)

数据集ChameleoclustChameleoclust NWbreast0.40069(0.41815)0.43344(0.45321)Liver0.22495(0.25447)0.24968(0.27445)Shape0.84699(0.87568)0.85008(0.87946)Glass0.60447(0.61149)0.64986(0.65809)diabetes0.33086(0.35844)0.33177(0.36743)

由表2的数据对照可以看出,无论是平均值还是最优值,Chameleoclust NW的效果都优于Chameleoclust.由图4可看出,在聚类数据集breast时,超过一定遗传迭代次数后,Chameleoclust NW的最佳适应值要明显优于Chameleoclust,即前者的搜索效率要明显高于后者.

图4 两种算法取得的最优适应值(breast)Fig.4 Best fitnesses achieved by two algorithms(breast)

参数s对算法的影响:选择压力参数s∈[0,1)的值直接影响了个体成为父代概率(公式(4)).图5给出了不同s值下的选择概率分布情况.可以看出,s的值越小,被选择的机会就越集中在排位靠后的优秀个体上;s的值越大,被选择的机会就分配得越平均,可加强搜索的全局性.

图5 不同s值下的选择概率分布对比Fig.5 Comparison of selection probability distributions with different s-values

图6 参数s对算法性能的影响(breast)Fig.6 Influence of parameters s on the algorithm′s performance(breast)

图6给出了在不同的s值情况下使用Chameleoclust NW算法对数据集breast聚类的最佳适应值增长情况.可以看出,s取值0.5时算法的搜索效率要明显高于取值0.1或0.8时,这说明过度强调优秀个体的作用(s太小)或过度强调搜索的全局性(s太大)都会对算法搜索效率产生一定的影响,只有把握好两者之间的平衡才能较好地发挥算法的性能.

5 结束语

本文将中性理论的思想与Chameleoclust算法的框架相结合,提出一种中性游走驱动的进化子空间聚类算法.该算法以进化潜力为启发信息,对算法的排序策略进行改进,并以精英个体的进化潜力为步长进行主动的中性游走,以此来对遗传进化过程中的主要角色中性突变进行主动引导,为搜索带来多样性的同时,提高了算法的搜索效率,也进一步避免了搜索陷入局部最优的情况.本文的后续工作包括:进一步探索进化策略相关参数对搜索稳定性的影响;尝试加入交叉变异算子来加强染色体个体之间的信息交流.