手寫(xiě)代碼實(shí)現(xiàn)基于信息熵劃分的決策樹(shù)算法
文章目錄
- 手寫(xiě)代碼實(shí)現(xiàn)基于信息熵劃分的決策樹(shù)算法
- 1. 簡(jiǎn)介
- 2. 算法實(shí)現(xiàn)思路
- 3.代碼如下
- 參考
1. 簡(jiǎn)介
閱讀本文需要以下背景知識(shí)：
-
掌握周志華《西瓜書(shū)》第四章決策樹(shù)原理
-
Python3.0基礎(chǔ)語(yǔ)法及數(shù)據(jù)類(lèi)型及操作
不了解決策樹(shù)請(qǐng)點(diǎn)擊下面鏈接西瓜書(shū)第四章決策樹(shù)學(xué)習(xí)筆記
本文是基于信息熵準(zhǔn)則進(jìn)行劃分選擇的決策樹(shù)算法的手寫(xiě)實(shí)現(xiàn)，不使用現(xiàn)有的機(jī)器學(xué)習(xí)包。算法流程見(jiàn)《西瓜書(shū)》第四章第一節(jié)。數(shù)據(jù)集使用西瓜數(shù)據(jù)集3.0（數(shù)據(jù)集在代碼中不需要另外下載），實(shí)現(xiàn)語(yǔ)言為Python3.0。代碼注解詳細(xì)，適合新手，歡迎轉(zhuǎn)載
2. 算法實(shí)現(xiàn)思路
算法流程是現(xiàn)成的，關(guān)鍵是如何把數(shù)據(jù)集嵌入到算法中并實(shí)現(xiàn)遞歸，我的思路如下：
對(duì)決策樹(shù)不同功能進(jìn)行劃分，每個(gè)功能封裝成函數(shù)，不同功能的函數(shù)有
-
def createDataSet()
#對(duì)數(shù)據(jù)集進(jìn)行加工，返回?cái)?shù)據(jù)集dataSet和特征集labels
-
def get_Value(dataSet, labels)
#以字典labelsCounts返回?cái)?shù)據(jù)集dataSet中所有的特征，和對(duì)應(yīng)特征的所有取值
-
def calcShannonEnt(dataSet)
#計(jì)算dataSet的信息熵。返回信息熵?cái)?shù)值
-
def chooseBestFeatureToSplit(dataSet)
#計(jì)算出信息增益，選擇信息增益最大的特征作為最優(yōu)劃分屬性。返回最優(yōu)屬性在特征集labels中的索引
-
def splitDataSet(dataSet, bestFeat, value)
#由給定的父數(shù)據(jù)集dataSet，最優(yōu)特征 bestFeat，和最優(yōu)特征的取值value（由labelsCounts獲得）劃分出數(shù)據(jù)子集，返回?cái)?shù)據(jù)子集
-
def majorityCnt(classList)
#輸入數(shù)據(jù)集dataSet的類(lèi)別標(biāo)簽列classList得到在數(shù)據(jù)集dataSet中類(lèi)別最多的樣本的類(lèi)別名（字符串）
-
def createTree(dataSet, labels, labelscounts)
#這是一個(gè)遞歸函數(shù)，輸入數(shù)據(jù)集dataSet，特征集labels和所有特征取值字典labelscounts得到一個(gè)具有一層分支的樹(shù)，要是這層分支中每個(gè)子集subdataSet都是葉節(jié)點(diǎn)，創(chuàng)建字典，以被劃分的最優(yōu)屬性的取值value為鍵，對(duì)應(yīng)這個(gè)取值的葉節(jié)點(diǎn)類(lèi)型為值（
葉節(jié)點(diǎn)判定標(biāo)準(zhǔn)：集合中樣本都相同標(biāo)簽也相同標(biāo)為葉節(jié)點(diǎn)，葉類(lèi)型為集合中樣本標(biāo)簽；集合中樣本都相同但是標(biāo)簽不同標(biāo)為葉節(jié)點(diǎn)，葉類(lèi)型為集合中眾數(shù)樣本類(lèi)別；集合為空集標(biāo)為葉結(jié)點(diǎn)，葉類(lèi)別為其父節(jié)點(diǎn)眾數(shù)樣本類(lèi)別
）。若這層分支中不全為葉節(jié)點(diǎn)，還有內(nèi)部節(jié)點(diǎn)。則對(duì)于葉節(jié)點(diǎn)，創(chuàng)建字典，以被劃分的最優(yōu)屬性的取值為鍵，對(duì)應(yīng)這個(gè)取值的葉節(jié)點(diǎn)類(lèi)型為值。對(duì)于內(nèi)部節(jié)點(diǎn)，把這個(gè)子集subdataSet作為新的父集，以新父集的劃分最優(yōu)屬性鍵，值是一個(gè)字典，并調(diào)用函數(shù)def createTree(subdataSet, sublabels, labelscounts)完成遞歸。返回一個(gè)以字典形式存儲(chǔ)的決策樹(shù)
-
treePlotter.createPlot(desicionTree)
#調(diào)用庫(kù)函數(shù)將決策樹(shù)繪出，treePlotter包是自定義包，代碼及使用方法見(jiàn)此treePlotter
3.代碼如下
#基于ID3算法的信息增益來(lái)實(shí)現(xiàn)的決策樹(shù)
#調(diào)用庫(kù)
from
math
import
log
import
operator
import
treePlotter
#自定義包，包和源程序應(yīng)在同一文件夾，包代碼見(jiàn)鏈接
''' 西瓜數(shù)據(jù)集3.0， dataset=[ # 1 ['青綠', '蜷縮', '濁響', '清晰', '凹陷', '硬滑', 0.697, 0.460, '好瓜'], # 2 ['烏黑', '蜷縮', '沉悶', '清晰', '凹陷', '硬滑', 0.774, 0.376, '好瓜'], # 3 ['烏黑', '蜷縮', '濁響', '清晰', '凹陷', '硬滑', 0.634, 0.264, '好瓜'], # 4 ['青綠', '蜷縮', '沉悶', '清晰', '凹陷', '硬滑', 0.608, 0.318, '好瓜'], # 5 ['淺白', '蜷縮', '濁響', '清晰', '凹陷', '硬滑', 0.556, 0.215, '好瓜'], # 6 ['青綠', '稍蜷', '濁響', '清晰', '稍凹', '軟粘', 0.403, 0.237, '好瓜'], # 7 ['烏黑', '稍蜷', '濁響', '稍糊', '稍凹', '軟粘', 0.481, 0.149, '好瓜'], # 8 ['烏黑', '稍蜷', '濁響', '清晰', '稍凹', '硬滑', 0.437, 0.211, '好瓜'], # ---------------------------------------------------- # 9 ['烏黑', '稍蜷', '沉悶', '稍糊', '稍凹', '硬滑', 0.666, 0.091, '壞瓜'], # 10 ['青綠', '硬挺', '清脆', '清晰', '平坦', '軟粘', 0.243, 0.267, '壞瓜'], # 11 ['淺白', '硬挺', '清脆', '模糊', '平坦', '硬滑', 0.245, 0.057, '壞瓜'], # 12 ['淺白', '蜷縮', '濁響', '模糊', '平坦', '軟粘', 0.343, 0.099, '壞瓜'], # 13 ['青綠', '稍蜷', '濁響', '稍糊', '凹陷', '硬滑', 0.639, 0.161, '壞瓜'], # 14 ['淺白', '稍蜷', '沉悶', '稍糊', '凹陷', '硬滑', 0.657, 0.198, '壞瓜'], # 15 ['烏黑', '稍蜷', '濁響', '清晰', '稍凹', '軟粘', 0.360, 0.370, '壞瓜'], # 16 ['淺白', '蜷縮', '濁響', '模糊', '平坦', '硬滑', 0.593, 0.042, '壞瓜'], # 17 ['青綠', '蜷縮', '沉悶', '稍糊', '稍凹', '硬滑', 0.719, 0.103, '壞瓜'] ] '''
#導(dǎo)入數(shù)據(jù)，數(shù)據(jù)集有八個(gè)特征 '色澤', '根蒂', '敲聲', '紋理'，'臍部'，'觸感'，'密度'，'含糖率' ，
#其中密度和含糖率是連續(xù)值，為了簡(jiǎn)略程序，我們忽略他們。為接下來(lái)要計(jì)算它們的信息增益率，來(lái)選擇節(jié)點(diǎn)的構(gòu)成方式做準(zhǔn)備。
def
createDataSet
(
)
:
""" 對(duì)數(shù)據(jù)集進(jìn)行一定處理，以方便顯示，不出現(xiàn)亂碼 色澤Color-> 0: 淺白 | 1: 青綠 | 2: 烏黑 根蒂Root-> 0: 硬挺 | 1: 稍蜷 | 2: 蜷縮 敲聲Knock-> 0: 清脆 | 1: 濁響 | 2：沉悶 紋理Texture-> 0: 清晰 | 1: 稍糊 | 2：模糊 臍部Umbilical-> 0: 平坦 | 1: 稍凹 | 2: 凹陷 觸感Touch-> 0: 硬滑 | 1: 軟粘 標(biāo)簽lab->'GoodMalen'| 'BadMalen' """
dataSet
=
[
[
1
,
2
,
1
,
0
,
2
,
0
,
'GoodMalen'
]
,
[
2
,
2
,
2
,
0
,
2
,
0
,
'GoodMalen'
]
,
[
2
,
2
,
1
,
0
,
2
,
0
,
'GoodMalen'
]
,
[
1
,
2
,
2
,
0
,
2
,
0
,
'GoodMalen'
]
,
[
0
,
2
,
1
,
0
,
2
,
0
,
'GoodMalen'
]
,
[
1
,
1
,
1
,
0
,
1
,
1
,
'GoodMalen'
]
,
[
2
,
1
,
1
,
1
,
1
,
1
,
'GoodMalen'
]
,
[
2
,
1
,
1
,
0
,
1
,
0
,
'GoodMalen'
]
,
[
2
,
1
,
2
,
1
,
1
,
0
,
'BadMalen'
]
,
[
1
,
0
,
0
,
0
,
0
,
1
,
'BadMalen'
]
,
[
0
,
0
,
0
,
2
,
0
,
0
,
'BadMalen'
]
,
[
0
,
2
,
1
,
2
,
0
,
1
,
'BadMalen'
]
,
[
1
,
1
,
1
,
1
,
2
,
0
,
'BadMalen'
]
,
[
0
,
1
,
2
,
1
,
2
,
0
,
'BadMalen'
]
,
[
2
,
1
,
1
,
0
,
1
,
1
,
'BadMalen'
]
,
[
0
,
1
,
1
,
2
,
0
,
0
,
'BadMalen'
]
,
[
1
,
1
,
2
,
1
,
1
,
0
,
'BadMalen'
]
]
labels
=
[
'Color'
,
'Root'
,
'Knock'
,
'Texture'
,
'Umbilical'
,
'Touch'
]
return
dataSet
,
labels
#獲得每個(gè)特征的所有出現(xiàn)的取值
def
get_Values
(
dataSet
,
labels
)
:
''' 輸入：一個(gè)數(shù)據(jù)集 輸出：數(shù)據(jù)集中每個(gè)特征的所有取值，字典形式；鍵是特征名，值是對(duì)應(yīng)特征的所有取值 描述：獲得特征的取值，為分支劃分做準(zhǔn)備 '''
labelsCounts
=
{
}
#初始化字典
for
label
in
labels
:
#遍歷特征集
index
=
labels
.
index
(
label
)
#獲得特征名稱(chēng)在特征集中的索引
featValues
=
[
example
[
index
]
for
example
in
dataSet
]
#取出一個(gè)特征的所有取值
uniqueVals
=
set
(
featValues
)
#利用集合性質(zhì)數(shù)據(jù)去重
labelsCounts
[
label
]
=
uniqueVals
#將去重后的數(shù)據(jù)放入字典中，鍵名為特征名字
return
labelsCounts
#計(jì)算數(shù)據(jù)集信息熵
def
calcShannonEnt
(
dataSet
)
:
""" 輸入：數(shù)據(jù)集 輸出：數(shù)據(jù)集的信息熵 描述：計(jì)算給定數(shù)據(jù)集的信息熵；熵越大，數(shù)據(jù)集的混亂程度越大 """
numEntries
=
len
(
dataSet
)
#樣本數(shù)
labelCounts
=
{
}
#創(chuàng)建一個(gè)數(shù)據(jù)字典：key是最后一列的數(shù)值（即標(biāo)簽，也就是目標(biāo)分類(lèi)的類(lèi)別），value是屬于該類(lèi)別的樣本個(gè)數(shù)，這個(gè)字典用來(lái)計(jì)數(shù)各個(gè)類(lèi)別的樣本的個(gè)數(shù)
for
featVec
in
dataSet
:
#遍歷數(shù)據(jù)集，每次取一行就是一個(gè)樣本
currentLabel
=
featVec
[
-
1
]
#取出每行最后一列的元素（也就是樣本標(biāo)簽）給currentLabel
if
currentLabel
not
in
labelCounts
.
keys
(
)
:
#判斷：標(biāo)簽在不在字典labelCounts中？
labelCounts
[
currentLabel
]
=
0
#不在字典中則給字典創(chuàng)建新鍵值對(duì)，key是標(biāo)簽，value設(shè)為0
labelCounts
[
currentLabel
]
+=
1
#計(jì)數(shù)每一類(lèi)樣本的數(shù)量， {'GoodMalen': 8, 'BadMalen': 9}
# print(labelCounts)
shannonEnt
=
0.0
# 初始化信息熵
for
key
in
labelCounts
:
#遍歷數(shù)據(jù)字典的鍵
prob
=
float
(
labelCounts
[
key
]
)
/
numEntries
#計(jì)算數(shù)據(jù)集D中K類(lèi)樣本所占比例Pk
shannonEnt
-=
prob
*
log
(
prob
,
2
)
#計(jì)算信息熵log2
return
shannonEnt
#計(jì)算樣本集中類(lèi)別數(shù)最多的類(lèi)別
def
calmaxCnt
(
dataSet
)
:
''' 輸入：數(shù)據(jù)集 輸出：在輸入數(shù)據(jù)集中類(lèi)別數(shù)最多的類(lèi)別名稱(chēng) 描述：對(duì)劃分出的數(shù)據(jù)集為空的子數(shù)據(jù)集不能劃分，標(biāo)記為葉節(jié)點(diǎn)，將其類(lèi)別設(shè)定為其父節(jié)點(diǎn)所含樣本中類(lèi) 別數(shù)最多的類(lèi)別名稱(chēng) '''
classCount
=
{
}
#創(chuàng)建字典
for
featVec
in
dataSet
:
#對(duì)數(shù)據(jù)集中每一行遍歷
if
featVec
[
-
1
]
not
in
classCount
.
keys
(
)
:
#鍵已存在字典中+1,不存在字典中創(chuàng)建后初始為0后+1
classCount
[
featVec
[
-
1
]
]
=
0
classCount
[
featVec
[
-
1
]
]
+=
1
items
=
list
(
classCount
.
items
(
)
)
#字典轉(zhuǎn)為列表
items
.
sort
(
key
=
lambda
x
:
x
[
1
]
,
reverse
=
True
)
#列表以值來(lái)排序（從大到小）
return
items
[
0
]
[
0
]
#輸出類(lèi)別數(shù)最多的類(lèi)別名稱(chēng)
#對(duì)數(shù)據(jù)集進(jìn)行葉節(jié)點(diǎn)標(biāo)記的準(zhǔn)則
def
majorityCnt
(
classList
)
:
""" #返回該數(shù)據(jù)集中類(lèi)別數(shù)最多的類(lèi)名 #該函數(shù)使用分類(lèi)名稱(chēng)的列表(某個(gè)數(shù)據(jù)集或者其子集的)，然后創(chuàng)建鍵值為classList中唯一值的 #數(shù)據(jù)字典。字典對(duì)象的存儲(chǔ)了classList中每個(gè)類(lèi)標(biāo)簽出現(xiàn)的頻率。最后利用operator操作鍵值排序字典， #并返回出現(xiàn)次數(shù)最多的分類(lèi)名稱(chēng) 輸入：分類(lèi)類(lèi)別列表 輸出：子節(jié)點(diǎn)的分類(lèi) 描述：數(shù)據(jù)集已經(jīng)處理了所有屬性，但是類(lèi)標(biāo)簽依然不是唯一的， 則采用多數(shù)判決的方法決定該子節(jié)點(diǎn)的分類(lèi) """
classCount
=
{
}
#創(chuàng)建字典
for
vote
in
classList
:
#對(duì)類(lèi)名列表遍歷
if
vote
not
in
classCount
.
keys
(
)
:
#鍵已存在字典中+1,不存在字典中創(chuàng)建后初始為0后+1
classCount
[
vote
]
=
0
classCount
[
vote
]
+=
1
# print(classCount)
sortedClassCount
=
sorted
(
classCount
.
iteritems
(
)
,
key
=
operator
.
itemgetter
(
1
)
,
reversed
=
True
)
#將字典轉(zhuǎn)換成列表并按照值（[i][1]）進(jìn)行從大到小排序
return
sortedClassCount
[
0
]
[
0
]
#選出最優(yōu)劃分特征
def
chooseBestFeatureToSplit
(
dataSet
)
:
""" 選取當(dāng)前數(shù)據(jù)集下，用于劃分?jǐn)?shù)據(jù)集的最優(yōu)特征 輸入：數(shù)據(jù)集dataSet 輸出：最好的劃分維度 描述：選擇最好的數(shù)據(jù)集劃分維度，返回的是該特征在該數(shù)據(jù)集中的索引 """
numFeatures
=
len
(
dataSet
[
0
]
)
-
1
#特征feature個(gè)數(shù)，數(shù)據(jù)集列數(shù)減一，減去的那個(gè)一是類(lèi)別標(biāo)簽
baseEntropy
=
calcShannonEnt
(
dataSet
)
#計(jì)算父樣本集的信息熵
bestInfoGain
=
0.0
#初始化信息增益為0.0
bestFeature
=
-
1
#初始化最佳特征索引維度
for
i
in
range
(
numFeatures
)
:
#遍歷每個(gè)特征
featList
=
[
example
[
i
]
for
example
in
dataSet
]
##獲取數(shù)據(jù)集中當(dāng)前特征下的所有值組成list
uniqueVals
=
set
(
featList
)
#集合數(shù)據(jù)去重，獲得當(dāng)前特征的所有取值
newEntropy
=
0.0
# splitInfo = 0.0 #初始化固有值，用于C4.5決策樹(shù)實(shí)現(xiàn)
for
value
in
uniqueVals
:
#遍歷該特征每一種取值結(jié)果
subDataSet
=
splitDataSet
(
dataSet
,
i
,
value
)
#獲得該種特征該種結(jié)果的子樣本集（去除了這種特征后的）
prob
=
len
(
subDataSet
)
/
float
(
len
(
dataSet
)
)
#計(jì)算|Dv|/|D|,計(jì)算子樣本集樣本數(shù)所占父樣本數(shù)權(quán)重
newEntropy
+=
prob
*
calcShannonEnt
(
subDataSet
)
#計(jì)算各個(gè)子樣本集的權(quán)重*子樣本集信息熵并加和
# splitInfo += -prob * log(prob, 2) #計(jì)算該特征固有值，用于C4.5決策樹(shù)實(shí)現(xiàn)
infoGain
=
baseEntropy
-
newEntropy
#這個(gè)feature的infoGain
# if (splitInfo == 0): # fix the overflow bug #用于C4.5決策樹(shù)實(shí)現(xiàn)
# continue #用于C4.5決策樹(shù)實(shí)現(xiàn)
# infoGainRatio = infoGain / splitInfo #這個(gè)feature的infoGainRatio#用于C4.5決策樹(shù)實(shí)現(xiàn)
if
(
infoGain
>
bestInfoGain
)
:
#選擇最大的信息增益gain對(duì)應(yīng)的特征，并獲得其索引，若用于C4.5決策樹(shù)實(shí)現(xiàn)需要更改一部分變量名稱(chēng)
bestInfoGain
=
infoGain
bestFeature
=
i
#選擇最大的gain對(duì)應(yīng)的特征，并把其索引賦值給bestFeature
return
bestFeature
#劃分?jǐn)?shù)據(jù)集，為下一層計(jì)算準(zhǔn)備
def
splitDataSet
(
dataSet
,
bestFeat
,
value
)
:
""" #axis是dataSet數(shù)據(jù)集下要進(jìn)行特征劃分的列號(hào)例如outlook是0列，value是該列下某個(gè)特征值，0列中的sunny 輸入：數(shù)據(jù)集，選擇維度，選擇值 輸出：劃分?jǐn)?shù)據(jù)集 描述：按照給定特征劃分?jǐn)?shù)據(jù)集；想要將某個(gè)數(shù)據(jù)集以某特征完全劃分成幾個(gè)子數(shù)據(jù)集需要遍歷該特征的不同取值并重復(fù)調(diào)用這個(gè)函數(shù) 新數(shù)據(jù)集由樣本中某特征axis取指定值value的樣本組成，且去除了該特征axis的列以避免之后的對(duì)該特征重復(fù)劃分 """
retDataSet
=
[
]
#初始化一個(gè)列表作為子集
for
featVec
in
dataSet
:
#對(duì)數(shù)據(jù)集中每一行遍歷
if
featVec
[
bestFeat
]
==
value
:
#當(dāng)某樣本在被選擇的特征列axis上取值＝value（我們所指定的特征值）時(shí)
reduceFeatVec
=
featVec
[
:
bestFeat
]
#復(fù)制出選中特征列前面的列
reduceFeatVec
.
extend
(
featVec
[
bestFeat
+
1
:
]
)
#由上面的列拼接選中特征列后面的列
#上兩行代碼作用是除去原樣本集的第axis列
retDataSet
.
append
(
reduceFeatVec
)
#把除去第axis列的樣本放到新數(shù)據(jù)集中
return
retDataSet
#多重字典構(gòu)建樹(shù)
def
createTree
(
dataSet
,
labels
,
labelscounts
)
:
""" 輸入：數(shù)據(jù)集，特征標(biāo)簽 輸出：決策樹(shù)，每個(gè)數(shù)據(jù)集中優(yōu)勢(shì)類(lèi)別的名稱(chēng) 描述：遞歸構(gòu)建決策樹(shù) """
classList
=
[
example
[
-
1
]
for
example
in
dataSet
]
#返回當(dāng)前數(shù)據(jù)集下標(biāo)簽列所有值
if
classList
.
count
(
classList
[
0
]
)
==
len
(
classList
)
:
#classList所有元素都相等，即類(lèi)別完全相同，停止劃分，設(shè)置為葉節(jié)點(diǎn)，以該集合中的類(lèi)別名作為葉節(jié)點(diǎn)標(biāo)簽
return
classList
[
0
]
#返回該類(lèi)標(biāo)簽值
if
len
(
dataSet
[
0
]
)
==
1
:
#因?yàn)槊看蝿澐侄汲チ吮粍澐痔卣髦祵?duì)應(yīng)的列，那么隨著劃分的進(jìn)行，列越來(lái)越短，直到只剩下標(biāo)
#簽列，該標(biāo)簽列中對(duì)應(yīng)的樣本都是特征值完全相同的，此時(shí)按照葉節(jié)點(diǎn)命名規(guī)則，取該標(biāo)簽列中類(lèi)
#別數(shù)最多的類(lèi)別作為葉節(jié)點(diǎn)的劃分
return
majorityCnt
(
classList
)
#遍歷完所有特征后返回出現(xiàn)次數(shù)最多的類(lèi)別標(biāo)簽值
bestFeat
=
chooseBestFeatureToSplit
(
dataSet
)
#獲得下次劃分時(shí)候的最佳特征的索引
#選擇最大的gain對(duì)應(yīng)的feature
bestFeatLabel
=
labels
[
bestFeat
]
#由索引取得最優(yōu)特征名稱(chēng)
# 這里直接使用字典變量來(lái)存儲(chǔ)樹(shù)信息，這對(duì)于繪制樹(shù)形圖很重要。
myTree
=
{
bestFeatLabel
:
{
}
}
#當(dāng)前數(shù)據(jù)集選取最好的特征存儲(chǔ)在bestFeat中
del
(
labels
[
bestFeat
]
)
#在labels中刪除已經(jīng)被選擇的特征
uniqueVals
=
labelscounts
[
bestFeatLabel
]
#獲得最佳特征對(duì)應(yīng)的所有特征值取值
for
value
in
uniqueVals
:
#對(duì)所有特征取值遍歷
subLabels
=
labels
[
:
]
#獲得子集的特征集
subdataSet
=
splitDataSet
(
dataSet
,
bestFeat
,
value
)
#劃分出數(shù)據(jù)子集
if
len
(
subdataSet
)
==
0
:
#若劃分出的數(shù)據(jù)子集為空集
myTree
[
bestFeatLabel
]
[
value
]
=
calmaxCnt
(
dataSet
)
#數(shù)據(jù)子集設(shè)置為葉節(jié)點(diǎn)，用數(shù)據(jù)子集的父集中眾數(shù)樣本類(lèi)別作為葉節(jié)點(diǎn)標(biāo)簽
else
:
myTree
[
bestFeatLabel
]
[
value
]
=
createTree
(
subdataSet
,
subLabels
,
labelscounts
)
#以最優(yōu)特征劃分?jǐn)?shù)據(jù)集為多個(gè)數(shù)據(jù)子集，并提供子集特征集，放入createTree（）函數(shù)中開(kāi)始遞歸
return
myTree
#返回字典形式樹(shù)結(jié)構(gòu)信息
#可視化決策樹(shù)的結(jié)果
dataSet
,
labels
=
createDataSet
(
)
#生成數(shù)據(jù)集D和特征集A
#print(len(dataSet[0]))#7
labelscounts
=
get_Values
(
dataSet
,
labels
)
#獲得每種特征對(duì)應(yīng)的所有特征值取值
#print(labelscounts)#{'Color': {0, 1, 2}, 'Root': {0, 1, 2}, 'Knock': {0, 1, 2}, 'Texture': {0, 1, 2}, 'Umbilical': {0, 1, 2}, 'Touch': {0, 1}}
labels_tmp
=
labels
[
:
]
#復(fù)制特征集
desicionTree
=
createTree
(
dataSet
,
labels_tmp
,
labelscounts
)
#創(chuàng)建決策樹(shù)
print
(
desicionTree
)
#{'Texture': {0: {'Root': {0: 'BadMalen', 1: {'Color': {0: 'GoodMalen', 1: 'GoodMalen', 2: {'Touch': {0: 'GoodMalen', 1: 'BadMalen'}}}}, 2: 'GoodMalen'}}, 1: {'Touch': {0: 'BadMalen', 1: 'GoodMalen'}}, 2: 'BadMalen'}}
#決策樹(shù)是一層層嵌套的字典,鍵是節(jié)點(diǎn)名（內(nèi)部節(jié)點(diǎn)）或者特征值（子樹(shù)的劃分），值是一個(gè)字典（子樹(shù)）或者類(lèi)別名（葉節(jié)點(diǎn)）
treePlotter
.
createPlot
(
desicionTree
)
#使用treePlotter繪制決策樹(shù)，
#對(duì)新數(shù)據(jù)進(jìn)行分類(lèi)
def
classify
(
inputTree
,
featLabels
,
testVec
)
:
""" 輸入：決策樹(shù)，分類(lèi)標(biāo)簽，測(cè)試數(shù)據(jù) 輸出：測(cè)試數(shù)據(jù)的決策結(jié)果 描述：跑決策樹(shù)去預(yù)測(cè)測(cè)試數(shù)據(jù)的標(biāo)簽，返回一個(gè)預(yù)測(cè)值 """
# print(testVec)
classLabel
=
[
]
#初始化測(cè)試數(shù)據(jù)標(biāo)簽
firstStr
=
list
(
inputTree
.
keys
(
)
)
[
0
]
#取出輸入樹(shù)中第一層字典的鍵名（某個(gè)特征）列表。樹(shù)字典中第一層只有一個(gè)鍵值對(duì)，是父節(jié)點(diǎn)名字（鍵）及其對(duì)應(yīng)子分支（值：字典形式）
secondDict
=
inputTree
[
firstStr
]
#取出輸入樹(shù)字典中父節(jié)點(diǎn)鍵對(duì)應(yīng)的值：除去了輸入樹(shù)第一層的樹(shù)字典:二層樹(shù)字典{0: {'B': {0: 'BadMalen', 1: {'A': {1: 'GoodMalen', 2: {'F': {0: 'GoodMalen', 1: 'BadMalen'}}}}, 2: 'GoodMalen'}}, 1: {'F': {0: 'BadMalen', 1: 'GoodMalen'}}, 2: 'BadMalen'}
featIndex
=
featLabels
.
index
(
firstStr
)
#獲得輸入樹(shù)中第一層字典的鍵名（父節(jié)點(diǎn)名稱(chēng)：某個(gè)特征）對(duì)應(yīng)特征名在特征集中的索引
for
key
in
secondDict
.
keys
(
)
:
#對(duì)第二層樹(shù)的鍵進(jìn)行遍歷，keys_value{'0','1','2'}，第二層樹(shù)的鍵的取值keys_value是對(duì)應(yīng)父節(jié)點(diǎn)名字的特征值取值
if
testVec
[
featIndex
]
==
key
:
# test數(shù)據(jù)的父節(jié)點(diǎn)上特征的取了哪個(gè)特征值（{'0','1','2'}），就走哪個(gè)子分支
if
type
(
secondDict
[
key
]
)
.
__name__
==
'dict'
:
# 如果子分支的鍵值對(duì)中的值secondDict[key]仍然是字典，則進(jìn)行遞歸
classLabel
=
classify
(
secondDict
[
key
]
,
featLabels
,
testVec
)
#遞歸函數(shù)的輸入是（子分支的鍵值對(duì)中的值secondDict[key]（字典，作為輸入樹(shù)），特征集，測(cè)試數(shù)據(jù)）
else
:
# 如果子分支的鍵值對(duì)中的值secondDict[key]已經(jīng)只是分類(lèi)標(biāo)簽了，則返回這個(gè)類(lèi)別標(biāo)簽
# print(testVec)
classLabel
=
secondDict
[
key
]
return
classLabel
#返回測(cè)試數(shù)據(jù)的分類(lèi)標(biāo)簽
# Create Test Set生成測(cè)試集
def
createTestSet
(
)
:
""" 色澤Color-> 0: 淺白 | 1: 青綠 | 2: 烏黑 根蒂Root-> 0: 硬挺 | 1: 稍蜷 | 2: 蜷縮 敲聲Knock-> 0: 清脆 | 1: 濁響 | 2：沉悶 紋理Texture-> 0: 清晰 | 1: 稍糊 | 2：模糊 臍部Umbilical-> 0: 平坦 | 1: 稍凹 | 2: 凹陷 觸感Touch-> 0: 硬滑 | 1: 軟粘 標(biāo)簽lab->'GoodMalen'| 'BadMalen' """
testSet
=
[
[
0
,
1
,
0
,
0
,
1
,
0
]
,
[
1
,
1
,
2
,
1
,
1
,
0
]
]
return
testSet
inputTree
=
desicionTree
#導(dǎo)入已經(jīng)建立的決策樹(shù)
featLabels
=
[
'Color'
,
'Root'
,
'Knock'
,
'Texture'
,
'Umbilical'
,
'Touch'
]
#定義特征集
testVec
=
[
0
,
1
,
0
,
0
,
1
,
0
]
#一個(gè)測(cè)試數(shù)據(jù)
classify
(
inputTree
,
featLabels
,
testVec
)
#對(duì)測(cè)試數(shù)據(jù)分類(lèi)
#print(classify(inputTree, featLabels, testVec))
#對(duì)多條新數(shù)據(jù)進(jìn)行分類(lèi)
def
classifyAll
(
inputTree
,
featLabels
,
testDataSet
)
:
""" 輸入：決策樹(shù)，分類(lèi)標(biāo)簽，測(cè)試數(shù)據(jù)集 輸出：決策結(jié)果 描述：跑決策樹(shù) """
classLabelAll
=
[
]
#初始化標(biāo)簽集
for
testVec
in
testDataSet
:
#對(duì)測(cè)試數(shù)據(jù)集中的數(shù)據(jù)逐行遍歷，對(duì)測(cè)試數(shù)據(jù)集中的數(shù)據(jù)逐個(gè)測(cè)試
# print(testVec)
classLabelAll
.
append
(
classify
(
inputTree
,
featLabels
,
testVec
)
)
#將測(cè)試結(jié)果添加到標(biāo)簽集中
return
classLabelAll
#返回測(cè)試集的標(biāo)簽集
testSet
=
createTestSet
(
)
#獲得測(cè)試集
print
(
'classifyResult:\n'
,
classifyAll
(
desicionTree
,
labels
,
testSet
)
)
#打印分類(lèi)結(jié)果
參考
周志華. (2016). 機(jī)器學(xué)習(xí). 清華大學(xué)出版社, 北京
決策樹(shù)的python實(shí)現(xiàn)
決策樹(shù)算法及python實(shí)現(xiàn)
treePlotter模塊
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
