ID3決策樹以及Python實現(xiàn)詳細過程
更新時間：2024年01月06日 10:26:43 作者：春風不曾溫柔
決策樹是我本人非常喜歡的機器學習模型,非常直觀容易理解,并且和數(shù)據(jù)結構的結合很緊密,下面這篇文章主要給大家介紹了關于ID3決策樹以及Python實現(xiàn)的相關資料,需要的朋友可以參考下
一、劃分特征的評價指標：
1、信息熵 Ent(D)：
信息熵，是度量樣本集合純度的一種指標，Ent(D)的值越小，則樣本集D的純度越高；
2、信息增益 Gain(D,a)：
信息增益越大，則意味著使用屬性a來劃分所獲得的“純度提升”越大；ID3決策樹算法就是基于信息增益來劃分屬性，下面介紹ID3決策樹的構建過程；
公式中各變量說明：
D：樣本集；
y：標簽（比如好瓜、壞瓜）；
pk：某一類樣本占總樣本數(shù)的比例；
V：屬性的取值（比如紋理屬性有3種取值：清晰、稍糊、模糊）；
Dv：屬性值==V從樣本集D劃分出的一個樣本子集；
二、決策樹學習算法偽代碼：
決策樹的生成是一個遞歸的過程，在決策樹基本算法中，有三種情形會導致遞歸返回：
當前結點包含的樣本全屬于同一類別，無需劃分；當前屬性集為空，或是所有樣本在所有屬性上取值相同，無法劃分；當前結點包含的樣本集合為空，不能劃分；
三、決策樹生成實例：
3.1 首先獲取一個訓練樣本集D，作為決策樹的訓練依據(jù)：
3.2 計算信息增益：
1、計算信息熵 Ent(D)：
2、計算當前特征集合 {色澤,根蒂,敲聲,紋理,臍部,觸感} 中各個特征a的信息增益Gain(D,a)：
以“色澤”為例計算Gain(D,色澤)：
色澤的取值：{青綠,烏黑,淺白}，使用“色澤”特征對D劃分可以得到3個子集：D1(色澤=青綠)={1,4,6,10,13,17}，D2(色澤=烏黑)={2,3,7,8,9,15}，D1(色澤=淺白)={5,11,12,14,16}，計算劃分子集后分支結點的熵 ：
所以，得到Gain(D,色澤)：
同理，計算其他特征的信息增益Gain(D,a)：
3.3 選取最優(yōu)信息增益，選取最優(yōu)劃分特征：
因為Gain(D,紋理)最大，所以選取“紋理”作為本輪劃分的最優(yōu)劃分特征，繼而可以得到基于“紋理”的根節(jié)點劃分：
3.4 決策樹算法再對每個分支進一步劃分（遞歸）：
將每個分支可以看成一個新的樣本集，進行進一步的劃分，在計算各特征信息增益時，需要將上一輪選出的最優(yōu)特征在樣本中去掉，不需要再對該特征進行比較。
就比如D1={1,2,3,4,5,6,8,10,15}，特征集合={色澤,根蒂,敲聲,臍部,觸感}?；贒1計算出各特征的信息增益Gain(D1,a)：
繼續(xù)選取最大的特征信息增益，選出最優(yōu)劃分特征，即重復3.3步驟，遞歸實現(xiàn)決策樹的建立；
3.5 生成最終的決策樹：
四、Python實現(xiàn)ID3決策樹：
總樣本集：
['青綠','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['烏黑','蜷縮','沉悶','清晰','凹陷','硬滑','好瓜'],
['烏黑','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['青綠','蜷縮','沉悶','清晰','凹陷','硬滑','好瓜'],
['青綠','稍蜷','濁響','清晰','稍凹','軟粘','好瓜'],
['烏黑','稍蜷','濁響','稍糊','稍凹','軟粘','好瓜'],
['烏黑','稍蜷','濁響','清晰','稍凹','硬滑','好瓜'],
['淺白','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['淺白','蜷縮','濁響','模糊','平坦','硬滑','壞瓜'],
['烏黑','稍蜷','沉悶','稍糊','稍凹','硬滑','壞瓜'],
['青綠','硬挺','清脆','清晰','平坦','軟粘','壞瓜'],
['淺白','蜷縮','濁響','模糊','平坦','軟粘','壞瓜'],
['青綠','稍蜷','濁響','稍糊','凹陷','硬滑','壞瓜'],
['淺白','稍蜷','沉悶','稍糊','凹陷','硬滑','壞瓜'],
['淺白','硬挺','清脆','模糊','平坦','硬滑','壞瓜'],
['烏黑','稍蜷','濁響','清晰','稍凹','軟粘','壞瓜'],
['青綠','蜷縮','沉悶','稍糊','稍凹','硬滑','壞瓜']
下面從總樣本種提取序號5、12、17為驗證集，剩下為訓練集進行訓練決策樹；
（1）訓練集：
['青綠','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['烏黑','蜷縮','沉悶','清晰','凹陷','硬滑','好瓜'],
['烏黑','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['青綠','蜷縮','沉悶','清晰','凹陷','硬滑','好瓜'],
['烏黑','稍蜷','濁響','稍糊','稍凹','軟粘','好瓜'],
['烏黑','稍蜷','濁響','清晰','稍凹','硬滑','好瓜'],
['淺白','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['淺白','蜷縮','濁響','模糊','平坦','硬滑','壞瓜'],
['烏黑','稍蜷','沉悶','稍糊','稍凹','硬滑','壞瓜'],
['淺白','蜷縮','濁響','模糊','平坦','軟粘','壞瓜'],
['青綠','稍蜷','濁響','稍糊','凹陷','硬滑','壞瓜'],
['淺白','稍蜷','沉悶','稍糊','凹陷','硬滑','壞瓜'],
['淺白','硬挺','清脆','模糊','平坦','硬滑','壞瓜'],
['青綠','蜷縮','沉悶','稍糊','稍凹','硬滑','壞瓜']
（2）驗證集：
['青綠','稍蜷','濁響','清晰','稍凹','軟粘'], ['好瓜']
['青綠','硬挺','清脆','清晰','平坦','軟粘'], ['壞瓜']
['烏黑','稍蜷','濁響','清晰','稍凹','軟粘'], ['壞瓜']
下面編寫各個函數(shù)，每個函數(shù)有特定的功能，代碼的分析過程已在code后注釋。
4.1 構建樣本集：
#? 構建數(shù)據(jù)集
# 返回一個元組 (dataSet,labels)
def createDataSet(): # 創(chuàng)造示例數(shù)據(jù)
dataSet=[['青綠','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['烏黑','蜷縮','沉悶','清晰','凹陷','硬滑','好瓜'],
['烏黑','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['青綠','蜷縮','沉悶','清晰','凹陷','硬滑','好瓜'],
['青綠','稍蜷','濁響','清晰','稍凹','軟粘','好瓜'],
['烏黑','稍蜷','濁響','稍糊','稍凹','軟粘','好瓜'],
['烏黑','稍蜷','濁響','清晰','稍凹','硬滑','好瓜'],
['烏黑','稍蜷','沉悶','稍糊','稍凹','硬滑','壞瓜'],
['青綠','硬挺','清脆','清晰','平坦','軟粘','壞瓜'],
['淺白','蜷縮','濁響','模糊','平坦','軟粘','壞瓜'],
['青綠','稍蜷','濁響','稍糊','凹陷','硬滑','壞瓜'],
['淺白','稍蜷','沉悶','稍糊','凹陷','硬滑','壞瓜'],
['烏黑','稍蜷','濁響','清晰','稍凹','軟粘','壞瓜'],
['青綠','蜷縮','沉悶','稍糊','稍凹','硬滑','壞瓜']]
labels = ['色澤','根蒂','敲聲','紋理','臍部','觸感'] #六個特征
return dataSet,labels函數(shù)作用：用于構建訓練集
變量說明：
- dataSet：樣本集
- labels：所有特征
4.2 計算信息熵：
#? 計算信息熵
# 返回輸入樣本集dataSet的信息熵 Ent
from math import log
def calEnt(dataSet):
sampleCounts=len(dataSet) # 樣本集的樣本數(shù)
labelCounts={} # key為標簽值label（好瓜、壞瓜），value為對應標簽key在樣本集中出現(xiàn)的次數(shù)
for sample in dataSet: # 遍歷樣本集dataSet中每個樣本sample
label=sample[-1] # 標簽label為樣本sample的最后一個元素值
if label not in labelCounts.keys(): # 如果該標簽label不在字典labelCounts的key值中
labelCounts[label]=0 # 則新增該key，并賦初值0
labelCounts[label]+=1 # 對遍歷到的每個sample統(tǒng)計其所屬標簽的個數(shù)
Ent=0.0 # 信息熵初始化
for key in labelCounts:
pro=float(labelCounts[key])/sampleCounts # 具體標簽占總樣本數(shù)的比例pro
Ent-=pro*log(pro,2) # 計算樣本集dataSet的信息熵Ent
return Ent函數(shù)作用：計算樣本集dataSet的信息熵E(dataSet)
變量說明：
dataSet：傳入的樣本集
sampleCounts：樣本集中的樣本數(shù)
labelCounts：key為標簽值（好瓜/壞瓜），value為對應標簽key在樣本集中出現(xiàn)的次數(shù)
sample：具體樣本
label：標簽（好瓜、壞瓜）
pro：具體標簽占總樣本數(shù)的比例
Ent：樣本集dataSet的熵 Ent(D)
4.3 按給定的特征值劃分出樣本子集：
#? 按給定特征值劃分出樣本子集
# 指定特征列的索引index，對特征值==value的樣本劃分出來為一個樣本子集retDataSet，并對這些樣本的value去掉，返回樣本子集 retDataSet
def splitDataSet(dataSet,index,value): # index是指定特征列的索引，value是該特征下的某一特征值
retDataSet=[]
for sample in dataSet: # 遍歷樣本集dataSet中的具體樣本sample
if sample[index]==value: # 找到目標特征值value的索引
# 去除特征值==value這些樣本的vlaue值
reducedSample=sample[:index] # 剪下目標索引前的列表
reducedSample.extend(sample[index+1:]) # 將目標索引后的列表添加到索引前列表的后面
retDataSet.append(reducedSample) # 將sample[index]==value并去除該vlaue的樣本添加到retDataSet樣本集中
return retDataSet函數(shù)作用：指定特征列的索引index，對樣本集中特征值==value的具體樣本sample劃分出來，組成一個dataSet的樣本子集retDataSet（并將這些樣本中的這些value去掉，去掉sample[index]的目的是因為下輪比較各特征信息增益Gain從而獲得最大信息增益bestGain（決定最優(yōu)劃分特征bestFeature）時，不能將已選出的最優(yōu)特征放在比較隊列中）
變量說明：
dataSet：傳入的樣本集
index：指定特征列的索引
value：指定特征的某一特征值
sample：dataSet的具體樣本
reducedSample：去除value后的具體樣本（該樣本sample[index]==value）
retDataSet：按指定某一特征值劃分出的樣本子集
4.4 選取當前樣本集下的最優(yōu)劃分特征索引：
#? 選取當前樣集下的最優(yōu)劃分特征索引
# 返回最優(yōu)劃分特征的索引 bestFeatureIndex
def chooseBestFeatureToSplit(dataSet):
featureCounts=len(dataSet[0])-1 # 獲取當前樣本集的特征個數(shù)，-1是因為最后一列是標簽
baseEnt=calEnt(dataSet) # 計算當前樣本集的信息熵Ent(D)
bestGain=0.0;bestFeatureIndex=-1 # 初始化最優(yōu)信息增益bestGain、最優(yōu)特征bestFeature
for i in range(featureCounts): # 遍歷每個特征，求各自的信息增益Gain
featValList=[sample[i] for sample in dataSet] # 第i個特征下所有樣本出現(xiàn)的特征值（有重復）
uniqueVals=set(featValList) # 第i個特征的可能特征值（無重復）
newEnt=0.0 # 初始化信息熵
for value in uniqueVals:
subDataSet=splitDataSet(dataSet,i,value) # 根據(jù)特定的特征值value劃分出的樣本子集
pro=len(subDataSet)/float(len(dataSet)) # 劃分出的樣本子集占總樣本數(shù)的比例
newEnt+=pro*calEnt(subDataSet) # 計算各特征值的熵并加和
Gain=baseEnt-newEnt # 計算信息增益Gain(D,a)
if(Gain>bestGain): # 求最大的信息增益Gain
bestGain=Gain
bestFeatureIndex=i # 獲取最優(yōu)劃分特征的索引
return bestFeatureIndex函數(shù)作用：計算各特征的信息增益Gain(dataset,feature)，從而選出最優(yōu)劃分特征bestFeature，最后返回最優(yōu)劃分特征的索引bestFeatureIndex；
變量說明：
dataSet：傳入的樣本集
featureCounts：當前樣本集中特征的個數(shù)
baseEnt：當前樣本集的熵 Ent(D)
bestGain：各特征中最大的信息增益 Gain(dataSet,bestFeature)
bestFeatureIndex：最優(yōu)劃分特征的索引列號
sample[i]：具體樣本第i個特征值
featureValList：第i個特征下所有樣本中出現(xiàn)的特征值（有重復值）
uniqueVals：第i個特征的可能特征值（無重復值）
newEnt：不同特征值下的熵 Ent(Di)
subDataSet：根據(jù)特定的特征值value劃分出的樣本子集
pro：樣本子集占總樣本數(shù)的比例
Gain：各個特征的信息增益Gain(D,a)
4.5 求樣本集中出現(xiàn)次數(shù)最多的標簽：
#? 求樣本集中出現(xiàn)次數(shù)最多的標簽
# 用于葉子節(jié)點的取值，返回樣本集中出現(xiàn)次數(shù)最多的標簽 sortedLabelCounts[0][0]
import operator
def majorLabel(labelList):
labelCounts={} # key為標簽（好瓜/壞瓜），value為標簽在labelList中出現(xiàn)的次數(shù)
for label in labelList: # 遍歷所有樣本的標簽
if label not in labelCounts.keys(): # 如果該標簽不在labelCounts的key值中
labelCounts[label]=0 # 則增加該key值，并賦初值=0
labelCounts[label]+=1 # 對labelCounts中已有的標簽計數(shù)+1
sortedLabelCounts=sorted(labelCounts.items(),key=operator.itemgetter(1),reverse=True) # 根據(jù)value值逆序排序labelCounts
return sortedLabelCounts[0][0] # 返回第一個元素的第一個元素（標簽）函數(shù)作用：選取葉子結點的取值，返回樣本集中出現(xiàn)次數(shù)最多的標簽（好瓜/壞瓜）sortedLabelCounts[0][0]；
變量說明：
labelList：返回樣本集中所有樣本的標簽（有重復值）
labelCounts：字典，key為標簽，value為該標簽key在labelList中出現(xiàn)的次數(shù)
label：具體標簽（好瓜/壞瓜）
labelCounts.keys()：labelCounts的key值
labelCounts[label]：labelCounts中key值==label對應的value值
sortedLabelCounts：根據(jù)value值，逆序排列l(wèi)abelCounts字典
sotredLabelCounts[0][0]：樣本集中出現(xiàn)次數(shù)最多的標簽
4.6 遞歸生成決策樹：
#? 生成決策樹 主方法
# 遞歸生成決策樹 decisionTree
# 遞歸是逐級由深向淺的返回
def createTree(dataSet,labels):
labelList=[sample[-1] for sample in dataSet] # 返回當前樣本集dataSet中所有樣本的標簽（有重復值列表）
# 跳出遞歸，生成葉子節(jié)點（好瓜/壞瓜）
if labelList.count(labelList[0])==len(labelList): # 如果labelList中的標簽完全相同
return labelList[0] # 則直接返回該標簽
if len(dataSet[0])==1: # 如果當前樣本集dataSet的樣本長度==1（只剩最后一列標簽，無特征可供繼續(xù)劃分又不滿足所有標簽相同）
return majorLabel(labelList) # 就返回出現(xiàn)次數(shù)最多的標簽作為葉子節(jié)點
bestFeatureIndex=chooseBestFeatureToSplit(dataSet) # 獲取當前樣本集dataSet最優(yōu)劃分特征的索引
bestFeature=labels[bestFeatureIndex] # 獲取當前樣本集dataSet的最優(yōu)劃分特征
decisionTree={bestFeature:{}} # 字典存儲決策樹的信息
del(labels[bestFeatureIndex]) # 刪除已經(jīng)選出的特征
featureVals=[sample[bestFeatureIndex] for sample in dataSet] # 樣本集中所有樣本中的最優(yōu)特征對應的特征值組成的列表（有重復值）
uniqueVals=set(featureVals) # 最優(yōu)特征對應的所有可能取值（無重復值）
for value in uniqueVals: # 遍歷最優(yōu)特征所有可能的取值value
subLabels=labels[:] # 將最優(yōu)特征去除后的特征列表傳遞給subLabels
decisionTree[bestFeature][value]=createTree(splitDataSet(dataSet,bestFeatureIndex,value),subLabels) # 遞歸生成decisionTree
return decisionTree函數(shù)作用：遞歸生成決策樹 decisionTree
變量說明：
dataSet：傳入的樣本集
labels：傳入的特征列表
labelList：存放樣本集dataSet中所有樣本的標簽（有重復值）
sample：樣本集的具體樣本
labelList[0]：第一個樣本的標簽
dataSet[0]：樣本集中的第一個樣本
majorLabel(labelList)：樣本集中出現(xiàn)次數(shù)最多的標簽
bestFeatureIndex：當前樣本集中最優(yōu)劃分特征的索引列
bestFeature：當前樣本集中最優(yōu)的劃分特征
labels[bestFeatureIndex]：最優(yōu)劃分特征索引對應的具體特征
decisionTree：生成的決策樹
featureVals：樣本集dataSet中最優(yōu)特征對應的所有特征值（有重復值）
uniqueVals：最優(yōu)特征對應的可能取值（無重復值）
value：最優(yōu)特征對應的具體取值
subLabels：去除最優(yōu)特征后的特征列表
4.7 對決策樣本進行分類：
#? 對驗證樣本進行分類 # 返回一個對樣本分類后的標簽classLabel def classify(decisionTree,features,testSample): rootFeature=list(decisionTree.keys())[0] # rootFeature：根節(jié)點是何種特征 rootDict=decisionTree[rootFeature] # rootDict為根節(jié)點的value值，是一個字典 rootFeatureIndex=features.index(rootFeature) # 獲取根節(jié)點在特征列表中的索引 for value in rootDict.keys(): # value為特征rootFeature的不同取值，并遍歷value if testSample[rootFeatureIndex]==value: # 如果待測樣本的該特征的特征值==value if type(rootDict[value])==dict: # 如果該特征值value對應的value'是一個字典 classLabel=classify(rootDict[value],features,testSample) # 則需要遞歸繼續(xù)向決策樹的下面結點查詢 else: # 如果該特征值value對應的value'是一個單獨的值（標簽） classLabel=rootDict[value] # 則該值就是要找的標簽 return classLabel # 返回該樣本testSample的標簽
函數(shù)作用：對傳入的待測樣本testSample根據(jù)已生成的決策樹decisionTree計算出該樣本的標簽（好瓜/壞瓜），返回該標簽 classLabel
變量說明：
decisionTree：某一結點出發(fā)的決策樹
features：所有特征列表
testSample：待測試樣本
decisionTree.keys()：（某一特征值下）對應根結點
decisionTree[rootFeature]：根節(jié)點對應的各個分支，字典
rootFeature：根節(jié)點（如紋理）
rootDict：根節(jié)點下的分支，字典（紋理結點對應的三個分支：模糊、清晰、稍糊）
rootFeatureIndex：節(jié)點在特征列表features中的索引；
value：以根節(jié)點為特征的不同特征取值（如模糊/清晰/稍糊）
testSample[rootFeatureIndex]：待測試樣本中以根節(jié)點為特征對應的具體特征值
rootDict[value]：具體特征值對應的value（可能是一個字典/標簽）
classLabel：該待測試樣本計算出的標簽
4.8 執(zhí)行：
if __name__=='__main__': # 如果在當前模塊/文件下執(zhí)行，將會指定下述代碼
dataSet, labels=createDataSet()
decisionTree=createTree(dataSet, labels)
print(f"\ndecisionTree={decisionTree}\n") # 輸出決策樹模型結果
# 驗證集
features= ['色澤','根蒂','敲聲','紋理','臍部','觸感'] # 特征列表
testSample=['淺白','蜷縮','濁響','清晰','凹陷','硬滑'] # 待測樣本
print(f"測試結果1sampleLabel= {classify(decisionTree,features,testSample)}\n") # 輸出測試結果
features= ['色澤','根蒂','敲聲','紋理','臍部','觸感'] # 特征列表
testSample=['淺白','硬挺','清脆','模糊','平坦','硬滑'] # 待測樣本
print(f"測試結果2sampleLabel= {classify(decisionTree,features,testSample)}\n") # 輸出測試結果
features= ['色澤','根蒂','敲聲','紋理','臍部','觸感'] # 特征列表
testSample=['淺白','蜷縮','濁響','模糊','平坦','硬滑'] # 待測樣本
print(f"測試結果3sampleLabel= {classify(decisionTree,features,testSample)}\n") # 輸出測試結果函數(shù)說明：執(zhí)行主函數(shù)代碼，利用上述各函數(shù)打印出最終的決策樹decisionTree并且對驗證集待測樣本進行測試檢驗
變量說明：
features：特征列表
testSample：待測試樣本
4.9 運行結果：
decisionTree={'紋理': {'稍糊': {'觸感': {'硬滑': '壞瓜', '軟粘': '好瓜'}}, '清晰': {'根蒂': {'硬挺': '壞瓜', '蜷縮': '好瓜', '稍蜷': {'色澤': {'青綠': '好瓜', '烏黑': {'觸感': {'硬滑': '好瓜', '軟粘': '壞瓜'}}}}}}, '模糊': '壞瓜'}}
測試結果1sampleLabel= 好瓜
測試結果2sampleLabel= 壞瓜
測試結果3sampleLabel= 壞瓜決策樹decisionTree：
{'紋理':
{'模糊': '壞瓜',
'清晰': {'根蒂':
{'稍蜷': {'色澤':
{'烏黑': {'觸感':
{'軟粘': '壞瓜',
'硬滑': '好瓜'}},
'青綠': '好瓜'}},
'硬挺': '壞瓜',
'蜷縮': '好瓜'}},
'稍糊': {'觸感':
{'軟粘': '好瓜',
'硬滑': '壞瓜'}}}}可視化為樹狀結構為：
4.10 實現(xiàn)決策樹的總代碼：
#! Decision Tree(ID3算法 信息增益Gain)
#? 構建數(shù)據(jù)集
# 返回一個元組 (dataSet,labels)
def createDataSet(): # 創(chuàng)造示例數(shù)據(jù)
dataSet=[['青綠','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['烏黑','蜷縮','沉悶','清晰','凹陷','硬滑','好瓜'],
['烏黑','蜷縮','濁響','清晰','凹陷','硬滑','好瓜'],
['青綠','蜷縮','沉悶','清晰','凹陷','硬滑','好瓜'],
['青綠','稍蜷','濁響','清晰','稍凹','軟粘','好瓜'],
['烏黑','稍蜷','濁響','稍糊','稍凹','軟粘','好瓜'],
['烏黑','稍蜷','濁響','清晰','稍凹','硬滑','好瓜'],
['烏黑','稍蜷','沉悶','稍糊','稍凹','硬滑','壞瓜'],
['青綠','硬挺','清脆','清晰','平坦','軟粘','壞瓜'],
['淺白','蜷縮','濁響','模糊','平坦','軟粘','壞瓜'],
['青綠','稍蜷','濁響','稍糊','凹陷','硬滑','壞瓜'],
['淺白','稍蜷','沉悶','稍糊','凹陷','硬滑','壞瓜'],
['烏黑','稍蜷','濁響','清晰','稍凹','軟粘','壞瓜'],
['青綠','蜷縮','沉悶','稍糊','稍凹','硬滑','壞瓜']]
labels = ['色澤','根蒂','敲聲','紋理','臍部','觸感'] #六個特征
return dataSet,labels
#? 計算信息熵
# 返回輸入樣本集dataSet的信息熵 Ent
from math import log
def calEnt(dataSet):
sampleCounts=len(dataSet) # 樣本集的樣本數(shù)
labelCounts={} # key為標簽值label（好瓜、壞瓜），value為對應標簽key在樣本集中出現(xiàn)的次數(shù)
for sample in dataSet: # 遍歷樣本集dataSet中每個樣本sample
label=sample[-1] # 標簽label為樣本sample的最后一個元素值
if label not in labelCounts.keys(): # 如果該標簽label不在字典labelCounts的key值中
labelCounts[label]=0 # 則新增該key，并賦初值0
labelCounts[label]+=1 # 對遍歷到的每個sample統(tǒng)計其所屬標簽的個數(shù)
Ent=0.0 # 信息熵初始化
for key in labelCounts:
pro=float(labelCounts[key])/sampleCounts # 具體標簽占總樣本數(shù)的比例pro
Ent-=pro*log(pro,2) # 計算樣本集dataSet的信息熵Ent
return Ent
#? 按給定特征值劃分出樣本子集
# 指定特征列的索引index，對特征值==value的樣本劃分出來為一個樣本子集retDataSet，并對這些樣本的value去掉，返回樣本子集 retDataSet
def splitDataSet(dataSet,index,value): # index是指定特征列的索引，value是該特征下的某一特征值
retDataSet=[]
for sample in dataSet: # 遍歷樣本集dataSet中的具體樣本sample
if sample[index]==value: # 找到目標特征值value的索引
# 去除特征值==value這些樣本的vlaue值
reducedSample=sample[:index] # 剪下目標索引前的列表
reducedSample.extend(sample[index+1:]) # 將目標索引后的列表添加到索引前列表的后面
retDataSet.append(reducedSample) # 將sample[index]==value并去除該vlaue的樣本添加到retDataSet樣本集中
return retDataSet
#? 選取當前樣集下的最優(yōu)劃分特征索引
# 返回最優(yōu)劃分特征的索引 bestFeatureIndex
def chooseBestFeatureToSplit(dataSet):
featureCounts=len(dataSet[0])-1 # 獲取當前樣本集的特征個數(shù)，-1是因為最后一列是標簽
baseEnt=calEnt(dataSet) # 計算當前樣本集的信息熵Ent(D)
bestGain=0.0;bestFeatureIndex=-1 # 初始化最優(yōu)信息增益bestGain、最優(yōu)特征bestFeature
for i in range(featureCounts): # 遍歷每個特征，求各自的信息增益Gain
featValList=[sample[i] for sample in dataSet] # 第i個特征下所有樣本出現(xiàn)的特征值（有重復）
uniqueVals=set(featValList) # 第i個特征的可能特征值（無重復）
newEnt=0.0 # 初始化信息熵
for value in uniqueVals:
subDataSet=splitDataSet(dataSet,i,value) # 根據(jù)特定的特征值value劃分出的樣本子集
pro=len(subDataSet)/float(len(dataSet)) # 劃分出的樣本子集占總樣本數(shù)的比例
newEnt+=pro*calEnt(subDataSet) # 計算各特征值的熵并加和
Gain=baseEnt-newEnt # 計算信息增益Gain(D,a)
if(Gain>bestGain): # 求最大的信息增益Gain
bestGain=Gain
bestFeatureIndex=i # 獲取最優(yōu)劃分特征的索引
return bestFeatureIndex
#? 求樣本集中出現(xiàn)次數(shù)最多的標簽
# 用于葉子節(jié)點的取值，返回樣本集中出現(xiàn)次數(shù)最多的標簽 sortedLabelCounts[0][0]
import operator
def majorLabel(labelList):
labelCounts={} # key為標簽（好瓜/壞瓜），value為標簽在labelList中出現(xiàn)的次數(shù)
for label in labelList: # 遍歷所有樣本的標簽
if label not in labelCounts.keys(): # 如果該標簽不在labelCounts的key值中
labelCounts[label]=0 # 則增加該key值，并賦初值=0
labelCounts[label]+=1 # 對labelCounts中已有的標簽計數(shù)+1
sortedLabelCounts=sorted(labelCounts.items(),key=operator.itemgetter(1),reverse=True) # 根據(jù)value值逆序排序labelCounts
return sortedLabelCounts[0][0] # 返回第一個元素的第一個元素（標簽）
#? 生成決策樹 主方法
# 遞歸生成決策樹 decisionTree
# 遞歸是逐級由深向淺的返回
def createTree(dataSet,labels):
labelList=[sample[-1] for sample in dataSet] # 返回當前樣本集dataSet中所有樣本的標簽（有重復值列表）
# 跳出遞歸，生成葉子節(jié)點（好瓜/壞瓜）
if labelList.count(labelList[0])==len(labelList): # 如果labelList中的標簽完全相同
return labelList[0] # 則直接返回該標簽
if len(dataSet[0])==1: # 如果當前樣本集dataSet的樣本長度==1（只剩最后一列標簽，無特征可供繼續(xù)劃分又不滿足所有標簽相同）
return majorLabel(labelList) # 就返回出現(xiàn)次數(shù)最多的標簽作為葉子節(jié)點
bestFeatureIndex=chooseBestFeatureToSplit(dataSet) # 獲取當前樣本集dataSet最優(yōu)劃分特征的索引
bestFeature=labels[bestFeatureIndex] # 獲取當前樣本集dataSet的最優(yōu)劃分特征
decisionTree={bestFeature:{}} # 字典存儲決策樹的信息
del(labels[bestFeatureIndex]) # 刪除已經(jīng)選出的特征
featureVals=[sample[bestFeatureIndex] for sample in dataSet] # 樣本集中所有樣本中的最優(yōu)特征對應的特征值組成的列表（有重復值）
uniqueVals=set(featureVals) # 最優(yōu)特征對應的所有可能取值（無重復值）
for value in uniqueVals: # 遍歷最優(yōu)特征所有可能的取值value
subLabels=labels[:] # 將最優(yōu)特征去除后的特征列表傳遞給subLabels
decisionTree[bestFeature][value]=createTree(splitDataSet(dataSet,bestFeatureIndex,value),subLabels) # 遞歸生成decisionTree
return decisionTree
#? 對驗證樣本進行分類
# 返回一個對樣本分類后的標簽classLabel
def classify(decisionTree,features,testSample):
rootFeature=list(decisionTree.keys())[0] # rootFeature：根節(jié)點是何種特征
rootDict=decisionTree[rootFeature] # rootDict為根節(jié)點的value值，是一個字典
rootFeatureIndex=features.index(rootFeature) # 獲取根節(jié)點在特征列表中的索引
for value in rootDict.keys(): # value為特征rootFeature的不同取值，并遍歷value
if testSample[rootFeatureIndex]==value: # 如果待測樣本的該特征的特征值==value
if type(rootDict[value])==dict: # 如果該特征值value對應的value'是一個字典
classLabel=classify(rootDict[value],features,testSample) # 則需要遞歸繼續(xù)向決策樹的下面結點查詢
else: # 如果該特征值value對應的value'是一個單獨的值（標簽）
classLabel=rootDict[value] # 則該值就是要找的標簽
return classLabel # 返回該樣本testSample的標簽
if __name__=='__main__': # 如果在當前模塊/文件下執(zhí)行，將會指定下述代碼
dataSet, labels=createDataSet()
decisionTree=createTree(dataSet, labels)
print(f"\ndecisionTree={decisionTree}\n") # 輸出決策樹模型結果
# 驗證集
features= ['色澤','根蒂','敲聲','紋理','臍部','觸感'] # 特征列表
testSample=['淺白','蜷縮','濁響','清晰','凹陷','硬滑'] # 待測樣本
print(f"測試結果1sampleLabel= {classify(decisionTree,features,testSample)}\n") # 輸出測試結果
features= ['色澤','根蒂','敲聲','紋理','臍部','觸感'] # 特征列表
testSample=['淺白','硬挺','清脆','模糊','平坦','硬滑'] # 待測樣本
print(f"測試結果2sampleLabel= {classify(decisionTree,features,testSample)}\n") # 輸出測試結果
features= ['色澤','根蒂','敲聲','紋理','臍部','觸感'] # 特征列表
testSample=['淺白','蜷縮','濁響','模糊','平坦','硬滑'] # 待測樣本
print(f"測試結果3sampleLabel= {classify(decisionTree,features,testSample)}\n") # 輸出測試結果總結
到此這篇關于ID3決策樹以及Python實現(xiàn)的文章就介紹到這了,更多相關Python實現(xiàn)ID3決策樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家介紹了pymilvus?offset參數(shù)不生效解決示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
在?Python?編程中,異常處理不僅是一項基本技能,更是一種高級藝術,本文將帶大家深入了解下Python中的復雜異常處理機制,希望對大家有所幫助2025-01-01
本文主要介紹了django配置使用asgi的實現(xiàn)步驟,支持 ASGI 協(xié)議能處理傳統(tǒng)HTTP請求,也能支持實時WebSocket通信,具有一定的參考價值,感興趣的可以了解一下2025-03-03
今天小編就為大家分享一篇Python修改文件往指定行插入內(nèi)容的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-01-01
Python win32com 操作Exce的l簡單方法(必看)
下面小編就為大家?guī)硪黄狿ython win32com 操作Exce的l簡單方法(必看)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
在日常系統(tǒng)管理和維護工作中,執(zhí)行DOS（Disk?Operating?System）命令是一項必不可少的任務,下面我們就來看看如何使用Python編寫一個簡單的DOS命令輔助工具,簡化系統(tǒng)管理任務吧2024-01-01
Python實現(xiàn)Opencv cv2.Canny()邊緣檢測
這篇博客將介紹Canny邊緣檢測的概念，并利用cv2.Canny()實現(xiàn)邊緣檢測，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-07-07
Spark是一款分布式的計算框架，用于調(diào)度成百上千的服務器集群，計算TB、PB乃至EB級別的海量數(shù)據(jù)，PySpark是由Spark官方開發(fā)的Python語言第三方庫，本文重點介紹PySpark和RDD對象，感興趣的朋友一起看看吧2023-01-01
在Python中,我們可以使用不同的方式來校驗數(shù)值的空值、字符串的空值以及對象的空值,本文為大家整理了一些常見的方法,希望對大家有所幫助2024-01-01
這篇文章主要介紹了python switch 實現(xiàn)多分支選擇功能,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12