聊聊機器學習中的那些樹

樹模型是機器學習領域內,除了深度學習之外,使用的最為廣泛,也是變種特別多的一種模型了,樹模型的好處是其很容易理解,且相對不容易過擬合,訓練時對資源的消耗也更少。最常用樹模型包括決策樹,隨機森林及XGBoost。而在去年,南大的周志華教授提出了deep forest,一種借鑒深度學習的樹模型,樹模型還有其他的更為冷門的變種,例如正則化貪心森林和。這篇文章將始簡單的介紹下上述的幾種樹模型的原理,樹模型是最容易理解的,請您放心,本文只有一個公式,是關於信息熵的。

樹模型主要用來做分類。最簡單的一種叫做決策樹,決策樹是一個非常接近人類思維的模型。 它形象的說就是一個調查問卷, 把一個最終的決策轉化為個若干問題, 每一步得到一個答案, 按照答案的正否來決定下一個問題是什麼,如此形成一個樹結構, 最後形成一個分類器。 比如經常被舉出的例子, 你要買電腦, 要根據很多特徵挑選電腦,比如cpu,gpu,硬碟,內存等, 你一定會問你自己一系列問題, 我要買那款cpu,gpu, 硬碟, 內存等,最後做出決策。決策樹要做的是把這個過程自動化,最後給我們我們希望的判定結果。

在一棵決策樹上,其中的節點可以分成根節點(藍色) 決策節點(紅色)和終止節點(綠色),而圖中的方框里包含的即是一顆子樹,這麼看來,樹模型是不是特別好理解?樹模型的第二個好處是可以方便的探索數據中那些維度更加重要(對做出正確的預測貢獻更大),比如上述的買電腦的例子,你會發現對於大多數人來說,CPU的型號最關鍵。樹模型的第三個好處是不怎麼需要做數據清洗和補全,還用買電腦的例子,假設你拿到的數據部分中沒有告訴GPU的型號,你不必要丟掉這部分數據,進入到相應的子樹里,隨機的讓這條數據進入一個終止節點就好了,這樣,你便能夠利用缺失的數據了。

談起樹模型,就要說起基尼係數,這個指數最常見的場景是描述貧富差距,但也可以用來指導樹模型在那裡分叉。假設一顆最簡單做二分類問題的決策樹,拿到的數據分為兩種特徵,一個是性別,一個是班級,預測學生們願不願打板球,下面的圖是兩種不同的樹模型,用性別來分,10個女生中有2個願意打球,而20個男生中有13個願意打球,而用班級分,效果則沒有那麼好,具體怎麼計算了,先從左到右依次計算每個終止節點的基尼係數,(0.2)*(0.2)+(0.8)*(0.8)=0.68 (0.65)*(0.65)+(0.35)*(0.35)=0.55 (0.43)*(0.43)+(0.57)*(0.57)=0.51 (0.56)*(0.56)+(0.44)*(0.44)=0.51,之後對每棵樹的基尼係數進行加權平均 :10/30)*0.68+(20/30)*0.55 = 0.59(按性別分),(14/30)*0.51+(16/30)*0.51 = 0.51(按班級分),因此在該例子中,性別是一個更好的特徵。

理解決策樹的下一個重要的概念是信息增益,信息可以看成是減少了多少系統中的無序,而描述系統的無序程度,可以用信息熵,對於二分類問題,計算公式是

對於每一次樹上的分叉,先算下父節點的熵,再計算下子節點的熵的加權平均,就可以計算出決策樹中的一個決策節點帶來了多少信息增益了。

信息熵公式告訴我們的是,我們每次對所有特徵都掃描一遍,選擇那個讓我們的信息增長最大的特徵。 依次在這個特徵的每個可能取值下,我們在尋找第二個關鍵特徵,列出第二個特徵選的可能取值並尋找第三個特徵依次類推。 再對每一分支的操作里, 如果我們發現在某個特徵組合下的樣本均為一類, 則停止分叉的過程。 整個操作過程形似尋找一顆不斷分叉的樹木, 故名決策樹。

決策樹能夠處理特徵之間的互相影響, 因為特徵之間的互相影響,我們並不像簡單貝葉斯那樣並列的處理這些特徵。 例如某個特徵可能在某個條件下式好的, 但在另外條件下就是壞的或者沒影響。 比如說找對象,你只在對方漂亮的時候才care他學歷。 我會根據之前問過的問題的答案來選擇下一步問什麼樣的問題, 如此, 我就能很好的處理特徵之間的關聯。

我們把這樣的思維步驟寫成偽代碼, 大概是這樣的 :

訓練集D (x1,y1)….

屬性 A attribute (a1,a2…..)

函數treegenerate

1, 生成結點node A(任選一個特徵)

2, 判斷D在A中樣本是否都屬於類型C,是則A標記為C類葉結點, 結束

3, 判斷A為空或D在A樣本取值同(x相同而非y),將node 標記為樣本多數分類的葉結點(max numbers),結束

終止條件不成立則:

從A中選擇最優劃分屬性a*,

循環:

對A*上的每一個值a*做如下處理:

If a*上的樣本為空,則a*為葉節點 (該值下用於判斷的樣本不足,判定為A*中樣本最多的類),

如果支點上的樣本集為D**

如果存在某個位置,使得D**為空,

則A*為葉節點,

否則,以a*為分支節點,回到第一句

接下來我們看一看更為複雜的情況,比如我們拿到的數據特徵不是兩個,而是一百個,那麼問題來了,我們的決策樹也要100層那麼深嗎?如果真的這麼深,那麼這個模型很容易過擬合的,任何一顆決策樹的都應該有終止條件,例如樹最深多少層,每個節點最少要有多少樣本,最多有多少個終止節點等,這些和終止條件有關的超參數設置決定了模型會不會過擬合。

下面我們從一棵樹過度到一群數,也就是機器學習中常用的begging,將原來的訓練數據集分成多份,每一份分別訓練一個分類器,最後再讓這些分類器進行投票表決。

而隨機森林,就是使用bagging技巧加持的決策樹,是不是很簡單?相比於決策樹,隨機森林的可解釋性差一些,另外對於標籤為連續的回歸問題,隨機森林所採取的求多個樹的平均數的策略會導致結果的不穩定。

隨機森林是將訓練數據隨機的分成很多類,分別訓練很多分類器,再將這些分類器聚合起來,而boosting則不講訓練數據分類,而是將弱分類器聚合起來,下圖的上半部分可以看成描述了三個弱分類器,每一個都有分錯的,而將他們集合起來,可以得出一個準確率比每一個弱分類器都高的分類模型。

你需要做的是將第一個分類器分類分錯的部分交給第二個分類器,再將第二個分類器分錯的部分交給第三個分類器,如下圖依次所示

最終得到了我們看到的強分類器。

總結來看,bagging類似於蟻群的智慧,沒有一隻螞蟻知道全部的信息,但利用螞蟻的集合,可以實現集愚成智,而boosting則是三個臭皮匠,勝過諸葛亮。Boost方法包含的非線性變換比較多,表達能力強,而且不需要做複雜的特徵工程和特徵變換。但不同於隨機森林,它是一個串列過程,不好並行化,而且計算複雜度高。

XGBoost 是 Extreme Gradient Boosting (極端梯度上升)的縮寫,是當下最常用的樹模型了,是上圖描述的Boosting Tree的一種高效實現,在R,Python等常用的語言下都有對應的包,它把樹模型複雜度作為正則項加到優化目標中,從而避免了過於複雜而容易過擬合的模型。

在Boost方法中,每一個被錯誤分類的樣本的權值會增加,以強調最困難的情況,從而使得接下來的模型能集中注意力來處理這些錯誤的樣本,然而這種方法把基於學習器的決策樹視為一個黑盒子,沒有利用樹結構本身。而Regularized Greedy Forest正則化貪心森林(RGF)會在當前森林某一步的結構變化後,依次調整整個森林中所有決策樹對應的「葉子」的權重,使損失函數最小化。例如下圖我們從原來的森林中發下右下的節點可以分叉,我們做的不止是將分叉後的樹加入森林,而且對森林中已有的樹中的對應節點也進行類似的分叉操作。

類似boost,RGF中每個節點的權重也要不斷優化,但不同的是,RGF不需要在梯度下降決策樹設置所需的樹尺寸(tree size)參數(例如,樹的數量,最大深度)。總結一下RGF是另一種樹集成技術,它類似梯度下降演算法,可用於有效建模非線性關係。

下面說說去年周志華教授提出深度森林deep forest,也叫做 gcForest,這也是一種基於決策樹的集成方法,下圖中每一層包括兩個隨機森林(藍色)和兩個complete random forests(黑色),所謂complete random forest,指的是其中的1000棵決策樹的每個節點都隨機的選擇一個特徵作為分裂特徵,不斷增長整棵樹,直到剩餘所有樣本屬於同一類,或樣本數量少於10。

至於每一層的輸出,也不是傳統決策樹的一個標籤,而是一個向量。圖中的每一個森林對每個輸入樣本都有一個輸出,對應建立該決策樹時,落在該葉子節點中的樣本集合中各個類別的樣本所佔的比例,如下圖所示,將多顆樹的結果求平均,得出這一層的輸出。為了避免過擬合,每個森林中 class vector 的產生採用了 k 折交叉驗證的方法,隨機的將k分之一的訓練樣本丟出去,再對k次訓練的結果求平均值。

deep forest還採取了類似卷積神經網路的滑動窗口,如下圖所示,原始樣本的為400維,定義一個大小為100的滑動窗口,將滑動窗口從原特徵上依次滑過,每次移動一步,每次窗口滑動獲取的100個特徵作為一個新的實例,等效於在400維特徵上每相鄰100維的特徵摘出來作為一個特徵實例,得到301個新的特徵實例(400 - 300 + 1)。

深度森林的源代碼也在Github上有開源版,總結一下,深度森林具有比肩深度神經網路的潛力,例如可以層次化的進行特徵提取及使用預訓練模型進行遷移學習,相比於深度學習,其具有少得多的超參數,並且對參數設置不太敏感,且在小數據集上,例如手寫數字識別中,表現的不比CNN差。深度森林的數據處理流如下圖所示。

總結下,樹模型作為一個常見的白盒模型,不管數據集的大小,不管是連續的回歸問題還是分類問題都適用。它不怎麼需要進行數據預處理,例如補全缺失值,去除異常點。樹模型可以針對特徵按照重要性進行排序,從而構造新的特徵或從中選出子集來壓縮數據。樹模型可以通過統計的方式去驗證模型的準確值,判斷訓練的進展,相比機器學習的模型,需要調整的超參數也更少。但和神經網路一樣,樹模型也不夠健壯,如同圖像上只需要改變幾個像素點就可以改變模型的結果,樹模型中輸入數據的微小變化也可能會顯著改變模型的結果。樹模型也有過擬合的危險,通過剪紙purning,即先讓樹長的深一些,再去除那些不帶來信息增益的分叉,留下那些最初的信息增益為負,但整體的信息增益為正的節點,可以組織樹模型的過擬合。

推薦閱讀:

機器學習基石筆記2:感知器學習演算法(PLA)
基於NLP的股價預測
Machine Learning: 機器學習項目Top 30 (v.2018)
嘗試克服一下小夥伴對神經網路的恐懼No.26
複習:決策樹

TAG:機器學習 | 決策樹 |