《第7章机器学习 人工智能与专家系统(第二版) 尹朝庆》由会员分享，可在线阅读，更多相关《第7章机器学习 人工智能与专家系统(第二版) 尹朝庆（161页珍藏版）》请在金锄头文库上搜索。
1、,人工智能与专家系统,第7章 机器学习,7.1 机器学习的特征与方法 7.2 归纳学习方法 7.3 遗传算法 7.4 人工神经网络方法,7.1 机器学习的特征与方法,1 机器学习的主要特征 (1)目的性 (2)结构性 (3)有效性 (4)开放性 2 机器学习的基本方法 (1)归纳学习 (2)遗传算法 (3)人工神经网络,7.2 归纳学习方法,归纳学习 是从特例推导一般规则的学习方法。,7.2.1 CLS算法 7.2.2ID3算法 7.2.3归纳学习生成产生式规则集的应用,7.2.1 CLS算法,1 CLS决策树构造算法 在CLS算法生成的决策树中，节点对应于待分类对 象的属性，由某一节点引出的
2、弧对应于这个属性的取 值，叶节点对应于分类的结果。 设分类对象的属性表为AttrList=A1, A2, , An，每 一个属性Ai的值域记为Value (Ai)，需要分类的分类结果 组成分类结果表Class=C1,C2,Cm。一般应有n1， m2。训练实例集T=中的一个元素就是一个训 练实例，训练实例的特征向量为X=(a1, a2, , an )，其中ai为这个实例的第i个属性Ai的取值， C为这个实例的分类结果，CClass。,CLS算法 (1)初始化： 输入初始学习实例，组成初始学习实例集合T； 输入分类属性，组成初始属性表 AttrList=(A1，A2，Ai，An) 输入各属性的值，
3、组成各属性的值域表： Value(A1)，Value(A2)，Value(Ai)，Value(An) (2)若所有的叶节点都是终叶节点，即算法成功终止；否则 转步骤(3)。 (3)若当前属性表AttrList=( )，则算法失败终止，否则转步 骤(4)。,(4)取当前属性表第1个属性Ai，逐一划分所有非终叶 节点中的实例集，并用属性Ai标记划分的非终叶节点。 (5)若属性Ai的值域表Value(Ai)有s个值，则将一个非 终叶节点中的实例集划分为s个子集，同一个子集节点中 的实例属性Ai有相同的属性值，并用属性值标记与子集 节点的连接弧。 若一个子集中的所有实例的分类结果均为Cj，则该 子集节
4、点称为终叶节点，且用分类结果Cj标记该节点； 若一个子集为空集，则该子集节点也称为终叶节点，且 予以删除，并删除相应的连接弧。 (6)删除当前属性表中的第1个属性，转步骤(2)。,CLS算法的应用 例7.1根据人员的外貌特征属性对人员进行 分类，3个分类特征属性分别是：身高、头发颜 色、眼睛颜色；分类结果是：P和N。 特征属性的值域分别是： Value(发色) = 亚麻色，棕色，黑色 Value(身高) = 矮，高 Value(眼色) = 兰色，黑色 初始属性表为AttrList = (身高，发色，眼色)。,现有8个实例组成学习实例集T： 表7.1 例7.1的学习实例集 应用CLS算法生成人员
5、分类决策树 由决策树得出产生式规则集 对规则集中的规则进行合并，给出没有冗余的规则集,解：(1)由表7.1给出的学习实例集可得出初始实例集T如下， 在T中，只表示了实例的序号及用括号括起来的分类类别。 T=( 1(P)，2(N)，3(P)，4(N)，5(N)，6(P)，7(N)，8(N) ) 初始属性表AttrList=(身高，发色，眼色) Loop1: 取属性表第1个属性“身高”划分T为2个子集。 身高 =“矮”的子集T1 = ( 1(P)，4(N)，8(N) ) 身高 =“高”的子集T2 = ( 2(N)，3(P)，5(N)，6(P)，7(N) ) 删除属性表中的第1个属性，使AttrLi
6、st=(发色，眼色),Loop2: 取属性表中第1个属性“发色”划分T1和T2，2个子循环分别是： Loop21: 属性“发色”划分T1为3个子集： 发色 =“亚麻色”的子集T11 = ( 1(P)，8(N) ) 发色 =“棕色”的子集T12 = ( ) 终叶节点，删除 发色 =“黑色”的子集T13 = ( 4(N) ) 终叶节点，标记为N Loop22: 属性“发色”划分T2为3个子集： 发色 =“亚麻色”的子集T21 = ( 2(N)，6(P) ) 发色 =“棕色”的子集T22 = ( 3(P) ) 终叶节点，标记为P 发色 =“黑色”的子集T23 = ( 5(N)，7(N) ) 终叶节点
7、，标记为N 删除属性表中第1个属性，使AttrList = (眼色),Loop3: 取属性表中第1个属性“眼色”划分T11和T21，2个子循环分别是： Loop31: 属性“眼色”划分T11为2个子集： 眼色 =“兰色”的子集T111 = ( 1(P) )终叶节点，标记为P 眼色 =“黑色”的子集T112 = ( 8(N) )终叶节点，标记为N Loop32: 属性“眼色”划分T21为2个子集： 眼色 =“兰色”的子集T211 = ( 6(P) )终叶节点，标记为P 眼色 =“黑色”的子集T212 = ( 2(N) )终叶节点，标记为N 删除属性表中第1个属性，使AttrList = （ ）
8、Loop4: 所有叶节点都是终叶节点，故算法成功终止。,图7.1 例7.1由CLS算法生成的决策树,(2)由决策树得出产生式规则集 R1：(身高 =“矮”)(发色 =“亚麻色”)(眼色 =“兰色”) 类别 =“P” R2：(身高 =“矮”)(发色 =“亚麻色”)(眼色 =“黑色”) 类别 =“N” R3：(身高 =“矮”)(发色 =“黑色”) 类别 =“N” R4：(身高 =“高”)(发色 =“亚麻色”)(眼色 =“兰色”) 类别 =“P” R5：(身高 =“高”)(发色 =“亚麻色”)(眼色 =“黑色”) 类别 =“N” R6：(身高 =“高”)(发色 =“棕色”) 类别 =“P” R7：(
9、身高 =“高”)(发色 =“黑色”) 类别 =“N”,(3)对规则集中的规则合并 对后件相同的规则，可考察前件包含的条件，合并 成新规则来代替原有规则。 R3与R7可合并为：发色 =“黑色” 类别=“N” R2与R5可合并为： (发色 =“亚麻色”)(眼色 =“黑色”) 类别 =“N” R1与R4可合并为： (发色 =“亚麻色”)(眼色 =“兰色”) 类别 =“P” R6：(身高 =“高”)(发色 =“棕色”) 类别 =“P”,7.2.2ID3算法,ID3算法 对属性的选择给出一种启发式搜索方法，通过计算 实例集的熵来选择平均信息量最小的属性来划分实例 集，扩展生成决策树。 (1)初始化： 输
10、入初始学习实例，组成初始学习实例集合T 输入分类属性，组成初始属性表： AttrList=(A1，A2，Ai，An) 输入各属性的值，组成各属性的值域表： Value(A1)，Value(A2)，Value(Ai)，Value(An),(2)若所有的叶节点都是终叶节点，即算法 成功终止；否则转步骤(3)。 (3)若当前属性表AttrList=( )，则算法失 败终止，否则转步骤(4)。,(4)从当前属性表中选择一个属性Ai，使得用Ai划分 非终叶节点实例集Tk 的平均信息量 I(Tk，Ai ) 最小，并 用属性Ai标记该划分的非终叶节点。 若属性Ai的值域表Value(Ai)有s个值，则将非终
11、叶 节点实例集Tk划分为s个子集： Tk1(i)，Tk2(i)，Tkx(i)，Tks(i) 同一个子集节点中的实例属性Ai有相同的属性值。, 计算每个子集的熵： 其中，ekx是子集Tkx(i)的实例数，ekx(Cj)是其中分类结果为 Cj的实例数。 计算用属性Ai划分Tk的平均信息量：, 比较当前属性表中的不同属性划分Tk的平均信息 量，取min I (Tk, Ai )来实际划分实例集Tk，并用Ai的属 性值标记与子集节点的连接弧。 若一个子集中的所有实例的分类结果均为Cj，则 该子集节点称为终叶节点，且用分类结果Cj标记该节点； 若一个子集为空集，则该子集节点也称为终叶节点，且予 以删除，并
12、删除相应的连接弧。 (5)删除当前属性表中已用于实际划分实例集Tk的属性 Ai，转步骤(2)。,例7.2 应用ID3算法重做例 7.1. 初始属性表为 AttrList=(身高，发色，眼色)。 (1) 应用ID3算法生成人员分类决策树 (2) 由决策树得出产生式规则集,解：(1)由表7.1给出的学习实例集可得出初始实例集T如下。 T = (1(P)，2(N)，3(P)，4(N)，5(N)，6(P)，7(N)，8(N) ) 初始属性表AttrList = (身高，发色，眼色),Loop1: 选择属性划分T，T的实例数e = 8。当前属性表中 有3个属性，3个子循环分别如下。 Loop11: 取属
13、性表第1个属性“身高”划分T为2个子集： 身高 =“矮”的子集T1(1) = ( 1(P)，4(N)，8(N) ) 实例数e1 = 3，其中e1(P) = 1，e1(N) = 2，计算T1(1)的熵：, 身高 =“高”的子集T2(1 ) = ( 2(N)，3(P)，5(N)，6(P)，7(N) ) 实例数e2 = 5，其中e2(P) = 2，e2(N) = 3，计算T2(1)的熵： 计算若使用属性“身高”划分T的平均信息量：,Loop12: 取属性表第2个属性“发色”划分T为3个子集： 发色 =“亚麻色”的子集T1(2) = (1(P)，2(N)，6(P)，8(N) ) 实例数e2 = 4，其
14、中e2(P) = 2，e2(N) = 2，计算T1(2)的熵： 发色=“棕色”的子集T2(2) = (3(P) ) 实例数e2 = 1，其中e2(P) = 1，e2(N) = 0，计算T2(2)的熵：, 发色=“黑色”的子集T3(2) = ( 2(N)，5(N)，7(N) ) 实例数e3 = 3，其中e3(P ) = 0，e3(N) = 3，计算T3(2)的熵： 计算若使用属性“发色”划分T的平均信息量：,Loop13: 取属性表第3个属性“眼色”划分T为2个子集： 眼色=“兰色”的子集T1(3 ) = ( 1(P)，3(P)，4(N)，5(N)，6(P) ) 实例数e1 = 5，其中e1(P
15、) = 3，e1(N) = 2，计算T1(3)的熵： 眼色=“黑色”的子集T2(3) = ( 2(N)，7(N)，8(N) ) 实例数e2 = 3，其中e2(P) = 0，e2(N) = 3，计算T2(3)的熵：,计算若使用属性“眼色”划分T的平均信息量： 比较不同属性划分T的平均信息量，有： I (T，身高 ) I (T，眼色) I (T，发色) 故选择属性“发色”将T划分为3个子集： 发色 =“亚麻色”的子集T1 = ( 1(P)，2(N)，6(P)，8(N) ) 发色 =“棕色”的子集T2 = ( 3(P) ) 终叶节点，标记为P 发色 =“黑色”的子集T3 = ( 2(N)，5(N)，
16、7(N) ) 终叶节点，标记为N 删除属性表中的属性“发色”，AttrList = (身高，眼色),Loop2: 选择属性划分T1，T1的实例数e = 4。当前属性表有2个属性，2个子循环分别如下。 Loop21: 取属性表第1个属性“身高”划分T1为2个子集： 身高 =“矮”的子集T11(1 ) = ( 1(P)，8(N) ) 实例数e1 = 2，其中e1(P) = 1，e1(N) = 1，计算T11(1)的熵：, 身高 =“高”的子集T12(1) = ( 2(N)，6(P) ) 实例数e1 = 2，其中e1(P) = 1，e1(N) =1，计算T12(1)的熵： 计算若使用属性“身高”划分T的平均信息量：,Loop22: 取属性表中第2个属性“眼色”划分T1为2个子集： 眼色 =“兰色”的子集T11(2 ) =
