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

—— 亞瑟·塞繆爾，1959

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

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

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

什么是決策樹？

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

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

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

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

決策樹算法：ID3

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

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

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

熵（Entropy）

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

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

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

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

信息增益（Information Gain）

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

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

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

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

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

參見下面的表格：

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

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

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

• 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屬性擁有最高的增益值，因此我們選取它作為根節(jié)點的決策屬性。

由于outlook有三個可能的值，因此其根節(jié)點有三個分支(sunny，overcast，rain)。那么下一個問題是，在sunny分支節(jié)點應該選什么屬性來檢測？由于我們已經(jīng)使用了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擁有最高的增益，因此，它被選作決策節(jié)點。這個過程一直持續(xù)到所有的數(shù)據(jù)都被完美地分類或者所有屬性被用完。

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

• 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

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

本文翻譯自，譯者：慧都控件網(wǎng)-回憶和感動