決策演算法題

㈠ 決策樹演算法原理是什麼

決策樹構造的輸入是一組帶有類別標記的例子，構造的結果是一棵二叉樹或多叉樹。二叉樹的 內部節點(非 葉子節點)一般表示為一個邏輯判斷，如形式為a=aj的邏輯判斷，其中a是屬性，aj是該屬性的所有取值：樹的邊是邏輯判斷的分支結果。

多叉樹(ID3)的內部結點是屬性，邊是該屬性的所有取值，有幾個 屬性值就有幾條邊。樹的葉子節點都是類別標記。

由於數據表示不當、有雜訊或者由於決策樹生成時產生重復的子樹等原因，都會造成產生的決策樹過大。

因此，簡化決策樹是一個不可缺少的環節。尋找一棵最優決策樹，主要應解決以下3個最優化問題：①生成最少數目的葉子節點；②生成的每個葉子節點的深度最小；③生成的決策樹葉子節點最少且每個葉子節點的深度最小。

(1)決策演算法題擴展閱讀：

決策樹演算法的優點如下：

（1）分類精度高；

（2）生成的模式簡單；

（3）對雜訊數據有很好的健壯性。

因而是目前應用最為廣泛的歸納推理演算法之一，在 數據挖掘中受到研究者的廣泛關注。

㈡ 5.10 決策樹與ID3演算法

https://blog.csdn.net/dorisi_h_n_q/article/details/82787295

決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）。決策過程是從根節點開始，測試待分類項中相應的特徵屬性，並按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。

決策樹的關鍵步驟是分裂屬性。就是在某節點處按某一特徵屬性的不同劃分構造不同的分支，目標是讓各個分裂子集盡可能地「純」。即讓一個分裂子集中待分類項屬於同一類別。

簡而言之，決策樹的劃分原則就是：將無序的數據變得更加有序

分裂屬性分為三種不同的情況 ：

構造決策樹的關鍵性內容是進行屬性選擇度量，屬性選擇度量（找一種計算方式來衡量怎麼劃分更劃算）是一種選擇分裂准則，它決定了拓撲結構及分裂點split_point的選擇。

屬性選擇度量演算法有很多，一般使用自頂向下遞歸分治法，並採用不回溯的貪心策略。這里介紹常用的ID3演算法。

貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，所做出的是在某種意義上的局部最優解。

此概念最早起源於物理學，是用來度量一個熱力學系統的無序程度。
而在信息學裡面，熵是對不確定性的度量。
在1948年，香農引入了信息熵，將其定義為離散隨機事件出現的概率，一個系統越是有序，信息熵就越低，反之一個系統越是混亂，它的信息熵就越高。所以信息熵可以被認為是系統有序化程度的一個度量。

熵定義為信息的期望值，在明晰這個概念之前，我們必須知道信息的定義。如果待分類的事務可能劃分在多個分類之中，則符號x的信息定義為：

在劃分數據集之前之後信息發生的變化稱為信息增益。
知道如何計算信息增益，就可計算每個特徵值劃分數據集獲得的信息增益，獲得信息增益最高的特徵就是最好的選擇。

條件熵 表示在已知隨機變數的條件下隨機變數的不確定性，隨機變數X給定的條件下隨機變數Y的條
件熵(conditional entropy) ，定義X給定條件下Y的條件概率分布的熵對X的數學期望：

根據上面公式，我們假設將訓練集D按屬性A進行劃分，則A對D劃分的期望信息為

則信息增益為如下兩者的差值

ID3演算法就是在每次需要分裂時，計算每個屬性的增益率，然後選擇增益率最大的屬性進行分裂

步驟：1. 對當前樣本集合，計算所有屬性的信息增益；

是最原始的決策樹分類演算法，基本流程是，從一棵空數出發，不斷的從決策表選取屬性加入數的生長過程中，直到決策樹可以滿足分類要求為止。CLS演算法存在的主要問題是在新增屬性選取時有很大的隨機性。ID3演算法是對CLS演算法的改進，主要是摒棄了屬性選擇的隨機性。

基於ID3演算法的改進，主要包括：使用信息增益比替換了信息增益下降度作為屬性選擇的標准；在決策樹構造的同時進行剪枝操作；避免了樹的過度擬合情況；可以對不完整屬性和連續型數據進行處理；使用k交叉驗證降低了計算復雜度；針對數據構成形式，提升了演算法的普適性。

信息增益值的大小相對於訓練數據集而言的，並沒有絕對意義，在分類問題困難時，也就是說在訓練數據集經驗熵大的時候，信息增益值會偏大，反之信息增益值會偏小，使用信息增益比可以對這個問題進行校正，這是特徵選擇
的另一個標准。
特徵對訓練數據集的信息增益比定義為其信息增益gR( D,A) 與訓練數據集的經驗熵g(D,A)之比 ：

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

sklearn的決策樹模型就是一個CART樹。是一種二分遞歸分割技術，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子節點都有兩個分支，因此，CART演算法生成的決策樹是結構簡潔的二叉樹。
分類回歸樹演算法(Classification and Regression Trees,簡稱CART演算法)是一種基於二分遞歸分割技術的演算法。該演算法是將當前的樣本集，分為兩個樣本子集，這樣做就使得每一個非葉子節點最多隻有兩個分支。因此，使用CART
演算法所建立的決策樹是一棵二叉樹，樹的結構簡單，與其它決策樹演算法相比，由該演算法生成的決策樹模型分類規則較少。

CART分類演算法的基本思想是：對訓練樣本集進行遞歸劃分自變數空間，並依次建立決策樹模型，然後採用驗證數據的方法進行樹枝修剪，從而得到一顆符合要求的決策樹分類模型。

CART分類演算法和C4.5演算法一樣既可以處理離散型數據，也可以處理連續型數據。CART分類演算法是根據基尼(gini)系
數來選擇測試屬性，gini系數的值越小，劃分效果越好。設樣本集合為T，則T的gini系數值可由下式計算：

CART演算法優點：除了具有一般決策樹的高准確性、高效性、模式簡單等特點外，還具有一些自身的特點。
如，CART演算法對目標變數和預測變數在概率分布上沒有要求，這樣就避免了因目標變數與預測變數概率分布的不同造成的結果；CART演算法能夠處理空缺值，這樣就避免了因空缺值造成的偏差；CART演算法能夠處理孤立的葉子結點，這樣可以避免因為數據集中與其它數據集具有不同的屬性的數據對進一步分支產生影響；CART演算法使用的是二元分支，能夠充分地運用數據集中的全部數據，進而發現全部樹的結構；比其它模型更容易理解，從模型中得到的規則能獲得非常直觀的解釋。

CART演算法缺點：CART演算法是一種大容量樣本集挖掘演算法，當樣本集比較小時不夠穩定；要求被選擇的屬性只能產生兩個子結點，當類別過多時，錯誤可能增加得比較快。

sklearn.tree.DecisionTreeClassifier

1.安裝graphviz.msi ， 一路next即可

ID3演算法就是在每次需要分裂時，計算每個屬性的增益率，然後選擇增益率最大的屬性進行分裂

按照好友密度劃分的信息增益：

按照是否使用真實頭像H劃分的信息增益

**所以，按先按好友密度劃分的信息增益比按真實頭像劃分的大。應先按好友密度劃分。

㈢ 一道高級c++演算法題！ csdn,高手請進! c++做做決策，可以寫出思路，但希望有詳細的指點！ c++高手我將付費

你留個qq吧

㈣ 結構化決策：對某一決策過程的環境及規則，能用確定的語言和過程描述，以適當的演算法產生

您好，中公教育為您服務。
【答案】 B 解析：這道題干中給出了兩個概念，結構化決策和非結構化決策，並分別對著兩個概念進行了解釋。根據問法，只問了非結構化決策，而且題干中兩個概念是互不相關的，那麼我們只要關注非結構化決策即可，即「決策過程復雜，不可能用確定的模型和語言來描述其決策過程，更無所謂最優解得決策。」
本題選項A、C、D都是比較簡單的方案，不符合復雜的，沒有確定模型和語言描述這樣的定義要點，只有B選項符合，故答案選擇B。

如有疑問，歡迎向中公教育企業知道提問。

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

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

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

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

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

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

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

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

先來看熵的概念：

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

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

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

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

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

㈥ 幾種常見的決策演算法

動態歸劃演算法，貪心演算法法。最大流演算法，最短路演算法。

㈦ 決策樹法的計算題

依據y坐標將六個點劃分為兩個子類，水平線上面的兩個點是同一個分類，但是水平線之下的四個點是不純凈的。

對這四個點進行再次分類，以x左邊分類，通過兩層分類，現了對樣本點的完全分類。

決策樹是一種具有樹狀結構的分類和預測工具，其中每個內部節點表示對一個屬性的測試，每個分支表示測試的結果，每個葉節點(終端節點)持有一個類標簽。

(7)決策演算法題擴展閱讀

決策樹演算法的關鍵

1、分裂屬性的選擇

即選擇哪個自變數作為樹叉，也就是在n個自變數中，優先選擇哪個自變數進行分叉。

2、樹剪枝

即在構建樹叉時，由於數據中的雜訊和離群點，許多分支反映的是訓練數據中的異常，而樹剪枝則是處理這種過分擬合的數據問題，常用的剪枝方法為先剪枝和後剪枝。

㈧ 畢業設計題目是（選用決策樹演算法的數據挖掘實例分析與設計）

應用遺傳演算法和決策樹演算法在數據挖掘中的比較
賈修一 MG0533024
(南京大學 計算機科學與技術系, 江蘇省南京市 210093)
A Comparision between the Genetic Algorithms and Decision Tree For Data
Mining
Abstract: This chapter introces the application with the genetic algorithms and ID3 for the data mining, choose
the better algorithm to classifier the given data sets through.the comparision between the two algorithms. And
analyzing the results of the experiment as well as reasons.
Key words: genetic algrithms; data ming; decision Tree
摘 要: 對訓練數據分別採用遺傳演算法和決策樹演算法進行數據挖掘,通過比較兩者實驗得出的結果,來選
擇更適合本數據集的演算法進行分類,並分析實驗結果及原因.
關鍵詞: 遺傳演算法;數據挖掘;決策樹演算法

1. 數據的描述
數據屬性有139351維,每個屬性的取值為0或1,分類標識只有兩類:A和I.數據的維數太高,在數
據預處理階段最好做屬性的約簡,進行降維的處理.
(1)數據維數太高,易造成一定的維數災難,使得分類挖掘時間過長.
(2)數據龐大,肯定有些噪音數據.
2.演算法的設計
為了提高最後分類的精確度,特設計了兩種方法進行比較,從中選出一種精確度高的方法.第一種是根
據數據的特點,每個屬性只取值0和1,所以進行屬性約簡的時候採用遺傳演算法.遺傳演算法的優點是可以對
大規模的數據進行一定的屬性約簡.
2.1 遺傳演算法描述:
(1) 遺傳演算法的步驟是編碼,選擇,交叉,變異.通過模仿自然界中的遺傳進化原理,來對數據進行
處理.而遺傳演算法的好壞取決於適應度函數的選擇,進化的次數,和交叉變異的合理性和概率性等,所以要
想設計一個合適的遺傳演算法必須經過大量的實驗.
(2) 就訓練數據而言,對每一維屬性的取值,在類標識一定的條件下,取1和取0的概率之間有個絕
對值差α1,α2,該差越大,說明該屬性的重要程度越高.同時還要考慮對同一維屬性,不論最終類標識是
什麼,取值都相同的話,則該屬性可以被認為是無效的屬性,對最後的分類沒有影響,所以適應度函數取對
每一維屬性的α1,α2的熵,熵越大,則屬性的重要程度就越低.
(3) 編碼階段,就把每一位屬性做為一個長度為139351的染色體的一個基因,1表示選擇該屬性,0
表示不選擇該屬性.隨機初始化8個種群,按照適應度函數的定義,從中選取4個適應度函數最小的染色體
做為父代.
(4) 將選出的父代進行交叉操作,因為是降維操作,所以交叉就是取兩個染色體之間隔位進行AND(與)
操作,變異就是按照一定的概率,在139351維上隨機的100位進行非操作,即:0變為1,1變為0.依次又
產生4個後代,結合原來的4個父代組成新的8個初始種群.進化50次.
然後利用貝葉斯方法進行分類.得到的是一個弱的學習器h,然後利用AdaBoost方法進行強化學習分類器.
2.2 AdaBoost演算法描述:
(1) 給定訓練集(x1,y1),(x2,y2),…,(xm,ym)m個.
(2) yi∈{-1,+1},實例xi∈X的正確標識.
(3) for t=1,…,T
2
{
構造{1,…,m}上的分布Dt,找出弱分類器 ht:X->{-1,+1},
同時在Dt產生很小的錯誤εt:
εt=PrDt[ht(xi)≠yi]
}
(4)構造 Dt,D1(i)=1/m
Dt+1(i)= Dt/Zt*exp(-αt*yi*ht(xi))//(注:yi和ht(xi)只能取值於{-1,+1})
其中Zt是歸一化因子(使Dt+1為分布)
αt=1/2*㏑((1-εt)/ εt)>0
(5)輸出最終分類器:Hfinal(x)=sign(∑αt*ht(x)).
第二種方法就是直接使用決策樹方法(ID3演算法)進行分類.求出每一維屬性的的信息增益,建立一棵
決策樹,利用決策樹來進行分類.
2.3 決策樹演算法(ID3)
(1)創建節點N;
(2)if samples都在同一個類C then
{
返回N作為葉結點,以類C標識;
}
(3)if attribut_list為空 then
{
返回N作為葉結點,標記為samples中最普通的類;
}
(4) 選擇attribute_list中具有最高信息增益的屬性test_attribute;標記節點N為test_attribute;
(5) for each test_attribute中的已知值a
由節點N長出一個條件為test_attribute=a的分枝;
(6) 設s是samples中test_attribute=a的樣本的集合;
(7) if s為空 then
加上一個樹葉,標記weisamples中最普通的類;
else
加上一個由ID3(s,attribute_list-test_attribute)返回的節點;
3. 實驗分析
就第一種方法:通過實驗,在進化次數上選取50次,使得維數約簡到1500維左右時得到的分類效果最
好,但由於種群是隨機產生的,所以在未進行boosting強化時正確率在60～85%之間,不是很穩定,但是符
合弱分類器的要求,即只要正確率超過50%就行,在進行boosting後,正確率能超過80%,但可能是數據進
行約簡的不好或進行迭代的次數選取不太合適,正確率卻沒有ID3的高.就本數據集而言,由於最終標識只
有2個,所以比較適合使用遺傳演算法和Adaboost進行訓練.正確率不高主要問題應該在:
(1)遺傳演算法的適應度函數沒有選好,不同的編碼方式對應不同的適應度函數取法,就本例而言,二進
制編碼方式應該是可以的,就是在對適應度函數取的時候沒有一個合適的數據表示,只好利用了熵的概念,
但在實際意義上感覺效果並不是很好.屬性約簡後正確率不高,這應該是最主要的原因.
(2)交叉變異的方式或許有問題,但是不是主要問題,只要適應度函數選好,也就是選擇操作正確的話,
這兩步操作對最終結果應該影響不大.
(3)進化次數的改進,通過實驗,考慮最後的正確率和運行時間,發現在進化50次和約簡到1500維時
賈修一:應用遺傳演算法和決策樹演算法在數據挖掘中的比較3
效果最好.但隨著適應度函數的不同,進化次數也不同.從理論上說,進化次數越多,效果也應該越好,最
終達到一個最優解,但同時要避免得到局部最優解,就需要對傳統的遺傳演算法進行改進,避免早熟問題.在
此就不討論.
(4)利用貝葉斯分類得到的弱學習器,在格式上並不和Adaboost完全適應,所以在應用的時候效果不
是很好,這也取決於迭代的次數和訓練樣集的選取.
就決策樹方法,對這么多維的屬性在某種意義上說並不合適,但就對本實驗給定的訓練樣例集而言,通
過建樹,只要6個結點就可以,而且正確率超過90%,所以,根據不同的數據集採用不同的方法得到的正確
率是不一樣的.所以在某種程度上說,奧卡姆剃刀原理是正確的.
由於時間有限,沒有對第一種方法進行一定的改進和進行其他方法的實驗,故最終採用ID3演算法進行分
類,採用前100個數據進行訓練,後10個進行測試,錯誤的只有1個.採用前80個數據進行訓練,後30
個進行測試的時候只有2個分類錯誤.正確率自測還是可以的.
4. 總結和感謝
通過本次實驗,最大的收獲就是採用了兩種不同的方法進行了實驗比較,雖然自己原先設計的演算法沒有
得到期望中的效果,並最終採用了其他的演算法,但是通過實驗,我對遺傳演算法和AdaBoost強化弱學習器方法
等有了更深的了解,也明白對不同的數據,是沒有一種萬能通用的解法的.以後會繼續改進自己的演算法,爭
取取得好的效果.最後感謝老師能提供這次實驗的數據.

㈨ 決策樹演算法原理

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

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

一棵決策樹的生成過程主要分為以下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。 當特徵在大多數樣本中具有零值時，與密集矩陣相比，稀疏矩陣輸入的訓練時間可以快幾個數量級。

㈩ 決策樹演算法之隨機森林

在 CART 分類回歸樹 的基礎之上，我們可以很容易的掌握隨機森林演算法，它們之間的區別在於，CART 決策樹較容易過擬合，而隨機森林可以在一定程度上解決該問題。

隨機森林的主要思想是：使用隨機性產生出一系列簡單的決策樹，並組合它們的預測結果為最終的結果，可謂三個臭皮匠賽過一個諸葛亮，下面我們就來具體了解一下。

產生隨機森林的步驟大致為三步

在第 1 步，它是一個可放回抽樣，即所產生的樣本是允許重復的，這種抽樣又被稱為 Bootstrap，例如我們有以下 mmy 數據

在做完 Bootstrap 之後，可能的樣本數據如下

可見，樣本數據中，第 3 條和第 4 條樣本是一樣的，都對應的是原始數據中的第 4 條。

接下來，就是要使用上面的樣本數據來產生決策樹了，產生決策樹的方法和 CART 基本一致，唯一的不同地方在於，節點的構建不是來自於全部的候選特徵，而是先從中隨機的選擇 n 個特徵，在這 n 個特徵中找出一個作為最佳節點。

舉個例子，假設 n = 2，且我們隨機選擇了「血液循環正常」和「血管堵塞」這兩個特徵來產生根節點，如下：

我們將在上述兩個特徵中選擇一個合適的特徵作為根節點，假設在計算完 Gini 不純度之後，「血液循環正常」這個特徵勝出，那麼我們的根節點便是「血液循環正常」，如下圖所示

接下來我們還需要構建根節點下面的節點，下一個節點將會在剩下的「胸口疼痛」、「血管堵塞」和「體重」三個特徵中產生，但我們依然不會計算所有這 3 個特徵的 Gini 不純度，而是從中隨機選擇 2 個特徵，取這 2 個特徵中的 Gini 不純度較低者作為節點。

例如我們隨機選到了「胸口疼痛」和「體重」這兩列，如下：

假設此時「體重」的 Gini 不純度更低，那麼第 2 個節點便是「體重」，如下圖：

繼續下去，我們便產生了一棵決策樹。

隨機森林是多棵決策樹，在產生完一棵決策樹後，接著會循環執行上述過程：Bootstrap 出訓練樣本，訓練決策樹，直到樹的數量達到設置值——通常為幾百棵樹。

現在我們產生了幾百棵樹的隨機森林，當我們要預測一條數據時，該怎麼做呢？我們會聚合這些樹的結果，選擇預測結果最多的那個分類作為最終的預測結果。

例如我們現在有一條數據：

該條數據被所有樹預測的結果如下：

上述結果聚合後為：

取最多的那項為最終的預測結果，即 Yes——該病人被診斷為患有心臟病。

以上，隨機森林的兩個過程： B ootstrap 和 Agg regate 又被稱為 Bagging 。

本文我們一起學習了隨機森林的演算法，和 CART 決策樹比起來，它主要被用來解決過擬合問題，其主要的思想為 Bagging，即隨機性有助於增強模型的泛化（Variance） 能力。

參考：

相關文章：