前言

??決策樹是一類常見的機器學習方法，屬于監督學習算法。決策樹本身不是一種很復雜的算法，只需要簡單的數學基礎的就可以理解其內容。一些比較典型的決策樹算法有：ID3、C4.5、CART等等決策樹算法。

理論介紹

??一般的，一棵決策樹包含一個根結點、若干個內部結點、若干個葉結點。葉結點是最后的決策結果，其余結點都對應與某一個屬性的測試（決策）。每個結點所包含的樣本集合根據對屬性的決策，往下劃分到其的子結點中。根節點包含整個樣本集，隨著樹的結點逐漸往下延伸，樣本集也被分散到各個結點中。

算法偽代碼：

算法：

Generate_decision_tree(D, A)。由給定的訓練數據產生一棵判定樹。

輸入：

訓練集 D={(x1,y1),(x2,y2),...,(xm,ym)}
屬性集 A={a1,a2,...,ad}

輸出：

返回的是一個決策樹。

方法：

Generate_decision_tree(D, A)
創建結點 N；
if D都在同一個類C then //類標號屬性的值均為C，其候選屬性值不考慮
??return N 作為葉結點，以類C標記；
if A為空集 or D中樣本在A上取值相同 then
??return N 作為葉結點，標記為D中出現最多的類；
選擇A中具有最高信息增益的屬性a?；//找出最好的劃分屬性
for 遍歷a?中的所有可能取值av? //將樣本D按照屬性a?進行劃分
??由結點 N 長出一個分枝；
??令Dv表示樣本集D中在該屬性a?上取值為av?的樣本子集
??if Dv為空 then
????加上一個葉節點，標記為樣本集D中出現最多的類；//從樣本中找出類標號數量最多的，作為此節點的標記
??else
????加上一個由 Generate_decision_tree(Dv , A–a?)返回的結點；//對數據子集Dv遞歸調用，此時候選屬性已，因為已經用作結點，所以屬性A要刪除a?

參考博客：http://blog.csdn.net/liema2000/article/details/6118384

??從偽代碼中我們可以看出：決策樹的生成是一個不斷向下調用遞歸函數的過程。那么我們就希望關注遞歸函數的返回條件，也就是決策樹生成到了葉結點的時候。從偽代碼中可以發現有以下幾種情況：

• 當前結點包含的所有樣本都是屬于同一個類別，這時沒有必要劃分了
• 當前屬性集為空時，也就是沒有屬性可以用來劃分了
• 當前屬性下，所有樣本取值一樣，即當前屬性無法對數據集劃分起到作用
• 當前屬性下所含的樣本集合為空，即沒有多的樣本來劃分了

??以上對應偽代碼中的幾個if判斷，如果符合條件，則將當前結點視作葉節點，并返回。

劃分依據

信息熵(information entropy)

??假定當前樣本集合D中第k類樣本所占的比例為pk(k=1,2,3,...,|γ|)，則D的信息熵定義為：
Ent(D)=?∑k=1|γ|pklog2pk
??從信息論中我們知道熵的定義時“用來消除不確定性的東西”。換句話說，就是對不確定性的度量。熵越大，不確定性越大；熵越小，不確定性越小，這也是通常我們希望看到的。所以，我們希望Ent(D)盡可能地小。

信息增益(information gain)

??假定離散屬性a有V個可能的取值{a1,a2,a3,...,aV}，若使用屬性a對樣本集合D進行劃分，則會產生V個分支結點。那么其中第v個結點，包含了樣本集合D在屬性a上取值為av的樣本子集，記為Dv。
??根據前面的公式，可以很容易計算出Dv的信息熵Ent(D)。
??根據屬性劃分后，樣本數據集D被分到了各個子集中，那么理所當然，熵也會發生變化。現在想要求出劃分之后的熵，跟劃分前的熵作差就可以知道熵的變化值。這個熵的差值就意味著不確定性的減少，而我們希望這個差值能盡可能大。這個差值我們就叫做信息增益。
Gain(D,a)=Ent(D)?∑v=1V|Dv||D|Ent(Dv)
??這里，劃分后的結點所包含的樣本數不同，所以對其每個結點的熵做了加權平均。每個結點的權重是|Dv||D|，即樣本數越多的結點影響越大。

??一般來說，在選擇劃分屬性時，我們希望減少不確定性，那么信息增益要盡可能大。所以在劃分時，會計算每個屬性的信息增益，并選取最大值。

a?=arga∈Amax(Gain(D,a))
??著名的ID3算法就是基于信息增益來選擇劃分屬性的。

增益率(Gain Ratio)

??增益率定義為：

Gainratio(D,a)=Gain(D,a)IV(a)
??其中，
IV(a)=?∑v=1V|Dv||D|log2|Dv||D|
??稱為屬性 a的固有值。其特點是：屬性a的可能取值屬性越多，即 V越大，則IV(a)的值就會越大。
??前面提到的信息增益 Gain(D,a)會對可取值數目多（ V更大）的屬性有所偏好，而為了消除這個偏好的影響，所以引入了IV(a)。與信息增益相反，增益率會對可取值數目較少的屬性有所偏好。
??在C4.5算法中使用的就是增益率，但是并不是直接使用增益率作為劃分標準。而是，先從候選劃分屬性中通過信息增益劃分出高于平均水平的屬性，隨后，再選取增益率最高的那個屬性。

基尼指數(Gini index)

??CART決策樹算法中采用的就是基尼指數。

Gini(D)=∑k=1|γ|∑k′≠kpkpk′=1?∑k=1|γ|p2k
??直觀地理解，相當于在數據集D中抽取兩個樣本（總共有 |γ|個類，默認取第 k個類），這兩個樣本的類別不一樣的概率。也等于兩個類都相同的概率的反例，即1減去它。Gini(D)越小越好。
??對于屬性 a的基尼指數：
Giniindex(D,a)=∑v=1V|Dv||D|Gini(Dv)
??選取是的劃分后基尼指數最小的屬性作為最優劃分屬性：
a?=arga∈Amax(Giniindex(D,a))

剪枝處理

預剪枝(prepruning)

??在決策樹生成過程中，對每個結點在劃分前進行估計。若當前結點劃分后不能使決策樹的泛化性能有所提高（一般來說是，在交叉訓練集中表現得更好），則停止劃分并把當前結點標記為葉節點，類別就去出現次數最多的那個類別。

后剪枝

??從訓練集中生成好了一個完整的決策樹之后，然后自底向上對非葉結點進行測試。若將該節點對應的子樹換成葉節點，能帶來決策樹泛化性能的提升（劃分前后的準確率提高），則將該指數替換為結點。

連續值處理

??決策樹的屬性并不只有離散值，也可能出現屬性是一個連續值的情況。由于連續屬性的可取值數目不再是有限的，所以不能再根據連續屬性的可取值來劃分結點。
??C4.5決策樹算法中：采用二分法(bi-partition)對連續值進行處理。
??給定樣本集D和連續屬性值a，假定屬性a在數據集D上出現了n個可能的取值，將這些值從小到大排序，即為{a1,a2,a3,...,an}。基于劃分點t可以將D劃分為子集D?t和D+t，其中D?t包含了那些在屬性a上取值不大于t的樣本，而D+t則包含了那些在屬性a上取值大于t的樣本。
??對于連續屬性a，我么你可以考察包含n?1個元素的候選劃分點集合：

Ta={ai+ai+12|1≤i≤n?1}
??選取區間 [ai,ai+1)的中點作為候選劃分點。
Gain(D,a)=maxt∈TaGain(D,a,t)=maxt∈TaEnt(D)?∑λ∈(?,+)∣∣Dtt∣∣|D|Ent(Dλt)
??其中， Gain(D,a,t)是樣本集 D基于劃分點t二分后的信息增益。
??之后的處理方法與普通的離散值的處理方法一樣。

缺失值處理

??有時會遇到不完整的樣本，即樣本的某些屬性值有缺失。但是有時，這些屬性值雖然缺失了一部分，但卻對訓練結果有好的影響。所以不能簡單地就丟棄掉這些數據。
??給定訓練集D和屬性a，令D?表示D在屬性a上沒有缺失值的樣本子集。
??假定屬性a有V個可取值{a1,a2,...,an}，令Dv?表示D?中在屬性a上取值為av的樣本子集，Dk?表示D?中屬于第k類(k=1,2,3...,|γ|)的樣本子集。
??顯然有：

D?=?k=1|γ|Dk?D?=?v=1VDv?
??假定為每一個樣本 x都賦予一個權重ωx，有：
ρ=∑x∈D?ωx∑x∈Dωxpk?=∑x∈Dk?ωx∑x∈Dωx,(1≤k≤|γ|)rv?=∑x∈Dv?ωx∑x∈Dωx,(1≤v≤V)
??直觀地看，對于屬性 a：
ρ表示無缺失值樣本所占的比例；
?? pk?表示無缺失值樣本中第 k類所占的比例；
rv?表示無缺失值樣本中在屬性 a上取值av的樣本所占的比例。
??則可以將信息增益的計算公式推廣為：
Gain(D,a)=ρ×Gain(D,a)=ρ×(Ent(D?)?∑v=1Vrv?Ent(Dv?))
??其中，
Ent(D?)=?∑k=1|γ|pk?log2pk?

??決策樹算法的原理不算特別復雜，主要還是在編程。下次再去整理下程序。
??(? ??_??)?

總結

以上是生活随笔為你收集整理的机器学习入门学习笔记：（3.1）决策树算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。