決策樹算法的原理（接地氣版）
?決策樹（）是一類很常見很經(jīng)典的機(jī)器學(xué)習(xí)算法，既可以作為分類算法也可以作為回歸算法。同時(shí)也適合許多集成算法，如, ，以后會逐一介紹。本篇介紹一下決策樹算法的原理。?
決策樹算法不像前面介紹的SVM那樣，散發(fā)著濃厚的數(shù)學(xué)氣味。這個(gè)算法還是比較接地氣的。
信息論基礎(chǔ)
這個(gè)語法結(jié)構(gòu)大家應(yīng)該不陌生。怎樣準(zhǔn)確地定量選擇 后面的條件，也就是要找到一個(gè)性能指標(biāo)來衡量這個(gè)條件的好壞。（就像SVM中引入了來衡量一條直線的好壞）。
70年代，一個(gè)名為昆蘭的大牛找到了信息論中的「熵」來度量決策樹的決策選擇過程。注意，信息論中的熵是香農(nóng)提出的。昆蘭只是將熵應(yīng)用于決策樹的人。
熵度量了事物的不確定性(可以聯(lián)想化學(xué)里的熵，混亂程度)，越不確定的事物，它的熵就越大。具體的，隨機(jī)變量X的熵的表達(dá)式如下：
決策樹構(gòu)造
決策樹的組成：
根節(jié)點(diǎn)：第一個(gè)選擇點(diǎn) 非葉子節(jié)點(diǎn)與分支：中間過程 葉子節(jié)點(diǎn)：最終的決策結(jié)果 
就像這張圖展示的，第一個(gè)節(jié)點(diǎn)就是根節(jié)點(diǎn)，綠色的代表 也就是葉子節(jié)點(diǎn)，其它的節(jié)點(diǎn)也就是非葉子節(jié)點(diǎn)(用于決策)，也就是 。
那么如何構(gòu)造決策樹呢？
「第一步，選擇根節(jié)點(diǎn)」。
問題來了，特征不唯一，選哪一個(gè)作根節(jié)點(diǎn)最優(yōu)？
這就涉及到了衡量標(biāo)準(zhǔn)，一般而言，隨著劃分過程不斷進(jìn)行，我們希望節(jié)點(diǎn)的熵能夠迅速地降低。因?yàn)?strong>隨機(jī)變量的熵越大，隨機(jī)變量的不確定性越大，代表純度越低。所以希望節(jié)點(diǎn)的熵能夠迅速降低，使得純度不斷增加。所以以「信息增益」作為衡量標(biāo)準(zhǔn)。
引入一個(gè)信息增益( )的概念。
?「定義」：特征 對訓(xùn)練數(shù)據(jù)集 的信息增益 ，定義為集合 的經(jīng)驗(yàn)熵 與特征 給定條件下 的經(jīng)驗(yàn)條件熵 之差，即
?
信息增益也就度量了熵降低的程度。
以信息增益作為衡量標(biāo)準(zhǔn)的算法被稱為ID3算法。
「第二步，選擇子節(jié)點(diǎn)」
依然是采用信息增益的標(biāo)準(zhǔn)進(jìn)行選擇。
「第三步，何時(shí)停止」
其實(shí)這一步就涉及到剪枝，下文詳解。
如果對這些概念還是有點(diǎn)模糊，可以結(jié)合下面的實(shí)例再思考思考。
實(shí)例
這是數(shù)據(jù)（14天的打球情況），有四種環(huán)境特征（outlook,humidity）,最后一列(play）代表最后有沒有出去打球。
「首先，選擇根節(jié)點(diǎn)」。一共有四個(gè)特征，所以根節(jié)點(diǎn)的選擇有四種。
在我們的原始數(shù)據(jù)（14天）有9天打球，5天不大，所以此時(shí)的熵為：
接著，四個(gè)特征逐一分析，先從(天氣)下手：
當(dāng) 時(shí)，
當(dāng) 時(shí)，
當(dāng) 時(shí)，
根據(jù)數(shù)據(jù)， 取 ,,的概率分別為,
熵值計(jì)算（幾個(gè)特征屬性熵的加權(quán)求和）：
信息增益：
同樣的方式計(jì)算其它三個(gè)特征的信息增益：
四個(gè)特征中， 的增益最大，所以選擇作為根節(jié)點(diǎn)。
「接下來的子節(jié)點(diǎn)選擇同上」。
「何時(shí)停止？」
上文也說了，"何時(shí)停止"涉及到剪枝。為什么要剪枝？
決策樹存在較大的過擬合風(fēng)險(xiǎn)，理論上，決策樹可以將樣本數(shù)據(jù)完全分開，但是這樣就帶來了非常大的過擬合風(fēng)險(xiǎn)，使得模型的泛化能力極差。
剪枝和日常樹木的修建是一個(gè)道理。這里介紹最常用的「預(yù)剪枝」，在構(gòu)造決策樹的過程中，提前停止。
具體的預(yù)剪枝策略有：
限制深度，例如，只構(gòu)造到兩層就停止。 限制葉子節(jié)點(diǎn)個(gè)數(shù)，例如，葉子節(jié)點(diǎn)個(gè)數(shù)超過某個(gè)閾值就停止
等等
Bagging ：訓(xùn)練多個(gè)分類器，最后可采取投票機(jī)制選擇最終結(jié)果。這里的分類器常常是決策樹。代表算法是 Boosting：仍是訓(xùn)練多個(gè)分類器，將最后的結(jié)果加權(quán)求和，代表算法是,
這些算法在一些比賽中都是很常見的。
本篇主要介紹的ID3算法仍有一定缺陷，之后的文章會繼續(xù)介紹。
編輯：tech小百科
參考目錄：
猜你喜歡