（计算机应用技术专业论文）基于遗传算法的关联规则挖掘研究.pdf

摘要 摘要 数据挖掘是指从大型数据库的数据中提取出隐含的、事先未知的、潜在有用 的信息的非平凡过程。而关联规则是数据挖掘中一个重要的技术，也是在无指导 学习系统中挖掘本地模式的最普通形式。遗传算法则是一种基于生物进化论和分 子遗传学的全局随机搜索算法。 本文对遗传算法和关联规则分别进行了阐述和研究。并在此基础上，进一步 研究了基于遗传算法的关联规则数据挖掘。首先对遗传算法的关键技术进行了分 析，其中包括适应度函数的设计、遗传算子的操作等，尤其是在染色体编码中应 用了实数编码，从理论上解释了如何应用遗传算法解决实际问题。其次在分析遗 传算法的基础上阐述了如何和关联规则结合起来，对数据库进行挖掘。而且为了 更好挖掘关联规则，提出了一种增加关联规则属性的计算方法，即从原有的支持 度、置信度属性之外再添加一项规则关注规则的方法，改进了通常以往关联 方法中仅依靠规则的支持度和置信度来评价关联事物的特点，从而使得到的关联 规则包含有更多的信息，更加有助于用户的理解。 本文采用遗传算法和关联规则相结合的算法来寻找最优解，提高了通常关联 规则算法( 如a p r i o r i 算法) 处理大型数据库的效率，避免了资源浪费。通过 实验表明，这种算法切实可行、可操作性好、得到的结果也易于理解。 关键词：数据挖掘；关联规则；遗传算法；关注规则 a b s t r a c t a b s t r a c t t h ed a t am i n i n gi st h a tf i n d i n gt h ec o n c e a l m e n tu n k n o w n ，b e f o r e h a n d ，t h el a t e n t u s e f u li n f o r m a t i o nn o n - o r d i n a r yp r o c e s sf r o mt h el a r g e s c a l ed a t a b a s ed a t a a tt h e s a m et i m e ，a s s o c i a t i o nr u l ei sa ni m p o r t a n tt e c h n o l o g yi nt h ed a t am i n i n g a l s oi ti st h e m o s tc o n v e n t i o n a ld a t am i n i n gl o c a lp a t t e r ni nt h ei n s t r u c t i o ns t u d ys y s t e m t h e g e n e t i ca l g o r i t h m si so n ek i n db a s e do nt h eb i o l o g i c a lt h e o r yo fe v o l u t i o na n dt h e m o l e c u l a rg e n e t i c so v e r a l ls i t u a t i o ns t o c h a s t i cs e a r c ha l g o r i t h m t h i sa r t i c l eh a sc a r r i e do nt h ee l a b o r a t i o na n dt h er e s e a r c hs e p a r a t e l yt ot h e g e n e t i ca l g o r i t h m sa n dt h ea s s o c i a t i o nr u l e a n di nt h i sf o u n d a t i o n ，h a sf u r t h e rs t u d i e d b a s e do nt h eg e n e t i ca l g o r i t h m sa s s o c i a t i o nr u l ed a t am i n i n g f i r s tt h i sa r t i c l eh a s c a r r i e do nt h ea n a l y s i st ot h eg e n e t i ca l g o r i t h m se s s e n t i a lt e c h n o l o g y ，i n c l u d i n gt h e f i t n e s sf u n c t i o nd e s i g n ，t h eg e n e t i co p e r a t o ro p e r a t i o na n ds oo n ，a p p l i e dt h er e a l n u m b e rc o d ei np a r t i c u l a ri nt h ec h r o m o s o m ec o d e ，t h e o r e t i c a l l ye x p l a i n e dh o w a p p l i e st h eg e n e t i ca l g o r i t h m ss o l u t i o na c t u a lp r o b l e m n e x te l a b o r a t e di nt h ea n a l y s i s g e n e t i ca l g o r i t h m sf o u n d a t i o nh o wu n i f i e sw i t ht h ea s s o c i a t i o nr u l e ，c a r r i e so nt h e e x c a v a t i o nt ot h ed a t a b a s et h et e c h n o l o g y m o r e o v e ri no r d e rt ot h eb e t t e re x c a v a t i o n a s s o c i a t i o nm l e ，p r o p o s e do n ei n c r e a s ea s s o c i a t i o nr u l ea t t r i b u t e c o m p u t a t i o n a l m e t h o d ，n a m e l yf r o mo r i g i n a ls u p p o r t ，t h ec o n f i d e n c ea t t r i b u t ei n c r e a s e sar u l e a t t e n t i o nr u l ea g a i nt h em e t h o d ，i m p r o v e df o r m e r l yh a sb e e nc o n n e c t e di nt h em e t h o d o n l yt od e p e n du p o nt h er u l eu s u a l l ys u p p o r ta n dt h ec o n f i d e n c ea p p r a i s e st h e a s s o c i a t i o nt h i n gt h ec h a r a c t e r i s t i c ，t h u sc a u s e dt ot h ea s s o c i a t i o nr u l ec o n t a i n e dh a s m o r ei n f o r m a t i o n e v e nm o r ew a s h e l p f u lt ou s e r su n d e r s t a n d i n g t h i sa r t i c l eu s e st h ea l g o r i t h mw h i c ht h eg e n e t i ca l g o r i t h m sa n dt h ea s s o c i a t i o n r u l eu n i f i e st os e e kt h eo p t i m a ls o l u t i o n ，e n h a n c e dt h eu s u a la s s o c i a t i o nr u l ea l g o r i t h m ( f o re x a m p l et h ea p r i o r ia l g o r i t h m ) t op r o c e s st h el a r g e s c a l ed a t a b a s et h ee f f i c i e n c y ， a v o i dt h er e s o u r c e sw a s t e i n d i c a t e dt h r o u g ht h ee x p e r i m e n t ，t h i sa l g o r i t h mp r a c t i c a l a n df e a s i b l e ，t h ef e a s i b i l i t yg o o d ，o b t a i n st h er e s u l ti sa l s oe a s yt ou n d e r s t a n d k e yw o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e ；g e n e t i ca l g o r i t h m s ；a t t e n t i o nr u l e 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人 在论文写作中参考的其他个人或集体的研究成果，均在文中以明确方式标 明。本人依法享有和承担由此论文产生的权利和责任。 声明人( 签名) ：捌 年月日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有 权保留并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查 阅，有权将学位论文的内容编入有关数据库进行检索，有权将学位论文的 标题和摘要汇编出版。保密的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密() ( 请在以上相应括号内打“”) 日期：删年 m i n c o n f ，s u p p ( r ) 三m j n s u p ，则 称关联规则r 关于数据库成立。规则的前项及后项必须是频繁的是一个关联规 则成立的必要条件。一个关联规则必须同时满足最小支持度和最小置信度条件， 二者缺一不可。如果一个规则的置信度为1 0 0 ，但是它描述的并不是数据库中 的一个普遍模式，由于它不满足最小支持度的约束，该规则也应该被删除。假设 一个规则具有足够大的支持度，但是置信度却很低，例如购买电脑的顾客中5 的人也购买了衣服。这一事实虽然被数据库中的大部分数据支持，但是由于它不 能表示出项目间的较强的相关性，因此也不能作为一个关联规则存在。规则前项 及后项不相交条件并不是必须的：如果去掉这一约束条件不会产生错误的规则， 只是会产生冗余或没有意义的规则。如果xj y 是一个正确规则，由于 xj x u y 与xj y 是等价的，因此规则x _ x u r 就没有意义。规则的前项 x 可以是空集，每个交易都支持空项目集，因此整个数据库也支持空项目集。前 项为空集的规则的置信度等于后项目集的相对频度。同样道理，规则的后项y 必 须是非空的项目集，并且前项和后项项目集不能相交。对交易t 来说，规则r ： x j y 的置信度是一个条件概率，即c o n f ( r ) = p ( y tj x r ) 。如果y = 中， 则会出现如下情况：c o n f ( g ) = p ( 中tj x 丁) = s u p p ( x u 西) s u p p ( x ) = 1 。这 表明规则与x j x 与x 等m 是等价的。 3 1 2 关联规则的性质 关联规则项目集，具有以下四个性质。 性质3 1 ：规则的非结合型。 如果规则x j z 及y j z 在d 中成立，规则xu 王，j z 不一定在d 中 成立。如果x n y = ，并且d 中支持z 的所有交易都只支持x 或y ，则集 合x u y u z 的支持度为0 ，因此x u y j z 的置信度为0 。 类似的：如果规则x j y 及x j z 成立，规则x j y u z 不一定成立。 性质3 2 ：规则的不可分解性。 如果x u y j z 在d 中成立，规则x j z 及y j z 不一定在d 中成立。 第三章关联规则挖掘技术 例如，当z 只出现在一个交易中时，如果x 及y 也出现在其中，即s u p p ( x u y ) = s u p p ( z ) ，规则就是不可分解的。另外，如果x 与y 的支持度与x * y 的支 持度相比足够大，就会使得分解后的两个规则不具有所要求的置信度，因而规则 也不可分解。 因为s u p p ( x u y ) s u p p ( x u y u z ) 及s u p p ( x u z ) s u p p ( x o y u z ) ， 所以如果规则x j y u z 成立，则规则x j y 及x j z 都成立。由此可得较小规 则的支持度与置信度与原规则相比都有所增大。 性质3 3 ：规则的不可传递性。 由规则x j y 及y j z 成立不能推出规则x j z 。设t ( x ) c t ( y ) c t ( z ) 最 小置信度为m i n c o n f ，c o n y ( xjy ) = c o n y ( yjz ) = m i s c o n f 。 由t ( x ) c t ( y ) 可得c o n y ( x 辛y ) = s ( x u y ) i s ( y ) = s ( x ) s ( y ) = m i n c o n y 由t ( y ) c t ( z ) 可得c o n y ( yjz ) = s ( y u z ) s ( z ) = s ( y ) i s ( z ) = m i n c o n y 由t ( x ) c t ( z ) 可得c o n f ( xj z ) = s ( x u z ) s ( z ) = s ( x ) s ( z ) = m i s c o n f 由以上公式及m i n c o n f l ，可得c o n y ( xjz ) = m i s c o n f2 k 式中d 或k 是适当的常量。以上表达式基本上代表统计独立性的检验。显然， 必须考虑到已分析项集间的统计独立性的因素，从而决定关联规则是否有用。在 这个例子中，该检验过程会得出错误的结果： s ( x ，y ) 一s ( x ) 水s ( y ) = o 4 - 0 6 * 0 7 5 = 一0 0 5 ( 0 因此，尽管参数s 和c 的值都很高，但规则却没有意义。在这个例子中甚至 是错误的。所以，如果我们把支持度和置信度设得足够低，那么我们将得到两条 矛盾的规则。但另一方面，如果我们把那些参数设得足够高，我们只能得到不精 确的规则。总之，没有一对支持度和置信度的组合可以产生完全正确的关联。因 此本文中引入了关注规则，用来修剪无意义的规则，即避免生成“错觉”的关联 规则。关注规则本文设定是在基于统计独立性假设下真正的强度与期望的强度之 比，再加上一个适当的权重定义的。用来弥补支持度和置信度的不足之处。 3 3 2 用户自身决定规则的有效性 上面的讨论只是基于算法本身产生规则方面的考虑，但是一个规则的有用与 否最终取决于用户的感觉。只有用户可以决定规则的有效性、可行性。所以我们 应该将用户的需求和系统更加紧密的结合起来。 可以采用一种基于约束( c o n s t r a i n t - b a s e d ) 的挖掘。具体约束的内容可以有： 1 数据约束。用户可以指定对哪些数据进行挖掘，而不一定是全部的数据。 2 指定挖掘的维和层次。用户可以指定对数据哪些维以及这些维上的哪些 层次进行挖掘。 3 规则约束。可以指定哪些类型的规则是我们所需要的。引入一个模板 ( t e m p l a t e ) 的概念，用户使用它来确定哪些规则是令人感兴趣的，而哪 些则不然：如果一条规则匹配一个包含的模板( i n c l u s i v et e m p l a t e ) ，则 是令人关注的，可以采用的；然而如果一条规则匹配一个限制的模板 ( r e s t r i c t i v et e m p l a t e ) ，则被认为是缺乏关注的，不能使用的。 其中有些条件可以和算法紧密的结合，从而即提高了效率，又使挖掘的目的 更加的明确化了。其他的方法还有： 第三章关联规则挖掘技术 k l e i n b e r g 等人的工作是希望建立一套理论来判断所得模式的价值，他们认 为这个问题仅能在微观经济学框架里被解决，他们的模型提出了一个可以发展的 方向。他们引入并研究了一个新的优化问题分段( s e g m e n t a t i o n ) 问题，这个 框架包含了一些标准的组合分类问题。这个模型根据基本的目标函数，对“被挖 掘的数据”的价值提供一个特殊的算法的视角，显示了从这方面导出的具体的优 化问题的广泛的应用领域。k o r n 等就利用猜测误差( 这里他们使用“均方根”来 定义) 作为一些从给定的数据集所发现的规则的“好处”( g o o d n e s s ) 的度量。 3 4 关联规则的扩展 关联规则常见的几种扩展有： 1 多概念层次关联规则( a s s o c i a t i o nr u l e sw i t hh i e r a r c h y ) 刚开始的关联规则大都集于单层次的概念，但在现实生活中，有的用户感兴 趣的规则是由多层次的概念组成的。比如“6 0 买尿布的人也会买啤酒”是在较 高层次上的规则，但若在较低层次上得到“5 0 买强生尿布的人也会买向阳坊的 面包”规则也许会更加有用，因为它传递的消息更具体更明确。 2 基于约束的关联规则( c o n s t r a i n e da s s o c i a t i o nr u l e s ) 现实生活中，用户通常会对挖掘出的关联规则的子集感兴趣，例如用户可能只想 看到某些项目间的关联关系。基于约束的关联规贝1 ( c o n s t r a i n b a s e da s s o c i a t i o n r o l e s ) ，其中约束是用布尔表示的。一个简单的例子就是( 毛衣 布鞋) v ( 衣服a 一 运动鞋) ，它表示对规则的约束，规则中要么包含毛衣和布鞋，要么包含衣服但 不包含运动鞋。算法没有采取传统方法，先发现所有的规则，再修剪不满足约束 的规则，而是直接把约束结合到算法中去，大大提高了发现规则的效率。 3 周期关联规则“9 12 ”( p e f i o d i c “r u l e s ) 在数据的序列模式中，关联规则有时会显示出一些周期特性( p e r i o d i c a l p r o p e r t i e s ) 。而且有些规则在一个小的时间区段内有较高的支持度，但在整个数 据库中却没有。 4 加权关联规则。“( w e i g h t e da s s o c i a t i o nr u l e s ) 加权关联规则框架在计算支持度时，既要考虑规则中所有项目在数据库中同 时出现的频率，也要考虑所有项目的加权值。对此问题一个简单的办法是忽略权 基于遗传算法的关联规则挖掘研究 值较小的项目，但有的规则在高权值的项目相关的同时，很可能也与低权值的项 目相关。例如，在促销商品a 时，可能发现商品a 销售受到商品b 的影响，即有规 则b j a ，而商品b 最初由于我们不感兴趣而被赋予较低的权值。如果我们因权值 较低而忽略了商品b ，那么规则b j a 就不可能被发现，因此，该方法在这种情况 下是不可取的。另一种方法是直接采纳现有的关联规则发现算法，如a p r i o r i 算法， 这些算法基于所谓的向下封闭特性，即频繁项目集的任一子集必是频繁的。然而 在加权关联规则模型中，该性质不再成立，因此采用以前的算法只改变支持度的 计算是不行的 5 负关联规则。2 1 ( n e g a t i v ea s s o c i a t i o nr u l e s ) 负关联规则问题。也就是说如果顾客买了某些项目，那么他就可能不会去买 另一些项目。对此，一般形式的关联规则是不能做出回答的。负关联规则形如： “大多数顾客买速冻食品就不会买蔬菜。” 6 序列模式( s e q u e n t i a lp a t t e r n s ) 序列模式发现的是一定时间内项目间的共同出现( c o o c c u r r e n c e ) ，它构建于 关联的基本结构上，和关联有些类似，不过在分析和产生规则时把时间的概念加 了进去。序列模式的一个例子如“客户通常买了x 股票后，再去买y 股票，然后再 去买z 股票。 7 比例规则( r a t i or u l e s ) 关联规则反映的是项目间的关联，比例规则反映的则是不同项目的数量或价 钱之间的相互关系，例如“客户经常花1 ：5 ：7 的钱去购买电影票：饮料：零食。 第四章基于遗传算法的分类规则挖掘研究 第四章基于遗传算法的分类规则挖掘研究 4 1 遗传算法的基本原理 遗传算法o “( g e n e t i ca l g o r i t h m s g a ) 是模拟达尔文的遗传选择和自然淘汰 的生物进化过程的计算模型，它是由美国m i c h i g a n 大学的j h o l l a n d ”1 教授于1 9 7 5 年首先提出的。自然选择理论认为，生物要生存下去，就必须进行生存斗争，凡 是在生存斗争中获胜的个体都是对环境适应性比较强者，自然选择过程就是适者 生存、不适者淘汰的过程，遗传和变异在生物进化过程中起着决定性的作用，遗 传是指，父代与子代之间性状上存在的相似现象，变异是指，父代与子代之间在性 状上或多或少地存在的差异现象。遗传能使生物的性状不断地传送给后代，因而 保持物种的特性，变异能使生物的性状发生改变，从而适应新的环境而不断地向 前发展。现代遗传学研究表明，遗传物质的载体是染色体( c h r o m o s o m e ) ，而基 因( g e n e ) 又是染色体的功能单位和结构单位，染色体中基因的位置和基因的取 值决定了染色体的特性，也就决定了生物个体的性状。染色体有两种表现模式： 一是表现型，即指生物个体表现出来的性状；另一是基因型，是指与表现型密切 相关的基因组成。遗传算法是自然遗传学和计算机科学相结合而形成的一种新的 计算方法。遗传算法处理的是染色体，但它处理的不是染色体的表现型个体，而 是基因型个体，也就是说遗传算法不能直接处理问题空间的解数据，所以在执行 以前必须先将问题空间的数据( 表现型) 转换成基因型串结构，此过程叫做编码。 遗传算法执行完毕后，还需将结果中的基因型还原成表现型，该过程称作译码。 遗传算法处理的不是一个染色体，而是由一定数量的染色体组成的群体 ( p o p u l a t i o n ) ，遗传算法的基本方法是以群体中的个体为对象，对其进行选择、 交叉和变异等遗传操作。通过遗传操作使群体一代又一代地不断进化，最终得到 最优解。群体的进化以一初始群体( 通过随机的方法产生) 为初始代进行，初始 代中个体的数目称作群体大小或群体规模。在进化的过程中，以个体对环境的适 应度( f i t n e s s ) 函数值为依据评估其优劣，从当前群体中选出优良的个体，使它 们有机会作为父代繁殖子孙，这是与达尔文的自然进化学说相符的。 基于遗传算法的关联规则挖掘研究 遗传算法是模仿自然界生物遗传进化过程中“物竞天泽、适者生存”的原理 而开发出的一种全局优化随机搜索算法，具有自组织、自适应、自学习等特征， 能获得较高的效率，而且具有简单、易操作和通用的特性。但是，由于在遗传进 化过程中新一代种群的产生主要是依靠上一代种群之间的随机交叉重组来完成 的，所以即使己经搜索到最优解附近，如果想达到这个最优解，却要费一番功夫， 甚至需要花费较大的代价。因此遗传算法也具有易早熟，局部搜索能力不强等缺 点，这些缺点严重影响了遗传算法的运行效率。另一方面，局部搜索算法是基于 贪婪思想利用邻域函数进行搜索的优化算法，它具有较强的局部搜索能力，但却 对整个搜索空间缺乏了解，不利于搜索最有希望的区域。 遗传算法是多学科交叉与结合的产物，已经发展成一种适合于求解大规模问 题并具有自组织、自适应等特征的算法。迄今为止，遗传算法的理论研究仍主要 针对标准遗传算法模型。高级的遗传算法由于其本身的多样性，理论方面的研究 相当分散，尚未取得引人注目的结果。同时，大部分结论都是通过计算机数值仿 真来说明的，数学上严格完整且令人信服的解释仍需努力探索。遗传算法的收敛 性研究，尤其是如何提高算法的收敛速度和鲁棒性，仍是具有重要研究价值的课 题。 在遗传算法中，种群规模和遗传算子的控制参数的选取非常困难，但它们又 是影响算法性能的关键因素，在这方面，已有一些具有指导性的实验结果。另外， 遗传算法还有过早收敛的现象，如何阻止过早收敛也是人们正在研究的问题。为 了改进算法的性能，一些混合优化策略也得到了应用和发展。 遗传算法由于其解决问题以混沌、随机和非线性为典型特征，为其它科学技 术无法解决或难以解决的复杂问题提供了新的计算模型。对于大量数据的嘈杂无 序的特征，遗传算法是有效解决此类问题的方法之一。为了提高数据挖掘的效率， 人们自然想到把遗传算法用于数据挖掘中。遗传算法应用于决策树、分类规则和 模糊规则的获取等方面的文献不断涌现。与其他分类方法相比，遗传算法具有很 强的处理嗓声、无效和不准确数据的能力。目前研究各种高性能和高可扩展性的 分类算法是数据挖掘面临的主要问题之一。 生物遗传物质的主要载体是染色体。遗传物质是由基因组成的，生物的各种 性状由其相应的基因所控制。无数个基因组成染色体，基因在染色体中所占据的 位置称作基因座。而同一基因座可能有的全部基因叫做等位基因，基因和基因座 第四章基于遗传算法的分类规则挖掘研究 决定了染色体的特征，也就决定了生物个体的性状。染色体有两种相应的表示模 式，即基因型和表现型。所谓表现型是指生物个体在环境中所表现出来的性状。 而基因型指与表现型密切相关的基因组成。同一种基因型的生物个体在不同的环 境条件下可以有不同的表现型，因此表现型是基因型与环境条件相互作用的结 果。在标准遗传算法中，染色体通常是由一维的串结构数据来表现的，串的各个 位置对应上述的基因座，而各位置上所取的值对应上述的等位基因。 生物在其繁衍过程中，逐渐适应生存环境，品质不断改良，这种生命现象称 为进化。生物的进化是以集团为单位进行的，这样的集团称为种群，也叫群体。 组成种群的单个生物称为个体。种群中个体的数目称为种群的大小，也叫种群规 模。而每个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适 应度。 4 2 遗传算法的基本思想 从遗传算法的计算模型可以看出它是一种迭代式的全局优化搜索算法，它具 有以下特点： 1 运算的是解集编码而非解集本身，可以直接对集合、队列、矩阵、图表 等结构对象进行操作。本文利用遗传算法对集合的操作，实现对规则集 合的优化。 2 搜索始于解的一个群体，是对问题解的集合而不是单个解进行搜索，从 而避免陷入局部最优，逐步逼近全局最优解，同时也使遗传算法十分易 于并行化。 3 遗传算法属于随机搜索范畴，但它使用适应度函数( 而不是使用导数或 其他辅助知识) 来搜寻那些有希望改善质量的串。这样，既有的放矢， 又不至于过于复杂。 4 数据源先要预处理、编码，使处理的数据全部是整数或实数。 遗传算法应用位串编码技术，先对问题产生初始种群，再对该种群进行适应 度评估，继而进行选择、交叉和变异等操作，采用基于适应度值比例的选择策略 在当前种群中选择个体，使用交叉和变异产生下一代种群。这样一代一代遗传下 去，直到满足希望的条件为止。遗传算法因为利用了种群的方式组织搜索，所以 基于遗传算法的关联规则挖掘研究 可同时搜索解空间内的多个区域，而且特别适合于大规模并行处理，遗传算法具 有自组织、自适应、自学习等特征，而且优胜劣汰的自然选择和简单的遗传操作 使计算不受其搜索空间限制性条件( 如可微、连续、单峰) 的约束以及不需要其它 辅助信息( 如可导) ，因此遗传算法不但能获得较高的效率，而且具有简单、易操 作和通用的特性。目前，随着计算机技术的发展，遗传算法愈来愈得到人们的重 视，并在机器学习、模式识别、图像处理、组合优化、v l s i 设计和优化控制等 领域得到了成功应用。 遗传算法本身就是一种自动的机器学习技术，当我们将机器学习的问题表示 成适当的形式后，遗传算法就能自动地进行学习，结果以某种规范格式( 比如： 规则、函数、程序等) 表示出来。采用遗传算法求解机器学习问题是遗传算法 的一个重要研究领域，迄今为止可以将有关的成果归纳为两种基本类型： ( 1 ) h o h a n d 设计的c s l 恻系统。1 9 7 8 年h o l l a n d 设计了第一个基于g a 的 机器学习系统c s l ( c o g n i t i v es y s t e m ，l e v e lo n e ) ，用以求解两个迷宫问题 ( m a z e r u n n i n g ) 。 ( 2 ) s m i t h 设计的l s - 1 叫系统。1 9 8 0 年，s m i t h 提出了另一种基于g a 的机 器学习系统l s l ( 1 e a r n i n gs y s t e m ，l e v e lo n e ) 。 4 3 遗传算法的基本流程 遗传算法并不是简单的随机比较搜索算法，它通过对染色体的适应度评估和 染色体中基因的作用，有效地利用已有的信息来指导搜索最有希望改善优化质量 的状态。标准遗传算法的流程图如图4 1 所示。 第四章基于遗传算法的分类规则挖掘研究 # 濯 图4 - 1 a 标准遗传算法流程图 图4 - 1 b 标准遗传算法流程图 基于遗传算法的关联规则挖掘研究 4 4 遗传算法关键参数与操作的设计 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的 领域和种类。通常遗传算法的设计可按以下步骤进行： 1 确定问题的编码方案，即确定出个体的基因型及遗传算法的搜索空间。 2 确定适应度函数。 3 遗传算子的设计，即确定出选择、交叉、变异等遗传算子的具体操作方 法。 4 确定算法相关运行参数的值，即确定出遗传算法的种群规模、交叉概率、 变异概率等参数。 5 确定算法的终止条件。 其中，问题的编码方案和遗传算子的设计是构造遗传算法时需要考虑的两个 主要问题，也是设计遗传算法时的两个关键步骤。 4 4 1 编码 在遗传算法中，所有表现型个体( 有效的候选解) 组成的空间称为问题的解空 间，所有基因型个体组成的空间称为问题的搜索空间。标准遗传算法不能直接对 问题的解空间进行操作，必须将解空间的解变量转换成搜索空间中由基因按一定 结构组成的染色体或个体，这一转换操作就叫做编码。编码是应用遗传算法时要 解决的首要问题，也是设计遗传算法时的一个关键步骤。编码方法对于遗传算子， 尤其是对于交叉算子的功能有很大的影响。在很多情况下，编码形式决定了交叉 算子，编码问题往住称作编码一交叉问题。 遗传算法将实际问题表示成位串空间，以群体为基础，根据适者生存的原则， 从中选择出高适应值的位串进行遗传操作，产生下一代适应性好的位串集合，从 而将整个群体不断转移到位串空间中适应值高的子集上，直到获得问题的最优 解。遗传算法在工作过程中，建立并管理着问题参数空间、位串空间( 或称为编 码空间) 、模式空间和适应值空间等四个空间及其之间的转换关系。 第四章基于遗传算法的分类规则挖掘研究 图4 2 遗传算法管理的空间以及关系 评估编码方法常采用以下3 条规范。1 1 完备一 生( c o m p l e t e n e s s ) ：解空间中的所有点都能作为搜索空间中的点表现。 2 健全性( s o u n d n e s s ) ：搜索空间中的染色体能对应所有解空间中的候选 解。 3 非冗余性( n o n r e d u n d a n c y ) ：染色体和候选解一一对应。 上述3 条评估规范是独立于问题领域的普遍准则。因此，对于某个具体的应 用领域而言，应该客观地比较和评估该问题中所用的编码方法，由此得到更好的 编码方法。但是，上述3 条评估规范缺乏具体的指导思想，不一定能有效提高遗 传算法的搜索效率。相比之下，d ej o n g ”提出了两条操作性较强的实用编码原 则( 又称为编码规则) ( 1 ) 有意义积木块编码原则：应使用能易于产生与所求问题相关的且具有低 阶、短定义长度模式的编码方案。 ( 2 ) 最小字符集编码原则：应使用能使问题得到自然表示或描述的具有最小 编码字符集的编码方案。 第一条编码原则可以理解为应使用易于生成适应度较高的个体的编码方案。 第二条编码原则说明了人们为何偏爱于使用二进制编码方案的原因。需注意的 是，上述编码原则只是一个指导性大纲，它并不适合于所有的问题。所以对于实 际应用问题，仍必须对编码方法、交叉运算方法、变异运算方法等统一考虑，以 寻求到一种对问题的描述最为方便、效率最高的编码方案。 在遗传算法中，目前常用的编码方法有：一维染色体编码、多参数映射编码、 基于遗传算法的关联规则挖掘研究 可变染色体长度编码、树结构编码、二维染色体编码、大字符集编码、序列编码、 实数编码、自适应编码、乱序编码、二倍体和显性规律编码等等。 4 4 2 适应度函数 在遗传进化过程中，适应度较高的个体遗传到下一代的概率较大，而适应度 较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应 度函数。适应度函数用于对个体进行评价，也是优化过程发展的依据。在简单问 题的优化时，通常可以直接利用目标函数变换成适应度函数。在复杂问题的优化 时，往往需要构造合适的适应度函数，使其适应g a 进行优化。将目标函数转换 成适应度函数一般要遵循以下两个基本原则： 1 优化过程中目标函数的优化方向( 如寻求目标函数的最大值或最小值) 与种群进化过程中适应度函数值增加的方向相一致。 2 适应度函数值为非负。 适应度函数评估是遗传选择操作的依据，适应度函数设计直接影响到遗传算 法的性能。由于适应度函数值度量意义下的个体差异与目标函数值度量意义下的 个体差异有所不同，因此适应度函数设计不当将难以体现个体的差异，选择操作 的作用就很难体现出来，从而造成早熟收敛等缺点。常用的改进方法有线性变换、 指数变换等，即通过某种变换改变原适应度函数之间的比例关系。此外，目前已 开发了许多基于序的选择操作，它基于目标值的好坏分配选择概率，无需设计适 应度函数，一定程度上缓解了适应度函数定义的难度。 4 4 3 遗传操作 遗传算法的基本思想是优胜劣汰，它应在选择、交叉、变异等遗传算子中得 以体现。 1 种群初始化 遗传算法中初始群体中的个体是随机产生的，但考虑到搜索的效率和质量， 一方面要求尽量使初始种群均匀地分布于整个解空间，另一方面可以采用一些简 单方法或规则快速产生其中一些解作为初始个体。常采用如下两种策略：( 1 ) 先 随机生成一定数目的个体，然后从中挑出最好的个体加入初始群体。如此往复， 一2 8 第四章基于遗传算法的分类规则挖掘研究 直到初始群体规模达到了预先确定的规模。( 2 ) 根据问题固有知识，设法把握最 优解所占空间在整个解空间中的分布范围，然后，在此分布范围内随机选择初始 个体。 2 选择算子 选择算子( 或称为复制算子) 的主要目的是为了避免基因缺失、提高全局收敛 性和计算效率。选择操作是建立在对个体的适应度进行评估的基础上。它从旧种 群中选择出适应度高的某些染色体，放入匹配集( 缓冲区) ，为染色体交叉和变异 运算产生新种群做准备。适应度越高的染色体被选择的可能性越大，其遗传基因 在下一代群体中的分布就越广，其子孙在下一代出现的数量就越多。目前常用的 方法有适应值比例选择、精英选择、排序选择、联赛选择、稳态选择等。 ( 1 ) 适应值比例选择。1 。用正比于个体适应度的概率来选择相应个体。设群 体大小为m ，个体i 的适应度为f ；，所有个体适应度之和为f ，则个体i 被选中 的概率为f i f ，适应度越高的个体被选中的概率就越大，适应度越低的个体被选 中的概率越小。通常用轮盘赌( r o u l e t t e w h e e l ) 方式实现。选择过程体现了生物 进化过程中“适者生存，优胜劣汰”的思想，并且保证优良基因遗传给下一代个 体。由于选择的随机性，这种方法的选择误差比较大，种群中适应度最差的个体 有时也可能被选中。 ( 2 ) 精英选择。当前种群中最优秀( 适应度最高) 的个体不进行交叉和变异运 算，而是直接把它们复制到下一代，以免交叉和变异运算破坏种群中的优秀个体。 这种方法可保证当前最优个体不会被交叉、变异等遗传运算所破坏，它是遗传算 法收敛性的一个重要保证条件。但是，它也容易使得某个局部最优个体不易被淘 汰反而迅速扩散，从而使得算法的局部搜索能力不强。 ( 3 ) 排序选择。对种群中个体按其适应度大小进行排序，基于这个排序按一 定的方式来分配各个个体被选中的概率，具体分配方式不限，但要求适应度越高 的个体分配的概率越大，且所有个体分配到的概率之和为1 。 ( 4 ) 联赛选择。从种群中随机选取n 个个体，将其中适应度最高的个体复制 到下一代种群中，如此重复 1 次，就可得到下一代种群的m 个个体。 ( 5 ) 稳态选择。g a 进化过程是以代为标志进行的，当前群体经过选择、交叉、 变异等遗传操作生成下一代群体。由于遗传操作的随机性，或者采用精英选择策 略，下一代群体的部分可以与上一代相同，称为两代群体是重叠的。d ej o n g 将 基于遗传算法的关联规则挖掘研究 下一代群体中生成的与上一代不同的新个体所占的比例为“代沟”或“代距” ( g e n e r a t i o ng a p ) 。代距越大说明新个体的生成比例越高，群体正在搜索新的编码 空间。与之相反，稳态选择操作中，仅有少量个体按适应值比例选择方法被选择， 通过遗传操作生成新的个体。新个体放回群体是睦，随机替代等量的旧个体，或 者替代等量的最差的旧个体。h o l l a n d 将稳态选择方法应用于分类器规则学习中， 最大程度上继承己获得的规则，实现增量学( i n c r e m e n t a ll e a r n i n g ) 。基于稳态选 择方式的g a 称为稳态g a ( s t e a d y s t a t eg a ) 。 3 交叉算子 交叉运算是遗传算法中产生新个体的主要方法，它决定了遗传算法的全局搜 索能力。遗传算法中的所谓交叉运算是指通过对两个相互配对的染色体按某种方 式交换其部分基因，从而产生两个新个体。目前常用的配对策略是随机配对，即 将种群中的m 个个体以随机方式组成m 2 对配对个体组，交叉运算在配对个体组 的两个个体之间进行。交叉算子的设计包括两个方面的内容：一是如何确定交叉 点的位置；二是如何进行部分基因交换。 交叉算子的设计一般需要满足交叉算子的评估准则，即交叉算子需保证前一 代中优秀个体的性状能在后一代的新个体中尽可能得到遗传。另外，交叉算子的 设计和编码的设计是相互联系的，需统一考虑。 交叉操作一般分为以下几个步骤： ( 1 ) 从交配池中随机取出要交配的一对个体； ( 2 ) 根据位串长度l ，对要交配的一对个体，随机选取 1 ，l _ 1 中一个或多 个的整数k 作为交叉位置； ( 3 ) 根据交叉概率p c ( o p 。1 ) 实现交叉操作，配对个体在交叉位置处，相 互交换各自的部分内容，从而形成新的一对个体。 目前常用的交叉算子有单点交叉、两点交叉、多点交叉、一致交叉等。 ( 1 ) 单点交叉( o n e p o i n tc r o s s o v e r ) 。首先在个体编码串中随机设置一个交叉 位置，然后对换交叉点后的个体编码串。譬如：配对个体组 x ，y ，其中x = 1 0 1 0 1 1 1 ， = 1 0 0 1 1 0 0 ，若交叉位置为5 ，则得到的新个体分别为互。= 1 0 1 0 1 0 0 和y 。= i 0 0 1 1 1 l 。 ( 2 ) 两点交叉( t w o p o i n tc r o s s o v e r ) 。首先在个体编码串中随机设置两个交叉 位置，然后对换两交叉点之间的个体编码串。若交叉位置为2 和6 ，配对个体组 同上，则得到的新个体分别为x 。= 1 0 0 1 1 0 1 和y + = 1 0 1 0 1 1 0 0 。 第四章基于遗传算法的分类规则挖掘研究 ( 3 ) 多点交叉( m u l t i p o i n tc r o s s o v e r ) 。多点交叉是对于选定的两个个体位串， 随机选择多个交叉点，构成交叉点集合。多点交叉算子的交叉点位置有多种方法。 对于实参数优化问题采用二进制编码，一般交叉点的数量不宜低于实参数的维 数。 ( 4 ) 一致交叉( u n i f o r m c r o s s o v e r