决策树挑出好西瓜
一、決策樹
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 datadef 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 = 0for 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.0attribute = 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-tempGainreturn Gain #選擇最優屬性 def selectOptimalAttribute(dataSet,labels):bestGain = 0sequence = 0for iColumn in range(0,len(labels)):#不計最后的類別列Gain = infoGain(dataSet,iColumn)if Gain>bestGain:bestGain = Gainsequence = iColumnprint(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 myTreedef main():filePath = 'watermalon.xls'data = getData(filePath)dataSet = dataDeal(data)labels = getLabels(data)myTree = createTree(dataSet,labels)return myTreemytree = main()print(mytree)?
（三）用sklearn庫算法代碼
1.數據集如下
?2.導入庫
導入相關庫 import pandas as pd import graphviz from sklearn.model_selection import train_test_split from sklearn import treef = 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] = 1elif(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] = 2else:x[i][j] = 3y = 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.訓練結果
當選擇“根蒂",“敲聲”,“紋理”,“臍部”,"觸感”進行訓練時
四、決策樹算法——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博客
總結
- 上一篇： 向日葵族群的典型特征
- 下一篇： 爬虫练习3 爬取堆糖网校花照片