電子發燒友App
今天，我們介紹機器學習里比較常用的一種分類算法，決策樹。決策樹是對人類認知識別的一種模擬，給你一堆看似雜亂無章的數據，如何用盡可能少的特征，對這些數據進行有效的分類。
決策樹借助了一種層級分類的概念，每一次都選擇一個區分性最好的特征進行分類，對于可以直接給出標簽 label 的數據，可能最初選擇的幾個特征就能很好地進行區分，有些數據可能需要更多的特征，所以決策樹的深度也就表示了你需要選擇的幾種特征。
在進行特征選擇的時候，常常需要借助信息論的概念，利用最大熵原則。
決策樹一般是用來對離散數據進行分類的，對于連續數據，可以事先對其離散化。
在介紹決策樹之前，我們先簡單的介紹一下信息熵，我們知道，熵的定義為：
?
我們先構造一些簡單的數據：
from sklearn import datasets
import numpy as np
import matplotlib.pyplot as plt
import math
import operator
def Create_data（）：
dataset = ［［1，1，‘yes’］，
［1， 1，‘yes’］，
［1， 0， ‘no’］，
［0， 1， ‘no’］，
［0， 1， ‘no’］，
［3， 0， ‘maybe’］］
feat_name = ［‘no surfacing’， ‘flippers’］
return dataset， feat_name
然后定義一個計算熵的函數：
def Cal_entrpy（dataset）：
n_sample = len（dataset）
n_label = {}
for featvec in dataset：
current_label = featvec［-1］
if current_label not in n_label.keys（）：
n_label［current_label］ = 0
n_label［current_label］ += 1
shannonEnt = 0.0
for key in n_label：
prob = float（n_label［key］） / n_sample
shannonEnt -= prob * math.log（prob， 2）
return shannonEnt
要注意的是，熵越大，說明數據的類別越分散，越呈現某種無序的狀態。
下面再定義一個拆分數據集的函數：
def Split_dataset（dataset， axis， value）：
retDataSet = ［］
for featVec in dataset：
if featVec［axis］ == value：
reducedFeatVec = featVec［：axis］
reducedFeatVec.extend（featVec［axis+1 ：］）
retDataSet.append（reducedFeatVec）
return retDataSet
結合前面的幾個函數，我們可以構造一個特征選擇的函數：
def Choose_feature（dataset）：
num_sample = len（dataset）
num_feature = len（dataset［0］） - 1
baseEntrpy = Cal_entrpy（dataset）
best_Infogain = 0.0
bestFeat = -1
for i in range （num_feature）：
featlist = ［example［i］ for example in dataset］
uniquValus = set（featlist）
newEntrpy = 0.0
for value in uniquValus：
subData = Split_dataset（dataset， i， value）
prob = len（subData） / float（num_sample）
newEntrpy += prob * Cal_entrpy（subData）
info_gain = baseEntrpy - newEntrpy
if （info_gain 》 best_Infogain）：
best_Infogain = info_gain
bestFeat = i
return bestFeat
然后再構造一個投票及計票的函數
def Major_cnt（classlist）：
class_num = {}
for vote in classlist：
if vote not in class_num.keys（）：
class_num［vote］ = 0
class_num［vote］ += 1
Sort_K = sorted（class_num.iteritems（），
key = operator.itemgetter（1）， reverse=True）
return Sort_K［0］［0］
有了這些，就可以構造我們需要的決策樹了：
def Create_tree（dataset， featName）：
classlist = ［example［-1］ for example in dataset］
if classlist.count（classlist［0］） == len（classlist）：
return classlist［0］
if len（dataset［0］） == 1：
return Major_cnt（classlist）
bestFeat = Choose_feature（dataset）
bestFeatName = featName［bestFeat］
myTree = {bestFeatName： {}}
del（featName［bestFeat］）
featValues = ［example［bestFeat］ for example in dataset］
uniqueVals = set（featValues）
for value in uniqueVals：
subLabels = featName［：］
myTree［bestFeatName］［value］ = Create_tree（Split_dataset
（dataset， bestFeat， value）， subLabels）
return myTree
def Get_numleafs（myTree）：
numLeafs = 0
firstStr = myTree.keys（）［0］
secondDict = myTree［firstStr］
for key in secondDict.keys（）：
if type（secondDict［key］）.__name__ == ‘dict’ ：
numLeafs += Get_numleafs（secondDict［key］）
else：
numLeafs += 1
return numLeafs
def Get_treedepth（myTree）：
max_depth = 0
firstStr = myTree.keys（）［0］
secondDict = myTree［firstStr］
for key in secondDict.keys（）：
if type（secondDict［key］）.__name__ == ‘dict’ ：
this_depth = 1 + Get_treedepth（secondDict［key］）
else：
this_depth = 1
if this_depth 》 max_depth：
max_depth = this_depth
return max_depth
我們也可以把決策樹繪制出來：
def Plot_node（nodeTxt， centerPt， parentPt， nodeType）：
Create_plot.ax1.annotate（nodeTxt， xy=parentPt，
xycoords=‘axes fraction’，
xytext=centerPt， textcoords=‘axes fraction’，
va=“center”， ha=“center”， bbox=nodeType， arrowprops=arrow_args）
def Plot_tree（myTree， parentPt， nodeTxt）：
numLeafs = Get_numleafs（myTree）
Get_treedepth（myTree）
firstStr = myTree.keys（）［0］
cntrPt = （Plot_tree.xOff + （1.0 + float（numLeafs））/2.0/Plot_tree.totalW，
Plot_tree.yOff）
Plot_midtext（cntrPt， parentPt， nodeTxt）
Plot_node（firstStr， cntrPt， parentPt， decisionNode）
secondDict = myTree［firstStr］
Plot_tree.yOff = Plot_tree.yOff - 1.0/Plot_tree.totalD
for key in secondDict.keys（）：
if type（secondDict［key］）.__name__==‘dict’：
Plot_tree（secondDict［key］，cntrPt，str（key））
else：
Plot_tree.xOff = Plot_tree.xOff + 1.0/Plot_tree.totalW
Plot_node（secondDict［key］， （Plot_tree.xOff， Plot_tree.yOff），
cntrPt， leafNode）
Plot_midtext（（Plot_tree.xOff， Plot_tree.yOff）， cntrPt， str（key））
Plot_tree.yOff = Plot_tree.yOff + 1.0/Plot_tree.totalD
def Create_plot （myTree）：
fig = plt.figure（1， facecolor = ‘white’）
fig.clf（）
axprops = dict（xticks=［］， yticks=［］）
Create_plot.ax1 = plt.subplot（111， frameon=False， **axprops）
Plot_tree.totalW = float（Get_numleafs（myTree））
Plot_tree.totalD = float（Get_treedepth（myTree））
Plot_tree.xOff = -0.5/Plot_tree.totalW; Plot_tree.yOff = 1.0;
Plot_tree（myTree， （0.5，1.0）， ‘’）
plt.show（）
def Plot_midtext（cntrPt， parentPt， txtString）：
xMid = （parentPt［0］ - cntrPt［0］） / 2.0 + cntrPt［0］
yMid = （parentPt［1］ - cntrPt［1］） / 2.0 + cntrPt［1］
Create_plot.ax1.text（xMid， yMid， txtString）
def Classify（myTree， featLabels， testVec）：
firstStr = myTree.keys（）［0］
secondDict = myTree［firstStr］
featIndex = featLabels.index（firstStr）
for key in secondDict.keys（）：
if testVec［featIndex］ == key：
if type（secondDict［key］）.__name__ == ‘dict’ ：
classLabel = Classify（secondDict［key］，featLabels，testVec）
else：
classLabel = secondDict［key］
return classLabel
最后，可以測試我們的構造的決策樹分類器：
decisionNode = dict（boxstyle=“sawtooth”， fc=“0.8”）
leafNode = dict（boxstyle=“round4”， fc=“0.8”）
arrow_args = dict（arrowstyle=“《-”）
myData， featName = Create_data（）
S_entrpy = Cal_entrpy（myData）
new_data = Split_dataset（myData， 0， 1）
best_feat = Choose_feature（myData）
myTree = Create_tree（myData， featName［：］）
num_leafs = Get_numleafs（myTree）
depth = Get_treedepth（myTree）
Create_plot（myTree）
predict_label = Classify（myTree， featName， ［1， 0］）
print（“the predict label is： ”， predict_label）
print（“the decision tree is： ”， myTree）
print（“the best feature index is： ”， best_feat）
print（“the new dataset： ”， new_data）
print（“the original dataset： ”， myData）
print（“the feature names are： ”， featName）
print（“the entrpy is：”， S_entrpy）
print（“the number of leafs is： ”， num_leafs）
print（“the dpeth is： ”， depth）
print（“All is well.”）
構造的決策樹最后如下所示：
?
工商網監
評論