決策樹本質(zhì)上是一個(gè)classfication 問(wèn)題的監(jiān)督學(xué)習(xí)算法，其結(jié)構(gòu)上分為根節(jié)點(diǎn)和葉節(jié)點(diǎn)塌西，底層python 的實(shí)現(xiàn)可以參考機(jī)器學(xué)習(xí)實(shí)戰(zhàn)一書脖阵，本質(zhì)上是一個(gè)遞歸實(shí)現(xiàn)。
- 偽代碼的介紹
假定一個(gè)訓(xùn)練集合D={（x1,y1),(x2,y2),...,(xm,ym)};
屬性集合A={a1,a2,...,ad}.
有三種情況下荷辕，導(dǎo)致遞歸直接返回結(jié)果：（1)當(dāng)前節(jié)點(diǎn)包含的樣本全部屬于同一個(gè)類別，無(wú)需進(jìn)行劃分件豌；（2)當(dāng)前屬性為空疮方，或者是所有樣本在所有的屬性上的取值相等，無(wú)法劃分茧彤；（3)當(dāng)前節(jié)點(diǎn)包含的樣本集合為空骡显，不能劃分
- 決策樹劃分的原則和定量值
一般而言，隨著劃分的不斷進(jìn)行曾掂，希望決策樹的分支點(diǎn)所包含的樣本盡可能的屬于同一類別惫谤，即節(jié)點(diǎn)的純度要高，衡量純度的標(biāo)準(zhǔn)為信息熵
信息熵有如下的定義：假定樣本集合D中的第x類樣本所占的比例之和為px珠洗，則D的信息熵為：
假定離散屬性a有V個(gè)可能的取值{a1,a2,...,av}溜歪，若使用a對(duì)樣本集合D來(lái)進(jìn)行劃分，則會(huì)產(chǎn)生v個(gè)分支節(jié)點(diǎn)许蓖，其中第v個(gè)分支節(jié)點(diǎn)包含了D中所有在屬性a上取值為av的樣本蝴猪，記作Dv，且考慮到不同的分支節(jié)點(diǎn)所包含的樣本數(shù)不同膊爪，給分支節(jié)點(diǎn)賦予權(quán)重|Dv|/|D|自阱，即樣本數(shù)越多的分支節(jié)點(diǎn)的影響越大
Gain(D,a)=H[x]-(v=1到v=v的和）|Dv|/|D|*Ent(Dv)
具體來(lái)講，當(dāng)有多個(gè)屬性米酬，每一個(gè)屬性都對(duì)應(yīng)多個(gè)屬性值沛豌，那么就計(jì)算每一個(gè)屬性的信息熵，哪一個(gè)屬性的信息熵大赃额，則選擇該屬性為決策樹的節(jié)點(diǎn)
- 增益率
在周志華p78有一個(gè)例子加派，判斷是否為好瓜阁簸，有17個(gè)樣本，把每一個(gè)樣本進(jìn)行編號(hào)哼丈，作為一列，如果把該列也作為屬性筛严，那么它的信息增益應(yīng)該最大醉旦，因?yàn)檫@樣決策樹就會(huì)產(chǎn)生17個(gè)分支，每一個(gè)分支的節(jié)點(diǎn)就包含一個(gè)樣本桨啃，純度達(dá)到最大车胡，這樣的決策樹準(zhǔn)確率高，但是不具備泛化能力照瘾，無(wú)法對(duì)新樣本進(jìn)行有效的預(yù)測(cè)
增益率的公式為：
Gain_ratio(D,a)=Gain(D,a)/IV(a)
其中匈棘，iv(a)=-(v=1到v=v的和）|Dv|/|D|*log2|Dv|/|D| (C4.5算法）
- 基尼指數(shù)（CART Classification and regression Tree 的簡(jiǎn)稱，這是一種著名決策樹的學(xué)習(xí)算法析命，分類和回歸都可以使用）
其中屬性a的基尼指數(shù)定義為:
Gini_index(D,a)=(v=1 到v=v的和)|Dv|/|D|Gini(Dv)
- 對(duì)過(guò)擬合的解決方法
采用預(yù)剪枝/后剪枝的方法來(lái)進(jìn)行處理
周志華p81-p83對(duì)于此講解十分清楚主卫，感興趣可以去拜讀一下
下面介紹sklearn 官方文檔
- criterion 可以使用"gini"或者"entropy"，前者就是上文代表的基尼系數(shù)鹃愤，后者代表信息增益簇搅。一般說(shuō)使用默認(rèn)的基尼系數(shù)"gini"就可以了，即CART算法软吐。
- splitter 可以使用"best"或者"random"瘩将。前者在特征的所有劃分點(diǎn)中找出最優(yōu)的劃分點(diǎn)。后者是隨機(jī)的在部分劃分點(diǎn)中找局部最優(yōu)的劃分點(diǎn)凹耙。 默認(rèn)的"best"適合樣本量不大的時(shí)候姿现，而如果樣本數(shù)據(jù)量非常大，此時(shí)決策樹構(gòu)建推薦"random"
- max_depth 決策樹的最大深度肖抱， 決策樹的最大深度备典，默認(rèn)可以不輸入，如果不輸入的話虐沥，決策樹在建立子樹的時(shí)候不會(huì)限制子樹的深度熊经。一般來(lái)說(shuō)，數(shù)據(jù)少或者特征少的時(shí)候可以不管這個(gè)值欲险。如果模型樣本量多镐依，特征也多的情況下，推薦限制這個(gè)最大深度天试，具體的取值取決于數(shù)據(jù)的分布槐壳。常用的可以取值10-100之間
- min_samples_split 這個(gè)值限制了子樹繼續(xù)劃分的條件，如果某節(jié)點(diǎn)的樣本數(shù)少于min_samples_split喜每，則不會(huì)繼續(xù)再嘗試選擇最優(yōu)特征來(lái)進(jìn)行劃分务唐。 默認(rèn)是2 如果樣本量不大雳攘，不需要管這個(gè)值。如果樣本量數(shù)量級(jí)非常大枫笛，則推薦增大這個(gè)值
- min_samples_leaf 這個(gè)值限制了葉子節(jié)點(diǎn)最少的樣本數(shù)吨灭，如果某葉子節(jié)點(diǎn)數(shù)目小于樣本數(shù)，則會(huì)和兄弟節(jié)點(diǎn)一起被剪枝刑巧。 默認(rèn)是1,可以輸入最少的樣本數(shù)的整數(shù)
- min_weight_fraction_leaf 這個(gè)值限制了葉子節(jié)點(diǎn)所有樣本權(quán)重和的最小值喧兄，如果小于這個(gè)值，則會(huì)和兄弟節(jié)點(diǎn)一起被剪枝啊楚。 默認(rèn)是0吠冤，就是不考慮權(quán)重問(wèn)題。一般來(lái)說(shuō)恭理，如果我們有較多樣本有缺失值拯辙，或者分類樹樣本的分布類別偏差很大，就會(huì)引入樣本權(quán)重颜价，這時(shí)我們就要注意這個(gè)值了涯保。
- max_leaf_nodes 通過(guò)限制最大葉子節(jié)點(diǎn)數(shù)，可以防止過(guò)擬合拍嵌，默認(rèn)是"None”遭赂，即不限制最大的葉子節(jié)點(diǎn)數(shù)。如果加了限制横辆，算法會(huì)建立在最大葉子節(jié)點(diǎn)數(shù)內(nèi)最優(yōu)的決策樹撇他。如果特征不多，可以不考慮這個(gè)值狈蚤，但是如果特征分成多的話困肩，可以加以限制，具體的值可以通過(guò)交叉驗(yàn)證得到脆侮。
- max_features The number of features to consider when looking for the best split 用于劃分選取的最大特征值的個(gè)數(shù)
methods
- apply(X, check_input=True) Returns the index of the leaf that each sample is predicted as.
- decision_path(X, check_input=True) Return the decision path in the tree
- fit(X, y, sample_weight=None, check_input=True, X_idx_sorted=None) 其中锌畸，X為樣本集合，y為所屬的類標(biāo)簽靖避，參數(shù)sample_weight 為樣本的權(quán)重潭枣，默認(rèn)為None,權(quán)重相同
- get_params(deep=True) 得到評(píng)估器的參數(shù)，deep 默認(rèn)為True ,表示輸出所有參數(shù)
- predict_log_proba(X) Predict class log-probabilities of the input samples X. 得到預(yù)測(cè)屬于某一類別的log 值
- predict_proba(X, check_input=True) Predict class probabilities of the input samples X 得到預(yù)測(cè)屬于某一類別的值
- score(X, y, sample_weight=None) X為測(cè)試集幻捏， y為測(cè)試集的真實(shí)的類別標(biāo)簽盆犁，返回的是測(cè)試結(jié)果準(zhǔn)確度（即多少判斷正確，多少判斷錯(cuò)誤）
下面來(lái)看一個(gè)簡(jiǎn)單的demo
import sklearn
from sklearn import tree#輸出決策樹
x=[[0,0],[2,2]]
y=[0,1]
clf=tree.DecisionTreeClassifier()#這是用于進(jìn)行分類問(wèn)題
clf=clf.fit(x,y)
#print (clf.predict_proba([[1,1]]))
#print (clf.apply(x)) 返回葉節(jié)點(diǎn)所在位置的索引
#print (clf.predict([[3,4]]))
x=[[0,0],[2,2]]
y=[0.5,2.5]#注意這時(shí)候標(biāo)簽是浮點(diǎn)類型的篡九，且是不連續(xù)的
clf=tree.DecisionTreeRegressor()#就要用到回歸決策樹分類器
clf=clf.fit(x,y)
#print (clf.predict_proba([[1,1]]))
#print (clf.apply(x)) 返回葉節(jié)點(diǎn)所在位置的索引
print (clf.predict([[3,4]]))
最后是一個(gè)官方的實(shí)例谐岁，結(jié)合matplotlib的呈現(xiàn)
import sklearn
from sklearn.tree import DecisionTreeRegressor#輸出回歸決策樹
import numpy as np
import matplotlib.pyplot as plt
rng=np.random.RandomState(1)#其中1為偽隨機(jī)種子。只要隨機(jī)種子一樣，那么生成的序列就相同
x=np.sort(5*rng.rand(80,1),axis=0)#其中random.rand 的用處是生成一個(gè)指定形狀的數(shù)組伊佃，np.sort 參數(shù)axis默認(rèn)為-1窜司，表示按照最后一行排序
#print (x) 最終生成了一組80個(gè)由小到大排列的數(shù)
"""
>>> a = np.array([[1,4],[3,1]])
>>> np.sort(a) # sort along the last axis
array([[1, 4],
[1, 3]])
>>> np.sort(a, axis=None) # sort the flattened array
array([1, 1, 3, 4])
>>> np.sort(a, axis=0) # sort along the first axis
array([[1, 1],
[3, 4]])
"""
y=np.sin(x).ravel()#np.sin(np.pi/2)得到[[1]],ravel的作用是降維的作用
y[::5]+=3*(0.5-rng.rand(16))# 80/5=16 利用rand 產(chǎn)生16個(gè)一維數(shù)組
# #print (y)
regr_1=DecisionTreeRegressor(max_depth=2)
regr_2=DecisionTreeRegressor(max_depth=5)#產(chǎn)生兩個(gè)深度不同的樹
regr_1.fit(x,y)
regr_2.fit(x,y)#分別訓(xùn)練兩棵樹
#ppredict
x_test=np.arange(0.0,5.0,0.01)[:,np.newaxis]#將1行多列的數(shù)組轉(zhuǎn)化為多行一列的數(shù)組
y_1=regr_1.predict(x_test)
y_2=regr_2.predict(x_test)
#picture
plt.figure()#畫布搭建
plt.scatter(x,y, s=20,marker='<',edgecolor='black',c='darkorange',label='data')
"""
其中的s可以理解為點(diǎn)的大小，c為顏色序列,當(dāng)有多個(gè)點(diǎn)的時(shí)候航揉，可以接受一個(gè)顏色組成的列表塞祈，每個(gè)點(diǎn)的顏色按照序列顏色生成
marker 表示生成的點(diǎn)的形狀，默認(rèn)為'o'
label 圖像標(biāo)簽
"""
plt.plot(x_test, y_1, color="cornflowerblue",label="max_depth=2", linewidth=2)
plt.plot(x_test, y_2, color="yellowgreen", label="max_depth=5", linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()
最終的圖像展示如下
未完待續(xù)帅涂。织咧。。漠秋。。抵屿。
