增益比率 - 決策樹(shù)的構(gòu)建設(shè)計(jì)并用Graphviz實(shí)現(xiàn)決策樹(shù)的可視化

增益比率是信息增益方法的一種擴(kuò)展，是為了克服信息增益帶來(lái)的弱泛化的缺陷。因?yàn)榘凑招畔⒃鲆孢x擇，總是會(huì)傾向于選擇分支多的屬性，這樣會(huì)是的每個(gè)子集的信息熵最小。例如給每個(gè)數(shù)據(jù)添加一個(gè)第一無(wú)二的id值特征，則按照這個(gè)id值進(jìn)行分類是獲得信息增益最大的，這樣每個(gè)子集中的信息熵都為0，但是這樣的分類便沒(méi)有任何意義，沒(méi)有任何泛化能力，類似過(guò)擬合。

因此我們可以通過(guò)引入一個(gè)分裂信息來(lái)找到一個(gè)更合適的衡量數(shù)據(jù)劃分的標(biāo)準(zhǔn)，即增益比率。

分裂信息的公式表示為:

可見(jiàn)如果數(shù)據(jù)分的越多，分裂信息的值就會(huì)越大

這時(shí)候把分裂信息的值放到分母上便會(huì)中和信息增益帶來(lái)的弊端。

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

基尼不純度(Gini impurity)

基尼不純度的定義:

其中m 表示數(shù)據(jù)集D 中類別的個(gè)數(shù), pi 表示某種類型出現(xiàn)的概率。可見(jiàn)當(dāng)只有一種類型的時(shí)候基尼不純度的值為0，此時(shí)不純度最低。

針對(duì)劃分成k個(gè)子數(shù)據(jù)集的數(shù)據(jù)集的基尼不純度可以通過(guò)如下式子計(jì)算:

由此我們可以根據(jù)不純度的變化來(lái)選取最有的樹(shù)分裂屬性

樹(shù)分裂

有了選取最佳分裂屬性的算法，下面我們就需要根據(jù)選擇的屬性來(lái)將樹(shù)進(jìn)一步的分裂。所謂樹(shù)分裂只不過(guò)是根據(jù)選擇的屬性將數(shù)據(jù)集劃分，然后在總劃分出來(lái)的數(shù)據(jù)集中再次調(diào)用選取屬性的方法選取子數(shù)據(jù)集的中屬性。實(shí)現(xiàn)的最好方式就是遞歸了.

關(guān)于用什么數(shù)據(jù)結(jié)構(gòu)來(lái)表示決策樹(shù)，在Python中可以使用字典很方便的表示決策樹(shù)的嵌套，一個(gè)樹(shù)的根節(jié)點(diǎn)便是屬性，屬性對(duì)應(yīng)的值又是一個(gè)新的字典，其中key為屬性的可能值，value為新的子樹(shù)。

下面是我使用Python實(shí)現(xiàn)的根據(jù)數(shù)據(jù)集創(chuàng)建決策樹(shù)：
def create_tree(self, dataset, classes, feat_names):
''' 根據(jù)當(dāng)前數(shù)據(jù)集遞歸創(chuàng)建決策樹(shù)

:param dataset: 數(shù)據(jù)集
:param feat_names: 數(shù)據(jù)集中數(shù)據(jù)相應(yīng)的特征名稱
:param classes: 數(shù)據(jù)集中數(shù)據(jù)相應(yīng)的類型

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

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

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

# 創(chuàng)建用于遞歸創(chuàng)建子樹(shù)的子數(shù)據(jù)集
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

樹(shù)分裂的終止條件有兩個(gè)

一個(gè)是遍歷完所有的屬性
可以看到，在進(jìn)行樹(shù)分裂的時(shí)候，我們的數(shù)據(jù)集中的數(shù)據(jù)向量的長(zhǎng)度是不斷縮短的，當(dāng)縮短到0時(shí)，說(shuō)明數(shù)據(jù)集已經(jīng)將所有的屬性用盡，便也分裂不下去了, 這時(shí)我們選取最終子數(shù)據(jù)集中的眾數(shù)作為最終的分類結(jié)果放到葉子節(jié)點(diǎn)上.

另一個(gè)是新劃分的數(shù)據(jù)集中只有一個(gè)類型。
若某個(gè)節(jié)點(diǎn)所指向的數(shù)據(jù)集都是同一種類型，那自然沒(méi)有必要在分裂下去了即使屬性還沒(méi)有遍歷完.

構(gòu)建一棵決策樹(shù)

這我用了一下MLiA書(shū)上附帶的隱形眼鏡的數(shù)據(jù)來(lái)生成一棵決策樹(shù)，數(shù)據(jù)中包含了患者眼部狀況以及醫(yī)生推薦的隱形眼鏡類型.

首先先導(dǎo)入數(shù)據(jù)并將數(shù)據(jù)特征同類型分開(kāi)作為訓(xùn)練數(shù)據(jù)用于生成決策樹(shù)
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])

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