一种基于改进粒子群的连续属性离散化算法

汪凌

1.北京交通大学中国产业安全研究中心，北京 100044

2.固体废物处理与环境安全教育部重点实验室，北京 100084

一种基于改进粒子群的连续属性离散化算法

汪凌

1.北京交通大学中国产业安全研究中心，北京 100044

2.固体废物处理与环境安全教育部重点实验室，北京 100084

1 引言

决策系统中的连续属性离散化在机器学习、数据挖掘等领域具有十分重要的作用。粗糙集理论只能处理离散型数据，而样本数据大多为连续属性。因此，离散化是粗糙集理论处理连续问题的关键，离散化结果直接关系到后续的数据挖掘。目前，国内外学者提出了多种属性离散化算法。如文献[1]给出了基于属性重要性的启发式离散化算法；文献[2]给出了基于信息熵的离散化算法；上述方法都充分考虑了决策表的不相容性，但算法时间复杂度较大；文献[3]给出了基于遗传算法的离散化方法，该方法计算速度较慢，且局部搜索能力差；文献[4]给出了基于聚类分析的连续属性离散化算法，该算法对于决策系统中数据量较大时存在计算复杂度较大、离散化效率较低等缺点。鉴于上述分析，本文将集群智能优化理论和粗糙集理论相结合，提出一种基于改进粒子群的连续属性离散化算法。算法分析和实验结果表明，该算法具有较好的离散化效果，能使决策系统的信息损失降低到最小，并可获取更为简洁的决策规则。

2 数据一致性度量

为了使离散化后保持决策系统中原有数据信息，可采用粗糙集理论对决策系统中数据进行一致性度量（或辨识函数）LC(D)=γC(D)，其中γC(D)为粗糙集决策属性D对条件属性C的依赖度，也称为分类质量，即

其中，POSC(D)为D的C正域，-CX为X的下近似集。数据一致性是属性离散化和属性选取的一个有效度量，反映了决策系统中根据条件属性C的信息对所有实例关于决策属性D的等价类的分辨能力，当γC(D)=1时称决策系统是相容的或协调的。因此，粗糙集中的连续属性离散化可以根据离散化后数据“一致性”值逐次调整终止条件，直至不一致性为零（最小），其目的是保持原有数据的分辨能力。

3 粒子群算法及其改进

3.1 基本粒子群算法

粒子群优化算法[5]（Particle Swarm Optimization）是Eberhart和Kennedy于1995年提出的一种基于集群智能优化算法，主要适用于求解非线性、不可微等复杂优化问题。由于PSO算法具有简单、计算速度快、易于获得全局最优解等优点，现已广泛应用于函数优化、神经网络训练及模糊系统控制等领域，但是该算法存在收敛精度较低，且易陷入局部最优等缺点。

3.2 改进的粒子群算法

为了防止陷入局部极值，有效提高粒子群算法的精度和全局收敛性能，本文对基本PSO算法进行以下改进，以便更好地进行连续属性离散化处理。

（1）初始化的改进：基本粒子群算法中一般粒子群的初始化均采用随机方法产生，如文献[7]提出均匀设计的方法产生的分割点集构成的初始群体比随机产生的初始群体更能从统计意义上反映出目标函数的特性。本文提出利用符合均匀分布的随机数来初始化粒子群体的位置，以此优化全局寻优效果。

（2）对最优粒子和最差粒子的处理：PSO算法中，每个粒子都是随机运动的，当最优粒子飞行到某一步时，若适应度变差，则下一步就会从变差的位置继续飞行，因而不能充分发挥最优粒子应有的优势功能。为了有效更新粒子群体中粒子的速度和位置，对于每一步最优粒子的飞行，现采用试探方法使其朝着适应度变优的方向飞行，即最优粒子飞行一步后，若适应度变好，则从新的位置继续飞行；若适应度变差，则返回原位置重新搜索。同时，对于每一步最差的粒子的飞行，应用该步的历史全局最优粒子取代。

（3）惯性权重w的取值：在粒子群体优化过程中，合理控制全局搜索和局部搜索的能力对于有效寻求最优解是非常关键的。从公式（2）可以看出，惯性权重w决定了粒子在上一个位置的速度对目前位置粒子的影响。因而，通过控制惯性权重w的值可以维护局部搜索和全局搜索的平衡，准确高效地搜索全局最优解。当w较大时，粒子有能力扩展搜索空间，全局搜索能力较强，但是收敛性相对下降；当w较小时，粒子可在特定区域内精细搜索，局部搜索能力较强。为了克服基本PSO算法固定参数不足的缺点，本文拟采用自适应MPSO算法调整w的策略，即让w随算法的迭代进行线性的减少。惯性权重w调整方法如式（4）所示：

其中，wmax、wmin分别为惯性权重的最大值与最小值，iter为当前迭代次数，itermax为最大迭代次数。

4 改进粒子群的属性离散化算法

4.1 初始分割点集选取

4.2 初始分割点集编码

为了简化问题的描述，本文拟采用二进制编码方式对决策系统中连续属性初始分割点集编码。用长度为P的二进制串来表示一个个体，该串由M个子串组成，每个子串对应决策系统中一个条件属性的初始分割点集，每一位对应一个分割点。其值“1”和“0”分别代表该分割点的“取”和“舍”。

4.3 适应度函数

适应度函数用来确定群体中个体的适应度值，而适应度值是粒子群算法中区分个体“好坏”的唯一标准，也是更新粒子群的唯一依据。由分割点选取的合理性衡量标准可知，个体的适应度主要取决于两个方面：一是所包含的分割点数应该尽可能少；二是利用该分割点进行离散化后应保持决策系统的一致性。因此适应度函数由分割点数和分辨关系两者共同确定。综合起来，适应度函数可定义为：

其中，x为个体所表示的分割点集，P表示个体的二进制串长度，即初始总分割点数，Lx为个体所包含的分割点数目，γC(D)为粒子所包含的分割点划分后的决策系统中决策属性对条件属性的依赖度，α、β为权重调节因子。显然，分割点数目越小，粒子的适应度值越大；分类质量越大，决策系统一致性越高，适应度值越大。

4.4 算法步骤

步骤1初始化算法参数。设定粒子群体规模M、学习因子c1和c2、惯性权重w的上下限及粒子更新的速度限值等，设置最大迭代次数itermax，设定迭代次数iter=0，随机产生M个粒子，按均匀分布函数初始化粒子的初始位置xi，粒子的初始速度νi设为0，个体极值pbest，i，全局极值gbest。

步骤2根据每个粒子i表示的分割点集将初始决策系统DS转化成离散化的决策系统DSP，计算离散化后分割点数和决策系统中决策属性对条件属性的依赖度γC(D)，作为每个粒子的适应度值Fitness(i)。

步骤3对群体中的每个粒子i，执行以下操作步骤：

（1）根据公式（5）计算各粒子i的适应度值Fitness(i)；

（2）若Fitness(i)优于此前的个体极值pbest，i，则将其设为pbest，i；若最佳的pbest，i优于此前的全局极值gbest，则将其设为gbest。

步骤4根据公式（2）～（4）更新每个粒子的速度νi和位置xi；若νi〉νmax，则取νi=νmax，若νi〈νmin，则取νi=νmin。

步骤5根据每个粒子i表示的分割点集将初始决策系统DS转化成离散决策系统DSP；然后根据公式（1）计算决策属性对条件属性集的依赖度γC(D)，调整粒子的适应度值Fitness(i)。

步骤6对每一步的最优粒子和最差粒子进行处理。

步骤7若迭代次数达到itermax，则转入步骤9，否则转入步骤8。

步骤8判断γC(D)是否等于1，若是转入步骤9，否则iter=iter+1，自适应调整惯性权重w，转回步骤3继续迭代。

步骤9输出适应度值最优的粒子(gbest)作为最优分割点集对决策系统进行离散化。

连续属性离散化的改进PSO算法流程如图1所示。

4.5 算法复杂度分析

设决策系统的实例数为N，粒子群体大小为M，条件属性分割点数为R，最大迭代次数为L。本算法的计算复杂度主要由步骤2～步骤9所决定的。

步骤2中计算离散化的决策系统DSP，时间复杂度为O(N2)；

步骤3中计算适应度函数Fitness(i)，计算量为M×R× N2，由于粒子群体大小M、条件属性分割点数R都是常量，与决策系统实例数N相比可以忽略，因此计算适应度函数的时间复杂度为O(N2)；

图1 连续属性离散化的改进PSO算法流程图

步骤4～步骤9计算最优分割点集，其计算量为L×O(N2)，L为有限常量，因此算法时间复杂度为O(N2)。

综上所述，本算法总的时间复杂度为O(N2)，是一个比较有效的属性离散化算法。

5 实验结果及分析

为了验证改进的PSO离散化算法的有效性及性能，从UCI机器学习数据库中选取5组数据集进行离散化。为便于比较，将改进的PSO离散化算法实验结果和基于属性重要性的离散化算法、基于信息熵的离散化算法、遗传算法进行性能对比实验。实验基本配置CPU为3 GHz，内存为512 MB，仿真软件为Matlab7.0。改进的粒子群算法的基本参数设置：粒子群规模30，学习因子c1=c2=2.0，惯性因子wmax=1.2、wmin=0.4，粒子速度在[-4，4]间变化，最大迭代次数为itermax=50。

实验过程根据以下四个步骤进行：（1）从数据库中随机抽取70%的数据作为训练集，30%的数据作为测试集；（2）采用本算法对训练集进行离散化，得到离散化后的分割点集；（3）用训练集的分割点集对相应的测试集进行离散化；（4）用C5.0算法从训练集中获取分类规则对测试集进行判断获得平均分类精度。所有实验结果均为10次实验平均值。其中，表1给出了各数据集的基本信息，表2给出了四种离散化算法实验结果的相应数据。

表1 数据集基本信息

表2 四种离散化算法的实验结果比较

从实验结果可以看出：

（1）在对初始分割点进行筛选的四种算法中，改进PSO算法的初始分割点数明显少于其他三种算法的初始分割点数。这主要是因为改进PSO算法属全局寻优离散化算法，考虑了属性之间的依赖关系和决策系统的一致性等情况；而其他三种离散化算法仅考虑属性重要性或分割点重要性等。这表明，对于相同的一组实例数据，改进的PSO离散化算法可以对特定属性空间实现更简单的离散划分。

（2）与其他三种算法相比，本文提出的改进PSO离散化算法能大幅度提高规则的分类精度。由于改进PSO算法结合了粗糙集理论的思想，考虑了属性间的相互影响，从而产生了比较合理的分割点，提高了规则的分类精度；而其他三种离散化算法的分类精度主要来源于评价标准值的计算。

（3）在计算时间上，改进PSO离散化算法和遗传算法的计算时间比其他两种算法在相应数据集上的计算时间大。这是由于改进的PSO算法和遗传算法都属全局离散化算法，在初始分割点选择、样本数和迭代次数等方面都影响算法的计算时间。此外，改进的PSO离散化算法中，glass数据集的计算时间最高，这是因为glass数据集的决策分类最多，而改进PSO算法要考虑条件属性和决策属性之间的依赖关系。

（4）四种算法在数据集glass上的结果分割点数最多，这是因为数据集glass的决策分类数较多，从而导致glass数据集的分割点数最多。另外，四种算法在glass数据集上的测试精度也较低，这也与glass数据集的决策分类数较多等有关。由此可见，在数据集的样本数和连续属性数不变的条件下，决策分类越多，则分割点数越多，测试精度越低，计算时间越长。

6 结束语

决策系统中连续属性离散化是压缩数据、提取决策规则的有效手段。针对当前属性离散化算法中分割点选取存在的数量及选取合理性等问题，本文结合粗糙集理论和集群智能优化理论，提出一种基于改进粒子群的连续属性离散化算法，并以UCI机器学习数据库作为测试集，进行了仿真实验。算法分析和实验结果表明，本文算法具有较好的离散化效果，能使决策系统的信息损失降低到最小，并可获取更为简洁的决策规则。

[1]侯利娟，王国胤，聂能，等.粗糙集理论中的离散化问题[J].计算机科学，2000，27（12）：89-94.

[2]谢宏，程浩忠，牛晓东.基于信息熵的粗糙集连续属性离散化算法[J].计算机学报，2005，28（9）：1570-1574.

[3]赵卫东，戴伟辉，蔡斌.遗传算法在决策表连续属性离散化中的应用研究[J].系统工程理论与实践，2003（1）：62-67.

[4]韩秋明，赵轶群.Rough Set中基于聚类的连续属性离散化方法[J].计算机工程，2003（3）：81-87.

[5]Kennedy J，Eberhart R C.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks.Piscataway：IEEE Press，1995：1942-1948.

[6]Maurice C，Kennedy J.Τhe particle swarm explosion，stability，and convergence in a multidimensional complex space[J].IEEE Τransactions on Evolutionary Computation，2002，6（1）：58-73.

[7]张腾飞，王锡淮，肖键梅.基于微粒群优化的连续属性离散化[J].计算机工程，2006，32（3）：44-46.

[8]刘业政，杨善林，钟金宏.基于粗集理论的冗余分割点约简[J].计算机工程，2002（8）：17-19.

[9]陈国初，俞金寿.增强型微粒群优化算法及其在软测量中的应用[J].控制与决策，2005，20（4）：377-381.

[10]Shi Y，Eberhart R.A modified particle swarm optimizer[C]// Proceedings of IEEE International Conference on Evolutionary Computation，1998：69-73.

[11]王立宏，吴彦，吴耿锋.离散化的一种启发式搜索算法[J].计算机应用，2004，24（8）：41-43.

[12]王立宏，孙立民，孟佳娜.数值离散化中粒度熵与分类精度的相关性[J].重庆大学学报，2008，31（1）：57-61.

[13]Nguyen H S.Discretization of real value attributes：a boolean reasoning approach[D].Warsaw：Computer Science Department，University of Warsaw，1997.

[14]Nguyen H S，Skowron A.Quantization of real values attributes[C]//Proc of the 2nd Joint Annual Conference on Information Science，Wrightsville Beach，North Carolina，1995：34-37.

[15]姚耀如，徐玉如.粒子群优化算法分析[J].哈尔滨工程大学学报，2007，28（11）：1242-1246.

[16]Eberhart R C，Shi Y.Particle Swarm Optimization：developments，applications and resources[C]//Proceedings of the IEEE Congresss on Evolutionary Computation.Piscataway，NJ：IEEE Service Center，2001：81-86.

WANG Ling

1.China Center for Industrial Security Research,Beijing Jiaotong University,Beijing 100044,China
2.Key Lab for Solid Waste Management and Environment Safety,Ministry of Education of China,Beijing 100084,China

An algorithm of continuous attribute discretization based on improved particle swarm is proposed.Τhe algorithm combines intelligent optimization theory and rough sets theory.Each attribute discretization points are initialized to particle group, seeking the optimal discretization points through the interaction between particles.Discretization algorithm is applied to the UCI data sets in the experiment,and the experimental results show that,the algorithm can make the loss of information decision system reduce to the minimum,and get more concise decision rules.

improved particle swarm;intelligent optimization;rough sets;continuous attribute discretization

提出一种基于改进粒子群的连续属性离散化算法。该算法结合集群智能优化理论和粗糙集理论，将各属性离散化分割点初始化为粒子群体，通过粒子间的相互作用寻求最优离散化分割点。将提出的离散化算法应用于UCI数据集实验中，实验结果表明，该算法能使决策系统的信息损失降低到最小，并可获取更为简洁的决策规则。

改进粒子群；智能优化；粗糙集；连续属性离散化

A

ΤP311

10.3778/j.issn.1002-8331.1305-0492

WANG Ling.Algorithm of continuous attribute discretization based on improved particle swarm.Computer Engineering and Applications,2013,49（21）：29-32.

教育部人文社会科学研究青年基金项目（No.11YJC630195）；安徽省高校省级自然科学研究重点项目（No.KJ2012A076）；固体废物处理与环境安全教育部重点实验室开放基金项目（No.SWMES 2011-05）。

汪凌（1976—），男，博士后，研究方向：粗集决策分析、数据挖掘、智能交通等。E-mail：tcwling@126.com

2013-06-04

2013-08-30

1002-8331（2013）21-0029-04