決策樹的定義

　　決策樹（decision tree）是一個樹結(jié)構(gòu)（可以是二叉樹或非二叉樹）。其每個非葉節(jié)點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節(jié)點存放一個類別。使用決策樹進行決策的過程就是從根節(jié)點開始，測試待分類項中相應(yīng)的特征屬性，并按照其值選擇輸出分支，直到到達葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結(jié)果。

　　樹是由節(jié)點和邊兩種元素組成的結(jié)構(gòu)。理解樹，就需要理解幾個關(guān)鍵詞：根節(jié)點、父節(jié)點、子節(jié)點和葉子節(jié)點。

　　父節(jié)點和子節(jié)點是相對的，說白了子節(jié)點由父節(jié)點根據(jù)某一規(guī)則分裂而來，然后子節(jié)點作為新的父親節(jié)點繼續(xù)分裂，直至不能分裂為止。

　　而根節(jié)點是沒有父節(jié)點的節(jié)點，即初始分裂節(jié)點，葉子節(jié)點是沒有子節(jié)點的節(jié)點，如下圖所示：

　　決策樹利用如上圖所示的樹結(jié)構(gòu)進行決策，每一個非葉子節(jié)點是一個判斷條件，每一個葉子節(jié)點是結(jié)論。從跟節(jié)點開始，經(jīng)過多次判斷得出結(jié)論。

決策樹如何做決策

　　案例：預(yù)測?明今天出不出門打球

　　步驟1：將所有的數(shù)據(jù)看成是一個節(jié)點，進入步驟2；

　　步驟2：從所有的數(shù)據(jù)特征中挑選一個數(shù)據(jù)特征對節(jié)點進行分割，進入步驟3；

　　步驟3：生成若干孩子節(jié)點，對每一個孩子節(jié)點進行判斷，如果滿足停止分裂的條件，進入步驟4；否則，進入步驟2；

　　步驟4：設(shè)置該節(jié)點是子節(jié)點，其輸出的結(jié)果為該節(jié)點數(shù)量占比最大的類別。

數(shù)據(jù)分割

　　分裂屬性的數(shù)據(jù)類型分為離散型和連續(xù)性兩種情況。

　　對于離散型的數(shù)據(jù)，按照屬性值進行分裂，每個屬性值對應(yīng)一個分裂節(jié)點；

　　對于連續(xù)性屬性，一般性的做法是對數(shù)據(jù)按照該屬性進行排序，再將數(shù)據(jù)分成若干區(qū)間，如[0,10]、[10,20]、[20,30]…，一個區(qū)間對應(yīng)一個節(jié)點，若數(shù)據(jù)的屬性值落入某一區(qū)間則該數(shù)據(jù)就屬于其對應(yīng)的節(jié)點。

分裂屬性的選擇

　　決策樹采用貪婪思想進行分裂，即選擇可以得到最優(yōu)分裂結(jié)果的屬性進行分裂。

　　需要一個衡量Purity(純潔度) 的 標(biāo)準(zhǔn)(metrics)，這個標(biāo)準(zhǔn)需要是對稱性的 ( 4是/0否 = 0是/4否 )

a）熵

　　熵描述了數(shù)據(jù)的混亂程度，熵越大，混亂程度越高，也就是純度越低；反之，熵越小，混亂程度越低，純度越高。

   　　  其中P_i 表示類i的數(shù)量占比。

　　以二分類問題為例，如果兩類的數(shù)量相同，此時分類節(jié)點的純度最低，熵 等于1；如果節(jié)點的數(shù)據(jù)屬于同一類時，此時節(jié)點的純度最高，熵 等于0。

栗子：

　　H(S) = - P(是)logP(是) - P(否)logP(否)

　　計算3是/3否：H(S) =  - 3/6log3/6  -  3/6logP3/6 = 1

　　計算4是/0否：H(S) =  - 4/4log4/4  -  0/4logP0/4 = 0

b）信息增益

      用信息增益表示分裂前后的數(shù)據(jù)復(fù)雜度和分裂節(jié)點數(shù)據(jù)復(fù)雜度的變化值，計算公式表示為：

　　其中Gain表示節(jié)點的復(fù)雜度，Gain越高，說明復(fù)雜度越高。

　　信息增益就是分裂前的數(shù)據(jù)復(fù)雜度 減去 孩子節(jié)點的數(shù)據(jù)復(fù)雜度的和，信息增益越大，分裂后的復(fù)雜度減小得越多，分類的效果越明顯。

常見算法

　　決策樹的構(gòu)建算法主要有ID₃、C_4.5、CART三種，其中ID₃和C_4.5是分類樹，CART是分類回歸樹

ID₃算法：

　　1）對當(dāng)前樣本集合，計算所有屬性的信息增益；

　　2）選擇信息增益最?的屬性作為測試屬性，把測試屬性取值相同的樣本劃為同?個?樣本集；

　　3）若?樣本集的類別屬性只含有單個屬性，則分?為葉?節(jié)點，判斷其屬性值并標(biāo)上相應(yīng)的符號，然后返回調(diào)?處；否則對?樣本集遞歸調(diào)?本算法。

過渡擬合(overfitting)

　　采用上面算法生成的決策樹在事件中往往會導(dǎo)致過濾擬合。也就是該決策樹對訓(xùn)練數(shù)據(jù)可以得到很低的錯誤率，但是運用到測試數(shù)據(jù)上卻得到非常高的錯誤率。過渡擬合的原因有以下幾點：

　　噪音數(shù)據(jù)：訓(xùn)練數(shù)據(jù)中存在噪音數(shù)據(jù)，決策樹的某些節(jié)點有噪音數(shù)據(jù)作為分割標(biāo)準(zhǔn)，導(dǎo)致決策樹無法代表真實數(shù)據(jù)。

　　缺少代表性數(shù)據(jù)：訓(xùn)練數(shù)據(jù)沒有包含所有具有代表性的數(shù)據(jù)，如在日期這個條件下做分裂，導(dǎo)致某一類數(shù)據(jù)無法很好的匹配，這一點可以通過觀察混淆矩陣（Confusion Matrix）分析得出。

　　多重比較：永遠可以把N個數(shù)據(jù)分成100%純潔的N組

優(yōu)化方案：

1、減少不必要的分裂，規(guī)定分裂條件得到結(jié)果的隨機性百分比，超過一定比例才作為分列條件

2、減枝Prune（根據(jù)ValidationSet 驗證集）

　　如果數(shù)據(jù)集為14條，采用10條作為訓(xùn)練數(shù)據(jù)，4條為驗證集，當(dāng)決策樹組合后，人為減少枝，使用驗證集能否分出pure分裂，判斷枝是否多余。

C_4.5算法

　　ID₃算法存在一個問題，就是偏向于多值屬性。

　　例如，如果存在唯一標(biāo)識屬性ID，則ID₃會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。

　　ID₃的后繼算法C_4.5使用增益率（Gain Ratio）的信息增益擴充，試圖克服這個偏倚。

      其中各符號意義與ID₃算法相同，然后，增益率被定義為：

　　C_4.5選擇具有最大增益率的屬性作為分裂屬性，其具體應(yīng)用與ID₃類似，不再贅述。

Bootstraping

　　它是一種有放回的抽樣方法，它是非參數(shù)統(tǒng)計中一種重要的估計統(tǒng)計量方差進而進行區(qū)間估計的統(tǒng)計方法。其核心思想和基本步驟如下：

　　（1） 采用重抽樣技術(shù)從原始樣本中抽取一定數(shù)量（自己給定）的樣本，此過程允許重復(fù)抽樣。 

　?。?） 根據(jù)抽出的樣本計算給定的統(tǒng)計量T。 

　　（3） 重復(fù)上述N次（一般大于1000），得到N個統(tǒng)計量T。 

　?。?） 計算上述N個統(tǒng)計量T的樣本方差，得到統(tǒng)計量的方差。

　　應(yīng)該說Bootstrap是現(xiàn)代統(tǒng)計學(xué)較為流行的一種統(tǒng)計方法，在小樣本時效果很好。通過方差的估計可以構(gòu)造置信區(qū)間等，其運用范圍得到進一步延伸。

Bagging

　　Fit many large trees to bootstrap-resampled versions of the training data, and classify by majority vote. 

　　bootstrap aggregating的縮寫。

　　讓該學(xué)習(xí)算法訓(xùn)練多輪，每輪的訓(xùn)練集由從初始的訓(xùn)練集中隨機取出的n個訓(xùn)練樣本組成，

　　某個初始訓(xùn)練樣本在某輪訓(xùn)練集中可以出現(xiàn)多次或根本不出現(xiàn)，訓(xùn)練之后可得到一個預(yù)測函數(shù)序列h_1，? ?h_n ；

　　最終的預(yù)測函數(shù)H對分類問題采用投票方式，對回歸問題采用簡單平均方法對新示例進行判別。

Random Forest 隨機森林

　　1、從原始訓(xùn)練數(shù)據(jù)集中，應(yīng)?bootstrap?法有放回地隨機抽取K個新的?助樣本集，并由此構(gòu)建K棵分類回歸樹，每一棵樹的輸入樣本都不是全部的樣本，使得相對不容易出現(xiàn)over-fitting。

　　2、設(shè)有n個特征，則在每?棵樹的每個節(jié)點處隨機抽取m個特征，通過計算每個特征蘊含的信息量，特征中選擇?個最具有分類能?的特征進?節(jié)點分裂。 

　　3、每棵樹最?限度地?長， 不做任何剪裁 （由于之前的兩個隨機采樣的過程保證了隨機性）

　　4、將?成的多棵樹組成隨機森林， ?隨機森林對新的數(shù)據(jù)進?分類， 分類結(jié)果按樹分類器投票多少?定。

Bootsing

　　1、先在原數(shù)據(jù)集中生成出一顆樹

　　2、把前一顆樹沒能完美分類的數(shù)據(jù)重新設(shè)置權(quán)重

　　3、?新的權(quán)重樹再訓(xùn)練出一顆樹

　　4、最終的分類結(jié)果由加權(quán)投票決定

AdaBoost

　　1、初始化訓(xùn)練數(shù)據(jù)的權(quán)值分布。每?個訓(xùn)練樣本最開始時都被賦予相同的權(quán)值： 1/N

　　2、進?多輪迭代，?m = 1,2, ..., M 表?迭代的第多少輪

　　　　a）使?具有權(quán)值分布Dm的訓(xùn)練數(shù)據(jù)集學(xué)習(xí)，得到基本分類器 

　　　　b）計算G_m(x)在訓(xùn)練數(shù)據(jù)集上的分類誤差率

　　　　例如：設(shè)定推測結(jié)果與真實結(jié)果的情況為有誤差是1，沒有誤差是0

　　　　e_m就是被G_m(x)誤分類樣本的權(quán)值之和，1000個樣本錯誤100個，e_m就是1/10

　　3、計算G_m(x)的系數(shù)， a_m表?G_m(x)在最終分類器中的重要程度

　　　　e_m ≤ 1/2時， a_m ≥ 0，且a_m隨著e_m的減??增?，意味著分類誤差率越?的基本分類器在最終分類器中的作?越?

　　4、更新訓(xùn)練集數(shù)據(jù)權(quán)重

　　使得被基本分類器G_m(x)誤分類樣本的權(quán)值增?，?被正確分類樣本的權(quán)值減?

　　Z_m是規(guī)范化因?，使所有w的和為1 

　　5、組合各個弱分類器 ，從?得到最終分類器

GBDT

　　Adaboost的Error計算

　　GBDT的Error計算

　　把殘差作為下?輪的學(xué)習(xí)?標(biāo)

　　比如: ?GBDT預(yù)測年齡 A的真實年齡是18歲，但第一棵樹的預(yù)測年齡是12歲，差了6歲，即殘差為6歲。 那么在第二棵樹里我們把A的年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹真的能把A分到6歲的葉子節(jié)點， 那累加兩棵樹的結(jié)論就是A的真實年齡；如果第二棵樹的結(jié)論是5歲，則A仍然存在1歲的殘差， 第三棵樹里A的年齡就變成1歲，繼續(xù)學(xué)。

　　最終的結(jié)果有加權(quán)和值得到，不再是簡單的多數(shù)投票

XGBoost

　　a）使?L1 L2 Regularization 防?Overfitting

　　b）對代價函數(shù)?階和?階求導(dǎo)，更快的Converge

　　c）樹長全后再從底部向上減枝，防?算法貪婪