關於「樹」的算法:現實生活中的決策樹

全文共2874字，預計學習時長8分鐘

圖源：unsplash

就像樹木是人類生活的重要組成部分一樣，基於樹的算法也是機器學習的重要組成部分。樹的結構給了我們開發算法的靈感，並再將其反饋到機器，讓它們學習我們希望它們學習的東西，以解決現實生活中的問題。

這些基於樹的學習算法被認為是最好和最常用的監督學習方法之一：決策樹、隨機森林、梯度提升等方法在各種數據科學問題中得到了廣泛應用。對於每一個機器學習的初學者來說，學習這些算法並將其用於建模非常重要。

決策樹是什麼?

決策樹是一種帶有節點的樹狀圖，節點表示我們選取一個屬性並提出問題，邊表示問題的答案，葉表示實際輸出或類標籤。它們被用於具有簡單線性決策面的非線性決策。

決策樹對例子進行分類，方法是將它們從樹的根排序到某個葉節點，葉節點為例子進行分類。樹中的每個節點作為某個屬性的測試用例，從該節點下行的每條邊都對應於測試用例的可能答案之一。這個過程本質上屬於遞歸性質，並且對於每一個紮根於新節點的子樹都要重複進行。

現實生活中的決策樹

你肯定在生活中使用過決策樹來做決定。舉個例子，決定是否要在某天和孩子一起打網球。

這取決於各種各樣的因素，比如你是否能按時下班，是否能提前下班，你是否能在晚上6點之前到家，這取決於交通狀況，或者你的孩子那天是否已經安排了其他活動；總的來說，你是否能和孩子一起出去打網球，取決於你和你的孩子在那一天的時間安排和外面的天氣。

如果天氣很好，你可以按時下班，也可以準時回家，孩子也沒有別的課，你可以和他一起去網球場。如果你按時到達，但他那天已經安排了其他活動，你可能只想在家放鬆一下，看一些電影。

這是一個典型的現實生活中決策樹的例子。我們已經建立了一個樹來模擬一組連續的、分層的決策，這些決策最終會導致一些最終的結果。

請注意，我們還選擇了相當「高級」的決策，以保持樹的規模。例如，如果我們設置很多可能的天氣選項，比如25度晴，25度雨，26度晴，26度雨，27度晴……等等，我們的樹將變得巨大！確切的溫度其實不太重要，我們只是想知道是否適合戶外活動。

因此，你可以把最近幾天的因素都計算出來，並繪製一個查詢表，如下所示。

決策樹算法如何工作？

任何決策樹算法背後都有如下基本思想：

1.使用屬性選擇度量（ASM）選擇最佳屬性來分割記錄。

2.將該屬性設為一個決策節點，並將數據集分解為更小的子集。

3.通過對每個子元素遞歸重複此過程來開始建樹，直到滿足以下條件之一：

· 所有元組屬於同一屬性值

· 沒有其他屬性

· 沒有其他實例

ASM通過解釋給定的數據集為每個特性（或屬性）提供了一個等級。最佳得分屬性將被選擇為分割屬性。對於連續值屬性，還需要定義分支的分割點。最常用的選擇指標是信息增益、增益比和基尼係數。

信息增益是什麼，如何衡量？

信息增益是一種統計屬性，它測量給定屬性根據目標分類分離訓練實例的程度。

信息增益是熵（隨機性）的降低。根據給定的屬性值計算數據集分割前熵與分割後平均熵的差值。熵的基本計算公式為：

其中，Pi是D中任意元組屬於類Ci的概率。

那麼，信息增益的計算方式為：

現在，來計算每個父節點和子節點的熵：

E(Parent Node) =-[P(tennis)log(base2)P(tennis)

+ P(Home)log(base2)P(Home)]

= — [(1/2)log(base2)(1/2) +(1/2)log(base2)(1/2)]

= 1

Since P(tennis) = 1/2 and P(Home) = 1/2

現在，讓我們看看父節點是否按第一個屬性分割，即天氣。如果我們看到上面給出的數據，根據天氣屬性，我們會得到以下值，供我們決定是否打網球：

Rainy: Stay at Home

Sunny: Tennis,Tennis,StayHome

右側子節點的熵——E(rainy)：

= -P(Home)log(base2)P(Home)

=-1log(1)= 0

左側子節點的熵——E(Sunny)：

-[P(Home)log(base2)P(Home)

+ P(Tennis)log(base2)P(Tennis)]

= -[(1/3)log(base2)(1/3) +(2/3)log(base2)(2/3)] = 0.9

可得

Information Gain(Weather) =Entropy(Parent) — [sum of(weighted average*entropy of each child)]

= 1 — [(3/4)*(0.9)+(1/4)*0] = 0.325

同樣，我們也計算了其他屬性的熵和信息增益，得到以下結果：

IG(WorkSchedule) = 1

IG(Traffic) = 0.325

IG(Availability) = 0.325

由於「工作日程」這個屬性的信息增益最高，我們可以說，能夠預測你當天是否會打網球的最準確的屬性是你的工作日程。

基尼指數是什麼？

決策樹算法CART（分類與回歸樹）採用基尼法創建分割點。

其中，pi是D中元組屬於Ci類的概率。

基尼指數，又稱基尼雜質，指計算隨機選取某一特定屬性時分類錯誤的概率。如果所有元素都連結到一個類，那麼它就可以被稱為pure。基尼指數考慮每個屬性的二元分割。你可以計算每個分區雜質的加權和。若對屬性A進行二叉分割，將數據D分成D1和D2，則D的基尼指數為：

在離散值屬性的情況下，為所選屬性提供最小基尼指數的子集被選為分割屬性。對於連續值屬性，策略是選擇每對相鄰的值作為可能的分割點，選擇基尼指數較小的點作為分割點。

選擇基尼指數最小的屬性作為分割屬性。

現在，試著根據天氣屬性來計算上面數據的基尼指數。

Gini(Sunny) = 1 — [(2/3)*(2/3) +(1/3)*(1/3)] = 4/9 = 0.444

Gini(Rainy) = 1 — [(1/1)*(1/1)] = 0

可得

Gini(Weather) = (3/4) * 0.444 + (1/4) * 0 =0.333

基於其他屬性，基尼指數如下：

Gini(Traffic) = (3/4) * {1 —[(1/3)*(1/3) + (2/3)*(2/3)] } + (1/4) * { 1- [ (1/1)*(1/1)]} = 0.333

Gini(Work Schedule) = (2/4) * [1 —(1*1)] + (2/4) * [1 — (1*1)] = 0

Gini(Availability) = 0.333

因此，基尼係數最小的屬性，即工作日程，在這裡是決策的分割屬性。

留言點讚關注

我們一起分享AI學習與發展的乾貨

如轉載，請後臺留言，遵守轉載規範