實現決策樹演算法步驟

⑴ 如何畫決策樹

畫決策樹的步驟如下：

A、先畫一個方框作為出發點，又稱決策節點；
B、從出發點向右引出若干條直線，這些直線叫做方案枝；
C、在每個方案枝的末端畫一個圓圈，這個圓圈稱為概率分叉點，或自然狀態點；
D、從自然狀態點引出代表各自然狀態的分枝，稱為概率分枝；
E、如果問題只需要一級決策，則概率分枝末端畫三角形，表示終點。


例題）
假設有一項工程，施工管理人員需要決定下月是否開工。如果開工後天氣好，則可為國家創收4萬元，若開工後天氣壞，將給國家造成損失1萬元，不開工則損失1000元。根據過去的統計資料，下月天氣好的概率是0.3,天氣壞的概率是0.7。請做出決策。現採用決策樹方法進行決策
【解】第一步：將題意表格化

⑵ 決策樹演算法

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

演算法理論：

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

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

⑶ 決策樹法分為那幾個步驟

1、特徵選擇

特徵選擇決定了使用哪些特徵來做判斷。在訓練數據集中，每個樣本的屬性可能有很多個，不同屬性的作用有大有小。因而特徵選擇的作用就是篩選出跟分類結果相關性較高的特徵，也就是分類能力較強的特徵。在特徵選擇中通常使用的准則是：信息增益。

2、決策樹生成

選擇好特徵後，就從根節點觸發，對節點計算所有特徵的信息增益，選擇信息增益最大的特徵作為節點特徵，根據該特徵的不同取值建立子節點；對每個子節點使用相同的方式生成新的子節點，直到信息增益很小或者沒有特徵可以選擇為止。

3、決策樹剪枝

剪枝的主要目的是對抗「過擬合」，通過主動去掉部分分支來降低過擬合的風險。

【簡介】

決策樹是一種解決分類問題的演算法，決策樹演算法採用樹形結構，使用層層推理來實現最終的分類。

⑷ 決策樹的演算法

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 模型構建的預測樹在很多情況下比常用的統計方法構建的代數學預測准則更加准確，且數據越復雜、變數越多，演算法的優越性就越顯著。模型的關鍵是預測准則的構建，准確的。
定義：
分類和回歸首先利用已知的多變數數據構建預測准則, 進而根據其它變數值對一個變數進行預測。在分類中, 人們往往先對某一客體進行各種測量, 然後利用一定的分類准則確定該客體歸屬那一類。例如, 給定某一化石的鑒定特徵, 預測該化石屬那一科、那一屬, 甚至那一種。另外一個例子是, 已知某一地區的地質和物化探信息, 預測該區是否有礦。回歸則與分類不同, 它被用來預測客體的某一數值, 而不是客體的歸類。例如, 給定某一地區的礦產資源特徵, 預測該區的資源量。

⑸ 決策樹的原理及演算法

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

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

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

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

⑹ 決策樹分析方法的基本步驟

決策樹分析方法的基本步驟

1.繪制決策樹圖。從左到右的順序畫決策樹，此過程本身就是對決策問題的再分析過程。

2.按從右到左的順序計算各方案的期望值，並將結果寫在相應方案節點上方。期望值的計算是從右到左沿著決策樹的反方向進行計算的。

3.對比各方案的期望值的大小，將期望值小的方案(即劣等方案)剪掉，所剩的最後方案為最佳方案。

決策樹(簡稱DT)利用概率論的原理，並且利用一種樹形圖作為分析工具。其基本原理是用決策點代表決策問題，用方案分枝代表可供選擇的方案，用概率分枝代表方案可能出現的各種結果，經過對各種方案在各種結果條件下損益值的計算比較，為決策者提供決策依據。

缺點：

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都是基於特徵選擇進行優化。

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

⑻ 決策樹演算法的介紹

決策樹演算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進行處理，利用歸納演算法生成可讀的規則和決策樹，然後使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。決策樹方法最早產生於上世紀60年代，到70年代末。由J Ross Quinlan提出了ID3演算法，此演算法的目的在於減少樹的深度。但是忽略了葉子數目的研究。C4.5演算法在ID3演算法的基礎上進行了改進，對於預測變數的缺值處理、剪枝技術、派生規則等方面作了較大改進，既適合於分類問題，又適合於回歸問題。決策樹演算法構造決策樹來發現數據中蘊涵的分類規則．如何構造精度高、規模小的決策樹是決策樹演算法的核心內容。決策樹構造可以分兩步進行。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用於數據分析處理的數據集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進行檢驗、校正和修下的過程，主要是用新的樣本數據集（稱為測試數據集）中的數據校驗決策樹生成過程中產生的初步規則，將那些影響預衡准確性的分枝剪除。

⑼ 決策樹(decisionTree)

決策樹(decisionTree)是一種基本的分類和回歸方法。此文僅討論用於分類方法的決策樹。

決策樹的學習通常分為3步：

決策樹的學習的思想主要源於

定義決策樹 ：

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

其中，圓表示內部結點，方框表示葉結點。

if-then規則，簡單來說就是 ：

舉例：對於一個蘋果，外表是紅色的是紅蘋果，外表是綠色的是青蘋果。可以表示為：

if-then規則集合具有一個重要的性質：

這就是說每一個實例都被一條路徑或規則覆蓋，並且只被一條路徑或規則覆蓋。這里所謂的覆蓋是指實例的特徵與路徑上的特徵一致，或實例滿足規則的條件。

給定數據集：

其中， 為輸入實例（特徵向量），含有 個特徵， 為類標記， , 為樣本容量。

目標 ：
根據給定的訓練數據集構建一個決策樹模型，使它能夠對實例進行正確分類。

特徵選擇在於選取對訓練數據具有分類能力的特徵，這樣可以提高決策樹學習的效率。

如果我們利用某一個特徵進行分類的結果與隨機分類的結果沒什麼很大的差別的話，則稱這個特徵沒有分類能力。

那麼問題來了，怎麼選擇特徵呢？

通常特徵選擇的准則是

下面通過例子來說明一下。

目標 ：
希望通過所給的訓練集數據，學習一個貸款申請的決策樹。當新的客戶提出貸款申請的時候，根據申請人的特徵利用決策樹決定是否批准貸款申請。

可見這里共有4個特徵可供選擇。用特徵選擇的准則是 。接下來介紹 。

：
熵是表示隨機變數不確定性的度量。

設 是一個取有限個值的隨機變數，其概率分布為

則隨機變數 的熵定義為

若 ，則定義 。通常對數取以2為底，或是以 為底，熵的單位分布為比特（bit）或是納特（nat）。
由上式可知，熵只依賴 的分布，而已 的值無關，則 的熵還可記作 ，即

則從定義可知

當隨機變數只取2個值的時候，例如 時， 的分布為

熵為

熵隨概率變化的曲線為

當 或 時 ，隨機變數完全沒有不確定性，當 時 ，熵取值最大，隨機變數不確定性最大。

設隨機變數 ，其聯合概率分布

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

信息增益
特徵 對訓練集 的信息增益

根據信息增益准則的特徵選擇方法：對訓練集 ，計算其每個特徵的信息增益，並比較大小，選擇信息增益最大的特徵。

前期定義各個量：

信息增益的演算法
輸入：訓練集 和特徵 ；
輸出：特徵 對訓練集 的信息增益

回看剛才的例子，

解 ：

這一次我很無聊的想用一下.csv文件類型。

所以訓練數據集部分如下，我存在一個loan.csv文件里了。對.csv文件的各種處理一般由python的pandas模塊完成。

第一步，導入相關模塊

第二步，讀入數據

若是使用jupyter，可以即刻查看一下數據，和數據標簽。

可以看出，除了'ID'之外前4個標簽 'age', 'work', 'own house', 'Credit conditions'為我們一直在說的特徵 ，而最後一個標簽'label'是我們所說的類 ，所以要處理一下這些標簽，

第三步，計算訓練集 的熵 ：

這里會用到pandas的一個統計數據的功能， groupby(by = [列]).groups ，將數據統計成字典的形式，這么說比較抽象，看下圖，將我們用pandas讀入的data，分為2類， ， Index 表示索引，即第0，1，4，5，6，14（python計數從0開始）個數據的 ，第2，3，7，8，9，10，11，12，13個數據的 .

那麼計算訓練集 的熵

第四步，計算特徵 對數據集 的條件熵

第五步 ，計算信息增益

輸入：訓練集 和特徵 和閾值 ；
輸出：決策樹
(1) 中所有實例都屬於同一類 ，則 為單結點樹，並將類 作為該結點的類標記，返回 ；
(2) 若 ，則 為單結點樹，並將 中實例數最大的類 作為該結點的類標記，返回 ；
(3)否則，按照上述信息增益的演算法，計算 中各個特徵對 的信息增益，選擇信息增益最大的特徵 ；
(4)如果特徵 的信息增益小於閾值 ，將置 為單結點樹，並將 中實例數最大的類 作為該結點的類標記，返回 ；
(5)否則，對 的每一個可能值 ，依 將 分割為若干非空子集 ，將 中實例數最大的類 作為該結點的類標記，構建子結點，由結點及其子結點構成樹 ，返回 ；
(6)對第 個子結點，以 為訓練集，以 為特徵集，遞歸的調用步驟(1)~步驟(5)，得到子樹 ，返回 。

對上述表的訓練集數據，利用ID3演算法建立決策樹。

解 ：

第一次迭代 ：

【特徵：有自己的房子】將數據集 劃分為2個子集 （有自己的房子）和 （沒有自己的房子），觀察一下 和 ：

：

由於 所有實例都屬於同一類 ，所以它是一個葉結點，結點的類標記為「是」。

：

對於 則需從特徵 中選擇新的特徵。

第二次迭代 ：

將 看作新的數據集 。【特徵：有工作】有2個可能值，劃分為2個子集 （有工作）和 （沒有工作），觀察一下 和 ：

：

由於 所有實例都屬於同一類 ，所以它是一個葉結點，結點的類標記為「是」。

：

⑽ 決策樹（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：
整理得到最終的決策樹：