基于小生境遗传算法的关联规则挖掘研究

《基于小生境遗传算法的关联规则挖掘研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、·应用研究·徐程郑洪源基于小生境遗传算法的关联规则挖掘研究67基于小生境遗传算法的关联规则挖掘研究徐程，郑洪源(南京航空航天大学信息科学与技术学院，江苏南京210016)摘要：在对传统遗传算法的早熟收敛和后期收敛速度慢等问题分析的基础上，提出了一种改进的小生境遗传算法模型。该模型针对传统遗传算法的不足，采用小生境方法代替传统遗传算法的选择方式，重点改进了遗传算子，能够有效调整种群规模，延迟早熟收敛现象，控制后期收敛速度，从而能够挖掘到尽可能多的有效关联规则。最后，以中医药的疾病配方为例，验证了此算法的可

2、行性和有效性。关键词：数据挖掘；遗传算法；小生境；早熟收敛；关联规则中图分类号：TP301文献标识码：A文章编号：1672—1616(2008)23—0067—04随着科技的进步，作为我国经典医学的中医药是改进遗传算法搜索性能的关键[引。为了使遗传学，其应用价值开始得到越来越多人的认可。中医算法尽可能挖掘到全局最优解，本文引入小生境技药学累积了大量的组方数据，如何对这些数据进行术，同时改进SGA。合理有效的挖掘，尽可能多地发现各种疾病和医药药方之间的关系，以便指导中医进行更有效的医疗1小生境遗传算法与改

3、进组方，有着重大的现实意义。于是，用于挖掘中医在自然界中，普遍地存在“物以类聚，人以群药材组方的数据挖掘方法应运而生，其中，使用遗分”的小生境现象。生物总是倾向于与自己特征、传算法进行关联规则挖掘是一种极其有效而流行性状相似的同类生物生活在一起，一般总是与同类的数据挖掘方法。交配并繁殖后代，这种正选型交配方式在生物遗传标准遗传算法(SGA)具有智能式搜索、渐进式进化过程中具有积极的作用。但是这并不意味着优化、黑箱式结构、通用性强和并行式算法等独特与同类繁殖就一定可以产生优秀后代，往往差别很的优势。尽管S

4、GA有以上优点，但也存在一些缺大的两个祖先也经常会繁殖产生优秀后代_4j。受陷和不足：(1)采用按适应值比例复制的随机选择此自然现象的启发，为了挖掘到更多的有效规则，策略，导致搜索过程徘徊不前，产生早熟收敛现象；把小生境引入传统遗传算法里。(2)在搜索后期，绝大多数个体的适应值与群体平小生境思想(NGA)是将符合最小适应度的每均适应值接近，难以使种群进化过程向前推进；(3)代个体划分为若干种群，再将种群的个体通过交SGA除了存在不能保证每次都能获得全局最优解叉、变异产生新一代个体群，通过比较最终搜索到的

5、问题外，还存在只能获得一部分次优解的问全局最优解。题[。1．1遗传算子的改进通过对SGA缺点的分析可以看出，足够的个对SGA的改进主要集中在如下方面：适应度体多样性有利于改善全局收敛的可靠性，强的选择函数、选择算子和变异算子。压和适当降低交叉操作的不确定度可加快局部收1．1．1适应度函数的改进敛速度。但维持种群中个体的多样性和增加选择关联规则挖掘的任务就是要发现能够反映记压是互为矛盾的两个因素，强的选择压易造成个体录属性之间的关联或者是关系，这些规则都具有一多样性的损失l。因此，在提高选择压的同时，确定

6、的支持度，首先根据支持度选择出符合条件的关保维持种群中个体的多样性；在交叉操作中引入某联规则。SGA在使用赌轮选择算法时是按支持度种引导进化的指导信息，使交叉操作不但能不断开的比例选择符合条件的个体，故直接用支持度来定辟新的搜索空间，而且能保证子代个体的高质量，义支持度，本文不是按比例选择，而是先把所有个收稿日期：2008—1106作者简介：徐程(1983一)，男，山东临沂人，南京航空航天大学硕士研究生，主要研究方向为知识工程、人机交互技术等。2008年12月中国制造业信息化第37卷第23期体分成n个小

7、生境进行演化，最后阶段才淘汰个其中引入指导信号，即设置小生境代数T，控制种体，因此定义适应度函数为：群的后期收敛速度，确保对算法进程能进行有效的Fitness(t)=S—S控制。改进了小生境演化算法的策略，以弥补采用式中：S为经过遗传操作所形成的一条新规则的单一方法进行小生境组合导致后代优良个体缺失支持度；S为用户给定的支持度的阈值。的不足，并最大限度地挖掘到有效规则。同时为了1．1．2选择算子的改进克服群体收敛到单个最优值和进化中丢失有用规一般简单遗传算法选用的都是赌轮选择算法，则的缺点，并确保群体规

8、模不被破坏，提高遗传算然而赌轮算法容易早熟，并容易使遗传算法失去进法在关联规则挖掘应用中的性能，引入整理算子。化能力，此外对于关联规则，两个适应度高的个体，整理算子完成以下操作：在得到新的种群之后，检未必繁殖出一个高适应度的个体，相反两个适应度查种群中的个体，删除其中重复的个体，随机产生不高的个体可能繁殖出一个适应度高的个体。本新的个体补充到其中，在进化的每一代动态地更新文采用小生境组合，交替选择父本和母本，可以有群体，把优秀群体插入到下一