很早之前學習的決策樹寫一下，作為學習記錄。
決策樹
決策樹學習是應用最廣的歸納推理算法之一。 用逼近離散值函數的方法，對有噪聲的資料處理，健壯性好，并且能夠學習析取表達式。
決策樹的學習算法很多，包括ID3, ASSISTANT, C4.5 這些。
學習到的決策樹可以表示為多個if-then的規則。
決策樹的适應問題
- 執行個體是由『屬性-值』對表示的，例如：( Temperature -> Hot ) 這樣的。
- 目标函數具有離散的輸出值， 例如一個執行個體有bool分類為( yes , no )，這樣就很容易擴充為兩個以上的輸出值函數。
- 可能需要析取的描述，這個就是說，決策樹代表的析取表達式。
- 訓練資料可以包含錯誤，因為決策樹對錯誤資料的健壯性很好，是以容錯率高。
ID3算法
ID3 ( Examples, Target_attribute, Attributes )
Examples 是訓練樣集。Target_attribute是這棵樹要預測的目标屬性。Attributes是除目标屬性外功學習到的句冊數測試的屬性清單。
- 建立樹的Root節點
- 如果Examples都為正，那麼傳回label = + 的單節點樹Root
- 如果Examples都為反，那麼傳回label = - 的單節點樹Root
如果Attributes為空，那麼傳回單節點樹Root, label = Examples 中最普遍的Target_attribute值。
5.否則開始：
5.1 A<- Attributes 中分類Examples能力最好的屬性
5.2 Root決策屬性 <- A
5.3 對于A的每個可能的值V_i
5.3.1 在Root下加一個新的分支對應測試A = V_i
5.3.2 令Examples(V_i)為Examples中滿足A屬性值為V_i的子集
5.3.3 如果Examples(V_i)為空
5.3.3.1 在這個新分支下加一個葉子節點，節點的label = Examples中最普遍的Target_attribute值
5.3.3.2 否則在這個新分支下加一個子樹ID3 ( Examples(V_i), Target_attribute, Attributes-{A} )
- 結束
- 傳回root
這裡最重要的是找到：最高資訊增益 ( information gain ) 的屬性是最好的屬性
用熵來衡量
為了精确定義上面說的資訊增益，這裡使用熵來衡量資訊增益的程度：
其中P+是S中的正例占的比例，P-是S中的反例占的比例。Entropy是表示熵。其中 0log0 = 0.
假設Entropy([9 +, 5 -]) = -(9/14)log(9/14) - (5/14)log(5/15) = 0.940
這是bool型的熵函數，假如更一般的情況，S有c個狀态。熵定義為：
這裡P_i代表狀态為i所占的比例。
我自己的了解是：ID3算法就是用來構造整個決策樹，來決定每個屬性所在決策樹的位置。
優勢和不足
- ID3算法中的假設空間包含所有的決策樹，關于現有屬性的有限離散值函數的一個完整空間。
- 當周遊決策樹空間時，ID3僅僅維護單一的目前假設。例如：它不能判斷有多少個其他的決策樹也是與現有的訓練資料一緻的。
- 基本的ID3算法在搜尋中不進行回溯。就是說假如在某一個層次選擇了一個屬性，那麼就不會再回溯重新考慮這個選擇了。
- ID3算法在搜尋的每一步都使用目前的所有訓練樣例，以統計為基礎決定怎樣精化目前的假設。
決策樹學習的歸納偏置
我的了解就是：1. 選擇較短的樹。 2. 選擇資訊增益高的屬性，讓它離根節點更近的樹。
其實就是從一個空的樹，進行廣度優先周遊搜尋，考慮所有深度為1的，然後2的。。。
決策樹學習方法的問題
其實在決策樹學習的這個算法中，實際問題有很多的，例如：
- 确定決策樹的增長的深度；
- 處理連續值的屬性；
- 選擇一個适當的屬性篩選度量标準；
- 處理屬性值不完整的訓練資料；
- 處理不同代價的屬性；
- 提高計算效率；
避免過度拟合資料
這裡有個問題，就是我們訓練資料的政策并不是一定能行得通的！就是說資料中有噪聲或者數量不太多的情況，不能産生目标函數有代表性的采樣，那麼這個政策就很麻煩了。這種情況有有可能過度拟合。
就是說在假設空間裡h的錯誤率小于H的，但是在整個執行個體上，H錯誤率更小，那麼就是過度拟合了。
機器學習書上的定義：
給定一個假設空間H，一個假設h 屬于 H,如果存在其他假設h’ 屬于H， 使得訓練樣例上h 的錯誤率小于h’，但是在整個執行個體的分布上h’的錯誤率小于h，那麼就是假設h過度拟合訓練資料了。
原因比較多啊，就是有可能是有噪聲（沒噪聲的資料太少了…）還有就是有可能資料裡有錯誤資料啊，或者資料少沒法完全代表整個執行個體。就像抛硬币一樣，抛10次 100次 1000次 10萬次的資料分布的代表性是不一樣的。
那麼如何避免呢？
- 早點停止樹的增長，就是在完美分類資料之前就停止樹的增長。
- 後修剪法，就是把樹後面的資料修剪掉。
這裡面涉及到一個問題！那就是度的問題，什麼時候停止，修剪掉多少。
- 使用訓練樣例不同的分離陽曆，評估通過上面兩個方法的效用。類似評估函數。
- 使用所有可用資料訓練。
- 或者訂一個明确的标準衡量複雜度。
方法比較麻煩~~有時間再寫吧。
結語
為什麼我先寫決策樹呢，因為這個是用的比較多的，而且難度不大~~ 多交流