決策樹演算法年份要管嗎

❶ 決策樹演算法

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

演算法理論：

我了解的決策樹演算法，主要有三種，最早期的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的分類樹，默認不剪枝。然後在出圖後，自行選擇合適的葉節點進行拒絕操作。

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

❷ 決策樹法(一)

姓名：王映中 學號：20181214025 學院：廣研院

轉自 https://blog.csdn.net/weixin_42327752/article/details/117806076

【嵌牛導讀】決策樹（decision tree）是一種基本的分類與回歸方法。決策樹學習通常包括3個步驟：特徵選擇、決策樹的生成和決策樹的修剪。些決策樹學習的思想主要來源於由Quinlan在1986年提出的ID3演算法和1993年提出的C4.5演算法，以及由Breiman等人在1984年提出的CART演算法。

【嵌牛鼻子】決策樹模型與學習

【嵌牛提問】如何建立決策樹模型?

【嵌牛正文】

1 決策樹模型與學習

決策樹解決分類問題的一般方法

1.1 決策樹模型

定義：分類決策樹模型是一種描述對實例進行分類的樹形結構。決策樹由結點（node）和有向邊（directed edge）組成。結點有兩種類型：內部結點（internal node）和葉結點（leaf node）。內部結點表示一個特徵或屬性，葉結點表示一個類。

1.2 決策樹與if-then規則

可以將決策樹看成一個if-then規則的集合。將決策樹轉換成if-then規則的過程是這樣的：由決策樹的根結點到葉結點的每一條路徑構建一條規則；路徑上內部結點的特徵對應著規則的條件，而葉結點的類對應著規則的結論。

    決策樹的路徑或其對應的if-then規則集合具有一個重要的性質：互斥並且完備。這就是說，每一個實例都被一條路徑或一條規則所覆蓋，而且只被一條路徑或一條規則所覆蓋。這里所謂覆蓋是指實例的特徵與路徑上的特徵一致或實例滿足規則的條件。

1.3 決策樹與條件概率分布

1.4 決策樹學習

決策樹學習本質上是從訓練數據集中歸納出一組分類規則，與訓練數據集不相矛盾的決策樹（即能對訓練數據進行正確分類的決策樹）可能有多個，也可能一個也沒有。從另一個角度看，決策樹學習是由訓練數據集估計條件概率模型。基於特徵空間劃分的類的條件概率模型有無窮多個。我們選擇的條件概率模型應該不僅對訓練數據有很好的擬合，而且對未知數據有很好的預測。

    決策樹的損失函數是正則化的極大似然函數。當損失函數確定以後，學習問題就變為在損失函數意義下選擇最優決策樹的問題。因為從所有可能的決策樹中選取最優決策樹是NP完全問題，所以現實中決策樹學習演算法通常採用啟發式方法，近似求解這一最優化問題。這樣得到的決策樹是次最優（sub-optimal）的。

    決策樹學習的演算法通常是一個遞歸地選擇最優特徵，並根據該特徵對訓練數據進行分割，使得對各個子數據集有一個最好的分類的過程。這一過程對應著對特徵空間的劃分，也對應著決策樹的構建。開始，構建根結點，將所有訓練數據都放在根結點。選擇一個最優特徵，按照這一特徵將訓練數據集分割成子集，使得各個子集有一個在當前條件下最好的分類。如果這些子集已經能夠被基本正確分類，那麼構建葉結點，並將這些子集分到所對應的葉結點中去；如果還有子集不能被基本正確分類，那麼就對這些子集選擇新的最優特徵，繼續對其進行分割，構建相應的結點。如此遞歸地進行下去，直至所有訓練數據子集被基本正確分類，或者沒有合適的特徵為止。最後每個子集都被分到葉結點上，即都有了明確的類。這就生成了一棵決策樹。

    以上方法生成的決策樹可能對訓練數據有很好的分類能力，但對未知的測試數據卻未必有很好的分類能力，即可能發生過擬合現象。我們需要對已生成的樹自下而上進行剪枝，將樹變得更簡單，從而使它具有更好的泛化能力。具體地，就是去掉過於細分的葉結點，使其回退到父結點，甚至更高的結點，然後將父結點或更高的結點改為新的葉結點。

決策樹學習演算法包含特徵選擇、決策樹的生成與決策樹的剪枝過程。決策樹學習演算法包含特徵選擇、決策樹的生成與決策樹的剪枝過程。

    決策樹學習常用的演算法有ID3、C4.5與CART，下面結合這些演算法分別敘述決策樹學習的特徵選擇、決策樹的生成和剪枝過程。

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

分類決策樹模型是一種描述對實例進行分類的樹形結構. 決策樹由結點和有向邊組成. 結點有兩種類型: 內部結點和葉節點. 內部節點表示一個特徵或屬性, 葉節點表示一個類.
決策樹(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:

❹ 決策樹演算法總結

目錄

一、決策樹演算法思想

二、決策樹學習本質

三、總結

一、決策樹（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、決策樹的本質
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都是基於特徵選擇進行優化。

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

❻ 決策樹的演算法

C4.5演算法繼承了ID3演算法的優點，並在以下幾方面對ID3演算法進行了改進：
1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；
2) 在樹構造過程中進行剪枝；
3) 能夠完成對連續屬性的離散化處理；
4) 能夠對不完整數據進行處理。
C4.5演算法有如下優點：產生的分類規則易於理解，准確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致演算法的低效。此外，C4.5隻適合於能夠駐留於內存的數據集，當訓練集大得無法在內存容納時程序無法運行。
具體演算法步驟如下；
1創建節點N
2如果訓練集為空，在返回節點N標記為Failure
3如果訓練集中的所有記錄都屬於同一個類別，則以該類別標記節點N
4如果候選屬性為空，則返回N作為葉節點，標記為訓練集中最普通的類；
5for each 候選屬性 attribute_list
6if 候選屬性是連續的then
7對該屬性進行離散化
8選擇候選屬性attribute_list中具有最高信息增益率的屬性D
9標記節點N為屬性D
10for each 屬性D的一致值d
11由節點N長出一個條件為D=d的分支
12設s是訓練集中D=d的訓練樣本的集合
13if s為空
14加上一個樹葉，標記為訓練集中最普通的類
15else加上一個有C4.5（R - {D},C，s）返回的點 背景：
分類與回歸樹(CART——Classification And Regression Tree)) 是一種非常有趣並且十分有效的非參數分類和回歸方法。它通過構建二叉樹達到預測目的。
分類與回歸樹CART 模型最早由Breiman 等人提出，已經在統計領域和數據挖掘技術中普遍使用。它採用與傳統統計學完全不同的方式構建預測准則，它是以二叉樹的形式給出，易於理解、使用和解釋。由CART 模型構建的預測樹在很多情況下比常用的統計方法構建的代數學預測准則更加准確，且數據越復雜、變數越多，演算法的優越性就越顯著。模型的關鍵是預測准則的構建，准確的。
定義：
分類和回歸首先利用已知的多變數數據構建預測准則, 進而根據其它變數值對一個變數進行預測。在分類中, 人們往往先對某一客體進行各種測量, 然後利用一定的分類准則確定該客體歸屬那一類。例如, 給定某一化石的鑒定特徵, 預測該化石屬那一科、那一屬, 甚至那一種。另外一個例子是, 已知某一地區的地質和物化探信息, 預測該區是否有礦。回歸則與分類不同, 它被用來預測客體的某一數值, 而不是客體的歸類。例如, 給定某一地區的礦產資源特徵, 預測該區的資源量。

❼ 決策樹演算法原理

決策樹是通過一系列規則對數據進行分類的過程。它提供一種在什麼條件下會得到什麼值的類似規則的方法。決策樹分為分類樹和回歸樹兩種，分類樹對離散變數做決策樹，回歸樹對連續變數做決策樹。

如果不考慮效率等，那麼樣本所有特徵的判斷級聯起來終會將某一個樣本分到一個類終止塊上。實際上，樣本所有特徵中有一些特徵在分類時起到決定性作用，決策樹的構造過程就是找到這些具有決定性作用的特徵，根據其決定性程度來構造一個倒立的樹--決定性作用最大的那個特徵作為根節點，然後遞歸找到各分支下子數據集中次大的決定性特徵，直至子數據集中所有數據都屬於同一類。所以，構造決策樹的過程本質上就是根據數據特徵將數據集分類的遞歸過程，我們需要解決的第一個問題就是，當前數據集上哪個特徵在劃分數據分類時起決定性作用。

一棵決策樹的生成過程主要分為以下3個部分:

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

決策樹生成： 根據選擇的特徵評估標准，從上至下遞歸地生成子節點，直到數據集不可分則停止決策樹停止生長。 樹結構來說，遞歸結構是最容易理解的方式。

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

劃分數據集的最大原則是：使無序的數據變的有序。如果一個訓練數據中有20個特徵，那麼選取哪個做劃分依據？這就必須採用量化的方法來判斷，量化劃分方法有多重，其中一項就是「資訊理論度量信息分類」。基於資訊理論的決策樹演算法有ID3、CART和C4.5等演算法，其中C4.5和CART兩種演算法從ID3演算法中衍生而來。

CART和C4.5支持數據特徵為連續分布時的處理，主要通過使用二元切分來處理連續型變數，即求一個特定的值-分裂值：特徵值大於分裂值就走左子樹，或者就走右子樹。這個分裂值的選取的原則是使得劃分後的子樹中的「混亂程度」降低，具體到C4.5和CART演算法則有不同的定義方式。

ID3演算法由Ross Quinlan發明，建立在「奧卡姆剃刀」的基礎上：越是小型的決策樹越優於大的決策樹（be simple簡單理論）。ID3演算法中根據資訊理論的信息增益評估和選擇特徵，每次選擇信息增益最大的特徵做判斷模塊。ID3演算法可用於劃分標稱型數據集，沒有剪枝的過程，為了去除過度數據匹配的問題，可通過裁剪合並相鄰的無法產生大量信息增益的葉子節點（例如設置信息增益閥值）。使用信息增益的話其實是有一個缺點，那就是它偏向於具有大量值的屬性--就是說在訓練集中，某個屬性所取的不同值的個數越多，那麼越有可能拿它來作為分裂屬性，而這樣做有時候是沒有意義的，另外ID3不能處理連續分布的數據特徵，於是就有了C4.5演算法。CART演算法也支持連續分布的數據特徵。

C4.5是ID3的一個改進演算法，繼承了ID3演算法的優點。C4.5演算法用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足在樹構造過程中進行剪枝；能夠完成對連續屬性的離散化處理；能夠對不完整數據進行處理。C4.5演算法產生的分類規則易於理解、准確率較高；但效率低，因樹構造過程中，需要對數據集進行多次的順序掃描和排序。也是因為必須多次數據集掃描，C4.5隻適合於能夠駐留於內存的數據集。

CART演算法的全稱是Classification And Regression Tree，採用的是Gini指數（選Gini指數最小的特徵s）作為分裂標准,同時它也是包含後剪枝操作。ID3演算法和C4.5演算法雖然在對訓練樣本集的學習中可以盡可能多地挖掘信息，但其生成的決策樹分支較大，規模較大。為了簡化決策樹的規模，提高生成決策樹的效率，就出現了根據GINI系數來選擇測試屬性的決策樹演算法CART。

決策樹演算法的優點：

（1）便於理解和解釋，樹的結構可以可視化出來

（2）基本不需要預處理，不需要提前歸一化，處理缺失值

（3）使用決策樹預測的代價是O(log2m)，m為樣本數

（4）能夠處理數值型數據和分類數據

（5）可以處理多維度輸出的分類問題

（6）可以通過數值統計測試來驗證該模型，這使解釋驗證該模型的可靠性成為可能

（7）即使該模型假設的結果與真實模型所提供的數據有些違反，其表現依舊良好

決策樹演算法的缺點:

（1）決策樹模型容易產生一個過於復雜的模型,這樣的模型對數據的泛化性能會很差。這就是所謂的過擬合.一些策略像剪枝、設置葉節點所需的最小樣本數或設置數的最大深度是避免出現該問題最為有效地方法。

（2）決策樹可能是不穩定的，因為數據中的微小變化可能會導致完全不同的樹生成。這個問題可以通過決策樹的集成來得到緩解。

（3）在多方面性能最優和簡單化概念的要求下，學習一棵最優決策樹通常是一個NP難問題。因此，實際的決策樹學習演算法是基於啟發式演算法，例如在每個節點進行局部最優決策的貪心演算法。這樣的演算法不能保證返回全局最優決策樹。這個問題可以通過集成學習來訓練多棵決策樹來緩解,這多棵決策樹一般通過對特徵和樣本有放回的隨機采樣來生成。

（4）有些概念很難被決策樹學習到,因為決策樹很難清楚的表述這些概念。例如XOR，奇偶或者復用器的問題。

（5）如果某些類在問題中佔主導地位會使得創建的決策樹有偏差。因此，我們建議在擬合前先對數據集進行平衡。

（1）當數據的特徵維度很高而數據量又很少的時候，這樣的數據在構建決策樹的時候往往會過擬合。所以我們要控制樣本數量和特徵的之間正確的比率；

（2）在構建決策樹之前，可以考慮預先執行降維技術（如PCA，ICA或特徵選擇），以使我們生成的樹更有可能找到具有辨別力的特徵；

（3）在訓練一棵樹的時候，可以先設置max_depth=3來將樹可視化出來，以便我們找到樹是怎樣擬合我們數據的感覺，然後在增加我們樹的深度；

（4）樹每增加一層，填充所需的樣本數量是原來的2倍，比如我們設置了最小葉節點的樣本數量，當我們的樹層數增加一層的時候，所需的樣本數量就會翻倍，所以我們要控制好樹的最大深度，防止過擬合；

（5）使用min_samples_split（節點可以切分時擁有的最小樣本數） 和 min_samples_leaf（最小葉節點數）來控制葉節點的樣本數量。這兩個值設置的很小通常意味著我們的樹過擬合了，而設置的很大意味著我們樹預測的精度又會降低。通常設置min_samples_leaf=5；

（6）當樹的類比不平衡的時候，在訓練之前一定要先平很數據集，防止一些類別大的類主宰了決策樹。可以通過采樣的方法將各個類別的樣本數量到大致相等，或者最好是將每個類的樣本權重之和(sample_weight)規范化為相同的值。另請注意，基於權重的預剪枝標准（如min_weight_fraction_leaf）將比不知道樣本權重的標准（如min_samples_leaf）更少偏向主導類別。

（7）如果樣本是帶權重的，使用基於權重的預剪枝標准將更簡單的去優化樹結構，如mn_weight_fraction_leaf，這確保了葉節點至少包含了樣本權值總體總和的一小部分；

（8）在sklearn中所有決策樹使用的數據都是np.float32類型的內部數組。如果訓練數據不是這種格式，則將復制數據集，這樣會浪費計算機資源。

（9）如果輸入矩陣X非常稀疏，建議在調用fit函數和稀疏csr_matrix之前轉換為稀疏csc_matrix，然後再調用predict。 當特徵在大多數樣本中具有零值時，與密集矩陣相比，稀疏矩陣輸入的訓練時間可以快幾個數量級。

❽ 決策樹法有年份要乘年份嗎

決策樹法有年份也不需要乘年份 不需要乘年份

❾ 決策樹的原理及演算法

決策樹基本上就是把我們以前的經驗總結出來。我給你准備了一個打籃球的訓練集。如果我們要出門打籃球，一般會根據「天氣」、「溫度」、「濕度」、「刮風」這幾個條件來判斷，最後得到結果：去打籃球？還是不去？

上面這個圖就是一棵典型的決策樹。我們在做決策樹的時候，會經歷兩個階段：構造和剪枝。

構造就是生成一棵完整的決策樹。簡單來說，構造的過程就是選擇什麼屬性作為節點的過程，那麼在構造過程中，會存在三種節點：
根節點：就是樹的最頂端，最開始的那個節點。在上圖中，「天氣」就是一個根節點；
內部節點：就是樹中間的那些節點，比如說「溫度」、「濕度」、「刮風」；
葉節點：就是樹最底部的節點，也就是決策結果。

剪枝就是給決策樹瘦身，防止過擬合。分為「預剪枝」（Pre-Pruning）和「後剪枝」（Post-Pruning）。

預剪枝是在決策樹構造時就進行剪枝。方法是在構造的過程中對節點進行評估，如果對某個節點進行劃分，在驗證集中不能帶來准確性的提升，那麼對這個節點進行劃分就沒有意義，這時就會把當前節點作為葉節點，不對其進行劃分。

後剪枝就是在生成決策樹之後再進行剪枝，通常會從決策樹的葉節點開始，逐層向上對每個節點進行評估。如果剪掉這個節點子樹，與保留該節點子樹在分類准確性上差別不大，或者剪掉該節點子樹，能在驗證集中帶來准確性的提升，那麼就可以把該節點子樹進行剪枝。

1是欠擬合，3是過擬合，都會導致分類錯誤。

造成過擬合的原因之一就是因為訓練集中樣本量較小。如果決策樹選擇的屬性過多，構造出來的決策樹一定能夠「完美」地把訓練集中的樣本分類，但是這樣就會把訓練集中一些數據的特點當成所有數據的特點，但這個特點不一定是全部數據的特點，這就使得這個決策樹在真實的數據分類中出現錯誤，也就是模型的「泛化能力」差。

p(i|t) 代表了節點 t 為分類 i 的概率，其中 log2 為取以 2 為底的對數。這里我們不是來介紹公式的，而是說存在一種度量，它能幫我們反映出來這個信息的不確定度。當不確定性越大時，它所包含的信息量也就越大，信息熵也就越高。

ID3 演算法計算的是信息增益，信息增益指的就是劃分可以帶來純度的提高，信息熵的下降。它的計算公式，是父親節點的信息熵減去所有子節點的信息熵。

公式中 D 是父親節點，Di 是子節點，Gain(D,a) 中的 a 作為 D 節點的屬性選擇。

因為 ID3 在計算的時候，傾向於選擇取值多的屬性。為了避免這個問題，C4.5 採用信息增益率的方式來選擇屬性。信息增益率 = 信息增益 / 屬性熵，具體的計算公式這里省略。

當屬性有很多值的時候，相當於被劃分成了許多份，雖然信息增益變大了，但是對於 C4.5 來說，屬性熵也會變大，所以整體的信息增益率並不大。

ID3 構造決策樹的時候，容易產生過擬合的情況。在 C4.5 中，會在決策樹構造之後採用悲觀剪枝（PEP），這樣可以提升決策樹的泛化能力。

悲觀剪枝是後剪枝技術中的一種，通過遞歸估算每個內部節點的分類錯誤率，比較剪枝前後這個節點的分類錯誤率來決定是否對其進行剪枝。這種剪枝方法不再需要一個單獨的測試數據集。

C4.5 可以處理連續屬性的情況，對連續的屬性進行離散化的處理。比如打籃球存在的「濕度」屬性，不按照「高、中」劃分，而是按照濕度值進行計算，那麼濕度取什麼值都有可能。該怎麼選擇這個閾值呢，C4.5 選擇具有最高信息增益的劃分所對應的閾值。

針對數據集不完整的情況，C4.5 也可以進行處理。

暫無

請你用下面的例子來模擬下決策樹的流程，假設好蘋果的數據如下，請用 ID3 演算法來給出好蘋果的決策樹。

「紅」的信息增益為：1「大」的信息增益為：0
因此選擇「紅」的作為根節點，「大」沒有用，剪枝。

數據分析實戰45講.17 丨決策樹（上）：要不要去打籃球？決策樹來告訴你

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

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

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

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

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

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

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

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

先來看熵的概念：

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

例如：要給（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為劃分的總數，如果每個屬性值具有相同的記錄數，則 ，劃分信息等於 ，那麼如果某個屬性產生了大量劃分，則劃分信息很大，信息增益率低，就能規避這種情況了。

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

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

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