99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

決策樹之ID3算法及其Python實現(xiàn)

決策樹之ID3算法及其Python實現(xiàn)

新榮ssl適用于網(wǎng)站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：028-86922220（備注：SSL證書合作）期待與您的合作！

1. 決策樹背景知識

??決策樹是數(shù)據(jù)挖掘中最重要且最常用的方法之一，主要應用于數(shù)據(jù)挖掘中的分類和預測。決策樹是知識的一種呈現(xiàn)方式，決策樹中從頂點到每個結點的路徑都是一條分類規(guī)則。決策樹算法最先基于信息論發(fā)展起來，經(jīng)過幾十年發(fā)展，目前常用的算法有：ID3、C4.5、CART算法等。

2. 決策樹一般構建過程

??構建決策樹是一個自頂向下的過程。樹的生長過程是一個不斷把數(shù)據(jù)進行切分細分的過程，每一次切分都會產(chǎn)生一個數(shù)據(jù)子集對應的節(jié)點。從包含所有數(shù)據(jù)的根節(jié)點開始，根據(jù)選取分裂屬性的屬性值把訓練集劃分成不同的數(shù)據(jù)子集，生成由每個訓練數(shù)據(jù)子集對應新的非葉子節(jié)點。對生成的非葉子節(jié)點再重復以上過程，直到滿足特定的終止條件，停止對數(shù)據(jù)子集劃分，生成數(shù)據(jù)子集對應的葉子節(jié)點，即所需類別。測試集在決策樹構建完成后檢驗其性能。如果性能不達標，我們需要對決策樹算法進行改善，直到達到預期的性能指標。

??注：分裂屬性的選取是決策樹生產(chǎn)過程中的關鍵，它決定了生成的決策樹的性能、結構。分裂屬性選擇的評判標準是決策樹算法之間的根本區(qū)別。

3. ID3算法分裂屬性的選擇——信息增益

??屬性的選擇是決策樹算法中的核心。是對決策樹的結構、性能起到?jīng)Q定性的作用。ID3算法基于信息增益的分裂屬性選擇。基于信息增益的屬性選擇是指以信息熵的下降速度作為選擇屬性的方法。它以的信息論為基礎，選擇具有最高信息增益的屬性作為當前節(jié)點的分裂屬性。選擇該屬性作為分裂屬性后，使得分裂后的樣本的信息量最大，不確定性最小，即熵最小。

??信息增益的定義為變化前后熵的差值，而熵的定義為信息的期望值，因此在了解熵和信息增益之前，我們需要了解信息的定義。

??信息：分類標簽xi 在樣本集 S 中出現(xiàn)的頻率記為 p(xi)，則 xi 的信息定義為：?log2p(xi) 。

??分裂之前樣本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 為分類標簽的個數(shù)。

??通過屬性A分裂之后樣本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始樣本集通過屬性A的屬性值劃分為 m 個子樣本集，|Sj| 表示第j個子樣本集中樣本數(shù)量，|S| 表示分裂之前數(shù)據(jù)集中樣本總數(shù)量。

??通過屬性A分裂之后樣本集的信息增益：InfoGain(S,A)=E(S)?EA(S)

??注：分裂屬性的選擇標準為：分裂前后信息增益越大越好，即分裂后的熵越小越好。

4. ID3算法

??ID3算法是一種基于信息增益屬性選擇的決策樹學習方法。核心思想是：通過計算屬性的信息增益來選擇決策樹各級節(jié)點上的分裂屬性，使得在每一個非葉子節(jié)點進行測試時，獲得關于被測試樣本最大的類別信息。基本方法是：計算所有的屬性，選擇信息增益最大的屬性分裂產(chǎn)生決策樹節(jié)點，基于該屬性的不同屬性值建立各分支，再對各分支的子集遞歸調(diào)用該方法建立子節(jié)點的分支，直到所有子集僅包括同一類別或沒有可分裂的屬性為止。由此得到一棵決策樹，可用來對新樣本數(shù)據(jù)進行分類。

ID3算法流程：

(1) 創(chuàng)建一個初始節(jié)點。如果該節(jié)點中的樣本都在同一類別，則算法終止，把該節(jié)點標記為葉節(jié)點，并用該類別標記。

(2) 否則，依據(jù)算法選取信息增益最大的屬性，該屬性作為該節(jié)點的分裂屬性。

(3) 對該分裂屬性中的每一個值，延伸相應的一個分支，并依據(jù)屬性值劃分樣本。

(4) 使用同樣的過程，自頂向下的遞歸，直到滿足下面三個條件中的一個時就停止遞歸。

??A、待分裂節(jié)點的所有樣本同屬于一類。

??B、訓練樣本集中所有樣本均完成分類。

??C、所有屬性均被作為分裂屬性執(zhí)行一次。若此時，葉子結點中仍有屬于不同類別的樣本時，選取葉子結點中包含樣本最多的類別，作為該葉子結點的分類。

ID3算法優(yōu)缺點分析

優(yōu)點：構建決策樹的速度比較快，算法實現(xiàn)簡單，生成的規(guī)則容易理解。

缺點：在屬性選擇時，傾向于選擇那些擁有多個屬性值的屬性作為分裂屬性，而這些屬性不一定是最佳分裂屬性；不能處理屬性值連續(xù)的屬性；無修剪過程，無法對決策樹進行優(yōu)化，生成的決策樹可能存在過度擬合的情況。

python中的sklearn中決策樹使用的是哪一種算法

要弄清楚這個問題，首先要弄懂決策樹三大流行算法ID3、C4.5和CART的原理，以及sklearn框架下DecisionTreeClassifier的幫助文檔。

3個算法的主要區(qū)別在于度量信息方法、選擇節(jié)點特征還有分支數(shù)量的不同。

ID3，采用熵（entropy）來度量信息不確定度，選擇“信息增益”最大的作為節(jié)點特征，它是多叉樹，即一個節(jié)點可以有多個分支。

C4.5，同樣采用熵（entropy）來度量信息不確定度，選擇“信息增益比”最大的作為節(jié)點特征，同樣是多叉樹，即一個節(jié)點可以有多個分支。

CART，采用基尼指數(shù)（Gini index）來度量信息不純度，選擇基尼指數(shù)最小的作為節(jié)點特征，它是二叉樹，即一個節(jié)點只分兩支。

然后你認真閱讀sklearn的DecisionTreeClassifier的幫助文檔，可以發(fā)現(xiàn)，度量信息的方法默認是Gini，但可以改成entropy，請按需選擇；構建的樹是二叉樹；可以通過設置max_deepth、max_leaf等來實現(xiàn)“剪枝”，這是根據(jù)CART的損失函數(shù)減少的理論進行的。

所以總結說，如果信息度量方法按照默認的設置，那么sklearn所用的決策樹分類器就是CART，如果改成了entropy，那么只是使用了別的度量方法而已。其實兩者差不多。

決策樹（Decision Tree）

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

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

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

我們可以用計算事件發(fā)生的概率來計算事件的信息，又稱“香農(nóng)信息”（ Shannon Information ）。一個離散事件x的信息可以表示為：

h(x) = -log(p(x))

p() 代表事件x發(fā)生的概率， log() 為以二為底的對數(shù)函數(shù)，即一個事件的信息量就是這個事件發(fā)生的概率的負對數(shù)。選擇以二為底的對數(shù)函數(shù)代表計算信息的單位是二進制。因為概率p(x)小于1，所以負號就保證了信息熵永遠不為負數(shù)。當事件的概率為1時，也就是當某事件百分之百發(fā)生時，信息為0。

熵（ entropy ），又稱“香農(nóng)熵”（ Shannon entropy ），表示一個隨機變量的分布所需要的平均比特數(shù)。一個隨機變量的信息熵可以表示為：

H(x) = -sum(each k in K p(k)log(p(k)))

K表示變量x所可能具有的所有狀態(tài)（所有事件），將發(fā)生特定事件的概率和該事件的信息相乘，最后加和，即可得到該變量的信息熵。可以理解為，信息熵就是平均而言發(fā)生一個事件我們得到的信息量大小。所以數(shù)學上，信息熵其實是事件信息量的期望。

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

當一個事件主導時，比如偏態(tài)分布（ Skewed Probability Distribution ），不確定性減小，信息熵較低（low entropy）；當所有事件發(fā)生概率相同時，比如均衡分布（ Balanced Probability Distribution ），不確定性極大，信息熵較高（high entropy）。

由以上的香農(nóng)信息公式可知，信息熵主要有三條性質(zhì)：

- 單調(diào)性 。發(fā)生概率越高的事件，其所攜帶的信息熵越低。比如一個真理的不確定性是極低的，那么它所攜帶的信息熵就極低。

- 非負性 。信息熵不能為負。單純從邏輯層面理解，如果得知了某個信息后，卻增加了不確定性，這也是不合邏輯的。

- 可加性 。即多隨機事件同時發(fā)生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和。

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

可以理解為，兩個隨機變量的互信息度量了兩個變量間相互依賴的程度。X 和 Y的互信息可以表示為：

I(X;Y) = H(X) - H(X|Y)

H(X)是X的信息熵，H(X|Y)是已知Y的情況下，X的信息熵。結果的單位是比特。

簡單來說，互信息的性質(zhì)為：

- I(X;Y)=0 互信息永遠不可能為負

- H(X) - H(X|Y) = I(X;Y) = I (Y;X) = H(Y) - H(Y|X) 互信息是對稱的

-當X，Y獨立的時候， I(X;Y) = 0 互信息值越大，兩變量相關性越強。

-當X，Y知道一個就能推斷另一個的時候， I(X;Y) = H(Y) = H(X)

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

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

那數(shù)據(jù)集的信息熵又是怎么計算的呢？比如一個常見的0,1二分類問題，我們可以計算它的熵為：

Entropy = -(p(0) * log(P(0)) + p(1)\ * log(P(1)))

當該數(shù)據(jù)集為50/50的數(shù)據(jù)集時，它的信息熵是最大的（1bit）。而10/90的數(shù)據(jù)集將會大大減少結果的不確定性，減小數(shù)據(jù)集的信息熵（約為0.469bit）。

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

信息增益是提供了一種可以使用信息熵計算數(shù)據(jù)集經(jīng)過一定的規(guī)則（比如決策樹中的一系列規(guī)則）進行數(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é)省的比特數(shù)。

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

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

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

這種時候，信息增益率就起到了很重要的作用。

gR(D,A)=g(D,A)/HA(D)

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

在CART算法中，基尼不純度表示一個隨機選中的樣本被分錯類別的可能性，即這個樣本被選中的概率乘以它被分錯的概率。當一個節(jié)點中所有樣本均為一種時（沒有被分錯的樣本），基尼不純度達到最低值0。

舉例來說，如果有綠色和藍色兩類數(shù)據(jù)點，各占一半（藍色50%，綠色50%）。那么我們隨機分類，有以下四種情況：

-分為藍色，但實際上是綠色（?），概率25%

-分為藍色，實際上也是藍色（??），概率25%

-分為綠色，實際上也是綠色（??），概率25%

-分為綠色，但實際上是藍色（?），概率25%

那么將任意一個數(shù)據(jù)點分錯的概率為25%+25% = 50%。基尼不純度為0.5。

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

噪音數(shù)據(jù)簡單來說就是會對模型造成誤導的數(shù)據(jù)。分為類別噪聲（ class noise 或 label noise ）和 變量噪聲（ attribute noise ）。類別噪聲指的的是被錯誤標記的錯誤數(shù)據(jù)，比如兩個相同的樣本具有不同的標簽等情況。變量噪聲指的是有問題的變量，比如缺失值、異常值和無關值等。

決策樹其實是一種圖結構，由節(jié)點和邊構成。

-根節(jié)點：只有出邊沒有入邊。包含樣本全集，表示一個對樣本最初的判斷。

-內(nèi)部節(jié)點：一個入邊多個出邊。表示一個特征或是屬性。每個內(nèi)部節(jié)點都是一個判斷條件，包含數(shù)據(jù)集中從根節(jié)點到該節(jié)點所有滿足條件的數(shù)據(jù)的集合。

-葉節(jié)點：一個入邊無出邊。表示一個類，對應于決策結果。

決策樹的生成主要分為三個步驟：

1. 節(jié)點的分裂 ：當一個節(jié)點不夠純（單一分類占比不夠大或者說信息熵較大）時，則選擇將這一節(jié)點進行分裂。

2. 決策邊界的確定 ：選擇正確的決策邊界（ Decision Boundary ），使分出的節(jié)點盡量純，信息增益（熵減少的值）盡可能大。

3. 重復及停止生長 ：重復1，2步驟，直到純度為0或樹達到最大深度。為避免過擬合，決策樹算法一般需要制定樹分裂的最大深度。到達這一深度后，即使熵不等于0，樹也不會繼續(xù)進行分裂。

下面以超級知名的鳶尾花數(shù)據(jù)集舉例來說明。

這個數(shù)據(jù)集含有四個特征：花瓣的長度（ petal length ）、花瓣的寬度( petal width )、花萼的長度( sepal length )和花萼的寬度( sepal width )。預測目標是鳶尾花的種類 iris setosa, iris versicolor 和 iris virginica 。

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

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

如上圖，根節(jié)點的決策邊界為' petal width = 0.8cm '。那么這個決策邊界是怎么決定的呢？

-遍歷所有可能的決策邊界（需要注意的是，所有可能的決策邊界代表的是該子集中該特征所有的值，不是以固定增幅遍歷一個區(qū)間內(nèi)的所有值！那樣很沒有必要的～）

-計算新建的兩個子集的基尼不純度。

-選擇可以使新的子集達到最小基尼不純度的分割閾值。這個“最小”可以指兩個子集的基尼不純度的和或平均值。

ID3是最早提出的決策樹算法。ID3算法的核心是在決策樹各個節(jié)點上根據(jù) 信息增益 來選擇進行劃分的特征，然后遞歸地構建決策樹。

- 缺點 ：

（1）沒有剪枝

（2）只能用于處理離散特征

（3）采用信息增益作為選擇最優(yōu)劃分特征的標準，然而信息增益會偏向那些取值較多的特征(例如，如果存在唯一標識屬性身份證號，則ID3會選擇它作為分裂屬性，這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處。)

C4.5 與ID3相似，但對ID3進行了改進：

-引入“悲觀剪枝”策略進行后剪枝

-信息增益率作為劃分標準

-將連續(xù)特征離散化，假設 n 個樣本的連續(xù)特征 A 有 m 個取值，C4.5 將其排序并取相鄰兩樣本值的平均數(shù)共 m-1 個劃分點，分別計算以該劃分點作為二元分類點時的信息增益，并選擇信息增益最大的點作為該連續(xù)特征的二元離散分類點；

-可以處理缺失值

對于缺失值的處理可以分為兩個子問題：

（1）在特征值缺失的情況下進行劃分特征的選擇？（即如何計算特征的信息增益率）

C4.5 中對于具有缺失值特征，用沒有缺失的樣本子集所占比重來折算；

（2）選定該劃分特征，對于缺失該特征值的樣本如何處理？（即到底把這個樣本劃分到哪個結點里）

C4.5 的做法是將樣本同時劃分到所有子節(jié)點，不過要調(diào)整樣本的權重值，其實也就是以不同概率劃分到不同節(jié)點中。

（1）剪枝策略可以再優(yōu)化；

（2）C4.5 用的是多叉樹，用二叉樹效率更高；

（3）C4.5 只能用于分類；

（4）C4.5 使用的熵模型擁有大量耗時的對數(shù)運算，連續(xù)值還有排序運算；

（5）C4.5 在構造樹的過程中，對數(shù)值屬性值需要按照其大小進行排序，從中選擇一個分割點，所以只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當訓練集大得無法在內(nèi)存容納時，程序無法運行。

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

CART 包含的基本過程有 分裂，剪枝和樹選擇 。

分裂 ：分裂過程是一個二叉遞歸劃分過程，其輸入和預測特征既可以是連續(xù)型的也可以是離散型的，CART 沒有停止準則，會一直生長下去；

剪枝 ：采用“代價復雜度”剪枝，從最大樹開始，每次選擇訓練數(shù)據(jù)熵對整體性能貢獻最小的那個分裂節(jié)點作為下一個剪枝對象，直到只剩下根節(jié)點。CART 會產(chǎn)生一系列嵌套的剪枝樹，需要從中選出一顆最優(yōu)的決策樹；

樹選擇 ：用單獨的測試集評估每棵剪枝樹的預測性能（也可以用交叉驗證）。

（1）C4.5 為多叉樹，運算速度慢，CART 為二叉樹，運算速度快；

（2）C4.5 只能分類，CART 既可以分類也可以回歸；

（3）CART 使用 Gini 系數(shù)作為變量的不純度量，減少了大量的對數(shù)運算；

（4）CART 采用代理測試來估計缺失值，而 C4.5 以不同概率劃分到不同節(jié)點中；

（5）CART 采用“基于代價復雜度剪枝”方法進行剪枝，而 C4.5 采用悲觀剪枝方法。

（1）決策樹易于理解和解釋，可以可視化分析，容易提取出規(guī)則

（2）可以同時處理分類型和數(shù)值型數(shù)據(jù)

（3）可以處理缺失值

（4）運行速度比較快（使用Gini的快于使用信息熵，因為信息熵算法有l(wèi)og）

（1）容易發(fā)生過擬合（集成算法如隨機森林可以很大程度上減少過擬合）

（2）容易忽略數(shù)據(jù)集中屬性的相互關聯(lián)；

（3）對于那些各類別樣本數(shù)量不一致的數(shù)據(jù)，在決策樹中，進行屬性劃分時，不同的判定準則會帶來不同的屬性選擇傾向。

寫在后面：這個專輯主要是本小白在機器學習算法學習過程中的一些總結筆記和心得，如有不對之處還請各位大神多多指正！（關于決策樹的剪枝還有很多沒有搞懂，之后弄明白了會再單獨出一篇總結噠）

參考資料鏈接：

1.

2.

3.

4.

5.

6.

7.

8.

新聞標題：python決策樹函數(shù) python 決策樹算法
網(wǎng)頁鏈接：http://www.ef60e0e.cn/article/doeepjg.html