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

陈晓燕

(琼州学院电子信息工程学院，海南三亚572022)

0 引言

近年来，随着计算机网络技术和数据库技术的发展，人们所拥有的信息量在急剧的增长，如何从海量的信息中深层次的发掘有价值的信息，是目前迫切解决的问题。在此情况下，一种新的数据分析技术应运而生——数据挖掘(Data Mining)技术。应用于数据挖掘的算法很多，但都有一个造成算法局部收敛的共同弱点，而遗传算法在空间搜索过程中非常独立，弥补了其它算法在理论和应用上的许多缺陷。遗传算法应用在数据挖掘中，在各类问题的求解和应用中已表现出了它独特的优势。

1 数据挖掘技术

对于数据挖掘技术，一种公认的定义是:数据挖掘技术是指从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程［1］。在很多情况下，人们并不知道数据存在哪些有价值的信息，而数据挖掘技术可以帮助人们获得决策所需的多种知识，因此，研究数据挖掘技术有着重要的意义。

应用于数据挖掘的方法有很多，常见的方法有以下几种:

(1)人工神经网络人工神经网络是典型的机器学习方法，广泛应用于预测、模式识别、优化计算等领域，也可用于数据挖掘中的聚类分析。在结构上，人工神经网络方法是模仿生物神经网络，是一种通过训练来学习的非线性预测模型，可以完成分类、聚类、特征挖掘等多种数据挖掘任务。目前，神经网络主要有三种模型:前馈式网络、反馈式网络、自组织网络。

(2)关联规则挖掘技术关联规则挖掘技术是比较成熟的数据挖掘技术，它的目的是发现数据之间的关联特性，主要应用于数据挖掘中的关联分析。

(3)决策树方法决策树方法以数据集中各字段的信息增益为依据，以信息增益最大的字段作为决策树的根结点，并依次对各个子树进行类似的操作，直到确定决策树的所有结点［2］。

(4)遗传算法遗传算法(Genetic Algorithm，GA)是模拟生物进化的自然选择和遗传机制的一种寻优算法［3］。它先将搜索结构编码为染色体，然后分别通过选择、交叉、变异三个基本遗传算子对其进行循环操作，遗传算法对于复杂的优化问题无需建模和进行复杂运算，只需要利用遗传算法的算子就能寻找到问题的最优解或满意解。研究遗传算法在数据挖掘中的应用，对于进一步分析和研究演化计算，寻求高效的数据挖掘有着重要的理论意义。

2 基于遗传算法的数据挖掘

遗传算法操作的基本对象是染色体或个体，每个染色体代表求解问题的一个可能解。在应用遗传算法时，需要确定以下要素:(1)染色体的编码方法，如何由染色体的编码体现问题的解。(2)表示个体的适应度的评价函数。适应度高的个体有更大的概率遗传到下一代群体。(3)如何产生初始群体(4)确定遗传算子，即如何进行复制，交叉，变异等遗传操作并产生下一代群体。(5)确定运行参数，包括群体规模popsize，终止进化代数MaxGen，交叉概率PC和变异概率Pm［4］。图1表示了遗传算法的过程。

2.1 遗传操作的选择、交叉和变异3个基本算子轮盘赌选择:轮盘赌选择方法类似于博彩中的轮盘赌。它先计算个体的相对适应值，这种选择策略可以如下实现:先生成一个［0，1］内的随机数 r，若 P0+P1+… +Pi1＜ r＜ P0+P1+ … +Pi，则选择个体 i，此处假设P0=0。

交叉:是指对两个相互交叉的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。它是产生新个体的主要方法。图2分别表示的是单点杂交和两点杂交。

变异:是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。

图1 标准的遗传算法

图2 单点杂交和两点杂交

2.2 编码DNA中遗传信息在一个长链上按一定的模式排列，也即进行了遗传编码。遗传编码可以看作从表现型到遗传子型的映射。在遗传算法中，将n维决策向量X=［x1，x2，…xn］T用n个记号xi(i=1，2，…，n)所组成的符号串X来表示:

把每个xi看作一个遗传基因，它的所有可能取值成为等位基因，这样，X就可以看作由n个遗传基因所组成的一个染色体。在一般情况下，染色体长度n是固定的，但是对一些问题n也可以是变化的。根据不同的情况，等位基因可以是一组整数，也可以是某一个范围内的实数，或者纯粹一个记号。最常用的编码有两个:一个是二进制编码，另一个是浮点数编码。在遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。

3 实例应用

以来海南旅游的游客基本信息为依托，建立一个数据库，构建的表如下:

表1 游客信息表

根据游客信息表中的条件，用两个基因分别代表游客的散客或跟团的游客性质;用三个基因分别表示游客经济状况的差、良、好。用三个基因分别表示团队规模的小、中、大。于是有八个基因定义游客类型，将每个基因的值用“是”和“否“来表示特定宇段的值是否存在于某个客户群中完成对染色体的二进制编码，这样可以产生一群随机生物个体，如表2所示。

表2 游客新基因组成

随之，依据这些个体的环境适应性，利用遗传算法进行迭代处理。在遗传算法中的多种算法形式，本实例采用的是一种只在局部范围内进行竞争和交叉以产生最优个体的简化形式。首先将这些游客信息放在一张二维表格中，然后按照竞争、交叉、变异、重复的步骤进行生物的遗传进化算法。

4 小结

遗传算法以其收敛速度快、计算时间短等特点，深受广大研究人员的青睐。重点研究了将遗传算法与数据挖掘相结合，应用到现实生活当中去，有着非常重要的意义。下一步还将继续研究遗传算法与数据挖掘的结合，将遗传算法的功能更加全面、深刻的体现出来。

［1］彭木根.数据仓库技术与实现.电子工业出版社，2002:104－143.

［2］钟波，肖智，李勇，等.一种基于遗传算法的数据预处理组合方法［J］.西南师范大学学报，2002，27(4):497－500.

［3］曾令明，金虎.基于遗传算法的双向关联规则挖掘.微电子学与计算机，2006(23):35－37.

［4］陈晓燕.基于量子遗传算法的无线传感器网络节点定位算法研究［D］.华中师范大学硕士学位论文，2009.