決策樹
從最簡單的地方開始吧全闷，決策樹。
前面隨機森林的部分有寫過萍启，最簡單的決策樹就是從常人的思維方式產(chǎn)生的总珠，拿比較接地氣的例子來說，某人判斷相親對象是否應(yīng)該再約的過程勘纯，就是一個典型的決策樹：
某人會首先關(guān)注性別是否相同局服，同性當然就拜拜了，異性的話就先看看年齡屡律，如果在20-30之間腌逢，就繼續(xù)看看長相，如果年齡超過30歲超埋，就直接問問收入搏讶，接著看看性格，學歷霍殴，大概就知道自己喜不喜歡媒惕，要繼續(xù)約會還是直接拜拜。以上這顆決策樹是某人通過對十幾個相親對象的考察来庭，結(jié)合自己的喜好建立的模型（這個過程就是機器學習中的“訓練”）妒蔚，這樣建立模型的好處在于，當下一個相親對象出現(xiàn)時，可以在很短的時間內(nèi)做出判斷肴盏，減少猶豫和糾結(jié)的時間科盛。
是不是很好理解？菜皂，基本跟工作流程圖沒啥區(qū)別贞绵。我們知道所有一般化的常識之所以能夠升級為高級的知識，都是在實踐中為了解決困難而慢慢變得復雜和專業(yè)恍飘。相親的問題固然簡單榨崩，但是遇到諸如預測天氣、預測比賽結(jié)果章母、預測疾病診斷母蛛、預測股市漲跌之類的情景，上面這種簡單的決策機制就不好辦了乳怎。說不好辦彩郊，主要也是一下幾個因素造成的：
1. 對于某一類現(xiàn)象（比如天氣），影響它的因素往往成百上千（比如氣壓舞肆、風速焦辅、濕度、溫度椿胯、日照時間等等）筷登；
2. 這些因素往往同時包括離散變量和連續(xù)變量，甚至有時需要預測的值是連續(xù)變量（例如冷和熱是離散變量哩盲，而溫度是連續(xù)變量前方，上述相親例子中全是離散變量）；
3. 這些因素對于分類效果的貢獻往往千差萬別廉油，有些甚至幾乎沒有什么貢獻（例如在預測天氣的時候考慮是否有冤案發(fā)生）惠险；
4. 數(shù)據(jù)采集階段可能沒有獲得高質(zhì)量的樣本群，或者樣本采集有嚴重偏好（例如收集了北方的天氣數(shù)據(jù)去預測南方天氣）抒线；
在解決這些問題之前班巩，決策樹建立需要考慮的最重要的一件事，就是如何決定下一個節(jié)點該如何分解嘶炭。比如當我們獲得了溫度抱慌、濕度和風速的數(shù)據(jù)之后，如何確定第一個考慮的因素眨猎，以及如何劃分這個因素抑进，這里就要引入三個概念：信息增益、信息增益比和基尼系數(shù)（Gini index）睡陪。這三個概念都是衡量一個因素對分類的貢獻程度寺渗，但是算法不一樣：
1. 信息增益：
p(i|t) 代表了節(jié)點 t 為分類 i 的概率匿情，其中 log2 為取以 2 為底的對數(shù)，c為某個節(jié)點中包含的樣本數(shù)信殊，k為該因素的取值范圍炬称。從公式可以看出，如果一個因素為陽性時鸡号，有更多樣本也為陽性（例如當濕度很高的時候转砖，往往會下雨），那么這個因素的信息增益就會比較高鲸伴。
2. 信息增益比：
信息增益的問題在于，擁有更大取值范圍的因素會占便宜晋控，于是可以計算信息增益比汞窗，信息增益率 = 信息增益 / 屬性熵，但是這種算法依然有問題赡译，擁有更小取值范圍的因素會占便宜仲吏。
3. Gini系數(shù)：
基尼系數(shù)相對而言比較合理，
pk表示選中的樣本屬于k類別的概率蝌焚，則這個樣本被分錯的概率是(1-pk)裹唆；基尼系數(shù)越高的因素，就可以作為劃分節(jié)點的首選只洒。
對應(yīng)上述三種計算信息增益的方法许帐，決策樹被分為ID3，C4.5和CART類型毕谴。想要真正理解這三種算法成畦，還得去實際的案例中，仔細看看計算過程涝开，這里為了偷懶循帐，貼一篇比較詳細的 決策樹 - 小小獵魔人 - 博客園，當然舀武，西瓜書里也有拄养。
回歸樹
然后，是回歸樹银舱，看名字就知道跟決策樹是一回事瘪匿，只不過預測對象從離散變量換成了連續(xù)變量，例如從預測是否下雨纵朋，到預測單日降雨量柿顶。以CART樹為例，在處理分類問題和回歸問題中的相同和差異：
相同：
????????在分類問題和回歸問題中操软，CART 都是一棵二叉樹嘁锯，除葉子節(jié)點外的所有節(jié)點都有且僅有兩個子節(jié)點；
????????所有落在同一片葉子中的輸入都有同樣的輸出。
差異：
????????在分類問題中家乘，CART 使用基尼指數(shù)（Gini index）作為選擇特征（feature）和劃分（split）的依據(jù)蝗羊；在回歸問題中，CART 使用 mse（mean square error）或者 mae（mean absolute error）作為選擇 feature 和 split 的 criteria仁锯。
????????在分類問題中耀找，CART 的每一片葉子都代表的是一個 class；在回歸問題中业崖，CART 的每一片葉子表示的是一個預測值野芒，取值是連續(xù)的∷唬回歸樹同樣要首先面對節(jié)點如何劃分的問題狞悲，與決策樹不同的是，回歸樹是根據(jù)均方誤差（MSE）作為標準來衡量劃分的優(yōu)劣妇斤，選取MSE最小的元素及其取值作為劃分的依據(jù)摇锋。MSE的計算方法如下：
j表示第j個元素（例如濕度），s是j的某個取值（例如濕度=80%）站超，yi表示觀測值（例如降雨量100毫米）荸恕，xi表示屬于該節(jié)點的樣本，c1和c2表示從父節(jié)點劃分出來的兩個節(jié)點中所有樣本的均值（因為均值可以保證每個節(jié)點的mse最兴老唷）融求。下面通過一個習題來解釋上面公式的計算過程，習題來自李航的《統(tǒng)計學習方法》第5章決策樹習題中的5.2題：
用平方誤差損失準則生成一個二叉回歸樹：
首先媳纬，我們?nèi)=1（即s取xi變量的第一個值作為劃分的界限）双肤，也就是大于4.5的和小于等于4.5的分開，于是钮惠，原本的10個樣本被分成兩組：R1 = {1}茅糜，R2={2,3,4,5,6,7,8,9,10}，然后計算c1和c2素挽，即兩組的均值蔑赘，R1只有一個值，均值就是4.5预明，R2有9個值：
這樣缩赛，得到c1=4.5，c2=6.85撰糠。
接著酥馍，我們?nèi) = 2（即s取xi變量的第2個值作為劃分的界限），也就是大于4.75的和小于等于4.75的分開阅酪，于是旨袒，原本的10個樣本被分成兩組：R1={1,2}汁针，R2={3,4,5,6,7,8,9,10}，然后計算c1和c2砚尽，即兩組的均值施无，R1有兩個值，R2有8個值：
c1 = 1/2*（4.5+4.75）=4.63
c2 = 1/8*（4.91+5.34+5.8+7.05+7.9+8.23+8.7+9）=7.12
接著必孤，我們?nèi)=3猾骡，....，以此類推敷搪，計算出10個c1和c2值：
然后兴想，來計算每個s取值對應(yīng)的MSE:
計算出10個MSE值：
于是，我們發(fā)現(xiàn)對于xi這個變量而言购啄，選擇s=5的時候?qū)?yīng)MSE（5）=3.36是最小的MSE襟企，因此，選擇s=5來劃分這個節(jié)點狮含，也就是把10個樣本劃分為兩組：R1={1,2,3,4,5}，R2={6,7,8,9,10}曼振，此時c1=5.06几迄，c2=8.18，我們得到了回歸樹的第一層：
接下來對分好的兩組重復上述步驟冰评，最終得到完整的回歸樹：
這顆回歸樹的10個葉子節(jié)點的均值就表示對原始10個值的擬合映胁，值得注意的是，回歸樹的深度決定了擬合的程度甲雅，太深就會產(chǎn)生過擬合風險解孙，相比線性回歸，回歸樹的優(yōu)點在于對原始值的尺度不敏感抛人，無需做太多轉(zhuǎn)化弛姜，且對于非線性分布的樣本理論上可以得到優(yōu)于多元線性回歸的結(jié)果，且可以通過樹深度來控制擬合：
說到過擬合風險妖枚，就不得不提決策樹和回歸樹都要面臨的剪枝問題廷臼，顧名思義，剪枝就是把樹上的一些多余的枝葉減掉绝页，目的是防止樹的生長誤入歧途荠商。剪枝策略分為預剪枝和后剪枝，預剪枝是在構(gòu)造決策樹的同時進行剪枝续誉。所有決策樹的構(gòu)建方法莱没，都是在無法進一步降低熵的情況下才會停止創(chuàng)建分支的過程，為了避免過擬合酷鸦，可以設(shè)定一個閾值饰躲，熵減小的數(shù)量小于這個閾值牙咏，即使還可以繼續(xù)降低熵，也停止繼續(xù)創(chuàng)建分支属铁。但是這種方法實際中的效果并不好眠寿。
后剪枝是在決策樹生長完成之后，對樹進行剪枝焦蘑，得到簡化版的決策樹盯拱。剪枝的過程是對擁有同樣父節(jié)點的一組節(jié)點進行檢查，判斷如果將其合并例嘱，熵的增加量是否小于某一閾值狡逢。如果確實小，則這一組節(jié)點可以合并一個節(jié)點拼卵，其中包含了所有可能的結(jié)果奢浑。后剪枝是目前最普遍的做法。
后剪枝的剪枝過程是刪除一些子樹腋腮，然后用其葉子節(jié)點代替雀彼，這個葉子節(jié)點所標識的類別通過大多數(shù)原則(majority class criterion)確定。所謂大多數(shù)原則即寡，是指剪枝過程中, 將一些子樹刪除而用葉節(jié)點代替,這個葉節(jié)點所標識的類別用這棵子樹中大多數(shù)訓練樣本所屬的類別來標識,所標識的類稱為majority class 徊哑，（majority class 在很多英文文獻中也多次出現(xiàn)）。
關(guān)于剪枝的問題另外再整理一篇單獨研究聪富。
樹的提升
現(xiàn)在回到前面羅列的影響決策樹的幾個問題（變量多莺丑，取值范圍不一，權(quán)重不好衡量等）墩蔓，不難發(fā)現(xiàn)在面對實際問題時梢莽，一棵樹即便長得再好，也只是一棵樹奸披，只能給出一個結(jié)果昏名，那如果同時培育很多棵樹，對同一個樣本給出不同的預測結(jié)果源内，是不是可以獲得更準確的判斷呢葡粒？，這就是集成學習的初衷膜钓，也就是把一些弱學習器（例如一棵決策樹）進行組合嗽交，獲得強學習器的思路。按照廣度和深度颂斜，集成學習分成了bagging和boosting兩種學習策略夫壁，前者通過隨機采樣生成很多相互獨立的基學習器，對預測結(jié)果進行投票沃疮；后者通過對預測效果的不斷提升生成很多相互影響的基學習器盒让，對預測結(jié)果進行優(yōu)化梅肤。
bagging的代表就是隨機森林，boosting在決策樹上的實現(xiàn)就是梯度提升樹（GBDT）以及adaboost邑茄。
隨機森林就不贅述了姨蝴，只想提一句隨機森林最突出的缺點，就是其隨機性很容易導致正確結(jié)果被錯誤結(jié)果淹沒肺缕。
直接來看梯度提升樹左医。梯度提升樹的原理是在決策樹的基礎(chǔ)上，利用誤差生成另一棵決策樹同木，不斷迭代浮梢，直到損失函數(shù)收斂，最后將所有對應(yīng)子節(jié)點的值相加得到最終的預測值彤路。提升采用前向分步算法秕硝，第t步的模型由第t-1步的模型形成，算法簡述如下：
舉個例子洲尊，參考自一篇博客GBDT實例远豺，該博客舉出的例子較直觀地展現(xiàn)出多棵決策樹線性求和過程以及殘差的意義。
??訓練一個提升樹模型來預測年齡：
??訓練集是4個人坞嘀，A憋飞，B，C姆吭，D年齡分別是14，16唁盏，24内狸，26。樣本中有購物金額厘擂、上網(wǎng)時長昆淡、經(jīng)常到百度知道提問等特征。提升樹的過程如下：
Adaboost是英文”Adaptive Boosting“（自適應(yīng)增強）的縮寫刽严，由Yoav Freund和Robert Schapire在1995年提出昂灵。Adaboost相對來說我了解比較少，它主要是按照貢獻程度給每個變量賦予了權(quán)重的概念舞萄，然后按照權(quán)重進行樹的迭代眨补，不斷更新權(quán)重。adaboost比較特別的地方在于倒脓，它所有的樹都是單層樹撑螺，也就是每棵樹只對應(yīng)一個變量，稱為stump（樹樁）：
上圖崎弃，adaboost有三個特點：
1. 弱學習器都是單層決策樹stump
2. 各個stump的權(quán)重不一樣
3.各個stump之間是迭代的關(guān)系
《統(tǒng)計學習方法》中adaboost算法的描述如下：
Adaboost的計算實例再次偷懶貼一篇Adaboost實例甘晤。
后面我會針對樹學習器在具體項目中的應(yīng)用繼續(xù)補充內(nèi)容含潘。
