遗传算法在数据挖掘中的研究与应用

1、遗传算法在数据挖掘中的研究与应用 学院： 计算机学院 班级： 计研-14 学号： 2deeeeeeeeeee 姓名： 笑嘻嘻 2015年1月遗传算法在数据挖掘中的研究与应用摘 要 遗传算法(genectialgoritlllnn,GA)是一种模拟生物进化过程的自适应全局优化算法，是解决现代非线性优化问题的一种重要方法。对于大量数据的嘈杂无序的特征，遗传算法是有效解决此类问题的方法之一。它模拟自然选择和生物遗传机制，利用遗传算子产生后代,通过群体的迭代，使个体的适应性不断提高，最终群体中适应值最高的个体即是优化问题的最优或次优解。数据挖掘(DataMining,DM)就是从大量的、不完全的、有噪

2、声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。它借助了多年来数理统计技术和人工智能以及知识工程等领域的研究成果构建自己的理论体系,是一个交叉学科领域,集成了数据库、人工智能、数理统计、可视化、并行计算等技术。关联规则作为数据挖掘领域的一个重要研究分支，针对关联规则挖掘中经典算法-Aprior算法的局限性,在划分技术的基础上提出了一种基于遗传算法的关联规则挖掘模型。分类是数据挖掘中最重要的方法之一，决策树作为发现分类模型的常用技术现已被广泛研究并取得了很大的进展。然而，在决策树的构造过程中采用贪心算法，造成了决策树容易过分拟合、规模过大、产生的

3、规则长度过长等缺点。针对这些缺陷，提出了一种基于遗传算法与关联规则算法的混合分类挖掘方法。本论文主要围绕着遗传算法应用于数据挖掘研究展开,基本上分为四部分：(1)对KDD(Knowledge Discovery in Database)技术进行了总体上的概述，包括KDD的含义、一般过程、主要方法和技术、研究的现状及存在的问题等，为在这一领域进行更为深入的研究打下初步基础。在此基础之上对发现分类模型的各种技术以及关联规则挖掘算法进行了较为全面的研究。(2)对遗传算法的编码方法、适应度函数、遗传操作算子、参数的选择作了全面且深入的研究。(3)对提出的基于遗传算法的关联规则挖掘方法进行了全面的描述。

4、(4)对提出的基于遗传算法与关联规则算法相结合的混合分类方法进行了全面的分析。关键词 遗传算法；数据挖掘；分类；关联规则Research and Application on Data Mining based on Genetic AlgorithmAbstract Genetic Algorithm is a kind of global optimization algorithm which simulates the process of biological evolution, its a important method to settle modern nonlinear o

5、ptimization problems. For the chaos of the vest data, Genetic Algorithm is one of the effective methods that can solve this kind of question. It simulates natural selection and biological genetic mechanism and generates the offspring by genetic operators. Through the iterativeness of population, the

6、 fitnesses of the individuals is improved and finally the individual with the highest fitness just is the optimal solution or suboptimal solution of the optimization problem.Data Mining(DM) is a process that pick previously unknown and potentially useful information and technology from large volumes

7、 of incomplete, fuzzy and stochastic data with noise. It made use research achievements of many years in the areas of statistical and mathematical techniques, artificial intelligence and knowledge engineering etc. to form its theory system. It is a Cross-Discipline Field which integrated the technol

8、ogy such as database, artificial intelligence, statistical and mathematical techniques, Description and Visualization, Parallel Computing etc.Associate rule is an important theme in the data mining. In view of the Apriori algorithms limitation,an improved Apriori algorithm based on partition technol

9、ogy is proposed in this paper. Classification is one of the important themes in Data mining. Decision Tree is a method of Data mining that is used widely to mining classification model. It has studied widely and made a great progress. However, Decision Tree always leads to be over-fitting, to have l

10、arge scales and induce longer classification rules if it adopts greedy algorithm. According to these shortcomings, an approach to data mining which integrates genetic algorithm and association rule algorithm is proposed in this paper. There are four main points in this thesis as follows:1.The concep

11、tion in data mining, basic process, main technology and the development of the Situation are described in this theme. And the same time, some useful classification algorithms are discussed such as decision tree, genetic algorithm, and neural networks.2.Biological principle, mathematic principle, sea

12、rch principle and the feature are completely described in the paper.3.The approach to association which integrates genetic algorithm is described in the paper.4.The approach to classification which integrates genetic algorithm and association rule algorithm is described in the paper.Keywords Genetic

13、 algorithm; Data mining; Classification; Association rules1. 数据挖掘1.1数据挖掘的产生和研究目标近年来随着数据库技术和计算机网络的广泛应用，加上使用先进的自动数据生成和采集工具，人们所拥有的数据量急剧增大。激增的数据背后隐藏着许多重要的信息，如何从大量的数据中提取并找到有用的信息以指导决策，是迫切需要解决的问题。在这种情况下，数据挖掘1新型的数据分析技术于 1995 年诞生了。目前，数据挖掘的研究重点转向多种发现策略和技术的集成，以及多种学科之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成为当前计算机科学界

14、的一大热点。数据挖掘是一门新兴的数据处理技术,涉及数据库技术、人工智能、机器学习、神经网络等学科。遗传算法作为一种模拟自然进化思想的启发式全局寻优算法，是进化计算的杰出代表，也是机器学习的重要方法。将遗传算法引入数据挖掘领域越来越引起学术界的重视，国外己经有不少成功的范例。国内主要集中在遗传算法理论与数据挖掘领域的探讨上,建立了一些基本的数据挖掘问题计算模型,如在分类和关联规则挖掘过程中采用遗传计算技术。随着数据挖掘应用领域的不断拓展，将遗传算法引入数据挖掘中，为数据挖掘提供了一个崭新的思考模式,指出了一个新的研究方向。本文的研究工作主要源于上述背景，将遗传算法应用于数据挖掘中关联规则的提取，

15、并结合教师测评系统，将数据挖掘技术引入教育领域，实现了基于遗传算法的关联规则数据挖掘的应用实现。本文的主要研究内容有：l 数据挖掘技术的分析研究 在数据挖掘相关概念基础上，对数据挖掘的目的与功能、分析方法、挖掘过程与工具、挖掘方法与技术做了详细的归纳和总结。同时，对数据挖掘的发展和应用状况也进行了客观的分析。 l 关联规则的分析研究 全面研究了关联规则的相关知识，对其核心算法Apriori算法进行了分析；在对关联规则的价值衡量标准进行研究的基础上，重点探讨了本文应用实例中使用到的有关兴趣度的内容。 l 遗传算法的分析研究 介绍了遗传算法的基本概念和基本思想，分析了遗传算法中染色体编码方案、适应

16、度函数构造及遗传算子的设计和改进方法，同时对遗传算法的应用流程和算法也做了分析研究。 l 基于遗传算法的关联规则挖掘的应用研究 通过对数据挖掘、关联规则和遗传算法的分析研究，提出一种基于遗传算法的关联规则数据挖掘模型，并将其应用于教育领域中的教师测评系统，给出了该应用的实现技术和算法。通过实验证明了算法的有效性和可行性，实验效果良好。1.2数据挖掘基本概念随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的数据量急剧增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些信息从数据库中抽取出来，将创造很多潜在的利润，而这种从海量数据库中挖掘信息的技术，就称之为数据挖掘(Data

17、Mining-DM)。数据挖掘是从一个新的角度将数据库技术、机器学习、统计学等领域结合起来，从更深层次发掘存在于数据内部的、有效的、新颖的、具有潜在效应的乃至最终可理解的模式2。数据挖掘能预测未来趋势和行为，使商务活动具有前瞻性，有助于企业做出基于知识驱动的决策。数据挖掘所提供的自动预期分析，已经远远超出了由典型的决策支持系统工具对过去实践所做的回顾性分析范围。数据挖掘可以解决传统上需花费很多时间解决的商务问题，它能搜索整个数据库并查找隐藏的模式，找出那些专家可能错过的预测信息3。理解数据挖掘需要从技术和应用两个层面进行。从技术层面上看，数据挖掘是利用多种分析工具从海量数据中发现模型和数据间关

18、系的过程，其基于机器学习、统计学、神经网络、数据库系统和信息科学等技术。从应用层面上看，数据挖掘是一个决策过程，基于多种技术，分析企业商务数据，为企业做出正确的市场预测等提供支持。数据挖掘的一般过程如图1-1所示：图 1-1 数据挖掘的一般过程1.3 数据挖掘中的关联规则 关联规则的提取是数据挖掘技术研究的一个重要课题。由于符合人类认知世界的思维模式，关联规则的提取广泛应用于商业、保险等行业。在实际的大型数据库（如超级市场的交易事务数据库）中发现了如“购买物品A和B的客户中85同时也购买C和D”这样的规则，对于分类设计、商店布局、市场分析等方面都大有帮助。目前关联规则的挖掘研究大都以这种商用事

19、务数据库为主要对象，其属性域局限于布尔类型，因而也称为布尔相关问题。而普通关系数据库中属性类型较为丰富，它可以包含数量属性（如年龄、工资等）和类别属性（如性别、教育程度等），布尔类型可以看成是类别属性的一个特例。如何发现普通数据库中各属性之间的关联，也称为数量相关问题，具有更为普遍的意义，目前该方面的研究工作开始增多。本文的关联规则挖掘就是关于数值关联规则的挖掘。1.4数据挖掘的分析方法9数据挖掘的目的是发现有意义的知识以便为决策支持等具体业务提供帮助。数据挖掘的分析方法一般包括以下几种： （1）关联分析 关联分析的目的是发现数据集中所隐含的若干项目之间的相互关系10,11。比如，超市记录了每

20、次交易的商品清单，通过对顾客购物行为进行关联分析，从而可以获取各个商品在销售上的关联程度。关联分析往往以关联规则的形式表达，并以支持度、置信度等参数来描述关联规则。 （2）数据分类 数据分类是发现数据集中各个对象的一般特征，并按照不同的分类模型将这些对象划分成不同的类12-14。对数据进行分类时，假定数据集中的每个对象事先已知属于某一个类，而分类则是生成这些类的描述。因此，分类分析需要事先对每个对象加上标记以区分出所属的类。数据分类方法指的是或者导出区分所有类的规则集合，或者仅仅获得某一个类区别于其它类的区分规则集合，这两者的侧重点是不同的。 （3）聚类分析 聚类是一个过程，它将数据集中的对象

21、进行分组，生成相似对象的类15,16。聚类分析是无导师的学习过程。聚类分析目的是将大量数据的对象集合分成若干个有意义的类，使得每个类的内部对象具有较高的相似程度，而不同类的对象之间具有较小的相似程度。 （4）序列模式分析 序列模式分析侧重于分析数据之间的前后因果关系17,18。比如对于超市，序列模式分析可用于发现顾客购物模式的次序，如先购买商品X，再购买商品Y。对于股票市场，序列模式分析可用于发现股票价格变化的先后关系，如股票A上涨一定幅度后，股票B也将上涨一定幅度。可见，序列模式分析与关联分析不同，关联分析仅考虑数据间的联系，而并不关心先后顺序。在实际的决策支持等具体业务过程中，则往往需要综

22、合应用上面的各种数据挖掘的分析方法，以便获得更好的效果。2. 遗传算法2.1遗传算法的基本思想遗传算法的基本思想可归为两点：第一，将物种进化的理论用于求问题的解，物种的进化又可分为遗传和变异两个方面；第二，只有最适合环境的物种才能保留下来，因而需经反复求解后才可以得到最佳的解。遗传算法按照一定的规则生成经过基因编码的初始群体，然后从这些代表问题的可能潜在解的初始群体出发，挑选适应度强的个体进行交叉（或称交配、交换）和变异，以期发现适应度更佳的个体，如此一代代地演化，得到一个最优个体，将其解码，该最佳个体编码则对应问题的最优解或近似最优解。遗传算法主要由六个部分组成:染色体编码、初始群体产生方法

23、、个体适应度评价、遗传操作(选择算子，交叉算子，变异算子)、算法终止条件以及遗传参数的设置。2.2遗传算法的构成要素（1）染色体编码最常用的是二进制编码，即将问题域参数空间中的一个点映射到个体的染色体上，二进制每一位即为染色体上的一个基因，字母表为0，1。对于离散型变量直接编码，对于连续型变量先离散化后再编码。（2）适应度函数在遗传算法的讨论中，一般希望适应度越大越好，且要求适应度非负，因此要对适应度函数进行一些变换，以适应上述的要求。（3）遗传算子包括选择算子、交叉算子、变异算子。选择算子最常用的是基于适应度比例的选择，最常用的是赌轮选择。选择是从种群中选择生命力强的染色体产生新种群的过程。

24、选择的依据是每个染色体的适应度大小。适应度越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。它在很大程度上决定着遗传算法的收敛速度和收敛效果。常用的适应度计算方法有以下两种： 按比例的适应度计算（proportional fitness assignment）；基于排序的适应度计算（rank-based fitness assignment）； 接着，在适应度计算之后是实际的选择，按照适应度进行父代个体的选择。可以挑选以下的算法： 赌轮盘选择（roulette wheel selection）；随机遍历抽样（stochastic universal sampling）；局部选择（loc

25、al selection）；截断选择（truncation selection）；锦标赛选择（tournament selection）。交叉算子又称重组(recombination) 、配对(breeding)算子。当许多染色体相同或后代的染色体与上一代没有多大差别时，就利用交叉算子来产生新一代染色体，所以交叉算子可以产生新的个体。染色体交叉分两个步骤进行：首先，在新复制的群体中随机选取两个染色体，每个染色体由多个位(基因)组成；然后，沿着这两个染色体的基因随机取一个位置，二者互换从该位置起至末尾的部分基因。 根据交叉点的数目不同，可以将交叉分为单点交叉和两点交叉。在单点交叉中，交叉点之后的

26、所有字符全部参加交换。在两点交叉中，只有两个交叉点之间的字符才参加交换。进一步推广，也可以进行多点交叉。在这里，我们介绍一下单点交叉的作用过程： 首先产生一个在1到L-1之间的整型随机数i；然后配对的两个串相互交换从i+1到L的对应位段。假设从交配池中选择编号为1和2的两个串为配对串，且交叉点选在2，则交叉算子作用的结果为: 遗传算法的有效性主要来自选择和交叉操作，尤其是交叉操作，在遗传算法中起着核心作用。变异就是以很小的概率，随机改变字符串某个位置上的值。在二进制编码中，就是将0变成1，将1变成0，它本身是一种随机搜索，但与选择、交叉算子结合在一起，在保证遗传算法的有效性和局部随机搜索能力的

27、同时，使遗传算法保持种群的多样性，以防止出现未成熟而过早收敛。2.3设置控制参数遗传算法是一种弱方法，对所要求解决的问题数学要求不是太高，但它却要求人们在使用该方法时，事先确定若干个控制参数，这些参数的选择对遗传算法的性能和效率的影响都比较大。其中，主要的控制参数有以下几种：（1）编码串的长度 L: 编码长度 L 与所用的编码方法有关。本文使用实数数组的编码方案，编码长度等于数据库中我们希望得到的相关字段的个数。根据上述分析，本例中编码长度为 10。 （2）群体规模：如果群体规模大，可提供大量模式，使遗传算法进行启发式搜索，防止早熟发生，但会降低效率；如果群体规模小，可提高速度，但却会降低效率

28、。一般取值范围在20100之间。（3）遗传算法的终止进化代数：一般取100500。 （4）交叉率（Pc）：在每次迭代中，要求有PcN个个体进行交叉操作。它影响着交叉算子的使用频率，交叉率越高，可以越快地收敛到全局最优解，因此一般选择较大的交叉率。一般取值范围在0.40.9之间。 （5）变异率（Pm）：在每次迭代中，群体中每个个体的任一位置的基因按变异率随机改变，大约发生Pm次变异操作。变异率控制着变异算子的使用频率，它的大小将影响群体的多样性及成熟前的收敛性能。变异率的选取一般受种群大小、染色体长度等因素影响，通常选取很小的值。2.4遗传算法的框架算法过程：(1)随机产生一个由确定长度的特征串

29、组成的初始化群体。(2)对串群体迭代进行下面的（i）和（ii），知道满足停止准则：（i）计算群体中每个个体的适应值；（ii）应用选择、交叉、变异算子产生下一代群体。(3)把在任一代中出现的最好个体串指定为遗传算法的执行结果，这个结果可以表示问题的一个解（或近似解）。图2-1 遗传算法的过程3. 遗传算法与数据挖掘遗传算法是数据挖掘的主要算法之一。遗传算法作为一种有效的全面并行优化搜索工具,早被众多应用领域所接受,在数据挖掘方面的应用也得到了极高的重视。遗传算法应用于决策树、分类器、模糊规则获取等方面的文献不断涌现，是数据挖掘领域的一个重要研究课题4。 遗传算法以其解决问题的混沌、随机和非线性为

30、典型特征，它为其它科学技术无法解决或难以解决的复杂问题提供了新的计算模型。对于数据嘈杂无序的特征，遗传算法是有效解决此类问题的方法之一5。许多知识发现的问题可以看成是搜索问题，数据库可以看作是搜索空间，发现算法可以看作是搜索策略，而遗传算法是模拟自然进化的全局搜索算法。应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化，直到数据库能够被该组规则覆盖，从而挖掘出隐含在数据库中的规则。遗传算法避免了搜索过程中的局部最优解，用在规则发现方面有希望发现真正有用的规则。4. 基于遗传算法的数据挖掘4.1利用遗传算法进行关联规则挖掘基于遗传算法的方法是运用遗传算法的自适应寻优及智能搜索技术，获取

31、与客观事实最相容的问题解，即使用遗传算法进行了关联规则的挖掘38。 目前，广泛使用的关联规则挖掘算法是Aprior算法或其改进算法。这些算法的基本思想是将关联规则的挖掘分解为两步：首先找到所有支持度大于用户最小支持度的项集，这些项集称为频集；然后从找到的频集中构造其可信度大于用户最小可信度的关联规则。算法思想的核心问题是找到频集，这个过程其实是一个全局搜索的过程，而遗传算法就是一种全局优化算法，它可以有效地避免搜索过程的局部最优解。因此，将遗传算法用于关联规则的发现和提取方面能够找到有价值的规则。例如，Sunil已经成功地开发了一个基于遗传算法的知识发现工具，结果表明遗传算法是进行知识发现的有

32、效方法之一。4.2 规则的提取与评价 根据适应度函数和遗传算子选择出的规则所表示出的是所有具有关联的属性，但是无法分辨出规则是如何关联的。比如，挖掘出0152003这样一条规则，我们只能知道 1523 这几个属性是关联的，但究竟是如何关联的，可能是 15=23，也可能是 152=3，还可能是 23=15 等等。这一条规则中共包含了 24 条关联规则，但未必每一条都符合可信度的要求，并且都是用户感兴趣的规则。所以，必须对所挖掘出来的规则进行提取，找出符合要求和用户感兴趣的关联规则。本文的提取标准是：满足用户给定的可信度和兴趣度要求的规则才输出，否则舍去。 规则提取算法步骤如下： （1）从侯选集中

33、取出一条侯选规则； （2）计算该规则的可信度 C和兴趣度 I； （3）if C C then 计算该规则的兴趣度 I； if II then 输出该规则； 转到（4）； else if I- I then 输出该规则的反面规则； 转到（4）； else 转到（4）； （4）如果侯选集为空，则结束提取，否则转到（1）。5. 应用实例分析5.1实例中变量设计通过采用一所大学的学生信息的数据集对基于AGA算法的挖掘结果和基于简单遗传算法的挖掘性能进行了测试。模型系统中的变量如表5-1所示:其中特征属性Depart一code的取值域为jsjkx、jsjtx、zdh、xxaq,分别代表计算机科学与技术专

34、业、计算机通讯专业、自动化专业、信息安全专业;特征属性Gender的取值域为male、female;特征属性Mtermrate的取值域为A、B、C、D;特征属性Coursetype的取值域为required、。ptionnal;特征属性coursedif经过离散化处理后的取值域为easy、midd、diff、vdiff;特征属性flunkratio经过离散化处理后的取值域为no、low、high、vhigh;类别属性的取值范围为vgood、good、paSS、faiz;5.2关联规则挖掘结果取群体初始规模为100,适应度函数:F(r)= a*S(r)+b*A(r)+c*C(r),其中a=b=c

35、=l。对1000个数据记录实施AGA算法,挖掘结果如表所示。表5-2中每条规则后赋有相应的适应度值、支持度、置信度和覆盖度。5.3与简单遗传算法(SGA)的性能比较简单遗传算法(SGA)采用赌轮方式选择交配组，即根据个体的适应度与平均适应度的比例来确定该个体的复制比例。通常SGA算法中的交叉操作,是随机取两个染色体进行单点交叉操作。在SGA算法中适应函数为:F(r)=aS(r)+bA(r)+cC(r),其中:r为规则变量;a,b,c为常数且0a,b,c1;S(r)为规则支持度;A(r)为规则的可信度;C(r)为规则的覆盖度。a,b,c的值由用户根据需要调整,使进化沿着用户期望的方向进。SGA中

36、参数设置如下表5-3所示：在遗传代数100/200/300/400/500的情况,对提出的AGA算法与传统的简单遗传算法在平均出错率方面进行了对比,实验结果如图5-3示:图5-3 AGA性能测试图由图5-3可以看出,由于AGA算法是在Apriori算法的基础上进行的,在遗传代数较小的情况下,出错率要比简单遗传算法小得多,随着遗传代数的增大,平均出错次数也会线性减少,但减少率明显下降。如图5-3中遗传代数为50,100时,执行AGA算法的出错率比执行一般遗传算法所产生的出错次数要小得多。当遗传代数较大时,基于Apriori算法的初始化结果对搜索的加速作用会变得越来越小。当遗传代数大到一定程度时,

37、基于Apriori初始化结果相当于一组随机的规则,AGA算法转变成简单遗传算法。由图5-3可以看出随着遗传代数的增加,执行AGA算法所产生的平均出错次数越来越接近执行简单遗传算法,这说明AGA算法适用于遗传代数较小的情况。但由于一般情况下遗传代数比较少,因此该算法具有实用性。6. 总结本文讲述的是数据挖掘中关联规则的挖掘。针对于传统关联规则的数据挖掘算法中只考虑支持度和置信度所存在的问题，将基于差异的兴趣度引入到关联规则的提取和评价中，过滤掉一些常规的、实用价值不是很高的规则，真正挖掘出用户感兴趣的、实用价值高的规则。目前，兴趣度的研究是数据挖掘中关联规则挖掘的一个重要方向。 本文采用遗传算法

38、进行数据挖掘中关联规则的挖掘。文中详细讨论了遗传算法在关联规则提取方面的应用，针对于事务型数据库的特点，提出了使用实数数组的编码方法，并在此基础上，讨论了适应度函数的构造，对选择、交叉和变异算子进行了改进，最后通过一个高职学院外聘教师基本信息与测评结果关联规则挖掘的实例给出了算法的具体实现，不仅验证了算法的有效性和可行性，而且对数据挖掘技术在教育领域的应用进行了初步的尝试。参考文献1朱明，数据挖掘M，中国科技大学出版社2002 2林杰斌，刘明德，陈湘，数据挖掘与OLAP理论与实务M，清华大学出版社2003 3钟晓，马少平，张钹等，数据挖掘综述，模式识别与人工智能，2001，14(1)：4855 4许国艳，史宇清，遗传算法在关联规则挖掘中的应用，计算机工程，2002，28（7）：122124 5 D.E Goldberg，Genetic Algorithms and Walsh Functions：Part ，Deception and its Analysis，Complex Systems 1989 vol(3)：153171 6J.Han，J.pei，ect. Frequent pattern projected sequential pattern miningIn Proc