人工智能课件：第16讲-总结.pptx

1、AI课程总结周雄辉第一章 人工智能概述主要内容 人工智能概念 人工智能的发展历史及学派 人工智能的应用领域第二章 确定性知识系统的表示与推理主要内容 谓词逻辑表示法 产生式系统的推理 语义网络表示法 自然演绎推理6谓词逻辑表示的经典例子谓词逻辑表示的经典例子机器人移盒子机器人移盒子 (1/5)abc例例 机器人移盒子机器人移盒子解：解：分别定义描述状态和动作的谓词分别定义描述状态和动作的谓词描述状态的谓词：描述状态的谓词： TABLE( x)：x是桌子是桌子 EMPTY( y )：y手中是空的手中是空的 AT( y, z )：y在在z处处 HOLDS( y, w )：y拿着拿着w ON(w,

2、x)：w在在x桌面上桌面上变元的个体域：变元的个体域： x的个体域是的个体域是a, b y的个体域是的个体域是robot z的个体域是的个体域是a, b, c w的个体域是的个体域是box7问题的初始状态：问题的初始状态： AT( robot, c ) EMPTY( robot ) ON( box, a ) TABLE( a ) TABLE( b ) 问题的目标状态：问题的目标状态： AT( robot, c ) EMPTY( robot ) ON( box, b ) TABLE( a ) TABLE( b ) 机器人行动的目标是把问题的初始状态转换为目标状态，而要实现问题状机器人行动的目标是

3、把问题的初始状态转换为目标状态，而要实现问题状态的转换需要完成一系列的操作。态的转换需要完成一系列的操作。描述操作的谓词描述操作的谓词 条件部分：条件部分：用来说明执行该操作必须具备的先决条件，用谓词公式来表示。用来说明执行该操作必须具备的先决条件，用谓词公式来表示。 动作部分：动作部分：给出了该操作对问题状态的改变情况，通过在执行该操作前的给出了该操作对问题状态的改变情况，通过在执行该操作前的问题状态中删去和增加相应的谓词来实现。问题状态中删去和增加相应的谓词来实现。 这些操作包括：这些操作包括： Goto( x, y )：从：从x处走到处走到y处。处。 Pickup( x )：在：在x处拿

4、起盒子。处拿起盒子。 Setdown( y )：在：在x处放下盒子。处放下盒子。谓词逻辑谓词逻辑表示的经典例子表示的经典例子机器人移盒子机器人移盒子 (2/5)8各操作的条件和动作：各操作的条件和动作： Goto( x，y ) 条件：条件：AT( robot，x) 动作：删除表：动作：删除表：AT( robot，x ) 添加表：添加表：AT( robot，y ) Pickup( x ) 条件：条件：ON( box，x )，TABLE( x )，AT( robot，x )，EMPTY( robot ) 动作：删除表：动作：删除表：EMPTY( robot )，ON( box，x ) 添加表：添加

5、表：HOLDS( robot，box ) Setdown( x ) 条件：条件：AT( robot，x )，TABLE( x )，HOLDS( robot，box ) 动作：删除表：动作：删除表：HOLDS( robot，box ) 添加表：添加表：EMPTY( robot )，ON( box，x )各操作的执行方法：各操作的执行方法： 机器人每执行一操作前，都要检查该操作的先决条件是否可以满足。如果机器人每执行一操作前，都要检查该操作的先决条件是否可以满足。如果满足，就执行相应的操作；否则再检查下一个操作。满足，就执行相应的操作；否则再检查下一个操作。谓词逻辑谓词逻辑表示的经典例子表示的经典

6、例子机器人移盒子机器人移盒子 (3/5)9这个机器人行动规划问题的求解过程如下：这个机器人行动规划问题的求解过程如下： 状态状态1(初始状态初始状态) AT( robot, c ) 开始开始 EMPTY( robot ) = ON( box, a ) TABLE( a ) TABLE( b ) 状态状态2 AT( robot, a ) Goto( c, a) EMPTY( robot ) = ON( box, a ) TABLE( a ) TABLE( b ) 状态状态3 AT( robot, a ) Pickup( a ) HOLDS( robot, box ) = TABLE( a ) T

7、ABLE( b ) 谓词逻辑谓词逻辑表示的经典例子表示的经典例子机器人移盒子机器人移盒子 (4/5)10 状态状态4 AT( robot, b ) Goto( a, b ) HOLDS( robot, box ) = TABLE( a ) TABLE( b ) 状态状态5 AT( robot, b) Setdown( b ) EMPTY( robot ) = ON( box, b) TABLE( a ) TABLE( b ) 状态状态6(目标状态目标状态) AT( robot, c ) Goto( b, c ) EMPTY( robot ) = ON( box, b ) TABLE( a )

8、TABLE( b )谓词逻辑谓词逻辑表示的经典例子表示的经典例子机器人移盒子机器人移盒子 (5/5)11产生式系统简例产生式系统简例基于规则的动物识别系统基于规则的动物识别系统(1/4) 例例 一一个用于动物识别的产生式系统个用于动物识别的产生式系统 该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这该系统可以识别老虎、金钱豹、斑马、长颈鹿、企鹅、信天翁这6种动物。种动物。其规则库包含如下其规则库包含如下15条规则：条规则： r1 IF 动物有毛发动物有毛发 THEN 动物是哺乳动物动物是哺乳动物 r2 IF 动物有奶动物有奶 THEN 动物是哺乳动物动物是哺乳动物 r3 IF 动物有羽

9、毛动物有羽毛 THEN 动物是鸟动物是鸟 r4 IF 动物会飞动物会飞 AND 动物会下蛋动物会下蛋 THEN 动物是鸟动物是鸟 r5 IF 动物吃肉动物吃肉 THEN 动物是食肉动物动物是食肉动物 r6 IF 动物有犬齿动物有犬齿 AND 动物有爪动物有爪 AND 该物眼盯前方该物眼盯前方 THEN 动物是食肉动物动物是食肉动物 r7 IF 动物是哺乳动物动物是哺乳动物 AND 动物有蹄动物有蹄 THEN 动物是有蹄类动物动物是有蹄类动物 r8 IF 动物是哺乳动物动物是哺乳动物 AND 动物是嚼反刍动物动物是嚼反刍动物 THEN 动物是有蹄类动物动物是有蹄类动物 r9 IF 动物是哺乳动物

10、动物是哺乳动物 AND 动物是食肉动物动物是食肉动物 AND 动物是黄褐色动物是黄褐色 AND 动物身上有暗斑点动物身上有暗斑点 THEN 动物是金钱豹动物是金钱豹12产生式系统简例产生式系统简例基于规则的动物识别系统基于规则的动物识别系统(2/4)r10 IF 动物是哺乳动物动物是哺乳动物 AND 动物是食肉动物动物是食肉动物 AND 动物是黄褐色动物是黄褐色 AND 动物身上有黑色条纹动物身上有黑色条纹 THEN 动物是虎动物是虎r11 IF 动物是有蹄类动物动物是有蹄类动物 AND 动物有长脖子动物有长脖子 AND 动物有长腿动物有长腿 AND 动物身上有暗斑点动物身上有暗斑点 THEN

11、 动物是长颈鹿动物是长颈鹿r12 IF 动物是有蹄类动物动物是有蹄类动物 AND 动物身上有黑色条纹动物身上有黑色条纹 THEN 动物是斑马动物是斑马r13 IF 动物是鸟动物是鸟 AND 动物有长脖子动物有长脖子 AND 动物有长腿动物有长腿 AND 动物不会飞动物不会飞 AND 动物有黑白二色动物有黑白二色 THEN 动物是鸵鸟动物是鸵鸟r14 IF 动物是鸟动物是鸟 AND 动物会游泳动物会游泳 AND 动物不会飞动物不会飞 AND 动物有黑白二色动物有黑白二色 THEN 动物是企鹅动物是企鹅r15 IF 动物是鸟动物是鸟 AND 动物善飞动物善飞 THEN 动物是信天翁动物是信天翁 其

12、中，其中，ri(i=1,2,.,15)是规则的编号是规则的编号 初始综合数据库包含的事实有：初始综合数据库包含的事实有： 动物有暗斑点，动物有暗斑点，动物动物有长脖子，有长脖子，动物动物有长腿，有长腿，动物动物有奶，有奶，动物动物有蹄有蹄 该例子的部分推理网络如下：该例子的部分推理网络如下：13产生式系统简例产生式系统简例基于规则的动物识别系统基于规则的动物识别系统(3/4)r2r8r11r12r1图中最上层的结点称为图中最上层的结点称为“假设假设”或或“结论结论”中间结点称为中间结点称为“中间假设中间假设”；终结点称为终结点称为“证据证据”或或“事实事实”；每个每个“结论结论”都是本问题的一

13、个目标，所有都是本问题的一个目标，所有“假设假设”构成了本问题的目标集构成了本问题的目标集合合动物是长颈鹿动物是长颈鹿动物有暗斑点动物有暗斑点动物有长脖子动物有长脖子 动物有蹄动物有蹄动物是有蹄类动物动物是有蹄类动物动物是斑马动物是斑马动物是嚼反刍动物动物是嚼反刍动物 动物是哺乳动物动物是哺乳动物 动物有奶动物有奶动物有毛发动物有毛发 动物有长腿动物有长腿动物有黑条纹动物有黑条纹r714产生式系统简例产生式系统简例基于规则的动物识别系统基于规则的动物识别系统(4/4)系统的推理过程系统的推理过程 (1) 先从规则库中取出第一条规则先从规则库中取出第一条规则r1，检查其前提是否可与综合数据库中的

14、已，检查其前提是否可与综合数据库中的已知事实相匹配。知事实相匹配。 r1的前提是的前提是“动物有毛发动物有毛发”，但事实库中无此事实，故匹配失败。，但事实库中无此事实，故匹配失败。然后取然后取r2，该前提可与已知事实，该前提可与已知事实“动物有奶动物有奶”相匹配，相匹配，r2被执行，并将其结论被执行，并将其结论“动物是哺乳动物动物是哺乳动物”作为新的事实加入到综合数据库中。此时，综合数据库的内作为新的事实加入到综合数据库中。此时，综合数据库的内容为：容为： 动物有暗斑，动物有长脖子，动物有长腿，动物有奶，动物有蹄动物有暗斑，动物有长脖子，动物有长腿，动物有奶，动物有蹄 动物是哺乳动物动物是哺乳

15、动物 (2) 再从规则库中取再从规则库中取r3，r4，r5，r6进行匹配，均失败。接着取进行匹配，均失败。接着取r7，该前提与已，该前提与已知事实知事实“动物是哺乳动物动物是哺乳动物”相匹配，相匹配，r7被执行，并将其结论被执行，并将其结论“动物是有蹄类动物动物是有蹄类动物” 作为新的事实加入到综合数据库中。此时，综合数据库的内容变为：作为新的事实加入到综合数据库中。此时，综合数据库的内容变为： 动物有暗斑，动物有长脖子，动物有长腿，动物有奶，动物有蹄动物有暗斑，动物有长脖子，动物有长腿，动物有奶，动物有蹄 动物是哺乳动物，动物是有蹄类动物动物是哺乳动物，动物是有蹄类动物 (3) 此后，此后，

16、r8，r9，r10均匹配失败。接着取均匹配失败。接着取r11，该前提，该前提 “动物是有蹄类动物动物是有蹄类动物 AND 动物有长脖子动物有长脖子 AND 动物有长腿动物有长腿 AND 动物身上有暗斑动物身上有暗斑” 与已知事实相与已知事实相匹配，匹配，r11被执行，并推出被执行，并推出“动物是长颈鹿动物是长颈鹿”。由于。由于“长颈鹿长颈鹿”已是目标集合中已是目标集合中的一个具体动物，即已推出最终结果，故问题求解过程结束。的一个具体动物，即已推出最终结果，故问题求解过程结束。15语义网络语义网络 语义网络是一种用实体及其语义关系来表达知识的有向图。语义网络是一种用实体及其语义关系来表达知识的有

17、向图。 结点：结点：代表代表实体实体，表示事物、概念、情况、属性、状态、事件、动作等，表示事物、概念、情况、属性、状态、事件、动作等 弧：弧：代表代表语义关系语义关系，表示所连两个实体之间的语义联系，必须带有标识，表示所连两个实体之间的语义联系，必须带有标识语义基元语义基元 语义网络中最基本的语义单元称为语义基元，可用三元组表示为：语义网络中最基本的语义单元称为语义基元，可用三元组表示为： （结点（结点1，弧，结点，弧，结点2）基本网元基本网元 指一个语义基元对应的有向图，是语义网络中最基本的结构单元指一个语义基元对应的有向图，是语义网络中最基本的结构单元 例如：例如：语义基元（语义基元（A,

18、 R, B）所对应的基）所对应的基本网元，如图本网元，如图2-3所示。所示。 例例2.6 用语义基元表示用语义基元表示“鸵鸟是一种鸟鸵鸟是一种鸟”这一事实。这一事实。 解：解：如图如图2-4所示。所示。说明：说明：弧的方向不可随意调换。弧的方向不可随意调换。ABR图图2-4鸵鸟鸵鸟鸟鸟是一种是一种图图2-3自然演绎推理 (1) 假言推理 P, PQ Q (2) 拒取式 Q, PQ P (3) 假言三段论 PQ, QR PR第三章 搜索策略主要内容 搜索问题的表示法 盲目搜索：广度优先，深度优先 启发式搜索：解树的代价的计算第四章 计算智能主要内容 进化计算（遗传算法）21计算种群中各个个体的适

19、应度，并进行评价计算种群中各个个体的适应度，并进行评价满足终止条件吗？满足终止条件吗？终止终止选择交叉交叉变异变异Y图图4-18 基本遗传算法的算法流程图基本遗传算法的算法流程图编码和生成初始种群编码和生成初始种群N选择选择 其算法流程如其算法流程如图图4-18所示。所示。 遗传算法的基本结构22 常用的遗传编码算法有霍兰德二进制码、格雷码（常用的遗传编码算法有霍兰德二进制码、格雷码（Gray Code）、实数编码）、实数编码和字符编码等。和字符编码等。(1)二进制编码（二进制编码（Binary encoding） 二进制编码是将原问题的结构变换为染色体的位串结构。在二进制编码中，二进制编码是

20、将原问题的结构变换为染色体的位串结构。在二进制编码中，首先要确定二进制字符串的长度首先要确定二进制字符串的长度l，该长度与变量的定义域和所求问题的计算，该长度与变量的定义域和所求问题的计算精度有关。精度有关。 例例5.5 假设变量假设变量x的定义域为的定义域为5，10，要求的计算精度为，要求的计算精度为10-5，则需要将，则需要将5，10至少分为至少分为600000个等长小区间，每个小区间用一个二进制串表示。于是，个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于串长至少等于20，原因是：，原因是： 524288=219600000220=1048576这样，对应于区间这样，对应于

21、区间5，10内满足精度要求的每个值内满足精度要求的每个值x，都可用一个，都可用一个20位编码的位编码的二进制串二进制串来表示。来表示。 二进制编码存在的主要缺点二进制编码存在的主要缺点是汉明（是汉明（Hamming）悬崖。）悬崖。 例如，例如，7和和8的二进制数分别为的二进制数分别为0111和和1000，当算法从，当算法从7改进到改进到8时，就必须时，就必须改变所有的位。改变所有的位。 遗传编码(1/3)23 适应度函数是一个用于对个体的适应性进行度量的函数。通常，一适应度函数是一个用于对个体的适应性进行度量的函数。通常，一个个体的适应度值越大，它被遗传到下一代种群中的概率也就越大。个个体的适

22、应度值越大，它被遗传到下一代种群中的概率也就越大。(1) 常用的适应度函数常用的适应度函数 在遗传算法中，有许多计算适应度的方法，其中最常用的适应度函在遗传算法中，有许多计算适应度的方法，其中最常用的适应度函数有以下两种：数有以下两种： 原始适应度函数原始适应度函数 它是直接将待求解问题的目标函数它是直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函定义为遗传算法的适应度函数。例如，在求解极值问题数。例如，在求解极值问题时，时，f(x)即为即为x的原始适应度函数。的原始适应度函数。 采用原始适应度函数的采用原始适应度函数的优点优点是能够直接反映出待求解问题的最初求是能够直接反映出待求解

23、问题的最初求解目标，其解目标，其缺点缺点是有可能出现适应度值为负的情况。是有可能出现适应度值为负的情况。 )(max,xfbax适应度函数(1/3)24 标准适应度函数标准适应度函数 在遗传算法中，在遗传算法中，一般要求适应度函数非负，并其适应度值越大越好一般要求适应度函数非负，并其适应度值越大越好。这就。这就往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数fNormal(x)。例如下面的极小

24、化和极大化问题：例如下面的极小化和极大化问题： 极小化问题极小化问题 对极小化问题，其标准适应度函数可定义为对极小化问题，其标准适应度函数可定义为 (4.11)其中，其中，fmax (x)是原始适应函数是原始适应函数f(x)的一个上界。如果的一个上界。如果fmax (x) 未知，则可用当前未知，则可用当前代或到目前为止各演化代中的代或到目前为止各演化代中的f(x)的最大值来代替。可见，的最大值来代替。可见， fmax (x) 是会随着进是会随着进化代数的增加而不断变化的。化代数的增加而不断变化的。 否则当0)()()()()(maxmaxxfxfxfxfxfnomal适应度函数(2/3)25

25、极大化问题极大化问题 对极大化问题，其标准适应度函数可定义为对极大化问题，其标准适应度函数可定义为 (4.12)其中，其中，fmin(x)是原始适应函数是原始适应函数f(x)的一个下界。如果的一个下界。如果fmin(x) 未知，则可用当前未知，则可用当前代或到目前为止各演化代中的代或到目前为止各演化代中的f(x)的最小值来代替。的最小值来代替。 否则当0)()()()()(minminxfxfxfxfxfnomal适应度函数(3/3)26 遗传算法中的基本遗传操作包括选择、交叉和变异遗传算法中的基本遗传操作包括选择、交叉和变异3种，而每种操作种，而每种操作又包括多种不同的方法，下面分别对它们进

26、行介绍。又包括多种不同的方法，下面分别对它们进行介绍。(1). 选择操作选择操作 选择（选择（Selection）操作是指根据选择概率按某种策略从当前种群中）操作是指根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。 常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。 比例选择比例选择 比例选择方法（比例选择方法（Proportional Model）的基本思想是：各个个体被选）的基本思想是：各个个体被选中的概率与其适应度

27、大小成正比。中的概率与其适应度大小成正比。 常用的比例选择策略包括常用的比例选择策略包括 轮盘赌选择轮盘赌选择 繁殖池选择繁殖池选择基本遗传操作(1/11)27 轮盘赌选择轮盘赌选择 轮盘赌选择法又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体轮盘赌选择法又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：其中，其中，P(xi)是个体是个体xi的相对适应度，即个体的相对适应度，即个体xi被选中的概率；被选中的概率；f(xi)是个体是个体xi的原的原始适应度；是种群的累加适

28、应度。始适应度；是种群的累加适应度。 轮盘赌选择算法的基本思想是：根据每个个体的选择概率轮盘赌选择算法的基本思想是：根据每个个体的选择概率P(xi)将一个圆盘将一个圆盘分成分成N个扇区，其中第个扇区，其中第i个扇区的中心角为：个扇区的中心角为：再设立一个移动指针，将圆盘的转动等价为指针的移动。选择时，假想转动圆盘，若再设立一个移动指针，将圆盘的转动等价为指针的移动。选择时，假想转动圆盘，若静止时指针指向第静止时指针指向第i个扇区，则选择个体个扇区，则选择个体i。其物理意义如图。其物理意义如图5-19所示。所示。1()()()iiNjjf xP xf x1()22()()iiNijjf xp x

29、fx基本遗传操作(2/11)28P(x1)P(x2)P(xN)P(xi)2p(xp(xi i) )图图4-19 轮盘赌选择轮盘赌选择 从统计角度看，个从统计角度看，个体的适应度值越大，体的适应度值越大，其对应的扇区的面积其对应的扇区的面积越大，被选中的可能越大，被选中的可能性也越大。这种方法性也越大。这种方法有点类似于发放奖品有点类似于发放奖品使用的轮盘，并带有使用的轮盘，并带有某种赌博的意思，因某种赌博的意思，因此亦被称为轮盘赌选此亦被称为轮盘赌选择。择。基本遗传操作(3/11)29(2)交叉操作交叉操作 交叉（交叉（Crossover）操作是指按照某种方式对选择的父代个体的染色）操作是指按

30、照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。交配重组是自然界体的部分基因进行交配重组，从而形成新的个体。交配重组是自然界中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为二进制交叉和实值交叉两种类型二进制交叉和实值交叉两种类型。 二进制交叉二进制交叉 二进制交叉（二进制交叉（Binary Valued Crossover）是指二进制编码情况下所）是指二进制编码情况下所采用的交

31、叉操作，它主要包括采用的交叉操作，它主要包括单点交叉、两点交叉、多点交叉和均匀单点交叉、两点交叉、多点交叉和均匀交叉交叉等方法。等方法。基本遗传操作(4/11)30 单点交叉单点交叉 单点交叉也称简单交叉，它是先在两个父代个体的编码串中随机设定一个单点交叉也称简单交叉，它是先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体。假设两个父代的个体串分别是：生成子代中的两个新的个体。假设两个父代的个体串分别是： X=x1 x2 xk xk+1 xn Y=y1

32、 y2 yk yk+1 yn 随机选择第随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方法，但位为交叉点，若采用对交叉点后面的基因进行交换的方法，但点交叉是将点交叉是将X中的中的xk+1到到xn部分与部分与Y中的中的yk+1到到yn部分进行交叉，交叉后生成的部分进行交叉，交叉后生成的两个新的个体是：两个新的个体是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk xk+1 xn 例例4.7 设有两个父代的个体串设有两个父代的个体串A=0 0 1 1 0 1 和和B=1 1 0 0 1 0 ，若随机交叉点，若随机交叉点为为4，则交叉后生成的两个新的个体是：，则交叉后生

33、成的两个新的个体是： A= 0 0 1 1 1 0 B= 1 1 0 0 0 1 基本遗传操作(5/11)31 两点交叉两点交叉 两点交叉是指先在两个父代个体的编码串中随机设定两个交叉点，然后再两点交叉是指先在两个父代个体的编码串中随机设定两个交叉点，然后再按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。 假设两个父代的个体串分别是：假设两个父代的个体串分别是： X=x1 x2 xi xj xn Y=y1 y2 yi yj ,yn 随机设定第随机设定第i、j位为两个交叉点（其中位为两个交叉点（其中ijn），两点交叉是将），两点

34、交叉是将X中的中的xi+1到到xj部分与部分与Y中的中的yi+1到到yj部分进行交换，交叉后生成的两个新的个体是：部分进行交换，交叉后生成的两个新的个体是： X= x1 x2 xi yi+1 yj xj+1 xn Y= y1 y2 yi xi+1 xj yj+1 yn 例例4.8 设有两个父代的个体串设有两个父代的个体串A= 0 0 1 1 0 1 和和B= 1 1 0 0 1 0 ，若随机交叉点，若随机交叉点为为3和和5，则交叉后的两个新的个体是：，则交叉后的两个新的个体是： A= 0 0 1 0 1 1 B= 1 1 0 1 0 0 基本遗传操作(6/11)32 多点交叉多点交叉 多点交是

35、指先随机生成多个交叉点，然后再按这些交叉点分段地进行部分基因多点交是指先随机生成多个交叉点，然后再按这些交叉点分段地进行部分基因交换，生成子代中的两个新的个体。交换，生成子代中的两个新的个体。 假设交叉点个数为假设交叉点个数为m，则可将个体串划分为，则可将个体串划分为m+1个分段，其划分方法是：个分段，其划分方法是： 当当m为偶数时，对全部交叉点依次进行两两配对，构成为偶数时，对全部交叉点依次进行两两配对，构成m/2个交叉段。个交叉段。 当当m为奇数时，对前为奇数时，对前(m-1)个交叉点依次进行两两配对，构成个交叉点依次进行两两配对，构成(m-1)/2个交叉段，个交叉段，而第而第m个交叉点则

36、按单点交叉方法构成一个交叉段。个交叉点则按单点交叉方法构成一个交叉段。 下面以下面以m=3为例进行讨论。假设两个父代的个体串分别是为例进行讨论。假设两个父代的个体串分别是X=x1 x2 xi xj xk xn和和Y=y1 y2 yi yj yk yn，随机设定第随机设定第i、j、k位为三个交叉点（其位为三个交叉点（其中中ijk4545否否高高 会会2 2女女31453145否否高高会会3 3女女20302030是是低低会会4 4男男2020是是低低不会不会5 5女女20302030是是中中不会不会6 6女女20302030否否中中会会7 7女女31453145否否高高会会8 8男男314531

37、45是是中中不会不会9 9男男31453145否否中中会会1010女女2002022-1-205151()1()()()(/)=()()nikiiikjP CP x CP X C P CP CXP XP X 训练样本中对于(女性，年龄介于3145之间，不具学生身份，收入中等)的个人，按照朴素贝叶斯分类会将其分到办信用卡一类中。 办卡的概率是(0.044)/(0.044+0)=1(正规化分类的结果P(会)/(P(会)+P(不会)。2022-1-205252nave bayes2022-1-20532022-1-20542022-1-2055第六章 符号学习主要内容 决策树(ID3) 支持向量机构

38、造树 训练样本的信息值训练样本的信息值 第一棵树，属性，各叶节点的信息值第一棵树，属性，各叶节点的信息值 第一棵树，属性，导致的信息增益第一棵树，属性，导致的信息增益 依次，计算每棵树导致的依次，计算每棵树导致的信息增益信息增益 选择获得最大信息增益的属性进行划分选择获得最大信息增益的属性进行划分 以此类推，递归，继续划分以此类推，递归，继续划分 当所有叶节点都是纯的，划分过程终止当所有叶节点都是纯的，划分过程终止例子 气象数据集，都是标称属性什么因素影响是否去什么因素影响是否去打网球？打网球？OutlookTemperatureHumidityWindyPlay?sunnyhothighfa

39、lseNosunnyhothightrueNoovercasthothighfalseYesrainmildhighfalseYesraincoolnormalfalseYesraincoolnormaltrueNoovercastcoolnormaltrueYessunnymildhighfalseNosunnycoolnormalfalseYesrainmildnormalfalseYessunnymildnormaltrueYesovercastmildhightrueYesovercasthotnormalfalseYesrainmildhightrueNo （1）训练样本的信息值(基

40、于类的比例） 训练样本（用来创建树的数据集）在包含9个yes和5个no的根节点上，对应于信息值 info(9,5)=0.940位位 总的信息 （2） 第一棵树，属性，各叶节点的信息值 基于天气(outlook)的划分，在叶节点的yes和no类的个数分别是2,3，4,0，和3,2，而这些节点的信息值分别是： info(2,3)=0.971位 sunny info(4,0)=0. 0位 overcast info(3,2)=0.971位 rainYESNo合计sunny235overcast404rain325合计95 （3）第一棵树，属性，导致的信息增益 计算平均信息值。 根据天气的树导致的信息

41、增益为：基于类比例原来信息需求-基于天气属性划分之后得到的信息需求gain(outlook)=info(9,5)-info(2,3,4,0,3,2)=0.940-0.693=0.247位位 （4）依次，计算每棵树导致的信息增益为每个属性计算信息增益 gain(outlook)=0.247位 gain(temperature)=0.029位 gain(humidity)=0.152位 gain(windy)=0.048位 （5）选择获得最大信息增益的属性进行划分最大信息增益：最大信息增益： gain(outlook)=0.247位位选择天气作为树的根节点的划分属性，其中一个子女节点是最纯的，并且

42、这使它明显优于其他属性。湿度是次佳选择，它产生了一个几乎完全纯的较大的子女节点。 （6）以此类推，递归，继续划分递归继续选择当天气为晴时，所达到的节点上的可 能的深一层的分支除天气外，其他属性产生的信息增益 分别为： gain(temperature)=0.571位 gain(humidity)=0.971位 gain(windy)=0.020位继续再选择湿度(humidity)作为划分属性支持向量机概念 支持向量机的目标：为了实现小样本的分类器的构造，设计一个最大间隔的超平面，把数据样本分成两类；对于线性不可分的情况，使用核函数将数据点转换到更高维的空间，让你在高维空间线性可分。 VC维：n维空间的VC维为n+1支持向量支持向量机示意图机示意图 决策边界离两类数据应尽可能远 最大化间隔 m第 1 类第 2 类m第七章 联结学习神经网络模型 三层BP网络Thanks!70