決策樹（一）

• 簡介

　　基于樹的學習算法被認為是最好的和最常用的監督學習方法之一。 基于樹的方法賦予預測模型高精度，穩定性和易于解釋的能力。 與線性模型不同，它們非常好地映射非線性關系。 它們适用于解決手頭的任何問題（分類或回歸）。決策樹，随機森林，梯度增強等方法正在各種資料科學問題中廣泛使用。 是以，對于每個分析師學習這些算法并将其用于模組化非常重要。本文的目的是介紹決策樹學習的基本理論基礎，并提出ID3算法。

什麼是決策樹？

　　簡而言之，決策樹是一棵樹，其中每個分支節點代表多個備選方案之間的選擇，每個葉節點代表一個決策。它是一種監督學習算法，主要用于分類問題，适用于分類和連續輸入和輸出變量。 是歸納推理的最廣泛使用和實用的方法之一（歸納推理是從具體例子中得出一般結論的過程）。決策樹從給定的例子中學習和訓練資料，并預測不可見的情況。

決策樹的圖形表示可以是：

　　

有幾種算法可以建構決策樹，其中一些是：

• CART（分類和回歸樹）：使用基尼指數作為度量。
• ID3算法：使用熵函數和資訊增益作為度量。

在本文中，我們将重點關注ID3算法。

與決策樹相關的重要術語

基本術語：

• 根節點(Root Node)：它代表整個種群或樣本，并進一步分為兩個或更多個同類集。
• 拆分(Splitting)：這是将節點劃分為兩個或更多個子節點的過程。
• 決策節點(Decision Node)：當子節點分裂成更多的子節點時，它被稱為決策節點。
• 葉子/終端節點(Leaf/ Terminal Node)：不分割的節點稱為葉子或終端節點。

• 修剪(Pruning)：當我們删除決策節點的子節點時，此過程稱為修剪。 你可以說相反的分裂過程。
• 分支/子樹(Branch / Sub-Tree)：整個樹的子部分稱為分支或子樹。
• 父節點和子節點(Parent and Child Node)：劃分為子節點的節點稱為子節點的父節點，其中子節點是父節點的子節點。

分類VS回歸

　　當因變量是連續的時，使用回歸樹。因變量是分類時使用分類樹。

• 在回歸樹的情況下，訓練資料中終端節點獲得的值是落在該區域中的觀測的平均值。是以，如果看不見的資料觀觀測屬于該區域，我們将使用平均值進行預測。
• 在分類樹的情況下，終端節點在訓練資料中獲得的值（類）是落在該區域中的觀察模式。是以，如果看不見的資料觀察屬于該區域，我們将使用模式值進行預測。

　　兩棵樹都将預測空間（自變量）劃分為不同的和不重疊的區域。為簡單起見，您可以将這些區域視為框。

　　這兩棵樹都遵循自上而下的貪婪方法，稱為遞歸二進制分裂。我們将其稱為“自上而下”，因為當所有觀察在單個區域中可用時，它從樹的頂部開始，并且連續地将預測器空間分成樹下​​的兩個新分支。它被稱為“貪婪”，因為該算法隻關注目前分裂的關鍵（尋找最佳可用變量），而不關心将來會導緻更好樹的分裂。繼續該拆分過程，直到達到使用者定義的停止标準。例如：一旦每個節點的觀測數量小于50，我們就可以告訴算法停止。

　　在這兩種情況下，分裂過程都會導緻樹木完全生長，直到達到停止标準。但是，完全成長的樹可能會過度填充資料，導緻看不見的資料的準确性很差。這帶來了'修剪'。修剪是用于解決過度拟合的技術之一。

優點

1. 易于了解：即使對于非分析背景的人來說，決策樹輸出也很容易了解。它不需要任何統計知識來閱讀和解釋它們。它的圖形表示非常直覺。
2. 在資料探索中很有用：決策樹是識别最重要變量和兩個或多個變量之間關系的最快方法之一。在決策樹的幫助下，我們可以建立具有更好預測目标變量能力的新變量（特征）。你可以參考一篇文章（Trick to enhance power of regression model）。它也可以用于資料探索階段。例如，我們正在研究一個問題，即我們有數百個變量可用的資訊，決策樹将有助于識别最重要的變量。
3. 需要更少的資料清理：與其他一些模組化技術相比，它需要更少的資料清理。它不受異常值和缺失值的影響。
4. 資料類型不是限制：它可以處理數字和分類變量。
5. 非參數方法：決策樹被認為是非參數方法。這意味着決策樹沒有關于空間分布和分類器結構的假設。

缺點

1. 過拟合：過拟合是決策樹模型最實用的難點之一。 通過設定模型參數和修剪的限制來解決這個問題。
2. 不适合連續變量：在處理連續數值變量時，決策樹在對不同類别的變量進行分類時會丢失資訊。

ID3算法

　　ID3代表Iterative Dichotomizer 3。ID3算法由Ross Quinlan發明。 它從一組固定的執行個體建構決策樹，結果樹用于對測試樣本進行分類。基本思想是通過在給定集合中使用自上而下的貪婪搜尋來構造決策樹，以測試每個樹節點處的每個屬性。決策樹的構造是作為重複過程完成的，估計哪個變量可以獲得最大的資訊增益。資訊增益是當已知自變量的狀态時因變量的熵的減少。從本質上講，當我們根據因變量的值将它分成組時，它會測量獨立變量的組織程度。選擇提供組織最大增加的因變量，并根據此變量拆分資料集。

資訊熵（Entropy）

在資訊論中，熵是衡量消息來源不确定性的名額。 它為我們提供了資料中的無組織程度。

給定集合S包含某些目标概念的正面和負面示例，S相對于此布爾分類的熵是：

這裡，p +和p-是S中正負例子的比例。

考慮相對于布爾分類（即二分類）的這種熵函數，因為正例p +的比例在0和1之間變化。

假設S是14個例子的集合，包括9個正例和5個負例子[9 +，5-]。 然後S的熵是：

請注意，如果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相對于示例集合S的資訊增益增益（S，A）被定義為：

• S =屬性A的所有可能值的每個值v
• Sv =屬性A具有值v的S的子集
• | SV| = Sv中的元素數
• | S | = S中的元素數 

具體例子

　　 假設我們想要ID3來決定天氣是否适合打棒球。 在兩周的時間内，收集資料以幫助ID3建構決策樹。 目标分類是“我們應該打棒球嗎？”，可以是或不是。

天氣屬性是 outlook, temperature, humidity, and wind speed.。 

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

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

 計算資料集上最高資訊增益的步驟

1.計算整個資料集的熵

14個記錄，9個yes，5個No

• Entropy(S) = – (9/14) Log2 (9/14) – (5/14) Log2 (5/14) = 0.940

2.計算每個屬性熵

2.1 - outlook 

 outlook屬性包含三個 不同的觀測:

• outlook = { sunny, overcast, rain }

• • overcast: 4 個記錄, 4 個 “yes”

  • 

  • rainy: 5 個記錄, 3 個 “yes”

  • 

  • sunny: 5 個幾率, 2 個“yes”

    

•  預期的新熵：

• 

2.2 - temperature

預期的新熵：

2.3 - humidity

預期的新熵：

2.4 - windy

預期的新熵：

3.資訊增益

顯然，outlook屬性的增益最高。 是以，它用作根節點。

　　由于outlook有三個可能的值，是以根節點有三個分支（ sunny, overcast, rain ）。 接下來的問題是，應該在sunny分支節點測試什麼屬性？ 由于我們在根部使用了outlook，我們隻決定其餘三個屬性： temperature, humidity, and wind。

• Ssunny = {D1, D2, D8, D9, D11} = 5 examples from the table with outlook = sunny
• 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

最終會生成一顆像下邊一樣的樹：

轉載于:https://www.cnblogs.com/jin-liang/p/9609144.html