決策樹和隨機森林學習筆記-歡迎補充

編者：以下資料來源於網路高質量博客，編者只是摘錄精華再加上自己的理解進行補充。

決策樹-基礎概念

信息熵（熵、聯合熵、條件熵、互信息）

「熵」是什麼？ 怎樣以簡單易懂的方式向其他人解釋？

演算法的思想

基本思想是以信息熵為度量構造一棵熵值下降最快的樹，到葉子節點處的熵值為零，此時每個葉節點中的實例都屬於同一類。

ID3演算法的核心思想就是以信息增益度量屬性選擇，選擇分裂後信息增益最大（我理解為信息熵-不確定性減小最快）的屬性進行分裂。

什麼是信息增益？

信息增益表示得知特徵A的信息而使得類X的信息的不確定性減少的程度。

設D為用類別對訓練元組進行的劃分，則D的熵（entropy）表示為：

其中pi表示第i個類別在整個訓練元組中出現的概率，可以用屬於此類別元素的數量除以訓練元組元素總數量作為估計。

熵的實際意義表示是D中元組的類標號所需要的平均信息量（怎麼理解？）

現在我們假設將訓練元組D按屬性A進行劃分，則A對D劃分的期望信息為：

上圖公式中v是什麼？為什麼這麼定義？

而信息增益即為兩者的差值：

ID3演算法就是在每次需要分裂時，計算每個屬性的增益率，然後選擇增益率最大的屬性進行分裂。

————

特徵A給定條件下D的經驗條件熵H(D|A)，gain（L）

根據下文畫紅線的公式算的，日誌密度Ll（3個yes，0個no）,m（3個yes，1個no）,s（2個yes，1個no）

因此日誌密度的信息增益是0.276。

用同樣方法得到H和F的信息增益分別為0.033和0.553。

因為好友密度F具有最大的信息增益，所以第一次分裂選擇F為分裂屬性，分裂後的結果如下圖表示：

ID3演算法存在一個問題，就是偏向於多值屬性，例如，如果存在唯一標識屬性ID，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。ID3的後繼演算法C4.5使用增益率（gain ratio）的信息增益擴充，試圖克服這個偏倚。

C4.5演算法首先定義了「分裂信息」，其定義可以表示成：

其中各符號意義與ID3演算法相同，然後，增益率被定義為：

C4.5選擇具有最大增益率的屬性作為分裂屬性，其具體應用與ID3類似，不再贅述。

------參考資料-------

演算法雜貨鋪--分類演算法之決策樹(Decision tree)（開篇例子舉得不錯，演算法講的不詳細）

程序猿風格的博客（演算法流程圖&&代碼）

決策樹--從原理到實現 - DarkScope從這裡開始 - 博客頻道 - CSDN.NET

------數學公式補充--

條件熵的定義式

(X,Y)發生所包含的熵，減去X單獨發生包含的熵

理解成：在X發生的前提下，Y發生「新」帶來的熵

--------------------------

假設現在市場上有100個量化工具作為訓練數據集，這些量化工具已經被貼上了「可用」和「不可用」的標籤。

我們首先嘗試通過「API是否易用」將數據集分為兩類；發現有90個量化工具的API是好用的，10個量化工具的API是不好用的。而這90個量化工具中，被貼上「可以使用」標籤的佔了40個，「不可以使用」標籤的佔了50個，那麼，通過「API是否易用」對於數據的分類效果並不是特別好。因為，給你一個新的量化工具，即使它的API是易用的，你還是不能很好貼上「使用」的標籤。

再假設，同樣的100個量化工具，通過「是否支持模擬交易」可以將數據集分為兩類，其中一類有40個量化工具數據，這40個量化工具都支持模擬交易，都最終被貼上了「使用」的標籤，另一類有60個量化工具，都不支持模擬交易，也都最終被貼上了「不使用」的標籤。如果一個新的量化工具支持模擬交易，你就能判斷這個量化工具是可以使用。我們認為，通過「是否支持模擬交易」對於數據的分類效果就很好。

在現實應用中，數據集往往不能達到上述「是否支持模擬交易」的分類效果。所以我們用不同的準則衡量特徵的貢獻程度。主流準則的列舉3個：ID3演算法（J. Ross Quinlan於1986年提出），採用信息增益最大的特徵；C4.5演算法（J. Ross Quinlan於1993年提出）採用信息增益比選擇特徵；CART演算法（Breiman等人於1984年提出）利用基尼指數最小化準則進行特徵選擇。

（這三種演算法，有什麼區別，我還沒理解。先應用著，歡迎補充）

（如果想進行更深一步的學習，可以參考《統計學習方法》或者相關博文進行更一步的學習。未來的量化課堂也會涉及這方面的內容。）

【數學】隨機森林入門 - 知乎專欄

隨機森林

機器學習中的演算法——決策樹模型組合之隨機森林與GBDT

http://www.36dsj.com/archives/21036

Bagging與Boosting這兩種集成演算法主要區別在於「加沒加權」。Bagging的訓練集是隨機生成，分類器相互獨立；而Boosting的分類器是迭代生成，更關註上一輪的錯分元組。因此Bagging的各個預測函數可以並行生成；而Boosting只能順序生成。因此對於像一些比較耗時的分類器訓練演算法（如神經網路等）如果使用Bagging可以極大地解約時間開銷。

（Boosting怎麼加權的？是在投票的時候？還是在生成訓練集的時候，歡迎補充）

但是通過在大多數數據集的實驗，Boosting的準確率多數會高於Bagging，但是也有極個別數據集使用Boosting反倒會退化。

模式識別與機器學習-bagging與boosting - 知乎專欄

隨機森林的優點與缺點

優點：

1.隨機森林演算法能解決分類與回歸兩種類型的問題，並在這兩個方面都有相當好的估計表現；

2.隨機森林對於高維數據集的處理能力令人興奮，它可以處理成千上萬的輸入變數，並確定最重要的變數，因此被認為是一個不錯的降維方法。此外，該模型能夠輸出變數的重要性程度，這是一個非常便利的功能。

3.在對缺失數據進行估計時，隨機森林是一個十分有效的方法。就算存在大量的數據缺失，隨機森林也能較好地保持精確性。

哪裡有例子？

4.當存在分類不平衡的情況時，隨機森林能夠提供平衡數據集誤差的有效方法；（為什麼？）

5.模型的上述性能可以被擴展運用到未標記的數據集中，用於引導無監督聚類、數據透視和異常檢測；

6.隨機森林演算法中包含了對輸入數據的重複自抽樣過程，即所謂的bootstrap抽樣。這樣一來，數據集中大約三分之一將沒有用於模型的訓練而是用於測試，這樣的數據被稱為out of bag samples，通過這些樣本估計的誤差被稱為out of bag error。研究表明，這種out of bag方法的與測試集規模同訓練集一致的估計方法有著相同的精確程度，因此在隨機森林中我們無需再對測試集進行另外的設置。

缺點：

1.隨機森林在解決回歸問題時並沒有像它在分類中表現的那麼好，這是因為它並不能給出一個連續型的輸出。當進行回歸時，隨機森林不能夠作出超越訓練集數據範圍的預測，這可能導致在對某些還有特定雜訊的數據進行建模時出現過度擬合。

2.對於許多統計建模者來說，隨機森林給人的感覺像是一個黑盒子——你幾乎無法控制模型內部的運行，只能在不同的參數和隨機種子之間進行嘗試。

推薦閱讀：