決策樹之ID3算法及其Python實現，具體內容如下

主要內容

決策樹背景知識
決策樹一般構建過程
ID3算法分裂屬性的選擇
ID3算法流程及其優缺點分析
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)