機(jī)器學(xué)習(xí)是計(jì)算機(jī)科學(xué)的一個(gè)分支，它使計(jì)算機(jī)能夠在沒有編程的情況下進(jìn)行學(xué)習(xí)。

—— 亞瑟·塞繆爾，1959

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

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

所以，我們有必要對(duì)機(jī)器學(xué)習(xí)作一個(gè)簡單的認(rèn)識(shí)。現(xiàn)在我們來看看機(jī)器學(xué)習(xí)的一項(xiàng)熱門技術(shù)——決策樹。

什么是決策樹？

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

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

決策樹從給定的例子中學(xué)習(xí)和訓(xùn)練自己，并預(yù)測(cè)看不見的情況。

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

決策樹算法：ID3

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

這聽起來很簡單，但是我們?cè)撊绾芜x擇節(jié)點(diǎn)來構(gòu)建正確和最精確的決策樹呢？我們?cè)撛鯓幼龀鰶Q策呢？

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

熵（Entropy）

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

集合S中包含了與目標(biāo)內(nèi)容有正反偏差的實(shí)例，那么S在布爾分類上的熵就是：

在這里，p+和p-是S中正反實(shí)例的占比。由于這個(gè)熵函數(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；當(dāng)集合中包含的正反例子數(shù)量相等時(shí)，熵的值就為1；如果集合中包含了不相等的正反例子，那么熵值就介于0和1之間。

信息增益（Information Gain）

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

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

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

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

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

參見下面的表格：

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

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

我們需要找到在決策樹中哪個(gè)屬性會(huì)成為根節(jié)點(diǎn)。

• 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

對(duì)于其它幾個(gè)屬性我們也可以照這種方法進(jìn)行計(jì)算，得出的結(jié)果分別為：

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

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

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

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

Humidity擁有最高的增益，因此，它被選作決策節(jié)點(diǎn)。這個(gè)過程一直持續(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

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

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