首先通過兩個(gè)圖來引入什么是決策樹。
決策樹是仿樹結(jié)構(gòu)來進(jìn)行決策的，例如上圖來說，我們要對(duì)‘是否學(xué)習(xí)’這個(gè)問題進(jìn)行決策時(shí)，通常伴隨一系列的子決策。先看是否有‘對(duì)象’，有的話是否需要‘陪伴對(duì)象’，通過一次次子決策后得到最終決策：是否學(xué)習(xí)。
一般情況下，一棵決策樹包含一個(gè)根節(jié)點(diǎn)，若干內(nèi)部節(jié)點(diǎn)和若干葉節(jié)點(diǎn)，如下圖所示，那么與是否學(xué)習(xí)的決策過程對(duì)應(yīng)起來，‘女票’為根節(jié)點(diǎn),'陪女友'和‘任務(wù)’‘吃雞’為內(nèi)部節(jié)點(diǎn)，最下面一層為葉子節(jié)點(diǎn)。
決策樹算法第一種常見的機(jī)器學(xué)習(xí)方法，常用于分類任務(wù)中，從給定的訓(xùn)練數(shù)據(jù)集中學(xué)習(xí)到一個(gè)模型用于對(duì)新示例進(jìn)行分類。決策樹需要兩部分?jǐn)?shù)據(jù)：
- 訓(xùn)練數(shù)據(jù)：用于構(gòu)造決策樹，即決策機(jī)制
-
測試數(shù)據(jù)：驗(yàn)證所構(gòu)造決策樹的錯(cuò)誤率
下面給出決策樹學(xué)習(xí)算法偽代碼：
決策樹學(xué)習(xí)算法偽代碼
下面我們以一個(gè)具體的小實(shí)例來講解決策樹算法
數(shù)據(jù)為一個(gè)簡單的判別生物是否為魚類的數(shù)據(jù)集，通過對(duì)下面數(shù)據(jù)進(jìn)行分析，建立決策樹。
| 序號(hào) | 不浮出水面是否可以生存 | 是否有腳蹼 | 屬于魚類 |
|---|---|---|---|
| 1 | 是 | 是 | 是 |
| 2 | 是 | 是 | 是 |
| 3 | 是 | 否 | 否 |
| 4 | 否 | 是 | 否 |
| 5 | 否 | 否 | 否 |
第一步是數(shù)據(jù)處理
def Dataset():
data=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,0,'no']] #數(shù)據(jù)集
labels=['no surfacing','flipper']
return data,labels
def splitdata(dataset,row,label): #按照特定屬性劃分?jǐn)?shù)據(jù)集
Dataset=[]
for data in dataset:
if data[row]==label:
reducedata=data[:row]
reducedata.extend(data[row+1:])
Dataset.append(reducedata)
return Dataset
偽代碼的第8行是決策樹建模很關(guān)鍵的一步，那么如何選擇最優(yōu)劃分屬性的呢？我們希望伴隨著劃分過程進(jìn)行時(shí)，決策樹分支節(jié)點(diǎn)所包含 樣本盡可能屬于同一類別，即節(jié)點(diǎn)的純度越來越高。一般常用方法是利用信息增益。
在介紹信息增益之前先引入一個(gè)概念--信息熵
信息熵
Ent(D)就是信息熵，其中pk為樣本集合D中第k類樣本所占比例，Ent(D)的值越小，就代表該樣本集D的純度越高。
信息增益
假設(shè)屬性a有V個(gè)可能取值，那么用a來對(duì)樣本集進(jìn)行劃分，就會(huì)產(chǎn)生V個(gè)分支節(jié)點(diǎn)，Dv是第v個(gè)分支所包含的樣本。上式就可計(jì)算出用屬性a對(duì)樣本集D進(jìn)行劃分所獲得的信息增益。信息增益越大，用屬性a對(duì)樣本進(jìn)行劃分的純度越高。所以選擇使得信息增益最大的屬性進(jìn)行劃分。具體代碼實(shí)現(xiàn)如下：
def shannonEnt(dataset): #計(jì)算信息熵
lens=len(dataset)
count={}
for data in dataset:
key=data[-1]
count[key]=count.get(key,0)+1
Ent=0
for key in count:
prob=count[key]/lens
Ent-=prob*log(prob,2)
return Ent
def choosefeature(dataset): #選擇最優(yōu)劃分屬性
lens=len(dataset[0])-1
bestfeature=-1
entropy=shannonEnt(dataset)
bestInfo=0
for i in range(lens):
featurelist=set([example[i] for example in dataset])
Newentropy=0
for j in featurelist:
Data=splitdata(dataset,i,j)
Prob=len(Data)/len(dataset)
Newentropy-=Prob*shannonEnt(Data)
infoGain=entropy+Newentropy
if(infoGain>bestInfo):
bestInfo=infoGain
bestfeature=i
return bestfeature
下面就開始構(gòu)建決策樹并進(jìn)行測試：
def createtree(dataset,labels):
classlist=[example[-1] for example in dataset]
if classlist.count(classlist[0])==len(classlist): #類別相同停止劃分
return classlist[0]
bestfeature=choosefeature(dataset)
bestlabel=labels[bestfeature]
myTree={bestlabel:{}}
del(labels[bestfeature])
tags=set([example[bestfeature] for example in dataset]) #得到列表所包含的所有屬性
for tag in tags:
myTree[bestlabel][tag]=creattree(splitdata(dataset,bestfeature,tag),labels)
return myTree
print(createtree(data,labels))#打印樹結(jié)構(gòu)
def classify(data,labels,test): #測試
first = list(data.keys())[0]
second = data[first] # {0: 'no', 1: {'flipper': {0: 'no', 1: 'yes'}}}
featIndex = labels.index(first) # 0
for key in second.keys():
if test[featIndex]==key:
if type(second[key]).__name__=='dict':
classlabel=classify(second[key],labels,test)
else:
classlabel=second[key]
return classlabel
以上為我對(duì)決策樹的理解，如有錯(cuò)誤，請(qǐng)指正。
