決策樹是個極其易懂的算法，也是最常用的數據挖掘算法，決策樹允許機器根據數據集創造規則，其實這就是機器學習的過程。專家系統中經常會使用到決策樹及其變種，而且決策樹給出的結果往往可以匹敵在當前領域具有幾十年工作經驗的專家。
* **優點**：決策樹的計算復雜度不高，輸出結果易于理解，對中間值的缺失不敏感，可以處理不相關特征數據；
* **缺點**：可能會產生過度匹配的問題；
* **適用數據類型**：數值型和標稱型。
這一章節的主要任務是討論決策樹的方法，以及編寫構造決策樹的python代碼，使用遞歸調用建立分類器，最后可使用Matplotlib繪制決策樹圖。算法驗證部分，對決策樹輸入一些隱形眼鏡的處方數據，并由訓練好的分類器預測需要的鏡片類型。
以下是決策樹的Python實現：
一、首先編寫幾個函數對數據進行預處理：
**1.計算熵函數**：熵代表集合的無序程度，集合越的分布無序，則熵越大；
~~~
from math import log
def entropy(sample):
log2 = lambda x:log(x)/log(2)
results = {}
for row in sample:
r = row[len(row)-1]
results[r] = results.get(r, 0) + 1
ent = 0.0 # entropy
for r in results.keys():
p = float(results[r]) / len(sample)
ent -= p * log2(p)
return ent
~~~
**2.按屬性和值獲取數據集函數**，可以看到使用python編寫的函數十分簡潔，該函數的意義是從數據集sample序列中取得第k列的值為v的子集，并從獲得的子集中去掉第k列：
~~~
def fetch_subdataset(sample, k, v):
return [d[:k] + d[k+1:] for d in sample if d[k] == v]
~~~
**3.計算最大概率屬性的相關函數**，在構建決策樹時，在處理所有決策屬性后，還不能唯一區分數據時，我們采用多數表決的方法來選擇最終分類：
~~~
def MaxFeature(classList):
classCount = {}
for cla in classList:
classCount[cla] = classCount.get(cla, 0) + 1
sortedClassCount = sorted(classCount.items(), key=lambda d: d[1], reverse = True)
return sortedClassCount[0][0]
~~~
二.選取最優數據特征劃分方式的函數
在構造決策樹之前，首先需要評估每個特性的作用，思考以哪一列的值劃分集合，從而獲得最大的信息增益，以下函數實現了這一功能，輸入數據集，輸出最優的特征值。
~~~
def DecisionFeature(sample):
ent, feature = 100000000, -1
for i in range(len(sample[0]) - 1):
feat_list = [e[i] for e in sample]
unq_feat_list = set(feat_list)
ent_t = 0.0
for f in unq_feat_list:
sub_data = fetch_subdataset(sample, i, f)
ent_t += entropy(sub_data) * len(sub_data) / len(sample)
if ent_t < ent:
ent, feature = ent_t, i
return feature
~~~
三.使用遞歸構建決策樹
~~~
def buildTree(sample, datalabel):
cla = [c[-1] for c in sample]
if len(cla) == cla.count(cla[0]):
return cla[0]
if len(sample[0]) == 1:
return MaxFeature(sample)
feature = DecisionFeature(sample)
featureLabel = datalabel[feature]
decisionTree = {featureLabel:{}}
del(datalabel[feature])
featValue = [d[feature] for d in sample]
UniqueFeatValue = set(featValue)
for value in UniqueFeatValue:
subLabel = datalabel[:]
decisionTree[featureLabel][value] = buildTree( \
fetch_subdataset(sample, feature, value), subLabel)
return decisionTree
~~~
四.使用決策樹
~~~
def classify(decisionTree, featLabels, test):
label = decisionTree.keys()[0]
next_dict = decisionTree[label]
feat_index = featLabels.index(label)
for key in next_dict.keys():
if test[feat_index] == key:
if type(next_dict[key]).__name__ == 'dict':
c_label = classify(next_dict[key], featLabels, test)
else:
c_label = next_dict[key]
return c_label
~~~
由于時間有限，只能分析到這里，實現結果和實例驗證有待進一步討論。
