決策樹之ID3算法及其Python實現

1. 決策樹背景知識
??決策樹是數據挖掘中最重要且最常用的方法之一，主要應用于數據挖掘中的分類和預測。決策樹是知識的一種呈現方式，決策樹中從頂點到每個結點的路徑都是一條分類規則。決策樹算法最先基于信息論發展起來，經過幾十年發展，目前常用的算法有：ID3、C4.5、CART算法等。

2. 決策樹一般構建過程
??構建決策樹是一個自頂向下的過程。樹的生長過程是一個不斷把數據進行切分細分的過程，每一次切分都會產生一個數據子集對應的節點。從包含所有數據的根節點開始，根據選取分裂屬性的屬性值把訓練集劃分成不同的數據子集，生成由每個訓練數據子集對應新的非葉子節點。對生成的非葉子節點再重復以上過程，直到滿足特定的終止條件，停止對數據子集劃分，生成數據子集對應的葉子節點，即所需類別。測試集在決策樹構建完成后檢驗其性能。如果性能不達標，我們需要對決策樹算法進行改善，直到達到預期的性能指標。
??注：分裂屬性的選取是決策樹生產過程中的關鍵，它決定了生成的決策樹的性能、結構。分裂屬性選擇的評判標準是決策樹算法之間的根本區別。

3. ID3算法分裂屬性的選擇——信息增益
??屬性的選擇是決策樹算法中的核心。是對決策樹的結構、性能起到決定性的作用。ID3算法基于信息增益的分裂屬性選擇?；谛畔⒃鲆娴膶傩赃x擇是指以信息熵的下降速度作為選擇屬性的方法。它以的信息論為基礎，選擇具有最高信息增益的屬性作為當前節點的分裂屬性。選擇該屬性作為分裂屬性后，使得分裂后的樣本的信息量最大，不確定性最小，即熵最小。
??信息增益的定義為變化前后熵的差值，而熵的定義為信息的期望值，因此在了解熵和信息增益之前，我們需要了解信息的定義。
??信息：分類標簽xi 在樣本集 S 中出現的頻率記為 p(xi)，則 xi 的信息定義為：?log2p(xi) 。
??分裂之前樣本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 為分類標簽的個數。
??通過屬性A分裂之后樣本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始樣本集通過屬性A的屬性值劃分為 m 個子樣本集，|Sj| 表示第j個子樣本集中樣本數量，|S| 表示分裂之前數據集中樣本總數量。
??通過屬性A分裂之后樣本集的信息增益：InfoGain(S,A)=E(S)?EA(S)
??注：分裂屬性的選擇標準為：分裂前后信息增益越大越好，即分裂后的熵越小越好。

4. ID3算法
??ID3算法是一種基于信息增益屬性選擇的決策樹學習方法。核心思想是：通過計算屬性的信息增益來選擇決策樹各級節點上的分裂屬性，使得在每一個非葉子節點進行測試時，獲得關于被測試樣本最大的類別信息?；痉椒ㄊ牵河嬎闼械膶傩?，選擇信息增益最大的屬性分裂產生決策樹節點，基于該屬性的不同屬性值建立各分支，再對各分支的子集遞歸調用該方法建立子節點的分支，直到所有子集僅包括同一類別或沒有可分裂的屬性為止。由此得到一棵決策樹，可用來對新樣本數據進行分類。

ID3算法流程：
(1) 創建一個初始節點。如果該節點中的樣本都在同一類別，則算法終止，把該節點標記為葉節點，并用該類別標記。
(2) 否則，依據算法選取信息增益最大的屬性，該屬性作為該節點的分裂屬性。
(3) 對該分裂屬性中的每一個值，延伸相應的一個分支，并依據屬性值劃分樣本。
(4) 使用同樣的過程，自頂向下的遞歸，直到滿足下面三個條件中的一個時就停止遞歸。
??A、待分裂節點的所有樣本同屬于一類。
??B、訓練樣本集中所有樣本均完成分類。
??C、所有屬性均被作為分裂屬性執行一次。若此時，葉子結點中仍有屬于不同類別的樣本時，選取葉子結點中包含樣本最多的類別，作為該葉子結點的分類。

ID3算法優缺點分析
優點：構建決策樹的速度比較快，算法實現簡單，生成的規則容易理解。
缺點：在屬性選擇時，傾向于選擇那些擁有多個屬性值的屬性作為分裂屬性，而這些屬性不一定是最佳分裂屬性；不能處理屬性值連續的屬性；無修剪過程，無法對決策樹進行優化，生成的決策樹可能存在過度擬合的情況。