科技

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

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

一、基本概念決策樹的定義:

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

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

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

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

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

預測方式:

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

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

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

二、決策樹構建過程

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

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

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

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

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

對資料進行分割。選擇分裂特徵。什麼時候停止分裂。1. 對資料進行分割根據屬性值的型別進行劃分:

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

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

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

2. 找到最好的分裂特徵決策樹演算法是一種“貪心”演算法策略——只考慮在當前資料特徵情況下的最好分割方式。

在某種意義上的區域性最優解,也就是說我只保證在當分裂的時候,能夠保證資料最純就好。

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

決策樹使用資訊增益作為選擇特徵的依據,公式如下:

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

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

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

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

Gini:

資訊熵:

錯誤率:

3. 什麼時候停止分裂一般情況有兩種停止條件:

當每個子節點只有一種型別的時候停止構建。當前節點中記錄數小於某個閾值,同時迭代次數達到給定值時,停止構建過程。此時,使用 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):

五、總結ID3和5演算法均只適合在小規模資料集上使用。ID3和5演算法都是單變數決策樹當屬性值取值比較多的時候,最好考慮C4.5演算法,ID3得出的效果會比較差 決策樹分類一般情況只適合小資料量的情況(資料可以放記憶體) CART演算法是三種演算法中最常用的一種決策樹構建演算法(sklearn中僅支援CART)。三種演算法的區別僅僅只是對於當前樹的評價標準不同而已,ID3使用資訊增益、 5使用資訊增益率、CART使用基尼係數。CART演算法構建的一定是二叉樹,ID3和5構建的不一定是二叉樹。本文由 @SincerityY 原創釋出於人人都是產品經理。未經許可,禁止轉載

題圖來自Unsplash,基於CC0協議

Reference:科技日報

看更多!請加入我們的粉絲團

轉載請附文章網址

不可錯過的話題