從根上理解決策樹演算法

⑴ 什麼是決策樹

決策樹是用二叉樹形圖來表示處理邏輯的一種工具。可以直觀、清晰地表達加工的邏輯要求。特別適合於判斷因素比較少、邏輯組合關系不復雜的情況。
決策樹提供了一種展示類似在什麼條件下會得到什麼值這類規則的方法。比如，在貸款申請中，要對申請的風險大小做出判斷，圖是為了解決這個問題而建立的一棵決策樹，從中我們可以看到決策樹的基本組成部分：決策節點、分支和葉子。
決策樹中最上面的節點稱為根節點，是整個決策樹的開始。本例中根節點是「收入>￥40,000」，對此問題的不同回答產生了「是」和「否」兩個分支。
決策樹的每個節點子節點的個數與決策樹在用的演算法有關。如CART演算法得到的決策樹每個節點有兩個分支，這種樹稱為二叉樹。允許節點含有多於兩個子節點的樹稱為多叉樹。
每個分支要麼是一個新的決策節點，要麼是樹的結尾，稱為葉子。在沿著決策樹從上到下遍歷的過程中，在每個節點都會遇到一個問題，對每個節點上問題的不同回答導致不同的分支，最後會到達一個葉子節點。這個過程就是利用決策樹進行分類的過程，利用幾個變數（每個變數對應一個問題）來判斷所屬的類別（最後每個葉子會對應一個類別）。
假如負責借貸的銀行官員利用上面這棵決策樹來決定支持哪些貸款和拒絕哪些貸款，那麼他就可以用貸款申請表來運行這棵決策樹，用決策樹來判斷風險的大小。「年收入>￥40,00」和「高負債」的用戶被認為是「高風險」，同時「收入<￥40,000」但「工作時間>5年」的申請，則被認為「低風險」而建議貸款給他/她。
數據挖掘中決策樹是一種經常要用到的技術，可以用於分析數據，同樣也可以用來作預測（就像上面的銀行官員用他來預測貸款風險）。常用的演算法有CHAID、 CART、 Quest 和C5.0。
建立決策樹的過程，即樹的生長過程是不斷的把數據進行切分的過程，每次切分對應一個問題，也對應著一個節點。對每個切分都要求分成的組之間的「差異」最大。
各種決策樹演算法之間的主要區別就是對這個「差異」衡量方式的區別。對具體衡量方式演算法的討論超出了本文的范圍，在此我們只需要把切分看成是把一組數據分成幾份，份與份之間盡量不同，而同一份內的數據盡量相同。這個切分的過程也可稱為數據的「純化」。看我們的例子，包含兩個類別--低風險和高風險。如果經過一次切分後得到的分組，每個分組中的數據都屬於同一個類別，顯然達到這樣效果的切分方法就是我們所追求的。
到現在為止我們所討論的例子都是非常簡單的，樹也容易理解，當然實際中應用的決策樹可能非常復雜。假定我們利用歷史數據建立了一個包含幾百個屬性、輸出的類有十幾種的決策樹，這樣的一棵樹對人來說可能太復雜了，但每一條從根結點到葉子節點的路徑所描述的含義仍然是可以理解的。決策樹的這種易理解性對數據挖掘的使用者來說是一個顯著的優點。
然而決策樹的這種明確性可能帶來誤導。比如，決策樹每個節點對應分割的定義都是非常明確毫不含糊的，但在實際生活中這種明確可能帶來麻煩（憑什麼說年收入￥40,001的人具有較小的信用風險而￥40,000的人就沒有）。
建立一顆決策樹可能只要對資料庫進行幾遍掃描之後就能完成，這也意味著需要的計算資源較少，而且可以很容易的處理包含很多預測變數的情況，因此決策樹模型可以建立得很快，並適合應用到大量的數據上。
對最終要拿給人看的決策樹來說，在建立過程中讓其生長的太「枝繁葉茂」是沒有必要的，這樣既降低了樹的可理解性和可用性，同時也使決策樹本身對歷史數據的依賴性增大，也就是說這是這棵決策樹對此歷史數據可能非常准確，一旦應用到新的數據時准確性卻急劇下降，我們稱這種情況為訓練過度。為了使得到的決策樹所蘊含的規則具有普遍意義，必須防止訓練過度，同時也減少了訓練的時間。因此我們需要有一種方法能讓我們在適當的時候停止樹的生長。常用的方法是設定決策樹的最大高度（層數）來限制樹的生長。還有一種方法是設定每個節點必須包含的最少記錄數，當節點中記錄的個數小於這個數值時就停止分割。
與設置停止增長條件相對應的是在樹建立好之後對其進行修剪。先允許樹盡量生長，然後再把樹修剪到較小的尺寸，當然在修剪的同時要求盡量保持決策樹的准確度盡量不要下降太多。
對決策樹常見的批評是說其在為一個節點選擇怎樣進行分割時使用「貪心」演算法。此種演算法在決定當前這個分割時根本不考慮此次選擇會對將來的分割造成什麼樣的影響。換句話說，所有的分割都是順序完成的，一個節點完成分割之後不可能以後再有機會回過頭來再考察此次分割的合理性，每次分割都是依賴於他前面的分割方法，也就是說決策樹中所有的分割都受根結點的第一次分割的影響，只要第一次分割有一點點不同，那麼由此得到的整個決策樹就會完全不同。那麼是否在選擇一個節點的分割的同時向後考慮兩層甚至更多的方法，會具有更好的結果呢？目前我們知道的還不是很清楚，但至少這種方法使建立決策樹的計算量成倍的增長，因此現在還沒有哪個產品使用這種方法。
而且，通常的分割演算法在決定怎麼在一個節點進行分割時，都只考察一個預測變數，即節點用於分割的問題只與一個變數有關。這樣生成的決策樹在有些本應很明確的情況下可能變得復雜而且意義含混，為此目前新提出的一些演算法開始在一個節點同時用多個變數來決定分割的方法。比如以前的決策樹中可能只能出現類似「收入<￥35,000」的判斷，現在則可以用「收入<(0.35*抵押)」或「收入>￥35,000或抵押<150,000」這樣的問題。
決策樹很擅長處理非數值型數據，這與神經網路只能處理數值型數據比起來，就免去了很多數據預處理工作。
甚至有些決策樹演算法專為處理非數值型數據而設計，因此當採用此種方法建立決策樹同時又要處理數值型數據時，反而要做把數值型數據映射到非數值型數據的預處理。

⑵ 決策樹（Decision Tree）

  決策樹（Decision Tree）是一種基本的分類與回歸方法，其模型呈樹狀結構，在分類問題中，表示基於特徵對實例進行分類的過程。本質上，決策樹模型就是一個定義在特徵空間與類空間上的條件概率分布。決策樹學習通常包括三個步驟： 特徵選擇 、 決策樹的生成 和 決策樹的修剪 。

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

  利用決策樹進行分類，從根節點開始，對實例的某一特徵進行測試，根據測試結果將實例分配到其子節點；這時，每一個子節點對應著該特徵的一個取值。如此遞歸地對實例進行測試並分配，直至達到葉節點。最後將實例分到葉節點的類中。

  決策樹是給定特徵條件下類的條件概率分布，這一條件概率分布定義在特徵區間的一個劃分（partiton）上。將特徵空間劃分為互不相交的單元（cell）或區域（region），並在每個單元定義一個類的概率分布就構成了一個條件概率分布。決策樹的一條路徑對應劃分中的一個單元，決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成。假設X為表示特徵的隨機變數，Y為表示類的隨機變數，那麼這個條件概率分布可以表示成P(Y|X)。X取值於給定劃分下單元的集合，Y取值於類的集合，各葉節點（單元）上的條件概率往往偏向於某一個類，即屬於某一類的概率較大，決策樹分類時將該節點的實例分到條件概率大的那一類去。也就以為著決策樹學習的過程其實也就是由數據集估計條件概率模型的過程，這些基於特徵區間劃分的類的條件概率模型由無窮多個，在進行選擇時，不僅要考慮模型的擬合能力還要考慮其泛化能力。

  為了使模型兼顧模型的擬合和泛化能力，決策樹學習使用正則化的極大似然函數來作為損失函數，以最小化損失函數為目標，尋找最優的模型。顯然從所有可能的決策樹中選取最優決策樹是NP完全問題，所以在實際中通常採用啟發式的方法，近似求解這一最優化問題： 通過遞歸的選擇最優特徵，根據該特徵對訓練數據進行劃分直到使得各個子數據集有一個最好的分類，最終生成特徵樹 。當然，這樣得到的決策樹實際上是次最優（sub-optimal）的。進一步的，由於決策樹的演算法特性，為了防止模型過擬合，需要對已生成的決策樹自下而上進行剪枝，將樹變得更簡單，提升模型的泛化能力。具體來說，就是去掉過於細分的葉節點，使其退回到父節點，甚至更高的節點，然後將父節點或更高的節點改為新的葉節點。如果數據集的特徵較多，也可以在進行決策樹學習之前，對數據集進行特徵篩選。

  由於決策樹是一個條件概率分布，所以深淺不同的決策樹對應著不同復雜度的概率模型，決策樹的生成對應模型的局部選擇，決策樹的剪枝對應著模型的全局選擇。

   熵（Entropy） 的概念最早起源於物理學，最初物理學家用這個概念度量一個熱力學系統的無序程度。在1948年， 克勞德·艾爾伍德·香農 將熱力學的熵，引入到 資訊理論 ，因此它又被稱為 香農熵 。在資訊理論中，熵是對不確定性的量度，在一條信息的熵越高則能傳輸越多的信息，反之，則意味著傳輸的信息越少。

  如果有一枚理想的硬幣，其出現正面和反面的機會相等，則拋硬幣事件的熵等於其能夠達到的最大值。我們無法知道下一個硬幣拋擲的結果是什麼，因此每一次拋硬幣都是不可預測的。因此，使用一枚正常硬幣進行若干次拋擲，這個事件的熵是一 比特 ，因為結果不外乎兩個——正面或者反面，可以表示為 0, 1 編碼，而且兩個結果彼此之間相互獨立。若進行 n 次 獨立實驗 ，則熵為 n ，因為可以用長度為 n 的比特流表示。但是如果一枚硬幣的兩面完全相同，那個這個系列拋硬幣事件的熵等於零，因為 結果能被准確預測 。現實世界裡，我們收集到的數據的熵介於上面兩種情況之間。

  另一個稍微復雜的例子是假設一個 隨機變數 X ，取三種可能值 ，概率分別為 ，那麼編碼平均比特長度是： 。其熵為 。因此<u>熵實際是對隨機變數的比特量和順次發生概率相乘再總和的</u> 數學期望 。

  依據玻爾茲曼H定理，香農把隨機變數X的熵 定義為：

  其中 是隨機變數X的信息量，當隨機變數取自有限樣本時，熵可以表示為：

  若 ，則定義 。

  同理可以定義條件熵 :

  很容易看出，條件熵（conditional entropy） 就是X給定條件下Y的條件概率分布的熵對X的數學期望。當熵和條件熵中的概率有極大似然估計得到時，所對應的熵和條件熵分別稱為檢驗熵（empirical entropy）和經驗條件熵（empirical conditional entropy）.

  熵越大，隨機變數的不確定性就越大，從定義可以驗證:

  當底數 時，熵的單位是 ；當 時，熵的單位是 ;而當 時，熵的單位是 .

  如英語有26個字母，假如每個字母在文章中出現的次數平均的話，每個字母的信息量 為：

  同理常用漢字2500有個，假設每個漢字在文章中出現的次數平均的話，每個漢字的信息量 為：

  事實上每個字母和漢字在文章中出現的次數並不平均，少見字母和罕見漢字具有相對較高的信息量，顯然，由期望的定義，熵是整個消息系統的平均消息量。

  熵可以用來表示數據集的不確定性，熵越大，則數據集的不確定性越大。因此使用 劃分前後數據集熵的差值 量度使用當前特徵對於數據集進行劃分的效果（類似於深度學習的代價函數）。對於待劃分的數據集 ，其劃分前的數據集的熵 是一定的，但是劃分之後的熵 是不定的， 越小說明使用此特徵劃分得到的子集的不確定性越小（也就是純度越高）。因此 越大，說明使用當前特徵劃分數據集 時，純度上升的更快。而我們在構建最優的決策樹的時候總希望能更快速到達純度更高的數據子集，這一點可以參考優化演算法中的梯度下降演算法，每一步沿著負梯度方法最小化損失函數的原因就是負梯度方向是函數值減小最快的方向。同理：在決策樹構建的過程中我們總是希望集合往最快到達純度更高的子集合方向發展，因此我們總是選擇使得信息增益最大的特徵來劃分當前數據集 。

  顯然這種劃分方式是存在弊端的，按信息增益准則的劃分方式，當數據集的某個特徵B取值較多時，依此特徵進行劃分更容易得到純度更高的數據子集，使得 偏小，信息增益會偏大，最終導致信息增益偏向取值較多的特徵。

  設 是 個數據樣本的集合，假定類別屬性具有 個不同的值： ,設 是類 中的樣本數。對於一個給定樣本，它的信息熵為：

  其中， 是任意樣本屬於 的概率，一般可以用 估計。

  設一個屬性A具有 個不同的值 ，利用屬性A將集合 劃分為 個子集 ，其中 包含了集合 中屬性 取 值的樣本。若選擇屬性A為測試屬性，則這些子集就是從集合 的節點生長出來的新的葉節點。設 是子集 中類別為 的樣本數，則根據屬性A劃分樣本的信息熵為：

  其中 , 是子集 中類別為 的樣本的概率。最後，用屬性A劃分樣本子集 後所得的 信息增益(Gain) 為：

  即，<u>屬性A的信息增益=劃分前數據的熵-按屬性A劃分後數據子集的熵</u>。 信息增益（information gain）又稱為互信息（matual information）表示得知特徵X的信息而使得類Y的信息的不確定性減少的程度 。信息增益顯然 越小， 的值越大，說明選擇測試屬性A對於分類提供的信息越多，選擇A之後對分類的不確定程度越小。

  經典演算法 ID3 使用的信息增益特徵選擇准則會使得劃分更偏相遇取值更多的特徵，為了避免這種情況。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基礎上將特徵選擇准則由 信息增益 改為了 信息增益率 。在信息增益的基礎之上乘上一個懲罰參數。特徵個數較多時，懲罰參數較小；特徵個數較少時，懲罰參數較大（類似於正則化）。這個懲罰參數就是 分裂信息度量 的倒數 。

  不同於 ID3 和 C4.5 , CART 使用基尼不純度來作為特徵選擇准則。基尼不純度也叫基尼指數 , 表示在樣本集合中一個隨機選中的樣本被分錯的概率 則<u>基尼指數（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率</u>。Gini指數越小表示集合中被選中的樣本被分錯的概率越小，也就是說集合的純度越高，反之，集合越不純。

樣本集合的基尼指數：
樣本集合 有m個類別， 表示第 個類別的樣本數量,則 的Gini指數為：

基於某個特徵劃分樣本集合S之後的基尼指數：
  CART是一個二叉樹，也就是當使用某個特徵劃分樣本集合後，得到兩個集合：a.等於給定的特徵值的樣本集合 ；b.不等於給定特徵值的樣本集合 。實質上是對擁有多個取值的特徵的二值處理。

對於上述的每一種劃分，都可以計算出基於劃分特=某個特徵值將樣本集合劃分為兩個子集的純度：

因而對於一個具有多個取值（超過2個）的特徵，需要計算以每個取值為劃分點，對樣本集合劃分後子集的純度 ( 表示特徵 的可能取值)然後從所有的劃分可能 中找出Gini指數最小的劃分，這個劃分的劃分點，就是使用特徵 對樣本集合 進行劃分的最佳劃分點。

參考文獻 ：

決策樹--信息增益，信息增益比，Geni指數的理解

【機器學習】深入理解--信息熵（Information Entropy）

統計學習方法 （李航）

  為了便於理解，利用以下數據集分別使用三種方法進行分類：

  在進行具體分析之前，考慮到收入是數值類型，要使用決策樹演算法，需要先對該屬性進行離散化。
  在機器學習演算法中，一些分類演算法（ID3、Apriori等）要求數據是分類屬性形式，因此在處理分類問題時經常需要將一些連續屬性變換為分類屬性。一般來說，連續屬性的離散化都是通過在數據集的值域內設定若干個離散的劃分點，將值域劃分為若干區間，然後用不同的符號或整數數值代表落在每個子區間中的數據值。所以，離散化最核心的兩個問題是：如何確定分類數以及如何將連續屬性映射到這些分類值。常用的離散化方法有 等寬法 ， 等頻法 以及 一維聚類法 等。

在實際使用時往往使用Pandas的 cut() 函數實現等寬離散化:

  可以看到與手工計算的離散化結果相同，需要注意的是，<u> 等寬法對於離群點比較敏感，傾向於不均勻地把屬性值分布到各個區間，導致某些區間數據較多，某些區間數據很少，這顯然不利用決策模型的建立。 </u>

使用四個分位數作為邊界點，對區間進行劃分：

<u> 等頻率離散化雖然避免了等寬離散化的數據分布不均勻的問題,卻可能將相同的數據值分到不同的區間以滿足每個區間具有相同數量的屬性取值的要求。 </u>

使用一維聚類的離散化方法後得到數據集為：

  在本次實例中選擇使用基於聚類的離散化方法後得到的數據集進行指標計算。為了預測客戶能否償還債務，使用A（擁有房產）、B（婚姻情況）、C（年收入）等屬性來進行數據集的劃分最終構建決策樹。

單身 ：

離婚 ：

已婚 ：

顯然，由B屬性取值'已婚'劃分得到的子數據集屬於同一個葉節點，無法再進行分類。
接下來，對由B屬性取值'單身'劃分得到的子數據集 再進行最優特徵選擇：

1）計算數據集 總的信息熵，其中4個數據中，能否償還債務為'是'數據有3，'否'數據有1,則總的信息熵：

2）對於A(擁有房產)屬性，其屬性值有'是'和'否'兩種。其中，在A為'是'的前提下，能否償還債務為'是'的有1、'否'的有0；在A為'否'的前提下，能否償還債務為'是'的有2、為'否'的有1，則A屬性的信息熵為：

3)對於B（婚姻情況）屬性，由於已被確定，在這個數據子集信息熵為0

4)對於C（年收入）屬性，其屬性值有'中等輸入'、'低收入'兩種。在C為'中等收入'的前提下，能否償還作為為'是'的有1,為'否'的有0；在C為'低收入'的前提下，能否償還作為為'是'的有2,為'否'的有1;則C屬性的信息熵為：

5）最後分別計算兩個屬性的信息增益值：


信息增益值相同，說明以兩個屬性對數據子集進行劃分後決策樹的純度上升是相同的，此時任選其一成為葉節點即可。
同理，對數據子集 進行最優特徵選擇，發現信息熵為0：
整理得到最終的決策樹：

⑶ 決策樹的原理及演算法

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

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

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

剪枝就是給決策樹瘦身，防止過擬合。分為「預剪枝」（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 丨決策樹（上）：要不要去打籃球？決策樹來告訴你

⑷ 決策樹演算法

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

演算法理論：

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

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

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

決策樹是什麼？

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

決策樹的目標是什麼？

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

    表現為「熵」（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， 葉子節點覆蓋的樣本未必是同一類，所佔的大多數，那麼該葉子節點的類別就是那個佔大多數的類

⑹ 決策樹演算法-原理篇

關於決策樹演算法，我打算分兩篇來講，一篇講思想原理，另一篇直接擼碼來分析演算法。本篇為原理篇。
通過閱讀這篇文章，你可以學到：
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都是基於特徵選擇進行優化。

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

⑺ 決策樹的理解與應用

決策樹🌲是一種基本的分類和回歸的方法【以前總是下意識以為決策樹只能用於分類，事實上還可以用於回歸】。在分類問題中，決策樹基於特徵對實例進行分類，這個分類過程可以認為是if-then的規則集合，也可以認為是特徵空間與類空間上的條件概率分布。

NOTE:
if—then規則集合具有一個重要的特徵：互斥且完備，即每個實例都被一條路徑或者一條規則所覆蓋，而且只能被一條路徑或一條規則所覆蓋

優點 ：簡單易理解、分類速度快

過程 ：利用損失函數最小化原則對訓練集進行建模，再利用建立好的模型進行分類。決策樹的學習演算法通常是遞歸地選擇最優特徵，並根據特徵對訓練集進行分割，最終形成從【根結點->葉子結點】的樹模型， 但是這樣生成的樹可以容易發生過擬合，所以需要自底向上修剪✋

決策樹學習包括三個步驟：特徵選擇、決策樹生成、決策樹修剪
1.當特徵數量較多時，在學習之前先進行特徵選擇
2.決策樹生成對應局部最優
3.決策樹修剪對應全局最優

目標 ：選擇一個與訓練數據矛盾較小的決策樹，同時具有很好的泛化能力。

通常，特徵選擇的准則是 信息增益或者信息增益比

先介紹基本概念：

決策樹的生成過程僅考慮到對訓練數據集分類的准確性，這樣生成的樹模型容易出現過擬合且構建的樹過於復雜，所以有必要對其進行剪枝。

剪枝 ：從已生成的樹上裁掉一些子樹或者葉結點，並將其根結點或者父結點作為新的葉結點，從而簡化分類樹模型。 剪枝往往是通過極小化決策樹的整體損失函數來實現的

定義損失函數 ：
設樹 的葉結點個數為 , 是樹的葉結點，該葉結點有 個樣本點，其中 類的樣本點有 ，其中 是葉子結點 的經驗熵， 為參數，決策樹學習的損失函數為：

其中
所以最終的損失函數表示為：

公式解釋： 是表示模型對訓練集的預測誤差，即模型與訓練集的擬合程度， 表示模型的復雜度，葉子節點數越大模型越復雜， 是調節參數，控制模型的擬合和復雜程度。
當 確定時，選擇損失函數最小的模型，這里定義的損失函數其實等價於正則化的極大似然估計。

演算法：
INPUT: 生成演算法產生的整個樹 ，參數
OUPUT: 修剪後的子樹
1.計算每個結點的經驗熵
2.遞歸地從樹的葉結點向上回縮
回縮前後整體樹的損失函數比較，如果回縮前的損失函數大於回縮後，進行剪枝。
3.重復2，直到不能繼續為止，得到損失函數最小的子樹

後期加入

總結：決策樹是一種簡單快速的分類演算法，本文不僅把熵相關的概念給整理了一遍，文中信息增益和信息增益比也可以用於其他模型的特徵選擇，而最後剪枝部分提到的決策樹的損失函數是我之前在專門寫的《詳述機器學習中的損失函數》博客中沒有提到的，這里也是一個補充。

⑻ 決策樹演算法原理

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

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

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

⑼ 決策樹演算法的基本思想

1）樹以代表訓練樣本的單個結點開始。
2）如果樣本都在同一個類．則該結點成為樹葉，並用該類標記。
3）否則，演算法選擇最有分類能力的屬性作為決策樹的當前結點．
4）根據當前決策結點屬性取值的不同，將訓練樣本數據集tlI分為若乾子集，每個取值形成一個分枝，有幾個取值形成幾個分枝。勻針對上一步得到的一個子集，重復進行先前步驟，遞4'I形成每個劃分樣本上的決策樹。一旦一個屬性出現在一個結點上，就不必在該結點的任何後代考慮它。
5）遞歸劃分步驟僅當下列條件之一成立時停止：
①給定結點的所有樣本屬於同一類。
②沒有剩餘屬性可以用來進一步劃分樣本．在這種情況下．使用多數表決，將給定的結點轉換成樹葉，並以樣本中元組個數最多的類別作為類別標記，同時也可以存放該結點樣本的類別分布，
③如果某一分枝tc，沒有滿足該分支中已有分類的樣本，則以樣本的多數類創建一個樹葉。

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

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