目錄：
1.決策樹簡介
2.決策樹生成
a) 選擇標準——熵
b) 信息增益——ID3算法
c) 信息增益率——C4.5算法
d) Gini系數(shù)——CART算法
e) 評價標準——評價函數(shù)
-
3.剪枝操作
- a) 預剪枝
- b) 后剪枝
4.決策樹的集成——隨機森林
-
5.Sklearn構(gòu)造決策樹
- a) 數(shù)據(jù)包介紹
- b) 5行代碼構(gòu)造決策樹
- c) 參數(shù)簡介
1.決策樹簡介
決策樹概念：決策樹(Decision Trees)是一種非參監(jiān)督學習方法映跟，即沒有固定的參數(shù)爬橡，對數(shù)據(jù)進行分類或回歸學習缰盏。決策樹的目標是從已知數(shù)據(jù)中學習得到一套規(guī)則，能夠通過簡單的規(guī)則判斷，對未知數(shù)據(jù)進行預測。這里我們只討論決策樹分類的功能袁勺。
決策樹組成：根節(jié)點、非葉子節(jié)點（也叫決策點畜普、子節(jié)點期丰、內(nèi)部節(jié)點）、分支（有向邊）吃挑、葉子節(jié)點（葉節(jié)點）钝荡。其中非葉子節(jié)點是一個分支的終點，無法繼續(xù)分離舶衬。
決策流程：所有的數(shù)據(jù)埠通，從根節(jié)點開始，根據(jù)某一特征的條件進行分配逛犹，進入不同的子節(jié)點端辱，不斷遞歸，最終到達葉子節(jié)點停止虽画。例如下圖是一個判斷一家人誰愛玩游戲的決策樹舞蔽。
2.決策樹的生成
a.選擇標準——熵
決策樹很重要的一個問題是選擇什么條件和特征來進行分類。舉個相親的例子：當決定是否要與一個相親的對象見面時码撰，會有一些硬性的標準渗柿，比如年齡、長相等灸拍，也有一些次要的條件做祝，比如是否是公務員等。和這些標準一樣鸡岗，決策樹中也要選擇重要的條件和特征進行分類混槐，這種重要性用熵來表示。
熵(entropy)：在高中化學中表示物體內(nèi)部的混亂程度轩性。在概率統(tǒng)計中声登，表示隨機變量不確定性的程度。熵越大，越不確定悯嗓；熵越接近于0件舵，越確定。舉個數(shù)組的例子「現(xiàn)在有AB兩個數(shù)組：
A=[1,2,3,4,2,3,5]
B=[1,1,1,1,2,1,2]
A中數(shù)字多铅祸，且混亂，而B中主要都是1合武，偶爾出現(xiàn)2临梗，那么就說A比較混亂，不確定性大稼跳，B比較整潔盟庞，比較確定。那么A的熵值高汤善，B的熵低什猖。在決策樹中，我們希望數(shù)據(jù)經(jīng)過一個分支分類后红淡，盡量被分離得清晰整潔不狮，像B一樣。熵用數(shù)學公式來表達如下：
它表示選用某個特征條件進行分類后在旱，分類結(jié)果的混亂程度荤傲。其中P代表一個條件下發(fā)生的概率。P=0時颈渊，定義熵H=0遂黍。所以無論P接近0或者1，H都接近0俊嗽，此時數(shù)據(jù)結(jié)論趨向一致雾家，混亂度低。例如將B數(shù)組進行分類绍豁，得到[1,1,1,1,1]和[2,2]兩個葉子節(jié)點芯咧，那么根節(jié)點的熵為：
有了衡量標準竹揍，那么構(gòu)造決策樹的思路也就有了：隨著樹深度的增加，讓節(jié)點熵迅速降低芬位。省略掉一些沒有實際意義的特征，最終得到一棵最矮的決策樹昧碉。那么就產(chǎn)生了ID3算法揽惹。
b.信息增益——ID3算法
舉個分類的例子
在outlook中，一共有14種情況四康，9個yes和5個no搪搏，那么根節(jié)點的信息熵為：
經(jīng)過分類后，形成了三個葉子節(jié)點闪金，此時相當于已知兩個隨機變量X疯溺，Y，求聯(lián)合概率分布下的熵：
根據(jù)此公式哎垦，先計算各葉子節(jié)點中的熵：
Outlook=sunny時喝检，H1=0.971
Outlook=overcast時，H2=0
Outlook=rainy時撼泛，H3=0.971
再計算分類后的熵：5/140.971+4/140+5/14*0.971=0.693
這樣熵下降了：0.940-0.693=0.247
分類前與分類后，熵的差值澡谭，叫做信息增益：
**
**
它表示特征A對訓練集D的信息增益愿题。因此，我們計算各個分類方法的信息增益蛙奖，選出最gain(D,A)最大的作為分類條件潘酗，即可讓總體的熵下降最快。這也是ID3算法的核心思想雁仲。
c.信息增益率——C4.5算法
但是信息增益也有行不通的時候仔夺。舉一個極端的反例。假設每個樣本都帶有一個不重復的ID攒砖，用這些ID作為分類條件缸兔，可以一步就完成分類，這種分類方法的熵為0吹艇，信息增益很大惰蜜。但是用這種條件進行分類顯然是不靠譜的。因此受神，可能存在某個條件抛猖，分出的種類非常多，每個種類的樣本非常少鼻听。為了解決這個問題财著，提出了信息增益率（也叫信息增益比），它等于信息增益除以自身熵：
**
**
如果分類很快撑碴，分布很廣的情況發(fā)生撑教，雖然方法的信息增益較大，但是自身的熵也會很大驮履，信息增益與自身熵的比就會很小玫镐。因此，使用信息增益率來作決策杜跷，能夠有效地排除上述這種特殊情況葛闷。
d.Gini系數(shù)——CART算法
同樣淑趾，Gini系數(shù)也是越小扣泊，總體越穩(wěn)定延蟹∫抖眩基于Gini系數(shù)最小的原則沥匈，產(chǎn)生了CART算法咐熙。
e.評價標準——評價函數(shù)
在決策樹構(gòu)建完成后棋恼，需要評價構(gòu)建的效果爪飘。這個評價效果是由決策樹每個葉子節(jié)點決定的师崎。
H(t)：每個葉子節(jié)點的熵值犁罩。
Nt：葉子節(jié)點上總共的樣本數(shù)床估。
3.剪枝操作
當決策樹訓練完成后丐巫，并不是分完就完成了递胧。如果分的太細缎脾，可能會出現(xiàn)過擬合的情況遗菠。當對未知數(shù)據(jù)進行分類時舷蒲，效果可能不好。這時就需要剪枝操作域滥。剪枝操作分兩種启绰，分別是預剪枝（前置剪枝）和后剪枝（后置剪枝）委可。
a.預剪枝
在構(gòu)建時，加入一些條件拾酝，在訓練過程中控制決策樹的大小蒿囤。此方法用的較多材诽。預剪枝方法如下：
- 指定最大深度脸侥。當達到設定深度后，停止剪枝涝缝。
- 指定節(jié)點最小樣本數(shù)量，當小于某個值時臀规，停止剪枝塔嬉。
b.后剪枝
在決策樹構(gòu)建完成后恩袱，對樹進行剪枝操作畔塔。此方法使用較少澈吨。某個節(jié)點如果不進行分割時谅辣，損失值為：
Cα(T)=C(T)1+α
進行分割后桑阶，損失值為：
Cα(T)=C(T)2+α|Tleaf|
哪個損失值低，就采用哪個方法包归。參數(shù)α比較大時公壤，限制比較嚴，α比較小時沾鳄，限制較弱。
4.決策樹的集成——隨機森林
只構(gòu)造一棵樹的時候休弃，可能因為部分錯誤數(shù)據(jù)吞歼，或某些不重要的特征，造成樹過擬合或出現(xiàn)誤差塔猾。因此可以通過構(gòu)造很多樹篙骡，共同來進行決策，降低錯誤發(fā)生的概率丈甸。這種集成的算法叫做隨機森林糯俗。
隨機有兩層含義。第一睦擂，有放回的隨機采樣得湘。假設有100個數(shù)據(jù)，隨機有放回采樣60個進行訓練顿仇。這樣能減少離譜數(shù)據(jù)和錯誤數(shù)據(jù)對樹造成影響。第二今膊，在特征上也進行隨機選擇恕刘，假設共有10個特征含蓉，每棵樹隨機選5個特征進行分類着降，降低不重要的特征對樹造成影響。
森林：訓練許多棵樹，例如訓練20棵。把新的數(shù)據(jù)分別用這20棵樹進行預測齿梁，結(jié)果遵循少數(shù)服從多數(shù)的原則稿辙，采用20棵樹中結(jié)果概率最大的分類吨娜。
5.sklearn建立決策樹：
在sklearn庫中勾扭，提供了決策樹分類方法。大致的步驟是：導入數(shù)據(jù)→訓練模型→預測數(shù)據(jù)笋鄙。
a.自帶數(shù)據(jù)包介紹
Sklearn中自帶了一些基礎(chǔ)的數(shù)據(jù)集，可供大家練手。例如iris鳶尾花數(shù)據(jù)集庶艾、digits手寫數(shù)字數(shù)據(jù)集蟹地、boston波士頓房價數(shù)據(jù)集遍愿。它們存放在sklearn.datasets中，只要導入坞笙，就可以使用了。
from sklearn import datasets
iris = datasets.load_iris()
boston = datasets.load_boston()
這些數(shù)據(jù)集有點類似于字典，存儲了所有的，包括樣本民傻、標簽喧半、元數(shù)據(jù)等信息构蹬。樣本數(shù)據(jù)存儲在.data中隐绵，它是一個二維數(shù)組，兩個維度分別是各樣本和各樣本的特征拙毫，大小為[n_samples, n_features]依许。對應標簽存儲在.target中，大小為[n_samples]缀蹄。因此峭跳，可以使用.data和.target可以查看樣本和標簽。
print (iris.data)
print (iris.target)
b.五行代碼構(gòu)造決策樹
以iris數(shù)據(jù)集為例缺前，鳶尾花數(shù)據(jù)集中包括了3個品種的150朵鳶尾花的數(shù)據(jù)蛀醉，數(shù)據(jù)有4個特征，分別是花瓣和花萼的長度和寬度衅码。以這組數(shù)據(jù)為例拯刁，使用sklearn對150個數(shù)據(jù)進行分類。我們要設置一個決策樹的學習器逝段，并根據(jù)需要設置參數(shù)垛玻。學習器也可以是其他類型，例如支持向量機奶躯、線性回歸等帚桩。
from sklearn import tree
clf = tree.DecisionTreeClassifier()
學習器設置完畢后，依次對模型進行擬合與預測嘹黔。讓學習器對數(shù)據(jù)進行擬合使用.fit函數(shù)账嚎，預測使用.predict函數(shù)。
clf = clf.fit (iris.data[:-2],iris.target[:-2])
clf.predict (iris.data[-2:])
以上代碼將數(shù)據(jù)集分成了兩部分儡蔓，從頭開始到倒數(shù)第二個值作為訓練樣本郭蕉，訓練完畢后，將最后兩個值作為未知樣本喂江，進行預測召锈。其中[:-2]表示從頭到倒數(shù)第二個值，[-2:]最后兩個值开呐。完整代碼如下：
from sklearn import datasets,tree
iris = datasets.load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data[:-2],iris.target[:-2])
print (clf.predict(iris.data[-2:]))
同樣的烟勋，對于隨機森林，一段簡單的操作代碼如下：
from sklearn.ensemble import RandomForestClassifier
from sklearn import datasets
iris =datasets.load_iris()
clf=RandomForestClassifier(n_estimators=5)
clf =clf.fit(iris.data[:-2],iris.target[:-2])
print (clf.predict(iris.data[-2:]))
c.參數(shù)簡介
以上是使用sklearn構(gòu)造的簡單的模型筐付。而sklearn.tree.DecisionTreeClassifier()這個類的構(gòu)造代碼如下：
class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best',max_depth=None, min_samples_split=2, min_samples_leaf=1,min_weight_fraction_leaf=0.0, max_features=None, random_state=None,max_leaf_nodes=None, min_impurity_split=1e-07, class_weight=None, presort=False)
以下是一些參數(shù)簡介卵惦。
- criterion：建立劃分標準：例如gini系數(shù)、熵值劃分等
- splitter：best或random瓦戚，best是找到最好的切分點沮尿，random進行隨機的選擇。
- max_features：最多選多少個特征较解。特征少的時候不用設置畜疾。
- max_depth：指定樹最大深度是多少。避免數(shù)據(jù)太多時太龐大印衔。
- min_samples_split：樹進行節(jié)點切分時啡捶，某個節(jié)點樣本個數(shù)少于此數(shù)值，就不再向下切分了奸焙。因為切的越多瞎暑，越準確，但是過擬合的可能越大与帆。
- min_samples_leaf：限制葉子節(jié)點最少的樣本數(shù)了赌。如果葉子節(jié)點數(shù)目小于樣本數(shù)，則會和兄弟節(jié)點一起被剪枝玄糟。
- min_weitht_fraction_leaf：權(quán)重項勿她。每個葉子節(jié)點加一個權(quán)重。當權(quán)重乘以葉子節(jié)點樣本個數(shù)太小阵翎，則被剪枝逢并。
- max_leaf_nodes：最大的葉子節(jié)點數(shù)。
- class_weight：樣本的權(quán)重項郭卫。處理不均衡的數(shù)據(jù)時筒狠，可以對這些數(shù)據(jù)進行權(quán)重預處理。
- min_impurity_split：限制決策樹的生成箱沦。切分后辩恼，如果gini系數(shù)等參考標準變化小于此值，停止切分谓形。
還有一些優(yōu)化問題和準確度計算等方面的內(nèi)容灶伊，以后再和大家討論。
