搜索
1第7章机器学习参考答案7-6设训练例子集如下表所示：序号属性分类x1x21TT+2TT+3TF-4FF+5FT_6FT_请用ID3算法完成其学习过程。解：设根节点为S，尽管它包含了所有的训练例子，但却没有包含任何分类信息，因此具有最大的信息熵。即：H(S)=-(P(+)log2P(+)+P(-)log2P(-))式中P(+)=3/6，P(-)=3/6分别是决策方案为“+”或“-”时的概率。因此有H(S)=-((3/6)log2(3/6)+(3/6)log2(3/6))=1按照ID3算法，需要选择一个能使S的期望熵为最小的一个属性对根节点进行扩展，因此我们需要先计算S关于每个属性的条件熵：H(S|xi)=(|ST|/|S|)*H(ST)+(|SF|/|S|)*H(SF)其中，T和F为属性xi的属性值，ST和SF分别为xi=T或xi=F时的例子集，|S|、|ST|和|SF|分别为例子集S、ST和SF的大小。下面先计算S关于属性x1的条件熵：在本题中，当x1=T时，有：ST={1，2，3}当x1=F时，有：SF={4，5，6}其中，ST和SF中的数字均为例子集S中的各个例子的序号，且有|S|=6，|ST|=|SF|=3。由ST可知，其决策方案为“+”或“-”的概率分别是：PST(+)=2/3PST(-)=1/3因此有：H(ST)=-(PST(+)log2PST(+)+PST(-)log2PST(-))2=-((2/3)log2(2/3)+(1/3)log2(1/3))=0.9183再由SF可知，其决策方案为“+”或“-”的概率分别是：PSF(+)=1/3PSF(-)=2/3则有：H(SF)=-(PSF(+)log2PSF(+)+PSF(-)log2PSF(-))=-((1/3)log2(1/3)+(2/3)log2(2/3))=0.9183将H(ST)和H(SF)代入条件熵公式，有：H(S|x1)=(|ST|/|S|)H(ST)+(|SF|/|S|)H(SF)=(3/6)﹡0.9183+(3/6)﹡0.9183=0.9183下面再计算S关于属性x2的条件熵：在本题中，当x2=T时，有：ST={1，2，5，6}当x2=F时，有：SF={3，4}其中，ST和SF中的数字均为例子集S中的各个例子的序号，且有|S|=6，|ST|=4，|SF|=2。由ST可知：PST(+)=2/4PST(-)=2/4则有：H(ST)=-(PST(+)log2PST(+)+PST(-)log2PST(-))=-((2/4)log2(2/4)+(2/4)log2(2/4))=1再由SF可知：PSF(+)=1/2PSF(-)=1/2则有：H(SF)=-(P(+)log2P(+)+P(-)log2P(-))=-((1/2)log2(1/2)+(1/2)log2(1/2))=1将H(ST)和H(SF)代入条件熵公式，有：H(S|x2)=(|ST|/|S|)H(ST)+(|SF|/|S|)H(SF)=(4/6)﹡1+(2/6)﹡1=1可见，应该选择属性x1对根节点进行扩展。用x1对S扩展后所得到的部分决策树如下图所示。3在该决策树中，其2个叶节点均不是最终决策方案，因此还需要继续扩展。而要继续扩展，只有属性x2可选择，因此不需要再进行条件熵的计算，可直接对属性x2进行扩展。对x2扩展后所得到的决策树如下图所示：7-9假设w1(0)=0.2,w2(0)=0.4,θ(0)=0.3,η=0.4，请用单层感知器完成逻辑或运算的学习过程。解：根据“或”运算的逻辑关系，可将问题转换为：输入向量：X1=[0,0,1,1]X2=[0,1,0,1]输出向量：Y=[0,1,1,1]由题意可知，初始连接权值、阈值，以及增益因子的取值分别为：w1(0)=0.2,w2(0)=0.4,θ(0)=0.3，η=0.4即其输入向量X(0)和连接权值向量W(0)可分别表示为：X(0)=(-1,x1(0),x2(0))W(0)=(θ(0),w1(0),w2(0))根据单层感知起学习算法，其学习过程如下：设感知器的两个输入为x1(0)=0和x2(0)=0，其期望输出为d(0)=0，实际输出为：y(0)=f(w1(0)x1(0)+w2(0)x2(0)-θ(0))=f(0.2*0+0.4*0-0.3)=f(-0.3)=0实际输出与期望输出相同，不需要调节权值。再取下一组输入：x1(0)=0和x2(0)=1，其期望输出为d(0)=1，实际输出为：y(0)=f(w1(0)x1(0)+w2(0)x2(0)-θ(0))=f(0.2*0+0.4*1-0.3)=f(0.1)=1实际输出与期望输出相同，不需要调节权值。再取下一组输入：x1(0)=1和x2(0)=0，其期望输出为d(0)=1，实际输出为：S(+,+,-)(+,-,-)x1=Tx2=F扩展x2后得到的完整决策树(+,+)(-)(-,-)(+)x2=Tx2=Fx2=Tx2=FS(+,+,-)(+,-,-)x1=Tx1=F扩展x1后的部分决策树4y(0)=f(w1(0)x1(0)+w2(0)x2(0)-θ(0))=f(0.2*1+0.4*0-0.3)=f(-0.1)=0实际输出与期望输出不同，需要调节权值，其调整如下：θ(1)=θ(0)+η(d(0)-y(0))*(-1)=0.3+0.4*(1-0)*(-1)=-0.1w1(1)=w1(0)+η(d(0)-y(0))x1(0)=0.2+0.4*(1-0)*1=0.6w2(1)=w2(0)+η(d(0)-y(0))x2(0)=0.4+0.4*(1-0)*0=0.4再取下一组输入：x1(1)=1和x2(1)=1，其期望输出为d(1)=1，实际输出为：y(1)=f(w1(1)x1(1)+w2(1)x2(1)-θ(1))=f(0.6*1+0.4*1+0.1)=f(1.1)=1实际输出与期望输出相同，不需要调节权值。再取下一组输入：x1(1)=0和x2(1)=0，其期望输出为d(0)=0，实际输出为：y(1)=f(w1(1)x1(1)+w2(1)x2(1)-θ(1))=f(0.6*0+0.4*0+0.1)=f(0.1)=1实际输出与期望输出不同，需要调节权值，其调整如下：θ(2)=θ(1)+η(d(1)-y(1))*(-1)=-0.1+0.4*(0-1)*(-1)=0.3w1(2)=w1(1)+η(d(1)-y(1))x1(1)=0.6+0.4*(0-1)*0=0.6w2(2)=w2(1)+η(d(1)-y(1))x2(1)=0.4+0.4*(0-1)*0=0.4再取下一组输入：x1(2)=0和x2(2)=1，其期望输出为d(2)=1，实际输出为：y(2)=f(w1(2)x1(2)+w2(2)x2(2)-θ(2))=f(0.6*0+0.4*1-0.3)=f(0.1)=1实际输出与期望输出相同，不需要调节权值。再取下一组输入：x1(2)=1和x2(2)=0，其期望输出为d(2)=1，实际输出为：y(2)=f(w1(2)x1(2)+w2(2)x2(2)-θ(2))=f(0.6*1+0.4*0-0.3)=f(0.3)=1实际输出与期望输出相同，不需要调节权值。再取下一组输入：x1(2)=1和x2(2)=1，其期望输出为d(2)=1，实际输出为：y(2)=f(w1(2)x1(2)+w2(2)x2(2)-θ(2))=f(0.6*1+0.4*1-0.3)=f(0.7)=1实际输出与期望输出相同，不需要调节权值。至此，学习过程结束。最后的得到的阈值和连接权值分别为：θ(2)=0.3w1(2)=0.6w2(2)=0.4不仿验证如下：对输入：“00”有y=f(0.6*0+0.4*0-0.3)=f(-0.3)=0对输入：“01”有y=f(0.6*0+0.4*1-0.3)=f(0.1)=1对输入：“10”有y=f(0.6*1+0.4*0-0.3)=f(0.3)=1对输入：“11”有y=f(0.6*1+0.4*1-0.3)=f(0.7)=1