機(jī)器學(xué)習(xí)課后作業(yè) 學(xué)院：電子工程學(xué)院專業(yè)：電子與通信工程姓名：葉旭慶學(xué)號3繼續(xù)考慮EnjoySport學(xué)習(xí)任務(wù)和2.2節(jié)中描述的假設(shè)空間H。如果定義一個新的假設(shè)空間H′，它包含H中所有假設(shè)的成對析取。如H′中一假設(shè)為：<?,Cold,High,?,?,?>∨<Sunny,?,High,?,?,Same>試跟蹤運(yùn)行使用該假設(shè)空間H′的候選消除算法，給定的訓(xùn)練樣例如表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考慮下面的訓(xùn)練樣例集合：請計(jì)算這個訓(xùn)練樣例集合對于目標(biāo)函數(shù)分類的熵。請計(jì)算屬性a2相對這些訓(xùn)練樣例的信息增益。答：3.4ID3僅尋找一個一致的假設(shè)，而候選消除算法尋找所有一致的假設(shè)。考慮這兩種學(xué)習(xí)算法間的對應(yīng)關(guān)系。（a）假定給定EnjoySport的四個訓(xùn)練樣例，畫出ID3學(xué)習(xí)的決策樹。其中EnjoySport目標(biāo)概念列在第2章的表2-1中。（b）學(xué)習(xí)到的決策樹和從同樣的樣例使用變型空間算法得到的變型空間（見第2章圖2-3）間有什么關(guān)系？樹等價(jià)于變型空間的一個成員嗎？（c）增加下面的訓(xùn)練樣例，計(jì)算新的決策樹。這一次，顯示出增長樹的每一步中每個候選屬性的信息增益。（d）假定我們希望設(shè)計(jì)一個學(xué)習(xí)器，它搜索決策樹假設(shè)空間（類似ID3）并尋找與數(shù)據(jù)一致的所有假設(shè)（類似候選消除）。簡單地說，我們希望應(yīng)用候選消除算法搜索決策樹假設(shè)空間。寫出經(jīng)過表2-1的第一個訓(xùn)練樣例后的S和G集合。注意S必須包含與數(shù)據(jù)一致的最特殊的決策樹，而G必須包含最一般的。說明遇到第二個訓(xùn)練樣例時(shí)S和G集合是如何被改進(jìn)的（可以去掉描述同一個概念的語法不同的樹）。在把候選消除算法應(yīng)用到?jīng)Q策樹假設(shè)空間時(shí)，預(yù)計(jì)會碰到什么樣的困難？答：（a）解：要畫決策樹，需要計(jì)算每個候選屬性相對于整個樣例集合S的信息增益，然后選擇信息增益最高的一個屬性作為樹節(jié)點(diǎn)上第一個被測試的屬性。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）學(xué)習(xí)到的決策樹只包含一個與訓(xùn)練樣例一致的假設(shè)，使用變型空間算法得到的變型空間包含了所有與訓(xùn)練樣例一致的假設(shè)，但變型空間只含各屬性合取式的集合，如果目標(biāo)函數(shù)不在假設(shè)空間中，即合取連接詞不能表示最小的子式時(shí)，變型空間將會是空的。在本例中，學(xué)習(xí)到的決策樹“Sky=Sunny”與變型空間中的G集合中的假設(shè)<Sunny,?,?,?,?,?>等價(jià)，“Air-Temp=Warm”與G中的<?,Warm,?,?,?,?>等價(jià)。學(xué)習(xí)到的決策樹是用變型空間算法得到的變型空間是一種包含關(guān)系，前者是后者的子集或者說是后者的一個元素，（2）在此例子中決策樹等價(jià)于變型空間的一個成員，但是一般情況的決策樹并不一定等價(jià)于變型空間中的一個成員，因?yàn)闆Q策樹的判別有順序，而假設(shè)空間中的元素的各個性質(zhì)沒有順序(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顯然第一個屬性應(yīng)該選擇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中的任何一個作為根節(jié)點(diǎn)的決策屬性即可，這里選擇Sky作為根節(jié)點(diǎn)的決策屬性，建立決策樹如下：計(jì)算下一步的信息增益如下：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做為新的葉子節(jié)點(diǎn)，建立決策樹如下：至此，已用完所有的訓(xùn)練樣例，決策樹建立完畢。（d）經(jīng)過表2-1的第一個訓(xùn)練樣例后的S和G如下：S1：G1:?表示對所有例子都接受為正例當(dāng)遇到第二個訓(xùn)練樣例：<Sunny，Warm，High，Strong，Warm，Same>，EnjoySport=YesS2：G2:?表示對所有例子都接受為正例在把候選消除算法應(yīng)用到?jīng)Q策樹假設(shè)空間時(shí)，預(yù)計(jì)會遇到如下四種困難：（1）在把候選消除算法應(yīng)用到?jīng)Q策樹假設(shè)空間時(shí)，如果目標(biāo)函數(shù)不在假設(shè)空間時(shí)，侯選消除算法得到的變型空間是空的，或者當(dāng)遇到含有噪聲的數(shù)據(jù)時(shí)，候選消除算法也可能出現(xiàn)空集合，而如果用ID3建立決策樹則不會出現(xiàn)這種情況。