決策樹的構(gòu)造

摘 要：本文分析了決策樹的幾個(gè)模塊之間的關(guān)系，并用代碼展示了decision tree的部分模塊的構(gòu)造過(guò)程。

關(guān)鍵詞：ID3算法;信息熵;決策樹;數(shù)據(jù)集

一、 背景介紹

ID3算法[1，2，3]由J. Ross Quinlan于1975年在悉尼大學(xué)提出用作分類預(yù)測(cè)，該算法的基礎(chǔ)是“信息熵”。通過(guò)計(jì)算每個(gè)屬性的增益信息，ID3算法以每次劃分選取信息增益最高的屬性為劃分標(biāo)準(zhǔn)，完成數(shù)據(jù)集劃分，直至生成一個(gè)能完美分類訓(xùn)練樣例的decision tree。

二、 構(gòu)造模塊之間的關(guān)系

決策樹包含信息熵增計(jì)算模塊，數(shù)據(jù)集劃分模塊，以及ID3貪心算法構(gòu)建樹的模塊。

該決策樹方法先根據(jù)訓(xùn)練集數(shù)據(jù)形成決策樹，如果該樹不能對(duì)所有對(duì)象給出正確的分類，則加入一些其他屬性到訓(xùn)練集數(shù)據(jù)中，重復(fù)該過(guò)程可形成正確的決策集。構(gòu)建決策樹，除了ID3算法構(gòu)造決策樹，還有C4.5和CART等算法。這里只是以ID3為例進(jìn)行說(shuō)明。

三、 決策樹的構(gòu)造

構(gòu)造決策樹的第一步是計(jì)算香濃熵。以下給出了計(jì)算香濃熵計(jì)算的描述：

def cal_shannon_entropy（dataSet）：

n=len（dataSet）

label_counts={}

# 統(tǒng)計(jì)每個(gè)類別出現(xiàn)的次數(shù)

for feature in dataSet：

label=feature[-1]

if label not in label_counts：

label_counts[label]=0 ?# 創(chuàng)建該元素并清零

label_counts[label]+=1

entropy=0

for key in label_counts：

prob=float（label_counts[key]）/n

entropy-=prob * log（p，2）

return entropy

完成了熵的計(jì)算，下一步就是處理數(shù)據(jù)集的劃分

#對(duì)dataSet進(jìn)行劃分

def split_dataSet（dataSet，axis，value）：

split_dset=[]

for f in dataSet： # f是特征向量

if f[axis]==value：

reduce_fv=f[：axis]

reduce_fv.extend（f[axis+1：]）

split_dset.append（reduce_fv）

return split_dset

嘗試使用每一個(gè)特征向量計(jì)算對(duì)應(yīng)的信息增益，選擇最大的那一個(gè)特征來(lái)劃分dataSet。特別強(qiáng)調(diào)的是，這里使用的分類方法并不是二分法，而是ID3的貪心法。

最后一步，遞歸構(gòu)建決策樹。

def create_tree（dataSet，__labels）：

labels=__labels.copy（）

classlist=[f[-1]for f in dataSet]

if classlist.count（classlist[0]）==len（classlist）：

return classlist[0]

if len（dataset[0]）==1：

return majority_cnt（classlist）

bestfeature=min_entropy_split_feature（dataset）[0]

bestf_label=labels[bestfeature]

newtree={bestf_label：{}}

del labels[bestfeature]

f_values=[f[bestfeature]for f in dataset] ?unique_f_values=set（f_values）

for v in unique_f_values：

sublabels=labels[：]

_splitedtree=splite_dataset（dataset，bestfeature，v）

newtree[bestf_label][v]=create_tree（_splitedtree.copy（），sublabels）

return newtree

四、 總結(jié)

在本文中，我們給出了決策樹的構(gòu)造過(guò)程。注意，dataSet是我們待處理的數(shù)據(jù)集。由于決策樹的特性，我們這里的數(shù)據(jù)集dataSet中的數(shù)據(jù)類型只能是數(shù)值型，或者標(biāo)稱型。本文給出了大致的算法過(guò)程描述。構(gòu)造決策樹是一個(gè)費(fèi)時(shí)的事務(wù)，對(duì)于一個(gè)不大的dataSet，也需要花費(fèi)很多的機(jī)時(shí)，因此，如果在數(shù)據(jù)集很大的情況下，自然的需要花費(fèi)更多的時(shí)間。故優(yōu)化的辦法是，每次調(diào)用易構(gòu)造好的決策樹。

參考文獻(xiàn)：

[1]黃愛輝，陳湘濤.決策樹ID3算法的改進(jìn)[J].計(jì)算機(jī)工程與科學(xué)，2009，31（6）：109-111.

[2]孫愛東，朱梅階，涂淑琴，等.基于屬性值的ID3算法改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（12）：3011-3012.

[3]BENNETT C H. Quantum information and computation[J]. Nature，2000，404.

作者簡(jiǎn)介：

智巖，廣東省廣州市，廣州工商學(xué)院。