機器學習 | 決策樹的生成過程是怎樣?(一)

1 評論 13370 瀏覽 31 收藏 12 分鐘

本文筆者將用具體例子講述決策樹的構建過程,分析:決策樹生成過程中有什么樣的問題?

一、基本概念

決策樹的定義:

首先,決策樹是一種有監督的分類算法——即給定X,Y值,構建X,Y的映射關系。

不同于線性回歸等是多項式,決策樹是一種樹形的結構,一般由根節點、父節點、子節點、葉子節點構成如圖所示。

父節點和子節點是相對的,子節點可以由父節點分裂而來,而子節點還能作為新的父節點繼續分裂;根節點是沒有父節點,即初始分裂節點,葉子節點是沒有子節點的節點,為終節點。

每一個分支代表著一個判斷,每個葉子節點代表一種結果。

這是在已知各種情況的發生的概率的基礎上,通過構建決策樹來進行分析的一種方式。

預測方式:

  • 根據輸入的樣本X的特征屬性和決策樹的取值,將輸入的X樣本分配到某一個葉子節點中。
  • 將葉子節點中出現最多的Y值,作為輸入的X樣本的預測類別。

目的:

最優的模型應該是:葉子節點中只包含一個類別的數據。

但是,事實是不可能將數據分的那么的純,因此,需要“貪心”策略,力爭在每次分割時都比上一次好一些,分的更純一些。

二、決策樹構建過程

步驟一:將所有的特征看成一個一個的節點,eg(擁有房產、婚姻狀態、年收入這些特征,我們可以看成一個一個的節點。)

步驟二:遍歷當前特征的每一種分割方式,找到最好的分割點eg(婚姻狀態這個特征,我們可以按照單身、已婚、離婚進行劃分;也可以按照結過婚、沒有結過婚進行劃分);將數據劃分為不同的子節點,eg: N1、 N2….Nm;計算劃分之后所有子節點的“純度”信息

步驟三:使用第二步遍歷所有特征,選擇出最優的特征,以及該特征的最優的劃分方式,得出最終的子節點N1、 N2….Nm

步驟四:對子節點N1、N2….Nm分別繼續執行2-3步,直到每個最終的子節點都足夠“純”。

從上述步驟可以看出,決策生成過程中有兩個重要的問題:

  1. 對數據進行分割。
  2. 選擇分裂特征。
  3. 什么時候停止分裂。

1. 對數據進行分割

根據屬性值的類型進行劃分:

如果值為離散型,且不生成二叉決策樹,則此時一個屬性就是可以一個分支,比如:上圖數據顯示,婚姻狀態為一個屬性,而下面有三個值,單身、已婚、離婚,則這三個值都可以作為一個分類。

如果值為離散型,且生成二叉決策樹,可以按照 “屬于此子集”和“不屬于此子集”分成兩個分支。還是像上面的婚姻狀態,這可以按照已婚,和非婚,形成兩個分支。

如果值為連續性,可以確定一個值作為分裂點,按照大于分割點,小于或等于分割點生成兩個分支,如上圖數據,我可以按照6千元的點劃分成:大于6千元和小于6千元。

2. 找到最好的分裂特征

決策樹算法是一種“貪心”算法策略——只考慮在當前數據特征情況下的最好分割方式。

在某種意義上的局部最優解,也就是說我只保證在當分裂的時候,能夠保證數據最純就好。

對于整體的數據集而言:按照所有的特征屬性進行劃分操作,對所有劃分操作的結果集的“純度”進行比較,選擇“純度”越高的特征屬性作為當前需要分割的數據集進行分割操作。

決策樹使用信息增益作為選擇特征的依據,公式如下:

H(D)為:分割前的純度。

H(D|A)為:在給定條件A下的純度,兩者之差為信息增益度。如果信息增益度越大,則H(D|A)越小,則代表結果集的數據越純。

計算純度的度量方式:Gini、信息熵、錯誤率。

一般情況下,選擇信息熵和Gini系數,這三者的值越大,表示越“不純”。

Gini:

信息熵:

錯誤率:

3. 什么時候停止分裂

一般情況有兩種停止條件:

  1. 當每個子節點只有一種類型的時候停止構建。
  2. 當前節點中記錄數小于某個閾值,同時迭代次數達到給定值時,停止構建過程。此時,使用 max(p(i))作為節點的對應類型。

方式一可能會使樹的節點過多,導致過擬合(Overfiting)等問題。所以,比較常用的方式是使用方式二作為停止條件。

三、舉例

數據集如下:

1. 對數據特征進行分割

  • 擁有房產(是、否)
  • 婚姻狀態(單身、已婚、離婚)
  • 年收入(80、97.5)

2. 通過信息增益找到分割特征

首先,計算按照擁有房產這個特征進行劃分的信息增益,使用錯誤率進行純度的計算:

計算原始數據的純度:

計算按擁有房產劃分后的結果集數據純度H(D|A):

H(D| X=有房產) 的計算方式:

H(D| X=無房產) 的計算方式:

計算信息增益度Gain(房產):

同理,可以計算:婚姻狀態 年收入=97.5

Gain(婚姻) = 0.205

Gain(婚姻) =0.395

按照Gain越大,分割后的純度越高,因此第一個分割屬性為收入,并按照97.5進行劃分。

左子樹的結果集夠純,因此不需要繼續劃分。

接下來,對右子樹年收入大于97.5的數據,繼續選擇特征進行劃分,且不再考慮收入這個特征,方法如上,可以得到如圖:

四、常見算法

ID3:

優點:決策樹構建速度快;實現簡單

缺點:

  • 計算依賴于特征數目較多的特征,而屬性值最多的屬性并不一定最優 。
  • ID3算法不是遞增算法,ID3算法是單變量決策樹,對于特征屬性之間的關系不會考慮。
  • 抗噪性差。
  • 只適合小規模數據集,需要將數據放到內存中。

C4.5:

在ID3算法的基礎上,進行算法優化提出的一種算法(C4.5),使用信息增益率來取代ID3中的信息增益。

CART(Classification And Regression Tree):

五、總結

  1. ID3和5算法均只適合在小規模數據集上使用。
  2. ID3和5算法都是單變量決策樹當屬性值取值比較多的時候,最好考慮C4.5算法,ID3得出的效果會比較差? 決策樹分類一般情況只適合小數據量的情況(數據可以放內存)? CART算法是三種算法中最常用的一種決策樹構建算法(sklearn中僅支持CART)。
  3. 三種算法的區別僅僅只是對于當前樹的評價標準不同而已,ID3使用信息增益、 5使用信息增益率、CART使用基尼系數。
  4. CART算法構建的一定是二叉樹,ID3和5構建的不一定是二叉樹。

 

本文由 @SincerityY 原創發布于人人都是產品經理。未經許可,禁止轉載

題圖來自Unsplash,基于CC0協議

更多精彩內容,請關注人人都是產品經理微信公眾號或下載App
評論
評論請登錄
  1. mark

    回復