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

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

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

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

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

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

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

決策樹(shù)算法

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

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

信息增益

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

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

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

任何一個(gè)序列都可以獲取這個(gè)序列的信息熵，也就是將此序列分類(lèi)后統(tǒng)計(jì)每個(gè)類(lèi)型的概率，再用上述公式計(jì)算，使用Python實(shí)現(xiàn)如下:
def get_shanno_entropy(self, values):
''' 根據(jù)給定列表中的值計(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ù)的信息熵會(huì)發(fā)生改變，我們可以通過(guò)使用信息熵的計(jì)算公式分別計(jì)算被劃分的子數(shù)據(jù)集的信息熵并計(jì)算他們的平均值(期望值)來(lái)作為分割后的數(shù)據(jù)集的信息熵。新的信息熵的相比未劃分?jǐn)?shù)據(jù)的信息熵的減小值便是信息增益了. 這里我在最初就理解錯(cuò)了，于是寫(xiě)出的代碼并不能創(chuàng)建正確的決策樹(shù)。

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

信息增益便是兩個(gè)信息熵的差值

在這里我主要使用信息增益來(lái)進(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ù)集對(duì)應(yīng)的類(lèi)型

: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))

增益比率