1 決策樹算法
決策樹（Decision Tree)是一類常見的機器學(xué)習(xí)方法，是一種非常常用的分類方法，它是一種監(jiān)督學(xué)習(xí)。常見的決策樹算法有ID3，C4.5、C5.0和CART（classification and regression tree），CART的分類效果一般要優(yōu)于其他決策樹。
決策樹是基于樹狀結(jié)構(gòu)來進行決策的，一般地，一棵決策樹包含一個根節(jié)點、若干個內(nèi)部節(jié)點和若干個葉節(jié)點。
每個內(nèi)部節(jié)點表示一個屬性上的判斷
每個分支代表一個判斷結(jié)果的輸出
每個葉節(jié)點代表一種分類結(jié)果。
根節(jié)點包含樣本全集
決策樹學(xué)習(xí)的目的是為了產(chǎn)生一棵泛化能力強，即處理未見示例能力強的決策樹，其基本流程遵循簡單且直觀的“分而治之”（divide-and-conquer）策略。
本文主要介紹ID3算法，ID3算法的核心是根據(jù)信息增益來選擇進行劃分的特征，然后遞歸地構(gòu)建決策樹。
1.1 特征選擇
特征選擇也即選擇最優(yōu)劃分屬性，從當(dāng)前數(shù)據(jù)的特征中選擇一個特征作為當(dāng)前節(jié)點的劃分標(biāo)準(zhǔn)。 隨著劃分過程不斷進行，希望決策樹的分支節(jié)點所包含的樣本盡可能屬于同一類別，即節(jié)點的“純度”越來越高。
1.2 熵（entropy）
熵表示事務(wù)不確定性的程度，也就是信息量的大?。ㄒ话阏f信息量大，就是指這個時候背后的不確定因素太多），熵的公式如下：
其中， p(xi)是分類 xi 出現(xiàn)的概率，n是分類的數(shù)目?？梢钥闯?，熵的大小只和變量的概率分布有關(guān)。
對于在X的條件下Y的條件熵，是指在X的信息之后，Y這個變量的信息量（不確定性）的大小，計算公式如下：
例如，當(dāng)只有A類和B類的時候，p(A)=p(B)=0.5，熵的大小為：
當(dāng)只有A類或只有B類時，
所以當(dāng)Entropy最大為1的時候，是分類效果最差的狀態(tài)，當(dāng)它最小為0的時候，是完全分類的狀態(tài)。因為熵等于零是理想狀態(tài)，一般實際情況下，熵介于0和1之間 。
熵的不斷最小化，實際上就是提高分類正確率的過程。
1.3 信息增益
信息增益：在劃分?jǐn)?shù)據(jù)集之前之后信息發(fā)生的變化，計算每個特征值劃分?jǐn)?shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。
定義屬性A對數(shù)據(jù)集D的信息增益為infoGain(D|A)，它等于D本身的熵，減去 給定A的條件下D的條件熵，即：
信息增益的意義：引入屬性A后，原來數(shù)據(jù)集D的不確定性減少了多少。
計算每個屬性引入后的信息增益，選擇給D帶來的信息增益最大的屬性，即為最優(yōu)劃分屬性。一般，信息增益越大，則意味著使用屬性A來進行劃分所得到的的“純度提升”越大。
2 ID3算法的python實現(xiàn)
以西瓜數(shù)據(jù)集為例
·watermalon.csv·文件內(nèi)容如下：
讀取文件數(shù)據(jù)
import numpy as np
import pandas as pd
import math
data = pd.read_csv('work/watermalon.csv')
data
計算熵
def info(x,y):
if x != y and x != 0:
# 計算當(dāng)前情況的熵
return -(x/y)*math.log2(x/y) - ((y-x)/y)*math.log2((y-x)/y)
if x == y or x == 0:
# 純度最大，熵值為0
return 0
info_D = info(8,17)
info_D
結(jié)果為：
0.9975025463691153
計算信息增益
# 計算每種情況的熵
seze_black_entropy = -(4/6)*math.log2(4/6)-(2/6)*math.log2(2/6)
seze_green_entropy = -(3/6)*math.log2(3/6)*2
seze_white_entropy = -(1/5)*math.log2(1/5)-(4/5)*math.log2(4/5)
# 計算色澤特征色信息熵
seze_entropy = (6/17)*seze_black_entropy+(6/17)*seze_green_entropy+(5/17)*seze_white_entropy
print(seze_entropy)
# 計算信息增益
info_D - seze_entropy
結(jié)果為：
0.10812516526536531
查看每種根蒂中好壞瓜情況的分布情況
data.根蒂.value_counts()
# 查看每種根蒂中好壞瓜情況的分布情況
print(data[data.根蒂=='蜷縮'])
print(data[data.根蒂=='稍蜷'])
print(data[data.根蒂=='硬挺'])
gendi_entropy = (8/17)*info(5,8)+(7/17)*info(3,7)+(2/17)*info(0,2)
gain_col = info_D - gendi_entropy
gain_col
根蒂的信息增益為：0.142674959566793
查看每種敲聲中好壞瓜情況的分布情況
data.敲聲.value_counts()
# 查看每種敲聲中好壞瓜情況的分布情況
print(data[data.敲聲=='濁響'])
print(data[data.敲聲=='沉悶'])
print(data[data.敲聲=='清脆'])
qiaosheng_entropy = (10/17)*info(6,10)+(5/17)*info(2,5)+(2/17)*info(0,2)
info_gain = info_D - qiaosheng_entropy
info_gain
查看每種紋理中好壞瓜情況的分布情況
data.紋理.value_counts()
# 查看每種紋理中好壞瓜情況的分布情況
print(data[data.紋理=="清晰"])
print(data[data.紋理=="稍糊"])
print(data[data.紋理=="模糊"])
wenli_entropy = (9/17)*info(7,9)+(5/17)*info(1,5)+(3/17)*info(0,3)
info_gain = info_D - wenli_entropy
info_gain
同理查看其他列的分布情況，這里不做演示
繪制可視化樹
import matplotlib.pylab as plt
import matplotlib
# 能夠顯示中文
matplotlib.rcParams['font.sans-serif'] = ['SimHei']
matplotlib.rcParams['font.serif'] = ['SimHei']
# 分叉節(jié)點，也就是決策節(jié)點
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
# 葉子節(jié)點
leafNode = dict(boxstyle="round4", fc="0.8")
# 箭頭樣式
arrow_args = dict(arrowstyle="<-")
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
"""
繪制一個節(jié)點
:param nodeTxt: 描述該節(jié)點的文本信息
:param centerPt: 文本的坐標(biāo)
:param parentPt: 點的坐標(biāo)，這里也是指父節(jié)點的坐標(biāo)
:param nodeType: 節(jié)點類型,分為葉子節(jié)點和決策節(jié)點
:return:
"""
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)
def getNumLeafs(myTree):
"""
獲取葉節(jié)點的數(shù)目
:param myTree:
:return:
"""
# 統(tǒng)計葉子節(jié)點的總數(shù)
numLeafs = 0
# 得到當(dāng)前第一個key，也就是根節(jié)點
firstStr = list(myTree.keys())[0]
# 得到第一個key對應(yīng)的內(nèi)容
secondDict = myTree[firstStr]
# 遞歸遍歷葉子節(jié)點
for key in secondDict.keys():
# 如果key對應(yīng)的是一個字典，就遞歸調(diào)用
if type(secondDict[key]).__name__ == 'dict':
numLeafs += getNumLeafs(secondDict[key])
# 不是的話，說明此時是一個葉子節(jié)點
else:
numLeafs += 1
return numLeafs
def getTreeDepth(myTree):
"""
得到數(shù)的深度層數(shù)
:param myTree:
:return:
"""
# 用來保存最大層數(shù)
maxDepth = 0
# 得到根節(jié)點
firstStr = list(myTree.keys())[0]
# 得到key對應(yīng)的內(nèi)容
secondDic = myTree[firstStr]
# 遍歷所有子節(jié)點
for key in secondDic.keys():
# 如果該節(jié)點是字典，就遞歸調(diào)用
if type(secondDic[key]).__name__ == 'dict':
# 子節(jié)點的深度加1
thisDepth = 1 + getTreeDepth(secondDic[key])
# 說明此時是葉子節(jié)點
else:
thisDepth = 1
# 替換最大層數(shù)
if thisDepth > maxDepth:
maxDepth = thisDepth
return maxDepth
def plotMidText(cntrPt, parentPt, txtString):
"""
計算出父節(jié)點和子節(jié)點的中間位置，填充信息
:param cntrPt: 子節(jié)點坐標(biāo)
:param parentPt: 父節(jié)點坐標(biāo)
:param txtString: 填充的文本信息
:return:
"""
# 計算x軸的中間位置
xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
# 計算y軸的中間位置
yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
# 進行繪制
createPlot.ax1.text(xMid, yMid, txtString)
def plotTree(myTree, parentPt, nodeTxt):
"""
繪制出樹的所有節(jié)點，遞歸繪制
:param myTree: 樹
:param parentPt: 父節(jié)點的坐標(biāo)
:param nodeTxt: 節(jié)點的文本信息
:return:
"""
# 計算葉子節(jié)點數(shù)
numLeafs = getNumLeafs(myTree=myTree)
# 計算樹的深度
depth = getTreeDepth(myTree=myTree)
# 得到根節(jié)點的信息內(nèi)容
firstStr = list(myTree.keys())[0]
# 計算出當(dāng)前根節(jié)點在所有子節(jié)點的中間坐標(biāo),也就是當(dāng)前x軸的偏移量加上計算出來的根節(jié)點的中心位置作為x軸（比如說第一次：初始的x偏移量為：-1/2W,計算出來的根節(jié)點中心位置為：(1+W)/2W，相加得到：1/2），當(dāng)前y軸偏移量作為y軸
cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
# 繪制該節(jié)點與父節(jié)點的聯(lián)系
plotMidText(cntrPt, parentPt, nodeTxt)
# 繪制該節(jié)點
plotNode(firstStr, cntrPt, parentPt, decisionNode)
# 得到當(dāng)前根節(jié)點對應(yīng)的子樹
secondDict = myTree[firstStr]
# 計算出新的y軸偏移量，向下移動1/D，也就是下一層的繪制y軸
plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
# 循環(huán)遍歷所有的key
for key in secondDict.keys():
# 如果當(dāng)前的key是字典的話，代表還有子樹，則遞歸遍歷
if isinstance(secondDict[key], dict):
plotTree(secondDict[key], cntrPt, str(key))
else:
# 計算新的x軸偏移量，也就是下個葉子繪制的x軸坐標(biāo)向右移動了1/W
plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
# 打開注釋可以觀察葉子節(jié)點的坐標(biāo)變化
# print((plotTree.xOff, plotTree.yOff), secondDict[key])
# 繪制葉子節(jié)點
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
# 繪制葉子節(jié)點和父節(jié)點的中間連線內(nèi)容
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
# 返回遞歸之前，需要將y軸的偏移量增加，向上移動1/D，也就是返回去繪制上一層的y軸
plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
def createPlot(inTree):
"""
需要繪制的決策樹
:param inTree: 決策樹字典
:return:
"""
# 創(chuàng)建一個圖像
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
# 計算出決策樹的總寬度
plotTree.totalW = float(getNumLeafs(inTree))
# 計算出決策樹的總深度
plotTree.totalD = float(getTreeDepth(inTree))
# 初始的x軸偏移量，也就是-1/2W，每次向右移動1/W，也就是第一個葉子節(jié)點繪制的x坐標(biāo)為：1/2W，第二個：3/2W，第三個：5/2W，最后一個：(W-1)/2W
plotTree.xOff = -0.5/plotTree.totalW
# 初始的y軸偏移量，每次向下或者向上移動1/D
plotTree.yOff = 1.0
# 調(diào)用函數(shù)進行繪制節(jié)點圖像
plotTree(inTree, (0.5, 1.0), '')
# 繪制
plt.show()
if __name__ == '__main__':
createPlot(mytree)
總結(jié)
決策樹ID3是一種經(jīng)典的機器學(xué)習(xí)算法，用于解決分類問題。它通過在特征空間中構(gòu)建樹形結(jié)構(gòu)來進行決策，并以信息增益作為劃分標(biāo)準(zhǔn)。ID3算法的關(guān)鍵在于選擇最佳的屬性進行劃分，以最大化信息增益。通過Python實現(xiàn)ID3算法，我們可以構(gòu)建出一棵高效而準(zhǔn)確的決策樹模型，用于分類預(yù)測和決策分析。文章來源：http://www.zghlxwxcb.cn/news/detail-717007.html
參考
https://zhuanlan.zhihu.com/p/133846252
https://cuijiahua.com/blog/2017/11/ml_2_decision_tree_1.html
https://blog.csdn.net/tauvan/article/details/121028351文章來源地址http://www.zghlxwxcb.cn/news/detail-717007.html
到了這里，關(guān)于【人工智能與機器學(xué)習(xí)】決策樹ID3及其python實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
