決策樹演算法概述

① 關於數據挖掘中決策樹的知識

在數據挖掘中，有很多的演算法是需要我們去學習的，比如決策樹演算法。在數據挖掘中，決策樹能夠幫助我們解決更多的問題。當然，關於決策樹的概念是有很多的，所以說我們需要多多學習多多總結，這樣才能夠學會並且學會數據挖掘的知識，在這篇文章中我們就重點為大家介紹一下關於決策樹的相關知識。
1.決策樹的演算法
決策樹的演算法是以樹狀結構表示數據分類的結果。一般情況，一棵決策樹包含一個根節點、若干個內部結點和若干個葉結點。而葉結點對應於決策結果，其他每個結點則對應於一個屬性測試；每個結點包含的樣本集合根據屬性測試的結果被劃分到子結點中；根結點包含樣本全集，從根結點到每個葉結點的路徑對應了一個判定測試序列。決策樹學習的目的就是為了產生一棵泛化能力強，即能處理未見示例能力強的決策樹。這些就是決策樹演算法的結構。
2.決策樹的原理
一般來說，決策樹歸納的基本演算法是貪心演算法，自頂向下以遞歸方式構造決策樹。而貪心演算法在每一步選擇中都採取在當前狀態下最優的選擇。在決策樹生成過程中，劃分選擇即屬性選擇度量是關鍵。通過屬性選擇度量，選擇出最好的將樣本分類的屬性。這樣就能夠方便數據屬性的劃分，然後，下一步是樹的剪枝。在決策樹學習中，為了盡可能正確分類訓練樣本，結點劃分過程將不斷重復，這樣才能夠使用決策樹解決很多的問題。而分類是數據挖掘中的一種應用方法，而決策樹則是一種典型的普遍使用的分類方法，並且決策樹技術早已被證明是利用計算機模擬人決策的有效方法。
3.決策樹的現狀
近年來隨著信息技術、計算機科學的迅速發展，決策樹作為重要方法之一，越來越受到人們的關注。而其在人工智慧方面的潛力以及與越來越多新技術的結合，由此可見，決策樹在數據挖掘乃至數據分析中還是有很長的使用時間，這就是決策樹至今經典的原因。
在這篇文章中我們給大家介紹了關於數據挖掘中決策樹的知識，當大家學習了決策樹的概念，決策樹的結構以決策樹的原理，就能夠掌握決策樹的基礎知識。不過要想學習數據挖掘，還是要學習更多的知識，希望這篇文章能夠幫助到大家。

② 決策樹演算法

決策樹演算法的演算法理論和應用場景

演算法理論：

我了解的決策樹演算法，主要有三種，最早期的ID3，再到後來的C4.5和CART這三種演算法。

這三種演算法的大致框架近似。

決策樹的學習過程

1.特徵選擇

在訓練數據中 眾多X中選擇一個特徵作為當前節點分裂的標准。如何選擇特徵有著很多不同量化評估標准，從而衍生出不同的決策樹演算法。

2.決策樹生成

根據選擇的特徵評估標准，從上至下遞歸生成子節點，直到數據集不可分或者最小節點滿足閾值，此時決策樹停止生長。

3.剪枝

決策樹極其容易過擬合，一般需要通過剪枝，縮小樹結構規模、緩解過擬合。剪枝技術有前剪枝和後剪枝兩種。

有些演算法用剪枝過程，有些沒有，如ID3。

預剪枝：對每個結點劃分前先進行估計，若當前結點的劃分不能帶來決策樹的泛化性能的提升，則停止劃分，並標記為葉結點。

後剪枝：現從訓練集生成一棵完整的決策樹，然後自底向上對非葉子結點進行考察，若該結點對應的子樹用葉結點能帶來決策樹泛化性能的提升，則將該子樹替換為葉結點。

但不管是預剪枝還是後剪枝都是用驗證集的數據進行評估。

ID3演算法是最早成型的決策樹演算法。ID3的演算法核心是在決策樹各個節點上應用信息增益准則來選擇特徵，遞歸構建決策樹。缺點是，在選擇分裂變數時容易選擇分類多的特徵，如ID值【值越多、分叉越多，子節點的不純度就越小，信息增益就越大】。

ID3之所以無法 處理缺失值、無法處理連續值、不剪紙等情況，主要是當時的重點並不是這些。

C4.5演算法與ID3近似，只是分裂標准從 信息增益 轉變成  信息增益率。可以處理連續值，含剪枝，可以處理缺失值，這里的做法多是 概率權重。

CART：1.可以處理連續值 2.可以進行缺失值處理 3.支持剪枝 4.可以分類可以回歸。

缺失值的處理是 作為一個單獨的類別進行分類。

建立CART樹

我們的演算法從根節點開始，用訓練集遞歸的建立CART樹。

1) 對於當前節點的數據集為D，如果樣本個數小於閾值或者沒有特徵，則返回決策子樹，當前節點停止遞歸。

2) 計算樣本集D的基尼系數， 如果基尼系數小於閾值 （說明已經很純了！！不需要再分了！！），則返回決策樹子樹，當前節點停止遞歸。

3) 計算當前節點現有的各個特徵的各個特徵值對數據集D的基尼系數。

4) 在計算出來的各個特徵的各個特徵值對數據集D的基尼系數中，選擇 基尼系數最小的特徵A和對應的特徵值a。根據這個最優特徵和最優特徵值，把數據集劃分成兩部分D1和D2，同時建立當前節點的左右節點，做節點的數據集D為D1，右節點的數據集D為D2。 (註：注意是二叉樹，故這里的D1和D2是有集合關系的，D2=D-D1)

5) 對左右的子節點遞歸的調用1-4步，生成決策樹。

CART採用的辦法是後剪枝法，即先生成決策樹，然後產生所有可能的剪枝後的CART樹，然後使用交叉驗證來檢驗各種剪枝的效果，選擇泛化能力最好的剪枝策略。

應用場景

比如欺詐問題中，通過決策樹演算法簡單分類，默認是CART的分類樹，默認不剪枝。然後在出圖後，自行選擇合適的葉節點進行拒絕操作。

這個不剪枝是因為欺詐問題的特殊性，欺詐問題一般而言較少，如數據的萬幾水平，即正樣本少，而整個欺詐問題需要解決的速度較快。此時只能根據業務要求，迅速針對已有的正樣本情況，在控制准確率的前提下，盡可能提高召回率。這種情況下，可以使用決策樹來簡單應用，這個可以替代原本手工選擇特徵及特徵閾值的情況。

③ 決策樹計算公式

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

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

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

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

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

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

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

④ 決策樹演算法-原理篇

關於決策樹演算法，我打算分兩篇來講，一篇講思想原理，另一篇直接擼碼來分析演算法。本篇為原理篇。
通過閱讀這篇文章，你可以學到：
1、決策樹的本質
2、決策樹的構造過程
3、決策樹的優化方向

決策樹根據使用目的分為：分類樹和回歸樹，其本質上是一樣的。本文只講分類樹。

決策樹，根據名字來解釋就是，使用樹型結構來模擬決策。
用圖形表示就是下面這樣。

其中橢圓形代表：特徵或屬性。長方形代表：類別結果。
面對一堆數據（含有特徵和類別），決策樹就是根據這些特徵（橢圓形）來給數據歸類（長方形）
例如，信用貸款問題，我根據《神奇動物在哪裡》的劇情給銀行造了個決策樹模型，如下圖：

然而，決定是否貸款可以根據很多特徵，然麻雞銀行選擇了：（1）是否房產價值>100w；（2）是否有其他值錢的抵押物；（3）月收入>10k；（4）是否結婚；這四個特徵，來決定是否給予貸款。
先不管是否合理，但可以肯定的是，決策樹做了特徵選擇工作，即選擇出類別區分度高的特徵。

由此可見， 決策樹其實是一種特徵選擇方法。 （特徵選擇有多種，決策樹屬於嵌入型特徵選擇，以後或許會講到，先給個圖）即選擇區分度高的特徵子集。

那麼， 從特徵選擇角度來看決策樹，決策樹就是嵌入型特徵選擇技術

同時，決策樹也是機器學習中經典分類器演算法，通過決策路徑，最終能確定實例屬於哪一類別。
那麼， 從分類器角度來看決策樹，決策樹就是樹型結構的分類模型

從人工智慧知識表示法角度來看，決策樹類似於if-then的產生式表示法。
那麼， 從知識表示角度來看決策樹，決策樹就是if-then規則的集合

由上面的例子可知，麻雞銀行通過決策樹模型來決定給哪些人貸款，這樣決定貸款的流程就是固定的，而不由人的主觀情感來決定。
那麼， 從使用者角度來看決策樹，決策樹就是規范流程的方法

最後我們再來看看決策樹的本質是什麼已經不重要了。
決策樹好像是一種思想，而通過應用在分類任務中從而成就了「決策樹演算法」。

下面內容還是繼續講解用於分類的「決策樹演算法」。

前面講了決策樹是一種 特徵選擇技術 。

既然決策樹就是一種特徵選擇的方法，那麼經典決策樹演算法其實就是使用了不同的特徵選擇方案。
如：
（1）ID3：使用信息增益作為特徵選擇
（2）C4.5：使用信息增益率作為特徵選擇
（3）CART：使用GINI系數作為特徵選擇
具體選擇的方法網上一大把，在這里我提供幾個鏈接，不細講。

但，不僅僅如此。
決策樹作為嵌入型特徵選擇技術結合了特徵選擇和分類演算法，根據特徵選擇如何生成分類模型也是決策樹的一部分。
其生成過程基本如下：

根據這三個步驟，可以確定決策樹由：（1）特徵選擇；（2）生成方法；（3）剪枝，組成。
決策樹中學習演算法與特徵選擇的關系如下圖所示：

原始特徵集合T：就是包含收集到的原始數據所有的特徵，例如：麻瓜銀行收集到與是否具有償還能力的所有特徵，如：是否結婚、是否擁有100w的房產、是否擁有汽車、是否有小孩、月收入是否>10k等等。
中間的虛線框就是特徵選擇過程，例如：ID3使用信息增益、C4.5使用信息增益率、CART使用GINI系數。
其中評價指標（如：信息增益）就是對特徵的要求，特徵需要滿足這種條件（一般是某個閾值），才能被選擇，而這一選擇過程嵌入在學習演算法中，最終被選擇的特徵子集也歸到學習演算法中去。
這就是抽象的決策樹生成過程，不論哪種演算法都是將這一抽象過程的具體化。
其具體演算法我將留在下一篇文章來講解。

而決策樹的剪枝，其實用得不是很多，因為很多情況下隨機森林能解決決策樹帶來的過擬合問題，因此在這里也不講了。

決策樹的優化主要也是圍繞決策樹生成過程的三個步驟來進行優化的。
樹型結構，可想而知，演算法效率決定於樹的深度，優化這方面主要從特徵選擇方向上優化。
提高分類性能是最重要的優化目標，其主要也是特徵選擇。
面對過擬合問題，一般使用剪枝來優化，如：李國和基於決策樹生成及剪枝的數據集優化及其應用。
同時，決策樹有很多不足，如：多值偏向、計算效率低下、對數據空缺較為敏感等，這方面的優化也有很多，大部分也是特徵選擇方向，如：陳沛玲使用粗糙集進行特徵降維。
由此，決策樹的優化方向大多都是特徵選擇方向，像ID3、C4.5、CART都是基於特徵選擇進行優化。

參考文獻
統計學習方法-李航
特徵選擇方法綜述-李郅琴
決策樹分類演算法優化研究_陳沛玲
基於決策樹生成及剪枝的數據集優化及其應用-李國和

⑤ 決策樹演算法總結

目錄

一、決策樹演算法思想

二、決策樹學習本質

三、總結

一、決策樹（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、對類別不平衡的數據不友好。

⑥ 決策樹演算法的介紹

決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納演算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。決策樹方法最早產生於上世紀60年代，到70年代末。由J Ross Quinlan提出了ID3演算法，此演算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5演算法在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為劃分的總數，如果每個屬性值具有相同的記錄數，則 ，劃分信息等於 ，那麼如果某個屬性產生了大量劃分，則劃分信息很大，信息增益率低，就能規避這種情況了。

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

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

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