基于遗传算法的连续属性离散化方法研究

《基于遗传算法的连续属性离散化方法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于遗传算法的连续属性离散化方法研究颜菲【摘要】对连续属性进行离散化(discretization)，也即实型空间向整型空间的映射，是许多数据挖掘过程中数据预处理阶段的重要步骤。由于它在减少后继算法的时空复杂度，提高系统的鲁棒性上的重要作用而被广泛研究。本文提出了一种基于遗传算法的连续属性离散化方法，将最小断点集作为优化目标，并构造一个新的算子来保证所选断点能保持原决策系统的不可分辩关系。【关键词】连续属性离散化遗传算法【作者简介】颜菲，女，柳州运输职业技术学院信息工程系讲师。广西柳州，545007一、引言本文中提出的基于遗传算法的连续属性离散方法，建立在遗传算法的基础上，结合分

2、层聚类的思想，建立一个分层聚类树，每个树的节点可以看成连续数据的一个区间，通过选择不同的初始区间，利用遗传算法进行优化，在遗传算法中利用属性的支持度为控制条件，合理的控制了遗传进化的代数，从而提高了算法的效率。而且，由于利用了属性的支持度为控制条件，因此可以得到最好的离散化结果，提高了离散化值的准确性，为后面的属性约简操作提供了方便。二、算法的基本思想在离散化过程中，如果划分较细，可以提高对决策属性的支持，但是往往会使决策表含有很多的冗余信息，降低了约简效率；如果划分较粗，则可能增加决策表中不相容信息。因此，必须在决策属性支持度不变的条件下，寻找能提高约简效率的划分。在本算法中充

3、分考虑到这些因素的影响，使用遗传算法进行属性离散化之前，先将连续属性进行初始的断点处理，利用分层聚类的方法形成每一个条件属性的断点聚类树，可以利用经验任意选择树中的断点集，也可以多次选择树中的断点集，进行后面的离散化操作，比较几次的离散化结果中条件属性对决策属性的支持度情况，选择最优的离散化结果，这样有利于形成最优的断点划分。在遗传算法的进化过程中，本算法利用每次遗传进化后的条件属性对决策属性支持度的计算，控制是否继续进行遗传进化，可以减少遗传代数，有利于快速形成最优解。三、算法具体描述输入：决策表S=,R=C∪{d},输入条件属性集合和决策属性集合。输出：最优

4、条件属性的断点集合形成的新决策表Sp=步骤：(1)在条件属性集合中选择每个条件属性1…n，对属性1…n进行分层聚类，生成n棵断点树，设置初始的正整数r，作为循环控制条件，x=0。(2)在每一棵断点树中任意选择一组断点集合（集合的选择可以根据支持度大的再次被选中的原则进行选择)，计算各条件属性断点集合对决策属性支持度，spt1(d)…sptn(d)为初始支持度。(3)将断点集合进行组合，利用基于支持度的遗传算法(SupportbySimpleGeneticAlgorithms,SSGA)优化断点，算法SSGA计算生成的各条件属性断点对决策属性支持度spt2(d

5、)',a为条件属性1…n，如果ifspta(d)'-spta(d)>0and

6、spta(d)-spta(d)'

7、>ε，thenspta(d)=spta(d)'；在每一个断点树中选择一组断点集合，集合的选择可以根据支持度大的再次被选中的原则进行选择；返回(3)；elseif

8、spta(d)-spta(d)'

9、<ε：(ε为任意小的正整数，a为条件属性1…n)thenx=x+1；ifx>rreturn结束算法生成新的决策表，离散化结束；elsereturn(2)；(4)选择其中条件属性对决策属性支持度最大的断点集，作为最优离散化结果。其中，在本算法步骤(2)中，分层聚类的方法将数据对象

10、组成一棵聚类树，根据层次分解顺序的不同可以分为凝聚的层次聚类和分裂的层次聚类两种，本算法中应用的是凝聚的层次聚类方法。步骤：(1)首先对条件属性中属性初始点集合进行排序，使初始按由小到大的顺序排列。(2)比较前后两点的距离，如果距离小于ε，选取距离最小的两点进行聚类，删除这两点，将这两点距离的平均值作为新的点，加入属性点集中，重复(2)的操作，直到形成属性的聚类树。在算法步骤(3)中，遗传算法优化断点(SSGA)算法描述：步骤：(1)设置初始m(m为控制循环次数)，x=0，条件属性断点对决策属性支持度spta(d)'=0，a为条件属性1…n；(2)initializepop(t)

11、：初始化随机产生初始种群pop(t)；(3)evaluatepop(t)：对pop(t)适应值进行评估；(4)while(x<=m)do(5){从pop(t)中选择下一代pop(t+1)；(6)crossoverpop(t+l)：对pop(t+l)进行杂交操作；(7)mutatepop(t+l)：对pop(t+l)进行变异操作；(8)计算生成条件属性断点对决策属性支持度spta(d)",a为条件属性1…nifspta(d)''-spta(d)'>0and

12、spta(d)''-sp