一慌洪、決策樹(shù)簡(jiǎn)介

決策樹(shù)的特點(diǎn)：
1）既可以處理分類(lèi)問(wèn)題，也可以處理回歸問(wèn)題
2）對(duì)于缺失值數(shù)據(jù)也能比較好的處理
3）高度可解釋

決策樹(shù)的思想很簡(jiǎn)單： 根據(jù)特征及判斷閾贮匕，按照一定的路徑來(lái)決定最終的判斷結(jié)果往史。所以這里有幾個(gè)問(wèn)題：
1）節(jié)點(diǎn)如何確定？也就是說(shuō)該如何選擇用于分裂的特征黍瞧？路徑怎么決定诸尽？也就是說(shuō)，我要把哪個(gè)特征放前面進(jìn)行判斷印颤，哪個(gè)特征放后面進(jìn)行判斷您机？
2）閾值怎么確定？
3）何時(shí)停止年局？并不是把所有的數(shù)據(jù)都分割才算是好的际看，否則有可能算法對(duì)訓(xùn)練集能非常好的擬合，但是對(duì)測(cè)試集就擬合的不夠好（過(guò)擬合）
4）預(yù)測(cè)的值是什么某宪？對(duì)于分類(lèi)問(wèn)題比較好說(shuō)仿村，我們可以通過(guò)樣本類(lèi)型來(lái)進(jìn)行分類(lèi)判斷。對(duì)于回歸問(wèn)題兴喂，我們?nèi)绾蔚玫筋A(yù)測(cè)值呢蔼囊？ 我們可以有很多種方法，例如取多次樣本的平均值衣迷，或者畏鼓，直接用葉節(jié)點(diǎn)的數(shù)據(jù)再做一個(gè)線(xiàn)形回歸等等。

因此壶谒，決策樹(shù)的生成也分為如下幾步：
1）節(jié)點(diǎn)的分裂：一般當(dāng)一個(gè)節(jié)點(diǎn)所代表的屬性無(wú)法給出判斷時(shí)云矫，將這一個(gè)節(jié)點(diǎn)分裂成若干個(gè)子節(jié)點(diǎn)；
2）閾值的確定：選擇適當(dāng)?shù)拈撝凳沟梅诸?lèi)錯(cuò)誤率最小汗菜。
3）深度的確定
4 ）最終預(yù)測(cè)值的算法確定

二让禀、熵

在講后面的具體算法之前，我們先要講一下“熵”陨界。那么什么是“熵”呢巡揍？按照一般的說(shuō)法。熵就是混沌狀態(tài)的一種度量菌瘪。熵越大腮敌，表示越混沌。而所謂的增熵原理，就是說(shuō)宇宙中的事物都有自發(fā)變得更混亂的傾向糜工，也就是說(shuō)熵會(huì)不斷增加弊添。 怎么理解？ 例如：一個(gè)整潔的房間捌木，如果不加收拾油坝，會(huì)變得越來(lái)越凌亂。一個(gè)建筑物钮莲，如果不加修繕免钻，會(huì)變得越來(lái)越破舊彼水。我們本來(lái)將整理得好好的耳機(jī)線(xiàn)放在口袋里崔拥，可是，不出意外的是凤覆，每次從口袋里掏出它链瓦，它又變得亂糟糟的。但是反過(guò)來(lái)盯桦，我們從來(lái)沒(méi)有見(jiàn)過(guò)一個(gè)亂糟糟的房間不加收拾慈俯，會(huì)自然變得很整潔；一團(tuán)亂麻的手機(jī)線(xiàn)拥峦，不加真理贴膘，會(huì)自然變得很整齊。任何物體略号，一定是從有序變成無(wú)序刑峡，而不是相反，因?yàn)闊o(wú)序總是更有可能發(fā)生玄柠。既然是度量突梦，我們就有公式。熵的計(jì)算公式如下：
關(guān)于熵的介紹羽利，我們這里就點(diǎn)到為止宫患。還有不懂或者感興趣的同學(xué)，可以參考下面的文章这弧。

三娃闲、信息熵

上面講了熵，現(xiàn)在再來(lái)說(shuō)信息熵匾浪。
首先皇帮，我們要知道什么是信息量。
信息量是對(duì)信息的度量户矢，就跟時(shí)間的度量是秒一樣玲献，當(dāng)我們考慮一個(gè)離散的隨機(jī)變量x的時(shí)候，當(dāng)我們觀(guān)察到的這個(gè)變量的一個(gè)具體值的時(shí)候，我們接收到了多少信息呢捌年？
多少信息用信息量來(lái)衡量瓢娜，我們接受到的信息量跟具體發(fā)生的事件有關(guān)。
信息的大小跟隨機(jī)事件的概率有關(guān)礼预。越小概率的事情發(fā)生了產(chǎn)生的信息量越大眠砾，如湖南產(chǎn)生的地震了；越大概率的事情發(fā)生了產(chǎn)生的信息量越小托酸，如太陽(yáng)從東邊升起來(lái)了（肯定發(fā)生嘛褒颈，沒(méi)什么信息量）。
下面我們正式引出信息熵励堡。
信息量度量的是一個(gè)具體事件發(fā)生了所帶來(lái)的信息谷丸，而熵則是在結(jié)果出來(lái)之前對(duì)可能產(chǎn)生的信息量的期望——考慮該隨機(jī)變量的所有可能取值，即所有可能發(fā)生事件所帶來(lái)的信息量的期望应结。即

四刨疼、ID3 決策樹(shù)算法

有了上面的理論基礎(chǔ)，為了能讓我們的決策樹(shù)分類(lèi)越正確鹅龄，越穩(wěn)定揩慕，信息量越大，我們就需要信息熵能達(dá)到最小扮休。這就是我們進(jìn)行選擇節(jié)點(diǎn)和閾值的依據(jù)迎卤。另外，構(gòu)建樹(shù)的另外一個(gè)基本想法是隨著樹(shù)的深度的增加玷坠，節(jié)點(diǎn)的熵迅速的降低蜗搔。熵降低的速度越快越好，這樣就能得到一顆較矮的決策樹(shù)（能 3 步判斷出來(lái)就不用 5 步判斷）∏仍悖現(xiàn)在我們來(lái)使用ID3算法構(gòu)建一個(gè)決策樹(shù)碍扔。先看如下的一個(gè)樣本例子：

同理，我們可以計(jì)算出赋兵，采用temperature作為根節(jié)點(diǎn)后的熵為：0.91笔咽；采用humidty作為根節(jié)點(diǎn)后的熵為：0.79；采用windy后的熵為：0.89
我們可以看到霹期，使用outlook能使得我們的熵最幸蹲椤（下降得最快），因此历造，根節(jié)點(diǎn)我們選用outlook甩十。

2）選擇內(nèi)節(jié)點(diǎn)
根節(jié)點(diǎn)確定后船庇，我們?cè)谟猛瑯拥姆椒▉?lái)選擇內(nèi)節(jié)點(diǎn)。
當(dāng)根節(jié)點(diǎn)的值為overcast時(shí)侣监，不用再分了溢十。熵已經(jīng)最小。
當(dāng)根節(jié)點(diǎn)的值為sunny時(shí)达吞，選temperature作為內(nèi)節(jié)點(diǎn)张弛，得到熵為：，選humidity作為內(nèi)節(jié)點(diǎn)酪劫，得到的熵為0吞鸭，選wind得到的熵為0.95。顯然我們要選擇humidity作為sunny下面的內(nèi)節(jié)點(diǎn)覆糟。
當(dāng)根節(jié)點(diǎn)值為rainy時(shí)刻剥，原理同上。

以上就是ID3構(gòu)建決策樹(shù)的基本思想滩字。
當(dāng)然造虏，這個(gè)算法有個(gè)致命弱點(diǎn)，就是特征的不同特征值越多麦箍，越容易被采用為內(nèi)（根）節(jié)點(diǎn)漓藕。試想一下，如果有一個(gè)特征挟裂，對(duì)于14個(gè)樣本數(shù)據(jù)享钞，有14個(gè)不同的值，那么他的信息熵就會(huì)為0诀蓉，然后決策樹(shù)會(huì)用這個(gè)特征來(lái)劃分原數(shù)據(jù)集栗竖，其實(shí)這種劃分毫無(wú)意義。所以渠啤，引申出了另外一個(gè)決策算法——C4.5

五狐肢、C4.5 決策樹(shù)算法

為了解決上面ID3提到的問(wèn)題，我們把ID3的評(píng)估算法稍微改進(jìn)一下：
ID3 評(píng)估一個(gè)特征能否成為節(jié)點(diǎn)沥曹，是用原始熵減去該節(jié)點(diǎn)的熵份名，得到的一個(gè)信息增益。信息增益越大架专，代表該節(jié)點(diǎn)相對(duì)于原始節(jié)點(diǎn)來(lái)說(shuō)同窘，信息熵越低，降低得越快部脚。
C4.5 在信息增益的基礎(chǔ)上想邦，需要除以該節(jié)點(diǎn)“純度”。例如如果該特征有14個(gè)不同的特征值委刘，其純度為14丧没，某特征有3個(gè)不同的特征值鹰椒，其純度為3。顯然呕童，純度越大漆际，也即分母越大，那么最終得到的值越小夺饲。 相當(dāng)于加了一個(gè)懲罰項(xiàng)（懲罰因子）奸汇，來(lái)進(jìn)行平衡。

另外往声，ID3只能處理特征值是分類(lèi)變量的情況擂找。C4.5改進(jìn)了算法，支持特征為連續(xù)值的情況浩销。主要思路是將連續(xù)型變量離散化贯涎。具體做法為：
1）將連續(xù)變量的值從小到大排列；
2）取兩個(gè)相鄰變量的平均數(shù)慢洋，得到m-1個(gè)劃分點(diǎn)塘雳；
3）將這m-1個(gè)劃分點(diǎn)作為離散值，分別計(jì)算其信息熵的增益普筹，選擇信息增益最大的點(diǎn)作為該連續(xù)特征的分類(lèi)閾值败明。

六、CART 決策樹(shù)算法

不同于ID3斑芜、C4.5所袁，CART沒(méi)有使用信息熵增益來(lái)進(jìn)行決策何之，而是用了另外一個(gè)衡量標(biāo)準(zhǔn)——基尼系數(shù)钓试∮霭耍基尼系數(shù)代表了模型的不純度蛔外，基尼系數(shù)越小呐伞，不純度越低猎贴，特征越好搁吓。這和信息增益（比）相反崭添。
假設(shè)K個(gè)類(lèi)別寓娩，第k個(gè)類(lèi)別的概率為，概率分布的基尼系數(shù)表達(dá)式為：呼渣。
如果是二分類(lèi)問(wèn)題棘伴，第一個(gè)樣本輸出概率為p，概率分布的基尼系數(shù)表達(dá)式為：屁置。
對(duì)于樣本D焊夸，個(gè)數(shù)為|D|，根據(jù)特征A的某個(gè)值a蓝角，把D分成|D1|和|D2|阱穗，則在特征A的條件下饭冬，樣本D的基尼系數(shù)表達(dá)式為：。
直接上例子揪阶。還是上面那個(gè)例子昌抠。假設(shè)我們選擇outlook作為根節(jié)點(diǎn)，則:
當(dāng)閾值為sunny時(shí)鲁僚，其基尼系數(shù)為：
當(dāng)閾值為overcast時(shí)炊苫，其基尼系數(shù)為：
當(dāng)閾值為rainy時(shí)，其基尼系數(shù)為：
同理冰沙，我們計(jì)算出其他幾個(gè)特征對(duì)應(yīng)的基尼系數(shù)：



因?yàn)閔umidity和windy的特征都只有兩個(gè)劝评，所以他們都只有一個(gè)切分點(diǎn)

顯然，Gini(outlook,overcast) 最小倦淀，因此我們會(huì)選擇outlook作為根節(jié)點(diǎn)蒋畜，overcast作為切分點(diǎn)，劃分出一個(gè)葉節(jié)點(diǎn)撞叽，一個(gè)內(nèi)節(jié)點(diǎn)姻成，然后對(duì)內(nèi)節(jié)點(diǎn)再按照上述步驟計(jì)算基尼系數(shù)，進(jìn)一步進(jìn)行劃分愿棋。

所以科展，CART作為分類(lèi)算法時(shí)，其思想跟ID3是一樣的糠雨，只不過(guò)是決策的方法不同而已才睹。另外，在對(duì)離散變量進(jìn)行處理時(shí)甘邀，是采用的不停的二分策略琅攘。在ID3、C4.5松邪，特征A被選取建立決策樹(shù)節(jié)點(diǎn)坞琴，如果它有3個(gè)類(lèi)別A1,A2,A3，我們會(huì)在決策樹(shù)上建立一個(gè)三叉點(diǎn)逗抑，這樣決策樹(shù)是多叉樹(shù)剧辐。CART采用的是不停的二分。會(huì)考慮把特征A分成{A1}和{A2,A3}邮府、{A2}和{A1,A3}荧关、{A3}和{A1,A2}三種情況，找到基尼系數(shù)最小的組合褂傀。

CART除了可以作為分類(lèi)算法忍啤，也可以作為回歸算法。分類(lèi)樹(shù)與回歸樹(shù)的區(qū)別在樣本的輸出紊服，如果樣本輸出是離散值檀轨，這是分類(lèi)樹(shù)胸竞；樣本輸出是連續(xù)值，這是回歸樹(shù)参萄。當(dāng)作為分類(lèi)樹(shù)時(shí)卫枝，我們用基尼系數(shù)來(lái)進(jìn)行度量劃分節(jié)點(diǎn)的優(yōu)劣，且預(yù)測(cè)結(jié)果采用葉子節(jié)點(diǎn)里概率最大的類(lèi)別作為當(dāng)前節(jié)點(diǎn)的預(yù)測(cè)類(lèi)別讹挎。而作為回歸樹(shù)時(shí)校赤，我們用SSE來(lái)進(jìn)行度量劃分節(jié)點(diǎn)的優(yōu)劣，采用葉子節(jié)點(diǎn)的均值或者中位數(shù)來(lái)預(yù)測(cè)輸出結(jié)果筒溃。具體來(lái)說(shuō)马篮，度量目標(biāo)是對(duì)于劃分特征A，對(duì)應(yīng)劃分點(diǎn)s兩邊的數(shù)據(jù)集D1和D2怜奖，求出使D1和D2各自集合的均方差最小浑测，同時(shí)D1和D2的均方差之和最小。

#給定一個(gè)分類(lèi)點(diǎn)歪玲，將數(shù)據(jù)分為兩類(lèi)迁央，分別計(jì)算這兩類(lèi)的均方差
compute_SSE_split <- function(v, y, split_point) {
  index<-v<split_point #這里的index全是false或者ture，也可以認(rèn)為是0和1
  y1<-y[index] # 取出來(lái)所有為true對(duì)應(yīng)的y值
  y2<-y[!index] # 取出所有為fasle對(duì)應(yīng)的y值
  SSE<-sum((y1-mean(y1))^2) + sum((y2-mean(y2))^2) #計(jì)算兩堆數(shù)的方差
  return(SSE)
}

#給定一個(gè)向量v和一個(gè)y值滥崩，把向量v按照里面的每個(gè)元素進(jìn)行分類(lèi)岖圈，將數(shù)據(jù)分為兩類(lèi)，分別計(jì)算這兩類(lèi)數(shù)據(jù)的均方差
compute_all_SSE_splits <- function(v, y) {
  sapply(unique(v), function(sp) compute_SSE_split(v,y,sp))
}

set.seed(99)
x1<-rbinom(20,1,0.5) #生成20個(gè)0,1钙皮。1次試驗(yàn)蜂科，概率0.5
set.seed(100)
x2<-round(10+rnorm(20,5,5),2) #產(chǎn)生20個(gè)均值為5，標(biāo)準(zhǔn)差也為5的隨機(jī)數(shù)短条，加上10后导匣，進(jìn)行四舍五入，保留兩位小數(shù)慌烧。
set.seed(101)
y<-round((1+(x2*2/5)+x1-rnorm(20,0,3)),2) #生成y
rcart_df<-data.frame(x1,x2,y)

x1splits<-compute_all_SSE_splits(x1,y)  #對(duì)特征1計(jì)算所有的方差逐抑。因?yàn)閤1只有0和1兩個(gè)數(shù)，因此只會(huì)有2個(gè)結(jié)果屹蚊。其中小于0并不能進(jìn)行區(qū)分，其實(shí)是有一個(gè)結(jié)果有效进每。
x2splits<-compute_all_SSE_splits(x2,y)  #對(duì)特征2計(jì)算所有的方差汹粤。特征2是離散值，有多少個(gè)不同的特征田晚，就會(huì)有多少個(gè)不同的結(jié)果嘱兼。當(dāng)然，對(duì)于最小的特征贤徒，其最終得到的sse也是無(wú)用的芹壕。

決策樹(shù)很容易對(duì)訓(xùn)練集過(guò)擬合汇四，導(dǎo)致泛化能力差，所以要對(duì)CART樹(shù)進(jìn)行剪枝踢涌，即類(lèi)似線(xiàn)性回歸的正則化通孽。剪枝分為預(yù)減枝和后剪枝兩種方法。預(yù)剪枝就是在做模型前睁壁，先想好每個(gè)葉節(jié)點(diǎn)上要保留多少數(shù)據(jù)量背苦。事先設(shè)定一個(gè)閾值，來(lái)確定每個(gè)葉節(jié)點(diǎn)上的數(shù)據(jù)量潘明。如果小于了該值行剂，則不再分裂，確保每個(gè)葉節(jié)點(diǎn)上的數(shù)據(jù)量不至于太少钳降。后剪枝則是先生成決策樹(shù)厚宰，然后再根據(jù)剪枝損失函數(shù)和交叉檢驗(yàn)來(lái)決定要剪掉哪條，保留泛化能力最強(qiáng)的分支遂填。剪枝損失函數(shù)表達(dá)式：铲觉。其中，為正則化參數(shù)(和線(xiàn)性回歸的正則化一樣)城菊，為訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差（回歸樹(shù)為均方差备燃，分類(lèi)樹(shù)為基尼系數(shù)），為樹(shù)T葉子節(jié)點(diǎn)數(shù)量凌唬。CART采用后剪枝法并齐。

七、其他決策樹(shù)算法

** M5 回歸模型樹(shù)**
M5 回歸模型樹(shù)與CART的區(qū)別在于：
1）CART在做回歸時(shí)客税，是取的葉節(jié)點(diǎn)的均值或中位數(shù)况褪，而M5是用葉節(jié)點(diǎn)的數(shù)據(jù)再做了一個(gè)線(xiàn)性模型，用線(xiàn)形模型的結(jié)果做為輸出更耻；
2）M5 在做分裂判斷時(shí)测垛，用的是標(biāo)準(zhǔn)差的加權(quán)（MSE），CART用的是均方差秧均；

# 在R中使用M5算法
library(RWeka)
m5tree<-M5P(LeagueIndex~., data=skillcraft_train)

八食侮、總結(jié)及R的實(shí)現(xiàn)

rpart包常用參數(shù)如下：

C50使用示例：

#預(yù)測(cè)紙幣的真實(shí)性，四個(gè)特征分別是：小波變換后圖像的方差戒劫、偏斜度半夷、峰度以及圖像的熵
bnote <- read.csv("data_banknote_authentication.txt", header=FALSE)
names(bnote) <- c("waveletVar", "waveletSkew", "waveletCurt", "entropy", "class") #添加列名
bnote$class <- factor(bnote$class)

#劃分測(cè)試集和訓(xùn)練集
library(caret)
set.seed(266)
bnote_sampling_vector <- createDataPartition(bnote$class, p = 0.80, list = FALSE)
bnote_train <- bnote[bnote_sampling_vector,]
bnote_test <- bnote[-bnote_sampling_vector,]

#使用C50算法構(gòu)建決策樹(shù)
library(C50)
bnote_tree <- C5.0(class~.,data=bnote_train)

#在測(cè)試集上進(jìn)行預(yù)測(cè)
bnote_predictions <- predict(bnote_tree,bnote_test)
mean(bnote_test$class == bnote_predictions) #評(píng)判測(cè)試集上的預(yù)測(cè)效果

rpart 使用示例：

#預(yù)測(cè)星際爭(zhēng)霸的比賽
skillcraft <- read.csv("SkillCraft1_Dataset.csv")
#去掉GameId，因?yàn)椴皇翘卣髁垦赶福瑢?duì)分類(lèi)無(wú)用
skillcraft<-skillcraft[-1]
skillcraft$TotalHours=as.numeric(skillcraft$TotalHours)
skillcraft$HoursPerWeek=as.numeric(skillcraft$HoursPerWeek)
skillcraft$Age=as.numeric(skillcraft$Age)

View(skillcraft)

#劃分測(cè)試集和訓(xùn)練集
library(caret)
set.seed(133)
skillcraft_sampling_vector <- createDataPartition(skillcraft$LeagueIndex, p = 0.80, list = FALSE)
skillcraft_train <- skillcraft[skillcraft_sampling_vector,]
skillcraft_test <- skillcraft[-skillcraft_sampling_vector,]

#使用rpart進(jìn)行決策樹(shù)分類(lèi)
library(rpart)
regtree <- rpart(LeagueIndex~., data=skillcraft_train)

#計(jì)算SSE
compute_SSE <- function(correct,predictions) {
  return(sum((correct-predictions)^2))
}

#在測(cè)試集上進(jìn)行預(yù)測(cè)
regtree_predictions = predict(regtree, skillcraft_test)
(regtree_SSE <- compute_SSE(regtree_predictions, skillcraft_test$LeagueIndex))#評(píng)判測(cè)試集上的預(yù)測(cè)效果

#minsplit指定父節(jié)點(diǎn)和子節(jié)點(diǎn)中所包含的最少樣本量,是最小分支節(jié)點(diǎn)數(shù)巫橄，這里指大于等于20，那么該節(jié)點(diǎn)會(huì)繼續(xù)分劃下去茵典，否則停止
#minbucket：葉子節(jié)點(diǎn)最小樣本數(shù)
#cp 復(fù)雜程度.用于控制樹(shù)的復(fù)雜度湘换，指某個(gè)點(diǎn)的復(fù)雜度，對(duì)每一步拆分,模型的擬合優(yōu)度必須提高的程度统阿。值越低彩倚，復(fù)雜度越高，默認(rèn)為0.01扶平；
#maxdepth 最大10層
#xval指定交叉驗(yàn)證的次數(shù)帆离；
regtree.random <- rpart(LeagueIndex~., data=skillcraft_train, 
                        control=rpart.control(minsplit=20, cp=0.001, maxdepth=10))
regtree.random_predictions = predict(regtree.random, skillcraft_test)
(regtree.random_SSE <- compute_SSE(regtree.random_predictions, 
                                   skillcraft_test$LeagueIndex))
#調(diào)參
library(e1071)
rpart.ranges<-list(minsplit=seq(5,50,by=5), 
                   cp=c(0,0.001,0.002,0.005,0.01,0.02,0.05,0.1,0.2,0.5), maxdepth=1:10)
(regtree.tune<-tune(rpart,LeagueIndex~., data=skillcraft_train, ranges=rpart.ranges))

#用調(diào)參后的值進(jìn)行預(yù)測(cè)
regtree.tuned <- rpart(LeagueIndex~., data=skillcraft_train,control=rpart.control(minsplit=50, cp=0.002, maxdepth=7))
regtree.tuned_predictions = predict(regtree.tuned, skillcraft_test)
(regtree.tuned_SSE <- compute_SSE(regtree.tuned_predictions, skillcraft_test$LeagueIndex))

【參考文章】
能否盡量通俗地解釋什么叫做熵？
信息熵是什么结澄？
通俗理解信息熵
機(jī)器學(xué)習(xí)實(shí)戰(zhàn)（三）——決策樹(shù)
通俗易懂的講解決策樹(shù)
決策樹(shù)算法原理
R語(yǔ)言：決策樹(shù)ID3/C4.5/CART/C5.0算法的實(shí)現(xiàn)