基于非随机初始种群遗传算法的分类规则挖掘

《基于非随机初始种群遗传算法的分类规则挖掘》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9卷第2期2009年1月科学技术与工程Vo1．9No．2Jan．20091671—1819(2009)2-0283—06ScienceTechnologyandEngineering@2009Sci．Tech．Engng．基于非随机初始种群遗传算法的分类规则挖掘阮家港马金平吕晓慧(青岛大学国际商学院，青岛266071)摘要数据挖掘中分类问题一直是数据挖掘领域中研究的热点问题，先后提出了各种分类算法；其中遗传算法被认为是一种高效的分类算法。但是，传统的GA存在着易于陷入局部最优，致使得到的分类规则概括性不强的问题。提出了一种基于非随机初始种群的遗传算法分类规则挖掘算法。算法利用均匀种群方

2、法生成非随机的初始种群，并通过均匀算子确保连续迭代过程中种群的多样性，从而达到防止GA早熟的目的。采用两个标准的公共领域的数据集验证了算法的有效性。实验结果表明，该算法能消除遗传算法在分类挖掘任务中收敛于局部最优的局限性，且能快速挖掘出易于理解的分类规则，提高对知识的理解力。关键词数据挖掘分类规则遗传算法均匀种群中图法分类号TP301．6；文献标志码A数据挖掘(DataMining)是计算机科学中的一得最优分类规则集]。但是，传统遗传算法存在着个重要研究领域，其目标是从数据中抽取知识．2J。易于陷入局部最优而达不到全局最优，致使得到的分类规则是数据挖掘的主要研究内容之一，通过分分类规则概

3、括性不强的问题。析训练集数据，产生关于类别的精确描述。这种本文提出了一种基于非随机初始种群的遗传类别描述常由分类规则组成，可以用来对未来的数算法分类规则挖掘算法。利用均匀种群方法生成据进行分类预测，有着广泛的应用前景。非随机的初始种群，通过均匀算子确保连续迭代过分类规则的挖掘目前主要有以下方法：决策树程中种群的多样性并防止遗传算法的早熟，挖掘易方法、贝叶斯方法、人工神经网络方法、粗糙集方法于理解的分类规则，提高规则的简单性和对知识的等。这些方法追求的是较高的分类正确率，但往往理解力。不能抽取出使人易于理解的分类规则HJ。遗传算法是一种基于生物进化论和分子遗传学的全局随1基于非随机初始种群

4、GA分类规则挖掘机搜索算法，具有应用广泛、使用简单、鲁棒性强等算法特点。遗传算法在分类中应用的基本思想是将分类规则按某种形式进行编码，形成染色体。再随机1．1染色体编码选取N个染色体构成初始种群，然后根据预定的评一条分类规则可以看作是由合取范式构成的价函数对每个染色体计算适应值。通过遗传操作逻辑公式，规则左部的每个合取项对应一个特征属(选择、交叉、变异)来产生一群新的更适应环境的性，一个合取项又可由表示概念的析取式组成，表染色体，形成新的种群。这样一代代不断繁殖进示特征属性的不同取值；规则的右部表示满足规则化，最后收敛到一批最适应环境的个体上，从而求左部合取式的实例应归属的类别。如IF(

5、buying=vhighorhigh)AND(maint=vhighorhigh)THEN2008年l0月7日收到unacceptable就是一条由2个合取项包含了内部析第一作者简介：阮家港(1980一)，男，青岛大学管理科学与工程系取式组成的分类规则，其中buying和maint为特征硕士研究生。E—mail：ruanjiashuai@sina．corn。属性，分别表示汽车的购买价格和维修价格；unac—284科学技术与工程8卷ceptable为类标号属性，表示不可接受。设凡是所挖的基因集(尽可能等长)，如图2所示。掘数据中类标号属性的个数。则一个染色体由n个C可以看作是C。的补集，其

6、它的染色体基于基因组成，其中每个基因对应于一个特征属性。第iC。和c产生。本文以二进制编码的形式为例来解个基因划分成三个部分：标记(F)，关系算子(RO)释该方法，此法同样适用与其它的编码形式。在均和属性值(vi)，如图1所示。染色体表示一条规则匀种群方法中，从一个随机产染色体中产生2一1的整个IF语句部分并不包含此规则所预测的类标个新的染色体。因此，如果种群规模固定，将以系号属性。在GA每一次迭代中，算法搜索具有同一统的方法产生2一2个新的染色体。设IPI是固定类标号的所有染色体。因此，对于每一个预测类标的种群规模数，最大的r值要使不等式2≤lPl成号GA至少运行一次。立。然后让r以1

7、递减从而根据新的r值产生出标记字段(F)是区间范围内的一个二进制值2一2个新的染色体。依此类推直至新的r值递减变量，表示其对应的属性是否在规则中为2。在以上过程中，产生染色体的总数会大于种出现，1表示该属性出现，0表示不出现。尽管群规模数，在此情况下，我们仅选择它们中的部分每个染色体有一个固定的长度，以这种方式表示的染色体来确保固定的种群规模数。基因串意味着规则长度可变。因此，不同的染色体为简便起见，取lP}=54，新染色体的产生过