id3演算法的流程圖

❶ 大數據經典演算法解析（1）一C4.5演算法

姓名：崔升    學號：14020120005

【嵌牛導讀】：

C4.5作為一種經典的處理大數據的演算法，是我們在學習互聯網大數據時不得不去了解的一種常用演算法

【嵌牛鼻子】：經典大數據演算法之C4.5簡單介紹

【嵌牛提問】：C4.5是一種怎麼的演算法，其決策機制靠什麼實現？

【嵌牛正文】：

決策樹模型：

決策樹是一種通過對特徵屬性的分類對樣本進行分類的樹形結構，包括有向邊與三類節點：

根節點（root node），表示第一個特徵屬性，只有出邊沒有入邊；

內部節點（internal node），表示特徵屬性，有一條入邊至少兩條出邊

葉子節點（leaf node），表示類別，只有一條入邊沒有出邊。

上圖給出了（二叉）決策樹的示例。決策樹具有以下特點：

對於二叉決策樹而言，可以看作是if-then規則集合，由決策樹的根節點到葉子節點對應於一條分類規則;

分類規則是 互斥並且完備 的，所謂 互斥 即每一條樣本記錄不會同時匹配上兩條分類規則，所謂 完備 即每條樣本記錄都在決策樹中都能匹配上一條規則。

分類的本質是對特徵空間的劃分，如下圖所示，

決策樹學習：

決策樹學習的本質是從訓練數據集中歸納出一組分類規則[2]。但隨著分裂屬性次序的不同，所得到的決策樹也會不同。如何得到一棵決策樹既對訓練數據有較好的擬合，又對未知數據有很好的預測呢？

首先，我們要解決兩個問題：

如何選擇較優的特徵屬性進行分裂？每一次特徵屬性的分裂，相當於對訓練數據集進行再劃分，對應於一次決策樹的生長。ID3演算法定義了目標函數來進行特徵選擇。

什麼時候應該停止分裂？有兩種自然情況應該停止分裂，一是該節點對應的所有樣本記錄均屬於同一類別，二是該節點對應的所有樣本的特徵屬性值均相等。但除此之外，是不是還應該其他情況停止分裂呢？

2. 決策樹演算法

特徵選擇

特徵選擇指選擇最大化所定義目標函數的特徵。下面給出如下三種特徵（Gender, Car Type, Customer ID）分裂的例子：

圖中有兩類類別（C0, C1），C0: 6是對C0類別的計數。直觀上，應選擇Car Type特徵進行分裂，因為其類別的分布概率具有更大的傾斜程度，類別不確定程度更小。

為了衡量類別分布概率的傾斜程度，定義決策樹節點tt的不純度（impurity），其滿足：不純度越小，則類別的分布概率越傾斜；下面給出不純度的的三種度量：

其中，p(ck|t)p(ck|t)表示對於決策樹節點tt類別ckck的概率。這三種不純度的度量是等價的，在等概率分布是達到最大值。

為了判斷分裂前後節點不純度的變化情況，目標函數定義為信息增益（information gain）：

I(⋅)I(⋅)對應於決策樹節點的不純度，parentparent表示分裂前的父節點，NN表示父節點所包含的樣本記錄數，aiai表示父節點分裂後的某子節點，N(ai)N(ai)為其計數，nn為分裂後的子節點數。

特別地，ID3演算法選取 熵值 作為不純度I(⋅)I(⋅)的度量，則

cc指父節點對應所有樣本記錄的類別；AA表示選擇的特徵屬性，即aiai的集合。那麼，決策樹學習中的信息增益ΔΔ等價於訓練數據集中 類與特徵的互信息 ，表示由於得知特徵AA的信息訓練數據集cc不確定性減少的程度。

在特徵分裂後，有些子節點的記錄數可能偏少，以至於影響分類結果。為了解決這個問題，CART演算法提出了只進行特徵的二元分裂，即決策樹是一棵二叉樹；C4.5演算法改進分裂目標函數，用信息增益比（information gain ratio）來選擇特徵：

因而，特徵選擇的過程等同於計算每個特徵的信息增益，選擇最大信息增益的特徵進行分裂。此即回答前面所提出的第一個問題（選擇較優特徵）。ID3演算法設定一閾值，當最大信息增益小於閾值時，認為沒有找到有較優分類能力的特徵，沒有往下繼續分裂的必要。根據最大表決原則，將最多計數的類別作為此葉子節點。即回答前面所提出的第二個問題（停止分裂條件）。

決策樹生成：

ID3演算法的核心是根據信息增益最大的准則，遞歸地構造決策樹；演算法流程如下：

如果節點滿足停止分裂條件（所有記錄屬同一類別 or 最大信息增益小於閾值），將其置為葉子節點；

選擇信息增益最大的特徵進行分裂；

重復步驟1-2，直至分類完成。

C4.5演算法流程與ID3相類似，只不過將信息增益改為 信息增益比 。

3. 決策樹剪枝

過擬合

生成的決策樹對訓練數據會有很好的分類效果，卻可能對未知數據的預測不準確，即決策樹模型發生過擬合（overfitting）——訓練誤差（training error）很小、泛化誤差（generalization error，亦可看作為test error）較大。下圖給出訓練誤差、測試誤差（test error）隨決策樹節點數的變化情況：

可以觀察到，當節點數較小時，訓練誤差與測試誤差均較大，即發生了欠擬合（underfitting）。當節點數較大時，訓練誤差較小，測試誤差卻很大，即發生了過擬合。只有當節點數適中是，訓練誤差居中，測試誤差較小；對訓練數據有較好的擬合，同時對未知數據有很好的分類准確率。

發生過擬合的根本原因是分類模型過於復雜，可能的原因如下：

訓練數據集中有噪音樣本點，對訓練數據擬合的同時也對噪音進行擬合，從而影響了分類的效果；

決策樹的葉子節點中缺乏有分類價值的樣本記錄，也就是說此葉子節點應被剪掉。

剪枝策略

為了解決過擬合，C4.5通過剪枝以減少模型的復雜度。[2]中提出一種簡單剪枝策略，通過極小化決策樹的整體損失函數（loss function）或代價函數（cost function）來實現，決策樹TT的損失函數為：

其中，C(T)C(T)表示決策樹的訓練誤差，αα為調節參數，|T||T|為模型的復雜度。當模型越復雜時，訓練的誤差就越小。上述定義的損失正好做了兩者之間的權衡。

如果剪枝後損失函數減少了，即說明這是有效剪枝。具體剪枝演算法可以由動態規劃等來實現。

4. 參考資料

[1] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introction to Data Mining .

[2] 李航，《統計學習方法》.

[3] Naren Ramakrishnan, The Top Ten Algorithms in Data Mining.

❷ 簡述ID3演算法基本原理和步驟

1.基本原理：
以信息增益/信息熵為度量，用於決策樹結點的屬性選擇的標准，每次優先選取信息量最多（信息增益最大）的屬性，即信息熵值最小的屬性，以構造一顆熵值下降最快的決策樹，到葉子節點處的熵值為0。（信息熵 無條件熵 條件熵 信息增益 請查找其他資料理解）
決策樹將停止生長條件及葉子結點的類別取值：
①數據子集的每一條數據均已經歸類到每一類，此時，葉子結點取當前樣本類別值。
②數據子集類別仍有混亂，但已經找不到新的屬性進行結點分解，此時，葉子結點按當前樣本中少數服從多數的原則進行類別取值。
③數據子集為空，則按整個樣本中少數服從多數的原則進行類別取值。

步驟：
理解了上述停止增長條件以及信息熵，步驟就很簡單

❸ 決策樹ID3，C4.5，CART演算法中某一屬性分類後，是否能運用該屬性繼續分類

決策樹主要有ID3，C4.5，CART等形式。ID3選取信息增益的屬性遞歸進行分類，C4.5改進為使用信息增益率來選取分類屬性。CART是Classfication and Regression Tree的縮寫。表明CART不僅可以進行分類，也可以進行回歸。其中使用基尼系數選取分類屬性。以下主要介紹ID3和CART演算法。
ID3演算法：
信息熵： H(X)=-sigma（對每一個x）（plogp） H(Y|X)=sigma(對每一個x)（pH(Y|X=xi)）
信息增益：H（D）-H(D|X) H(D)是整個數據集的熵
信息增益率：（H(D)-H(D|X)）/H(X)
演算法流程：（1）對每一個屬性計算信息增益，若信息增益小於閾值，則將該支置為葉節點，選擇其中個數最多的類標簽作為該類的類標簽。否則，選擇其中最大的作為分類屬 性。
（2）若各個分支中都只含有同一類數據，則將這支置為葉子節點。
否則 繼續進行（1）。
CART演算法：
基尼系數：Gini（p）=sigma（每一個類）p(1-p)
回歸樹：屬性值為連續實數。將整個輸入空間劃分為m塊，每一塊以其平均值作為輸出。f(x)=sigma(每一塊)Cm*I(x屬於Rm)
回歸樹生成：（1）選取切分變數和切分點，將輸入空間分為兩份。
（2）每一份分別進行第一步，直到滿足停止條件。
切分變數和切分點選取：對於每一個變數進行遍歷，從中選擇切分點。選擇一個切分點滿足分類均方誤差最小。然後在選出所有變數中最小分類誤差最小的變數作為切分 變數。
分類樹：屬性值為離散值。
分類樹生成：（1）根據每一個屬性的每一個取值，是否取該值將樣本分成兩類，計算基尼系數。選擇基尼系數最小的特徵和屬性值，將樣本分成兩份。
（2）遞歸調用（1）直到無法分割。完成CART樹生成。

決策樹剪枝策略：
預剪枝（樹提前停止生長）和後剪枝（完全生成以後減去一些子樹提高預測准確率）
降低錯誤率剪枝：自下而上對每一個內部節點比較減去以其為葉節點和子樹的准確率。如果減去准確率提高，則減去，依次類推知道准確率不在提高。
代價復雜度剪枝：從原始決策樹T0開始生成一個子樹序列{T0、T1、T2、...、Tn},其中Ti+1是從Ti總產生，Tn為根節點。每次均從Ti中 減去具有最小誤差增長率的子樹。然後通過 交叉驗證比較序列中各子樹的效果選擇最優決策樹。

❹ 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劃分的信息增益

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

❺ 決策樹的演算法

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

❻ 常見決策樹分類演算法都有哪些

在機器學習中，有一個體系叫做決策樹，決策樹能夠解決很多問題。在決策樹中，也有很多需要我們去學習的演算法，要知道，在決策樹中，每一個演算法都是實用的演算法，所以了解決策樹中的演算法對我們是有很大的幫助的。在這篇文章中我們就給大家介紹一下關於決策樹分類的演算法，希望能夠幫助大家更好地去理解決策樹。
1.C4.5演算法
C4.5演算法就是基於ID3演算法的改進，這種演算法主要包括的內容就是使用信息增益率替換了信息增益下降度作為屬性選擇的標准；在決策樹構造的同時進行剪枝操作；避免了樹的過度擬合情況；可以對不完整屬性和連續型數據進行處理；使用k交叉驗證降低了計算復雜度；針對數據構成形式，提升了演算法的普適性等內容，這種演算法是一個十分使用的演算法。
2.CLS演算法
CLS演算法就是最原始的決策樹分類演算法，基本流程是，從一棵空數出發，不斷的從決策表選取屬性加入數的生長過程中，直到決策樹可以滿足分類要求為止。CLS演算法存在的主要問題是在新增屬性選取時有很大的隨機性。
3.ID3演算法
ID3演算法就是對CLS演算法的最大改進是摒棄了屬性選擇的隨機性，利用信息熵的下降速度作為屬性選擇的度量。ID3是一種基於信息熵的決策樹分類學習演算法，以信息增益和信息熵，作為對象分類的衡量標准。ID3演算法結構簡單、學習能力強、分類速度快適合大規模數據分類。但同時由於信息增益的不穩定性，容易傾向於眾數屬性導致過度擬合，演算法抗干擾能力差。
3.1.ID3演算法的優缺點
ID3演算法的優點就是方法簡單、計算量小、理論清晰、學習能力較強、比較適用於處理規模較大的學習問題。缺點就是傾向於選擇那些屬性取值比較多的屬性，在實際的應用中往往取值比較多的屬性對分類沒有太大價值、不能對連續屬性進行處理、對雜訊數據比較敏感、需計算每一個屬性的信息增益值、計算代價較高。
3.2.ID3演算法的核心思想
根據樣本子集屬性取值的信息增益值的大小來選擇決策屬性，並根據該屬性的不同取值生成決策樹的分支，再對子集進行遞歸調用該方法，當所有子集的數據都只包含於同一個類別時結束。最後，根據生成的決策樹模型，對新的、未知類別的數據對象進行分類。
在這篇文章中我們給大家介紹了決策樹分類演算法的具體內容，包括有很多種演算法。從中我們不難發現決策樹的演算法都是經過不不斷的改造趨於成熟的。所以說，機器學習的發展在某種程度上就是由於這些演算法的進步而來的。

❼ 用python實現紅酒數據集的ID3,C4.5和CART演算法

ID3演算法介紹
ID3演算法全稱為迭代二叉樹3代演算法（Iterative Dichotomiser 3）
該演算法要先進行特徵選擇，再生成決策樹，其中特徵選擇是基於「信息增益」最大的原則進行的。
但由於決策樹完全基於訓練集生成的，有可能對訓練集過於「依賴」，即產生過擬合現象。因此在生成決策樹後，需要對決策樹進行剪枝。剪枝有兩種形式，分別為前剪枝（Pre-Pruning）和後剪枝（Post-Pruning），一般採用後剪枝。
信息熵、條件熵和信息增益
信息熵：來自於香農定理，表示信息集合所含信息的平均不確定性。信息熵越大，表示不確定性越大，所含的信息量也就越大。
設x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x
1

,x
2

,x
3

,...x
n

為信息集合X的n個取值，則x i x_ix
i

的概率：
P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n
P(X=i)=p
i

,i=1,2,3,...,n

信息集合X的信息熵為：
H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}
H(X)=−
i=1
∑
n

p
i

logp
i

條件熵：指已知某個隨機變數的情況下，信息集合的信息熵。
設信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y
1

,y
2

,y
3

,...y
m

組成的隨機變數集合Y，則隨機變數（X，Y）的聯合概率分布為
P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}
P(x=i,y=j)=p
ij

條件熵：
H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}
H(X∣Y)=
j=1
∑
m

p(y
j

)H(X∣y
j

)
由
H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ⁡ p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}
H(X∣y
j

)=−
j=1
∑
m

p(y
j

)
i=1
∑
n

p(x
i

∣y
j

)logp(x
i

∣y
j

)
和貝葉斯公式：
p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)
p(x
i

y
j

)=p(x
i

∣y
j

)p(y
j

)
可以化簡條件熵的計算公式為:
H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ⁡ p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}
H(X∣Y)=
j=1
∑
m

i=1
∑
n

p(x
i

,y
j

)log
p(x
i

,y
j

)
p(x
i

)

信息增益：信息熵-條件熵，用於衡量在知道已知隨機變數後，信息不確定性減小越大。
d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)
d(X,Y)=H(X)−H(X∣Y)

python代碼實現
import numpy as np
import math

def calShannonEnt(dataSet):
""" 計算信息熵 """
labelCountDict = {}
for d in dataSet:
label = d[-1]
if label not in labelCountDict.keys():
labelCountDict[label] = 1
else:
labelCountDict[label] += 1
entropy = 0.0
for l, c in labelCountDict.items():
p = 1.0 * c / len(dataSet)
entropy -= p * math.log(p, 2)
return entropy

def filterSubDataSet(dataSet, colIndex, value):
"""返回colIndex特徵列label等於value，並且過濾掉改特徵列的數據集"""
subDataSetList = []
for r in dataSet:
if r[colIndex] == value:
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
subDataSetList.append(newR)
return np.array(subDataSetList)

def chooseFeature(dataSet):
""" 通過計算信息增益選擇最合適的特徵"""
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeatureIndex = -1
for i in range(featureNum):
uniqueValues = np.unique(dataSet[:, i])
condition_entropy = 0.0

for v in uniqueValues: #計算條件熵
subDataSet = filterSubDataSet(dataSet, i, v)
p = 1.0 * len(subDataSet) / len(dataSet)
condition_entropy += p * calShannonEnt(subDataSet)
infoGain = entropy - condition_entropy #計算信息增益

if infoGain >= bestInfoGain: #選擇最大信息增益
bestInfoGain = infoGain
bestFeatureIndex = i
return bestFeatureIndex

def creatDecisionTree(dataSet, featNames):
""" 通過訓練集生成決策樹 """
featureName = featNames[:] # 拷貝featNames，此處不能直接用賦值操作，否則新變數會指向舊變數的地址
classList = list(dataSet[:, -1])
if len(set(classList)) == 1: # 只有一個類別
return classList[0]
if dataSet.shape[1] == 1: #當所有特徵屬性都利用完仍然無法判斷樣本屬於哪一類，此時歸為該數據集中數量最多的那一類
return max(set(classList), key=classList.count)

bestFeatureIndex = chooseFeature(dataSet) #選擇特徵
bestFeatureName = featNames[bestFeatureIndex]
del featureName[bestFeatureIndex] #移除已選特徵列
decisionTree = {bestFeatureName: {}}

featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已選特徵列所包含的類別， 通過遞歸生成決策樹
for v in featureValueUnique:
FeatureName = featureName[:]
subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, FeatureName)
return decisionTree

def classify(decisionTree, featnames, featList):
""" 使用訓練所得的決策樹進行分類 """
classLabel = None
root = decisionTree.keys()[0]
firstGenDict = decisionTree[root]
featIndex = featnames.index(root)
for k in firstGenDict.keys():
if featList[featIndex] == k:
if isinstance(firstGenDict[k], dict): #若子節點仍是樹，則遞歸查找
classLabel = classify(firstGenDict[k], featnames, featList)
else:
classLabel = firstGenDict[k]
return classLabel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
下面用鳶尾花數據集對該演算法進行測試。由於ID3演算法只能用於標稱型數據，因此用在對連續型的數值數據上時，還需要對數據進行離散化，離散化的方法稍後說明，此處為了簡化，先使用每一種特徵所有連續性數值的中值作為分界點，小於中值的標記為1，大於中值的標記為0。訓練1000次，統計准確率均值。

from sklearn import datasets
from sklearn.model_selection import train_test_split

iris = datasets.load_iris()
data = np.c_[iris.data, iris.target]

scoreL = []
for i in range(1000): #對該過程進行10000次
trainData, testData = train_test_split(data) #區分測試集和訓練集

featNames = iris.feature_names[:]
for i in range(trainData.shape[1] - 1): #對訓練集每個特徵，以中值為分界點進行離散化
splitPoint = np.mean(trainData[:, i])
featNames[i] = featNames[i]+'<='+'{:.3f}'.format(splitPoint)
trainData[:, i] = [1 if x <= splitPoint else 0 for x in trainData[:, i]]
testData[:, i] = [1 if x <= splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
print 'score: ', np.mean(scoreL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
輸出結果為：score: 0.7335，即准確率有73%。每次訓練和預測的准確率分布如下：

數據離散化
然而，在上例中對特徵值離散化的劃分點實際上過於「野蠻」，此處介紹一種通過信息增益最大的標准來對數據進行離散化。原理很簡單，當信息增益最大時，說明用該點劃分能最大程度降低數據集的不確定性。
具體步驟如下：

對每個特徵所包含的數值型特徵值排序
對相鄰兩個特徵值取均值，這些均值就是待選的劃分點
用每一個待選點把該特徵的特徵值劃分成兩類，小於該特徵點置為1， 大於該特徵點置為0，計算此時的條件熵，並計算出信息增益
選擇信息使信息增益最大的劃分點進行特徵離散化
實現代碼如下：

def filterRawData(dataSet, colIndex, value, tag):
""" 用於把每個特徵的連續值按照區分點分成兩類，加入tag參數，可用於標記篩選的是哪一部分數據"""
filterDataList = []
for r in dataSet:
if (tag and r[colIndex] <= value) or ((not tag) and r[colIndex] > value):
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
filterDataList.append(newR)
return np.array(filterDataList)

def dataDiscretization(dataSet, featName):
""" 對數據每個特徵的數值型特徵值進行離散化 """
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)

for featIndex in range(featureNum): #對於每一個特徵
uniqueValues = sorted(np.unique(dataSet[:, featIndex]))
meanPoint = []

for i in range(len(uniqueValues) - 1): # 求出相鄰兩個值的平均值
meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)
bestInfoGain = 0.0
bestMeanPoint = -1
for mp in meanPoint: #對於每個劃分點
subEntropy = 0.0 #計算該劃分點的信息熵
for tag in range(2): #分別劃分為兩類
subDataSet = filterRawData(dataSet, featIndex, mp, tag)
p = 1.0 * len(subDataSet) / len(dataSet)
subEntropy += p * calShannonEnt(subDataSet)

## 計算信息增益
infoGain = entropy - subEntropy
## 選擇最大信息增益
if infoGain >= bestInfoGain:
bestInfoGain = infoGain
bestMeanPoint = mp
featName[featIndex] = featName[featIndex] + "<=" + "{:.3f}".format(bestMeanPoint)
dataSet[:, featIndex] = [1 if x <= bestMeanPoint else 0 for x in dataSet[:, featIndex]]
return dataSet, featName
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
重新對數據進行離散化，並重復該步驟1000次，同時用sklearn中的DecisionTreeClassifier對相同數據進行分類，分別統計平均准確率。運行代碼如下:

from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
scoreL = []
scoreL_sk = []
for i in range(1000): #對該過程進行1000次
featNames = iris.feature_names[:]
trainData, testData = train_test_split(data) #區分測試集和訓練集
trainData_tmp = .(trainData)
testData_tmp = .(testData)
discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根據信息增益離散化
for i in range(testData.shape[1]-1): #根據測試集的區分點離散化訓練集
splitPoint = float(discritizationFeatName[i].split('<=')[-1])
testData[:, i] = [1 if x<=splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

clf = DecisionTreeClassifier('entropy')
clf.fit(trainData[:, :-1], trainData[:, -1])
clf.predict(testData[:, :-1])
scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))

print 'score: ', np.mean(scoreL)
print 'score-sk: ', np.mean(scoreL_sk)
fig = plt.figure(figsize=(10, 4))
plt.subplot(1,2,1)
pd.Series(scoreL).hist(grid=False, bins=10)
plt.subplot(1,2,2)
pd.Series(scoreL_sk).hist(grid=False, bins=10)
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
兩者准確率分別為：
score: 0.7037894736842105
score-sk: 0.7044736842105263

准確率分布如下：

兩者的結果非常一樣。
（但是。。為什麼根據信息熵離散化得到的准確率比直接用均值離散化的准確率還要低啊？？哇的哭出聲。。）

最後一次決策樹圖形如下：

決策樹剪枝
由於決策樹是完全依照訓練集生成的，有可能會有過擬合現象，因此一般會對生成的決策樹進行剪枝。常用的是通過決策樹損失函數剪枝，決策樹損失函數表示為:
C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|
C
a

(T)=
t=1
∑
T

N
t

H
t

(T)+α∣T∣

其中，H t ( T ) H_t(T)H
t

(T)表示葉子節點t的熵值，T表示決策樹的深度。前項∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑
t=1
T

N
t

H
t

(T)是決策樹的經驗損失函數當隨著T的增加，該節點被不停的劃分的時候，熵值可以達到最小，然而T的增加會使後項的值增大。決策樹損失函數要做的就是在兩者之間進行平衡，使得該值最小。
對於決策樹損失函數的理解，如何理解決策樹的損失函數? - 陶輕松的回答 - 知乎這個回答寫得挺好，可以按照答主的思路理解一下

C4.5演算法
ID3演算法通過信息增益來進行特徵選擇會有一個比較明顯的缺點：即在選擇的過程中該演算法會優先選擇類別較多的屬性（這些屬性的不確定性小，條件熵小，因此信息增益會大），另外，ID3演算法無法解決當每個特徵屬性中每個分類都只有一個樣本的情況（此時每個屬性的條件熵都為0）。
C4.5演算法ID3演算法的改進，它不是依據信息增益進行特徵選擇，而是依據信息增益率，它添加了特徵分裂信息作為懲罰項。定義分裂信息：
S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ⁡ ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}
SplitInfo(X,Y)=−
i
∑
n

∣X∣
∣X
i

∣

log
∣X∣
∣X
i

∣

則信息增益率為：
G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}
GainRatio(X,Y)=
SplitInfo(X,Y)
d(X,Y)

關於ID3和C4.5演算法
在學習分類回歸決策樹演算法時，看了不少的資料和博客。關於這兩個演算法，ID3演算法是最早的分類演算法，這個演算法剛出生的時候其實帶有很多缺陷：

無法處理連續性特徵數據
特徵選取會傾向於分類較多的特徵
沒有解決過擬合的問題
沒有解決缺失值的問題
即該演算法出生時是沒有帶有連續特徵離散化、剪枝等步驟的。C4.5作為ID3的改進版本彌補列ID3演算法不少的缺陷：

通過信息最大增益的標准離散化連續的特徵數據
在選擇特徵是標准從「最大信息增益」改為「最大信息增益率」
通過加入正則項系數對決策樹進行剪枝
對缺失值的處理體現在兩個方面：特徵選擇和生成決策樹。初始條件下對每個樣本的權重置為1。
特徵選擇：在選取最優特徵時，計算出每個特徵的信息增益後，需要乘以一個**「非缺失值樣本權重占總樣本權重的比例」**作為系數來對比每個特徵信息增益的大小
生成決策樹：在生成決策樹時，對於缺失的樣本我們按照一定比例把它歸屬到每個特徵值中，比例為該特徵每一個特徵值占非缺失數據的比重
關於C4.5和CART回歸樹
作為ID3的改進版本，C4.5克服了許多缺陷，但是它自身還是存在不少問題：

C4.5的熵運算中涉及了對數運算，在數據量大的時候效率非常低。
C4.5的剪枝過於簡單
C4.5隻能用於分類運算不能用於回歸
當特徵有多個特徵值是C4.5生成多叉樹會使樹的深度加深
————————————————
版權聲明：本文為CSDN博主「Sarah Huang」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/weixin_44794704/article/details/89406612

❽ 決策樹之ID3演算法及其Python實現

決策樹之ID3演算法及其Python實現

1. 決策樹背景知識
??決策樹是數據挖掘中最重要且最常用的方法之一，主要應用於數據挖掘中的分類和預測。決策樹是知識的一種呈現方式，決策樹中從頂點到每個結點的路徑都是一條分類規則。決策樹演算法最先基於資訊理論發展起來，經過幾十年發展，目前常用的演算法有：ID3、C4.5、CART演算法等。
2. 決策樹一般構建過程
??構建決策樹是一個自頂向下的過程。樹的生長過程是一個不斷把數據進行切分細分的過程，每一次切分都會產生一個數據子集對應的節點。從包含所有數據的根節點開始，根據選取分裂屬性的屬性值把訓練集劃分成不同的數據子集，生成由每個訓練數據子集對應新的非葉子節點。對生成的非葉子節點再重復以上過程，直到滿足特定的終止條件，停止對數據子集劃分，生成數據子集對應的葉子節點，即所需類別。測試集在決策樹構建完成後檢驗其性能。如果性能不達標，我們需要對決策樹演算法進行改善，直到達到預期的性能指標。
??註：分裂屬性的選取是決策樹生產過程中的關鍵，它決定了生成的決策樹的性能、結構。分裂屬性選擇的評判標準是決策樹演算法之間的根本區別。
3. ID3演算法分裂屬性的選擇——信息增益
??屬性的選擇是決策樹演算法中的核心。是對決策樹的結構、性能起到決定性的作用。ID3演算法基於信息增益的分裂屬性選擇。基於信息增益的屬性選擇是指以信息熵的下降速度作為選擇屬性的方法。它以的資訊理論為基礎，選擇具有最高信息增益的屬性作為當前節點的分裂屬性。選擇該屬性作為分裂屬性後，使得分裂後的樣本的信息量最大，不確定性最小，即熵最小。
??信息增益的定義為變化前後熵的差值，而熵的定義為信息的期望值，因此在了解熵和信息增益之前，我們需要了解信息的定義。
??信息：分類標簽xi 在樣本集 S 中出現的頻率記為 p(xi)，則 xi 的信息定義為：?log2p(xi) 。
??分裂之前樣本集的熵：E(S)=?∑Ni=1p(xi)log2p(xi)，其中 N 為分類標簽的個數。
??通過屬性A分裂之後樣本集的熵：EA(S)=?∑mj=1|Sj||S|E(Sj)，其中 m 代表原始樣本集通過屬性A的屬性值劃分為 m 個子樣本集，|Sj| 表示第j個子樣本集中樣本數量，|S| 表示分裂之前數據集中樣本總數量。
??通過屬性A分裂之後樣本集的信息增益：InfoGain(S,A)=E(S)?EA(S)
??註：分裂屬性的選擇標准為：分裂前後信息增益越大越好，即分裂後的熵越小越好。
4. ID3演算法
??ID3演算法是一種基於信息增益屬性選擇的決策樹學習方法。核心思想是：通過計算屬性的信息增益來選擇決策樹各級節點上的分裂屬性，使得在每一個非葉子節點進行測試時，獲得關於被測試樣本最大的類別信息。基本方法是：計算所有的屬性，選擇信息增益最大的屬性分裂產生決策樹節點，基於該屬性的不同屬性值建立各分支，再對各分支的子集遞歸調用該方法建立子節點的分支，直到所有子集僅包括同一類別或沒有可分裂的屬性為止。由此得到一棵決策樹，可用來對新樣本數據進行分類。
ID3演算法流程：
(1) 創建一個初始節點。如果該節點中的樣本都在同一類別，則演算法終止，把該節點標記為葉節點，並用該類別標記。
(2) 否則，依據演算法選取信息增益最大的屬性，該屬性作為該節點的分裂屬性。
(3) 對該分裂屬性中的每一個值，延伸相應的一個分支，並依據屬性值劃分樣本。
(4) 使用同樣的過程，自頂向下的遞歸，直到滿足下面三個條件中的一個時就停止遞歸。
??A、待分裂節點的所有樣本同屬於一類。
??B、訓練樣本集中所有樣本均完成分類。
??C、所有屬性均被作為分裂屬性執行一次。若此時，葉子結點中仍有屬於不同類別的樣本時，選取葉子結點中包含樣本最多的類別，作為該葉子結點的分類。
ID3演算法優缺點分析
優點：構建決策樹的速度比較快，演算法實現簡單，生成的規則容易理解。
缺點：在屬性選擇時，傾向於選擇那些擁有多個屬性值的屬性作為分裂屬性，而這些屬性不一定是最佳分裂屬性；不能處理屬性值連續的屬性；無修剪過程，無法對決策樹進行優化，生成的決策樹可能存在過度擬合的情況。

❾ 決策樹演算法

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

演算法理論：

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

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