決策樹---周志華閱讀筆記

來自專欄 機器學習及NLP

決策樹

最近需要使用到相關知識，所以寫筆記自己來看看

一，基礎概念

是一個基礎的分類決策任務，我們平時所做的任何決策都是一個簡單的決策樹。而基於我們之前所做的決策做的第二步決策，就是第二級節點的決策。

簡單來說，我們會根據我們所判定的事物的屬性進行分類。我們希望可以學習到一棵泛化能力強的決策樹。

遞歸返回：

1，當前節點包含的樣本全屬於同一類別，無需劃分

2，當前屬性集為空，或者是所有樣本在所有屬性上去取值相同，無法劃分

3，當前節點包含的樣本集合為空，不能劃分

關鍵：

如何選擇最優劃分屬性。隨著劃分的不斷進行，我們希望決策樹的分支節點所包含的樣本儘可能屬於同一類別，即節點的『純度』越來越高。信息熵是度量樣本集合純度最常用的一種指標。熵越小，則純度越高。所謂信息增益，就是依據某一個屬性劃分之後，純度變高了多少，就是增益了多少。

信息增益---ID3---缺點：信息增益準則對可取值數目較多的屬性有所偏好（如何理解【1】），為了減少這種偏好可能帶來的不利影響，便有了

信息增益率---C4.5決策樹演算法---缺點：信息增益率對可取值數目較少的屬性有所偏好（與上面的相反）。因此C4.5使用啟發式：先從候選劃分屬性中選出信息增益高於平均水平的屬性，再從中選擇增益率最高的。

CART決策樹使用『基尼指數（Gini index）』來選擇劃分屬性。直觀來說，Gini（D）反映了從數據集D中隨機抽取兩個樣本，其類別標記不一致的概率。因此，Gini（D）越小，則數據集D的純度越高。於是我們使用使劃分後基尼指數最小的屬性作為最優劃分屬性，

【1】太細碎的屬性，會導致將對象分的太細碎。一個是這樣的屬性可能是獨有的（例如依據指紋對人群進行分類是不科學的），不具有泛化性（泛化性如何理解？就是訓練學習出的模型可以適用於很多未知實例）

二，如何防止過擬合

對於DT，我們有獨特的方式：剪枝處理（pruning）。這個是決策樹演算法對付過擬合的主要手段。分為預剪枝和後剪枝兩種。

前者是在劃分前先進行估計，後者是在劃分後自底向上的對非葉節點進行考察。如何判斷性能是否提升，可以使用交叉驗證【2】的方式進行檢驗。

【2】http://blog.csdn.net/holybin/article/details/27185659

三，連續屬性

對於連續屬性來說我們可以類似的計算信息增益，然後選擇使信息增益最大的值作為劃分點。需要注意的是，與離散屬性不同，若當前節點的劃分屬性為連續屬性，該屬性還可以作為其後代的劃分屬性。

四，缺失值處理

解決問題：

1，如何在屬性值缺失的情況下進行劃分屬性選擇？

2，給定劃分屬性，若樣本在該屬性上的值缺失，如何對樣本進行劃分？

五，多變數決策樹