經(jīng)典機(jī)器學(xué)習(xí)系列之【決策樹詳解】

??這節(jié)我們來講說一下決策樹杨刨。介紹一下決策樹的基礎(chǔ)知識、決策樹的基本算法周霉、決策樹中的問題以及決策樹的理解和解釋。

??本文主要思路結(jié)構(gòu)如下：先從直觀上解釋決策樹的算法流程珊拼。之后針對在實(shí)際操作過程中會遇到的6個問題對其進(jìn)行具體分析，其簡要包括(后文會詳細(xì)分析)：

??處理選擇最佳劃分屬性：依據(jù)不純度來選擇最佳劃分屬性，而依據(jù)不純度的不同，最佳劃分的度量標(biāo)準(zhǔn)又可分為三種：熵減最大馁筐、基尼指數(shù)減最大涂召、誤分類減最大坠非。而信息增益標(biāo)準(zhǔn)里面存在一個內(nèi)在的偏置，它會偏好去選擇具有較多屬性值的屬性果正，又提出了分裂信息的項(xiàng)作分母來懲罰具有較多屬性值的屬性炎码。在分裂信息中，當(dāng)劃分屬性在當(dāng)前結(jié)點(diǎn)中幾乎都取相同的屬性值時秋泳，會導(dǎo)致增益率無定義或者非常大(分母可能為0或者非常小)的情況潦闲，提出了平均增益度量。將其組合迫皱，得到6種選擇最佳劃分的度量標(biāo)準(zhǔn)歉闰。之后再舉實(shí)際例子，輔助解釋上述概念卓起。

??處理缺失值的問題：當(dāng)一些樣本的特征為空時和敬，主要有兩種解決辦法：舍棄這個樣本和估計(jì)這個缺失值大小。而估計(jì)這個缺失值的方法又可以分為三種：依據(jù)該屬性所有樣本戏阅、依據(jù)該節(jié)點(diǎn)中該屬性同類樣本昼弟、依據(jù)可能值賦予概率對其估計(jì)。

??處理連續(xù)屬性值問題：主要采用數(shù)據(jù)離散化技術(shù)奕筐，介紹了有監(jiān)督離散化和無監(jiān)督離散化兩大類舱痘。無監(jiān)督離散化技術(shù)又可以分為等深分箱法和等寬分箱法兩類变骡；有監(jiān)督離散化技術(shù)有：二分法，最小長度描述法芭逝。

??處理葉子節(jié)點(diǎn)的判定問題：主要有空葉子塌碌、純?nèi)~子、和屬性被測試完的葉子旬盯。

??處理過擬合問題：主要介紹了預(yù)剪枝和后剪枝技術(shù)誊爹。還介紹了最終確定正確樹的規(guī)模的三種辦法。

??處理待測試樣本的分類問題：將樣本帶入決策樹瓢捉，之后根據(jù)該葉子結(jié)點(diǎn)上的訓(xùn)練樣本集計(jì)算其后驗(yàn)概率频丘，最后把具有最大后驗(yàn)概率的類賦給待測樣本。計(jì)算其后驗(yàn)概率的常用方法包括：投票法泡态、加權(quán)投票法搂漠、局部概率模型法。在算后驗(yàn)概率的過程常采用的概率估計(jì)方法：基于頻率的極大似然估計(jì)某弦、拉普拉斯估計(jì)桐汤、基于相似度（距離）加權(quán)的拉普拉斯估計(jì)、m-估計(jì)靶壮，樸素貝葉斯估計(jì)等等怔毛。

決策樹學(xué)習(xí)的基礎(chǔ)知識

??這種算法是從傳統(tǒng)的手寫規(guī)則演變而來的，直觀上的理解就是：給你一個樣本腾降，然后問你拣度，它是正類嗎？你需要對這個問題進(jìn)行決策跟判別螃壤。到這里不難發(fā)現(xiàn)抗果，整個算法的核心就是：依據(jù)什么進(jìn)行決策跟判別。

??決策樹學(xué)習(xí)顧名思義就是用來做決策的樹奸晴。是一種逼近離散值目標(biāo)函數(shù)的方法冤馏，學(xué)習(xí)到的函數(shù)被表示為一顆決策樹。一顆決策樹包含一個根結(jié)點(diǎn)寄啼，若干個內(nèi)部結(jié)點(diǎn)逮光，若干個葉子結(jié)點(diǎn)。

根結(jié)點(diǎn)包含了所有的訓(xùn)練樣本墩划。
內(nèi)部結(jié)點(diǎn)包含對應(yīng)的屬性測試涕刚，每個內(nèi)部結(jié)點(diǎn)包含的樣本集合，依據(jù)屬性測試的結(jié)果走诞，被劃分到它的子結(jié)點(diǎn)副女。
葉子結(jié)點(diǎn)對應(yīng)于決策結(jié)界。

??從根結(jié)點(diǎn)到每個葉子結(jié)點(diǎn)的路徑對應(yīng)了一條決策規(guī)則。

決策樹學(xué)習(xí)的基本算法

??決策樹學(xué)習(xí)的目的是為了構(gòu)造一顆泛化能力強(qiáng)碑幅，即在測試樣本上就有很好表現(xiàn)的決策樹戴陡。基本算法遵循自頂向下沟涨、分而治之的策略恤批，具體步驟有以下幾點(diǎn)：

選擇最好的屬性作為測試屬性并創(chuàng)建樹的根結(jié)點(diǎn)
為測試屬性每個可能的取值產(chǎn)生一個分支
訓(xùn)練樣本劃分到適當(dāng)?shù)姆种?/strong>形成子結(jié)點(diǎn)

對每個子節(jié)點(diǎn)重復(fù)上面的過程，直到所有結(jié)點(diǎn)都是葉子結(jié)點(diǎn)裹赴。

決策樹學(xué)習(xí)中的常見問題

??可見喜庞，決策樹的學(xué)習(xí)是一個遞歸過程，過程的實(shí)現(xiàn)還需要解決以下六個方面的問題：

一棋返、 最佳劃分的度量問題：

??就是怎么產(chǎn)生子結(jié)點(diǎn)延都？從決策樹學(xué)習(xí)基本算法的步驟可以看出，決策樹學(xué)習(xí)的關(guān)鍵是如何選擇最佳劃分屬性睛竣。一般而言晰房，隨著長樹過程的不斷進(jìn)行，我們希望決策樹的分支結(jié)點(diǎn)所包含的樣本越來越歸屬于同一類別射沟，即結(jié)點(diǎn)的“不純度”(impurity) 越來越低殊者。

??因此，為了確定按某個屬性劃分的效果验夯，我們需要比較劃分前（父親結(jié)點(diǎn)）和劃分后（所有兒子結(jié)點(diǎn)）不純度的降低程度猖吴，降低越多，劃分的效果就越好挥转。那么我們需要在數(shù)學(xué)上對這個不純度進(jìn)行量化：

若記不純度的降低程度為 $\Delta$ 海蔽，則用來確定劃分效果的度量標(biāo)準(zhǔn)可以用以下數(shù)學(xué)公式來定義：

$\Delta_{I} = I_{(parent)} - \sum_{j=1}^{k} \frac{N(j)}{N}I(j)$

??其中， $I_{(parent)}$ 是父結(jié)點(diǎn)的不純度度量扁位， $k$ 是劃分屬性取值的個數(shù)准潭。 $N$ 是父親結(jié)點(diǎn)上樣本的總數(shù)趁俊， $N(j)$ 是第 $j$ 個兒子結(jié)點(diǎn)上樣本的數(shù)目域仇， $I(j)$ 是第 $j$ 個兒子節(jié)點(diǎn)的不純度度量。

??到這里寺擂，還有一個量沒有說怎么來計(jì)算暇务，就是不純度 $I$ 怎么來算：給定任意結(jié)點(diǎn) $t$ ，如何來定義它的不純度度量怔软，令 $p(i)$ 為結(jié)點(diǎn) $t$ 中第 $i$ 類樣本所占有的比例垦细，則結(jié)點(diǎn) $t$ 的不純度度量主要包括以下三種方式：

熵：

$Entropy(t) = -\sum_{i=1}^{c}p(i)log_{2}p(i)$

基尼指數(shù)：

$Gini(t)=1-\sum_{i=1}^{c}p(i)^{2}$

誤分類率：

$Error(t) = 1-max_{i}p(i)$

??其中， $c$ 為類別數(shù)目挡逼，并且在計(jì)算熵時括改，令 $0log_{2}0=0$ 。著名的 $ID3$ 決策樹算法就是以信息增益(熵)為準(zhǔn)則來選擇劃分屬性的家坎。CART決策樹算法則使用的是“基尼指數(shù)”嘱能×呙罚基尼指數(shù)反應(yīng)的是從數(shù)據(jù)集中隨機(jī)抽取兩個樣本，其類別標(biāo)記不一致的概率惹骂。因此 $Gini(t)$ 越小苏携，數(shù)據(jù)集純度越高。

??基于以上三種不純度的度量方式对粪，我們就可以得到以下3種選擇最佳劃分的度量標(biāo)準(zhǔn)：

熵減最大：

$\Delta_{Entropy Reduction} = Entropy(parent) - \sum_{j=1}^{k} \frac{N(j)}{N}Entropy(j)$

基尼指數(shù)減最大：

$\Delta_{Gini Reduction} = Gini(parent)-\sum_{j=1}^{k}\frac{N(j)}{N}Gini(j)$

誤分類率減最大：

$\Delta_{Error Reduction} = Error(parent)-\sum_{j=1}^{k}\frac{N(j)}{N}Error(j)$

??上式中右冻，熵減最大度量標(biāo)準(zhǔn)說的是信息增益最大度量標(biāo)準(zhǔn)，記作： $\Delta_{info}$ 著拭。

C4.5算法

??但信息增益標(biāo)準(zhǔn)里面存在一個內(nèi)在的偏置纱扭，它會偏好去選擇具有較多屬性值的屬性，為了減少這種偏好帶來的不利影響儡遮，著名的決策樹算法C4.5算法并不直接使用信息增益跪但，而使用“增益率”(Gain Ratio)來選擇最佳劃分屬性。

??那增益率如何定義的呢峦萎？增益率就是在信息增益度量中除以一個“分裂信息”(Split Information)的項(xiàng)作分母來懲罰具有較多屬性值的屬性：

$GainRatio = \frac{\Delta_{info}}{SplitInfo}$

??其中屡久， $SplitInfo$ 是劃分屬性的分裂信息。其數(shù)學(xué)表達(dá)如下所示：

$SplitInfo = -\sum_{j=1}^{k}p(j)log_{2}p(j)$

??其中爱榔， $p(j)$ 是當(dāng)前結(jié)點(diǎn)中劃分屬性第 $j$ 個屬性值所占有樣本的比例被环。分裂信息 $SplitInfo$ 度量了屬性劃分?jǐn)?shù)據(jù)的廣度和均勻性。分裂信息實(shí)際上就是當(dāng)前結(jié)點(diǎn)關(guān)于劃分屬性各值的熵详幽，它可以阻礙選擇屬性值均勻分布的屬性筛欢。

??在引入分裂信息 $SplitInfo$ 的同時，也產(chǎn)生了一個新的實(shí)際問題：當(dāng)劃分屬性在當(dāng)前結(jié)點(diǎn)中幾乎都取相同的屬性值時唇聘，會導(dǎo)致增益率無定義或者非常大(分母可能為0或者非常小)版姑。也可以理解為對可取值數(shù)目較少的屬性有所偏好。

??為了避免選擇這種屬性迟郎，C4.5決策樹算法并不直接選擇增益率最大的劃分屬性剥险，而使用一個啟發(fā)式方法：先計(jì)算每個屬性的信息增益及平均值，然后僅對信息增益高于平均值的屬性應(yīng)用增益率度量宪肖。

平均增益度量

??為了克服信息增益度量和增益率的問題表制，平均增益(AverGain)度量被提出。平均增益度量用劃分屬性取值的個數(shù)來替換屬性的分裂信息控乾，不僅懲罰了屬性較多的屬性么介，還避免了增益率度量在實(shí)際操作過程中的問題。具體的度量公式如下：

$AverGain = \frac{\Delta_{Info}}{k}$

??其中蜕衡， $k$ 是劃分屬性取值的個數(shù)壤短。

??增益率和平均增益度量改進(jìn)信息增益度量的方法同樣適合于基尼指數(shù)和誤分類率，由此，我們又可以得到6種選擇最佳劃分的度量標(biāo)準(zhǔn)久脯。

熵減率最大：

$\Delta_{EntropyReductionRato} = \frac{\Delta_{EntropyReduction}}{SplitInfo}$

基尼指數(shù)減率最大：

$\Delta_{GiniReductionRato}=\frac{\Delta_{GiniReduction}}{SplitInfo}$

誤分類率減率最大：

$\Delta_{ErrorReductionRato}=\frac{\Delta_{ErrorReduction}}{SplitInfo}$

平均熵減最大:

$\Delta_{AverGiniReduction }=\frac{\Delta_{GiniReduction}}{k}$

平均基尼指數(shù)減最大：

$\Delta_{AverGiniReduction}=\frac{\Delta_{GiniReduction}}{k}$

平均誤分類率減最大

$\Delta_{AverErrorReduction}=\frac{\Delta_{ErrorReduction}}{k}$

??到這里可能有點(diǎn)迷糊蒜绽，我們舉一個例子利用上述數(shù)學(xué)方法來實(shí)際演練一波：

??給定訓(xùn)練集 $S$ ，下面以信息增益度量作為最佳劃分的標(biāo)準(zhǔn)桶现，演示信息增益的計(jì)算和決策樹生長的過程躲雅。

數(shù)據(jù)集

??這是網(wǎng)上的一個樣本數(shù)據(jù)集，每一天相當(dāng)于是一個樣本骡和，總共是14個樣本相赁，每個樣本有四個特征，一個標(biāo)簽慰于。四個特征分別是：Outlook钮科、Temperature、Humidity婆赠、Wind绵脯；標(biāo)簽是：PlayTennis，標(biāo)簽里面只有兩類類別休里。

??假如Outlook被選作劃分屬性蛆挫，其圖形表示如下所示：

依據(jù)Outlook屬性劃分

??那么它劃分訓(xùn)練集 $S$ 的信息增益，等于訓(xùn)練集 $S$ 的熵妙黍，減去它兒子結(jié)點(diǎn)上熵的加權(quán)和悴侵，其中的權(quán)值就是兒子結(jié)點(diǎn)上樣本數(shù)目占父親結(jié)點(diǎn)上樣本的數(shù)目的比例。具體的表達(dá)公式如下所示：

$Gain(S,Outlook)=E(S)-[\frac{5}{14}E(S_{Sunny})+\frac{4}{14}E(S_{Overcast})+\frac{5}{14}E(S_{Rain})]$

??其中：

$E(S)=- \frac{9}{14}log_{2}\frac{9}{14}-\frac{5}{14}log_{2}\frac{5}{14}$

$E(S_{Sunny})=-\frac{2}{5}log_{2}\frac{2}{5}-\frac{3}{5}log_{2}\frac{3}{5}$

$E({S_{Overcast}})=-\frac{4}{4}log_{2}4 -\frac{0}{4}log_{2}\frac{0}{4}$

$E(S_{Rain})=-\frac{3}{5}log_{2}\frac{3}{5}-\frac{2}{5}log_{2}\frac{2}{5}$

??由此計(jì)算出 $Gain(S,Outlook)=0.246$ 拭嫁，以同樣的方法可以分別得到Temperature可免，Humidity、Wind作為劃分屬性的信息增益： $Gain(S,Temperature)=0.029$ 做粤、 $Gain(S,Humidity)=0.151$ 浇借、 $Gain(S,Wind)=0.048$ 。

??因此怕品，對于當(dāng)前結(jié)點(diǎn)妇垢，用 “Outlook”劃分樣本集S的信息增益最大，被選為劃分屬性堵泽。根節(jié)點(diǎn)選定為Ourlook為劃分屬性修己。劃分之后就如上圖依據(jù)Outlook屬性劃分所示。

??對于生成的每一個兒子結(jié)點(diǎn)迎罗，重復(fù)上面的過程，直到所有的結(jié)點(diǎn)為葉子結(jié)點(diǎn)片仿。

二纹安、處理缺失屬性值問題：

??也即樣本的一些特征為空。現(xiàn)實(shí)任務(wù)中常會遇到不完整樣本，即樣本的某些屬性值缺失厢岂，尤其是在屬性數(shù)目較多的情況下光督，往往會有大量樣本出現(xiàn)缺失值。面對缺失屬性值塔粒，決策樹學(xué)習(xí)會面臨兩個方面的問題：

如何計(jì)算含缺失值屬性的劃分度量结借、并進(jìn)行最佳劃分的選擇？

選擇好最佳劃分后卒茬，若樣本在該屬性上的值缺失船老，如何對樣本進(jìn)行劃分?

處理這種屬性值缺失的問題，通常有兩個辦法

放棄這個樣本圃酵，使用無缺失樣本進(jìn)行學(xué)習(xí)柳畔。但這種方法會造成資源的浪費(fèi)。

依據(jù)此屬性值已知的其它樣本來對其進(jìn)行估計(jì)：a. 賦予其當(dāng)前結(jié)點(diǎn)所有樣本該屬性最常見的值郭赐；b. 賦予它當(dāng)前結(jié)點(diǎn)同類樣本中該屬性值最常見的值薪韩；c. 為缺失值屬性的每個可能值賦予一個概率，而不是簡單地將最常見的值賦給它捌锭。

三俘陷、處理連續(xù)屬性值問題：

??上文討論的都是決策樹學(xué)習(xí)中的離散屬性問題，但是在實(shí)際操作過程中观谦，通常會遇到連續(xù)屬性岭洲，因此我們有必要討論決策樹如何來對連續(xù)屬性進(jìn)行處理。

??由于連續(xù)屬性的可取值數(shù)目不是有限的坎匿，當(dāng)選定一個特征之后盾剩，它所對應(yīng)的子節(jié)點(diǎn)無法展開，那么我們就需要將數(shù)據(jù)進(jìn)行離散化替蔬。數(shù)據(jù)離散化技術(shù)大致可以分為有監(jiān)督離散化和無監(jiān)督離散化兩大類告私。

??無監(jiān)督離散化技術(shù)又可以分為等深分箱法和等寬分箱法兩類。在等深分箱法中承桥，讓每個分箱中的樣本數(shù)目一致驻粟。在等寬分箱法中，讓每個分箱中的取值范圍一致凶异，本質(zhì)上就是將一個區(qū)間等分成若干段蜀撑，每段附一個離散值。

??有監(jiān)督離散化技術(shù)有：二分法(C4.5算法采用的機(jī)制)剩彬，最小長度描述法酷麦。

??在二分法中將連續(xù)的屬性按選定的閾值分割成布爾屬性。它具體的做法是：

按照某個連續(xù)的屬性 $T$ 對樣本進(jìn)行排序喉恋；

找到類標(biāo)記不同的相鄰樣本沃饶；

計(jì)算類標(biāo)記不同的相鄰樣本的屬性 $T$ 的中間值母廷，產(chǎn)生一組候選閾值『簦可以證明產(chǎn)生最大信息增益的閾值一定在這樣的邊界中(Fayyad, 1991)琴昆；

計(jì)算與每個候選閾值關(guān)聯(lián)的信息增益，選擇具有最大信息增益的閾值來離散化連續(xù)屬性 $T$ 馆揉。

??二分法的擴(kuò)展是最小描述長度法(Minimum Description Length MDL)(Fayyad & Irani, 1993)业舍。MDL法將連續(xù)取值的屬性分割成多個區(qū)間，而不是單一閾值的兩個區(qū)間升酣。

四舷暮、 葉子結(jié)點(diǎn)的判定問題：

??上文都是圍繞決策樹如何展開生長的討論，那決策樹什么時候停止生長呢拗踢？

??如果我們暫且不考慮樹的規(guī)模過大而導(dǎo)致的過擬合問題脚牍，在決策樹學(xué)習(xí)基本算法中，有三種情形會判定為葉子結(jié)點(diǎn):

當(dāng)前結(jié)點(diǎn)中的樣本集合為空巢墅，即空葉子诸狭；

當(dāng)前結(jié)點(diǎn)中的所有樣本全部歸屬于同一類別，即純?nèi)~子君纫；

當(dāng)前結(jié)點(diǎn)中的所有樣本在接下來劃分的所有屬性上取值相同驯遇，即屬性被測試完的葉子。

??2和3可合并等價為最佳劃分的度量值為0的情況蓄髓。

五叉庐、 怎樣解決過擬合問題：

??在決策樹學(xué)習(xí)中，為了盡可能正確分類訓(xùn)練樣本会喝，結(jié)點(diǎn)劃分過程將不斷重復(fù)陡叠，有時會造成決策樹分支過多，這時就可能因?yàn)橛?xùn)練樣本學(xué)得“太好”了肢执，上述對葉子結(jié)點(diǎn)判定的情形枉阵，都太過苛刻和完美，從而造成決策樹的規(guī)模過大预茄，以致于把訓(xùn)練集自身的一些特點(diǎn)當(dāng)作所有數(shù)據(jù)都具有的一般性質(zhì)而導(dǎo)致過擬合兴溜。

??剪枝(pruning)是解決過擬合問題的主要手段，基本策略有“預(yù)剪枝”(prepruning)和“后剪枝” (post pruning) 耻陕。

預(yù)剪枝：在算法完美劃分訓(xùn)練數(shù)據(jù)之前就停止樹生長拙徽。在決策樹展開之前，對每個節(jié)點(diǎn)在劃分前先進(jìn)行估計(jì)诗宣，若當(dāng)前結(jié)點(diǎn)的劃分不能帶來決策樹泛化性能提升膘怕，則停止劃分，并將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)梧田；

后剪枝：允許樹過度擬合訓(xùn)練數(shù)據(jù)淳蔼，然后對樹進(jìn)行后修剪侧蘸。從訓(xùn)練集生成一顆完整的決策樹裁眯，然后自底向上地對非葉結(jié)點(diǎn)進(jìn)行考察鹉梨，若將該結(jié)點(diǎn)對應(yīng)的子樹替換為葉節(jié)點(diǎn)能帶來決策樹泛化性能提升，則將該子樹替換為葉節(jié)點(diǎn)穿稳。

??盡管預(yù)剪枝可能看起來更直接存皂，但后剪枝方法在實(shí)踐中往往更好。因?yàn)樵陬A(yù)剪枝中精確地估計(jì)何時停止增長樹是非常困難的逢艘。

??無論是通過預(yù)剪枝還是后剪枝來得到正確規(guī)模的樹旦袋，一個關(guān)鍵的問題是使用什么樣的準(zhǔn)則來確定最終正確樹的規(guī)模？建立決策樹的初衷是希望模型能夠?qū)y試樣本具有足夠強(qiáng)的泛化能力它改，所以有以下三種判斷方法：

采用留出法疤孕，即預(yù)留一部分?jǐn)?shù)據(jù)用作“驗(yàn)證集”以進(jìn)行性能評估。

使用所有可用數(shù)據(jù)進(jìn)行訓(xùn)練央拖，但進(jìn)行統(tǒng)計(jì)測試來估計(jì)生長或修剪一個特定的結(jié)點(diǎn)是否有可能改善在訓(xùn)練集以外的樣例上的性能祭阀。

使用一個明確的標(biāo)準(zhǔn)來衡量訓(xùn)練樣例和決策樹的復(fù)雜度，當(dāng)這個編碼的長度最小時停止樹增長鲜戒。

??上面的第一種方法是最普通的专控，常被稱為訓(xùn)練和驗(yàn)證集法。它將可用數(shù)據(jù)分成兩個樣例集合：訓(xùn)練集用于形成學(xué)習(xí)到的假設(shè)遏餐；驗(yàn)證集用于評估這個假設(shè)在后續(xù)數(shù)據(jù)上的精度伦腐。

??訓(xùn)練和驗(yàn)證集法的動機(jī)：即使學(xué)習(xí)器可能會被訓(xùn)練集誤導(dǎo)，但驗(yàn)證集不大可能表現(xiàn)出同樣的隨機(jī)波動失都。通常的做法是柏蘑，所有樣例的三分之二作訓(xùn)練集，三分之一作驗(yàn)證集粹庞。

??訓(xùn)練和驗(yàn)證集法主要包括：錯誤率降低修剪和規(guī)則后修剪咳焚。具體算法可參閱 [Mitchell, 1997]。

六信粮、 待測試樣本的分類問題：

??到此黔攒，我們解決了決策樹生長的相關(guān)問題，那么强缘，決策樹學(xué)習(xí)學(xué)到后督惰，怎樣應(yīng)用決策樹進(jìn)行待測樣本的分類？

??分類待測樣本的方法：從決策樹的根結(jié)點(diǎn)開始旅掂，測試這個結(jié)點(diǎn)指定的劃分屬性赏胚，然后按照待測樣本的該屬性值對應(yīng)的樹枝向下移動。這個過程再在以新結(jié)點(diǎn)為根的子樹上重復(fù)商虐，直到將待測樣本劃分到某個葉子結(jié)點(diǎn)為止觉阅。然后根據(jù)該葉子結(jié)點(diǎn)上的訓(xùn)練樣本集計(jì)算其后驗(yàn)概率崖疤，最后把具有最大后驗(yàn)概率的類賦給待測樣本。

??給定一個葉子結(jié)點(diǎn)（其本質(zhì)就是一個訓(xùn)練樣本的集合）典勇，計(jì)算其后驗(yàn)概率的常用方法包括：投票法劫哼、加權(quán)投票法割笙、局部概率模型法权烧。當(dāng)計(jì)算得到的后驗(yàn)概率出現(xiàn)相同的情況下，可以采用隨機(jī)分類或者拒判的方法進(jìn)行處理伤溉。

??在計(jì)算后驗(yàn)概率的過程經(jīng)常會采用一些常用的概率估計(jì)方法：基于頻率的極大似然估計(jì)般码、拉普拉斯估計(jì)、基于相似度（距離）加權(quán)的拉普拉斯估計(jì)乱顾、m-估計(jì)板祝，樸素貝葉斯估計(jì)等等。

??舉個例子：

決策樹舉例

??假設(shè)有一個樣本走净，其特征分別是sunny券时、hot、normal温技、weak革为；真實(shí)標(biāo)簽是Yes。將其運(yùn)用于構(gòu)建好的決策樹舵鳞，如上圖所示震檩。應(yīng)用拉普拉斯估計(jì)(分子加1分母加2，背后的思想是：在實(shí)驗(yàn)之前已經(jīng)有兩次實(shí)驗(yàn)蜓堕，一次正抛虏，一次反。為了防止出現(xiàn)零概率估計(jì))得到待測試樣本 $x$ 屬于 $Yes$ 和 $No$ 的概率分別為：

$P(Yes|x)=\frac{2+1}{2+2}=\frac{3}{4}$

$P(No|x)=\frac{0+1}{2+2}=\frac{1}{4}$

決策樹學(xué)習(xí)的理解和解釋

??決策樹學(xué)習(xí)是以樣本為基礎(chǔ)的歸納學(xué)習(xí)方法套才，它采用自頂向下的遞歸方式來生長決策樹迂猴。隨著樹的生長，完成對訓(xùn)練樣本集的不斷細(xì)分背伴，最終都被細(xì)分到了每個葉子結(jié)點(diǎn)上沸毁。

??決策樹的每個結(jié)點(diǎn)都是樣本的集合，熵等度量刻畫了樣本集的不純度傻寂，決策樹的生長過程是一個熵降低息尺、信息增益、從混沌到有序的過程疾掰。

??決策樹學(xué)習(xí)對噪聲數(shù)據(jù)具有很好的魯棒性搂誉，而且學(xué)習(xí)得到的決策樹還能被表示為多條if-then形式的決策規(guī)則，因此具有很強(qiáng)的可讀性和可解釋性静檬。

我的微信公眾號名稱：深度學(xué)習(xí)先進(jìn)智能決策
微信公眾號ID：MultiAgent1024
公眾號介紹：主要研究深度學(xué)習(xí)炭懊、強(qiáng)化學(xué)習(xí)并级、機(jī)器博弈等相關(guān)內(nèi)容！期待您的關(guān)注侮腹，歡迎一起學(xué)習(xí)交流進(jìn)步嘲碧！

最后編輯于：2020.02.04 15:22:08

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市凯旋，隨后出現(xiàn)的幾起案子呀潭，更是在濱河造成了極大的恐慌钉迷，老刑警劉巖至非，帶你破解...
沈念sama閱讀 217,509評論 6贊 504
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異糠聪，居然都是意外死亡荒椭，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,806評論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門舰蟆，熙熙樓的掌柜王于貴愁眉苦臉地迎上來趣惠，“玉大人，你說我怎么就攤上這事身害∥肚模” “怎么了？”我有些...
開封第一講書人閱讀 163,875評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵塌鸯，是天一觀的道長侍瑟。經(jīng)常有香客問我，道長丙猬，這世上最難降的妖魔是什么涨颜？我笑而不...
開封第一講書人閱讀 58,441評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮茧球，結(jié)果婚禮上庭瑰，老公的妹妹穿的比我還像新娘。我一直安慰自己抢埋，他們只是感情好弹灭，可當(dāng)我...
茶點(diǎn)故事閱讀 67,488評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著揪垄，像睡著了一般穷吮。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上福侈，一...
開封第一講書人閱讀 51,365評論 1贊 302
城市分裂傳說
那天酒来，我揣著相機(jī)與錄音，去河邊找鬼肪凛。笑死堰汉，一個胖子當(dāng)著我的面吹牛辽社，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播翘鸭，決...
沈念sama閱讀 40,190評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼滴铅，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了就乓？” 一聲冷哼從身側(cè)響起汉匙，我...
開封第一講書人閱讀 39,062評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎生蚁，沒想到半個月后噩翠，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,500評論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡邦投，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,706評論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年伤锚，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片志衣。...
茶點(diǎn)故事閱讀 39,834評論 1贊 347
活死人
序言：一個原本活蹦亂跳的男人離奇死亡屯援，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出念脯，到底是詐尸還是另有隱情狞洋，我是刑警寧澤，帶...
沈念sama閱讀 35,559評論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布绿店，位于F島的核電站吉懊，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏惯吕。R本人自食惡果不足惜惕它，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,167評論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望废登。院中可真熱鬧淹魄，春花似錦、人聲如沸堡距。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,779評論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽羽戒。三九已至缤沦，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間易稠，已是汗流浹背缸废。一陣腳步聲響...
開封第一講書人閱讀 32,912評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人企量。一個月前我還...
沈念sama閱讀 47,958評論 2贊 370
代替公主和親
正文我出身青樓测萎，卻偏偏與公主長得像，于是被迫代替她去往敵國和親届巩。傳聞我的和親對象是個殘疾皇子硅瞧，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,779評論 2贊 354

經(jīng)典機(jī)器學(xué)習(xí)系列之【決策樹詳解】

經(jīng)典機(jī)器學(xué)習(xí)系列之【決策樹詳解】

決策樹學(xué)習(xí)的基礎(chǔ)知識

決策樹學(xué)習(xí)的基本算法

決策樹學(xué)習(xí)中的常見問題

一棋返、最佳劃分的度量問題：

C4.5算法

平均增益度量

二纹安、處理缺失屬性值問題：

三俘陷、處理連續(xù)屬性值問題：

四舷暮、葉子結(jié)點(diǎn)的判定問題：

五叉庐、怎樣解決過擬合問題：

決策樹學(xué)習(xí)的理解和解釋

推薦閱讀更多精彩內(nèi)容

經(jīng)典機(jī)器學(xué)習(xí)系列之【決策樹詳解】

決策樹學(xué)習(xí)的基礎(chǔ)知識

決策樹學(xué)習(xí)的基本算法

決策樹學(xué)習(xí)中的常見問題

一棋返、 最佳劃分的度量問題：

C4.5算法

平均增益度量

二纹安、處理缺失屬性值問題：

三俘陷、處理連續(xù)屬性值問題：

四舷暮、 葉子結(jié)點(diǎn)的判定問題：

五叉庐、 怎樣解決過擬合問題：

決策樹學(xué)習(xí)的理解和解釋

推薦閱讀更多精彩內(nèi)容

一棋返、最佳劃分的度量問題：

四舷暮、葉子結(jié)點(diǎn)的判定問題：

五叉庐、怎樣解決過擬合問題：