決策樹演算法的優缺點

『壹』 決策樹基本概念及演算法優缺點

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

CART的全稱是分類和回歸樹，既可以做分類演算法，也可以做回歸。
決策樹的優缺點：
優點：

1.可以生成可以理解的規則。
2.計算量相對來說不是很大。
3.可以處理連續和種類欄位。
4.決策樹可以清晰的顯示哪些欄位比較重要
缺點：

1. 對連續性的欄位比較難預測。
2.對有時間順序的數據，需要很多預處理的工作。
3.當類別太多時，錯誤可能就會增加的比較快。
4.一般的演算法分類的時候，只是根據一個欄位來分類。

『叄』 機器學習中常見的演算法的優缺點之決策樹

決策樹在機器學習中是一個十分優秀的演算法，在很多技術中都需要用到決策樹這一演算法，由此可見，決策樹是一個經典的演算法，在這篇文章中我們給大家介紹決策樹演算法的優缺點，希望這篇文章能夠更好的幫助大家理解決策樹演算法。
其實決策樹倍受大家歡迎的原因就是其中的一個優勢，那就是易於解釋。同時決策樹可以毫無壓力地處理特徵間的交互關系並且是非參數化的，因此你不必擔心異常值或者數據是否線性可分。但是決策樹的有一個缺點就是不支持在線學習，於是在新樣本到來後，決策樹需要全部重建。另一個缺點就是容易出現過擬合，但這也就是諸如隨機森林RF之類的集成方法的切入點。另外，隨機森林經常是很多分類問題的贏家，決策樹訓練快速並且可調，同時大家無須擔心要像支持向量機那樣調一大堆參數，所以在以前都一直很受歡迎。
那麼決策樹自身的優點都有什麼呢，總結下來就是有六點，第一就是決策樹易於理解和解釋，可以可視化分析，容易提取出規則。第二就是可以同時處理標稱型和數值型數據。第三就是比較適合處理有缺失屬性的樣本。第四就是能夠處理不相關的特徵。第五就是測試數據集時，運行速度比較快。第六就是在相對短的時間內能夠對大型數據源做出可行且效果良好的結果。
那麼決策樹的缺點是什麼呢？總結下來有三點，第一就是決策樹容易發生過擬合，但是隨機森林可以很大程度上減少過擬合。第二就是決策樹容易忽略數據集中屬性的相互關聯。第三就是對於那些各類別樣本數量不一致的數據，在決策樹中，進行屬性劃分時，不同的判定準則會帶來不同的屬性選擇傾向；信息增益准則對可取數目較多的屬性有所偏好，而增益率准則CART則對可取數目較少的屬性有所偏好，但CART進行屬性劃分時候不再簡單地直接利用增益率盡心劃分，而是採用一種啟發式規則。
通過上述的內容相信大家已經知道了決策樹的優點和缺點了吧，大家在學習或者使用決策樹演算法的時候可以更好的幫助大家理解決策樹的具體情況，只有了解了這些演算法，我們才能夠更好的使用決策樹演算法。

『肆』 請比較k近鄰，決策樹和樸素貝葉斯這三種分類演算法之間的異同點

決策樹演算法主要包括id3，c45，cart等演算法，生成樹形決策樹，而樸素貝葉斯是利用貝葉斯定律，根據先驗概率求算後驗概率。

如果訓練集很小，那麼高偏差/低方差分類器（如樸素貝葉斯分類器）要優於低偏差/高方差分類器（如k近鄰分類器），因為後者容易過擬合。然而，隨著訓練集的增大，低偏差/高方差分類器將開始勝出（它們具有較低的漸近誤差），因為高偏差分類器不足以提供准確的模型。

一些特定演算法的優點：

樸素貝葉斯的優點：

超級簡單，你只是在做一串計算。如果樸素貝葉斯（NB）條件獨立性假設成立，相比於邏輯回歸這類的判別模型，樸素貝葉斯分類器將收斂得更快，所以只需要較小的訓練集。而且，即使NB假設不成立，樸素貝葉斯分類器在實踐方面仍然表現很好。

如果想得到簡單快捷的執行效果，這將是個好的選擇。它的主要缺點是，不能學習特徵之間的相互作用（比如，它不能學習出：雖然你喜歡布拉德·皮特和湯姆·克魯斯的電影，但卻不喜歡他們一起合作的電影）。

邏輯回歸的優點：

有許多正則化模型的方法，不需要像在樸素貝葉斯分類器中那樣擔心特徵間的相互關聯性。與決策樹和支撐向量機不同，還可以有一個很好的概率解釋，並能容易地更新模型來吸收新數據（使用一個在線梯度下降方法）。

如果想要一個概率框架（比如，簡單地調整分類閾值，說出什麼時候是不太確定的，或者獲得置信區間），或你期望未來接收更多想要快速並入模型中的訓練數據，就選擇邏輯回歸。

決策樹的優點：

易於說明和解釋（對某些人來說—我不確定自己是否屬於這個陣營）。它們可以很容易地處理特徵間的相互作用，並且是非參數化的，所以你不用擔心異常值或者數據是否線性可分（比如，決策樹可以很容易地某特徵x的低端是類A，中間是類B，然後高端又是類A的情況）。

一個缺點是，不支持在線學習，所以當有新樣本時，你將不得不重建決策樹。另一個缺點是，容易過擬合，但這也正是諸如隨機森林（或提高樹）之類的集成方法的切入點。另外，隨機森林往往是很多分類問題的贏家（我相信通常略優於支持向量機），它們快速並且可擴展，同時你不須擔心要像支持向量機那樣調一堆參數，所以它們最近似乎相當受歡迎。

(4)決策樹演算法的優缺點擴展閱讀：

樸素貝葉斯演算法：

設每個數據樣本用一個n維特徵向量來描述n個屬性的值，即：X={x1，x2，…，xn}，假定有m個類，分別用C1, C2,…，Cm表示。給定一個未知的數據樣本X（即沒有類標號），若樸素貝葉斯分類法將未知的樣本X分配給類Ci，則一定是

P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i

根據貝葉斯定理：

由於P(X)對於所有類為常數，最大化後驗概率P(Ci|X)可轉化為最大化先驗概率P(X|Ci)P(Ci)。如果訓練數據集有許多屬性和元組，計算P(X|Ci)的開銷可能非常大，為此，通常假設各屬性的取值互相獨立，這樣

先驗概率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以從訓練數據集求得。

根據此方法，對一個未知類別的樣本X，可以先分別計算出X屬於每一個類別Ci的概率P(X|Ci)P(Ci)，然後選擇其中概率最大的類別作為其類別。

樸素貝葉斯演算法成立的前提是各屬性之間互相獨立。當數據集滿足這種獨立性假設時,分類的准確度較高，否則可能較低。另外，該演算法沒有分類規則輸出。

TAN演算法（樹增強型樸素貝葉斯演算法）

TAN演算法通過發現屬性對之間的依賴關系來降低NB中任意屬性之間獨立的假設。它是在NB網路結構的基礎上增加屬性對之間的關聯(邊)來實現的。

實現方法是：用結點表示屬性，用有向邊表示屬性之間的依賴關系，把類別屬性作為根結點，其餘所有屬性都作為它的子節點。通常，用虛線代表NB所需的邊，用實線代表新增的邊。屬性Ai與Aj之間的邊意味著屬性Ai對類別變數C的影響還取決於屬性Aj的取值。

這些增加的邊需滿足下列條件：類別變數沒有雙親結點，每個屬性有一個類別變數雙親結點和最多另外一個屬性作為其雙親結點。

『伍』 決策樹演算法總結

目錄

一、決策樹演算法思想

二、決策樹學習本質

三、總結

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