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

人工智能与专家系统(第二版）中国水利水电出版社人工智能与专家系统人工智能与专家系统(第二版）中国水利水电出版社第7章机器学习7.1机器学习的特征与方法7.2归纳学习方法7.3遗传算法7.4人工神经网络方法人工智能与专家系统(第二版）中国水利水电出版社7.1机器学习的特征与方法1机器学习的主要特征(1)目的性(2)结构性(3)有效性(4)开放性2机器学习的基本方法(1)归纳学习(2)遗传算法(3)人工神经网络人工智能与专家系统(第二版）中国水利水电出版社7.2归纳学习方法归纳学习是从特例推导一般规则的学习方法。7.2.1CLS算法7.2.2．ID3算法7.2.3．归纳学习生成产生式规则集的应用人工智能与专家系统(第二版）中国水利水电出版社7.2.1CLS算法1CLS决策树构造算法在CLS算法生成的决策树中，节点对应于待分类对象的属性，由某一节点引出的弧对应于这个属性的取值，叶节点对应于分类的结果。设分类对象的属性表为AttrList={A1,A2,…,An}，每一个属性Ai的值域记为Value(Ai)，需要分类的分类结果组成分类结果表Class={C1,C2,……,Cm}。一般应有n≥1，m≥2。训练实例集T={X,C}中的一个元素就是一个训练实例X,C，训练实例X，C的特征向量为X=(a1,a2,……,an)，其中ai为这个实例的第i个属性Ai的取值，C为这个实例的分类结果，C∈Class。人工智能与专家系统(第二版）中国水利水电出版社CLS算法(1)初始化：输入初始学习实例，组成初始学习实例集合T；输入分类属性，组成初始属性表AttrList=(A1，A2，…，Ai，…An)输入各属性的值，组成各属性的值域表：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，则该子集节点称为终叶节点，且用分类结果Cj标记该节点；若一个子集为空集，则该子集节点也称为终叶节点，且予以删除，并删除相应的连接弧。(6)删除当前属性表中的第1个属性，转步骤(2)。人工智能与专家系统(第二版）中国水利水电出版社2CLS算法的应用例7.1根据人员的外貌特征属性对人员进行分类，3个分类特征属性分别是：身高、头发颜色、眼睛颜色；分类结果是：P和N。特征属性的值域分别是：Value(发色)={亚麻色，棕色，黑色}Value(身高)={矮，高}Value(眼色)={兰色，黑色}初始属性表为AttrList=(身高，发色，眼色)。人工智能与专家系统(第二版）中国水利水电出版社现有8个实例组成学习实例集T：表7.1例7.1的学习实例集1.应用CLS算法生成人员分类决策树2.由决策树得出产生式规则集3.对规则集中的规则进行合并，给出没有冗余的规则集人工智能与专家系统(第二版）中国水利水电出版社解：(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个属性，使AttrList=(发色，眼色)人工智能与专家系统(第二版）中国水利水电出版社Loop2:取属性表中第1个属性“发色”划分T1和T2，2个子循环分别是：Loop21:属性“发色”划分T1为3个子集：发色=“亚麻色”的子集T11=(1(P)，8(N))发色=“棕色”的子集T12=()终叶节点，删除发色=“黑色”的子集T13=(4(N))终叶节点，标记为NLoop22:属性“发色”划分T2为3个子集：发色=“亚麻色”的子集T21=(2(N)，6(P))发色=“棕色”的子集T22=(3(P))终叶节点，标记为P发色=“黑色”的子集T23=(5(N)，7(N))终叶节点，标记为N删除属性表中第1个属性，使AttrList=(眼色)人工智能与专家系统(第二版）中国水利水电出版社Loop3:取属性表中第1个属性“眼色”划分T11和T21，2个子循环分别是：Loop31:属性“眼色”划分T11为2个子集：眼色=“兰色”的子集T111=(1(P))终叶节点，标记为P眼色=“黑色”的子集T112=(8(N))终叶节点，标记为NLoop32:属性“眼色”划分T21为2个子集：眼色=“兰色”的子集T211=(6(P))终叶节点，标记为P眼色=“黑色”的子集T212=(2(N))终叶节点，标记为N删除属性表中第1个属性，使AttrList=（）Loop4:所有叶节点都是终叶节点，故算法成功终止。人工智能与专家系统(第二版）中国水利水电出版社图7.1例7.1由CLS算法生成的决策树人工智能与专家系统(第二版）中国水利水电出版社(2)由决策树得出产生式规则集R1：(身高=“矮”)∧(发色=“亚麻色”)∧(眼色=“兰色”)→类别=“P”R2：(身高=“矮”)∧(发色=“亚麻色”)∧(眼色=“黑色”)→类别=“N”R3：(身高=“矮”)∧(发色=“黑色”)→类别=“N”R4：(身高=“高”)∧(发色=“亚麻色”)∧(眼色=“兰色”)→类别=“P”R5：(身高=“高”)∧(发色=“亚麻色”)∧(眼色=“黑色”)→类别=“N”R6：(身高=“高”)∧(发色=“棕色”)→类别=“P”R7：(身高=“高”)∧(发色=“黑色”)→类别=“N”人工智能与专家系统(第二版）中国水利水电出版社(3)对规则集中的规则合并对后件相同的规则，可考察前件包含的条件，合并成新规则来代替原有规则。R3与R7可合并为：发色=“黑色”→类别=“N”R2与R5可合并为：(发色=“亚麻色”)∧(眼色=“黑色”)→类别=“N”R1与R4可合并为：(发色=“亚麻色”)∧(眼色=“兰色”)→类别=“P”R6：(身高=“高”)∧(发色=“棕色”)→类别=“P”人工智能与专家系统(第二版）中国水利水电出版社7.2.2．ID3算法ID3算法对属性的选择给出一种启发式搜索方法，通过计算实例集的熵来选择平均信息量最小的属性来划分实例集，扩展生成决策树。(1)初始化：输入初始学习实例，组成初始学习实例集合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个值，则将非终叶节点实例集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标记该节点；若一个子集为空集，则该子集节点也称为终叶节点，且予以删除，并删除相应的连接弧。(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:取属性表第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，其中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)=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)，7(N))终叶节点，标记为N删除属性表中的属性“发色”，AttrList=(身高，眼色)607.0083971.085))()((),()3(22)3(11TIeeTIeeTI眼色人工智能与专家系统(第二版）中国水利水电出版社Loop2:选择属性划分T1，T1的实例数e=4。当前属性表有2个属性，2个子循环分别如下。Loop21:取属性表第1个属性“身高”划分T1为2个子集：①身高=“矮”的子集T11(1)=(1