決策樹的定義

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

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

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

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

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

決策樹如何做決策

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

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

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

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

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

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

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

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

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

分裂屬性的選擇

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

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

a）熵

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

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

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

栗子：

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

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

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

b）信息增益

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

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

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

常見算法

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

ID₃算法：

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

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

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

過渡擬合(overfitting)

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

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

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

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

優(yōu)化方案：

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

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

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

C_4.5算法

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

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

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

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

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

Bootstraping

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

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

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

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

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

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

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)練集中隨機(jī)取出的n個(gè)訓(xùn)練樣本組成，

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

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

Random Forest 隨機(jī)森林

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

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

　　3,、每棵樹最?限度地?長(zhǎng),， 不做任何剪裁 （由于之前的兩個(gè)隨機(jī)采樣的過程保證了隨機(jī)性）

　　4、將?成的多棵樹組成隨機(jī)森林,， ?隨機(jī)森林對(duì)新的數(shù)據(jù)進(jìn)?分類,， 分類結(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)值分布。每?個(gè)訓(xùn)練樣本最開始時(shí)都被賦予相同的權(quán)值： 1/N

　　2,、進(jìn)?多輪迭代,，?m = 1,2, ..., M 表?迭代的第多少輪

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

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

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

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

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

　　　　e_m ≤ 1/2時(shí)， 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、組合各個(gè)弱分類器 ，從?得到最終分類器

GBDT

　　Adaboost的Error計(jì)算

　　GBDT的Error計(jì)算

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

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

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

XGBoost

　　a）使?L1 L2 Regularization 防?Overfitting

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

　　c）樹長(zhǎng)全后再?gòu)牡撞肯蛏蠝p枝,，防?算法貪婪