決策樹（DecisionTree）

發(fā)布時(shí)間：2025-08-28 | 來源：互聯(lián)網(wǎng)轉(zhuǎn)載和整理

決策樹是一種非參數(shù)有監(jiān)督的機(jī)器學(xué)習(xí)方法，可以用于解決回歸問題和分類問題。通過學(xué)習(xí)已有的數(shù)據(jù)，計(jì)算得出一系列推斷規(guī)則來預(yù)測(cè)目標(biāo)變量的值，并用類似流程圖的形式進(jìn)行展示。決策樹模型可以進(jìn)行可視化，具有很強(qiáng)的可解釋性，算法容易理解，以決策樹為基礎(chǔ)的各種集成算法在很多領(lǐng)域都有廣泛的應(yīng)用。

熵的概念最早起源于物理學(xué)，用于度量一個(gè)熱力學(xué)系統(tǒng)的無序程度。在信息論里面，信息熵代表著一個(gè)事件或一個(gè)變量等所含有的信息量。在信息世界熵越高，則能傳輸越多的信息，熵越低，則意味著傳輸?shù)男畔⒃缴佟?/p>

發(fā)生概率低的事件比發(fā)生概率高的事件具有更大的不確定性，需要更多的信息去描述他們，信息熵更高。

我們可以用計(jì)算事件發(fā)生的概率來計(jì)算事件的信息，又稱“香農(nóng)信息”（ShannonInformation）。一個(gè)離散事件x的信息可以表示為：h(x)=-log(p(x))p()代表事件x發(fā)生的概率，log()為以二為底的對(duì)數(shù)函數(shù)，即一個(gè)事件的信息量就是這個(gè)事件發(fā)生的概率的負(fù)對(duì)數(shù)。選擇以二為底的對(duì)數(shù)函數(shù)代表計(jì)算信息的單位是二進(jìn)制。因?yàn)楦怕蕄(x)小于1，所以負(fù)號(hào)就保證了信息熵永遠(yuǎn)不為負(fù)數(shù)。當(dāng)事件的概率為1時(shí)，也就是當(dāng)某事件百分之百發(fā)生時(shí)，信息為0。

熵（entropy），又稱“香農(nóng)熵”（Shannonentropy），表示一個(gè)隨機(jī)變量的分布所需要的平均比特?cái)?shù)。一個(gè)隨機(jī)變量的信息熵可以表示為：H(x)=-sum(eachkinKp(k)log(p(k)))K表示變量x所可能具有的所有狀態(tài)（所有事件），將發(fā)生特定事件的概率和該事件的信息相乘，最后加和，即可得到該變量的信息熵?？梢岳斫鉃樾畔㈧鼐褪瞧骄园l(fā)生一個(gè)事件我們得到的信息量大小。所以數(shù)學(xué)上信息熵其實(shí)是事件信息量的期望。

當(dāng)組成該隨機(jī)變量的一個(gè)事件的概率為1時(shí)信息熵最小，為0，即該事件必然發(fā)生。當(dāng)組成該隨機(jī)變量的所有事件發(fā)生的概率相等時(shí)，信息熵最大，即完全不能判斷那一個(gè)事件更容易發(fā)生，不確定性最大。

當(dāng)一個(gè)事件主導(dǎo)時(shí)，比如偏態(tài)分布（SkewedProbabilityDistribution），不確定性減小，信息熵較低（lowentropy）；當(dāng)所有事件發(fā)生概率相同時(shí)比如均衡分布（BalancedProbabilityDistribution），不確定性極大，信息熵較高（highentropy）。

由以上的香農(nóng)信息公式可知，信息熵主要有三條性質(zhì)：-單調(diào)性。發(fā)生概率越高的事件，其所攜帶的信息熵越低。比如一個(gè)真理的不確定性是極低的，那么它所攜帶的信息熵就極低。-非負(fù)性。信息熵不能為負(fù)。單純從邏輯層面理解，如果得知了某個(gè)信息后，卻增加了不確定性，這也是不合邏輯的。-可加性。即多隨機(jī)事件同時(shí)發(fā)生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和。

若兩事件A和B同時(shí)發(fā)生，兩個(gè)事件相互獨(dú)立。p(X=A,Y=B)=p(X=A)*p(Y=B),那么信息熵為H(A,B)=H(A)+H(B)。但若兩事件不相互獨(dú)立，那么H(A,B)=H(A)+H(B)-I(A,B)。其中I(A,B)是互信息（mutualinformation，MI），即一個(gè)隨機(jī)變量包含另一個(gè)隨機(jī)變量信息量的度量。即已知X的情況下，Y的分布是否會(huì)改變。

可以理解為兩個(gè)隨機(jī)變量的互信息度量了兩個(gè)變量間相互依賴的程度。X和Y的互信息可以表示為：I(X;Y)=H(X)-H(X|Y)H(X)是X的信息熵，H(X|Y)是已知Y的情況下，X的信息熵。結(jié)果的單位是比特。簡(jiǎn)單來說互信息的性質(zhì)為：-I(X;Y)>=0互信息永遠(yuǎn)不可能為負(fù)-H(X)-H(X|Y)=I(X;Y)=I(Y;X)=H(Y)-H(Y|X)互信息是對(duì)稱的-當(dāng)X，Y獨(dú)立的時(shí)候，I(X;Y)=0互信息值越大，兩變量相關(guān)性越強(qiáng)。-當(dāng)X，Y知道一個(gè)就能推斷另一個(gè)的時(shí)候，I(X;Y)=H(Y)=H(X)

在數(shù)據(jù)科學(xué)中，互信息常用于特征篩選。在通信系統(tǒng)中互信息也應(yīng)用廣泛。在一個(gè)點(diǎn)到點(diǎn)的通信系統(tǒng)中，發(fā)送信號(hào)為X，通過信道后，接收端接收到的信號(hào)為Y，那么信息通過信道傳遞的信息量就是互信息I(X,Y)。根據(jù)這個(gè)概念，香農(nóng)推導(dǎo)出信道容量（即臨界通信傳輸速率的值）。

信息增益（InformationGain）是用來按照一定規(guī)則劃分?jǐn)?shù)據(jù)集后，衡量信息熵減少量的指數(shù)。

那數(shù)據(jù)集的信息熵又是怎么計(jì)算的呢？比如一個(gè)常見的0,1二分類問題，我們可以計(jì)算它的熵為：Entropy=-(p(0)*log(P(0))+p(1)\*log(P(1)))當(dāng)該數(shù)據(jù)集為50/50的數(shù)據(jù)集時(shí)，它的信息熵是最大的（1bit）。而10/90的數(shù)據(jù)集將會(huì)大大減少結(jié)果的不確定性，減小數(shù)據(jù)集的信息熵（約為0.469bit）。

這樣來說信息熵可以用來表示數(shù)據(jù)集的***（purity）。信息熵為0就表示該數(shù)據(jù)集只含有一個(gè)類別，***最高。而較高的信息熵則代表較為平衡的數(shù)據(jù)集和較低的***。

信息增益是提供了一種可以使用信息熵計(jì)算數(shù)據(jù)集經(jīng)過一定的規(guī)則（比如決策樹中的一系列規(guī)則）進(jìn)行數(shù)據(jù)集分割后信息熵的變化的方法。IG(S,a)=H(S)-H(S|a)其中，H(s)是原數(shù)據(jù)集S的信息熵（在做任何改變之前），H(S|a)是經(jīng)過變量a的一定分割規(guī)則。所以信息增益描述的是數(shù)據(jù)集S變換后所節(jié)省的比特?cái)?shù)。

信息增益可以用做決策樹的分枝判斷方法。比如最常用CART樹（ClassificationandRegressionTree）中的分枝方法，只要在python中設(shè)置參數(shù)criterion為“entropy”即可。

信息增益也可以用作建模前的特征篩選。在這種場(chǎng)景下，信息增益和互信息表達(dá)的含義相同，會(huì)被用來計(jì)算兩變量之間的獨(dú)立性。比如scikit-learn中的函數(shù)mutual_info_classiif()

信息增益在面對(duì)類別較少的離散數(shù)據(jù)時(shí)效果較好，但是面對(duì)取值較多的特征時(shí)效果會(huì)有偏向性。因?yàn)楫?dāng)特征的取值較多時(shí)，根據(jù)此特征劃分得到的子集***有更大的可能性會(huì)更高(對(duì)比與取值較少的特征)，因此劃分之后的熵更低，由于劃分前的熵是一定的，因此信息增益更大，因此信息增益比較偏向取值較多的特征。舉一個(gè)極端的例子來說如果一個(gè)特征為身份證號(hào)，當(dāng)把每一個(gè)身份證號(hào)不同的樣本都分到不同的子節(jié)點(diǎn)時(shí)，熵會(huì)變?yōu)?，意味著信息增益最大，從而該特征會(huì)被算法選擇。但這種分法顯然沒有任何實(shí)際意義。

這種時(shí)候信息增益率就起到了很重要的作用。gR(D,A)=g(D,A)/HA(D)HA(D)又叫做特征A的內(nèi)部信息，HA(D)其實(shí)像是一個(gè)衡量以特征AA的不同取值將數(shù)據(jù)集D分類后的不確定性的度量。如果特征A的取值越多，那么不確定性通常會(huì)更大，那么HA(D)的值也會(huì)越大，而1/HA(D)的值也會(huì)越小。這相當(dāng)于是在信息增益的基礎(chǔ)上乘上了一個(gè)懲罰系數(shù)。即gR(D,A)=g(D,A)?懲罰系數(shù)。

在CART算法中，基尼不***表示一個(gè)隨機(jī)選中的樣本被分錯(cuò)類別的可能性，即這個(gè)樣本被選中的概率乘以它被分錯(cuò)的概率。當(dāng)一個(gè)節(jié)點(diǎn)中所有樣本均為一種時(shí)（沒有被分錯(cuò)的樣本），基尼不***達(dá)到最低值0。

舉例來說如果有綠色和藍(lán)色兩類數(shù)據(jù)點(diǎn)，各占一半（藍(lán)色50%，綠色50%）。那么我們隨機(jī)分類，有以下四種情況：-分為藍(lán)色，但實(shí)際上是綠色（?），概率25%-分為藍(lán)色，實(shí)際上也是藍(lán)色（??），概率25%-分為綠色，實(shí)際上也是綠色（??），概率25%-分為綠色，但實(shí)際上是藍(lán)色（?），概率25%那么將任意一個(gè)數(shù)據(jù)點(diǎn)分錯(cuò)的概率為25%+25%=50%?；岵?**為0.5。

在特征選擇中，我們可以選擇加入后使數(shù)據(jù)不***減少最多的特征。

噪音數(shù)據(jù)簡(jiǎn)單來說就是會(huì)對(duì)模型造成誤導(dǎo)的數(shù)據(jù)。分為類別噪聲（classnoise或labelnoise）和變量噪聲（attributenoise）。類別噪聲指的的是被錯(cuò)誤標(biāo)記的錯(cuò)誤數(shù)據(jù)，比如兩個(gè)相同的樣本具有不同的標(biāo)簽等情況。變量噪聲指的是有問題的變量，比如缺失值、異常值和無關(guān)值等。

決策樹其實(shí)是一種圖結(jié)構(gòu)，由節(jié)點(diǎn)和邊構(gòu)成。-根節(jié)點(diǎn)：只有出邊沒有入邊。包含樣本全集，表示一個(gè)對(duì)樣本最初的判斷。-內(nèi)部節(jié)點(diǎn)：一個(gè)入邊多個(gè)出邊。表示一個(gè)特征或是屬性。每個(gè)內(nèi)部節(jié)點(diǎn)都是一個(gè)判斷條件，包含數(shù)據(jù)集中從根節(jié)點(diǎn)到該節(jié)點(diǎn)所有滿足條件的數(shù)據(jù)的***。-葉節(jié)點(diǎn)：一個(gè)入邊無出邊。表示一個(gè)類對(duì)應(yīng)于決策結(jié)果。

決策樹的生成主要分為三個(gè)步驟：1.節(jié)點(diǎn)的分裂：當(dāng)一個(gè)節(jié)點(diǎn)不夠純（單一分類占比不夠大或者說信息熵較大）時(shí)，則選擇將這一節(jié)點(diǎn)進(jìn)行分裂。2.決策邊界的確定：選擇正確的決策邊界（DecisionBoundary），使分出的節(jié)點(diǎn)盡量純，信息增益（熵減少的值）盡可能大。3.重復(fù)及停止生長(zhǎng)：重復(fù)1，2步驟，直到***為0或樹達(dá)到最大深度。為避免過擬合，決策樹算法一般需要制定樹分裂的最大深度。到達(dá)這一深度后，即使熵不等于0，樹也不會(huì)繼續(xù)進(jìn)行分裂。

下面以超級(jí)知名的鳶尾花數(shù)據(jù)集舉例來說明。這個(gè)數(shù)據(jù)集含有四個(gè)特征：花瓣的長(zhǎng)度（petallength）、花瓣的寬度(petalwidth)、花萼的長(zhǎng)度(sepallength)和花萼的寬度(sepalwidth)。預(yù)測(cè)目標(biāo)是鳶尾花的種類irissetosa,irisversicolor和irisvirginica。

建立決策樹模型的目標(biāo)是根據(jù)特征盡可能正確地將樣本劃分到三個(gè)不同的“陣營(yíng)”中。

根結(jié)點(diǎn)的選擇基于全部數(shù)據(jù)集，使用了貪婪算法：遍歷所有的特征，選擇可以使信息熵降到最低、基尼不***最低的特征。

如上圖根節(jié)點(diǎn)的決策邊界為'petalwidth=0.8cm'。那么這個(gè)決策邊界是怎么決定的呢？-遍歷所有可能的決策邊界（需要注意的是，所有可能的決策邊界代表的是該子集中該特征所有的值，不是以固定增幅遍歷一個(gè)區(qū)間內(nèi)的所有值！那樣很沒有必要的～）-計(jì)算新建的兩個(gè)子集的基尼不***。-選擇可以使新的子集達(dá)到最小基尼不***的分割閾值。這個(gè)“最小”可以指兩個(gè)子集的基尼不***的和或平均值。

ID3是最早提出的決策樹算法。ID3算法的核心是在決策樹各個(gè)節(jié)點(diǎn)上根據(jù)信息增益來選擇進(jìn)行劃分的特征，然后遞歸地構(gòu)建決策樹。-缺點(diǎn)：（1）沒有剪枝（2）只能用于處理離散特征（3）采用信息增益作為選擇最優(yōu)劃分特征的標(biāo)準(zhǔn)，但是信息增益會(huì)偏向那些取值較多的特征(例如，如果存在唯一標(biāo)識(shí)屬性身份證號(hào)，則ID3會(huì)選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對(duì)分類幾乎毫無用處。)

C4.5與ID3相似，但對(duì)ID3進(jìn)行了改進(jìn)：-引入“悲觀剪枝”策略進(jìn)行后剪枝-信息增益率作為劃分標(biāo)準(zhǔn)-將連續(xù)特征離散化，假設(shè)n個(gè)樣本的連續(xù)特征A有m個(gè)取值，C4.5將其排序并取相鄰兩樣本值的平均數(shù)共m-1個(gè)劃分點(diǎn)，分別計(jì)算以該劃分點(diǎn)作為二元分類點(diǎn)時(shí)的信息增益，并選擇信息增益最大的點(diǎn)作為該連續(xù)特征的二元離散分類點(diǎn)；-可以處理缺失值

對(duì)于缺失值的處理可以分為兩個(gè)子問題：（1）在特征值缺失的情況下進(jìn)行劃分特征的選擇？（即如何計(jì)算特征的信息增益率）C4.5中對(duì)于具有缺失值特征，用沒有缺失的樣本子集所占比重來折算；（2）選定該劃分特征，對(duì)于缺失該特征值的樣本如何處理？（即到底把這個(gè)樣本劃分到哪個(gè)結(jié)點(diǎn)里）C4.5的做法是將樣本同時(shí)劃分到所有子節(jié)點(diǎn)，不過要調(diào)整樣本的權(quán)重值，其實(shí)也就是以不同概率劃分到不同節(jié)點(diǎn)中。

（1）剪枝策略可以再優(yōu)化；（2）C4.5用的是多叉樹，用二叉樹效率更高；（3）C4.5只能用于分類；（4）C4.5使用的熵模型擁有大量耗時(shí)的對(duì)數(shù)運(yùn)算，連續(xù)值還有排序運(yùn)算；（5）C4.5在構(gòu)造樹的過程中，對(duì)數(shù)值屬性值需要按照其大小進(jìn)行排序，從中選擇一個(gè)分割點(diǎn)，所以只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時(shí)，程序無法運(yùn)行。

可以用于分類，也可以用于回歸問題。CART算法使用了基尼系數(shù)取代了信息熵模型，計(jì)算復(fù)雜度更低。

CART包含的基本過程有分裂，剪枝和樹選擇。分裂：分裂過程是一個(gè)二叉遞歸劃分過程，其輸入和預(yù)測(cè)特征既可以是連續(xù)型的也可以是離散型的，CART沒有停止準(zhǔn)則，會(huì)一直生長(zhǎng)下去；剪枝：采用“代價(jià)復(fù)雜度”剪枝，從最大樹開始，每次選擇訓(xùn)練數(shù)據(jù)熵對(duì)整體性能貢獻(xiàn)最小的那個(gè)分裂節(jié)點(diǎn)作為下一個(gè)剪枝對(duì)象，直到只剩下根節(jié)點(diǎn)。CART會(huì)產(chǎn)生一系列嵌套的剪枝樹，需要從中選出一顆最優(yōu)的決策樹；樹選擇：用單獨(dú)的測(cè)試集評(píng)估每棵剪枝樹的預(yù)測(cè)性能（也可以用交叉驗(yàn)證）。

（1）C4.5為多叉樹，運(yùn)算速度慢，CART為二叉樹，運(yùn)算速度快；（2）C4.5只能分類，CART既可以分類也可以回歸；（3）CART使用Gini系數(shù)作為變量的不***量，減少了大量的對(duì)數(shù)運(yùn)算；（4）CART采用代理測(cè)試來估計(jì)缺失值，而C4.5以不同概率劃分到不同節(jié)點(diǎn)中；（5）CART采用“基于代價(jià)復(fù)雜度剪枝”方法進(jìn)行剪枝，而C4.5采用悲觀剪枝方法。

（1）決策樹易于理解和解釋，可以可視化分析，容易提取出規(guī)則（2）可以同時(shí)處理分類型和數(shù)值型數(shù)據(jù)（3）可以處理缺失值（4）運(yùn)行速度比較快（使用Gini的快于使用信息熵，因?yàn)樾畔㈧厮惴ㄓ衛(wèi)og）

（1）容易發(fā)生過擬合（集成算法如隨機(jī)森林可以很大程度上減少過擬合）（2）容易忽略數(shù)據(jù)集中屬性的相互關(guān)聯(lián)；（3）對(duì)于那些各類別樣本數(shù)量不一致的數(shù)據(jù)，在決策樹中，進(jìn)行屬性劃分時(shí)，不同的判定準(zhǔn)則會(huì)帶來不同的屬性選擇傾向。

寫在后面：這個(gè)專輯主要是本小白在機(jī)器學(xué)習(xí)算法學(xué)習(xí)過程中的一些總結(jié)筆記和心得，如有不對(duì)之處還請(qǐng)各位大神多多指正?。P(guān)于決策樹的剪枝還有很多沒有搞懂，之后弄明白了會(huì)再單獨(dú)出一篇總結(jié)噠）

參考資料鏈接：1.https://machinelearningmastery.com/what-is-information-entropy/2.https://zhuanlan.zhihu.com/p/296792773.https://machinelearningmastery.com/information-gain-and-mutual-information/4.https://victorzhou.com/blog/gini-impurity/5.https://sci2s.ugr.es/noisydata6.https://towardsdatascience.com/understanding-decision-trees-once-and-for-all-2d891b1be5797.https://blog.csdn.net/weixin_36586536/article/details/804684268.https://zhuanlan.zhihu.com/p/85731206