本文關(guān)鍵詞：決策樹(shù)學(xué)習(xí)及其剪枝算法研究，由筆耕文化傳播整理發(fā)布。

第八章 決策樹(shù)算法

1、什么是決策樹(shù)？決策樹(shù)是一種類(lèi)似于流程圖的樹(shù)結(jié)構(gòu)。其中，每個(gè)內(nèi)部結(jié)點(diǎn)（非樹(shù)葉結(jié)點(diǎn)）表示在一個(gè)屬性上的測(cè)試，每個(gè)分枝代表該測(cè)試的一個(gè)輸出，而每個(gè)樹(shù)葉結(jié)點(diǎn)存放一個(gè)類(lèi)標(biāo)號(hào)。樹(shù)的最頂層結(jié)點(diǎn)是根節(jié)點(diǎn)。內(nèi)部結(jié)點(diǎn)用矩形表示，而葉結(jié)點(diǎn)用橢圓表示。決策樹(shù)可以是二叉的，也可以是非二叉的（根據(jù)不同的決策樹(shù)算法而定）。一棵典型的決策樹(shù)如下圖：

2、如何使用決策樹(shù)分類(lèi)？給定一個(gè)類(lèi)標(biāo)號(hào)未知的元組X，，在該決策樹(shù)上測(cè)試該元組的屬性值。跟蹤一條由根到葉結(jié)點(diǎn)的路徑，該葉結(jié)點(diǎn)就存放著該元組的類(lèi)預(yù)測(cè)。

3、為什么決策樹(shù)分類(lèi)器如此流行？（1）決策樹(shù)分類(lèi)器的構(gòu)造不需要任何領(lǐng)域知識(shí)或參數(shù)設(shè)置，因此適合于探測(cè)式知識(shí)發(fā)現(xiàn)。

（2）決策樹(shù)可以處理高維數(shù)據(jù)。

（3）獲取的知識(shí)用樹(shù)的形式表示是直觀(guān)的，并且容易被人理解。

（4）決策樹(shù)歸納的學(xué)習(xí)和分類(lèi)步驟是簡(jiǎn)單和快速的。

（5）一般而言，決策樹(shù)分類(lèi)器具有很好的準(zhǔn)確率。

4、決策樹(shù)算法屬性選擇度量：是一種選擇分裂準(zhǔn)則，把給定類(lèi)標(biāo)記的訓(xùn)練元組的數(shù)據(jù)分區(qū)D“最好地”劃分成單獨(dú)類(lèi)的啟發(fā)式方法。理想情況下，D劃分后的每個(gè)小分區(qū)都是純的（即落在一個(gè)給定分區(qū)的所有元組都屬于相同的類(lèi)）�！白詈玫摹狈诸�(lèi)準(zhǔn)則是最接近這種情況的劃分。

根據(jù)分裂屬性選擇度量的不同，決策樹(shù)的常見(jiàn)算法有ID3（度量：信息增益）、C4.5（度量：增益率）、CART（度量：基尼指數(shù)）。當(dāng)然，決策樹(shù)算法之間的差別也包括用于剪枝的機(jī)制等。

它們都采用貪心（即非回溯）的方法，其中決策樹(shù)以自頂向下遞歸的分治法構(gòu)造。大多數(shù)決策樹(shù)算法都沿用這種自頂向下方法，從訓(xùn)練元組集和它們相關(guān)聯(lián)的類(lèi)標(biāo)號(hào)開(kāi)始構(gòu)造決策樹(shù)。隨著樹(shù)的構(gòu)建，訓(xùn)練集遞歸地劃分成較小的子集。這些子集分布在第一個(gè)決策點(diǎn)的所有分支上。如果某個(gè)分支下的數(shù)據(jù)屬于同一類(lèi)型，則當(dāng)前已經(jīng)正確地劃分?jǐn)?shù)據(jù)分類(lèi)，無(wú)需進(jìn)一步對(duì)數(shù)據(jù)集進(jìn)行分割。如果數(shù)據(jù)子集內(nèi)的數(shù)據(jù)不屬于同一類(lèi)型，則需要重復(fù)劃分?jǐn)?shù)據(jù)子集的過(guò)程。如何劃分?jǐn)?shù)據(jù)子集的算法和劃分原始數(shù)據(jù)集的方法相同，直到所有具有相同類(lèi)型的數(shù)據(jù)均在一個(gè)數(shù)據(jù)子集內(nèi)。

基本決策樹(shù)算法概括在下圖中：

圖 由訓(xùn)練元組歸納決策樹(shù)的基本算法

遞歸的終止條件是：程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性，或者每個(gè)分支下的所有實(shí)例都具有相同的分類(lèi)。

4.1 ID3算法（信息增益）ID3算法（Iterative Dichotomiser3 迭代的二分器3代）是一位機(jī)器學(xué)習(xí)研究人員J.Ross Quinlan開(kāi)發(fā)的決策樹(shù)算法。

ID3算法的核心思想：以信息增益作為屬性選擇度量（該度量基于香農(nóng)在研究消息的值或“信息內(nèi)容”的信息論方面的先驅(qū)工作），選擇分裂后信息增益最大的屬性進(jìn)行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹(shù)空間。

思想：（1）自頂向下的貪婪搜索遍歷可能的決策樹(shù)空間構(gòu)造決策樹(shù)

（2）從“哪一個(gè)屬性將在樹(shù)的根節(jié)點(diǎn)被測(cè)試”開(kāi)始；

（3）使用統(tǒng)計(jì)測(cè)試來(lái)確定每一個(gè)實(shí)例屬性單獨(dú)分類(lèi)訓(xùn)練樣例的能力，分類(lèi)能力最好的屬性作為樹(shù)的根結(jié)點(diǎn)測(cè)試。

（4）然后為根結(jié)點(diǎn)屬性的每個(gè)可能值產(chǎn)生一個(gè)分支，并把訓(xùn)練樣例排列到適當(dāng)?shù)姆种Вㄒ簿褪钦f(shuō)，樣例的該屬性值對(duì)應(yīng)的分支）之下。

（5）重復(fù)這個(gè)過(guò)程，用每個(gè)分支結(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例來(lái)選取在該點(diǎn)被測(cè)試的最佳屬性。

信息增益：原來(lái)的信息需求（僅基于類(lèi)比例）與新的信息需求（對(duì)屬性A劃分后）之間的差。

Gain（A）告訴我們通過(guò)屬性A上的劃分我們得到了多少。選擇具有最高增益Gain（A）的屬性A作為分裂屬性。這等價(jià)于在“能做最佳分類(lèi)”的屬性A上劃分，使得完成 元組分類(lèi)還需要的信息最�。醋钚』疘nfoA（D））

對(duì)D中的元組分類(lèi)所需的期望信息由下式給出：

其中，pi是D中任意元組屬于類(lèi)Ci的非零概率，Info（D）又稱(chēng)為D的熵。

離散屬性A（具有v個(gè)不同的觀(guān)測(cè)值）對(duì)D進(jìn)行屬性劃分后所需要的期望信息：

需要的期望信息越小，分區(qū)的純度越高。

例子：顧客數(shù)據(jù)庫(kù)標(biāo)記類(lèi)的訓(xùn)練元組

首先，計(jì)算對(duì)D中元組分類(lèi)所需要的期望信息：

下一步，需要計(jì)算每個(gè)屬性的期望信息需求（先計(jì)算屬性age）。

類(lèi)似地，可以計(jì)算Gain（income）=0.029位 Gain（student）=0.151位 Gain（credit_rating）=0.048位。

由于age在屬性中具有最高的信息增益，所以它被選作分裂屬性。并且每個(gè)屬性值生長(zhǎng)出一個(gè)分枝，然后元組據(jù)此劃分。

其中，落在分區(qū)age=“middle_age”的元組都屬于相同的類(lèi)。由于它們都屬于類(lèi)“yes”，所以要在該分枝的端點(diǎn)創(chuàng)建一個(gè)樹(shù)葉，并用“yes”標(biāo)記。 算法返回的最終決策樹(shù) 如下圖：

這個(gè)決策樹(shù)只是一個(gè)屬性分裂后的決策樹(shù)，還需在每個(gè)分枝上遞歸地進(jìn)行屬性分裂（比如，在youth這個(gè)分枝上的剩下元組中，可以對(duì)student屬性進(jìn)行分裂，因?yàn)檫@樣分類(lèi)后信息增益最大，student是no（yes），class是no（yes））。

上面我們說(shuō)的分裂屬性都是離散值的，如果是連續(xù)值的我們?cè)趺从?jì)算它們的信息增益呢？假設(shè)屬性A是連續(xù)值的，而不是離散值的（例如，假定有屬性age的原始值，而不是該屬性的離散化版本。）對(duì)于這種情況，必須確定A的“最佳”分裂點(diǎn)，其中分裂點(diǎn)是A上的閾值。

首先，將A的值按遞增序排序。典型地，每對(duì)相鄰值的中點(diǎn)被看作可能的分裂點(diǎn)。這樣，給定A的v個(gè)值，則需要計(jì)算v-1個(gè)可能的劃分。對(duì)于A的每個(gè)可能的分裂點(diǎn)，計(jì)算Info（D），其中分區(qū)的個(gè)數(shù)為2，A具有最小期望信息需求的點(diǎn)選作A的分裂點(diǎn)。D1是滿(mǎn)足A<=split_poin的元組集合，而D2是滿(mǎn)足A>split_poin的元組集合。這樣的話(huà)，就轉(zhuǎn)換成離散屬性的計(jì)算了。

在此，順便介紹一下，根據(jù)屬性分裂準(zhǔn)則劃分元組的三種可能性：

4.2 C4.5算法（增益率） ID3的缺點(diǎn)：信息增益度量偏向具有許多輸出的測(cè)試。換句話(huà)說(shuō)，它傾向于選擇具有大量值的屬性。例如，考慮充當(dāng)唯一標(biāo)識(shí)符的屬性，如product_ID。在product_ID的劃分將導(dǎo)致大量分區(qū)（與值一樣多），每個(gè)只包含一個(gè)元組。由于每個(gè)分區(qū)都是純的，所以基于該劃分對(duì)數(shù)據(jù)集D分類(lèi)所需要的信息為Infoproduct_ID(D)=0。因此，通過(guò)對(duì)該屬性的劃分得到的信息增益最大。顯然，這種劃分對(duì)分類(lèi)沒(méi)有用。C4.5的出現(xiàn)就是為了克服這種偏倚。

C4.5：也是Quinlan提出來(lái)的，它是對(duì)ID3算法的改進(jìn)，這些改進(jìn)包括處理數(shù)值屬性、缺失值、噪聲數(shù)據(jù)和由決策樹(shù)產(chǎn)生規(guī)則的方法。C4.5采用增益率作為屬性選擇度量，增益率定義為：

選擇具有最大增益率的屬性作為分裂屬性。然而需要注意的是，隨著劃分信息趨向于0，該比率變得不穩(wěn)定。為了避免這種情況，增加一個(gè)約束：選取的測(cè)試的信息增益必須較大，至少與考察的所有測(cè)試的平均增益一樣大。比如我們可以先計(jì)算每個(gè)屬性的增益，然后僅對(duì)那些增益高過(guò)平均值的屬性應(yīng)用增益率測(cè)試。

其中，分裂信息度量被定義為(分裂信息用來(lái)衡量屬性分裂數(shù)據(jù)的廣度和均勻)：

例子：

事務(wù)數(shù)據(jù)庫(kù)中屬性income的增益率的計(jì)算：

4.3 CART算法（基尼指數(shù)）CART：分類(lèi)和回歸樹(shù)（ClassificationAnd Regression Tree）算法由Breiman等人于1984年提出的。它是以二叉樹(shù)的形式給出，易于理解、使用和解釋。如果目標(biāo)變量是離散的，則該樹(shù)為分類(lèi)樹(shù)（classification tree），而對(duì)于連續(xù)數(shù)值目標(biāo)變量，則該樹(shù)稱(chēng)為回歸樹(shù)（regression

tree）。

Gini指數(shù)：是一種不等性度量，由意大利統(tǒng)計(jì)學(xué)家Corrado Gini提出，并于1912年發(fā)表在他的文章“Variabilita e mutabilita”中。它通常用來(lái)度量收入不平衡，但是它可以用來(lái)度量任何不均勻分布。Gini指數(shù)是一個(gè)0—1之間的數(shù)。其中0對(duì)應(yīng)于完全相等（其中每個(gè)人都具有相同的收入），而1對(duì)應(yīng)于完全不相等（其中一個(gè)人具有所有收入，而其他人收入都為零）�；�尼指數(shù)度量數(shù)據(jù)分區(qū)或訓(xùn)練元組集D的不純度，定義為：

其中pi是D中元組屬于Ci類(lèi)的概率，對(duì)m個(gè)類(lèi)計(jì)算和。

基尼指數(shù)考慮每個(gè)屬性的二元?jiǎng)澐帧?/p>

（1）首先考慮A是離散值屬性的情況，其中A具有v個(gè)不同值出現(xiàn)在D中。如果A具有v個(gè)可能的值，則存在2v個(gè)可能的子集。例如，如果income具有3個(gè)可能的值{low,medium,high}，則可能的子集具有8個(gè)。不考慮冪集（{

low,medium,high}）和空集（{ }），因?yàn)閺母拍钌现v，它不代表任何分裂。因此，基于A的二元?jiǎng)澐�，存�?v -2中形成數(shù)據(jù)集D的兩個(gè)分區(qū)的可能方法。

當(dāng)考慮二元?jiǎng)澐至褧r(shí)，計(jì)算每個(gè)結(jié)果分區(qū)的不純度的加權(quán)和。例如，如果A的二元?jiǎng)澐謱劃分成D1和D2，則給定該劃分，D的基尼指數(shù)為

選擇該屬性產(chǎn)生最小基尼指數(shù)的子集作為它的分裂子集。

（2）對(duì)于連續(xù)值屬性，其策略類(lèi)似于上面介紹的信息增益所使用的策略。

對(duì)于離散或連續(xù)值屬性A的二元?jiǎng)澐謱?dǎo)致的不純度降低為

最大化不純度降低（或等價(jià)地，具有最小基尼指數(shù)）的屬性選為分裂屬性。該屬性和它的分裂子集（對(duì)于離散值的分裂屬性）或分裂點(diǎn)（對(duì)于連續(xù)值的分裂屬性）一起 形成分裂準(zhǔn)則。

例子：繼續(xù)使用“顧客數(shù)據(jù)庫(kù)”進(jìn)行介紹。

（1）計(jì)算D的不純度：

（2）為了找出D中元組的分裂準(zhǔn)則，需要計(jì)算每個(gè)屬性的基尼指數(shù)。從屬性income開(kāi)始，并考慮每個(gè)可能的分裂子集�？紤]子集{low，medium}，基于該劃分計(jì)算出的基尼指數(shù)為：

類(lèi)似地，其余子集劃分的基尼指數(shù)值是：0.458（子集{low，high}和{medium}）和0.450（子集{medium，high}和{low}）。因此，屬性income的最好劃分在{low，medium}（或{high}） 上，因?yàn)樗钚』?#23612;指數(shù)。

評(píng)估屬性age，得到{youth，senior}（或{middle_aged}）為age的最好劃分，具有基尼指數(shù)0.357；

屬性student和credit_rating都是二元的，分別具有基尼指數(shù)值0.367和0.429。

（3）屬性age和分裂子集{youth，senior}產(chǎn)生最小的基尼指數(shù)。二元?jiǎng)澐帧癮ge屬于{youth，senior}？”導(dǎo)致D中元組的不純度降低最大，并返回作為分裂準(zhǔn)則。從它生長(zhǎng)出兩個(gè)分枝，并且相應(yīng)地劃分元組。5、決策樹(shù)算法之間的比較

信息增益偏向于多值屬性。盡管增益率調(diào)整了這種偏倚，但是它傾向于產(chǎn)生不平衡的劃分，其中一個(gè)分區(qū)比其他分區(qū)小得多�；�尼指數(shù)偏向于多值屬性，并且當(dāng)類(lèi)的數(shù)量很大時(shí)會(huì)有困難。它還傾向于導(dǎo)致相等大小的分區(qū)和純度。盡管是有偏的，但是這些度量在實(shí)踐中產(chǎn)生相當(dāng)好的結(jié)果。6、樹(shù)剪枝

決策樹(shù)為什么要剪枝？原因是避免決策樹(shù)過(guò)擬合(Overfitting)樣本。前面的算法生成的決策樹(shù)非常詳細(xì)并且龐大，每個(gè)屬性都被詳細(xì)地加以考慮，決策樹(shù)的樹(shù)葉節(jié)點(diǎn)所覆蓋的訓(xùn)練樣本都是“純”的。因此用這個(gè)決策樹(shù)來(lái)對(duì)訓(xùn)練樣本進(jìn)行分類(lèi)的話(huà)，你會(huì)發(fā)現(xiàn)對(duì)于訓(xùn)練樣本而言，這個(gè)樹(shù)表現(xiàn)完好，誤差率極低且能夠正確得對(duì)訓(xùn)練樣本集中的樣本進(jìn)行分類(lèi)。訓(xùn)練樣本中的錯(cuò)誤數(shù)據(jù)也會(huì)被決策樹(shù)學(xué)習(xí)，成為決策樹(shù)的部分，但是對(duì)于測(cè)試數(shù)據(jù)的表現(xiàn)就沒(méi)有想象的那么好，或者極差，這就是所謂的過(guò)擬合(Overfitting)問(wèn)題。

“如何進(jìn)行剪枝？”有兩種常用的剪枝方法：先剪枝和后剪枝先剪枝：通過(guò)提前停止樹(shù)的構(gòu)建（例如，通過(guò)決定在給定的節(jié)點(diǎn)不再分裂或劃分訓(xùn)練元組的子集）而對(duì)樹(shù)“剪枝”。一旦停止，結(jié)點(diǎn)就成為樹(shù)葉。該樹(shù)葉可以持有子集元組中最頻繁的類(lèi)，或這些元組的概率分布。

在構(gòu)造樹(shù)時(shí)，可以使用諸如統(tǒng)計(jì)顯著性、信息增益、基尼指數(shù)等度量來(lái)評(píng)估劃分的優(yōu)劣。如果劃分一個(gè)結(jié)點(diǎn)的元組導(dǎo)致低于預(yù)定義閾值的劃分，則給定子集的進(jìn)一步劃分將停止。然而，選取一個(gè)適當(dāng)?shù)拈?#20540;是困難的。高閾值可能導(dǎo)致過(guò)分簡(jiǎn)化的樹(shù)，而低閾值可能使得樹(shù)的簡(jiǎn)化太少。

例子：限定樹(shù)的最大生長(zhǎng)高度為3

后剪枝：它由“完全生長(zhǎng)”的樹(shù)剪去子樹(shù)。通過(guò)刪除節(jié)點(diǎn)的分枝并用樹(shù)葉替換它而剪掉給定結(jié)點(diǎn)上的子樹(shù)。該樹(shù)葉的類(lèi)標(biāo)號(hào)用子樹(shù)中最頻繁的類(lèi)標(biāo)記。

例子：

決策樹(shù)算法用的是什么剪枝？

CART使用的是：代價(jià)復(fù)雜度（后剪枝方法的一種實(shí)例）剪枝算法。

該方法把樹(shù)的復(fù)雜度看作樹(shù)中樹(shù)葉結(jié)點(diǎn)的個(gè)數(shù)和樹(shù)的錯(cuò)誤率的函數(shù)（其中，錯(cuò)誤率是樹(shù)誤分類(lèi)的元組所占的百分比）。它從樹(shù)的底部開(kāi)始。對(duì)于每個(gè)內(nèi)部結(jié)點(diǎn)N，計(jì)算N的子樹(shù)的代價(jià)復(fù)雜度和該子樹(shù)剪枝后N的子樹(shù)（即用一個(gè)樹(shù)葉節(jié)點(diǎn)替換）的代價(jià)復(fù)雜度，比較這兩個(gè)值。如果剪去結(jié)點(diǎn)N的子樹(shù)導(dǎo)致較小的代價(jià)復(fù)雜度，則剪掉該子樹(shù)；否則，保留該子樹(shù)。

C4.5使用的是：悲觀(guān)剪枝。它類(lèi)似于代價(jià)復(fù)雜度方法，因?yàn)樗彩褂缅e(cuò)誤率評(píng)估，對(duì)子樹(shù)剪枝做出決定。

剪枝后還可能存在什么困擾？另外，對(duì)于組合方法，先剪枝和后剪枝可以交叉使用。后剪枝所需要的計(jì)算比先剪枝多，但是通常產(chǎn)生更可靠的樹(shù)。

盡管剪枝后的樹(shù)一般比未剪枝的樹(shù)更緊湊，但是他們?nèi)匀豢赡芎艽蟆⒑軓?fù)雜。決策樹(shù)可能受到重復(fù)和復(fù)制的困擾，使得他們很難解釋。

沿著一條給定的分枝反復(fù)測(cè)試一個(gè)屬性時(shí)就會(huì)出現(xiàn)重復(fù)。復(fù)制是樹(shù)中存在重復(fù)的子樹(shù)。這些情況影響了決策樹(shù)的準(zhǔn)確率和可解釋性。

解決辦法：（1）使用多元?jiǎng)澐郑ɑ诮M合屬性的劃分）（2）使用不同形式的知識(shí)表示（如規(guī)則），而不是決策樹(shù)。

更多關(guān)于剪枝的內(nèi)容（特別是代價(jià)復(fù)雜度剪枝和悲觀(guān)剪枝），可以參考文獻(xiàn)：

決策樹(shù)分類(lèi)及剪枝算法研究_張宇（哈爾濱理工大學(xué)）

決策樹(shù)學(xué)習(xí)及其剪枝算法研究_王黎明（武漢理工大學(xué)）

7、可伸縮性與決策樹(shù)歸納（后期續(xù)寫(xiě)）

猜你在找

  本文關(guān)鍵詞：決策樹(shù)學(xué)習(xí)及其剪枝算法研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：243486