数据挖掘与知识发现(讲稿9遗传算法)_数据挖掘和知识发现

数据挖掘与知识发现(讲稿9遗传算法)由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据挖掘和知识发现”。

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

第九章

基于遗传算法的数据挖掘

面向属性的数据挖掘方法是基于逻辑的，神经网络挖掘方法是基于方程的，而本章要介绍的遗传算法，则是一种基于十字表的数据挖掘方法。它也是一种典型的知识发现方法。

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。在此基础上，由Goldberg在80年代对其进行了归纳总结，形成了遗传算法的基本框架。9.1 遗传算法概要

对于一个求函数最大值的优化问题（最小值类同），一般可描述为如下的数学规划模型：

maxf(X)

s.t.XR

（9-1）

RU式中，X[x1,x2,,xn]T为决策变量；f(X)为目标函数（线性或非线性；离散或连续；单峰或多峰）；U为基本空间；R为U上的一个子集。满足约束条件的解X称为可行解，集合R表示由所有满足约束条件的解组成的一个集合，叫做可行解集合。

图1 最优优问题的可行解及可行解集合传统的求最优解或近似最优解的方法主要有：枚举法、分枝定界法、1

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

启发式算法和搜索算法。随着问题种类的不同，以及问题规模的扩大，要寻找到一种能以有限的代价来解决上述最优化问题的通用方法仍是一个难题。而遗传算法正好能为此类问题提供一个有效途径和通用框架，开创了一种新的全局优化搜索算法。

遗传算法是模拟生物进化过程的计算模型，它是自然遗传学和计算机科学相互结合渗透而形成的新的计算方法。

生物的进化过程主要是通过染色体之间的交叉和变异来完成的。在遗传算法中，将n维决策向量X用n个记号Xi,i1,2,,n所组成的符号串来表示X：

XX1X2XnX[X1,X2,,Xn]T

把每一个Xi,i1,2,,n看作一个遗传基因，它的所有可能取值称为等位基因。这样，X就可看作是由n个遗传基因所组成的一个染色体（或个体）。对于每个个体，要按照一定的规则确定出其适应度。个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之适应度越小。所有染色体X就组成了问题的搜索空间。

生物的进化是以集团为主体的。与此对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。与生物一代一代的自然进化过程类似，遗传算法的运算过程也是一个反复迭代过程，第t代群体记为P(t)，经过一代遗传和进化后，得到第t1代群体，也是由多个个体组成的集合，记为P(t1)。这个群体不断地经过遗传和进化操作，并且每次都按优胜劣汰的规则将适应度较高的个体更多的遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它达到或接近于问题的最优解X*。

遗传算法中最优解的搜索过程也模仿生物的这种进化过程。使用所谓的遗传算子作用于群体P(t)中，进行下述的遗传操作，从而得到新一 2

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

代群体P(t1)。主要操作有：

 选择：根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t1)中；  交叉：将群体P(t)内的各个个体随机搭配成对，对每一对个体，以某个概率（称为交叉概率）交换它们之间的部分染色体；  变异：对群体P(t)中的每一个个体，以某一概率（称为变异概率）改变某一个或某一些基因座上的基因值为其他的等位基因。遗传算法的运算步骤为：

（1）初始化：设置进化代数计数器t0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)；

（2）个体评价：计算群体P(t)中各个个体的适应度；（3）选择运算：将选择算子作用于群体；（4）交叉运算：将交叉算子作用于群体；

（5）变异运算：将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)；

（6）终止条件判断：若tT，则tt1，转到步骤二；若tT，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。

遗传算法的执行过程如下图所示：

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

图1 遗传算法的执行过程

9.2 遗传算法的特点

与传统的优化算法：单纯形法、梯度法、动态规划法和分枝定界法相比，遗传算法是一类可用于复杂系统优化计算的鲁棒性搜索算法。其特点主要有：

 遗传算法以决策变量的编码作为运算对象。而传统的优化算法往往是直接利用决策变量的实际值本身来进行优化计算；  遗传算法直接以目标函数值作为搜索信息。而传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向；

 遗传算法同时使用多个搜索点的搜索信息。而传统的优化算法往往从解空间中的一个初始点开始最优解的迭代搜索过程；  遗传算法使用概率搜索技术。而传统的优化算法往往使用的是确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往也有可能使得搜索永远达不到最优点，因而限制了算法的应用范围。

9.3 遗传算法的应用

遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

多学科。

（1）优化函数（2）组合优化（3）生产调度问题（4）自动控制（5）机器人学（6）图像处理（7）人工生命（8）遗传编码（9）机器学习

9.4 遗传算法的构成要素及形式定义

构成遗传算法的要素主要有：染色体编码方法、个体适应度评价、遗传算子、基本遗传算法的运行参数。

（1）染色体编码方法

在实现对一个问题用遗传算法进行求解之前，必须先对问题的解空间进行编码，以便于它能够由遗传算法进行操作。最常用的编码方法是二进制编码、浮点数编码、格雷码编码、符号编码等。

如，二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号集0和1所组成的二值符号集{0，1}，它所构成的个体基因型是一个二进制编码符号串。

二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是[Umin,Umax]，若用长度为l的二进制编码符号串来表示该参数，则它总共能够产生2l种不同的编码，即为：

00000000...00000000=0 ——> Umin 00000000...00000001=1 ——> Umin1

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

.....11111111...11111111=2*2*2…2-1——>Umax 则二进制编码的编码精度为：

sUmaxUmin l21假如，对于x∈[0,1023]，若用10位长的二进制编码来表示该参数的话，则下述符号串：

X:

0 0 1 0 1 0 1 1 1 1

就可表示一个个体，它所对应的参数值为x=175。此时的编码精度s=1。

（2）适应度函数

在遗传算法中，模拟自然选择的过程主要通过评估函数和适应度函数来实现的。前者是用来评估一个染色体的优劣的绝对值，后者是用来评估一个染色体相对于整个群体的优劣的相对值的大小。

但在遗传算法中，评估函数和适应度函数的计算与应用比较相近，所以一般文献中常混为一谈。

（3）遗传算子

基本遗传算法使用下列三种遗传算子：

 选择算子：按照某种策略从父代中挑选个体进入中间群体，如使用比例选择；

 交叉算子：随机地从中间群体中抽取两个个体，并按照某种交叉策略使两个个体互相交换部分染色体码串，从而形成两个新的个体。如使用单点交叉；

 变异算子：通常按照一定的概率（一般较小），改变染色体中某些基因的值。

（4）基本遗传算法的运行参数

基本遗传算法有下述4个运行参数需要提前设定：（目前无合理的理论依据）

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

 M：群体大小：即群体中所含个体的数量，一般取20-100；  T：遗传算法的终止进化代数，一般取为100-500；  pc：交叉概率：一般取为0.4-0.99；  pm：变异概率：一般取为0.0001-0.1。基本遗传算法的形式定义为：

SGA(C,E,P0,M,,,,T)

其中，C---个体的编码方法；

E---个体适应度评价函数；

P0---初始群体；

M---群体大小；

---选择算子；

---交叉算子；

---变异算子；

T---遗优越性运算终止条件。9.5 遗传算法的数学理论

1.模式

定义：模式表示一些相似的模块，它描述了在某些位置上具有相似结构特征的个体编码串的一个子集。

不失一般性，以二进制编码为例，个体是由二值字符集V={0，1}中的元素所组成的一个编码串，而模式却是由三值字符集V{0,1,*}中的元素所组成的一个编码串，其中“*”表示通配符，它既可被当作“1”，也可被当作“0”。如，H=1***001*就是一个模式，串A=10100011与B=10110010都是与模式H相匹配的字符串，称为两者相似。

定义：模式H的第一个和最后一个常量之间的距离称为模式的定义长度，记为(H)。

定义：模式中常量的个数称为模式的阶数，记为O(H)。

如上例中，(H)6,O(H)4。再如(*****1**)1，O(*******1)1 显然，当字符串的长度固定时，模式的阶数越高，能与该模式匹配的字符串（称为样本）数就越少，因而该模式的确定性也就越高。

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

2.模式定理

在引入模式的概念之后，遗传算法的实质可看作是对模式的一种运算。对基本遗传算法而言，也就是某一模式H的各个样本经过选择运算、交叉运算、变异运算之后，得到一些新的样本和新的模式。

假设在进化过程中的第t代时，当前群体P(t)中能与模式H匹配的个体数（样本数）记为m(H,t)，下一代群体P(t1)中能与模式H匹配的个体数记为m(H,t1)。则在选择算子、交叉算子、变异算子的连续作用下，模式H的样本数m(H,t)的变化情况分析如下：（1）选择算子的作用

基本遗传算法中的选择算子使用的是比例选择算子。将当前群体中适应度的总和记为F(t)F(Ai)，在这个算子作用下，与模式H所匹配

i的各个个体Ai能够平均复制Mm(H,t1)

F(Ai)个个体到下一代群体中，即 F(t)Mf(H,t)F(t)AiHP(t)MF(Ai)F(t)AiHP(t)Mf(H,t)f(H,t)m(H,t)m(H,t)_F(t)F(t)

（9-2）

F(t)式中，f(H,t)是第t代群体中模式H所隐含个体的平均适应度；

_F(t)M是第t代群体的平均适应度。

若再假设模式H的平均适应度总是高出群体平均适应度的倍，则（9-2）式可改写为

m(H,t1)m(H,t)(1C)

（9-3）由此可见，m(H,t1)为一等比级数。其通项公式为

m(H,t)m(H,0)(1C)t

（9-4）显然，有

 若C>0，则m(H,t)呈指数级增长；

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

 若C

由此可得如下结论：在选择算子作用下，对于平均适应度高于群体平均适应度的模式，其样本数将呈指数级增长；反之，呈指数级减少。（2）交叉算子的作用

以单点交叉算子为例，见图所示的一个模式。

隐含在该模式中的样本与其他个体进行交叉操作时，根据交叉点的位置不同，有可能破坏该模式，也可能不破坏该模式而使其继续生存到下一代群体中。下面估算该模式生存概率ps的下界。

显然，当随机设置的交叉点在模式的定义长度之内时，将有可能破坏该模式；而当随机设置的交叉点在模式定义长度之外时，肯定不会破坏该模式。则由交叉概率pc发生时，模式H的生存概率的下界为

ps1pc(H)l（9-5）

这样，经过选择算子和交叉算子作用之后，模式H的样本数满足下式：

m(H,t1)m(H,t)(1C)[1pc(H)l1]

（9-6）

由式（9-6）知，在其他值固定的情况下（C>0）

 (H)越小，则m(H,t)越呈指数增长；  (H)越大，则m(H,t)越不容易呈指数增长。（3）变异算子的作用

这里，以常用的基本位变异算子为例进行研究。

若某一模式被破坏，则必然是模式描述形式中通配符“*”之处的某一基因发生了变化，其发生概率是：

1(1pm)O(H)当pm1时，有：

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

1(1pm)O(H)O(H)pm

由此可知，在变异算子作用下，模式H的生存概率大约是：

ps1O(H)pm

（9-7）显然知

 O(H)越小，模式H越易于生存；  O(H)越大，模式H越易被破坏。

综合上面的各式，并忽略一些极小项，则比例选择算子、单点交叉算子、基本位变异算子的连续作用下，群体中模式H的子代样本数为：

m(H,t1)m(H,t)f(H,t)F(t)_[1pc(H)l1O(H)pm]

（9-8）

[模式定理] 遗传算法中，在选择、交叉和变异算子的作用下，具有低价、短的定义长度，并且平均适应度高于群体平均适应度的模式将按指数级增长。

模式定理阐述了遗传算法的理论基础，说明了模式的增长规律，同时也给遗传算法的应用提供指导作用。9.6 积木块假设与遗传算法欺骗问题

1.积木块假设

具有模式定理中所述的呈指数增长的模式称为积木块或基因块。之所以称为积木块，是由于遗传算法的求解过程并不是在搜索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像搭积木一样，将它们拼接在一起，从而逐渐地构造出适应度越来越高的个体编码串。

模式定理说明了积木块的样本呈指数增长，亦即说明了用遗传算法寻找最优样本的可能性，但它并未指明遗传算法一定能够寻找到最优样本。

[积木块假设] 个体的基因块通过选择、交叉、变异等遗传算子作用，能够拼接在一起，形成适应度更高的个体编码。

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

注：积木块假设已得到完整而严密的数学证明，但大量的应用实践也已说明了其有效性。

2.遗传算法欺骗问题（GA Deceptive Problem）

应用实践表明，存在着一类用遗传算法难以求解的问题，这类称为“GA-难”的问题往往不满足积木块假设，即由基因块之间的拼接，往往会欺骗遗传算法，使其进化过程偏离最优解。

原因：各种研究结果表明，属于“GA-难”的问题一般包含有孤立的最优点，即在这个最优点周围是一些较差的点，从而使得遗传算法较难通过基因之间的相互拼接而达到这个最优点的模式。实际上，目前也尚无解决这类问题的较好方法或策略。所幸的是，现实所遇到的各种应用问题中，很少有这种奇怪的性质。9.7 基于遗传算法的数据挖掘示例

【示例】从200名脑出血和脑血栓病例中，按如下属性：“病人的既往史”、“起病方式”、“局部症状”、“病理反射”、“膝腱反射”和“病情发展”等六个方面，找出这两类病人的识别规则。其中

（1）病人的既往史

包括：高血压（有01，无00）、动脉硬化（有01，无00）；（2）起病方式

快（01）、慢（00）；（3）局部证状

偏瘫（是01，否00）

瞳孔不等大（是01，否00）

两便失禁（是01，否00）

语言障碍（是01，否00）

意识障碍（无00，深度01，轻度10）

（4）病理反射

阳（01），阴（00）

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 装 ┊ ┊ ┊ ┊ ┊ 订 ┊ ┊ ┊ ┊ ┊ 线 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

（5）膝腱反射

无（00），活跃（01），不活跃（10）

（6）病情发展

快（01），慢（00）

则可选30个病例作为训练样本，100个作为测试样本。

a)采用二进制编码方式。每个训练样本是由11个特征和1个类别组成，每个特征和类别都由2位二进制字符表示。那么，将样本编码成二进制字符串的消息就是一个由22位条件和2位结论组成的二元组。如，消息M=[***00101，01] b)假设训练集是由15个脑出血和15个脑血栓患者组成30个训练样本。本实验在对30个训练样本进行学习后，得到12条规则，学习终止于第170代。

（参见P201《数据仓库与数据挖掘》，陈文伟、黄金才编，人民邮电出版社，2004）

c)获取如下的7条主要规则：

（1）if 高血压=有∧瞳孔不等大=是∧膝腱反射=不活跃 then 脑出血（11）

（2）if 瞳孔不等大=是∧语言障碍=是 then 脑出血（12）

（3）if 高血压=有∧起病方式=快∧意识障碍=深度 then 脑出血（13）（4）if 高血压=有∧病情发展=快 then 脑出血（15）

（5）if 高血压=有∧动脉硬化=有∧起病方式= 慢 then 脑血栓（13）（6）if 动脉硬化=有∧病情发展=慢 then 脑血栓（15）（7）if 动脉硬化=有∧意识障碍=无 then 脑血栓（12）以上括号内的数值表示该规则的适应值。