機(jī)器學(xué)習(xí)從入門到放棄之決策樹算法

決策樹故名思意是用于基于條件來做決策的，而它運(yùn)行的邏輯相比一些復(fù)雜的算法更容易理解，只需按條件遍歷樹就可以了，需要花點(diǎn)心思的是理解如何建立決策樹。

舉個(gè)例子，就好像女兒回家，做媽媽的給女兒介紹對象，于是就有了以下對話：

媽媽：女啊，明天有沒有時(shí)間，媽媽給你介紹個(gè)對象

女兒：有啊，對方多大了。

媽媽：年齡和你相仿

女兒：帥不帥啊

媽媽: 帥

女兒：那我明天去看看

媽媽和女兒對話的這個(gè)過程中，女兒的決策過程可以用下圖表示：

你可能會(huì)認(rèn)為，這個(gè)決策的過程本質(zhì)上就是對數(shù)據(jù)集的每一個(gè)做if--else的判斷，這不很簡單嗎？那為什么還要專門弄一個(gè)算法出來呢？

不妨可以考慮兩點(diǎn)，假如訓(xùn)練數(shù)據(jù)集中存在無關(guān)項(xiàng)，比如以下的例子：

10-1 #表示第一項(xiàng)特征是1，第二項(xiàng)特征是0，最后推出的結(jié)果是1，以下同理

12-1

05-0

09-0

17-1

……

顯然的，最后結(jié)果和第二個(gè)特征無關(guān)，如果仍要做判斷就會(huì)增加了損耗。所以在建立決策樹的過程中，我們就希望把這些無關(guān)項(xiàng)扔掉。

第二點(diǎn)，回到媽媽給女兒介紹對象的這個(gè)例子，上圖是為了方面讀者理解，所以按照順序畫出，但事實(shí)上，有一個(gè)嚴(yán)重的問題，比如說女兒可能不能容忍某個(gè)缺點(diǎn)，而一旦對方的性格中具有這個(gè)缺點(diǎn)，那么其他一切都不用考慮。也就是說，有一個(gè)特征跟最后的結(jié)果相關(guān)度極高，這時(shí)我們就希望這個(gè)數(shù)據(jù)出現(xiàn)在根節(jié)點(diǎn)上，如果核心條件不滿足那就結(jié)束遍歷這棵樹了，避免無謂的損耗。

總言言之，決策樹第一個(gè)是需要從大量的已存在的樣本中推出可供做決策的規(guī)則，同時(shí)，這個(gè)規(guī)則應(yīng)該避免做無謂的損耗。

算法原理

構(gòu)造決策樹的關(guān)鍵步驟是分裂屬性。分裂屬性值得就是在某個(gè)節(jié)點(diǎn)處按照某一特征屬性的不同劃分構(gòu)造不同的分支，其目標(biāo)是讓各個(gè)分裂子集盡可能地“純”。盡可能“純”就是盡量讓一個(gè)分裂子集中待分類項(xiàng)屬于同一類別。這時(shí)分裂屬性可能會(huì)遇到三種不同的情況：

對離散值生成非二叉決策樹。此時(shí)用屬性的每一個(gè)劃分作為一個(gè)分支。

對離散值生成二叉決策樹。此時(shí)使用屬性劃分的一個(gè)子集進(jìn)行測試，按照“屬于此子集”和“不屬于此子集”分成兩個(gè)分支。

屬性是連續(xù)值。確定一個(gè)split_point，按照>split_point和<=split_point轉(zhuǎn)成成離散，分別建立兩個(gè)分支

構(gòu)造決策樹的關(guān)鍵性內(nèi)容是進(jìn)行屬性選擇度量，屬性選擇度量是一種選擇分裂準(zhǔn)則，是將給定的類標(biāo)記的訓(xùn)練集合的數(shù)據(jù)劃分D“最好”地分成個(gè)體類的啟發(fā)式方法，它決定了拓?fù)浣Y(jié)構(gòu)及分裂點(diǎn)split_point的選擇。

在這里僅介紹比較常用的ID3算法。

從信息論知識(shí)中我們直到，期望信息越小，信息增益越大，從而純度越高。所以ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進(jìn)行分裂。

循序本系列的從工程角度理解算法，而非數(shù)學(xué)角度理解算法的原則，因此這里只給出信息增益度量的計(jì)算方式，如果需要深入了解其數(shù)學(xué)原理，請查閱專業(yè)資料。

設(shè)D為用類別對訓(xùn)練元組進(jìn)行的劃分，則D的熵計(jì)算方法為：

其中pi表示第i個(gè)類別在整個(gè)訓(xùn)練集中出現(xiàn)的概率。

當(dāng)按照特征A分割后，其期望信息為：

其中Di/D表示每一個(gè)D在整體訓(xùn)練集占的比例。

而信息增益即為兩者的差值：

其中當(dāng)gain(A)達(dá)到最大時(shí)，該特征便是最佳的劃分特征，選中最佳特征作為當(dāng)前的節(jié)點(diǎn)，隨后對劃分后的子集進(jìn)行迭代操作。

算法實(shí)現(xiàn)

github

在本專欄的前面的文章描述了基于決策樹的五子棋游戲，算是一個(gè)基于決策樹的應(yīng)用了。