高斯核模糊粗糙集中基于粒子群算法的属性约简

刘东君， 陈红梅

(西南交通大学 信息科学与技术学院 四川 成都 611756)

0 引言

在数据挖掘中，数据中冗余和不必要的属性会影响算法执行的效率，并可能造成过拟合.属性约简是一种有效处理冗余属性、相关属性和不必要属性的方法，它在保持数据集分类能力不变的情况下，尽可能去除其中无关的、冗余的信息.Pawlak提出的粗糙集理论(rough set theory)[1]及其在属性约简中的应用得到了广泛的研究[2-4].但是由于经典粗糙集在处理数值数据中需要对数据进行离散化处理，从而导致信息的损失，Dubois和Prade提出的模糊粗糙集理论[5]可解决该问题.在模糊粗糙集理论中能直接对连续属性值进行分析，不会因为离散化而造成信息的损失.Jensen和Shen提出了模糊粗糙集理论的属性约简算法[6]，Hu等将核函数应用于模糊粗糙集，提出了核模糊粗糙集模型[7]，并在此基础上提出了高斯核模糊粗糙集及相关属性约简算法[8].

在粗糙集和模糊粗糙集属性约简中，为了提高约简精度和降低计算约简或最小约简所需时间，演化算法在粗糙集中的应用被广泛研究，如基于粒子群算法(particle swarm optimization，PSO)的粗糙集属性约简算法[9]、基于免疫遗传算法的粗糙集属性约简算法[10]、基于果蝇算法的粗糙集属性约简算法[11]、鱼群算法与粗糙集相结合的属性约简算法[12]、基于环粒子群算法的模糊粗糙集约简算法[13]、八哥群算法与模糊粗糙集属性约简的结合[14]等.可以看到，粗糙集与演化算法结合的算法已经得到了广泛的研究，但是模糊粗糙集与演化算法结合的研究还相对较少，尤其是在新兴的模糊粗糙集模型如Hu等提出的核模糊粗糙集模型[7]上还未见相关报道.高斯核由于带有可变参数的独特性质，通过与粒子群算法相结合，可根据参数的不同获取不同约简率的属性约简来提高分类的性能.实验表明本文提出的算法具有良好的约简性能，并且能够获取优化的属性约简以提高分类性能.

1 基本概念

1.1 模糊粗糙集相关理论

本节将介绍核模糊粗糙集相关的基本概念.Pawlak在粗糙集理论中定义了决策信息系统，用它来描述一个数据集.

定义2[5]设R为论域U上的一个模糊等价关系，那么模糊粗糙集的上、下近似定义为

定义3[16]设U是一个非空论域(不要求是有限的)，R是U上的任意模糊关系，对任意的A∈F(U)，模糊粗糙集的近似算子定义为

Hu等人通过把核函数引入模糊粗糙集，建立了基于核的模糊粗糙集模型[7]，并进一步给出了一种常用核函数高斯核的模糊粗糙集模型[8].

定义4[17]设U是一个有限论域，如果实值函数k:U×U→R满足条件：对∀x,y∈U，有k(x,y)=k(y,x)，且半正定，那么把k称为核.

高斯核被定义为kG(x,y)=exp(-‖x-y‖2/2σ2)，用高斯核所计算的模糊关系是Tcos-模糊等价关系[18]，这里‖·‖是x和y之间的欧氏距离.

基于该种依赖度定义，Hu提出了FS-GKA约简算法[8].本文将基于高斯核模糊粗糙集模型及其依赖度定义，构建与粒子群相结合的属性约简算法.

1.2 粒子群算法相关理论

pi(t+1)=pi(t)+vi(t+1)，

vi(t+1)=ω(t)·v(t)+c1·rand( )·(pbesti-pi(t))+c2·rand( )·(gbest-pi(t)).

2 基于粒子群算法的高斯核模糊粗糙集属性约简

在高斯核模糊粗糙集的约简计算中，和传统粒子群算法中每个维度坐标都是连续的不同，由于每个属性只有选择和不选择两种可能，所以这时候粒子的每个属性都是2值的，以{0,1}来表示.给定决策信息系统DIS=〈U,C∪D,V,f〉，对条件属性集C={c1,c2,…,cn}，用一个n维粒子p=(x1,x2,…,xn)表示对条件属性的选择，其中xi∈{0,1}，规定0表示不选择该属性，1表示选择该属性，把粒子的速度记为v=(y1,y2,…,yn)，yi∈R，对粒子进行更新时，若xi+yi≥0.5，则记为1，若xi+yi<0.5，则记为0.

粒子的适应度函数f(p)选择为f(p)=α·γp(D)+β·(|C|-|p|)/|C|，其中：α+β=1，α,β∈[0,1]；|C|为数据集属性的个数；|p|为当前粒子所选择的属性个数.

通过下面的分析将会看到，把粒子群算法与高斯核模糊粗糙集模型结合，选择不同的σ参数将会使最终所得到的约简的属性个数发生变化.

定理1若U被决策属性划分为{d1,d2,…,dI}，对任意di,若x∈di，即di(x)=1，那么

若取高斯核函数，则

当x∈di时，若y∈di，即di(x)=di(y)，这时di(y)=1，所以一定有Rn(x,y)≤di(y)，可得ϑTcos(Rn(x,y),di(y))=1，即

ϑTcos(Rn(x,y),di(y)).

当y∉di时，di(y)=0，于是可得

由定理1和正域的定义可以得出

下面给出粒子群算法与高斯核模糊粗糙集相结合的属性约简算法.

算法1基于粒子群算法的高斯核模糊粗糙集属性约简算法(PSO-GKFRA).

输入：决策信息系统DIS=〈U,C∪D,V,f〉，最大迭代次数N，参数σ，ωmax，ωmin，c1，c2，α，β；

输出：模糊粗糙集属性约简Red.

1. 随机初始化粒子S={p1,p2,…,pt}

2. n←0

3. While n

4. for each piin S

5. f(pi)←α·γpi(D)+β·(|C|-|pi|)/|C|

6. if f(pi)>f(pbesti) then

7. pbesti←pi

8. end if

9. if f(pi)>f(gbest) then

10. gbest←pi

11. end if

12. end for each

13. for each piin S

14. vi(n+1)=ω(n)·v(n)+c1·rand( )·(pbesti-pi(n))+c2·rand( )·(gbest-pi(n))

15. pi(n+1)←pi(n)+vi(n+1)

16. end for each

17. n←n+1

18. End While

19. Red←gbest

20. 输出Red

3 实验与结果分析

在本节中，将使用本文提出的属性约简算法，在4个公有数据集上进行实验，以测试算法性能.

3.1 实验方案

为了说明本文所提出的算法的正确性和有效性，实验采用UCI机器学习数据集中的常用数据集进行实验和对比，数据集见表1，表中给出了所选数据集样本数、属性个数、数值型属性个数以及类别数.

表1 数据集信息

本实验粒子群算法中ωmin设置为0.2，ωmax设置为0.6，预设迭代次数N设置为50，c1和c2均设置为0.6，α设为0.8，β设为0.2，粒子数设置为所选数据集属性数的一半，详细数目见表1的最后一列.

在不同σ值下，属性约简后的数据集属性数将会产生改变，表2、3给出了本文所提的PSO-GKFRA算法在不同σ下通过本文算法进行约简后的属性个数以及该情况下的分类精度.由于粒子群算法最终约简结果会受到初始粒子随机选择的影响，所以实验中每一个σ进行5组实验，表2、3中数据均为5次实验的平均值.此外还采用Hu所提出的FS-GKA算法[8]以及经典粗糙集属性约简算法RS进行比较，比较所采用的约简结果为文献[8]中给出的约简结果，分类所采用的算法为weka中的J48算法，采用十折交叉验证进行分类精度测定.

3.2 实验结果分析

根据以上实验结果，从以下3个方面进行分析.

表2 约简属性个数比较

注：PSO-GKFRA算法的属性个数为5次实验的平均值.

表3 分类精度比较

注：1) 表中加粗的数值为当前数据集的最高分类精度； 2) PSO-GKFRA算法的分类精度为5次实验的平均值.

1)σ的变化对约简属性数目的影响

通过对表2的分析可以得出，随着σ值的增加，应用本文算法进行属性约简所得到的约简结果的属性个数在sonar、iono、wine三个只包含数值型数据集上有明显增加，而在仅包含6个数值型属性的credit下没有表现出明显的约简后属性个数的变化.σ在[0.1,1]变化时，sonar、iono、wine这三个数据集约简后，属性个数与原始属性个数之比分别在区间[7.4/60,40.8/60]=[12.3%,68%]、[6.2/34,24.2/34]=[18.2%,71.2%]、[4.6/13,10.6/13]=[35.4%,81.5%]进行变动，并且最小约简属性个数均为个位数.由此可以看出，在相同的σ值下，对属性越多的数据集，本文算法属性的约简率越高,具体见图1.

图1 iono数据集上粒子全局最优点适应度与迭代次数关系Fig.1 The relationship between global best fitness and iteration times of data set iono

图2 σ=0.15时PSO-GKFRA算法在迭代次数为10、25、50下与FS-GKA的约简时间比较Fig.2 The running time of FS-GKA and PSO-GKFRA when iteration times=10,25,50,σ=0.15

2) 本文所提算法约简的有效性

从表3中可以看出，本文所提算法在σ取不同值时数据集sonar上的通过J48进行分类的精度均优于FS-GKA以及RS算法，且在所有σ值下均高于sonar、credit、iono的原始分类精度.此外在数据集credit上σ为0.1、0.5，iono上σ为0.15、0.5时的分类精度均高于FS-GKA以及RS算法，在数据集wine上分类精度均低于FS-GKA以及RS算法，但是最高分类精度也高于原始分类精度.由此可以看出，本文算法大部分数据集下分类精度都优于FS-GKA和RS算法，且相对于原始数据集都能进行有效约简.随着σ的变化，σ在0.1或0.15时在所有数据集上取得了3次最优分类精度，结合σ越小，约简后属性越少的变化情况，说明了本文算法在约简属性的同时，能够保持或增加数据集的分类精度，说明了算法的有效性，并且给出了σ的一个较为合适的范围[0.1,0.15]，具体见图2.

3) 算法的约简效率

图1中(a)和(b)子图为在数据集iono上算法执行迭代过程.图1中横坐标为迭代次数，纵坐标为粒子的适应度，每一条线表示一次实验中全局最优点适应度随迭代次数变化的过程，每一个σ都进行了5次实验.图1(a)为本文算法在σ=0.1时对数据集iono上的计算收敛过程，图1(b)为σ=1时在数据集iono上的计算收敛过程.从图中可以看出，在σ=0.1和σ=1时，粒子均有一个较快的收敛过程，普遍在25次迭代以前就能达到最优适应度，而且实验选择的粒子数只为数据集属性数目的一半，说明该算法收敛速度较快，粒子选择较少，有较好的计算效率.此外，在两种情况下最优解与最差解的依赖度差距都在0.005左右，说明该算法有较强的鲁棒性，受初始粒子选择影响小.通过图2可以看到，本文算法在credit、sonar、iono下迭代次数为25、50次的运行时间均高于FS-GKA算法，这是由于FS-GKA算法选择出的属性相对较少，约简率均大于67%，所以依赖度的计算次数就会比较少，消耗时间比较少.而对于本文算法，粒子群算法收敛的次数相对固定，所以不管选择属性多少，时间都会比较接近，所以在选择属性较少的情况下没有优势.在数据集wine上可以看出，本文算法在25次迭代时的时间低于FS-GKA算法，此时算法已基本收敛，因此效率高于FS-GKA算法，此时该算法约简率为54%.所以，本文算法在FS-GKA算法约简率较低时能够取得一定时间上的优势.

4 总结

本文所提出的基于粒子群算法的高斯核模糊粗糙集属性约简算法在数值型数据集上，通过改变高斯核中的σ参数可以有效控制约简后的属性个数，体现了模糊粗糙集能够直接处理数值型数据的特性.通过与其他算法进行比较，证明约简结果具有较好的分类精度，粒子的快速收敛说明算法有较快的约简速度，本文所提属性约简算法是有效的.