机器学习课后作业

机器学习课后作业 学院：电子工程学院专业：电子与通信工程姓名：叶旭庆学号3继续考虑EnjoySport学习任务和2.2节中描述的假设空间H。如果定义一个新的假设空间H´，它包含H中所有假设的成对析取。如H´中一假设为：<?,Cold,High,?,?,?>∨<Sunny,?,High,?,?,Same>试跟踪运行使用该假设空间H´的候选消除算法，给定的训练样例如表2-1所示（需要分步列出S和G集合）。答：S0=(φ,φ,φ,φ,φ,φ)v(φ,φ,φ,φ,φ,φ)G0=(?,?,?,?,?,?)v(?,?,?,?,?,?)Example1:<Sunny,Warm,Normal,Strong,Warm,Same,Yes>S1=(Sunny,Warm,Normal,Strong,Warm,Same)v(φ,φ,φ,φ,φ,φ)G1=(?,?,?,?,?,?)v(?,?,?,?,?,?)Example2:<Sunny,Warm,High,Strong,Warm,Same,Yes>S2={(Sunny,Warm,Normal,Strong,Warm,Same)v(Sunny,Warm,High,Strong,Warm,Same)，(Sunny,Warm,？,Strong,Warm,Same)v(φ,φ,φ,φ,φ,φ)}G2=(?,?,?,?,?,?)v(?,?,?,?,?,?)Example3:<Rainy,Cold,High,Strong,Warm,Change,No>S3={(Sunny,Warm,Normal,Strong,Warm,Same)v(Sunny,Warm,High,Strong,Warm,Same)，(Sunny,Warm,？,Strong,Warm,Same)v(φ,φ,φ,φ,φ,φ)}G3={(Sunny,?,?,?,?,?)v(?,Warm,?,?,?,?),(Sunny,?,?,?,?,?)v(?,?,?,?,?,Same),(?,Warm,?,?,?,?)v(?,?,?,?,?,Same)}2Example4:<Sunny,Warm,High,Strong,Cool,Change,Yes>S4={(Sunny,Warm,?,Strong,?,?)v(Sunny,Warm,High,Strong,Warm,Same)，(Sunny,Warm,Normal,Strong,Warm,Same)v(Sunny,Warm,High,Strong,?,?)，(Sunny,Warm,？,Strong,？,？)v(φ,φ,φ,φ,φ,φ)，(Sunny,Warm,？,Strong,Warm,Same)v(Sunny,Warm,High,Strong,Cool,Change)}G4={(Sunny,?,?,?,?,?)v(?,Warm,?,?,?,?),(Sunny,?,?,?,?,?)v(?,?,?,?,?,Same),(?,Warm,?,?,?,?)v(?,?,?,?,?,Same)}3.2考虑下面的训练样例集合：请计算这个训练样例集合对于目标函数分类的熵。请计算属性a2相对这些训练样例的信息增益。答：3.4ID3仅寻找一个一致的假设，而候选消除算法寻找所有一致的假设。考虑这两种学习算法间的对应关系。（a）假定给定EnjoySport的四个训练样例，画出ID3学习的决策树。其中EnjoySport目标概念列在第2章的表2-1中。（b）学习到的决策树和从同样的样例使用变型空间算法得到的变型空间（见第2章图2-3）间有什么关系？树等价于变型空间的一个成员吗？（c）增加下面的训练样例，计算新的决策树。这一次，显示出增长树的每一步中每个候选属性的信息增益。（d）假定我们希望设计一个学习器，它搜索决策树假设空间（类似ID3）并寻找与数据一致的所有假设（类似候选消除）。简单地说，我们希望应用候选消除算法搜索决策树假设空间。写出经过表2-1的第一个训练样例后的S和G集合。注意S必须包含与数据一致的最特殊的决策树，而G必须包含最一般的。说明遇到第二个训练样例时S和G集合是如何被改进的（可以去掉描述同一个概念的语法不同的树）。在把候选消除算法应用到决策树假设空间时，预计会碰到什么样的困难？答：（a）解：要画决策树，需要计算每个候选属性相对于整个样例集合S的信息增益，然后选择信息增益最高的一个属性作为树节点上第一个被测试的属性。Gain(S,Sky)=0.8113Gain(S,AirTemp)=0.8113Gain(S,Humidity)=0.1226Gain(S,Wind)=0Gain(S,Water)=0.1226Gain(S,Forecast)=0.3113(b)（1）学习到的决策树只包含一个与训练样例一致的假设，使用变型空间算法得到的变型空间包含了所有与训练样例一致的假设，但变型空间只含各属性合取式的集合，如果目标函数不在假设空间中，即合取连接词不能表示最小的子式时，变型空间将会是空的。在本例中，学习到的决策树“Sky=Sunny”与变型空间中的G集合中的假设<Sunny,?,?,?,?,?>等价，“Air-Temp=Warm”与G中的<?,Warm,?,?,?,?>等价。学习到的决策树是用变型空间算法得到的变型空间是一种包含关系，前者是后者的子集或者说是后者的一个元素，（2）在此例子中决策树等价于变型空间的一个成员，但是一般情况的决策树并不一定等价于变型空间中的一个成员，因为决策树的判别有顺序，而假设空间中的元素的各个性质没有顺序(c)Gain(S,Sky)=0.3219Gain(S,AirTemp)=0.3219Gain(S,Humidity)=0.0200Gain(S,Wind)=0.3219Gain(S,Water)=0.1710Gain(S,Forecast)=0.0200显然第一个属性应该选择SkyAirTempWind若第一个属性为Sky则：Gain(Ssunny,AirTemp)=0Gain(Ssunny,Humidity)=0.3113Gain(Ssunny,Wind)=0.8113(最大)Gain(Ssunny,Water)=0.1226Gain(Ssunny,Forecast)=0.1226若第一个属性为AirTemp则：Gain(Swarm,Sky)=0Gain(Swarm,Humidity)=0.3113Gain(Swarm,Wind)=0.8113(最大)Gain(Swarm,Water)=0.1226Gain(Swarm,Forecast)=0.1226若第一个属性为Wind则：Gain(Sstrony,Sky)=0.8113(最大)Gain(Sstrony,AirTemp)=0.8113(最大)Gain(Sstrony,Humidity)=0.1226Gain(Sstrony,Water)=0.1226Gain(Sstrony,Forecast)=0.3113Entropy(S)=-(3/5)log(3/5)(2/5)log(2/5)=0.9710所有六个属性的信息增益为：Gain(S,Sky)=Entropy(S)-4/5*((1/4)log(1/4)(3/4)log(3/4))1/5*log1=0.9710—0.6490=0.3220Gain(S,Air-Temp)=Entropy(S)-4/5*((1/4)log(1/4)(3/4)log(3/4))1/5*log1=0.9710—0.6490=0.3220Gain(S,Humidity)=Entropy(S)-2/5*(1/2*log(1/2)*2)3/5*(2/3*log(2/3)13*log(1/3))=0.9710—0.9510=0.0200Gain(S,Wind)=Entropy(S)-4/5*(1/4*log(1/4)3/4*log(3/4))1/5*log1=0.9710—0.6490=0.3220Gain(S,Warm)=Entropy(S)-4/5*(2/4*log(2/4)2/4*log(2/4))1/5*log1=0.9710—0.8000=0.1710Gain(S,Forecast)=Entropy(S)-2/5*(1/2*log(1/2)*2)3/5*(2/3*log(2/3)1/3*log(1/3))=0.9710—0.9510=0.0200选择Sky，Air-Temp，Wind中的任何一个作为根节点的决策属性即可，这里选择Sky作为根节点的决策属性，建立决策树如下：计算下一步的信息增益如下：Entropy(Sunny)=-(1/4)log(1/4)(3/4)log(3/4)=0.8113Gain(Sunny,Air-Temp)=Entropy(Sunny)-(1/4*log(1/4)3/4*log(3/4))=0Gain(Sunny,Humidity)=Entropy(S)-2/4*(1/2*log(1/2)*2)2/4*log1=0.8113—0.5000=0.3113Gain(Sunny,Wind)=Entropy(S)-3/4*log1-1/4*log1=0.8113Gain(Sunny,Water)=Entropy(S)-3/4*(1/3*log(1/3)2/3*log(3))1/4*log1=0.8113—0.6887=0.1226Gain(Sunny,Forecast)=Entropy(S)-3/4*(1/3*log(1/3)2/3*log(3))1/4*log1=0.8113—0.6887=0.1226由于Gain(Sunny,Wind)最大，选择Wind做为新的叶子节点，建立决策树如下：至此，已用完所有的训练样例，决策树建立完毕。（d）经过表2-1的第一个训练样例后的S和G如下：S1：G1:?表示对所有例子都接受为正例当遇到第二个训练样例：<Sunny，Warm，High，Strong，Warm，Same>，EnjoySport=YesS2：G2:?表示对所有例子都接受为正例在把候选消除算法应用到决策树假设空间时，预计会遇到如下四种困难：（1）在把候选消除算法应用到决策树假设空间时，如果目标函数不在假设空间时，侯选消除算法得到的变型空间是空的，或者当遇到含有噪声的数据时，候选消除算法也可能出现空集合，而如果用ID3建立决策树则不会出现这种情况。