第7章机器学习 人工智能与专家系统(第二版) 尹朝庆

1、，人工智能和专家系统，第7章机器学习，7.1机器学习的特征和方法7.2归纳学习方法7.3遗传算法7.4人工神经网络方法，7.1机器学习的特征和方法，1机器学习的主要特征(1)目的(2)结构(3)有效性(4)开放性2机器学习的基本方法(1)归纳学习(2)遗传算法(2)，7.2.1CLS算法，7.2.2ID3算法，7.2.3应用归纳学习生成产生规则集，7 . 2 . 3 1CLS决策树构造算法在CLS算法生成的决策树中，节点对应于待分类对象的属性，从某个节点画出的弧对应于该属性的值，叶节点对应于分类结果。 让分类对象的属性表为属性列表=A1、A2、An，并且每个属性Ai的值范围被记录为值(Ai)，

2、并且要分类的分类结果构成分类结果表Class=C1、C2、Cm。通常，n1和m2是必需的。trAining实例集合T=中的一个元素是一个training实例，并且该training实例的特征向量是X=(a1，a2，An)，其中ai是该实例的第I个属性ai的值，c是该实例的分类结果。CLS算法(1)初始化：输入初始学习样本，形成初始学习样本集t；输入分类属性，形成初始属性表属性列表=(A1，A2，Ai，An)，输入每个属性的值，形成每个属性的值域表：值(A1)，值(A2)，值(Ai)，值(An)(2)如果所有叶节点都是最终叶节点，算法成功终止；否则，转到步骤(3)。(3)如果当前属性表属性列表=

3、()，算法无法终止，否则，转到步骤(4)。(4)取当前属性表的第一个属性Ai，将所有非终端叶节点中的实例集逐一划分，并用属性Ai标记划分后的非终端叶节点。(5)如果属性AI的值(Ai)具有S值，则在非末端叶节点中设置的实例被分成S个子集，并且在同一子集节点中的实例属性Ai具有相同的属性值，并且与子集节点的连接弧用属性值标记。如果一个子集中所有实例的分类结果都是Cj，那么该子集节点被称为最终叶节点，并且该节点被标记有分类结果Cj；如果子集是一个空集，该子集的节点也被称为最终叶节点，它被删除，相应的连接弧被删除。(6)删除当前属性表中的第一个属性，并转到步骤(2)。CLS算法7.1的应用实例根据人

4、的外貌特征进行分类。三个分类特征是身高、头发颜色和眼睛颜色；分类结果为：p和n.特征属性的值范围为：值(头发颜色)=淡黄色，棕色，黑色值(高度)=短，高值(眨眼)=蓝色，黑色初始属性表为属性列表=(高度，头发颜色，眨眼)。现有8个学习实例集：表7.1示例7.1学习实例集使用CLS算法生成人员分类决策树。通过决策树获得产生式规则集，并将规则集中的规则进行合并，得到一个没有冗余的规则集。解决方案：(1)根据表7.1中给出的学习实例集，初始实例集T可以如下获得。在T中，只显示实例的序列号和括号中的分类类别。T=(1(P)、2(N)、3(P)、4(N)、5(N)、6(P)、7(N)、8(N)初始属性表

5、属性列表=(身高、头发颜色、眼睛接触)循环1:取属性表的第一个属性”，Height=short 子集T1=(1(P)、4(N)、8(N) height=high 子集T2=(2(N)、3(P)、5(N)、6(P)、7(N)删除属性表中的第一个属性。两个子循环是：循环21:属性“头发颜色”将T1分为三个子集：子集t11(头发颜色=(1(P)、8(N)子集T12(头发颜色=(棕色)=(末端叶节点。 并且删除了带有头发颜色为“黑色”的子集t13=(4(n)标记为NLoop22:的AttrList=头发颜色被分成三个子集：带有头发颜色为“淡黄色”的子集t21=(2(n)，6(P)带有头发颜色为“棕色”

6、的子集t22=(3(P)末端叶节点，以及带有头发颜色为“黑色”的子集t23=(5)Loop 3:采用属性表中的第一个属性“眼睛接触” 这两个子循环是：循环31:属性“眼睛接触”将T11分为两个子集：眼睛接触=蓝色子集T111=(1(P)末端叶节点，以及标记为P眼睛接触=黑色子集T112=(8(N 8)标记为NLoop32:的属性“眼睛接触”分为两个子集：眼睛接触=蓝色子集T211=(6(P)最终叶节点，眼睛接触=黑色子集T212=(2(N)最终图7.1示例7.1由CLS算法生成的决策树， (2)生产规则集R1: (height=short )(头发颜色=淡黄色)(眼睛颜色=蓝色)类别=p R2

7、: (height=short )(头发颜色=淡黄色)(眼睛颜色=黑色)类别=n Class=p r5: (height=high )(头发颜色=淡黄色)(眼睛颜色=黑色)类别=n R6: (height=high )(头发颜色=棕色)类别=p r7: (height=high ) R3和R7可以组合为：头发颜色=黑色 Category=n R2和R5可以组合为：(头发颜色=淡黄色)(眼神接触=黑色)Category=n R1和R4可以组合为：(头发颜色=淡黄色)(眼神接触=蓝色)Category=P (1)初始化：输入初始学习示例以形成初始学习示例集； 输入分类属性，形成初始属性表：属性列表

8、=(A1，A2，Ai，an)输入每个属性的值，形成每个属性的值域表：值(A1)，值(A2)，值(Ai)，值(an)，否则，转到步骤(3)。(3)如果当前属性表属性列表=()，算法无法终止，否则，转到步骤(4)。(4)从当前属性表中选择属性Ai，使得用Ai划分非末端叶节点实例集Tk的平均信息I (Tk，Ai)最小，并用属性Ai标记划分的非末端叶节点。如果属性Ai的值字段表值(Ai)具有S值，则非末端叶节点实例集Tk被分成S个子集：Tk(I)、Tk2(i)、Tkx(i)、Tks(i)。同一子集节点中的实例属性人工智能具有相同的属性值。计算每个子集的熵，其中ekx是子集Tkx(i)的实例数，ekx(

9、Cj)是分类结果为Cj的实例数。计算Tk除以属性Ai的平均信息：比较当前属性表中Tk除以不同属性的平均信息，取minI(Tk，Ai)对实例集Tk进行实际划分，并用Ai的属性值标记子集节点的连接弧。如果一个子集中所有实例的分类结果都是Cj，那么该子集节点被称为最终叶节点，并且该节点被标记有分类结果Cj；如果子集是一个空集，该子集的节点也被称为最终叶节点，它被删除，相应的连接弧被删除。(5)删除当前属性表中用于实际划分实例集Tk的属性Ai，并转到步骤(2)。例7.2用ID3算法重复例7.1。初始属性表是属性列表=(身高，头发颜色，眨眼)。(1)使用ID3算法生成用于人员分类的决策树(2)从决策树中

10、获得产生规则集，以及解决方案：(1)从表7.1中给出的学习样本集，可以如下获得初始样本集t。T=(1(P)，2(N)，3(P)，4(N)，5(N)，6(P)，7(N)，8(N)初始属性表属性列表=(身高，头发颜色，眼睛接触)，循环1:选择属性分区t，当前属性表中有三个属性，三个子循环如下。Loop11:采用属性表的第一个属性“height”并将t分成两个子集：height=short=(1 (p)、4(N)、8(N)的子集T1(1)和实例数e1=3，其中e1(P)=1和e1(N)=2，并计算t1 7(N)实例数e2=5，其中e2(P)=2，e2(N)=3。计算T2熵(1):如果属性“高度”用于

11、划分T，则计算平均信息：循环12:采用属性表中的第二个属性“头发颜色”将T划分为三个子集：头发颜色=淡黄色其中e2(P)=2，e2(N)=2，计算T1熵(2):子集T2(2)，颜色=棕色=(3 (p)，实例数量e2=1，其中e2(P)=1，e2(N)=0， 计算T2的熵(2)计算T3的熵(2):如果属性“头发颜色”用于划分T，则计算平均信息量：循环13:采用属性表中的第三个属性“眨眼”，并将T划分为两个子集：子集T1(3)=(1(P)，3(P)，4(N)，5(N)计算T1(3)的熵：眼睛接触=“黑色”子集T2(3)=(2(N)，7(N)，8(N)，实例数量e2=3，其中e2 选择属性列表将t分

12、为三个子集：头发颜色子集T1=(1(P)、2(N)、6(P)、8(N)头发颜色子集T2=(3(P)末端叶节点，标记为pHair color=“当前属性表有两个属性，两个子循环如下。 循环21:采用属性表中的第一个属性“高度”，并将T1分为两个子集：子集height=short T11(1)=(1(P)，8(N)，实例数e1=2，其中e1(P)=1，e1(N)=1，计算T11(1) E1(N)=1的值，计算T12(1)的熵：如果属性“高度”用于划分T:循环22:取6计算T11(2)的熵：眨眼=黑色子集T12(2)=(2(N)，8(N)实例号e1=2，其中e1(P)=0，e1(N)=2，计算T12

13、(2)的熵：并计算属性因此，选择属性眨眼以将T1分成两个子集：具有眨眼=蓝色=(1 (p)，6(P)末端叶节点的子集T11和具有眨眼=黑色=(2(P)的子集T12 图7.2示例7.2由ID3算法生成的决策树，(2)生产规则集R1:(头发颜色=亚麻色)(眼睛颜色=蓝色)类别=P R2:(头发颜色=亚麻色)(眼睛颜色=黑色)类别=N R3从决策树示例7.3根据长方体工件外部尺寸的加工误差对工件进行分类。 三个分类特征属性是：长误差范围、宽误差范围和高误差范围；分类结果为y(可用)和n(不可用)。特征属性的值范围为：值(长误差范围)=a1，a2，a3Value(宽误差范围)=b1，b2Value(高

14、误差)=h1，h2。初始属性表是属性列表=(长错误、宽错误、高错误)。目前，从工件检验数据库中随机选取8个工件，形成学习样本集t，如表7.2所示：表7.2样本7.3学习样本集，(1)使用CLS算法生成工件分类决策树。(2)通过决策树获得生产规则集。(3)合并规则集中的规则，得到没有冗余的规则集。(4)如果初始属性表为属性列表=(宽错误、长错误、高错误)，请重新设置主题。(5)用ID3算法重做主题。解决方案：(1)使用CLS算法生成工件分类决策树根据表7.2中给出的学习样本集，初始样本集可以如下获得：T=(1(Y)，2(N)，3(Y)，4(N)，5(N)，6(Y)，7(N)，8(N)循环1:获取属性表中的第一个属性“长误差”，并将其分成三个子集：长误差=子集t1“a1”=(1(Y)，2(N)，6(Y)， 8(N)长误差=子集“a2”的T2=(3(y)将其标记为N以删除第一个属性，属性列表=(宽误差，高误差，循环2:将属性表中的第一个属性T1分成两个子集：宽误差子集t11=(1(y)， 8(N)wide error= B2 =(2 Loops 3:的子集T12采用属性表中的第一个属性高错误来划分T11和T12:Loops 31:属性高错误将T11划分为两个子集：具有高错