機器學習方法與實踐 課件ID3

決策樹：ID3算法DecisionTree:IterativeDichotomiser3主講：耿陽李敖計算機與信息技術學院視覺智能實驗室（VisInt）BeijingJiaotong

University決策樹引入給定當天的天氣、溫度、濕度和風力四個屬性值，如何根據歷史數據判斷是否去打網球？決策樹引入可通過構建如下決策樹進行判斷Outlook（天氣狀況）決策樹引入可通過構建如下決策樹進行判斷Outlook（天氣狀況）Humidity（濕度）Sunny決策樹引入可通過構建如下決策樹進行判斷Outlook（天氣狀況）Humidity（濕度）SunnyHighNormalNoYes決策樹引入可通過構建如下決策樹進行判斷Outlook（天氣狀況）Humidity（濕度）SunnyHighNormalNoYesOvercastYes決策樹引入可通過構建如下決策樹進行判斷Outlook（天氣狀況）Humidity（濕度）SunnyHighNormalNoYesOvercastYesWind（風力）Rain決策樹引入可通過構建如下決策樹進行判斷Outlook（天氣狀況）Humidity（濕度）SunnyHighNormalNoYesOvercastYesWind（風力）RainStrongWeakNoYes決策樹引入可通過構建如下決策樹進行判斷Outlook（天氣狀況）Humidity（濕度）SunnyHighNormalNoYesOvercastYesWind（風力）RainStrongWeakNoYes如何根據歷史數據構建一棵決策樹？問題決策樹引入從上述構建決策樹的過程可以看出，每構建一個分支都是讓一類屬性值的不確定性降低的過程，直至建立最后的葉子結點得到確定的輸出結果不確定性熵密切相關信息熵基本概念對于具有n個取值（類別）的隨機變量（樣本集）X，X的信息熵H(X)為：

信息熵基本概念對于具有n個取值（類別）的隨機變量（樣本集）X，X的信息熵H(X)為：

信息熵的意義：衡量了樣本集的不確定性，熵越大不確定性越大

條件熵當存在兩個隨機變量X和Y時，如何在給定Y的條件下，度量X的不確定性？例如：如何在已知天氣狀況Y為晴天的情況下，求解濕度X的不確定性？條件熵基本概念當存在兩個隨機變量X和Y時，如何在給定Y的條件下，度量X的不確定性？例如：如何在已知天氣狀況Y的情況下，求解濕度X的不確定性？1.

條件概率的熵對于具有n個取值的隨機變量X，給定隨機變量Y的取值為v，在Y=v條件下的X的條件熵H(X|Y=v)為：即已知Y的具體取值條件下，X的信息熵（不確定性）2.條件熵進一步，對于具有n個取值的隨機變量X，當給定隨機變量Y時，X的條件熵H(X|Y)為：即具體的條件熵的期望信息增益當存在兩個隨機變量X和Y時，如何在給定Y的條件下，知道X的不確定性降低了多少？信息增益基本概念當存在兩個隨機變量X和Y時，如何在給定Y的條件下，知道X的不確定性降低了多少？

信息增益的意義：對于樣本集X和其中的屬性Y而言，信息增益衡量了屬性Y已知的條件下，樣本集X減少的不確定性；或使用屬性Y劃分樣本集X能提升的純度ID3算法基本概念

ID3算法示例以打網球問題為例：

ID3算法示例以打網球問題為例：

ID3算法示例以打網球問題為例：

ID3算法示例以打網球問題為例：

ID3算法示例以打網球問題為例：（5）屬性Outlook具有三個值，對于樣本子集XSunny，分別計算以屬性Temperature,Humidity和Wind劃分樣本子集XSunny的信息增益ID3算法示例以打網球問題為例：

ID3算法示例以打網球問題為例：（5）屬性Outlook具有三個值，對于樣本子集XSunny，分別計算以屬性Temperature,Humidity和Wind劃分樣本子集XSunny的信息增益

③

選擇信息增益最大的屬性Humidity作為子節點ID3算法示例以打網球問題為例：（6）同理，對于樣本子集XOvercast,XRain，分別