決策樹(shù)（Decision Tree）簡(jiǎn)介

決策樹(shù)是一種分類(lèi)和回歸算法。比較適合分析離散數(shù)據(jù)。如果是連續(xù)數(shù)據(jù)要先轉(zhuǎn)成離散數(shù)據(jù)在做分析。

決策樹(shù)簡(jiǎn)單例子

根據(jù)以上表格可以根據(jù)年齡為根節(jié)點(diǎn)畫(huà)出的決策樹(shù)如下所示：

也可以把收入和是否為學(xué)生等來(lái)作為根節(jié)點(diǎn)來(lái)畫(huà)出決策樹(shù)，因此決策樹(shù)不唯一。

熵（Entropy）概念

1948年，香農(nóng)提出了“信息熵”的概念。一條信息的信息量大小和它的不確定性有直接的關(guān)系，要搞清楚一件非常不確定的事情，或者是我們一無(wú)所知的事情，需要了解大量信息。信息量的度量就是等于不確定性的多少。

信息熵公式如下所示

p：代表概率；x:代表每種情況的可能性

例子：

其結(jié)果如下所示：

ID3算法

決策樹(shù)會(huì)選擇最大化信息增益來(lái)對(duì)結(jié)點(diǎn)進(jìn)行劃分，信息增益計(jì)算：

Info(D)最后結(jié)果的每個(gè)概率

利用ID3算法來(lái)計(jì)算例題：

選擇信息增益最大的作為根節(jié)點(diǎn)，確定根節(jié)點(diǎn)后在計(jì)算其余參數(shù)的信息增益。

ID3算法的缺點(diǎn)：計(jì)算信息增益的時(shí)更傾向于分支多的參數(shù)作為節(jié)點(diǎn)。

C4.5算法

C4.5是ID3算法的改進(jìn)，在ID3算法的基礎(chǔ)上添加了一個(gè)增益率。添加了增益率之后，優(yōu)化了ID3的缺點(diǎn)。

ID3算法實(shí)例：

數(shù)據(jù)集為例子中是否買(mǎi)電腦的例子，例子數(shù)據(jù)如下圖所示：

導(dǎo)入包：

from sklearn.feature_extraction import DictVectorizer from sklearn import tree from sklearn import preprocessing from sklearn.preprocessing import LabelBinarizer import csv

讀入數(shù)據(jù)：

Dtree=open(r'AllElectronics.csv','r')#可以讀取字符類(lèi)型 reader=csv.reader(Dtree) #獲取第一行數(shù)據(jù) headers=reader.__next__()#第一行 print(headers) #定義兩個(gè)列表 featureList=[]#特征 labelList=[]#標(biāo)簽 for row in reader:#把label 存入listlabelList.append(row[-1])#保存no or yesrowDict={}for i in range(1,len(row)-1):#建立一個(gè)數(shù)據(jù)字典rowDict[headers[i]]=row[i]#把數(shù)據(jù)字典存入listfeatureList.append(rowDict) print(featureList)

把數(shù)據(jù)轉(zhuǎn)化為0、1格式：

#把數(shù)據(jù)轉(zhuǎn)換成01表示 vec=DictVectorizer()#特征提取 x_data=vec.fit_transform(featureList).toarray()#轉(zhuǎn)化為01形式 print('x_data:'+str(x_data)) #打印屬性名稱(chēng) print(vec.get_feature_names()) print("labelList:"+str(labelList)) #把標(biāo)簽轉(zhuǎn)化為01表示 lb=LabelBinarizer() y_data=lb.fit_transform(labelList) print("y_data:"+str(y_data))

創(chuàng)建決策樹(shù)模型：

#創(chuàng)建決策樹(shù)模型 model=tree.DecisionTreeClassifier(criterion='entropy')#默認(rèn)基尼指數(shù) #輸入數(shù)據(jù)建立模型 model.fit(x_data,y_data)

測(cè)試和預(yù)測(cè)：

x_test=x_data[0] print('x_test:'+str(x_test)) predict=model.predict(x_test.reshape(1,-1)) print("predict:"+str(predict))

導(dǎo)出決策樹(shù)：

import graphviz dot_data=tree.export_graphviz(model,out_file=None,feature_names=vec.get_feature_names(),class_names=lb.classes_,filled=True,rounded=True,special_characters=True) graph=graphviz.Source(dot_data) graph.render('computer')

結(jié)果如下所示：

CART算法

CART決策樹(shù)的生成就是遞歸地構(gòu)建二叉樹(shù)的過(guò)程

CART用基尼（Gini）系數(shù)最小化準(zhǔn)則來(lái)進(jìn)行特征的選擇，生成二叉樹(shù)

GIni系數(shù)計(jì)算：

CART舉例

分別計(jì)算它們的Gini系數(shù)增益，取Gini系數(shù)增益值最大的屬性作為決策樹(shù)的根節(jié)點(diǎn)屬性，根節(jié)點(diǎn)的Gini系數(shù)：

根據(jù)是否有房來(lái)進(jìn)行劃分時(shí)，Gini系數(shù)增益計(jì)算：（左子節(jié)點(diǎn)代表yes，右zi節(jié)點(diǎn)代表no）

計(jì)算婚姻的狀況，由于CART算法是一個(gè)二叉樹(shù)，因此需要把婚姻狀態(tài)分為兩種，如下所示：

根據(jù)年收入進(jìn)行劃分時(shí)，由于年收入是一個(gè)連續(xù)性的數(shù)據(jù)。首要是要將年收入進(jìn)行排序，再計(jì)算相鄰值的中點(diǎn)（平均值），再分別計(jì)算Gini指數(shù)，其結(jié)果如下所示：

由于婚姻狀態(tài)和年收入屬性的最大Gini指數(shù)都為0.12，則假設(shè)選擇婚姻狀況作為根節(jié)點(diǎn)。接下來(lái)，使用同樣的方法，分別計(jì)算剩下的屬性，其根節(jié)點(diǎn)的Gini系數(shù)為：

最后構(gòu)建的CART決策樹(shù)如下所示：

剪枝

剪枝是將一顆子樹(shù)的子節(jié)點(diǎn)全部刪除，根節(jié)點(diǎn)作為葉子節(jié)點(diǎn)，具體如下圖所示：

為什么要剪枝？

決策樹(shù)是充分考慮了所有的數(shù)據(jù)點(diǎn)而生成的復(fù)雜樹(shù)，有可能出現(xiàn)過(guò)擬合的情況，決策樹(shù)越復(fù)雜，過(guò)擬合的程度會(huì)越高。

考慮極端的情況，如果我們令所有的葉子節(jié)點(diǎn)都只含有一個(gè)數(shù)據(jù)點(diǎn)，那么我們能夠保證所有的訓(xùn)練數(shù)據(jù)都能準(zhǔn)確分類(lèi)，但是很有可能得到高的預(yù)測(cè)誤差，原因是將訓(xùn)練數(shù)據(jù)中所有的噪聲數(shù)據(jù)都”準(zhǔn)確劃分”了，強(qiáng)化了噪聲數(shù)據(jù)的作用。

剪枝修剪分裂前后分類(lèi)誤差相差不大的子樹(shù)，能夠降低決策樹(shù)的復(fù)雜度，降低過(guò)擬合出現(xiàn)的概率。

怎樣剪枝？

兩種實(shí)現(xiàn)方案：先剪枝和后剪枝

先剪枝：說(shuō)白了通過(guò)提前停止樹(shù)的構(gòu)建而對(duì)樹(shù)剪枝，一旦停止，該節(jié)點(diǎn)就作為葉子節(jié)點(diǎn)了。

停止決策樹(shù)最簡(jiǎn)單的方法有：

• 定義一個(gè)高度，當(dāng)決策樹(shù)達(dá)到該高度時(shí)就停止決策樹(shù)的生長(zhǎng)
• 達(dá)到某個(gè)節(jié)點(diǎn)的實(shí)例具有相同的特征向量，及時(shí)這些實(shí)例不屬于同一類(lèi)，也可以停止決策樹(shù)的生長(zhǎng)。這個(gè)方法對(duì)于處理數(shù)據(jù)的數(shù)據(jù)沖突問(wèn)題比較有效。
• 定義一個(gè)閾值，當(dāng)達(dá)到某個(gè)節(jié)點(diǎn)的實(shí)例個(gè)數(shù)小于閾值時(shí)就可以停止決策樹(shù)的生長(zhǎng)
• 定義一個(gè)閾值，通過(guò)計(jì)算每次擴(kuò)張對(duì)系統(tǒng)性能的增益，并比較增益值與該閾值大小來(lái)決定是否停止決策樹(shù)的生長(zhǎng)

后剪枝：是在決策樹(shù)生長(zhǎng)完成之后再進(jìn)行剪枝的過(guò)程，后剪枝主要有錯(cuò)誤率降低剪枝(REP)、悲觀剪枝(PEP)和代價(jià)復(fù)雜度剪枝(CCP)三種方法。

1、REP-錯(cuò)誤率降低剪枝

顧名思義，該剪枝方法是根據(jù)錯(cuò)誤率進(jìn)行剪枝，如果一棵子樹(shù)修剪前后錯(cuò)誤率沒(méi)有下降，就可以認(rèn)為該子樹(shù)是可以修剪的。

REP剪枝需要用新的數(shù)據(jù)集，原因是如果用舊的數(shù)據(jù)集，不可能出現(xiàn)分裂后的錯(cuò)誤率比分裂前錯(cuò)誤率要高的情況。由于使用新的數(shù)據(jù)集沒(méi)有參與決策樹(shù)的構(gòu)建，能夠降低訓(xùn)練數(shù)據(jù)的影響，降低過(guò)擬合的程度，提高預(yù)測(cè)的準(zhǔn)確率。

2、PEP-悲觀剪枝

悲觀剪枝認(rèn)為如果決策樹(shù)的精度在剪枝前后沒(méi)有影響的話，則進(jìn)行剪枝。怎樣才算是沒(méi)有影響？如果剪枝后的誤差小于剪枝前經(jīng)度的上限，則說(shuō)明剪枝后的效果與剪枝前的效果一致，此時(shí)要進(jìn)行剪枝。

進(jìn)行剪枝必須滿足以下條件：

其中：

表示剪枝前子樹(shù)的誤差

表示剪枝后節(jié)點(diǎn)的誤差

兩者的計(jì)算公式如下所示：

，其中
，其中N為子樹(shù)的數(shù)據(jù)量。

上述公式中，0.5表示修正因子。由于子節(jié)點(diǎn)是父節(jié)點(diǎn)進(jìn)行分裂的結(jié)果，從理論上講，子節(jié)點(diǎn)的分類(lèi)效果總比父節(jié)點(diǎn)好，分類(lèi)的誤差更小，如果單純通過(guò)比較子節(jié)點(diǎn)和父節(jié)點(diǎn)的誤差進(jìn)行剪枝就完全沒(méi)有意義了，因此對(duì)節(jié)點(diǎn)的誤差計(jì)算方法進(jìn)行修正。修正的方法是給每一個(gè)節(jié)點(diǎn)都加上誤差修正因子0.5，在計(jì)算誤差的時(shí)候，子節(jié)點(diǎn)由于加上了誤差修正因子，就無(wú)法保證總誤差低于父節(jié)點(diǎn)。

例如：

所以應(yīng)該進(jìn)行剪枝。

3、CCP-代價(jià)復(fù)雜度剪枝

代價(jià)復(fù)雜度選擇節(jié)點(diǎn)表面誤差率增益值最小的非葉子節(jié)點(diǎn)，刪除該非葉子節(jié)點(diǎn)的左右子節(jié)點(diǎn)，若有多個(gè)非葉子節(jié)點(diǎn)的表面誤差率增益值相同小，則選擇非葉子節(jié)點(diǎn)中子節(jié)點(diǎn)數(shù)最多的非葉子節(jié)點(diǎn)進(jìn)行剪枝。

CART算法實(shí)現(xiàn)

數(shù)據(jù)集為例子中的數(shù)據(jù)。

需要進(jìn)行數(shù)據(jù)預(yù)處理，將文字設(shè)置為數(shù)字形式。其結(jié)果如下圖所示：

導(dǎo)包：

from sklearn import tree import numpy as np

載入數(shù)據(jù)：

data=np.genfromtxt("cart.csv",delimiter=",") x_data=data[1:,1:-1] y_data=data[1:,-1]

構(gòu)建決策樹(shù):

model=tree.DecisionTreeClassifier() #不傳遞參數(shù)的話，默認(rèn)就是CART算法 #輸入數(shù)據(jù)建立模型 model.fit(x_data,y_data)

導(dǎo)出決策樹(shù)：

import graphviz dot_data=tree.export_graphviz(model,out_file=None,feature_names=['house_yes','house_no','single','married','divorced','income'],class_names=['no','yes'],filled=True,rounded=True,special_characters=True) graph=graphviz.Source(dot_data) graph.render('cart')

其結(jié)果如下圖所示：

參考：https://www.cnblogs.com/mdumpling/p/8087396.html

參考：https://zhuanlan.zhihu.com/p/267368825

參考視頻：https://www.bilibili.com/video/BV1Rt411q7WJ?p=47&vd_source=166e4ef02c5e9ffa3f01c2406aec1508

總結(jié)

以上是生活随笔為你收集整理的机器学习笔记-决策树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。