機器學習是計算機科學的一個分支，它使計算機能夠在沒有編程的情況下進行學習。

—— 亞瑟·塞繆爾，1959

在熟悉的《終結者》系列中，我們看到了機器學習的身影，對于影片中強大的人工智能，有些人表現了對幻想成真的擔憂，而另一些人則表現出了對這全新世界的期待。或許，未來的人工智能可能想要消滅整個人類，但就目前而言，人工智能所帶來的成就和收益遠遠超出了我們想象。

谷歌的無人駕駛汽車，Facebook的人臉識別，亞馬遜的智能推薦，Siri和Cortana的語音識別，PayPal的欺詐檢測……諸如此類的應用還有很多很多。

所以，我們有必要對機器學習作一個簡單的認識。現在我們來看看機器學習的一項熱門技術——決策樹。

什么是決策樹？

簡單地說，決策樹是一棵樹，其中每個分支節點代表多個備選方案之間的選擇，每個葉節點代表一個決策。

它是一種受監督的學習算法(帶有預定義的目標變量)，主要用于分類問題和對持續性輸入輸出變量歸類的工作。它是歸納推理中應用最廣泛、最實用的方法之一。(歸納推理是從具體例子中得出一般結論的過程。)

決策樹從給定的例子中學習和訓練自己，并預測看不見的情況。

決策樹的圖形化示例如下所示：

決策樹算法：ID3

ID3是Iterative Dichotomizer 3的簡稱，此算法是由Ross Quinlan發明的，他通過對一組固定的示例構建決策樹，然后將結果樹用于對未來樣本進行分類。其基本思想是通過使用一個自上而下的、貪婪算法來構造決策樹，在每個樹節點上測試各種屬性。

這聽起來很簡單，但是我們該如何選擇節點來構建正確和最精確的決策樹呢？我們該怎樣做出決策呢？

嗯。我們可以采取一些措施來幫助我們進行最好的選擇！

熵（Entropy）

在信息論中，熵是對信息來源不確定性的量度。它定量了數據無序的程度。熵越大表示集合越混亂，反之則表示集合越有序。

集合S中包含了與目標內容有正反偏差的實例，那么S在布爾分類上的熵就是：

在這里，p+和p-是S中正反實例的占比。由于這個熵函數涉及到布爾分類，因此p+和p-的取值是介于0和1之間。

注意，如果S中只包含了一種分類，那么熵就是0。例如，如果所有的成員都是正的(p+ = 1)，那么p-等于0 ，Entropy(S) = -1 * log2(1)–0 * log2(0) = -1 * 0–0 * log2(0) = 0；當集合中包含的正反例子數量相等時，熵的值就為1；如果集合中包含了不相等的正反例子，那么熵值就介于0和1之間。

信息增益（Information Gain）

它衡量了熵值的預期減少量。它決定了哪個屬性會放入決策節點。為了讓決策樹的深度最小化，擁有最大化減少熵值的屬性是最優的選擇。

更確切地說，屬性A的信息增益Gain(S, A)相對于集合的例子S可被定義為：

其中S為屬性A可能出現的任意值的集合，Sv為屬性A在值為v時S的子集，|Sv|為Sv中的元素數量，|S|為S中的元素數量。

讓我們看看這些措施是如何工作的。

假設我們需要ID3來決定天氣是否適合打棒球。在兩周的時間里，收集數據來幫助ID3構建決策樹。目標分類是“我們應該打棒球嗎?”答案為是或者否。

參見下面的表格：

天氣屬性包含了outlook（氣象）, temperature（溫度）, humidity（濕度）和wind speed（風速），它們包含以下的值：

• outlook = {sunny, overcast, rain}
• temperature = {hot, mild, cool}
• humidity = {high, normal}
• wind = {weak, strong}

我們需要找到在決策樹中哪個屬性會成為根節點。

• Entropy(S) = –(9/14) Log2 (9/14) – (5/14) Log2 (5/14) = 0.940
• Gain(S, Wind) = Entropy(S) – (8/14)*Entropy(Sweak) – (6/14)*Entropy(Sstrong)= 0.940 – (8/14)*0.811 – (6/14)*1.00 = 0.048
  • Entropy(Sweak) = - (6/8)*log2(6/8) – (2/8)*log2(2/8) = 0.811
  • Entropy(Sstrong) = - (3/6)*log2(3/6) – (3/6)*log2(3/6) = 1.00

對于其它幾個屬性我們也可以照這種方法進行計算，得出的結果分別為：

• Gain(S, Outlook) = 0.246
• Gain(S, Temperature) = 0.029
• Gain(S, Humidity) = 0.151

很明顯，outlook屬性擁有最高的增益值，因此我們選取它作為根節點的決策屬性。

由于outlook有三個可能的值，因此其根節點有三個分支(sunny，overcast，rain)。那么下一個問題是，在sunny分支節點應該選什么屬性來檢測？由于我們已經使用了outlook，那么將在humidity, temperature和wind之間作出選擇。

• Ssunny = {D1, D2, D8, D9, D11} = 表格中outlook值為sunny的5個實例
• Gain(Ssunny, Humidity) = 0.970
• Gain(Ssunny, Temperature) = 0.570
• Gain(Ssunny, Wind) = 0.019

Humidity擁有最高的增益，因此，它被選作決策節點。這個過程一直持續到所有的數據都被完美地分類或者所有屬性被用完。

此決策樹也可以用規則格式表示為：

• IF outlook = sunny AND humidity = high THEN play baseball = no
• IF outlook = rain AND humidity = high THEN play baseball = no
• IF outlook = rain AND wind = strong THEN play baseball = yes
• IF outlook = overcast THEN play baseball = yes
• IF outlook = rain AND wind = weak THEN play baseball = yes

以上便是對決策樹的簡單介紹，希望對你有所幫助。

本文翻譯自，譯者：慧都控件網-回憶和感動