決策樹的構造

摘 要：本文分析了決策樹的幾個模塊之間的關系，并用代碼展示了decision tree的部分模塊的構造過程。

關鍵詞：ID3算法;信息熵;決策樹;數據集

一、 背景介紹

ID3算法[1，2，3]由J. Ross Quinlan于1975年在悉尼大學提出用作分類預測，該算法的基礎是“信息熵”。通過計算每個屬性的增益信息，ID3算法以每次劃分選取信息增益最高的屬性為劃分標準，完成數據集劃分，直至生成一個能完美分類訓練樣例的decision tree。

二、 構造模塊之間的關系

決策樹包含信息熵增計算模塊，數據集劃分模塊，以及ID3貪心算法構建樹的模塊。

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

三、 決策樹的構造

構造決策樹的第一步是計算香濃熵。以下給出了計算香濃熵計算的描述：

def cal_shannon_entropy（dataSet）：

n=len（dataSet）

label_counts={}

# 統計每個類別出現的次數

for feature in dataSet：

label=feature[-1]

if label not in label_counts：

label_counts[label]=0 ?# 創建該元素并清零

label_counts[label]+=1

entropy=0

for key in label_counts：

prob=float（label_counts[key]）/n

entropy-=prob * log（p，2）

return entropy

完成了熵的計算，下一步就是處理數據集的劃分

#對dataSet進行劃分

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

嘗試使用每一個特征向量計算對應的信息增益，選擇最大的那一個特征來劃分dataSet。特別強調的是，這里使用的分類方法并不是二分法，而是ID3的貪心法。

最后一步，遞歸構建決策樹。

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

四、 總結

在本文中，我們給出了決策樹的構造過程。注意，dataSet是我們待處理的數據集。由于決策樹的特性，我們這里的數據集dataSet中的數據類型只能是數值型，或者標稱型。本文給出了大致的算法過程描述。構造決策樹是一個費時的事務，對于一個不大的dataSet，也需要花費很多的機時，因此，如果在數據集很大的情況下，自然的需要花費更多的時間。故優化的辦法是，每次調用易構造好的決策樹。

參考文獻：

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

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

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

作者簡介：

智巖，廣東省廣州市，廣州工商學院。