決策樹（Decision Tree）是一種以樹形數(shù)據(jù)結(jié)構(gòu)來展示決策規(guī)則和分類結(jié)果的模型，它是將看似無序、雜亂的已知實(shí)例，通過某種技術(shù)手段將它們轉(zhuǎn)化成可以預(yù)測未知實(shí)例的樹狀模型。

時隔半月，已近年關(guān)。AI產(chǎn)品經(jīng)理必懂算法的第三篇終于來了，今天想和大家聊的是決策樹，閑言少敘，切入正題。

先上定義，決策樹（Decision Tree），又稱判斷樹，它是一種以樹形數(shù)據(jù)結(jié)構(gòu)來展示決策規(guī)則和分類結(jié)果的模型，作為一種歸納學(xué)習(xí)算法，其重點(diǎn)是將看似無序、雜亂的已知實(shí)例，通過某種技術(shù)手段將它們轉(zhuǎn)化成可以預(yù)測未知實(shí)例的樹狀模型，每一條從根結(jié)點(diǎn)（對最終分類結(jié)果貢獻(xiàn)最大的屬性）到葉子結(jié)點(diǎn)（最終分類結(jié)果）的路徑都代表一條決策的規(guī)則。

說完了拗口的定義，老規(guī)矩，我們還是用比較通俗易懂的例子，來講述決策樹算法的原理。

決策樹也是一種監(jiān)督學(xué)習(xí)的分類算法，要求輸入標(biāo)注好類別的訓(xùn)練樣本集，每個訓(xùn)練樣本由若干個用于分類的特征來表示。決策樹算法的訓(xùn)練目的在于構(gòu)建決策樹，希望能夠得到一顆可以將訓(xùn)練樣本按其類別進(jìn)行劃分的決策樹。

案例：假設(shè)現(xiàn)在我們想預(yù)測的是，女性到底想要嫁什么樣的人？我們現(xiàn)在手里擁有一些未婚男性的數(shù)據(jù)，其中包括了收入、房產(chǎn)、樣貌、學(xué)歷等字段。

提示：在構(gòu)建決策樹時，每次都要選擇區(qū)分度最高的特征，使用其特征值對數(shù)據(jù)進(jìn)行劃分，每次消耗一個特征，不斷迭代，直到所有特征均被使用為止。

• 如果還未使用全部特征，剩下的訓(xùn)練樣本就已經(jīng)具有相同類別了，則決策樹的構(gòu)建可以提前完成。
• 如果使用全部特征后，剩下的訓(xùn)練樣本中仍然包含一個以上的類別，則選擇剩下的訓(xùn)練樣本中占比最大的類別作為這批訓(xùn)練樣本的類別。

利用決策樹的思想，首先我們要考慮的是，上述哪些條件在女性選擇男友時最重要的考量指標(biāo)？好了，假設(shè)我就比較在意收入、比較在意物質(zhì)好了，那么我構(gòu)建的決策樹應(yīng)該是什么樣的呢？來張圖大家就明白了。

釋義：這張圖想表達(dá)的意思就是說，我們從如下幾個方面去判斷，是否要嫁？首先，看其收入是否達(dá)到1w元，未達(dá)標(biāo)的不嫁，從已經(jīng)合格的人群中繼續(xù)挑選，是否有房產(chǎn)，沒有的不行，以此類推，我們將所有的重要指標(biāo)都過濾一遍以后，就構(gòu)建出一個完整的決策樹了，在此之后，有任何男青年放在這兒，我們都能通過決策樹，輕松預(yù)測出，此人是否可嫁？

我們來出個題試試，某男，風(fēng)流倜儻、風(fēng)度翩翩，但是沒有獨(dú)立房產(chǎn)，收入不固定、學(xué)歷本科，那么到底要不要嫁呢？

圖中的收入、房產(chǎn)、學(xué)歷等都屬于特征，每一個特征都是一個判斷的節(jié)點(diǎn)，那些不可再向下延伸的就是葉子節(jié)點(diǎn)?？稍俜值姆Q之為分支節(jié)點(diǎn)。

接下來了解下決策樹算法的演進(jìn)歷史，這其中就包含了主流的幾種決策樹算法，順便我們也可以了解一下這幾種決策樹的差別。

1. ID3（Iterative Dichotomiser 3）

J.R.Quinlan在20世紀(jì)80年代提出了ID3算法，該算法奠定了日后決策樹算法發(fā)展的基礎(chǔ)。ID3采用香濃的信息熵來計算特征的區(qū)分度。選擇熵減少程度最大的特征來劃分?jǐn)?shù)據(jù)，也就是“最大信息熵增益”原則。它的核心思想是以信息增益作為分裂屬性選取的依據(jù)。

存在的缺陷：該算法未考慮如何處理連續(xù)屬性、屬性缺失以及噪聲等問題。

下面來介紹兩個與此有關(guān)的概念：

信息熵是一種信息的度量方式，表示信息的混亂程度，也就是說：信息越有序，信息熵越低。舉個列子：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。它的公式如下：

信息增益： 在劃分?jǐn)?shù)據(jù)集前后信息發(fā)生的變化稱為信息增益，信息增益越大，確定性越強(qiáng)。

2. C4.5

J.R.Quinlan針對ID3算法的不足設(shè)計了C4.5算法，引入信息增益率的概念。它克服了ID3算法無法處理屬性缺失和連續(xù)屬性的問題，并且引入了優(yōu)化決策樹的剪枝方法，使算法更高效，適用性更強(qiáng)。

后續(xù)，在1996年Mehta.M等人提出了C4.5算法的改進(jìn)算法SLIQ算法，該算法采用屬性表、分類表、類直方圖的策略來解決內(nèi)存溢出的問題。

同樣介紹一下信息增益率：在決策樹分類問題中，即就是決策樹在進(jìn)行屬性選擇劃分前和劃分后的信息差值。

3. CART（Classification and Regression Tree）

Breiman.L.I等人在1984年提出了CART算法，即分類回歸樹算法。CART算法用基尼指數(shù)（Gini Index）代替了信息熵，用二叉樹作為模型結(jié)構(gòu)，所以不是直接通過屬性值進(jìn)行數(shù)據(jù)劃分，該算法要在所有屬性中找出最佳的二元劃分。CART算法通過遞歸操作不斷地對決策屬性進(jìn)行劃分，同時利用驗(yàn)證數(shù)據(jù)對樹模型進(jìn)行優(yōu)化。

CART中用于選擇變量的不純性度量是Gini指數(shù)，總體內(nèi)包含的類別越雜亂，GINI指數(shù)就越大（跟熵的概念很相似）。

2000年Rastogi.R等人以CART算法為理論基礎(chǔ)，提出了PUBLIC（A Decision Tree Classifier that Integrates Building and Pruning）算法，剪枝策略更加高效。

當(dāng)我們了解了決策樹的大概情況之后，接下來就學(xué)習(xí)一下，如何構(gòu)造決策樹？

第一步：特征選擇；第二步：決策樹的生成；第三步：決策樹的剪枝。

我們來著重介紹一下剪枝。

剪枝的目的：決策樹是充分考慮了所有的數(shù)據(jù)點(diǎn)而生成的復(fù)雜樹，有可能出現(xiàn)過擬合的情況，決策樹越復(fù)雜，過擬合的程度會越高?？紤]極端的情況，如果我們令所有的葉子節(jié)點(diǎn)都只含有一個數(shù)據(jù)點(diǎn)，那么我們能夠保證所有的訓(xùn)練數(shù)據(jù)都能準(zhǔn)確分類，但是很有可能得到高的預(yù)測誤差，原因是將訓(xùn)練數(shù)據(jù)中所有的噪聲數(shù)據(jù)都”準(zhǔn)確劃分”了，強(qiáng)化了噪聲數(shù)據(jù)的作用。剪枝修剪分裂前后分類誤差相差不大的子樹，能夠降低決策樹的復(fù)雜度，降低過擬合出現(xiàn)的概率。

如何剪枝？

• 先剪枝：當(dāng)熵減少的數(shù)量小于某一個閾值時，就停止分支的創(chuàng)建。這是一種貪心算法。
• 后剪枝：先創(chuàng)建完整的決策樹，然后再嘗試消除多余的節(jié)點(diǎn)，也就是采用減枝的方法。

注意事項：

決策樹的生成對應(yīng)模型的局部選擇，決策樹的剪枝對應(yīng)于模型的全局選擇。決策樹的生成只考慮局部最優(yōu)，決策樹的剪枝則考慮全局最優(yōu)。

說了這么多，我們來總結(jié)一下決策樹算法的優(yōu)、缺點(diǎn)，以便了解的更為深入。

優(yōu)點(diǎn)：

1. 決策樹易于理解和實(shí)現(xiàn).人們在通過解釋后都有能力去理解決策樹所表達(dá)的意義。
2. 計算復(fù)雜度不高，輸出結(jié)果易于理解，數(shù)據(jù)缺失不敏感，可以處理不相關(guān)特征。

缺點(diǎn)：

1. 容易過擬合。
2. 對于各類別樣本數(shù)量不一致的數(shù)據(jù)，在決策樹當(dāng)中信息增益的結(jié)果偏向于那些具有更多數(shù)值的特征。

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

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