本文筆者將用具體例子講述決策樹的構(gòu)建過程，分析：決策樹生成過程中有什么樣的問題？

一、基本概念

決策樹的定義：

首先，決策樹是一種有監(jiān)督的分類算法——即給定X，Y值，構(gòu)建X，Y的映射關(guān)系。

不同于線性回歸等是多項(xiàng)式，決策樹是一種樹形的結(jié)構(gòu)，一般由根節(jié)點(diǎn)、父節(jié)點(diǎn)、子節(jié)點(diǎn)、葉子節(jié)點(diǎn)構(gòu)成如圖所示。

父節(jié)點(diǎn)和子節(jié)點(diǎn)是相對(duì)的，子節(jié)點(diǎn)可以由父節(jié)點(diǎn)分裂而來，而子節(jié)點(diǎn)還能作為新的父節(jié)點(diǎn)繼續(xù)分裂；根節(jié)點(diǎn)是沒有父節(jié)點(diǎn)，即初始分裂節(jié)點(diǎn)，葉子節(jié)點(diǎn)是沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，為終節(jié)點(diǎn)。

每一個(gè)分支代表著一個(gè)判斷，每個(gè)葉子節(jié)點(diǎn)代表一種結(jié)果。

這是在已知各種情況的發(fā)生的概率的基礎(chǔ)上，通過構(gòu)建決策樹來進(jìn)行分析的一種方式。

預(yù)測方式：

• 根據(jù)輸入的樣本X的特征屬性和決策樹的取值，將輸入的X樣本分配到某一個(gè)葉子節(jié)點(diǎn)中。
• 將葉子節(jié)點(diǎn)中出現(xiàn)最多的Y值，作為輸入的X樣本的預(yù)測類別。

目的：

最優(yōu)的模型應(yīng)該是：葉子節(jié)點(diǎn)中只包含一個(gè)類別的數(shù)據(jù)。

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

二、決策樹構(gòu)建過程

步驟一：將所有的特征看成一個(gè)一個(gè)的節(jié)點(diǎn)，eg（擁有房產(chǎn)、婚姻狀態(tài)、年收入這些特征，我們可以看成一個(gè)一個(gè)的節(jié)點(diǎn)。）

步驟二：遍歷當(dāng)前特征的每一種分割方式，找到最好的分割點(diǎn)eg（婚姻狀態(tài)這個(gè)特征，我們可以按照單身、已婚、離婚進(jìn)行劃分；也可以按照結(jié)過婚、沒有結(jié)過婚進(jìn)行劃分）；將數(shù)據(jù)劃分為不同的子節(jié)點(diǎn)，eg： N1、 N2….Nm；計(jì)算劃分之后所有子節(jié)點(diǎn)的“純度”信息

步驟三：使用第二步遍歷所有特征，選擇出最優(yōu)的特征，以及該特征的最優(yōu)的劃分方式，得出最終的子節(jié)點(diǎn)N1、 N2….Nm

步驟四：對(duì)子節(jié)點(diǎn)N1、N2….Nm分別繼續(xù)執(zhí)行2-3步，直到每個(gè)最終的子節(jié)點(diǎn)都足夠“純”。

從上述步驟可以看出，決策生成過程中有兩個(gè)重要的問題：

1. 對(duì)數(shù)據(jù)進(jìn)行分割。
2. 選擇分裂特征。
3. 什么時(shí)候停止分裂。

1. 對(duì)數(shù)據(jù)進(jìn)行分割

根據(jù)屬性值的類型進(jìn)行劃分：

如果值為離散型，且不生成二叉決策樹，則此時(shí)一個(gè)屬性就是可以一個(gè)分支，比如：上圖數(shù)據(jù)顯示，婚姻狀態(tài)為一個(gè)屬性，而下面有三個(gè)值，單身、已婚、離婚，則這三個(gè)值都可以作為一個(gè)分類。

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

如果值為連續(xù)性，可以確定一個(gè)值作為分裂點(diǎn)，按照大于分割點(diǎn)，小于或等于分割點(diǎn)生成兩個(gè)分支，如上圖數(shù)據(jù)，我可以按照6千元的點(diǎn)劃分成：大于6千元和小于6千元。

2. 找到最好的分裂特征

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

在某種意義上的局部最優(yōu)解，也就是說我只保證在當(dāng)分裂的時(shí)候，能夠保證數(shù)據(jù)最純就好。

對(duì)于整體的數(shù)據(jù)集而言：按照所有的特征屬性進(jìn)行劃分操作，對(duì)所有劃分操作的結(jié)果集的“純度”進(jìn)行比較，選擇“純度”越高的特征屬性作為當(dāng)前需要分割的數(shù)據(jù)集進(jìn)行分割操作。

決策樹使用信息增益作為選擇特征的依據(jù)，公式如下：

H（D）為：分割前的純度。

H（D｜A）為：在給定條件A下的純度，兩者之差為信息增益度。如果信息增益度越大，則H（D｜A）越小，則代表結(jié)果集的數(shù)據(jù)越純。

計(jì)算純度的度量方式：Gini、信息熵、錯(cuò)誤率。

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

Gini：

信息熵：

錯(cuò)誤率：

3. 什么時(shí)候停止分裂

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

1. 當(dāng)每個(gè)子節(jié)點(diǎn)只有一種類型的時(shí)候停止構(gòu)建。
2. 當(dāng)前節(jié)點(diǎn)中記錄數(shù)小于某個(gè)閾值，同時(shí)迭代次數(shù)達(dá)到給定值時(shí)，停止構(gòu)建過程。此時(shí)，使用 max(p(i))作為節(jié)點(diǎn)的對(duì)應(yīng)類型。

方式一可能會(huì)使樹的節(jié)點(diǎn)過多，導(dǎo)致過擬合(Overfiting)等問題。所以，比較常用的方式是使用方式二作為停止條件。

三、舉例

數(shù)據(jù)集如下：

1. 對(duì)數(shù)據(jù)特征進(jìn)行分割

• 擁有房產(chǎn)（是、否）
• 婚姻狀態(tài)（單身、已婚、離婚）
• 年收入（80、97.5）

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

首先，計(jì)算按照擁有房產(chǎn)這個(gè)特征進(jìn)行劃分的信息增益，使用錯(cuò)誤率進(jìn)行純度的計(jì)算：

計(jì)算原始數(shù)據(jù)的純度：

計(jì)算按擁有房產(chǎn)劃分后的結(jié)果集數(shù)據(jù)純度H（D｜A）：

H(D| X=有房產(chǎn)) 的計(jì)算方式：

H(D| X=無房產(chǎn)) 的計(jì)算方式：

計(jì)算信息增益度Gain(房產(chǎn))：

同理，可以計(jì)算：婚姻狀態(tài) 年收入=97.5

Gain(婚姻) = 0.205

Gain(婚姻) =0.395

按照Gain越大，分割后的純度越高，因此第一個(gè)分割屬性為收入，并按照97.5進(jìn)行劃分。

左子樹的結(jié)果集夠純，因此不需要繼續(xù)劃分。

接下來，對(duì)右子樹年收入大于97.5的數(shù)據(jù)，繼續(xù)選擇特征進(jìn)行劃分，且不再考慮收入這個(gè)特征，方法如上，可以得到如圖：

四、常見算法

ID3：

優(yōu)點(diǎn)：決策樹構(gòu)建速度快；實(shí)現(xiàn)簡單

缺點(diǎn)：

• 計(jì)算依賴于特征數(shù)目較多的特征，而屬性值最多的屬性并不一定最優(yōu) 。
• ID3算法不是遞增算法，ID3算法是單變量決策樹，對(duì)于特征屬性之間的關(guān)系不會(huì)考慮。
• 抗噪性差。
• 只適合小規(guī)模數(shù)據(jù)集，需要將數(shù)據(jù)放到內(nèi)存中。

C4.5：

在ID3算法的基礎(chǔ)上，進(jìn)行算法優(yōu)化提出的一種算法(C4.5)，使用信息增益率來取代ID3中的信息增益。

CART（Classification And Regression Tree）：

五、總結(jié)

1. ID3和5算法均只適合在小規(guī)模數(shù)據(jù)集上使用。
2. ID3和5算法都是單變量決策樹當(dāng)屬性值取值比較多的時(shí)候，最好考慮C4.5算法，ID3得出的效果會(huì)比較差? 決策樹分類一般情況只適合小數(shù)據(jù)量的情況(數(shù)據(jù)可以放內(nèi)存)? CART算法是三種算法中最常用的一種決策樹構(gòu)建算法(sklearn中僅支持CART)。
3. 三種算法的區(qū)別僅僅只是對(duì)于當(dāng)前樹的評(píng)價(jià)標(biāo)準(zhǔn)不同而已，ID3使用信息增益、 5使用信息增益率、CART使用基尼系數(shù)。
4. CART算法構(gòu)建的一定是二叉樹，ID3和5構(gòu)建的不一定是二叉樹。

本文由 @SincerityY 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來自Unsplash，基于CC0協(xié)議