增益比率是信息增益方法的一種擴展，是為了克服信息增益帶來的弱泛化的缺陷。因為按照信息增益選擇，總是會傾向于選擇分支多的屬性，這樣會是的每個子集的信息熵最小。例如給每個數據添加一個第一無二的id值特征，則按照這個id值進行分類是獲得信息增益最大的，這樣每個子集中的信息熵都為0，但是這樣的分類便沒有任何意義，沒有任何泛化能力，類似過擬合。

因此我們可以通過引入一個分裂信息來找到一個更合適的衡量數據劃分的標準，即增益比率。

分裂信息的公式表示為:

可見如果數據分的越多，分裂信息的值就會越大

這時候把分裂信息的值放到分母上便會中和信息增益帶來的弊端。

當然SplitInfo有可能趨近于0，這個時候增益比率就會變得非常大而不可信，因此有時還需在分母上添加一個平滑函數，具體的可以參考參考部分列出的文章

基尼不純度(Gini impurity)

基尼不純度的定義:

其中m 表示數據集D 中類別的個數, pi 表示某種類型出現的概率?？梢姰斨挥幸环N類型的時候基尼不純度的值為0，此時不純度最低。

針對劃分成k個子數據集的數據集的基尼不純度可以通過如下式子計算:

由此我們可以根據不純度的變化來選取最有的樹分裂屬性

樹分裂

有了選取最佳分裂屬性的算法，下面我們就需要根據選擇的屬性來將樹進一步的分裂。所謂樹分裂只不過是根據選擇的屬性將數據集劃分，然后在總劃分出來的數據集中再次調用選取屬性的方法選取子數據集的中屬性。實現的最好方式就是遞歸了.

關于用什么數據結構來表示決策樹，在Python中可以使用字典很方便的表示決策樹的嵌套，一個樹的根節點便是屬性，屬性對應的值又是一個新的字典，其中key為屬性的可能值，value為新的子樹。

下面是我使用Python實現的根據數據集創建決策樹：
def create_tree(self, dataset, classes, feat_names):
''' 根據當前數據集遞歸創建決策樹

:param dataset: 數據集
:param feat_names: 數據集中數據相應的特征名稱
:param classes: 數據集中數據相應的類型

:param tree: 以字典形式返回決策樹
'''
# 如果數據集中只有一種類型停止樹分裂
if len(set(classes)) == 1:
return classes[0]

# 如果遍歷完所有特征，返回比例最多的類型
if len(feat_names) == 0:
return get_majority(classes)

# 分裂創建新的子樹
tree = {}
best_feat_idx = self.choose_best_split_feature(dataset, classes)
feature = feat_names[best_feat_idx]
tree[feature] = {}

# 創建用于遞歸創建子樹的子數據集
sub_feat_names = feat_names[:]
sub_feat_names.pop(best_feat_idx)

splited_dict = self.split_dataset(dataset, classes, best_feat_idx)
for feat_val, (sub_dataset, sub_classes) in splited_dict.items():
tree[feature][feat_val] = self.create_tree(sub_dataset,
sub_classes,
sub_feat_names)
self.tree = tree
self.feat_names = feat_names

return tree

樹分裂的終止條件有兩個

一個是遍歷完所有的屬性
可以看到，在進行樹分裂的時候，我們的數據集中的數據向量的長度是不斷縮短的，當縮短到0時，說明數據集已經將所有的屬性用盡，便也分裂不下去了, 這時我們選取最終子數據集中的眾數作為最終的分類結果放到葉子節點上.

另一個是新劃分的數據集中只有一個類型。
若某個節點所指向的數據集都是同一種類型，那自然沒有必要在分裂下去了即使屬性還沒有遍歷完.

構建一棵決策樹

這我用了一下MLiA書上附帶的隱形眼鏡的數據來生成一棵決策樹，數據中包含了患者眼部狀況以及醫生推薦的隱形眼鏡類型.

首先先導入數據并將數據特征同類型分開作為訓練數據用于生成決策樹
from trees import DecisionTreeClassifier

lense_labels = ['age', 'prescript', 'astigmatic', 'tearRate']
X = []
Y = []

with open('lenses.txt', 'r') as f:
for line in f:
comps = line.strip().split('\t')
X.append(comps[: -1])
Y.append(comps[-1])

生成決策樹:
clf = DecisionTreeClassifier()
clf.create_tree(X, Y, lense_labels)