?

決策樹（）是一類很常見很經(jīng)典的機器學習算法，既可以作為分類算法也可以作為回歸算法。同時也適合許多集成算法，如, ，以后會逐一介紹。本篇介紹一下決策樹算法的原理。?

決策樹算法不像前面介紹的SVM那樣，散發(fā)著濃厚的數(shù)學氣味。這個算法還是比較接地氣的。

信息論基礎(chǔ)

這個語法結(jié)構(gòu)大家應(yīng)該不陌生。怎樣準確地定量選擇 后面的條件，也就是要找到一個性能指標來衡量這個條件的好壞。（就像SVM中引入了來衡量一條直線的好壞）。

70年代，一個名為昆蘭的大牛找到了信息論中的「熵」來度量決策樹的決策選擇過程。注意，信息論中的熵是香農(nóng)提出的。昆蘭只是將熵應(yīng)用于決策樹的人。

熵度量了事物的不確定性(可以聯(lián)想化學里的熵，混亂程度)，越不確定的事物，它的熵就越大。具體的，隨機變量X的熵的表達式如下：

決策樹構(gòu)造

決策樹的組成：

• 根節(jié)點：第一個選擇點
• 非葉子節(jié)點與分支：中間過程
• 葉子節(jié)點：最終的決策結(jié)果就像這張圖展示的，第一個節(jié)點就是根節(jié)點，綠色的代表 也就是葉子節(jié)點，其它的節(jié)點也就是非葉子節(jié)點(用于決策)，也就是 。

那么如何構(gòu)造決策樹呢？

「第一步，選擇根節(jié)點」。

問題來了，特征不唯一，選哪一個作根節(jié)點最優(yōu)？

這就涉及到了衡量標準，一般而言，隨著劃分過程不斷進行，我們希望節(jié)點的熵能夠迅速地降低。因為隨機變量的熵越大，隨機變量的不確定性越大，代表純度越低。所以希望節(jié)點的熵能夠迅速降低，使得純度不斷增加。所以以「信息增益」作為衡量標準。

引入一個信息增益( )的概念。

?

「定義」：特征 對訓(xùn)練數(shù)據(jù)集 的信息增益 ，定義為集合 的經(jīng)驗熵 與特征 給定條件下 的經(jīng)驗條件熵 之差，即

?

信息增益也就度量了熵降低的程度。
以信息增益作為衡量標準的算法被稱為ID3算法。

「第二步，選擇子節(jié)點」

依然是采用信息增益的標準進行選擇。

「第三步，何時停止」

其實這一步就涉及到剪枝，下文詳解。

如果對這些概念還是有點模糊，可以結(jié)合下面的實例再思考思考。

實例

這是數(shù)據(jù)（14天的打球情況），有四種環(huán)境特征（outlook,humidity）,最后一列(play）代表最后有沒有出去打球。

「首先，選擇根節(jié)點」。一共有四個特征，所以根節(jié)點的選擇有四種。

在我們的原始數(shù)據(jù)（14天）有9天打球，5天不大，所以此時的熵為：

接著，四個特征逐一分析，先從(天氣)下手：當 時，

當 時，
當 時，

根據(jù)數(shù)據(jù)， 取 ,,的概率分別為,
熵值計算（幾個特征屬性熵的加權(quán)求和）：

信息增益：

同樣的方式計算其它三個特征的信息增益：

四個特征中， 的增益最大，所以選擇作為根節(jié)點。
「接下來的子節(jié)點選擇同上」。

「何時停止？」
上文也說了，"何時停止"涉及到剪枝。為什么要剪枝？
決策樹存在較大的過擬合風險，理論上，決策樹可以將樣本數(shù)據(jù)完全分開，但是這樣就帶來了非常大的過擬合風險，使得模型的泛化能力極差。剪枝和日常樹木的修建是一個道理。這里介紹最常用的「預(yù)剪枝」，在構(gòu)造決策樹的過程中，提前停止。
具體的預(yù)剪枝策略有：

• 限制深度，例如，只構(gòu)造到兩層就停止。
• 限制葉子節(jié)點個數(shù)，例如，葉子節(jié)點個數(shù)超過某個閾值就停止
  等等

• Bagging ：訓(xùn)練多個分類器，最后可采取投票機制選擇最終結(jié)果。這里的分類器常常是決策樹。代表算法是
• Boosting：仍是訓(xùn)練多個分類器，將最后的結(jié)果加權(quán)求和，代表算法是,

這些算法在一些比賽中都是很常見的。

本篇主要介紹的ID3算法仍有一定缺陷，之后的文章會繼續(xù)介紹。

編輯：tech小百科

參考目錄：