最近打算系統(tǒng)學(xué)習(xí)下機(jī)器學(xué)習(xí)的基礎(chǔ)算法，避免眼高手低，決定把常用的機(jī)器學(xué)習(xí)基礎(chǔ)算法都實(shí)現(xiàn)一遍以便加深印象。本文為這系列博客的第一篇，關(guān)于決策樹(Decision Tree)的算法實(shí)現(xiàn)，文中我將對決策樹種涉及到的算法進(jìn)行總結(jié)并附上自己相關(guān)的實(shí)現(xiàn)代碼。所有算法代碼以及用于相應(yīng)模型的訓(xùn)練的數(shù)據(jù)都會放到GitHub上。

本文中我將一步步通過MLiA的隱形眼鏡處方數(shù)集構(gòu)建決策樹并使用Graphviz將決策樹可視化。

決策樹學(xué)習(xí)

決策樹學(xué)習(xí)是根據(jù)數(shù)據(jù)的屬性采用樹狀結(jié)構(gòu)建立的一種決策模型，可以用此模型解決分類和回歸問題。常見的算法包括 CART, ID3, C4.5等。我們往往根據(jù)數(shù)據(jù)集來構(gòu)建一棵決策樹，他的一個重要任務(wù)就是為了數(shù)據(jù)中所蘊(yùn)含的知識信息，并提取出一系列的規(guī)則，這些規(guī)則也就是樹結(jié)構(gòu)的創(chuàng)建過程就是機(jī)器學(xué)習(xí)的過程。

決策樹的結(jié)構(gòu)

以下面一個簡單的用于是否買電腦預(yù)測的決策樹為例子，樹中的內(nèi)部節(jié)點(diǎn)表示某個屬性，節(jié)點(diǎn)引出的分支表示此屬性的所有可能的值，葉子節(jié)點(diǎn)表示最終的判斷結(jié)果也就是類型。

借助可視化工具例如Graphviz，matplotlib的注解等等都可以講我們創(chuàng)建的決策樹模型可視化并直接被人理解，這是貝葉斯神經(jīng)網(wǎng)絡(luò)等算法沒有的特性。

決策樹算法

決策樹算法主要是指決策樹進(jìn)行創(chuàng)建中進(jìn)行樹分裂(劃分?jǐn)?shù)據(jù)集)的時候選取最優(yōu)特征的算法，他的主要目的就是要選取一個特征能夠?qū)⒎珠_的數(shù)據(jù)集盡量的規(guī)整，也就是盡可能的純. 最大的原則就是: 將無序的數(shù)據(jù)變得更加有序。

這里總結(jié)下三個常用的方法:
1.信息增益
2.增益比率
3.基尼不純度

信息增益

這里涉及到了信息論中的一些概念：某個事件的信息量，信息熵，信息增益等, 關(guān)于事件信息的通俗解釋可以看知乎上的一個回答

某個事件 i 的信息量: 這個事件發(fā)生的概率的負(fù)對數(shù)

信息熵就是平均而言一個事件發(fā)生得到的信息量大小，也就是信息量的期望值

任何一個序列都可以獲取這個序列的信息熵，也就是將此序列分類后統(tǒng)計每個類型的概率，再用上述公式計算，使用Python實(shí)現(xiàn)如下:
def get_shanno_entropy(self, values):
''' 根據(jù)給定列表中的值計算其Shanno Entropy
'''
uniq_vals = set(values)
val_nums = {key: values.count(key) for key in uniq_vals}
probs = [v/len(values) for k, v in val_nums.items()]
entropy = sum([-prob*log2(prob) for prob in probs])
return entropy

信息增益

我們將一組數(shù)據(jù)集進(jìn)行劃分后，數(shù)據(jù)的信息熵會發(fā)生改變，我們可以通過使用信息熵的計算公式分別計算被劃分的子數(shù)據(jù)集的信息熵并計算他們的平均值(期望值)來作為分割后的數(shù)據(jù)集的信息熵。新的信息熵的相比未劃分?jǐn)?shù)據(jù)的信息熵的減小值便是信息增益了. 這里我在最初就理解錯了，于是寫出的代碼并不能創(chuàng)建正確的決策樹。

假設(shè)我們將數(shù)據(jù)集D劃分成kk 份D1,D2,…,Dk，則劃分后的信息熵為:

信息增益便是兩個信息熵的差值

在這里我主要使用信息增益來進(jìn)行屬性選擇，具體的實(shí)現(xiàn)代碼如下:
def choose_best_split_feature(self, dataset, classes):
''' 根據(jù)信息增益確定最好的劃分?jǐn)?shù)據(jù)的特征

:param dataset: 待劃分的數(shù)據(jù)集
:param classes: 數(shù)據(jù)集對應(yīng)的類型

:return: 劃分?jǐn)?shù)據(jù)的增益最大的屬性索引
'''
base_entropy = self.get_shanno_entropy(classes)

feat_num = len(dataset[0])
entropy_gains = []
for i in range(feat_num):
splited_dict = self.split_dataset(dataset, classes, i)
new_entropy = sum([
len(sub_classes)/len(classes)*self.get_shanno_entropy(sub_classes)
for _, (_, sub_classes) in splited_dict.items()
])
entropy_gains.append(base_entropy - new_entropy)

return entropy_gains.index(max(entropy_gains))

增益比率