找到決策樹的最佳屬性

4

首先快了很多，讓清楚什麼是「最好的」屬性意味着決策樹的光 - 這是「最佳」分類可用訓練示例的屬性。有兩個術語需要熟悉以定義「最佳」 - 熵和信息增益。熵是一個來自信息論的術語 - 它是一個數字，表示一組示例基於目標類別的異構性。關於熵的另一種觀點 - 這是從一組示例中對隨機示例的類進行編碼所需的位數。另一方面，信息增益顯示如果選擇特定屬性，一組示例的熵將減少多少。另一種觀點 - 它顯示瞭如果選擇特定屬性，則表示隨機示例類別所需的位數會減少。

那麼，爲什麼我們選擇基於訓練樣例的「最佳」屬性呢？簡單的答案是因爲這是構造決策樹的算法的工作原理 - 它搜索所有可能的決策樹，並選擇第一個使用簡單到複雜的搜索正確分類訓練示例的決策樹。由於基本實現不包括任何重新訪問和更改早期決策的機制，因此使用貪婪方法而不是隨機方法是有意義的。

下面是一個簡單的例子，用於演示構建決策樹時不選擇「最佳」屬性的後果。讓我們假設我們有一個屬性考試，朋友，天氣以下培訓的例子和目標活動。這些示例根據是否即將進行考試，是否有朋友可用以及天氣是晴天還是雨天來描述首選活動。

╔══════╦═════════╦═════════╦══════════╗ 
║ Exam ║ Friends ║ Weather ║ Activity ║ 
╠══════╬═════════╬═════════╬══════════╣ 
║ yes ║ yes  ║ sunny ║ study ║ 
║ no ║ yes  ║ sunny ║ picnic ║ 
║ yes ║ no  ║ rain ║ study ║ 
║ yes ║ yes  ║ rain ║ study ║ 
║ no ║ yes  ║ rain ║ play  ║ 
║ no ║ no  ║ rain ║ play  ║ 
╚══════╩═════════╩═════════╩══════════╝

當我們這樣做，我們最終得到的信息增益下面的數字數學：

IG(D, Exam) ~ 1 
IG(D, Friends) ~ 0.13 
IG(D, Weather) ~ 0.46

「最好」的屬性來選擇決定樹的根是考試。下一步是確定哪些屬性要選擇何時檢查何時進行檢查，什麼時候沒有檢查。當很快進行考試時，活動總是在進行學習，所以不需要進一步的探索。當快沒有考試，我們需要計算的信息增益選擇朋友和天氣：

IG(D-No-Exam, Friends) ~ 0.25 
IG(D-No-Exam, Weather) ~ 0.92

繼相同的策略之前，我們會選擇天氣最後決策樹會是這樣的：

 Exam? 
    /\ 
    yes no 
    / \ 
STUDY  Weather? 
      / \ 
     sunny rain 
     /  \ 
     PICNIC  PLAY

現在，讓我們構建一個決策樹分類的例子，但使用不同的根 - 朋友和隨機町在需要的地方添加屬性。我們可以結束以下樹：

   Friends? 
       / \ 
       yes  no 
      /  \ 
      Exam?   Exam? 
     /\   / \ 
     yes no  yes no 
     / \  |  | 
    STUDY Weather? STUDY PLAY 
      / \ 
      sunny rain 
      /  \ 
      PICNIC PLAY

兩棵樹都正確地分類訓練示例。不同之處在於第二棵樹更復雜，可能過度適合訓練數據。通過始終選擇最佳屬性構建決策樹的算法「優先選擇」較短且較不復雜的樹，並首先檢查最佳屬性的樹。

來源

2016-03-22 16:13:43 mishless

0

確定在決策樹中選擇哪個屬性的常用方法是information gain。基本上，您可以嘗試每個屬性，並查看哪一個最適合您的數據。看看這個套牌的第6頁：http://homes.cs.washington.edu/~shapiro/EE596/notes/InfoGain.pdf

來源

2016-03-22 15:38:58 Nate

0

一如既往取決於案件。但大多數情況下，您希望儘可能快地執行該樹，因此您希望避免不必要的決策/分支。所以，你選擇了最好的功能（和相應的分割位置），而其他人則需要2-3個分支最終預測樣本。

可以很容易地看到處理樹時，與一般的10家分公司會比另外一個有30個分公司

來源

2016-03-22 15:42:53 user3085931

找到決策樹的最佳屬性

回答

相關問題