決策樹
4.1 基本流程
決策樹基于樹結(jié)構(gòu)來進(jìn)行決策的淋淀。決策樹的基本形式如下:
有關(guān)于節(jié)點:
根節(jié)點:最上面的節(jié)點,沒有進(jìn)只有出覆醇,只有一個朵纷。
中間節(jié)點:既有進(jìn)也有出炭臭。進(jìn)去只有一條,出去可以有很多條袍辞。
葉節(jié)點:有進(jìn)無出鞋仍。
子節(jié)點與父節(jié)點:相鄰的節(jié)點,更靠近根節(jié)點的是父節(jié)點搅吁,另一個是子節(jié)點威创。
4.2 劃分選擇
決策樹學(xué)習(xí)的關(guān)鍵是如何選擇最優(yōu)劃分屬性。隨著劃分的進(jìn)行谎懦,我們希望決策樹的分支節(jié)點包含的樣本盡可能屬于同一類別肚豺,即節(jié)點的純度越來越高。
4.2.1 ID3算法:信息增益
信息熵:度量樣本集合純度最常用的一種指標(biāo)界拦。
假定當(dāng)前樣本集合D中第類k樣本所占的比例為p_k吸申,則D的信息熵定義為:
約定:當(dāng)p=0時,p\log_2p=0寞奸。Ent(D)的最大值是\log_2|y|呛谜,最小值是0在跳。
信息增益越大枪萄,意味著使用屬性a劃分獲得的純度提升越大,因此可以用信息增益來進(jìn)行決策樹的劃分屬性選擇猫妙。
以下面這個表的數(shù)據(jù)進(jìn)行舉例:
表中共17個樣例瓷翻,包含8個正例和9個反例,其中共6劃分個屬性割坠。這是個二分類任務(wù)齐帚,顯然|y|=2。整個過程如下:
-
首先計算根節(jié)點的信息熵:
-
依次計算每個屬性的信息增益:
- “色澤”屬性有三個屬性值彼哼,以此屬性對D進(jìn)行劃分可得3個子集对妄,分別記為D1(色澤=青綠),D2(色澤=烏黑),D3(色澤=淺白)。其中敢朱,子集D1有6個樣例剪菱,包括3個正例和3個反例;子集D2有6個樣例拴签,包括4個正例和2個反例孝常;子集D3有5個樣例,包括1個正例和4個反例蚓哩。分別計算劃分后的3個分支節(jié)點的信息熵為:
-
計算屬性“色澤”的信息增益:
-
計算其余5個屬性的信息增益:
-
選擇信息增益最大的屬性作為劃分屬性:
這6個屬性里面构灸,選擇“紋理”作為劃分屬性:
-
得到上面的第一層中間節(jié)點后,繼續(xù)進(jìn)行劃分:
-
在“紋理”為“清晰”的節(jié)點中岸梨,共包含9個樣例喜颁。其中7個正例稠氮,2個反例。計算此時的信息熵:
-
計算屬性“根蒂”的各個子集的信息熵:
根蒂包含三個屬性半开,可形成3個子集括袒,分別為D{11}(根蒂=蜷縮),D{12}(根蒂=稍縮),D^{13}(根蒂=硬挺)项乒,其信息熵分別為:
-
計算屬性“根蒂”的信息增益:
-
以同樣的方法對其余的4個屬性計算信息增益:
可見退疫,“根蒂”望伦、“臍部”和“觸感”3個屬性的信息增益最大且相同舍悯,因此涝滴,可任選其一作為劃分屬性吧黄。由于“根蒂”中的屬性值“蜷縮”和“硬挺”均只對應(yīng)一個標(biāo)簽肺魁,而“稍縮”里面既有好瓜也有壞瓜添瓷,因此“蜷縮”和“硬挺”下面不再進(jìn)行劃分渺蒿,均屬于葉節(jié)點痢士。而“稍縮”還要繼續(xù)進(jìn)行劃分。
-
按同樣的方法繼續(xù)對“紋理”下面的“稍糊”和“模糊”屬性進(jìn)行劃分茂装,得到下面的決策樹:
-
4.2.2 C4.5算法:增益率
信息增益準(zhǔn)則對可取值數(shù)目較多的屬性有所偏好怠蹂,為減少此種偏好帶來的不利影響,C4.5決策樹算法使用增益率選擇最優(yōu)的劃分屬性少态。
增益率的定義為:
稱為屬性a的固有值城侧。屬性a的可能取值數(shù)目越多,即V越大彼妻,則IV(a)的值會越大嫌佑。
信息率準(zhǔn)則對可取值數(shù)目較少的屬性有所偏好,為減少此種偏好帶來的不利影響侨歉,C4.5決策樹算法先從候選劃分屬性中找出信息增益高于平均水平的屬性屋摇,再從中選擇增益率最高的屬性作為劃分屬性。
4.2.3 CART算法:基尼指數(shù)
CART算法使用基尼指數(shù)來選擇劃分屬性幽邓。數(shù)據(jù)集D的純度用基尼指數(shù)度量:
基尼指數(shù)反映了從數(shù)據(jù)集中隨機(jī)抽取兩個樣本炮温,其類別標(biāo)記不一致的概率。因此牵舵,基尼指數(shù)越小柒啤,數(shù)據(jù)集的純度越高。
屬性a的基尼指數(shù)定義為:
我們在候選屬性集合A中棋枕,選擇基尼指數(shù)最小的屬性作為劃分屬性白修。
4.3 剪枝
決策樹為了盡可能分類正確訓(xùn)練樣例,會不斷的劃分節(jié)點重斑,導(dǎo)致分支過多兵睛,造成嚴(yán)重的過擬合。剪枝是決策樹算法解決過擬合的主要手段。
剪枝的基本策略有預(yù)剪枝和后剪枝祖很。
采用留出法作為驗證決策樹的泛化能力笛丙。對前面的西瓜數(shù)據(jù)集進(jìn)行劃分,一部分用于訓(xùn)練集假颇,另一部分作為驗證集胚鸯,如下圖,雙橫線上面是訓(xùn)練集笨鸡,下面是驗證集:
采用ID3算法姜钳,用此訓(xùn)練集產(chǎn)生如下的決策樹:
4.3.1 預(yù)剪枝
預(yù)剪枝:在決策樹生成過程中,對每個節(jié)點在劃分前先進(jìn)行估計形耗,若當(dāng)前節(jié)點的劃分不能帶來泛化能力的提升哥桥,則停止劃分并將當(dāng)前結(jié)點作為葉結(jié)點。
在劃分前激涤,若將所有“臍部”屬性的樣本均標(biāo)記為好瓜拟糕,則在驗證集進(jìn)行驗證時,第4倦踢、5送滞、8樣例分類正確而第9、11辱挥、12犁嗅、13樣例分類錯誤,此時驗證集精度為\frac{3}{7}\times100%=42.9%般贼。
基于ID3算法愧哟,按照“臍部”的屬性值劃分后奥吩,根據(jù)“凹陷”哼蛆、“稍凹”和“平坦”在訓(xùn)練集中樣例的正例數(shù)量,將“凹陷”霞赫、“稍凹”和“平坦”分別標(biāo)記為“好瓜”腮介、“好瓜”和“壞瓜”的葉結(jié)點。此時在驗證集進(jìn)行驗證時端衰,第4叠洗、5、8旅东、11灭抑、12樣例分類正確而第9、13樣例分類錯誤抵代,此時驗證集精度為\frac{5}{7}\times100%=71.4%腾节。劃分前后,驗證集精度明顯上升(42.9%<71.4%),因此“臍部”進(jìn)行劃分是可以的案腺。
基于ID3算法庆冕,繼續(xù)對節(jié)點②進(jìn)行劃分,選擇的信息增益最大的屬性是“色澤”劈榨。根據(jù)上圖的決策樹访递,使用“色澤”劃分后,將“淺白”劃分為壞瓜同辣,因此在驗證集上拷姿,會將第5樣例分類錯誤,這樣原來5個分類正確的樣例數(shù)旱函,現(xiàn)在變成了4個跌前,此時驗證集精度為\frac{4}{7}\times100%=57.1%。精度變小陡舅,于是禁止節(jié)點②進(jìn)行劃分抵乓。
基于ID3算法,繼續(xù)對節(jié)點③進(jìn)行劃分靶衍,選擇的信息增益最大的屬性是“根蒂”灾炭。劃分后,驗證集中颅眶,樣例8仍是驗證正確蜈出,樣例9仍是驗證錯誤,因此驗證集精度不變涛酗,仍是71.4%铡原,于是禁止對節(jié)點③進(jìn)行劃分。
對于節(jié)點④商叹,所含樣本均是同一類燕刻,已經(jīng)是葉結(jié)點,不再進(jìn)行劃分剖笙。
剪枝后的決策樹如下:
可見卵洗,預(yù)剪枝使得很多分支未展開,顯著降低了過擬合的風(fēng)險弥咪,也降低了訓(xùn)練時間和驗證時間開銷过蹂。但有些分支當(dāng)前劃分雖然不能提升泛化性能甚至導(dǎo)致泛化性能下降,但在其基礎(chǔ)上進(jìn)行的后續(xù)劃分卻可能導(dǎo)致性能提升聚至,因此預(yù)剪枝為決策樹可能帶來欠擬合的風(fēng)險酷勺。
4.3.2 后剪枝
后剪枝:先從訓(xùn)練集生成一棵完整的樹,然后自底向上對非葉節(jié)點進(jìn)行考察扳躬,若將該結(jié)點對應(yīng)的字樹替換為葉結(jié)點能帶來決策樹泛化性能的提升脆诉,則將該結(jié)點替換為葉結(jié)點勋功。
對于上上圖中的決策樹,用驗證集測試库说,會得到分類正確的樣例4狂鞋、11、12潜的,其余分類錯誤骚揍,這樣驗證集精度為42.69%。
首先對結(jié)點6啰挪,將其分支檢剪除信不,即把其替換為葉結(jié)點,此時驗證集精度提升為57.1%亡呵。
然后對結(jié)點5抽活,把其替換為葉結(jié)點,此時驗證集精度仍為57.1%不變锰什,因此可以不進(jìn)行剪枝下硕。
對結(jié)點2,把其替換為葉結(jié)點汁胆,此時驗證集精度為71.4%梭姓,因此可以進(jìn)行剪枝。
同理對結(jié)點3和1嫩码,把其替換為葉結(jié)點誉尖,此時驗證集精度分別為71.4%和42.9%,不進(jìn)行剪枝铸题。
通常铡恕,后剪枝決策樹的欠擬合風(fēng)險小,泛化性能往往優(yōu)于預(yù)剪枝決策樹丢间,但后剪枝訓(xùn)練時間開銷比未剪枝決策樹和預(yù)剪枝決策樹要大很多探熔。
4.4 連續(xù)與缺失值
4.4.1 連續(xù)值處理
對于連續(xù)屬性,可取數(shù)目不再有限千劈,此時需要使用連續(xù)屬性離散化技術(shù)祭刚。最簡單的策略是采用二分法。
對于樣本數(shù)據(jù)集D和連續(xù)屬性a墙牌,假設(shè)a在D上出現(xiàn)了n個不同的取值,將這些值從小到大進(jìn)行排序暗甥,記為{a1,a2,\dots,a^n}喜滨。劃分點T_a表示為:
也就是說,把區(qū)間[ai,a{i+1})的中位點作為候選劃分點撤防∷浞纾可將劃分點設(shè)為該屬性在訓(xùn)練集中出現(xiàn)的不大于中位點的點,例如中位點是0.5185,可將0.518作為劃分點辜膝。此時:
作為示例无牵,在原有的西瓜數(shù)據(jù)集上增加“密度”和“含糖量”兩個屬性:
對于屬性“密度”,將這17個屬性值從小到大進(jìn)行排序厂抖,得到{0.243, 0.245, 0.343, 0.36, 0.403, 0.437, 0.481, 0.556, 0.593, 0.608, 0.634, 0.639, 0.657, 0.666, 0.697, 0.719, 0.774}茎毁,然后相鄰的兩個值取平均值作為劃分點,得到16個劃分點:{0.244 0.294 0.3515 0.3815 0.42 0.459 0.5185 0.5745 0.6005 0.621 0.6365 0.648 0.6615 0.6815 0.708 0.7465}忱辅。然后計算屬性“密度”的信息增益為0.262七蜘,對應(yīng)的劃分點為0.381。
同理對屬性“含糖率”墙懂,得到信息增益為0.349橡卤,對應(yīng)劃分點為0.126。
結(jié)合前面的離散數(shù)據(jù)的6個信息增益损搬,總體上碧库,還是以信息增益最大的“紋理”作為根結(jié)點,此后結(jié)點劃分過程遞歸進(jìn)行巧勤,得到如下決策樹:
需要注意的是谈为,不同于離散屬性,連續(xù)屬性可以作為其后代結(jié)點的劃分屬性踢关。
4.4.2 缺失值處理
有的樣本數(shù)據(jù)集缺失屬性值數(shù)據(jù)伞鲫,如果直接去掉有缺失值的樣本,那么會造成極大的浪費签舞。含有缺失值的樣例集的處理方法如下:
以屬性“色澤”為例秕脓,該屬性無缺失值的樣本集包括\vec{D}={2,3,4,6,7,8,9,10,11,12,14,15,16,17},計算其信息熵為:
“色澤”屬性包含3個屬性值“青綠”、“烏黑”及“淺白”儒搭,分別計算其信息熵為:
因此樣本集\vec{D}上的屬性“色澤”的信息增益為:
再求出樣本集D上“色澤”屬性的信息增益:
同樣地吠架,計算出所有屬性在D上的信息增益:
因此,以“紋理”作為根結(jié)點進(jìn)行劃分搂鲫,按照3個屬性值劃分成3個子節(jié)點傍药,分別包含7個、5個和3個樣例魂仍。注意拐辽,由于第8個樣例在“紋理”上缺乏屬性值,因此將它們同時加入三個子節(jié)點里面擦酌,但其權(quán)重分別為7/15俱诸、5/15、3/15赊舶。第10個樣例同理睁搭。
最終得到的決策樹如下:
4.5 多變量決策樹
決策樹所形成的分類邊界有一個明顯的特點赶诊,即軸平行,它的分類邊界由若干個與坐標(biāo)軸平行的分段組成园骆。
例如舔痪,如下的西瓜數(shù)據(jù)集:
對應(yīng)的決策樹及分類邊界如下:
這樣的分類邊界使得學(xué)習(xí)結(jié)果有很好的可解釋性,但在學(xué)習(xí)任務(wù)的真實分類邊界比較復(fù)雜時锌唾,必須使用很多段劃分才能得到較好的近似锄码,時間開銷很大。如果能使用斜的邊界鸠珠,決策樹模型將大為簡化巍耗,例如下面的紅色曲線:
多變量決策樹:可以實現(xiàn)斜著劃分甚至更復(fù)雜劃分的決策樹。
在此類決策樹中渐排,非葉結(jié)點不再是單個屬性炬太,而是多個屬性的線性組合,每個非葉結(jié)點都是\sum_{i=1}^j3gxi77w_ia_i=t的線性組合驯耻。例如同樣是對于上面的數(shù)據(jù)集亲族,學(xué)得下面的多變量決策樹,分類邊界是:
4.6 決策樹
import graphviz
import pandas as pd
from sklearn import tree
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
wine = load_wine()
wine.data.shape # 樣本數(shù)據(jù)可缚,(178, 13)
wine.feature_names # 屬性名霎迫,共13個屬性
wine.target_names # 三分類
pd.concat([pd.DataFrame(wine.data), pd.DataFrame(wine.target)], axis=1) # 查看整個表的數(shù)據(jù)
Xtrain, Xtest, Ytrain, Ytest = train_test_split(wine.data,wine.target,test_size=0.3) # 分出訓(xùn)練集及驗證集
wine_tree = tree.DecisionTreeClassifier(criterion="entropy"
,random_state=10
,splitter="best"
)
wine_tree = wine_tree.fit(Xtrain, Ytrain)
score = wine_tree.score(Xtest, Ytest) # 驗證分類準(zhǔn)確率
score # 0.926
# 畫出決策樹
dot_data = tree.export_graphviz(wine_tree
,feature_names=wine.feature_names
,class_names=wine.target_names
,filled=True
,rounded=True
)
graph = graphviz.Source(dot_data)
graph
[*zip(wine.feature_names, wine_tree.feature_importances_)] # 查看各個屬性的重要程度
'''
[('alcohol', 0.3105469459665367),
('malic_acid', 0.04914102355800148),
('ash', 0.021703756013797745),
('alcalinity_of_ash', 0.0),
('magnesium', 0.039325800285971386),
('total_phenols', 0.0),
('flavanoids', 0.36843622950210064),
('nonflavanoid_phenols', 0.014236961139536255),
('proanthocyanins', 0.0),
('color_intensity', 0.049683554827815106),
('hue', 0.025088839146435126),
('od280/od315_of_diluted_wines', 0.06244719458516666),
('proline', 0.059389694974638946)]
可見,有3個屬性未派上用場
'''
graph.render('tree.png', view=True)