一、決策樹原理

決策樹是用樣本的屬性作為結點，用屬性的取值作為分支的樹結構。
決策樹的根結點是所有樣本中信息量最大的屬性。樹的中間結點是該結點為根的子樹所包含的樣本子集中信息量最大的屬性。決策樹的葉結點是樣本的類別值。決策樹是一種知識表示形式，它是對所有樣本數據的高度概括決策樹能準確地識別所有樣本的類別，也能有效地識別新樣本的類別。 

決策樹算法ID3的基本思想：

首先找出最有判別力的屬性，把樣例分成多個子集，每個子集又選擇最有判別力的屬性進行劃分，一直進行到所有子集僅包含同一類型的數據為止。最后得到一棵決策樹。

J.R.Quinlan的工作主要是引進了信息論中的信息增益，他將其稱為信息增益（information gain），作為屬性判別能力的度量，設計了構造決策樹的遞歸算法。

舉例子比較容易理解：

對于氣候分類問題，屬性為:
天氣(A1) 取值為： 晴，多云，雨
氣溫(A2)  取值為： 冷 ，適中，熱
濕度(A3)  取值為： 高 ，正常
風 (A4)  取值為： 有風， 無風

每個樣例屬于不同的類別，此例僅有兩個類別，分別為P，N。P類和N類的樣例分別稱為正例和反例。將一些已知的正例和反例放在一起便得到訓練集。
由ID3算法得出一棵正確分類訓練集中每個樣例的決策樹，見下圖。

決策樹葉子為類別名，即P 或者N。其它結點由樣例的屬性組成，每個屬性的不同取值對應一分枝。
若要對一樣例分類，從樹根開始進行測試，按屬性的取值分枝向下進入下層結點，對該結點進行測試，過程一直進行到葉結點，樣例被判為屬于該葉結點所標記的類別。
現用圖來判一個具體例子，
某天早晨氣候描述為:
天氣：多云
氣溫：冷
濕度：正常
風： 無風

它屬于哪類氣候呢?-------------從圖中可判別該樣例的類別為P類。 

ID3就是要從表的訓練集構造圖這樣的決策樹。實際上，能正確分類訓練集的決策樹不止一棵。Quinlan的ID3算法能得出結點最少的決策樹。

ID3算法：

     1. 對當前例子集合，計算各屬性的信息增益；
     2. 選擇信息增益最大的屬性Ak；
     3. 把在Ak處取值相同的例子歸于同一子集，Ak取幾個值就得幾個子集；
     4.對既含正例又含反例的子集，遞歸調用建樹算法；
     5. 若子集僅含正例或反例，對應分枝標上P或N，返回調用處。