簡述
決策樹是機(jī)器學(xué)習(xí)的一類常見算法谣辞，其核心思想是通過構(gòu)建一個樹狀模型來對新樣本進(jìn)行預(yù)測。樹的葉結(jié)點(diǎn)是預(yù)測結(jié)果沐扳，而所有非葉結(jié)點(diǎn)皆是一個個決策過程泥从。決策樹很多任務(wù)都 是為了數(shù)據(jù)中所蘊(yùn)含的知識信息，因此決策樹可以使用不熟悉的數(shù)據(jù)集合沪摄，并從中提取出一系列規(guī)則躯嫉，機(jī)器學(xué)習(xí)算法最終將使用這些機(jī)器從數(shù)據(jù)集中創(chuàng)造的規(guī)則。
ps：決策樹實(shí)際上就是一個將數(shù)據(jù)按屬性分堆的過程杨拐。雖然名字叫的挺高大上的祈餐，但是背后的邏輯卻十分簡單。（其實(shí)大多數(shù)算法的思想都很簡單戏阅，大家不要被復(fù)雜的公式嚇到）昼弟，那么它較難的地方就不在于這個背后邏輯了啤它，而在于奕筐，比如我們是根據(jù)什么策略來決定屬性測試的順序的，因?yàn)槲颐磳傩缘膬?yōu)先級有特殊偏好变骡；選定屬性的取值的標(biāo)準(zhǔn)是什么离赫；構(gòu)建的決策樹是否足夠泛化等問題。
決策樹代碼
from math import log
import operator
def calcShannonEnt(dataSet): # 計(jì)算數(shù)據(jù)的熵(entropy)
numEntries=len(dataSet) # 數(shù)據(jù)條數(shù)
labelCounts={}
for featVec in dataSet:
currentLabel=featVec[-1] # 每行數(shù)據(jù)的最后一個字（類別）
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel]=0
labelCounts[currentLabel]+=1 # 統(tǒng)計(jì)有多少個類以及每個類的數(shù)量
shannonEnt=0
for key in labelCounts:
prob=float(labelCounts[key])/numEntries # 計(jì)算單個類的熵值
shannonEnt-=prob*log(prob,2) # 累加每個類的熵值
return shannonEnt
def createDataSet1(): # 創(chuàng)造示例數(shù)據(jù)
dataSet = [['青綠' , '蜷縮', '濁響', '清晰', '凹陷', '硬滑', '好瓜'],
['烏黑' , '蜷縮' , '沉悶' , '清晰' , '凹陷' , '硬滑' , '好瓜'] ,
['烏黑' , '蜷縮' , '濁響' , '清晰' , '凹陷' , '硬滑' , '好瓜'] ,
['青綠' , '蜷縮' , '沉悶' , '清晰' , '凹陷' , '硬滑' , '好瓜'] ,
['淺白' , '蜷縮' , '濁響' , '清晰' , '凹陷' , '硬滑' , '好瓜'] ,
['青綠' , '稍縮' , '濁響' , '清晰' , '稍凹' , '軟粘' , '好瓜'] ,
['烏黑' , '稍縮' , '濁響' , '稍糊' , '稍凹' , '軟粘' , '好瓜'] ,
['烏黑' , '稍縮' , '濁響' , '清晰' , '稍凹' , '硬滑' , '好瓜'] ,
['烏黑' , '稍縮' , '沉悶' , '稍糊' , '稍凹' , '硬滑' , '好瓜'] ,
['青綠' , '硬挺' , '清脆' , '清晰' , '平坦' , '硬滑' , '壞瓜'] ,
['淺白' , '硬挺' , '清脆' , '模糊' , '平坦' , '軟粘' , '壞瓜'] ,
['淺白' , '蜷縮' , '濁響' , '模糊' , '平坦' , '硬滑' , '壞瓜'] ,
['青綠' , '稍縮' , '濁響' , '稍糊' , '凹陷' , '軟粘' , '壞瓜'] ,
['淺白' , '稍縮' , '沉悶' , '稍糊' , '凹陷' , '硬滑' , '壞瓜'] ,
['烏黑' , '稍縮' , '濁響' , '清晰' , '稍凹' , '軟粘' , '壞瓜'] ,
['淺白' , '蜷縮' , '濁響' , '模糊' , '平坦' , '硬滑' , '壞瓜'] ,
['青綠' , '蜷縮' , '沉悶' , '稍糊' , '稍凹' , '硬滑' , '壞瓜'] ]
labels = ['色澤', '根蒂', '敲聲', '紋理', '臍部', '觸感'] #6個特征
return dataSet,labels
def splitDataSet(dataSet,axis,value): # 按某個特征分類后的數(shù)據(jù)
retDataSet=[]
for featVec in dataSet:
if featVec[axis]==value:
reducedFeatVec =featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
def chooseBestFeatureToSplit(dataSet): # 選擇最優(yōu)的分類特征
numFeatures = len(dataSet[0])-1
baseEntropy = calcShannonEnt(dataSet) # 原始的熵
bestInfoGain = 0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy = 0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet,i,value)
prob =len(subDataSet)/float(len(dataSet))
newEntropy +=prob*calcShannonEnt(subDataSet) # 按特征分類后的熵
infoGain = baseEntropy - newEntropy # 原始熵與按特征分類后的熵的差值
if (infoGain>bestInfoGain): # 若按某特征劃分后塌碌，熵值減少的最大渊胸，則次特征為最優(yōu)分類特征
bestInfoGain=infoGain
bestFeature = i
return bestFeature
def majorityCnt(classList): #按分類后類別數(shù)量排序，比如：最后分類為2好瓜1壞瓜台妆，則判定為好瓜翎猛；
classCount={}
for vote in classList:
if vote not in classCount.keys():
classCount[vote]=0
classCount[vote]+=1
sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0]
def createTree(dataSet,labels):
classList=[example[-1] for example in dataSet] # 類別：好瓜或壞瓜
if classList.count(classList[0])==len(classList):
return classList[0]
if len(dataSet[0])==1:
return majorityCnt(classList)
bestFeat=chooseBestFeatureToSplit(dataSet) #選擇最優(yōu)特征
bestFeatLabel=labels[bestFeat]
myTree={bestFeatLabel:{}} #分類結(jié)果以字典形式保存
del(labels[bestFeat])
featValues=[example[bestFeat] for example in dataSet]
uniqueVals=set(featValues)
for value in uniqueVals:
subLabels=labels[:]
myTree[bestFeatLabel][value]=createTree(splitDataSet\
(dataSet,bestFeat,value),subLabels)
return myTree
if __name__=='__main__':
dataSet, labels=createDataSet1() # 創(chuàng)造示列數(shù)據(jù)
print(createTree(dataSet, labels)) # 輸出決策樹模型結(jié)果
這里參考了andy老師的源碼胖翰，參考資料：https://gitee.com/ZHBIT-MachineLearning/Machine-Learning-Base/blob/master/Fourth_DecisionTree/Fourth_DecisionTree.py#
知識點(diǎn)
1、信息熵
“信息熵”（information entropy）是度量樣本集合純度最常用的一種指標(biāo)切厘。其代表的是不同的類別在數(shù)據(jù)在總數(shù)據(jù)集中的熵的和萨咳，當(dāng)樣本集合越“純”時，信息熵越幸吒濉（信息熵的取值范圍為0～log2(k)）培他。
2、信息增益
原始信息熵與新的劃分后的信息墑之差就是這次屬性劃分的“信息增益”（information gain）遗座，所以我們的屬性劃分選擇就是在每個結(jié)點(diǎn)找到最高信息增益的屬性舀凛。
3、增益率
增益率是讓信息增益除以選擇的劃分屬性的“固有值”（intrinsic value）途蒋。一般來說屬性a的可能取值數(shù)目越多猛遍，則固有值越大。
4号坡、基尼指數(shù)
原始基尼值與新劃分后的不同樣本集合的基尼值之和的差值就是“基尼指數(shù)”（Gini index）螃壤，而基尼值的公式如下：
Gini(D) = 1 - pk2
基尼值反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個樣本，其類別標(biāo)記不一致的概率筋帖。因此奸晴，基尼值越小，則數(shù)據(jù)集D的純度越高日麸。
決策樹的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
1寄啼、計(jì)算量簡單，可解釋性強(qiáng)代箭，比較適合處理有缺失屬性值的樣本墩划，能夠處理不相關(guān)的特征；
缺點(diǎn)：
1嗡综、單顆決策樹分類能力弱乙帮，并且對連續(xù)值變量難以處理；
2极景、容易過擬合（后續(xù)出現(xiàn)了隨機(jī)森林察净，減小了過擬合現(xiàn)象）；
決策樹構(gòu)建步驟
我們在劃分中盼樟，希望決策樹的分支結(jié)點(diǎn)所包含的樣本盡可能屬于同一類別氢卡，即結(jié)點(diǎn)的“純度”（purity）越來越高。要使得結(jié)點(diǎn)純度越來越高晨缴，我們得要選擇合適的指標(biāo)來對純度進(jìn)行評估译秦，并且我們也得要在這些指標(biāo)上對屬性的劃分進(jìn)行選擇。目前決策樹主流使用的屬性劃分指標(biāo)為以下三個（如何量化純度）：
［1］信息增益
"信息熵" (information entropy)是度量樣本集合純度最常用的一種指標(biāo).假定當(dāng)前樣本集合 D 中第 k 類樣本所占的比例為 Pk
(k = 1, 2,. . . , IYI) ，則 D的信息墑定義為：
屬性劃分邏輯是這樣的：信息熵代表的是樣本集合的純度筑悴，當(dāng)用一個屬性對樣本進(jìn)行劃分后们拙，分開的不同樣本集合的信息墑之和純度最高，那么這個屬性就是目前最好的劃分選擇阁吝。
如何度量數(shù)據(jù)集的無序程度的方式是計(jì)算信息熵睛竣。
即信息增益（information gain）=原始信息熵－新的劃分后的信息墑，所以我們的屬性劃分選擇就是在每個結(jié)點(diǎn)找到最高信息增益的屬性求摇。
［2］增益率
增益率是讓信息增益除以選擇的劃分屬性的“固有值”（intrinsic value）射沟。
為何要引入增益率？因?yàn)樵鲆媛适且粋€增量△值与境，引入增益率可以解決信息增益對可取值數(shù)目較多的屬性有所偏好的問題验夯，更加正確的描述樣本集合純度。
然而信息增益除以固有值后獲得的增益率反而是偏愛取值數(shù)目較少的屬性的摔刁。
解決辦法：先從候選劃分屬性中選出信息增益高于平均水平的屬性挥转，再從中選擇增益率最高的。
［3］基尼指數(shù)
基尼值的公式如下：
從上式可以看出共屈，基尼值反映了從數(shù)據(jù)集D中隨機(jī)抽取兩個樣本绑谣，其類別標(biāo)記不一致的概率。因此拗引，基尼值越小借宵，則數(shù)據(jù)集D的純度越高。
那么同信息增益的選擇策略一樣：當(dāng)用一個屬性對樣本進(jìn)行劃分后矾削，原始基尼值與新劃分后的不同樣本集合的基尼值之和的差值就是“基尼指數(shù)”（Gini index）壤玫，所以我們的屬性劃分選擇就是在每個結(jié)點(diǎn)找到劃分后最高基尼指數(shù)的屬性。
［4］剪枝處理
剪枝（pruning）是決策樹學(xué)習(xí)算法對付“過擬合”的主要手段哼凯。為了盡可能正確分類訓(xùn)練樣本欲间，會不斷的進(jìn)行結(jié)點(diǎn)劃分，有時會造成決策樹分支過多断部，這時就可能因?yàn)橛?xùn)練過程學(xué)得太好了猎贴，將訓(xùn)練集自身的一些特點(diǎn)當(dāng)作普遍化特征進(jìn)行學(xué)習(xí)而會導(dǎo)致過擬合。因此蝴光，可通過主動去掉一些分支來降低過擬合的風(fēng)險她渴。目前決策樹剪枝的基本策略有以下兩種：
前置剪枝（預(yù)剪枝）：在分裂節(jié)點(diǎn)的時候設(shè)計(jì)比較苛刻的條件，如不滿足則直接停止分裂（這樣干決策樹無法到最優(yōu)虱疏，也無法得到比較好的效果）
后置剪枝（后剪枝）：在樹建立完之后惹骂，用單個節(jié)點(diǎn)代替子樹苏携，節(jié)點(diǎn)的分類采用子樹中主要的分類（這種方法比較浪費(fèi)前面的建立過程）
減枝過程：使用第二章中提到的性能評估方法來比較泛化性能的改變：留出法做瞪、交叉驗(yàn)證法、自助法等。
從樣本預(yù)留出一部分?jǐn)?shù)據(jù)用作“驗(yàn)證集”以進(jìn)行性能評估装蓬。
由圖可看出著拭，頭結(jié)點(diǎn)臍部，精度由43.9%提高到71.4%牍帚，高于其他屬性儡遮，因此選擇臍部為頭結(jié)點(diǎn)，其他分支同理暗赶。第二個枝葉鄙币，選取色澤，精度從71.4%降低到了57.1%蹂随，所以該枝葉別減十嘿。
補(bǔ)充：剪枝代碼詳細(xì)解釋+周志華《機(jī)器學(xué)習(xí)》決策樹圖4.5、圖4.6岳锁、圖4.7繪制
部分代碼如下：
#這個用于預(yù)剪枝
deftesting_feat(feat,train_data,test_data,labels):
print"train_data=",json.dumps(train_data,ensure_ascii=False)
class_list=[example[-1]forexampleintrain_data]
bestFeatIndex=labels.index(feat)
train_data=[example[bestFeatIndex]forexampleintrain_data]
test_data=[(example[bestFeatIndex],example[-1])forexampleintest_data]
all_feat=set(train_data)
error=0.0
forvalueinall_feat:
class_feat=[class_list[i]foriinrange(len(class_list))iftrain_data[i]==value]
major=majorityCnt(class_feat)
fordataintest_data:
ifdata[0]==valueanddata[1]!=major:
error+=1.0
# print 'myTree %d' % error
returnerror
#這個函數(shù)用于預(yù)剪枝和后剪枝
deftestingMajor(major,data_test):
error=0.0
foriinrange(len(data_test)):
ifmajor!=data_test[i][-1]:
error+=1
# print 'major %d' % error
returnfloat(error)
#這個函數(shù)專門用于"后剪枝"
deftesting(myTree,data_test,labels):
#這里輸入的labels不是全部的特征名稱
#這里輸入的data_test不帶有全部的特征名稱
print"----------進(jìn)入testing函數(shù)--------------"
print"data_test=",json.dumps(data_test,ensure_ascii=False)
print"labels=",json.dumps(labels,ensure_ascii=False)
error=0.0
foriinrange(len(data_test)):
ifclassify(myTree,labels,data_test[i])!=data_test[i][-1]:#如果預(yù)測結(jié)果與驗(yàn)證數(shù)據(jù)的類別標(biāo)簽不一致
error+=1#那么錯誤數(shù)就+1
print('myTree %d'%error)
returnfloat(error)
參考資料：https://blog.csdn.net/appleyuchi/article/details/83041047
運(yùn)行結(jié)果：
ps：減少過擬合現(xiàn)象的另一種方法：構(gòu)建隨機(jī)森林RF
參考 http://www.reibang.com/p/d792279a30bc
隨機(jī)森林是有很多隨機(jī)得決策樹構(gòu)成绩衷，它們之間沒有關(guān)聯(lián)。得到RF以后激率，在預(yù)測時分別對每一個決策樹進(jìn)行判斷咳燕，最后使用Bagging的思想進(jìn)行結(jié)果的輸出（也就是投票的思想）
學(xué)習(xí)過程
1、現(xiàn)在有N個訓(xùn)練樣本乒躺，每個樣本的特征為M個招盲，需要建K顆樹
2、從N個訓(xùn)練樣本中有放回的取N個樣本作為一組訓(xùn)練集（其余未取到的樣本作為預(yù)測分類嘉冒，評估其誤差）
3宪肖、從M個特征中取m個特征左右子集特征(m<
4、對采樣的數(shù)據(jù)使用完全分裂的方式來建立決策樹健爬，這樣的決策樹每個節(jié)點(diǎn)要么無法分裂控乾，要么所有的樣本都指向同一個分類
5、重復(fù)2的過程K次娜遵，即可建立森林
［5］連續(xù)與缺失值
那么當(dāng)遇到屬性是連續(xù)或缺失時蜕衡，我們應(yīng)該知道該如何處理？
連續(xù)值處理
遇到連續(xù)值屬性時處理邏輯是：將連續(xù)值轉(zhuǎn)換為離散值设拟。我們需要做的是將訓(xùn)練樣本中該屬性的所有取值進(jìn)行排序慨仿，并對這排好序的取值隊(duì)列進(jìn)行分區(qū)劃分，每一個分區(qū)即為該屬性的一個離散點(diǎn)取值纳胧。
我們?nèi)《址ǎ捶譃閮蓚€分區(qū)镰吆，可以根據(jù)需要分為N個）來進(jìn)行描述。將區(qū)間的中位點(diǎn)作為候選劃分點(diǎn)：
根據(jù)不同的劃分跑慕，我們可以分別計(jì)算一下信息增益的大小万皿，然后選出一個最好的劃分來摧找。
需注意的是，和離散值不同牢硅，連續(xù)值的劃分是可以在子結(jié)點(diǎn)上繼續(xù)劃分的蹬耘。即你將身高劃分為“小于175”和“大于等于175”兩部分，對于“小于175”的子結(jié)點(diǎn)减余，你仍然可以繼續(xù)劃分為“小于160”和“大于160”兩部分综苔。
［6］缺失值處理
屬性值缺失的情況下進(jìn)行屬性劃分選擇
不將缺失值的樣本代入選擇判斷的公式計(jì)算（信息增益、增益率位岔、基尼指數(shù)）之中如筛，只在計(jì)算完后乘以一個有值的樣本比例即可。
比如訓(xùn)練集有10個樣本抒抬，在屬性 a 上妙黍，有兩個樣本缺失值，那么計(jì)算該屬性劃分的信息增益時瞧剖，我們可以忽略這兩個缺失值的樣本來計(jì)算信息增益拭嫁，然后在計(jì)算結(jié)果上乘以8/10即可。
本在劃分屬性上的值為時節(jié)點(diǎn)的分配
若樣本 x 在劃分屬性 a 上取值未知抓于，則將 x 劃入所有子結(jié)點(diǎn)做粤，但是對劃入不同子結(jié)點(diǎn)中的 x 賦予不同的權(quán)值（不同子結(jié)點(diǎn)上的不同權(quán)值一般體現(xiàn)為該子結(jié)點(diǎn)所包含的數(shù)據(jù)占父結(jié)點(diǎn)數(shù)據(jù)集合的比例）。
［7］多變量決策樹
在此類決策樹中捉撮，非葉結(jié)點(diǎn)不再是僅對某個屬性怕品，而是對屬性的線性組合進(jìn)行測試；換言之巾遭，每個非葉結(jié)點(diǎn)時一個形如線性回歸的線性分類器了肉康。下圖是一個在連續(xù)屬性密度和含糖率上的選瓜多變量決策樹樣例：
python構(gòu)建決策樹這篇文章總結(jié)的很好：http://www.reibang.com/p/e7ed734b8fcb
