決策樹(Decision Tree)是一個非參數的監督式學習方法，決策樹又稱為判定樹，是運用于分類的一種樹結構，其中的每個內部節點代表對某一屬性的一次測試，每條邊代表一個測試結果，葉節點代表某個類或類的分布。

0x00決策樹的判定流程

下圖表示禮物選擇地判定過程，首先根據顏的兩個選擇分支：當黑色的時候根據價格選擇喜歡不喜歡；當選擇白色的時候，可以再根據大小確定喜歡或者不喜歡。

決策樹的決策過程一般是從決策樹的根節點開始，將待測數據和決策樹中的特征節點進行比較，再選擇下一個比較分支，直到葉子節點作為最終的決策結果。

決策樹除了可以用來分類外，還可以用來回歸和預測。分類樹對離散變量做決策樹，回歸樹對連續變量做決策樹。

0x01決策樹的三種節點

從數據產生決策樹的機器學習技術成為決策樹學習，通俗的來說是決策樹，一個決策樹一般有三種節點

決策節點:是對幾種可能方案的選擇，即最后選擇的最佳方案。如果決策屬于多級決策，則決策樹的中間可以有多個決策點，以決策樹根部的決策點為最終決策方案。

狀態節點:代表備選方案的經濟效果(期望值)，通過各狀態節點的經濟效果對比，按照一定的決策標準就可以選出最佳方案。由狀態節點引出的分支稱為概率枝，概率枝的數目表示可能出現的自然狀態數目每個分支上要注明該狀態出現的概率。

終結點:每個方案在各種自然狀態下取得的最終結果.即樹的葉子。

0x02優缺點

*優點**

簡單易懂，原理清晰，決策樹可以實現可 視化;

決策樹算法的時間復雜度(預測數據)是 用于訓練決策樹的數據點的對數;

能夠處理數值和分類數據;

能夠處理多路輸出問題;

可以通過統計學檢驗驗證模型。這也使模 型的可靠性計算變得可能;

即使模型假設違反產生數據的真實模型， 表現性能依舊很好

缺點

決策樹有時候是不穩定的，因為數據微小 的變動，可能生成完全不同的決策樹

有些問題學習起來非常難，因為決策樹很難表達，如異或問題、奇偶校驗或多路復用器問題

如果有些因素占據支配地位，決策樹是有偏差的。因此建議在擬合決策樹之前先平衡數據的影響因子

對連續性的字段比較難預測

最優決策樹的構建屬于NP問題

👇摘抄自：百度百科

P問題

P問題是一個判定問題類，這些問題可以用一個確定性算法在多項式時間內判定或解出。如果一個判定性問題的復雜度是該問題的一個實例的規模n的多項式函數，則我們說這種可以在多項式時間內解決的判定性問題屬于P類問題。P類問題就是所有復雜度為多項式時間的問題的集合。

確定一個問題是否是多項式問題，在計算機科學中非常重要。已經證明，多項式問題是可解問題，因為除了P問題之外的問題，其時間復雜度都很高，即求解需要大量時間。

理論上有解但其時間復雜度巨大的問題，科學家將其稱為難解型問題。對計算機來說，這類問題是不可解的。因此，P問題成了區別問題是否可以被計算機求解的一個重要標志。

NP問題

NP問題是指可以在多項式時間內被非確定機解決的問題。通常它們的時間復雜度都是指數變量，如 等。

這里有一個著名的問題一千禧難題之首。是說P問題是否等于NP問題，也即是否所有在非確定機上多項式可解的問題都能在確定機上用多項式時間求解。這表明用NP問題尋找多項式時間表示的算法很困難，或許最后的結論是NP問題根本就不是P問題。

P=NP?問題

目前已經證明所有P問題都是NP問題，那么反之P—NP嗎?這就是所謂的“NP問題”。目前P與NP是否等價是一個既沒有證實也沒有證偽的問題。但是大部分科學家猜想：找一個問題的解很困難，但驗證一個解很容易(證比解易)，用公式表示就是P≠NP。問題較難求解(P)但容易驗證(NP)，這與我們的日常生活經驗是相符的。

【例1】對方程求解很難，但是驗證很容易。

假設證明了P=NP，那么依據計算復雜性的密碼技術就會沒有前途，因為答案很容易得到驗證的問題也同樣可以輕松求解，這將對計算機安全構成巨大威脅。因為目前的加密技術是將一個整數分解為幾個因數的乘積，正是因數分解過程煩瑣，才保證了信息的安全 [1] 。

NPC(NP Complete，NP完全)問題

計算機科學家將NP問題中最困難的稱為NPC問題。NPC問題有一個令人驚訝的性質，即如果一個NPC問題存在多項式時間算法，那么所有NP問題都可以在多項式時間內求解，即P=NP成立。

這是因為每一個NPC問題都可以在多項式時間內轉化成任何一個NP問題。只要任意一個NPC問題找到了一個多項式算法，那么所有NP問題都能用這個算法解決，也就解決了NP=P問題。但是給NPC找一個多項式算法太不可想象了，而且也從未成功，因此科學家認為，正是NPC問題的存在，使得人們相信P=NP。

NPC問題目前沒有多項式算法，只能用窮舉法逐個檢驗，最終得到答案。但是窮舉法的計算時間隨問題的復雜程度呈指數增長，很快問題就會變得不可計算了。

圍棋或象棋的博弈問題、國際象棋的n皇后問題、密碼學中的大素數分解問題等，都屬于NPC類問題。

0x03決策樹得學習過程

決策樹學習是數據挖掘中得經典算法，每個決策樹都表述了一種樹形結構，它由它的分支對該類型得對象依靠屬性進行分類。每個決策樹可以依靠對源數據庫得分隔進行數據測試。這個過程可以遞歸式地對樹進行修建。

其學習過程如下：

特征選擇：從訓練數據地特征中選擇一個特征作為當前節點地分裂標準(特征選擇地標準不同產生了不同地特征決策樹算法)

決策樹地產生：根據所選特征評估標準，從上而下遞歸地生成子節點，知道數據集不可分時再停止生成

剪枝：決策樹容易過擬合，需要剪枝來縮小樹地結構和規模(包括預剪枝和后剪枝)

0x04創建決策樹進行分類

創建決策樹進行分類的流程如下。

(1)創建數據集。

(2)計算數據集的信息熵。

(3 )遍歷所有特征，選擇信息熵最小的特征，即為最好的分類特征。

(4)根據上一步得到的分類特征分隔數據集， 并將該特征從列表中移除。

(5)執行遞歸函數，返回(3)，不斷分隔數據集，直到分類結束。

( 6)使用決策樹執行分類， 返回分類結果。

決策樹學習算法的偽代碼如下。

檢測數據集中的每個子項是否屬于同一類。

if每個子項屬于同一類return類標簽

else

( 1 )尋找劃分數據集的最好特征。

(2 )劃分數據集。

(3)創建分支節點。

①for每個劃分的子集。

②調用分支創建函數并增加返回結果到分支節點中。

( 4) return分支節點。

從上面代碼的實現過程可以發現，在構建決策樹的過程中，要尋找劃分數據集的最好

特征。

例如，如果一個訓練數據中有 10個特征,那么每次選取哪個特征作為劃分依據?

這 就必須采用量化的方法來判斷，量化劃分方法有多種,其中一項就是“信息論度量信息分類”， 即使無序的數據變得有序。

基于信息論的決策樹算法包括ID3、C4.5、 CART 等。J. Ross Quinlan在1975年提 出將信息熵的概念弓|入決策樹的構建，這就是鼎鼎有名的ID3算法，后續的C4.5、 C5.0、 CART等都是該方法的改進算法。下面是幾種算法的大致情況，詳細算法可以參考機器學 習有關書籍，這里不做重點介紹。

(學習由淺入深，我jio的這三個算法可以之前再了解，先往后看看關于信息熵的內容)

0x05信息熵

由于這些算法又涉及信息熵的概念，因此，下面就簡要介紹一下信 息熵的基本知識。

信息熵:在概率論中，信息熵是一種度量隨機變量不確定性的方式，熵就是信息的期

望值。假設S為所有事件集合，待分類的事物可能劃分在C類中，分別是C，C2,

Cn,每一類的概率分別是P1，P2, . Pn, 那么s的熵就定義為:

信息熵是以二進制位的個數來度量編碼長度的，因此熵的最大值是log2C。

舉個栗子(　o=^?ェ?)o　┏━┓

熵值越高，則數據混合的種類越高，其蘊含的含義是一個受重可能的支化越多 (反而 與變量具體的取值沒有任何關系，只和值的種類多少及發生概率有關)，它攜帶的信息量 就越大。熵在信息論中是一個非常重要的概念 ，很多機器學習的算法都會用到這個概念。

信息增益( Information Gain)是指信息劃分前后熵的變化，即由于使用這個屬性分 隔樣例而導致的期望熵降低。也就是說，信息增益就是原有信息熵與屬性劃分后信息熵(需 要對劃分后的信息熵取期望值)的差值，具體計算法為:

其由第二項為屬性A對S劃分的期望信息

再舉個栗子(　o=^?ェ?)o　┏━┓

這個數據集有四個樣本，兩個基本屬性，其中X1表示是否為紅色，X2表示大小，Y表示是否為好蘋果

由于只有兩個屬性，只可能有兩個決策樹，如下圖所示：

嘗試用代碼來計算熵：

換一組測試數據：

from math import log

def calcshan(dataSet):

lenData = len(dataSet)

p = {}

H = 0.0

for data in dataSet:

currentLabel = data[-1]#獲取類別標簽(也就是樣本的yes或no，比如上面例子的蘋果的好與壞)

if currentLabel not in p.keys():

p[currentLabel] = 0 #如果字典中沒有該類別標簽，則創建

p[currentLabel]+=1 #遞增類別標簽的值

for key in p:

px = float(p[key])/float(lenData) #計算某標簽的概率

# 計算信息熵

H -= px*log(px,2)

return H

if __name__ == "__main__":

dataSet=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]

print(calcshan(dataSet))

測試結果

(env_default) PS F:\workspace> python .\test.py

0.9709505944546686

(env_default) PS F:\workspace>

本作品采用《CC 協議》，轉載必須注明作者和本文鏈接

總結

以上是生活随笔為你收集整理的决策树分类python代码_分类算法-决策树 Decision Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

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