決策樹演算法比較

㈠ 決策樹計算公式

決策樹計算公式公式：H(X)=–∑P(x)log[P(x)]H(x)：表示熵 P(x)：表示x事件發生的概率。

決策樹法的具體計算過程：

①繪制決策樹圖形，按上述要求由左向右順序展開。

②計算每個結點的期望值，計算公式為：

狀態結點的期望值=Σ（損益值×概率值）×經營年限

③剪枝，即進行方案的選優。

方案凈效果=該方案狀態結點的期望值-該方案投資額

㈡ 決策樹原理及演算法比較

決策樹是什麼？

    和線性回歸一樣是一種模型，內部節點和葉節點。實現分類，內部節點和葉節點通過有向線（分類規      則）連接起來

決策樹的目標是什麼？

    決策樹通過對數據復雜度的計算，建立特徵分類標准，確定最佳分類特徵。

    表現為「熵」（entropy）和信息增益（information gain），基於決策樹思想的三種演算法：ID3，C4.5,CART演算法，三種演算法的信息衡量的指標也不同.

    熵來表示信息的復雜度，熵越大，信息也就越復雜，公式如下：

那些演算法能夠實現決策樹？

    在決策樹構建過程中，什麼是比較重要的。特徵選擇（按照熵變計算），演算法產生最重要的部分，

決策樹中葉節點的分類比較純，

節點順序的排列規則：

熵變：

數據的預處理：

改進思路一般有兩個1，換演算法；2，調參數

做好數據的預處理：

1，做好特徵選擇；

2，做好數據離散化、異常值處理、缺失填充

分類器：

在決策樹中，從根到達任意一個葉節點的之間最長路徑的長度，表示對應的演算法排序中最壞情況下的比較次數。這樣一個比較演算法排序中的最壞情況的比較次數就與其決策樹的高度相同，同時如果決策樹中每種排列以可達葉子的形式出現，那麼關於其決策樹高度的下界也就是關於比較排序演算法運行時間的下界，

ID3演算法存在的缺點：

    1，ID3演算法在選擇根節點和內部節點分支屬性時，採用信息增益作為評價標准。信息增益的缺點是傾向於選擇取值較多的屬性

    2，當數據為連續性變數的時候，ID3演算法就不是一個合理的演算法的模型了

C4.5信息增益比率，

     1，在信息增益的基礎上除以split-info，是將信息增益改為信息增益比，以解決取值較多的屬性的問題，另外它還可以處理連續型屬性，其判別標準是θ，

      2，C4.5演算法利用增益/熵值，克服了樹生長的過程中，總是『貪婪』選擇變數分類多的進行分類

      3，處理來內需型變數，C4.5的分類樹的分支就是兩條

衡量指標：

（1）信息增益

基於ID3演算法的信息增益對於判定連續型變數的時候病不是最優選擇，C4.5演算法用了信息增益率這個概念。

分類信息類的定義如下：

這個值表示將訓練數據集D劃分成對應屬性A測試的V個輸出v個劃分產生的信息，信息增益率定義為：

選擇最大信息增益率的屬性作為分裂屬性

Gini指標，CART

表明樣本的「純凈度」。Gini系數避免了信息增益產生的問題，

過擬合問題，非常好的泛化能力，有很好的推廣能力

Gini系數的計算：

在分類問題中，假設有k個類，樣本點屬於第k類的概率為Pk，則概率分布的gini指數的定義為：

如果樣本集合D根據某個特徵A被分割為D1，D2兩個部分，那麼在特徵A的提哦啊見下，集合D的gini指數的定義為：

Gini指數代表特徵A不同分組下的數據集D的不確定性，gini指數越大，樣本集合的不確定性也就越大，這一點和熵的概念相類似

決策樹原理介紹：

第三步：對於每個屬性執行劃分：

（1）該屬性為離散型變數

記樣本中的變數分為m中

窮舉m種取值分為兩類的劃分

對上述所有劃分計算GINI系數

（2）該屬性為連續型變數

將數據集中從小到大劃分

按順序逐一將兩個相臨值的均值作為分割點

對上述所有劃分計算GINI系數

學歷的劃分使得順序的劃分有個保證，化為連續型變數處理。

決策樹的生成演算法分為兩個步驟：

預剪枝和後剪枝  CCP（cost and complexity）演算法：在樹變小和變大的的情況有個判斷標准。誤差率增益值：α值為誤差的變化

決策樹的終止條件：

      1，某一個節點的分支所覆蓋的樣本都是同一類的時候

      2，某一個分支覆蓋的樣本的個數如果小於一個閾值，那麼也可以產生葉子節點，從而終止Tree-Growth

確定葉子結點的類：

      1，第一種方式，葉子結點覆蓋的樣本都屬於同一類

      2， 葉子節點覆蓋的樣本未必是同一類，所佔的大多數，那麼該葉子節點的類別就是那個佔大多數的類

㈢ 決策樹演算法總結

目錄

一、決策樹演算法思想

二、決策樹學習本質

三、總結

一、決策樹（decision tree）演算法思想：

決策樹是一種基本的分類與回歸方法。本文主要討論分類決策樹。決策樹模型呈樹形結構，在分類問題中，表示基於特徵對實例進行分類的過程。 它可以看做是if-then的條件集合，也可以認為是定義在特徵空間與類空間上的條件概率分布 。決策樹由結點和有向邊組成。結點有兩種類型：內部結點和葉結點，內部結點表示一個特徵或屬性，葉結點表示一個類。（橢圓表示內部結點，方塊表示葉結點）

         決策樹與if-then規則的關系

決策樹可以看做是多個if-then規則的集合。將決策樹轉換成if-then規則的過程是：由決策樹的根結點到葉結點的每一條路徑構建一條規則；路徑上的內部結點的特徵對應著規則的條件，而葉結點的類對應著規則的結論。決策樹的路徑或其對應的if-then規則集合具有一個重要的性質：互斥且完備。這就是說，每一個實例都被一條路徑或一條規則所覆蓋，且只被一條路徑或一條規則所覆蓋。這里的覆蓋是指實例的特徵與路徑上的特徵一致或實例滿足規則的條件。

         決策樹與條件概率分布的關系

決策樹還表示給定特徵條件下類的條件概率分布。這一條件概率分布定義在特徵空間的一個劃分上。將特徵空間劃分為互不相交的單元或區域，並在每個單元定義一個類的概率分布，就構成一個條件概率分布。決策樹的一條路徑對應於劃分中的一個單元。決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成。

         決策樹模型的優點

決策樹模型具有可讀性，分類速度快。學習時，利用訓練數據，根據損失函數最小化原則建立決策樹模型；預測時，對新的數據，利用決策樹模型進行分類 。

二、決策樹學習本質：

決策樹學習是從訓練數據集中歸納一組分類規則、與訓練數據集不相矛盾的決策樹可能有多個，也可能一個沒有。我們需要訓練一個與訓練數據矛盾較小的決策樹，同時具有很好的泛化能力。從另一個角度看 決策樹學習是訓練數據集估計條件概率模型 。基於特徵空間劃分的類的條件概率模型有無窮多個。我們選擇的條件概率模型應該是不僅對訓練數據有很好的擬合，而且對未知數據有很好的預測。 決策樹的學習使用損失函數表示這一目標，通常的損失函數是正則化的極大似然函數。決策樹的學習策略是以損失函數為目標函數的最小化。當損失函數確定後，決策樹學習問題變為損失函數意義下選擇最優決策樹的問題。這一過程通常是一個遞歸選擇最優特徵，並根據特徵對訓練數據進行分割，使得對各個子數據集有一個最好分類的過程。這一過程對應著特徵選擇、決策樹的生成、決策樹的剪枝。

         特徵選擇 ： 在於選擇對訓練數據具有分類能力的特徵，這樣可以提高決策樹的學習效率。

         決策樹的生成 ： 根據不同特徵作為根結點，劃分不同子結點構成不同的決策樹。

         決策樹的選擇 ：哪種特徵作為根結點的決策樹信息增益值最大，作為最終的決策樹（最佳分類特徵）。

         信息熵 ： 在資訊理論與概率統計中，熵是表示隨機變數不確定性的度量。設X是一個取有限個值的離散隨機變數，其概率分布為P(X= ) = ，i=1，2，3...n，則隨機變數X的熵定義為

        H(X) =  —  ，0 <=  H(X) <= 1，熵越大，隨機變數的不確定性就越大。

        條件熵（Y|X） ： 表示在已知隨機變數X的條件下隨機變數Y的不確定性。

         信息增益  ： 表示得知特徵X的信息而使得類Y的信息的不確定性減少的程度。

        信息增益  = 信息熵(父結點熵 ) — 條件熵（子結點加權熵）

三、 總結 ：

        優點

        1、可解釋性高，能處理非線性的數據，不需要做數據歸一化，對數據分布沒有偏好。

        2、可用於特徵工程，特徵選擇。

        3、可轉化為規則引擎。

        缺點

        1、啟發式生成，不是最優解。

        2、容易過擬合。

        3、微小的數據改變會改變整個數的形狀。

        4、對類別不平衡的數據不友好。

㈣ 常見決策樹分類演算法都有哪些

在機器學習中，有一個體系叫做決策樹，決策樹能夠解決很多問題。在決策樹中，也有很多需要我們去學習的演算法，要知道，在決策樹中，每一個演算法都是實用的演算法，所以了解決策樹中的演算法對我們是有很大的幫助的。在這篇文章中我們就給大家介紹一下關於決策樹分類的演算法，希望能夠幫助大家更好地去理解決策樹。
1.C4.5演算法
C4.5演算法就是基於ID3演算法的改進，這種演算法主要包括的內容就是使用信息增益率替換了信息增益下降度作為屬性選擇的標准；在決策樹構造的同時進行剪枝操作；避免了樹的過度擬合情況；可以對不完整屬性和連續型數據進行處理；使用k交叉驗證降低了計算復雜度；針對數據構成形式，提升了演算法的普適性等內容，這種演算法是一個十分使用的演算法。
2.CLS演算法
CLS演算法就是最原始的決策樹分類演算法，基本流程是，從一棵空數出發，不斷的從決策表選取屬性加入數的生長過程中，直到決策樹可以滿足分類要求為止。CLS演算法存在的主要問題是在新增屬性選取時有很大的隨機性。
3.ID3演算法
ID3演算法就是對CLS演算法的最大改進是摒棄了屬性選擇的隨機性，利用信息熵的下降速度作為屬性選擇的度量。ID3是一種基於信息熵的決策樹分類學習演算法，以信息增益和信息熵，作為對象分類的衡量標准。ID3演算法結構簡單、學習能力強、分類速度快適合大規模數據分類。但同時由於信息增益的不穩定性，容易傾向於眾數屬性導致過度擬合，演算法抗干擾能力差。
3.1.ID3演算法的優缺點
ID3演算法的優點就是方法簡單、計算量小、理論清晰、學習能力較強、比較適用於處理規模較大的學習問題。缺點就是傾向於選擇那些屬性取值比較多的屬性，在實際的應用中往往取值比較多的屬性對分類沒有太大價值、不能對連續屬性進行處理、對雜訊數據比較敏感、需計算每一個屬性的信息增益值、計算代價較高。
3.2.ID3演算法的核心思想
根據樣本子集屬性取值的信息增益值的大小來選擇決策屬性，並根據該屬性的不同取值生成決策樹的分支，再對子集進行遞歸調用該方法，當所有子集的數據都只包含於同一個類別時結束。最後，根據生成的決策樹模型，對新的、未知類別的數據對象進行分類。
在這篇文章中我們給大家介紹了決策樹分類演算法的具體內容，包括有很多種演算法。從中我們不難發現決策樹的演算法都是經過不不斷的改造趨於成熟的。所以說，機器學習的發展在某種程度上就是由於這些演算法的進步而來的。

㈤ 數據挖掘-決策樹演算法

決策樹演算法是一種比較簡易的監督學習分類演算法，既然叫做決策樹，那麼首先他是一個樹形結構，簡單寫一下樹形結構（數據結構的時候學過不少了）。

樹狀結構是一個或多個節點的有限集合，在決策樹里，構成比較簡單，有如下幾種元素：

在決策樹中，每個葉子節點都有一個類標簽，非葉子節點包含對屬性的測試條件，用此進行分類。
所以個人理解，決策樹就是 對一些樣本，用樹形結構對樣本的特徵進行分支，分到葉子節點就能得到樣本最終的分類，而其中的非葉子節點和分支就是分類的條件，測試和預測分類就可以照著這些條件來走相應的路徑進行分類。

根據這個邏輯，很明顯決策樹的關鍵就是如何找出決策條件和什麼時候算作葉子節點即決策樹終止。

決策樹的核心是為不同類型的特徵提供表示決策條件和對應輸出的方法，特徵類型和劃分方法包括以下幾個：

注意，這些圖中的第二層都是分支，不是葉子節點。

如何合理的對特徵進行劃分，從而找到最優的決策模型呢？在這里需要引入信息熵的概念。

先來看熵的概念：

在數據集中，參考熵的定義，把信息熵描述為樣本中的不純度，熵越高，不純度越高，數據越混亂（越難區分分類）。

例如：要給（0，1）分類，熵是0，因為能明顯分類，而均衡分布的（0.5，0.5）熵比較高，因為難以劃分。

信息熵的計算公式為：
其中 代表信息熵。 是類的個數， 代表在 類時 發生的概率。
另外有一種Gini系數，也可以用來衡量樣本的不純度：
其中 代表Gini系數，一般用於決策樹的 CART演算法 。

舉個例子：

如果有上述樣本，那麼樣本中可以知道，能被分為0類的有3個，分為1類的也有3個，那麼信息熵為：
Gini系數為：
總共有6個數據，那麼其中0類3個，佔比就是3/6，同理1類。

我們再來計算一個分布比較一下：

信息熵為：
Gini系數為：

很明顯，因為第二個分布中，很明顯這些數偏向了其中一類，所以 純度更高 ，相對的信息熵和Gini系數較低。

有了上述的概念，很明顯如果我們有一組數據要進行分類，最快的建立決策樹的途徑就是讓其在每一層都讓這個樣本純度最大化，那麼就要引入信息增益的概念。

所謂增益，就是做了一次決策之後，樣本的純度提升了多少（不純度降低了多少），也就是比較決策之前的樣本不純度和決策之後的樣本不純度，差越大，效果越好。
讓信息熵降低，每一層降低的越快越好。
度量這個信息熵差的方法如下：
其中 代表的就是信息熵（或者其他可以度量不純度的系數）的差， 是樣本(parent是決策之前， 是決策之後)的信息熵（或者其他可以度量不純度的系數）， 為特徵值的個數， 是原樣本的記錄總數， 是與決策後的樣本相關聯的記錄個數。

當選擇信息熵作為樣本的不純度度量時，Δ就叫做信息增益 。

我們可以遍歷每一個特徵，看就哪個特徵決策時，產生的信息增益最大，就把他作為當前決策節點，之後在下一層繼續這個過程。

舉個例子：

如果我們的目標是判斷什麼情況下，銷量會比較高（受天氣，周末，促銷三個因素影響），根據上述的信息增益求法，我們首先應該找到根據哪個特徵來決策，以信息熵為例：

首先肯定是要求 ，也就是銷量這個特徵的信息熵：

接下來，就分別看三個特徵關於銷量的信息熵，先看天氣，天氣分為好和壞兩種，其中天氣為好的條件下，銷量為高的有11條，低的有6條；天氣壞時，銷量為高的有7條，銷量為低的有10條，並且天氣好的總共17條，天氣壞的總共17條。

分別計算天氣好和天氣壞時的信息熵，天氣好時：

根據公式 ，可以知道，N是34，而天氣特徵有2個值，則k=2，第一個值有17條可以關聯到決策後的節點，第二個值也是17條，則能得出計算：

再計算周末這個特徵，也只有兩個特徵值，一個是，一個否，其中是有14條，否有20條；周末為是的中有11條銷量是高，3條銷量低，以此類推有：


信息增益為：

另外可以得到是否有促銷的信息增益為0.127268。

可以看出，以周末為決策，可以得到最大的信息增益，因此根節點就可以用周末這個特徵進行分支：

注意再接下來一層的原樣本集，不是34個而是周末為「是」和「否」分別計算，為是的是14個，否的是20個。
這樣一層一層往下遞歸，直到判斷節點中的樣本是否都屬於一類，或者都有同一個特徵值，此時就不繼續往下分了，也就生成了葉子節點。

上述模型的決策樹分配如下：

需要注意的是，特徵是否出現需要在分支當中看，並不是整體互斥的，周末生成的兩個分支，一個需要用促銷來決策，一個需要用天氣，並不代表再接下來就沒有特徵可以分了，而是在促銷決策層下面可以再分天氣，另外一遍天氣決策下面可以再分促銷。

決策樹的模型比較容易解釋，看這個樹形圖就能很容易的說出分類的條件。

我們知道屬性有二元屬性、標稱屬性、序數屬性和連續屬性，其中二元、標稱和序數都是類似的，因為是離散的屬性，按照上述方式進行信息增益計算即可，而連續屬性與這三個不同。

對於連續的屬性，為了降低其時間復雜度，我們可以先將屬性內部排序，之後取相鄰節點的均值作為決策值，依次取每兩個相鄰的屬性值的均值，之後比較他們的不純度度量。

需要注意的是，連續屬性可能在決策樹中出現多次，而不是像離散的屬性一樣在一個分支中出現一次就不會再出現了。

用信息熵或者Gini系數等不純度度量有一個缺點，就是會傾向於將多分支的屬性優先分類——而往往這種屬性並不是特徵。

例如上面例子中的第一行序號，有34個不同的值，那麼信息熵一定很高，但是實際上它並沒有任何意義，因此我們需要規避這種情況，如何規避呢，有兩種方式：

公式如下：

其中k為劃分的總數，如果每個屬性值具有相同的記錄數，則 ，劃分信息等於 ，那麼如果某個屬性產生了大量劃分，則劃分信息很大，信息增益率低，就能規避這種情況了。

為了防止過擬合現象，往往會對決策樹做優化，一般是通過剪枝的方式，剪枝又分為預剪枝和後剪枝。

在構建決策樹時，設定各種各樣的條件如葉子節點的樣本數不大於多少就停止分支，樹的最大深度等，讓決策樹的層級變少以防止過擬合。
也就是在生成決策樹之前，設定了決策樹的條件。

後剪枝就是在最大決策樹生成之後，進行剪枝，按照自底向上的方式進行修剪，修剪的規則是，評估葉子節點和其父節點的代價函數，如果父節點的代價函數比較小，則去掉這個葉子節點。
這里引入的代價函數公式是：
其中 代表的是葉子節點中樣本個數， 代表的是該葉子節點上的不純度度量，把每個葉子節點的 加起來，和父節點的 比較，之後進行剪枝即可。

㈥ 決策樹基本概念及演算法優缺點

分類決策樹模型是一種描述對實例進行分類的樹形結構. 決策樹由結點和有向邊組成. 結點有兩種類型: 內部結點和葉節點. 內部節點表示一個特徵或屬性, 葉節點表示一個類.
決策樹(Decision Tree),又稱為判定樹, 是一種以樹結構(包括二叉樹和多叉樹)形式表達的預測分析模型.

分類樹--對離散變數做決策樹

回歸樹--對連續變數做決策樹

優點:
(1)速度快: 計算量相對較小, 且容易轉化成分類規則. 只要沿著樹根向下一直走到葉, 沿途的分裂條件就能夠唯一確定一條分類的謂詞.
(2)准確性高: 挖掘出來的分類規則准確性高, 便於理解, 決策樹可以清晰的顯示哪些欄位比較重要, 即可以生成可以理解的規則.
(3)可以處理連續和種類欄位
(4)不需要任何領域知識和參數假設
(5)適合高維數據
缺點:
(1)對於各類別樣本數量不一致的數據, 信息增益偏向於那些更多數值的特徵
(2)容易過擬合
(3)忽略屬性之間的相關性

若一事假有k種結果, 對應概率為 , 則此事件發生後所得到的信息量I為:

給定包含關於某個目標概念的正反樣例的樣例集S, 那麼S相對這個布爾型分類的熵為:

其中 代表正樣例, 代表反樣例

假設隨機變數(X,Y), 其聯合分布概率為P(X=xi,Y=yi)=Pij, i=1,2,...,n;j=1,2,..,m
則條件熵H(Y|X)表示在已知隨機變數X的條件下隨機變數Y的不確定性, 其定義為X在給定條件下Y的條件概率分布的熵對X的數學期望

在Hunt演算法中, 通過遞歸的方式建立決策樹.

使用信息增益, 選擇 最高信息增益 的屬性作為當前節點的測試屬性

ID3( Examples,Target_attribute,Attributes )

Examples 即訓練樣例集. Target_attribute 是這棵樹要預測的目標屬性. Attributes 是除目標屬性外供學習到的決策樹測試的屬性列表. 返回能正確分類給定 Examples 的決策樹.

class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)

限制決策樹層數為4的DecisionTreeClassifier實例

This plot compares the decision surfaces learned by a dcision tree classifier(first column), by a random forest classifier(second column), by an extra-trees classifier(third column) and by an AdaBoost classifier(fouth column).

Output:

A comparison of a several classifiers in scikit-learn on synthetic datasets.
The point of this examples is to illustrate the nature of decision boundaries of different classifiers.

Particularly in high-dimensional spaces, data can more easily be separated linearly and the simplicity of classifiers such as naive Bayes and linear SVMs might lead to better generalization than is achieved by other classifiers.

This example fits an AdaBoost decisin stump on a non-linearly separable classification dataset composed of two "Gaussian quantiles" clusters and plots the decision boundary and decision scores.

Output:

㈦ 決策樹演算法 CART和C4.5決策樹有什麼區別各用於什麼領域

1、C4.5演算法是在ID3演算法的基礎上採用信息增益率的方法選擇測試屬性。CART演算法採用一種二分遞歸分割的技術，與基於信息熵的演算法不同，CART演算法對每次樣本集的劃分計算GINI系數，GINI系數，GINI系數越小則劃分越合理。
2、決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納演算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。
3、決策樹演算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹演算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡准確性的分枝剪除。