一、決策樹
1、決策樹（Decision Tree)是一類常見的機器學習方法，是一種非常常用的分類方法，它是一種監督學習。常見的決策樹算法有ID3，C4.5、C5.0和CART（classification and regression tree），CART的分類效果一般要優于其他決策樹。
2、決策樹是基于樹狀結構來進行決策的，一般地，一棵決策樹包含一個根節點、若幹個内部節點和若幹個葉節點。
3、 每個内部節點表示一個屬性上的判斷 每個分支代表一個判斷結果的輸出 每個葉節點代表一種分類結果。 根節點包含樣本全集
4、決策樹學習的目的是為了産生一棵泛化能力強，即處理未見示例能力強的決策樹，其基本流程遵循簡單且直覺的“分而治之”（divide-and-conquer）政策。
二、ID3算法理論
1.算法核心
ID3算法的核心是根據資訊增益來選擇進行劃分的特征，然後遞歸地建構決策樹
2.特征選擇
特征選擇也即選擇最優劃分屬性，從目前資料的特征中選擇一個特征作為目前節點的劃分标準。 随着劃分過程不斷進行，希望決策樹的分支節點所包含的樣本盡可能屬于同一類别，即節點的“純度”越來越高。
3.熵（entropy）
熵表示事務不确定性的程度，也就是資訊量的大小（一般說資訊量大，就是指這個時候背後的不确定因素太多），熵的公式如下
對于在X的條件下Y的條件熵，是指在X的資訊之後，Y這個變量的資訊量（不确定性）的大小，計算公式如下：
是以當Entropy最大為1的時候，是分類效果最差的狀态，當它最小為0的時候，是完全分類的狀态。因為熵等于零是理想狀态，一般實際情況下，熵介于0和1之間 。
熵的不斷最小化，實際上就是提高分類正确率的過程。
4.資訊增益（information gain）
資訊增益：在劃分資料集之前之後資訊發生的變化，計算每個特征值劃分資料集獲得的資訊增益，獲得資訊增益最高的特征就是最好的選擇。
定義屬性A對資料集D的資訊增益為infoGain(D|A)，它等于D本身的熵，減去 給定A的條件下D的條件熵，即：
資訊增益的意義：引入屬性A後，原來資料集D的不确定性減少了多少。
計算每個屬性引入後的資訊增益，選擇給D帶來的資訊增益最大的屬性，即為最優劃分屬性。一般，資訊增益越大，則意味着使用屬性A來進行劃分所得到的的“純度提升”越大。
5.步驟
- 從根節點開始，計算所有可能的特征的資訊增益，選擇資訊增益最大的特征作為節點的劃分特征；
- 由該特征的不同取值建立子節點；
- 再對子節點遞歸1-2步，建構決策樹；
- 直到沒有特征可以選擇或類别完全相同為止，得到最終的決策樹。
三、ID3算法應用舉例——西瓜樹
（一）西瓜樹理論推導
1.西瓜的決策樹
西瓜樣本建構決策樹模型
2.利用資訊增益選擇最優劃分屬性
（1）西瓜樹資訊熵
在西瓜樣本集中，共有17個樣本，其中正樣本8個，負樣本9個，樣本集的資訊熵為
2）西瓜樹資訊增量
西瓜樣本集中，以屬性“色澤”為例，它有3個取值{青綠、烏黑、淺白}，對應的子集D1（色澤=青綠）中有6個樣本，其中正負樣本各3個，D2（色澤=烏黑）中有6個樣本，正樣本4個，負樣本2個，D^3（色澤=淺白）中有5個樣本，正樣本1個，fuya負樣本4個。
同理也可以計算出其他幾個屬性的資訊增益，選擇資訊增益最大的屬性作為根節點來進行劃分，然後再對每個分支做進一步劃分.
（二）不用sklearn庫算法代碼
1.建立一個watergua.ipynb檔案
2.導入python子產品
3.資料擷取和處理函數
4.擷取屬性名稱和類别标記
5.葉節點标記
6.計算資訊熵
7.建構子資料集
8.計算資訊增益
9.選擇最優屬性
10.建立決策樹
11.調用函數
import pandas as pd
import numpy as np
from collections import Counter
from math import log2
#資料擷取與處理
def getData(filePath):
data = pd.read_excel(filePath)
return data
def dataDeal(data):
dataList = np.array(data).tolist()
dataSet = [element[1:] for element in dataList]
return dataSet
#擷取屬性名稱
def getLabels(data):
labels = list(data.columns)[1:-1]
return labels
#擷取類别标記
def targetClass(dataSet):
classification = set([element[-1] for element in dataSet])
return classification
#将分支結點标記為葉結點，選擇樣本數最多的類作為類标記
def majorityRule(dataSet):
mostKind = Counter([element[-1] for element in dataSet]).most_common(1)
majorityKind = mostKind[0][0]
return majorityKind
#計算資訊熵
def infoEntropy(dataSet):
classColumnCnt = Counter([element[-1] for element in dataSet])
Ent = 0
for symbol in classColumnCnt:
p_k = classColumnCnt[symbol]/len(dataSet)
Ent = Ent-p_k*log2(p_k)
return Ent
#子資料集建構
def makeAttributeData(dataSet,value,iColumn):
attributeData = []
for element in dataSet:
if element[iColumn]==value:
row = element[:iColumn]
row.extend(element[iColumn+1:])
attributeData.append(row)
return attributeData
#計算資訊增益
def infoGain(dataSet,iColumn):
Ent = infoEntropy(dataSet)
tempGain = 0.0
attribute = set([element[iColumn] for element in dataSet])
for value in attribute:
attributeData = makeAttributeData(dataSet,value,iColumn)
tempGain = tempGain+len(attributeData)/len(dataSet)*infoEntropy(attributeData)
Gain = Ent-tempGain
return Gain
#選擇最優屬性
def selectOptimalAttribute(dataSet,labels):
bestGain = 0
sequence = 0
for iColumn in range(0,len(labels)):#不計最後的類别列
Gain = infoGain(dataSet,iColumn)
if Gain>bestGain:
bestGain = Gain
sequence = iColumn
print(labels[iColumn],Gain)
return sequence
#建立決策樹
def createTree(dataSet,labels):
classification = targetClass(dataSet) #擷取類别種類（集合去重）
if len(classification) == 1:
return list(classification)[0]
if len(labels) == 1:
return majorityRule(dataSet)#傳回樣本種類較多的類别
sequence = selectOptimalAttribute(dataSet,labels)
print(labels)
optimalAttribute = labels[sequence]
del(labels[sequence])
myTree = {optimalAttribute:{}}
attribute = set([element[sequence] for element in dataSet])
for value in attribute:
print(myTree)
print(value)
subLabels = labels[:]
myTree[optimalAttribute][value] = \
createTree(makeAttributeData(dataSet,value,sequence),subLabels)
return myTree
def main():
filePath = 'watermalon.xls'
data = getData(filePath)
dataSet = dataDeal(data)
labels = getLabels(data)
myTree = createTree(dataSet,labels)
return myTree
mytree = main()
print(mytree)
（三）用sklearn庫算法代碼
1.資料集如下
2.導入庫
導入相關庫
import pandas as pd
import graphviz
from sklearn.model_selection import train_test_split
from sklearn import tree
f = open('C:/Users/王青松/watermalon.csv','r')
data = pd.read_csv(f)
x = data[["色澤","根蒂","敲聲","紋理","臍部","觸感"]].copy()
y = data['好瓜'].copy()
print(data)
3.資料轉換
#将特征值數值化
x = x.copy()
for i in ["色澤","根蒂","敲聲","紋理","臍部","觸感"]:
for j in range(len(x)):
if(x[i][j] == "青綠" or x[i][j] == "蜷縮" or data[i][j] == "濁響" \
or x[i][j] == "清晰" or x[i][j] == "凹陷" or x[i][j] == "硬滑"):
x[i][j] = 1
elif(x[i][j] == "烏黑" or x[i][j] == "稍蜷" or data[i][j] == "沉悶" \
or x[i][j] == "稍糊" or x[i][j] == "稍凹" or x[i][j] == "軟粘"):
x[i][j] = 2
else:
x[i][j] = 3
y = y.copy()
for i in range(len(y)):
if(y[i] == "是"):
y[i] = int(1)
else:
y[i] = int(-1)
#需要将資料x，y轉化好格式，資料框dataframe，否則格式報錯
x = pd.DataFrame(x).astype(int)
y = pd.DataFrame(y).astype(int)
print(x)
print(y)
4.建立模型并訓練
5.訓練結果
當選擇“根蒂",“敲聲”,“紋理”,“臍部”,"觸感”進行訓練時
#決策樹學習
clf = tree.DecisionTreeClassifier(criterion="entropy") #執行個體化
clf = clf.fit(x_train, y_train)
score = clf.score(x_test, y_test)
print(score)
四、決策樹算法——C4.5
（一）對比ID3的改進點
C4.5算法是用于生成決策樹的一種經典算法，是ID3算法的一種延伸和優化。C4.5算法對ID3算法進行了改進 ，改進點主要有：
用資訊增益率來選擇劃分特征，克服了用資訊增益選擇的不足，
資訊增益率對可取值數目較少的屬性有所偏好；
能夠處理離散型和連續型的屬性類型，即将連續型的屬性進行離散化處理；
能夠處理具有缺失屬性值的訓練資料；
在構造樹的過程中進行剪枝；
（二）特征選擇
特征選擇也即選擇最優劃分屬性，從目前資料的特征中選擇一個特征作為目前節點的劃分标準。 随着劃分過程不斷進行，希望決策樹的分支節點所包含的樣本盡可能屬于同一類别，即節點的“純度”越來越高。
（三）資訊增益率
資訊增益準則對可取值數目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，C4.5算法采用資訊增益率來選擇最優劃分屬性。增益率公式
資訊增益率準則對可取值數目較少的屬性有所偏好。是以，C4.5算法不是直接選擇資訊增益率最大的候選劃分屬性，而是先從候選劃分屬性中找出資訊增益高于平均水準的屬性，再從中選擇資訊增益率最高的。
（四）對連續特征的處理
- 當屬性類型為離散型，無須對資料進行離散化處理；
- 當屬性類型為連續型，則需要對資料進行離散化處理。具體思路如下：
（五）對缺失值的處理
ID3算法不能處理缺失值，而C4.5算法可以處理缺失值（常用機率權重方法），主要有三種情況，具體如下：
1.在有缺失值的特征上如何計算資訊增益率？
根據缺失比例，折算資訊增益（無缺失值樣本所占的比例乘以無缺失值樣本子集的資訊增益）和資訊增益率
2.標明了劃分屬性，若樣本在該屬性上的值是缺失的，那麼如何對這個樣本進行劃分？
将樣本以不同機率同時劃分到不同節點中，機率是根據其他非缺失屬性的比例來得到的
3.對新的樣本進行分類時，如果測試樣本特性有缺失值如何判斷其類别？
走所有分支，計算每個類别的機率，取機率最大的類别指派給該樣本
（六）剪枝
1.剪枝原因
因為過拟合的樹在泛化能力的表現非常差。
剪枝又分為前剪枝和後剪枝，前剪枝是指在構造樹的過程中就知道哪些節點可以剪掉 。 後剪枝是指構造出完整的決策樹之後再來考查哪些子樹可以剪掉。
2.剪前枝
在節點劃分前确定是否繼續增長，及早停止增長的主要方法有：
- 節點内資料樣本數小于切分最小樣本數門檻值；
- 所有節點特征都已分裂；
- 節點劃分前準确率比劃分後準确率高。 前剪枝不僅可以降低過拟合的風險而且還可以減少訓練時間，但另一方面它是基于“貪心”政策，會帶來欠拟合風險。
3.剪後枝
C4.5算法采用悲觀剪枝方法。根據剪枝前後的誤判率來判定是否進行子樹的修剪， 如果剪枝後與剪枝前相比其誤判率是保持或者下降，則這棵子樹就可以被替換為一個葉子節點。 是以，不需要單獨的剪枝資料集。C4.5 通過訓練資料集上的錯誤分類數量來估算未知樣本上的錯誤率。
把一顆子樹（具有多個葉子節點）的剪枝後用一個葉子節點來替代的話，在訓練集上的誤判率肯定是上升的，但是在新資料上不一定。于是我們需要把子樹的誤判計算加上一個經驗性的懲罰因子。對于一顆葉子節點，它覆寫了N個樣本，其中有E個錯誤，那麼該葉子節點的錯誤率為（E+0.5）/N。這個0.5就是懲罰因子，那麼一顆子樹，它有L個葉子節點，那麼該子樹的誤判率估計為：
這樣的話，我們可以看到一顆子樹雖然具有多個子節點，但由于加上了懲罰因子，是以子樹的誤判率計算未必占到便宜。剪枝後内部節點變成了葉子節點，其誤判個數J也需要加上一個懲罰因子，變成J+0.5。 [公式] 對于樣本的誤判率e，可以根據經驗把它估計成各種各樣的分布模型，比如是二項式分布，比如是正态分布。
那麼一棵樹錯誤分類一個樣本值為1，正确分類一個樣本值為0，該樹錯誤分類的機率（誤判率）為e，e通過下式來計算
那麼樹的誤判次數就是伯努利分布，我們可以估計出該樹的誤判次數的均值和标準差：
把子樹替換成葉子節點後，該葉子的誤判次數也是一個伯努利分布，因為子樹合并為一個葉子節點了，是以，L=1，将其代入上面計算誤判率的公式中，可以得到葉子節點的誤判率為
是以葉子節點的誤判次數均值為
這裡采用一種保守的分裂方案，即有足夠大的置信度保證分裂後準确率比不分裂時的準确率高時才分裂，否則就不分裂–也就是應該剪枝。
如果要分裂（即不剪枝）至少要保證分裂後的誤判數E(子樹誤判次數)要小于不分裂的誤判數E(葉子節點的誤判次數)，而且為了保證足夠高的置信度，加了一個标準差可以有95%的置信度，是以，要分裂（即不剪枝）需滿足如下不等式
反之就是不分裂，即剪枝的條件：
五、決策樹算法——CART算符
（一）簡介
ID3和C4.5算法，生成的決策樹是多叉樹，隻能處理分類不能處理回歸。而CART（classification and regression tree）分類回歸樹算法，既可用于分類也可用于回歸。 分類樹的輸出是樣本的類别， 回歸樹的輸出是一個實數。
ID3中使用了資訊增益選擇特征，增益大優先選擇。C4.5中，采用資訊增益率選擇特征，減少因特征值多導緻資訊增益大的問題。CART分類樹算法使用基尼系數選擇特征，基尼系數代表了模型的不純度，基尼系數越小，不純度越低，特征越好。這和資訊增益（率）相反。
CART算法步驟
- 特征選擇；
- 遞歸建立決策樹；
- 決策樹剪枝；
（二）基尼系數
資料集D的純度可用基尼值來度量
在屬性A的條件下，樣本D的基尼系數定義為
（三）對連續特征和離散特征的處理
1.連續特征
與C4.5思想相同，都是将連續的特征離散化。差別在選擇劃分點時，C4.5是資訊增益率，CART是基尼系數。
2.離散特征
思路：不停的二分離散特征
在ID3、C4.5，特征A被選取建立決策樹節點，如果它有3個類别A1,A2,A3，我們會在決策樹上建立一個三叉點，這樣決策樹是多叉樹，而且離散特征隻會參與一次節點的建立。
六、總結
本次實驗了解了決策樹的三種算法ID3、C4.5、CART，以及各自的優缺點，改進的不同之處。
ID3中使用了資訊增益選擇特征，增益大優先選擇。
C4.5中，采用資訊增益率選擇特征，減少因特征值多導緻資訊增益大的問題。
CART分類樹算法使用基尼系數選擇特征，基尼系數代表了模型的不純度，基尼系數越小，不純度越低，特征越好。
這和資訊增益（率）相反。通過實驗進一步了解他們各自的算法實作。
七、參考資料
決策樹挑出好西瓜_一隻特立獨行的豬️的部落格-CSDN部落格