文章目錄

• 1 決策樹算法簡介
• 2 決策樹算法
• • 2.1 引例
  • • 例1
    • 例2
  • 2.2 算法分類
  • • (1) 信息熵
    • (2) 信息增益
    • (3) 增益率
    • (4) 基尼指數(shù)
• 3 決策樹算法優(yōu)缺點
• 4 實驗
• 參考資料

注：轉(zhuǎn)載請標明原文出處鏈接：https://xiongyiming.blog.csdn.net/article/details/96630813

1 決策樹算法簡介

決策樹(Decision Tree) 是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評價項目風險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。在機器學(xué)習(xí)中，決策樹是一個預(yù)測模型，它代表的是對象屬性與對象值之間的一種映射關(guān)系。Entropy = 系統(tǒng)的凌亂程度，使用算法ID3, C4.5和C5.0生成樹算法使用熵。這一度量是基于信息學(xué)理論中熵的概念。
決策樹是一種樹形結(jié)構(gòu)，其中每個內(nèi)部節(jié)點表示一個屬性上的測試，每個分支代表一個測試輸出，每個葉節(jié)點代表一種類別。
(以上均來自百度百科)

決策樹學(xué)習(xí)算法的最大優(yōu)點是，它可以自學(xué)習(xí)。在學(xué)習(xí)的過程中，不需要使用者了解過多背景知識，只需要對訓(xùn)練實例進行較好的標注，就能夠進行學(xué)習(xí)。顯然，它屬于有監(jiān)督學(xué)習(xí)。從一類無序、無規(guī)則的事物(概念)中推理出決策樹表示的分類規(guī)則。

2 決策樹算法

分類決策樹模型是一種描述對實例進行分類的樹形結(jié)構(gòu)。決策樹由結(jié)點和有向邊組成。結(jié)點有三種類型：根節(jié)點、內(nèi)部結(jié)點和葉節(jié)點。
根結(jié)點：包含全部樣本;
葉結(jié)點：對應(yīng)決策的結(jié)果;
內(nèi)部結(jié)點：對應(yīng)屬性測試.

2.1 引例

例1

決策樹分類的思想類似于找對象。現(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：
女兒：多大年紀了？ (年齡)
母親：26。
女兒：長的帥不帥？ (長相)
母親：挺帥的。
女兒：收入高不？ (收入情況)
母親：不算很高，中等情況。
女兒：是公務(wù)員不？ (是否公務(wù)員)
母親：是，在稅務(wù)局上班呢。
女兒：那好，我去見見。

那么以上的對話女兒的最終決定是見，其中，葉節(jié)點就是“見”和“不見” ，內(nèi)部節(jié)點就是：年齡、長相、收入情況和公務(wù)員。
其決策樹如下圖所示：

例2

機器學(xué)習(xí)中的西瓜數(shù)據(jù)集如下：

由上面西瓜數(shù)據(jù)集可知，由17個樣本，對應(yīng)6中屬性(色澤、根蒂、敲聲、紋理，臍部和觸感)和最終的結(jié)果是不是好瓜。那么葉節(jié)點就是“好瓜”和“壞瓜” ，內(nèi)部節(jié)點就是：色澤、根蒂、敲聲、紋理，臍部和觸感。
決策樹的判別類似于人在面臨問題決策的問題時的處理機制。我們通常買西瓜會看習(xí)慣的顏色，新鮮感，敲一敲是什么聲音等。通過這幾個問題，最終我們會做出決策，這個是不是好瓜。
其決策樹如下圖所示：

2.2 算法分類

決策樹算法流程如下：

咋一眼，看著上面的算法比較復(fù)雜。其實決策樹的生成就是一個遞歸過程。下面以西瓜數(shù)據(jù)集為例，進行計算。
一般而言，我們希望決策樹的分支點所包含的樣本盡可能屬于同一類別，也就是節(jié)點的純度(purity) 越來越高。在樣本集中屬性都會編碼為一些數(shù)字(1，-1等)，如何從這些數(shù)字進行劃分呢？ 在實際使用中，我們衡量的常常是不純度。度量不純度的指標有很多，例如：信息熵，信息增益，增益率，基尼指數(shù)等。也就是通過信息熵，信息增益，增益率，基尼指數(shù)等對樣本中的數(shù)字進行劃分。

(1) 信息熵

信息熵定義表示隨機變量不確定性的度量，假設(shè)有當前樣本集合D中第k被樣本所占的比例為 ，則$D$的信息熵定義為$p_k(k=1,2,\dots ,\left|y\right|)$，則$D$的信息熵定義為
$$\mathrm{E}\mathrm{n}\mathrm{t}(D)=?\sum _{k=1}^{|y|}{p}_k{\log }_2{p}_k\text{\hspace{1em}(1)}$$
其中， $\mathrm{E}\mathrm{n}\mathrm{t}(D)$的值越小，則$D$的純度越高。

下面計算生成數(shù)據(jù)集然后計算熵（以機器學(xué)習(xí)實戰(zhàn)書上的海洋生物數(shù)據(jù)為例）。

函數(shù)calEnt()計算熵

函數(shù)createDataSet()生成數(shù)據(jù)集

代碼示例

import numpy as np import pandas as pd# calEnt 函數(shù)功能：計算熵 # 參數(shù)說明： # dataSet：原始數(shù)據(jù)集 # 返回： # ent:熵的值 # """ def calEnt(dataSet):n = dataSet.shape[0] #數(shù)據(jù)集總行數(shù)iset = dataSet.iloc[:,-1].value_counts() #標簽的所有類別p = iset/n #每一類標簽所占比ent = (-p*np.log2(p)).sum() #計算信息熵return ent#createDataSet 函數(shù)功能: 創(chuàng)建數(shù)據(jù)集 def createDataSet():row_data = {'no surfacing':[1,1,1,0,0],'flippers':[1,1,0,1,1],'fish':['yes','yes','no','no','no']}dataSet = pd.DataFrame(row_data)return dataSet# 調(diào)用 dataSet = createDataSet() # 調(diào)用創(chuàng)建數(shù)據(jù)集 函數(shù) result_calEnt=calEnt(dataSet)# 調(diào)用計算熵 函數(shù) print("dataSet=",dataSet) print("result_calEnt=",result_calEnt)

運行結(jié)果如下

注：熵越高，信息的不純度就越高，即數(shù)據(jù)越混亂。

(2) 信息增益

信息增益的計算其實就是父節(jié)點的信息熵與下面所有節(jié)點總信息熵之差。但是不是簡單地這里的子節(jié)點的總信息熵不能簡單地求和，需要在求和前進行修正。
假設(shè)離散屬性$a$有$V$個可能的取值 $\left\{a^1,a^2,\dots ,a^V\right\}$，若使用屬性a對樣本集D進行劃分，則會產(chǎn)生$V$個分直接點，其中第$v$個分直接點包含了$D$中所有在屬性$a$上取值為 $a^V$的樣本，記為 $D^V$。我們可以通過公式(1)計算 $D^V$的信息熵，再考慮到不同的分支點所辦函的樣本數(shù)不同，給分支點賦予權(quán)重 $\left|D^V\right|/\left|D\right|$，則樣本數(shù)越多的分支節(jié)點的影響最大，于是可以計算出用屬性$a$對樣本集$D$進行劃分所獲得的信息增益為：
$$\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D,\mathrm{a})=\mathrm{E}\mathrm{n}\mathrm{t}(D)?\sum _{v=1}^V\frac{\left|D^v\right|}{\left|D\right|}\mathrm{E}\mathrm{n}\mathrm{t}(D^v)\text{\hspace{1em}(2)}$$
其中，信息增益越大，則意味著用屬性a來進行劃分所獲得的純度提升越大。
著名的ID3(Iterative Dichotomiser, 迭代二分器) 決策樹學(xué)習(xí)算法就是以信息增益為準則來劃分屬性。
下面使用信息增益在西瓜數(shù)據(jù)集生成決策樹。

首先計算根節(jié)點的信息熵
$$\mathrm{E}\mathrm{n}\mathrm{t}(D)=?\sum _{k=1}^{|y|}{p}_k{\log }_2{p}_k=?(\frac{8}{17}{\log }_2\frac{8}{17}+\frac{9}{17}{\log }_2\frac{9}{17})=0.998$$
然后計算當前屬性集合(色澤、根蒂、敲聲、紋理，臍部和觸感)中每個屬性的信息增益。屬性“色澤”有三個屬性(青綠，烏黑，淺白)。若使用該屬性對數(shù)據(jù)集D進行劃分，則可以得到3個子集，分別記為： $D^1$(色澤=青綠)， $D^2$(色澤=烏黑)， $D^2$(色澤=淺白)
子集 $D^1$包含編號為(1,4,6,10,13,17)的6個樣例，其中好瓜占$p_1=\frac{3}{6}$，壞瓜占 $p_2=\frac{3}{6}$；同理子集 $D^2$中，好瓜占 $p_1=\frac{4}{6}$，壞瓜占 $p_1=\frac{2}{6}$；子集 $D^3$中，好瓜占 $p_1=\frac{1}{5}$，壞瓜占 $p_1=\frac{4}{5}$。則，根據(jù)公式(1)可以計算用屬性色澤劃分后所獲得的3個分支節(jié)點的信息熵為
$$\mathrm{E}\mathrm{n}\mathrm{t}(D^1)=?(\frac{3}{6}{\log }_2\frac{3}{6}+\frac{3}{6}{\log }_2\frac{3}{6})=1$$ $$\mathrm{E}\mathrm{n}\mathrm{t}(D^2)=?(\frac{4}{6}{\log }_2\frac{4}{6}+\frac{2}{6}{\log }_2\frac{2}{6})=0.918$$ $$\mathrm{E}\mathrm{n}\mathrm{t}(D^3)=?(\frac{1}{5}{\log }_2\frac{1}{5}+\frac{4}{5}{\log }_2\frac{4}{5})=0.722$$
則，根據(jù)公式(2)可以計算屬性色澤的信息增益為
$$\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D,a_1)=\mathrm{E}\mathrm{n}\mathrm{t}(D)?\sum _{v=1}^3\frac{\left|D^v\right|}{\left|D\right|}\mathrm{E}\mathrm{n}\mathrm{t}(D^v)=0.998?(\frac{6}{17}\times 1+\frac{6}{17}\times 0.918+\frac{5}{17}\times 0.722)=0.109$$
同理可以計算出其他屬性的信息增益(色澤、根蒂、敲聲、紋理，臍部和觸感分別用 $a_1,a_2,a_3,a_4,a_5,a_6$表示)，則
$$\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D,a_2)=0.143$$ $$\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D,a_3)=0.141$$ $$\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D,a_4)=0.381$$ $$\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D,a_5)=0.289$$ $$\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D,a_6)=0.006$$
顯然，屬性紋理使的信息增益最大，于是被選為劃分屬性，下圖為基于紋理對根節(jié)點進行劃分的結(jié)果。

然后決策樹學(xué)習(xí)算法將每一個節(jié)點做進一步劃分，最終得到?jīng)Q策樹如下圖所示

(3) 增益率

實際中，信息增益準則對可取值數(shù)目較多的屬性有所偏好，為了減少這種偏好對決策樹帶來不利影響，C4.5決策樹算法不直接使用信息增益，而是使用增益率來選擇最優(yōu)劃分屬性，增益率定義為
$$\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}\_\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}(D,\mathrm{a})=\frac{\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D,a)}{\mathrm{I}\mathrm{V}(a)}\text{\hspace{1em}(3)}$$
其中 $\mathrm{I}\mathrm{V}(a)$定義為：
$$\mathrm{I}\mathrm{V}(a)=?\sum _{v=1}^V\frac{\left|D^v\right|}{\left|D\right|}\mathrm{l}\mathrm{o}{\mathrm{g}}_2\frac{\left|D^v\right|}{\left|D\right|}\text{\hspace{1em}(4)}$$
$\mathrm{I}\mathrm{V}(a)$稱為屬性$a$的固有值。屬性$a$的可能取值數(shù)目越多(V越大)，則 $\mathrm{I}\mathrm{V}(a)$的值通常越大。增益率準則對可取值數(shù)目較少的屬性有所偏好，因此C4.5算法并不是直接選擇增益率最大的候選劃分屬性，而是使用一個啟發(fā)式：先從候選劃分屬性中找出信息增益高于平均水平的屬性，再從中選擇增益最高的。

(4) 基尼指數(shù)

CART(Classification and Regression Tree) 決策樹使用基尼指數(shù)(Gini index)來選擇劃分屬性，則數(shù)據(jù)集$D$的純度用基尼值定義為
$$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(D)=\sum _{k=1}^{|y|}\sum _{k^{\prime }?=k}{p}_k{p}_{k^{\prime }}=1?\sum _{k=1}^{|y|}{p}_k^2\text{\hspace{1em}(5)}$$
$\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D)$反映了從數(shù)據(jù)集D中隨機抽取兩個樣本，其類別標記不一致的概率。因此， $\mathrm{G}\mathrm{a}\mathrm{i}\mathrm{n}(D)$越小，數(shù)據(jù)集$D$的純度越高。
故，屬性$a$的基尼指數(shù)定義為
$$\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}\_\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}(D,a)=\sum _{k=1}^{|y|}\frac{\left|D^v\right|}{\left|D\right|}\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}(D^v)\text{\hspace{1em}(6)}$$
于是，我們選擇在候選屬性集合$A$中，選擇那么使得劃分后基尼指數(shù)最小的屬性作為最優(yōu)劃分屬性，
即 $a_{?}=\underset{a\in A}{\arg }\mathrm{G}\mathrm{i}\mathrm{n}\mathrm{i}\_\mathrm{i}\mathrm{n}\mathrm{d}\mathrm{e}\mathrm{x}(D,a)$

3 決策樹算法優(yōu)缺點

優(yōu)點：計算復(fù)雜度不高，輸出結(jié)果易于理解，對中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)；
缺點：可能會產(chǎn)生過度匹配問題；
適用數(shù)據(jù)范圍：數(shù)值型和標稱型。

4 實驗

以機器學(xué)習(xí)實戰(zhàn)書中的數(shù)據(jù)為例

trees.py

#trees.py from math import log import operatordef createDataSet(): #創(chuàng)建數(shù)據(jù)dataSet = [[1, 1, 'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no']]#labels = ['no surfacing','flippers']labels = ['不浮出水面', '腳蹼']#change to discrete valuesreturn dataSet, labelsdef calcShannonEnt(dataSet): #計算熵numEntries = len(dataSet)labelCounts = {}for featVec in dataSet: #the the number of unique elements and their occurancecurrentLabel = featVec[-1]if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1shannonEnt = 0.0for key in labelCounts:prob = float(labelCounts[key])/numEntriesshannonEnt -= prob * log(prob,2) #log base 2return shannonEntdef splitDataSet(dataSet, axis, value): # 劃分數(shù)據(jù)retDataSet = []for featVec in dataSet:if featVec[axis] == value:reducedFeatVec = featVec[:axis] #chop out axis used for splittingreducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec)return retDataSetdef chooseBestFeatureToSplit(dataSet): # 選擇最好的方式劃分數(shù)據(jù)集(利用信息增益)numFeatures = len(dataSet[0]) - 1 #the last column is used for the labelsbaseEntropy = calcShannonEnt(dataSet)bestInfoGain = 0.0; bestFeature = -1for i in range(numFeatures): #iterate over all the featuresfeatList = [example[i] for example in dataSet]#create a list of all the examples of this featureuniqueVals = set(featList) #get a set of unique valuesnewEntropy = 0.0for value in uniqueVals:subDataSet = splitDataSet(dataSet, i, value)prob = len(subDataSet)/float(len(dataSet))newEntropy += prob * calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropyif (infoGain > bestInfoGain): #compare this to the best gain so farbestInfoGain = infoGain #if better than current best, set to bestbestFeature = ireturn bestFeature #returns an integerdef majorityCnt(classList):classCount={}for vote in classList:if vote not in classCount.keys(): classCount[vote] = 0classCount[vote] += 1sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)return sortedClassCount[0][0]def createTree(dataSet,labels): # 創(chuàng)建樹classList = [example[-1] for example in dataSet]

main.py

# main.py from numpy import * import trees import treePlotter import matplotlib.pyplot as plt myData, labels=trees. createDataSet() # 讀取數(shù)據(jù) print(myData) # 打印數(shù)據(jù)entropy=trees.calcShannonEnt(myData) #計算熵 print(entropy)result=trees.chooseBestFeatureToSplit(myData) #利用信息增益得到?jīng)Q策樹 print(result) result_Tree=trees.createTree(myData, labels) print(result_Tree)

運行結(jié)果如下

---

參考資料

[1] 機器學(xué)習(xí)實戰(zhàn). 人民郵電出版社.
[2] https://coding.imooc.com/class/chapter/169.html#Anchor
[3] 機器學(xué)習(xí), 北京: 清華大學(xué)出版社, 2016年1月
[4] 機器學(xué)習(xí)(西瓜書). 公式推導(dǎo)解析

總結(jié)

以上是生活随笔為你收集整理的机器学习(6): 决策树算法 小结与实验的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。