簡(jiǎn)單問(wèn)題引入

如何判斷今天是什么季節(jié)？春天、夏天、秋天、冬天？

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)公司！專(zhuān)注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、成都微信小程序、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶(hù)創(chuàng)新互聯(lián)還提供了任丘免費(fèi)建站歡迎大家使用！

如果是我們的話(huà)，可以通過(guò)日期一下子知道今天的季節(jié)——“7月份，所以是夏天！”大概是這樣的發(fā)言。

但如果不讓你通過(guò)日期來(lái)判斷呢？選擇還是很多的，比如說(shuō)根據(jù)氣溫來(lái)判斷或許也可行？如果今天天氣非常非常冷，我可以認(rèn)為，這一定是冬天；今天天氣太熱了，一定需要一根雪糕來(lái)解暑的程度，這一定是夏天；天氣適宜的時(shí)候，難辦了——可能是春天，可能是夏天，這個(gè)時(shí)候我們可以看看窗外，窗外的樹(shù)上的葉子越來(lái)越多了，向著枝繁葉茂發(fā)展，那一定是春天；如果葉子越來(lái)越少，不斷凋零，那想必一定是秋天。

我們來(lái)對(duì)這個(gè)不允許使用時(shí)間的判斷方法進(jìn)行解讀。

我們發(fā)現(xiàn)，我們一共利用了周遭環(huán)境的兩個(gè)屬性：一是氣溫，氣溫有很高、很低和適宜三種情況；二是樹(shù)葉生長(zhǎng)情況，有不斷生長(zhǎng)和不斷凋零兩種狀態(tài)。

我們可以通過(guò)這個(gè)判斷方法畫(huà)出如下的一個(gè)判斷機(jī)制。

不難發(fā)現(xiàn)，這是一個(gè)樹(shù)形結(jié)構(gòu)。繼續(xù)觀(guān)察的話(huà)，可以發(fā)現(xiàn)更多的性質(zhì)：

1. 所有的葉子結(jié)點(diǎn)都是我們的選項(xiàng)
2. 所有的非葉子結(jié)點(diǎn)都是一個(gè)對(duì)屬性的判斷（氣溫和樹(shù)葉長(zhǎng)落，這是我們剛剛對(duì)周遭環(huán)境分析出來(lái)的兩個(gè)屬性）
3. 每一條邊都是一個(gè)屬性的判斷，一個(gè)非葉子結(jié)點(diǎn)向各個(gè)子節(jié)點(diǎn)連接的邊表示了對(duì)這個(gè)非葉子結(jié)點(diǎn)所討論的屬性的各種可能的情況。

這一棵樹(shù)生動(dòng)形象地將我們的判斷過(guò)程表現(xiàn)了出來(lái)，從根節(jié)點(diǎn)不斷進(jìn)行判斷可以一路走到葉子結(jié)點(diǎn)，從而得到我們所求的答案。這棵樹(shù)就是一棵決策樹(shù)。

如果我們把這樣的一棵樹(shù)丟給計(jì)算機(jī)，當(dāng)我們想知道今天屬于什么季節(jié)的時(shí)候，把今天的氣溫、樹(shù)葉長(zhǎng)落的兩個(gè)屬性的屬性值告訴這臺(tái)計(jì)算機(jī)，計(jì)算機(jī)從根節(jié)點(diǎn)就可以一路走向葉子結(jié)點(diǎn)，從而告訴我們今天是春天、夏天、秋天，還是冬天。

這就是一棵決策樹(shù)在做的事。

我們?cè)谟?xùn)練模型的過(guò)程中對(duì)決策樹(shù)有兩種操作：一種是構(gòu)造決策樹(shù)，一種是利用決策樹(shù)將所給的測(cè)試數(shù)據(jù)進(jìn)行判斷。

構(gòu)建決策樹(shù)簡(jiǎn)介

在訓(xùn)練模型的過(guò)程中，我們要通過(guò)所給的測(cè)試數(shù)據(jù)進(jìn)行決策樹(shù)的搭建。已知有 x x x個(gè)屬性，利用決策樹(shù)進(jìn)行類(lèi)別判斷的時(shí)候，我們本質(zhì)上是分別判斷這 x x x個(gè)屬性分別是什么來(lái)把類(lèi)別看出來(lái)。為了提高分類(lèi)的效率，我們希望可以盡可能早地排除盡可能多的錯(cuò)誤選項(xiàng)。

還是拿上圖的決策樹(shù)舉例，判斷季節(jié)我們用了兩個(gè)屬性，第一次判斷，我們通過(guò)氣溫是很低、很高、適宜，將四個(gè)季節(jié)分為了三類(lèi)；第二次判斷利用了樹(shù)葉的長(zhǎng)落情況，區(qū)分了氣溫適宜的兩個(gè)季節(jié)。

從判斷的順序來(lái)看，我們的順序是先判斷氣溫，后判斷樹(shù)葉長(zhǎng)落。

或許我們可以反過(guò)來(lái)？是不是也可以先判斷樹(shù)葉長(zhǎng)落，后判斷氣溫呢？如果我們先判斷樹(shù)葉長(zhǎng)落，那么決策樹(shù)大概是這個(gè)樣子：

看上去也是一種可行的方案。

不妨觀(guān)察和最開(kāi)始的那一棵決策樹(shù)相比有什么區(qū)別。

1. 無(wú)論是春夏秋冬哪一個(gè)季節(jié)，第二種決策樹(shù)都要進(jìn)行所有屬性的判斷，而第一種決策樹(shù)，如果氣溫很高或很低，我們可以只需要對(duì)氣溫的判斷就能知道季節(jié)。
2. 對(duì)于第二種決策樹(shù)，在作為第二個(gè)屬性進(jìn)行判斷的氣溫屬性，對(duì)應(yīng)不同的樹(shù)葉張落情況，其值域不太相同，當(dāng)樹(shù)葉生長(zhǎng)時(shí)，氣溫的情況為適宜、很高；當(dāng)樹(shù)葉枯落時(shí)，氣溫的情況為適宜、很低。

從我們前面提到的需求來(lái)看（盡可能早地排除盡可能多的錯(cuò)誤選項(xiàng)），第一個(gè)決策樹(shù)會(huì)更好一些。

從決策樹(shù)的應(yīng)用角度考慮會(huì)更加清晰：通常使用決策樹(shù)時(shí)都會(huì)給一組關(guān)于各個(gè)屬性的數(shù)據(jù)，站在根節(jié)點(diǎn)上的時(shí)候，我們可選的選項(xiàng)為所有的選項(xiàng)，每當(dāng)我們進(jìn)行判斷時(shí)，我們希望當(dāng)前可選的選項(xiàng)要變得盡可能小。

從決策樹(shù)的構(gòu)建角度來(lái)看：通常我們會(huì)通過(guò)給定的很多很多組關(guān)于各個(gè)屬性的數(shù)據(jù)（帶有最終的選項(xiàng)的答案）去訓(xùn)練出一棵決策樹(shù)，我們?nèi)绾芜x定當(dāng)前應(yīng)該先進(jìn)行哪一個(gè)屬性的判斷，使得我判斷完之后，分類(lèi)的效果最好，即對(duì)于這個(gè)屬性的每一個(gè)可選值，其篩選出來(lái)的所有組數(shù)據(jù)的最終選項(xiàng)最傾向于統(tǒng)一。

什么叫最傾向于統(tǒng)一呢？還是以判斷四季的情景為例，比如說(shuō)訓(xùn)練決策樹(shù)的過(guò)程中，我通過(guò)氣溫進(jìn)行當(dāng)前情況下的下一次判斷，分類(lèi)出來(lái)所有測(cè)試集數(shù)據(jù)選項(xiàng)如下：

觀(guān)察到，很低和很高把最后的結(jié)果分成大部分為冬和全部為夏，全部為夏是最理想的，因?yàn)檫@完全起到了分類(lèi)的效果，很多個(gè)冬里混了一個(gè)秋也還算不錯(cuò)，因?yàn)槲覀円材艽篌w看出他應(yīng)該是什么。氣溫適宜這個(gè)里面，一半是春，一半是秋，就有點(diǎn)混亂，不知道是春還是秋了。

這樣，對(duì)于先進(jìn)行氣溫屬性的判斷，最后的分類(lèi)是否統(tǒng)一，就看很低、適宜、很高分類(lèi)后的選項(xiàng)綜合到一起是否傾向于統(tǒng)一。也就是說(shuō)，要看氣溫屬性的判斷結(jié)果是不是統(tǒng)一，要綜合看很低、適宜、很高的分類(lèi)里面選項(xiàng)是否傾向于都是同一個(gè)選項(xiàng)。我們喜歡的就是傾向于同一個(gè)選項(xiàng)的，因?yàn)檫@符合盡可能早地排除盡可能多的錯(cuò)誤選項(xiàng)的思想。

對(duì)于每一個(gè)非葉子結(jié)點(diǎn)，我們把所有當(dāng)前還沒(méi)有判斷的屬性的這樣的是否統(tǒng)一的度量比較一下，選擇一個(gè)最統(tǒng)一的屬性作為當(dāng)前情況的下一個(gè)判斷的屬性。

于是自然而然地引出了訓(xùn)練決策樹(shù)的方法：我們通過(guò)訓(xùn)練集，從根節(jié)點(diǎn)開(kāi)始構(gòu)造。根節(jié)點(diǎn)處選擇一個(gè)分類(lèi)后最傾向于統(tǒng)一的屬性，然后按照可選值域進(jìn)行向下擴(kuò)展，對(duì)于每一個(gè)子樹(shù)的根節(jié)點(diǎn)，繼續(xù)用同樣的方法找出還沒(méi)有判斷過(guò)的屬性中最傾向于統(tǒng)一的屬性，把那個(gè)屬性作為這個(gè)節(jié)點(diǎn)的判斷屬性。以此類(lèi)推直到每一個(gè)分支都分出唯一的選項(xiàng)。

我們這里采用的是一個(gè)“統(tǒng)一”的定性的分析，但是在實(shí)現(xiàn)過(guò)程中，我們需要一個(gè)定量操作來(lái)判斷他的“統(tǒng)一”性，于是引入了熵的概念。

熵

大學(xué)物理中在熱力學(xué)章節(jié)里學(xué)過(guò)熵這個(gè)概念，大體上是描述一個(gè)狀態(tài)是否穩(wěn)定。我們經(jīng)常聽(tīng)到一個(gè)詞叫做“熵增”，就是描述一個(gè)過(guò)程變得更加不穩(wěn)定，或者更加混亂。

在決策樹(shù)中也有熵這一概念。我們用熵來(lái)表示當(dāng)前分類(lèi)的混亂程度（這和熵原本的含義是相近的）。

熵是表示隨機(jī)變量不確定性的度量。換句話(huà)說(shuō)，就是當(dāng)前物體內(nèi)部的混亂程度。

設(shè) H ( x ) H(x) H(x)表示 x x x狀態(tài)的熵，那么有公式

H ( x ) = ? ∑ i = 1 n p i × log ? 2 p i H(x)=-\displaystyle\sum\limits_{i=1}^n p_i\times \log_2 p_i H(x)=?i=1∑n?pi?×log2?pi?

p i p_i pi?表示 x x x狀態(tài)中某一個(gè)選項(xiàng)出現(xiàn)的概率（或許頻率這個(gè)詞更好？）。

我們通常都用以 2 2 2為底的 log ? \log log來(lái)算，但有少數(shù)情況也可以采用其他的底數(shù)，比如說(shuō)差值太小太小，精度要求太高之類(lèi)的情況。

熵是一個(gè)表示混亂程度的變量，也就是說(shuō)我們希望熵本身越小越好。

引入熵的概念之后，我們可以通過(guò)熵來(lái)定量地觀(guān)察接下來(lái)判斷哪一個(gè)屬性會(huì)使熵最小，每一個(gè)屬性都計(jì)算出一個(gè)熵，選擇一個(gè)熵最小的屬性，用于下一個(gè)判斷。

借用該視頻中的一個(gè)例子，來(lái)看如何通過(guò)熵來(lái)構(gòu)建一棵決策樹(shù)。

例：給定14天的天氣、溫度、濕度、風(fēng)的強(qiáng)度以及當(dāng)天是否打球的數(shù)據(jù)，目標(biāo)是構(gòu)造一棵決策樹(shù)。

不難發(fā)現(xiàn)，這個(gè)列表中，outlook、temperature、humidity、windy是自變量，play是因變量。換句話(huà)說(shuō)，前四個(gè)是屬性，最后一個(gè)是選項(xiàng)，選項(xiàng)有兩種，分別是no和yes。

構(gòu)造決策樹(shù)，相當(dāng)于考察各個(gè)屬性之間的判斷順序。我們需要通過(guò)這些數(shù)據(jù)集來(lái)判斷先進(jìn)行哪一個(gè)屬性的分類(lèi)會(huì)使整體的熵最小。想看誰(shuí)的熵最小，就需要對(duì)于每一個(gè)屬性都假設(shè)其為第一個(gè)進(jìn)行分類(lèi)的屬性，然后計(jì)算分類(lèi)后的熵，再看看哪一個(gè)可以使當(dāng)前熵下降的最多（和看哪一個(gè)的熵最小沒(méi)有什么區(qū)別）。

4種屬性的熵值計(jì)算方法相同，僅以outlook屬性為例。以outlook屬性為根節(jié)點(diǎn)處的分類(lèi)屬性后，大概分成了這個(gè)樣子：

首先，我們計(jì)算一下選定第一個(gè)分類(lèi)的屬性之前的熵值。根據(jù)數(shù)據(jù)，數(shù)據(jù)集中有9天在打球，5天沒(méi)有打球。此時(shí)的熵套入公式，為：

? 9 14 log ? 2 9 14 ? 5 14 log ? 2 5 14 = 0.940 -\frac{9}{14}\log_2 \frac{9}{14}-\frac{5}{14}\log_2 \frac{5}{14}=0.940 ?149?log2?149??145?log2?145?=0.940

其中， 9 14 \frac{9}{14} 149?為打球的概率， 5 14 \frac{5}{14} 145?為不打球的概率。這兩個(gè)數(shù)都是公式中 p i p_i pi?中的取值。

接下來(lái)看sunny中有5天的數(shù)據(jù)記錄，其中有2天打球，3天不打球，求得sunny情況下的熵為
? 2 5 log ? 2 2 5 ? 3 5 log ? 2 3 5 = 0.971 -\frac{2}{5}\log_2 \frac{2}{5}-\frac{3}{5}\log_2 \frac{3}{5}=0.971 ?52?log2?52??53?log2?53?=0.971

rainy中有5天的數(shù)據(jù)記錄，其中有3天打球，2天不打球，求得rainy情況下的熵為（不難看出其實(shí)和sunny一樣）
? 3 5 log ? 2 3 5 ? 2 5 log ? 2 2 5 = 0.971 -\frac{3}{5}\log_2 \frac{3}{5}-\frac{2}{5}\log_2 \frac{2}{5}=0.971 ?53?log2?53??52?log2?52?=0.971

overcast中有4天的數(shù)據(jù)記錄，其中有4天打球，0天不打球，是最理想的統(tǒng)一狀態(tài)，期望熵為0，但還是套一下公式看一看：
? 1 log ? 2 1 = 0 -1\log_2 1=0 ?1log2?1=0

現(xiàn)在，outlook中的每一個(gè)取值中的熵算好了，現(xiàn)在要統(tǒng)合這三種情況的熵，將他們合為一個(gè)整體。具體的做法是，把三個(gè)熵按照其中數(shù)據(jù)集的大小加權(quán)起來(lái)求一個(gè)平均數(shù)。

換句話(huà)說(shuō)，sunny在14組數(shù)據(jù)中出現(xiàn)了5次，權(quán)值就是\frac{5}{14}；rainy在14組數(shù)據(jù)中出現(xiàn)了5次，權(quán)值就是\frac{5}{14}；overcast在14組數(shù)據(jù)中出現(xiàn)了4次，權(quán)值就是\frac{4}{14}=\frac{2}{7}。

求得熵為加權(quán)平均數(shù)：
0.971 × 5 14 + 0.971 × 5 14 + 0 × 2 7 = 0.693 0.971\times \frac{5}{14}+0.971\times \frac{5}{14}+0\times \frac{2}{7}=0.693 0.971×145?+0.971×145?+0×72?=0.693

那么這樣分類(lèi)之后，整體系統(tǒng)的熵值從原來(lái)的0.940下降至了0.693，變化量是0.247。

這里引入一個(gè)新的概念信息增益。不難看出，我們期待熵值下降，而且分類(lèi)后熵值確實(shí)是下降，其下降的量是期待的數(shù)值，對(duì)我們來(lái)說(shuō)屬于一種增益，所以這個(gè)0.247就是這里的信息增益。

用同樣的方式計(jì)算temperature、humidity、windy三個(gè)屬性在作為第一次分類(lèi)屬性后系統(tǒng)的熵值，然后分別求得信息增益。

計(jì)算后求得，temperature分類(lèi)后信息增益為0.029，humidity為0.152，windy為0.048。

不難看出，按照outlook屬性作為第一次分類(lèi)的屬性，把outlook的分類(lèi)放在根節(jié)點(diǎn)上，對(duì)系統(tǒng)而言是最優(yōu)的。所以我們就把根節(jié)點(diǎn)設(shè)置為按照outlook分類(lèi)。

那么接下來(lái)將問(wèn)題分散到從根節(jié)點(diǎn)出發(fā)到sunny、rainy、overcast三棵子樹(shù)上的子問(wèn)題了。對(duì)于這些子問(wèn)題，再分別計(jì)算temperature、humidity、windy三個(gè)屬性給他們各自帶來(lái)的信息增益，然后取那個(gè)信息增益大的屬性，作為這個(gè)子樹(shù)里下一個(gè)要分類(lèi)的屬性。對(duì)于每一個(gè)子樹(shù)，我們只嘗試其祖先還沒(méi)有進(jìn)行分類(lèi)的屬性。這樣以此類(lèi)推，就可以建好整棵決策樹(shù)。

常見(jiàn)構(gòu)建方法

較為常見(jiàn)的三種決策樹(shù)構(gòu)建方法分別是ID3、C4.5、CART。（看不懂的算法名字）

ID3與C4.5(信息增益與信息增益率)

我們上面提到的決策樹(shù)構(gòu)建方法就是ID3，但是事實(shí)上由于存在一些問(wèn)題，所以現(xiàn)在用的非常少了。我們?cè)谏厦娴睦又杏玫降乃膫€(gè)屬性和打不打球這件事關(guān)系都比較大，但是如果我們的測(cè)試數(shù)據(jù)集中如果出現(xiàn)了一個(gè)和打球關(guān)系不大的屬性，再次引用視頻中的例子，如果此刻我們的數(shù)據(jù)集中出現(xiàn)了一個(gè)新的屬性——ID，即給每一天都加一個(gè)編號(hào)，從1到14編好，然后再跑一次ID3，就會(huì)發(fā)現(xiàn)，由于這個(gè)屬性每一條數(shù)據(jù)都各不相同，會(huì)發(fā)現(xiàn)分類(lèi)后會(huì)變成這個(gè)樣子：

會(huì)發(fā)現(xiàn)，分完類(lèi)后，ID屬性的每一個(gè)取值，都只能取到其中一條數(shù)據(jù)，套入熵的公式不難發(fā)現(xiàn)，當(dāng)前系統(tǒng)整體熵值為 0 0 0，這個(gè)屬性一定是最優(yōu)的，于是按照ID3的步驟，現(xiàn)在的情況下，下一個(gè)要判斷分類(lèi)的就是ID這個(gè)屬性了。

但是……ID這個(gè)屬性，和打球真的有什么關(guān)系嗎？答案顯然是沒(méi)有，這一步判斷是多余的、無(wú)用的。試想我們拿著這個(gè)決策樹(shù)去實(shí)際判斷是否該打球，這樣就變成了只看ID就來(lái)判斷能否打球了。這是不合理的。總結(jié)就是，由于屬性原因?qū)е滦畔⒃鲆娣浅Ｖ?，但這個(gè)屬性并不是我們需要的屬性，這說(shuō)明信息增益并不是百分之百好的。因?yàn)殡m然信息增益很優(yōu)秀，沒(méi)有考慮分類(lèi)后會(huì)變成什么樣子。分類(lèi)完成后，變得非常非常碎，有時(shí)也是決策樹(shù)最后應(yīng)用時(shí)失準(zhǔn)的可能原因之一。

于是信息增益率產(chǎn)生了。所謂信息增益率，是在原本的信息增益基礎(chǔ)上，再除以一個(gè)分母 I I I，分母 I I I公式為
I = ? ∑ i = 1 n p i × log ? 2 p i I=-\displaystyle\sum\limits_{i=1}^n p_i\times \log_2 p_i I=?i=1∑n?pi?×log2?pi?

其中 n n n為該屬性的可能取值數(shù)量， p i p_i pi?為當(dāng)前取值對(duì)應(yīng)的數(shù)據(jù)組數(shù)與總數(shù)據(jù)組數(shù)的比值，也就是當(dāng)前取值的頻率。

在選擇接下來(lái)要判定屬性的時(shí)候，將參考的量從信息增益變?yōu)樾畔⒃鲆媛?，一定程度上就可以解決這樣的問(wèn)題。

比如說(shuō)，圖中情況的系統(tǒng)總熵為
? 1 14 × log ? 2 1 14 × 14 = 3.81 -\frac{1}{14}\times \log_2 \frac{1}{14}\times 14=3.81 ?141?×log2?141?×14=3.81

對(duì)于ID這個(gè)屬性，信息增益率為0.930，信息增益率為0.244。

簡(jiǎn)單來(lái)說(shuō)，C4.5就是采用信息增益率作為標(biāo)準(zhǔn)，取代了信息增益。

CART(基尼指數(shù))

CART中，將這個(gè)標(biāo)準(zhǔn)從信息增益或信息增益率變成了一個(gè)叫做基尼指數(shù)的標(biāo)準(zhǔn)，即CART通過(guò)基尼指數(shù)選擇最優(yōu)特征。

基尼指數(shù)的計(jì)算方法：

G i n i ( p ) = ∑ i = 1 n p i ( 1 ? p i ) = 1 ? ∑ i = 1 n p i 2 Gini(p)=\displaystyle\sum\limits_{i=1}^n p_i(1-p_i)=1-\displaystyle\sum\limits_{i=1}^n p_i^2 Gini(p)=i=1∑n?pi?(1?pi?)=1?i=1∑n?pi2?

表示當(dāng)前有 n n n個(gè)類(lèi)別，每一個(gè)類(lèi)別在數(shù)據(jù)集中出現(xiàn)的頻率為 p i p_i pi?，此時(shí)的基尼指數(shù)。

剪枝

我們生活中會(huì)為花草樹(shù)木整形，將不好看的、多余的枝葉減去，此為剪枝。

決策樹(shù)也是一棵樹(shù)，也可以剪枝。只不過(guò)減掉一些枝的理由是決策樹(shù)過(guò)于龐大，導(dǎo)致后期利用決策樹(shù)進(jìn)行決策的時(shí)候，效率非常之低。

同時(shí)還有一點(diǎn)，如果將屬性綁定得過(guò)死，有時(shí)也會(huì)陷入誤區(qū)?？紤]一棵決策樹(shù)，如果我們把所有屬性全部判斷完，在決策樹(shù)上會(huì)從根節(jié)點(diǎn)一直走到葉子結(jié)點(diǎn)。根據(jù)決策樹(shù)的結(jié)構(gòu)我們知道，葉子結(jié)點(diǎn)對(duì)應(yīng)的只有一個(gè)屬性，換句話(huà)說(shuō)，對(duì)于每一個(gè)各個(gè)屬性的取值組，我們都對(duì)應(yīng)了唯一的一個(gè)答案。在某些情形下，這樣的做法并不一定好。比如說(shuō)，氣溫高、樹(shù)葉生長(zhǎng)，通過(guò)決策樹(shù)得到的結(jié)果一定是夏天，但也有可能是春天中的某一天突然變得很熱。這個(gè)被稱(chēng)作過(guò)擬合，這種一路跑到底的方法，有時(shí)過(guò)于死板而缺少了對(duì)其他干擾因素的靈活協(xié)調(diào)能力。

出于這樣那樣的考慮，我們接受將決策樹(shù)剪枝的結(jié)果，即可能有些路線(xiàn)不會(huì)得到所有屬性的判斷，得到的可選擇的選項(xiàng)也不一定唯一。但是為了提高性能和一些情況的特別需求，我們會(huì)進(jìn)行一些剪枝操作。

剪枝根據(jù)進(jìn)行剪枝的時(shí)間節(jié)點(diǎn)差異，分為預(yù)剪枝、后剪枝。

預(yù)剪枝

預(yù)剪枝的“預(yù)”取自“預(yù)先”，意味著在構(gòu)建決策樹(shù)之前預(yù)先進(jìn)行剪枝操作。但是由于構(gòu)建決策樹(shù)之前樹(shù)還沒(méi)有形成，所以這里所謂的剪枝操作不是真正的對(duì)樹(shù)進(jìn)行操作，而是在構(gòu)建決策樹(shù)之前先對(duì)構(gòu)建的方法進(jìn)行一個(gè)限制。

對(duì)于預(yù)剪枝，策略有限制深度、限制葉子結(jié)點(diǎn)個(gè)數(shù)、限制葉子結(jié)點(diǎn)包含的樣本數(shù)、限制信息增益量等。策略有很多，本質(zhì)上都是在構(gòu)造決策樹(shù)的時(shí)候限制樹(shù)的結(jié)點(diǎn)形成。

舉例來(lái)說(shuō)，在根據(jù)上一節(jié)講述的構(gòu)造方法時(shí)，如果構(gòu)造的結(jié)點(diǎn)所在的深度超過(guò)之前預(yù)設(shè)的深度，那么這個(gè)結(jié)點(diǎn)不生成，同時(shí)這個(gè)結(jié)點(diǎn)向下的所有屬性不再判斷。換句話(huà)說(shuō)，就是以這個(gè)結(jié)點(diǎn)為根的子樹(shù)全部舍棄。這個(gè)就是限制深度的策略。

即，所謂策略，就是在構(gòu)建決策樹(shù)時(shí)，如果這個(gè)結(jié)點(diǎn)和自己不符合自己設(shè)置的限制要求，那么就不新建這個(gè)結(jié)點(diǎn)，同時(shí)以這個(gè)結(jié)點(diǎn)為根的子樹(shù)也全部不建立。（直接把這一個(gè)枝全部剪掉，此所謂“剪枝”）。

那么限制葉子結(jié)點(diǎn)個(gè)數(shù)也是如此，當(dāng)從一個(gè)結(jié)點(diǎn)擴(kuò)展葉子結(jié)點(diǎn)的時(shí)候，如果擴(kuò)展完成后個(gè)數(shù)超過(guò)了之前的葉子結(jié)點(diǎn)要求的數(shù)，那么這個(gè)結(jié)點(diǎn)不擴(kuò)展。

限制葉子結(jié)點(diǎn)包含的樣本數(shù)要求支持一個(gè)葉子結(jié)點(diǎn)的樣本數(shù)必須達(dá)到一定的數(shù)量，如果當(dāng)前結(jié)點(diǎn)（無(wú)論是葉子結(jié)點(diǎn)還是非葉子結(jié)點(diǎn)）支持的樣本數(shù)已經(jīng)小于那個(gè)數(shù)量，那么下面的葉子結(jié)點(diǎn)包含的樣本數(shù)量必然小于那個(gè)數(shù)量，所以直接不創(chuàng)建這個(gè)結(jié)點(diǎn)（無(wú)論是葉子結(jié)點(diǎn)還是非葉子結(jié)點(diǎn)）。

限制信息增益量即如果當(dāng)前新建葉子結(jié)點(diǎn)選擇的屬性中產(chǎn)生的大信息增益小于一個(gè)定值，那么不新建這個(gè)葉子結(jié)點(diǎn)。根據(jù)不同的構(gòu)建方法，這個(gè)信息增益量可能是信息增益，也可能是信息增益率。

還有很多的限制方法，這個(gè)根據(jù)每一種不同的決策樹(shù)的構(gòu)建，選擇一個(gè)更加適合的限制方法即可?？梢悦恳粋€(gè)都試一試，最后選擇一個(gè)最合適的限制方法，所謂最合適，就是最后的訓(xùn)練效果最好，測(cè)試準(zhǔn)確率最高。

后剪枝

在構(gòu)建決策樹(shù)之后，通過(guò)一定的衡量標(biāo)準(zhǔn)對(duì)決策樹(shù)進(jìn)行剪枝。

以CART中的后剪枝策略為例。CART中為了讓決策樹(shù)生成的時(shí)候防止更多考慮的是訓(xùn)練數(shù)據(jù)，所以也有對(duì)應(yīng)的進(jìn)行剪枝的操作。CART為決策樹(shù)定義了一個(gè)叫做損失函數(shù)的東西，作為是否進(jìn)行剪枝的判斷標(biāo)準(zhǔn)。

后剪枝的判斷過(guò)程如下：

對(duì)于每一個(gè)結(jié)點(diǎn)，我們需要通過(guò)損失函數(shù)來(lái)進(jìn)行判斷該結(jié)點(diǎn)是否需要繼續(xù)進(jìn)行后續(xù)屬性的判斷：如果不進(jìn)行，則該結(jié)點(diǎn)直接作為決策樹(shù)的葉子結(jié)點(diǎn)；否則會(huì)變成一棵子樹(shù)的形狀，該結(jié)點(diǎn)不做葉子結(jié)點(diǎn)。

損失函數(shù)計(jì)算方法如下：

C α ( T ) = C ( T ) + α ? ∣ T l e a f ∣ C_{\alpha}(T)=C(T)+\alpha \cdot |T_{leaf}| Cα?(T)=C(T)+α?∣Tleaf?∣

其中 C ( T ) C(T) C(T)的計(jì)算方法為該子樹(shù)所有葉子結(jié)點(diǎn)的基尼指數(shù)×樣本個(gè)數(shù)之和， ∣ T l e a f ∣ |T_{leaf}| ∣Tleaf?∣是當(dāng)前子樹(shù)的葉子結(jié)點(diǎn)數(shù)量。 α \alpha α是一個(gè)超參數(shù)，其作用是控制預(yù)測(cè)誤差和樹(shù)復(fù)雜度之間的平衡。 α \alpha α大，會(huì)促使形成一棵簡(jiǎn)單的決策樹(shù)； α \alpha α小，會(huì)促使形成一棵復(fù)雜的決策樹(shù)。

舉例來(lái)說(shuō)，以這個(gè)圖為例：

下面的兩個(gè)節(jié)點(diǎn)是葉子結(jié)點(diǎn)，我們現(xiàn)在要通過(guò)損失函數(shù)計(jì)算是否應(yīng)當(dāng)把這兩個(gè)葉子結(jié)點(diǎn)剪掉。

先來(lái)計(jì)算一下不剪掉的損失函數(shù)值。不剪掉時(shí)，有兩個(gè)葉子結(jié)點(diǎn)，那么根據(jù)損失函數(shù)的公式有

C α ( T 1 ) = 0.0 × 3 + 0.4444 × 3 + 2 α C_{\alpha}(T_1)=0.0\times 3+0.4444\times 3 + 2\alpha Cα?(T1?)=0.0×3+0.4444×3+2α

如果把這兩個(gè)葉子結(jié)點(diǎn)剪掉，那么上面的那個(gè)樣本數(shù)6、基尼指數(shù)為0.4444的結(jié)點(diǎn)變?yōu)槿~子結(jié)點(diǎn)，共1個(gè)葉子結(jié)點(diǎn)。

C α ( T 2 ) = 0.4444 × 6 + α C_{\alpha}(T_2)=0.4444\times 6 + \alpha Cα?(T2?)=0.4444×6+α

不難發(fā)現(xiàn)，想要看是否應(yīng)當(dāng)剪掉下面的結(jié)點(diǎn)，將上面那個(gè)結(jié)點(diǎn)變?yōu)槿~子結(jié)點(diǎn)，重點(diǎn)在于 α \alpha α怎么取值。通常會(huì)對(duì) α \alpha α進(jìn)行一個(gè)預(yù)設(shè)，后剪枝時(shí)通過(guò)這個(gè)預(yù)設(shè)值進(jìn)行剪枝?？梢砸欢ǔ潭壬媳苊膺^(guò)擬合的現(xiàn)象出現(xiàn)。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱(chēng)：【學(xué)習(xí)筆記】決策樹(shù)-創(chuàng)新互聯(lián)
文章分享：http://jinyejixie.com/article48/diogep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、ChatGPT、外貿(mào)網(wǎng)站建設(shè)、App開(kāi)發(fā)、商城網(wǎng)站、定制開(kāi)發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)