決策樹歸納的理論介紹

摘要： 銀行貸款員需要分析數據，以便搞清楚哪些貸款申請者是“安全”那些是“有風險”的。銷售經理需要數據分析，以便幫助他猜測哪些顧客會購買計算機。再或者醫學研究人員需要分析乳腺癌數據，以便預測病人應當接受三種治療中的哪一種。在上面的例子中，數據分析任務都是分類，都需要構造一個模型來預測一個類別型數據。譬如安全或者不安全、會購買與不會購買、那種治療都是類別型。分類是一種重要的數據分析形式，它提取刻畫重要數據類的模型，用來預測（離散的、無序的）類標號。

作者：醜小鴨

什麼是分類？

銀行貸款員需要分析數據，以便搞清楚哪些貸款申請者是“安全”那些是“有風險”的。銷售經理需要數據分析，以便幫助他猜測哪些顧客會購買計算機。再或者醫學研究人員需要分析乳腺癌數據，以便預測病人應當接受三種治療中的哪一種。在上面的例子中，數據分析任務都是分類，都需要構造一個模型來預測一個類別型數據。譬如安全或者不安全、會購買與不會購買、那種治療都是類別型。分類是一種重要的數據分析形式，它提取刻畫重要數據類的模型，用來預測（離散的、無序的）類標號。

決策樹是一種類似於流程圖的樹結構，其中，每個內部節點(非樹葉節點）表示在一個屬性上的測試，每個分支代表該測試的一個輸出，而每個樹葉節點（或終端節點）存放一個類標號。樹的最頂層節點是根節點。

比如我們想要決定要不要給一個用戶貸款，第一個分裂準則可以定義為age年齡，年齡底下有三個分枝，Youth，middle_aged和Senior。年輕人中再以是否為大學生作為一個分裂節點，如果是學生就給貸款，yes就是這條枝子上的葉子節點，也就是最後的類標號。

數據分類過程：a)學習，及建立樹的階段。用分類算法分析訓練數據，學習的模型以分類規則（Splitting criterian）或者叫屬性選擇度量形式提供；b)分類。檢驗數據用於評估分類規則的準確率，如果準確率是可以接受的，則規則用於新的數據元組分類。

屬性選擇度量是一種選擇分裂標準，把給定類標記的訓練元組的數據分區D“最好地”劃分成單獨類的啟發方式，比如量——信息增益、增益率和基尼指數。

1、用信息增益進行決策樹歸納

看不懂公式可以直接看下面例子

該度量基於Claude Shannon在研究消息的值或“信息內容”的信息論方面的先驅工作。設計節點N代表或存放分區D的元組。選擇具有最高信息增益的屬性作為節點N的分裂屬性。該屬性使結果分區中對元組分類所需要的信息量最小，並反映這些分區中的最小隨機性或“不純性”。這種方法使得對一個對象的分類所需要的期望測試數目最小，並確保找到一顆簡單的（但不必是最簡單的）樹。

現在我們假設要按某屬性A劃分D中的元組，其中屬性A根據訓練數據的觀測具有v個不同的值｛a1,a2, …, av｝。理想情況下我們希望該劃分產生的元組的準確分類，即我們希望每個分區都是純的。然而這些分區多半是不純的（例如，分區可能包含來自不同類而不是來自單個類的元組）。為了得到準確的分類，我們需要下式度量：

例子：

首先使用（8.1）式計算D中元組分類所需要的期望信息：

Info(D)=-log₂(9/14)*(9/14)-log₂(5/14)*(5/14)=0.94

下一步計算每個屬性的期望信息需求。從屬性age開始，需要對age的每個類考察Yes和NO元組的分佈。對於age的類“youth”，有2個yes和3個no元組。同樣的，middle_aged有4個yes和0個no，senior有3個yes和2個No。使用（8.2）式，如果元組根據age劃分，則對D中的元組進行分類所需要的期望信息為：

類似的，可以計算Gain(Income)= 0.02, Gain(Student)= 0.151, Gain(credit_rating)=0.048。由於age屬性中具有最高的信息增益，所以它被選作分裂屬性。注意，落在分區age = middle_aged的元組都屬於相同的類，即分類都是yes，所以在該分支的端點是一個葉子節點。

這樣一次分裂就完成了。所以對於youth和senior可以用剛才的步驟進行下一步的分裂，直到結束。

基尼指數進行決策樹歸納的總體做法是跟上面的信息增益一式一樣的，只不過公式不同，再次不再作詳細的介紹。有興趣的童靴可以參考上面給出的書籍。不過基尼指數強制樹是二叉樹。

決策樹歸納的步驟：

這一部分我放在最後是因為放在一開始可能不利於理解。看完了上面的例子相信你可以更好地理解決策樹歸納的步驟：

~我們稱原始的數據集為D。開始，它是訓練元組和他們相應類標號的完全集。參數Attribute_list是描述元組屬性的列表。Attribute_selection_method指定選擇屬性的啟發式過程，用來選擇可以按類“最好地”區分給定元組的屬性。該過程使用一種屬性選擇度量，如信息增益或基尼指數（Gini Index）。樹是否是嚴格的二叉樹由屬性選擇度量決定。比如基尼指數強制結果樹是二叉樹。信息增益並非如此，它允許多路劃分（即從一個節點生長兩個或多個分枝）。

~樹從單個節點N開始，N代表D中的訓練元組。

~如果D中的元組都為同一類，則節點N變為樹葉，並用類標記它。

~否則調用Atrribute_selection_method確定分裂準則，使得每一個分枝上的輸出分區都盡可能“純”。一個分區是純的，如果它的所有元組都屬於同一類。換言之，如果根據分裂準則的互斥輸出劃分D中的元組，則希望結果分區盡可能純。

~分裂時有三種可能的情況，離散、連續、離散且必須產生二叉樹。比如color作為分枝節點，它的子節點是離散的，比如red,green,blue等等；income是連續的,這是我們的子節點可以分成兩支，對應於>=split_point和<split_point。比如income>= 10k和income<10k。其中的split_point作為分裂點；而在基尼指數中必須產生二叉樹，比如要限定Color的子節點為兩個,我們就可以定義一個集合S，比如S={red,green}，凡屬於這個集合的形成一個樹枝，不屬於的形成另一個。

~對於分區D的每個結果分區上的元組，算法使用同樣的過程遞歸地形成決策樹。

~遞歸劃分步驟僅當下列種植條件之一成立時停止：

1. 分區D的所有元組都屬於同一個類，如上面的middle_aged例子；
2. 沒有剩餘屬性可以用來進一步劃分元組，在此情況下使用多數表決，創建葉子節點，並用多數類來標記它；
3. 給定的分枝沒有元組，即分區為空，那就要用D中的多數類創建一個樹葉。

~返回結果決策樹。

剪枝

由於數據中的噪聲和離群點，可能會產生過分擬合的數據問題，剪枝就可以很好地解決。有兩種常見的剪枝方法：先剪枝和後剪枝。

先剪枝：通過提前停止樹的構建（例如，通過決定在給定的節點不再分裂或劃分訓練元組的子集）而對樹“剪枝”。一旦停止，節點就成為樹葉。該樹葉可以持有子集元組中最頻繁的類，或者這些元組的概率分佈。

在構造樹時，可以使用諸如統計顯著性、信息增益、基尼指數等度量來評估劃分的優劣。如果劃分一個節點的元組導致低於預定義閾值的劃分，則給定子集的進一步劃分將停止。然而，選取一個適當的閾值是困難的。更常用的方法是後剪枝。

後剪枝：它有“完全生長”的樹減去子樹，通過刪除節點的分枝並用葉子節點取代。該樹葉的類標號用子樹中最頻繁的類標記。CART使用的代價複雜度剪枝算法是後剪枝方法的一個實例。該方法把樹的複雜度看作樹中樹葉節點的個數和樹的錯誤率的函數（錯誤率是樹誤分類的元組佔的百分比）。它從樹的底部開始。對於每個內部節點，計算它的子樹的代價複雜度和該子樹剪枝後的該節點字數的代價複雜度，比較兩個值取較小的代價複雜度。

End.

轉貼自： 36大數據