姓名：崔升? ? 學號：14020120005
轉(zhuǎn)載自：https://www.cnblogs.com/en-heng/p/5013995.html
【嵌牛導讀】：
C4.5作為一種經(jīng)典的處理大數(shù)據(jù)的算法驳规，是我們在學習互聯(lián)網(wǎng)大數(shù)據(jù)時不得不去了解的一種常用算法
【嵌牛鼻子】：經(jīng)典大數(shù)據(jù)算法之C4.5簡單介紹
【嵌牛提問】：C4.5是一種怎么的算法，其決策機制靠什么實現(xiàn)署海？
【嵌牛正文】：
決策樹模型：
決策樹是一種通過對特征屬性的分類對樣本進行分類的樹形結構吗购，包括有向邊與三類節(jié)點：
根節(jié)點（root node），表示第一個特征屬性砸狞，只有出邊沒有入邊捻勉；
內(nèi)部節(jié)點（internal node），表示特征屬性刀森，有一條入邊至少兩條出邊
葉子節(jié)點（leaf node）踱启，表示類別，只有一條入邊沒有出邊。
上圖給出了（二叉）決策樹的示例埠偿。決策樹具有以下特點：
對于二叉決策樹而言透罢，可以看作是if-then規(guī)則集合，由決策樹的根節(jié)點到葉子節(jié)點對應于一條分類規(guī)則;
分類規(guī)則是互斥并且完備的胚想，所謂互斥即每一條樣本記錄不會同時匹配上兩條分類規(guī)則琐凭，所謂完備即每條樣本記錄都在決策樹中都能匹配上一條規(guī)則芽隆。
分類的本質(zhì)是對特征空間的劃分浊服，如下圖所示，
決策樹學習：
決策樹學習的本質(zhì)是從訓練數(shù)據(jù)集中歸納出一組分類規(guī)則[2]胚吁。但隨著分裂屬性次序的不同牙躺，所得到的決策樹也會不同。如何得到一棵決策樹既對訓練數(shù)據(jù)有較好的擬合腕扶，又對未知數(shù)據(jù)有很好的預測呢孽拷？
首先，我們要解決兩個問題：
如何選擇較優(yōu)的特征屬性進行分裂半抱？每一次特征屬性的分裂脓恕，相當于對訓練數(shù)據(jù)集進行再劃分，對應于一次決策樹的生長窿侈。ID3算法定義了目標函數(shù)來進行特征選擇炼幔。
什么時候應該停止分裂？有兩種自然情況應該停止分裂史简，一是該節(jié)點對應的所有樣本記錄均屬于同一類別乃秀，二是該節(jié)點對應的所有樣本的特征屬性值均相等。但除此之外圆兵，是不是還應該其他情況停止分裂呢跺讯？
2. 決策樹算法
特征選擇
特征選擇指選擇最大化所定義目標函數(shù)的特征。下面給出如下三種特征（Gender, Car Type, Customer ID）分裂的例子：
圖中有兩類類別（C0, C1）殉农，C0: 6是對C0類別的計數(shù)刀脏。直觀上，應選擇Car Type特征進行分裂超凳，因為其類別的分布概率具有更大的傾斜程度愈污，類別不確定程度更小。
為了衡量類別分布概率的傾斜程度聪建，定義決策樹節(jié)點tt的不純度（impurity）钙畔，其滿足：不純度越小，則類別的分布概率越傾斜金麸；下面給出不純度的的三種度量：
其中擎析，p(ck|t)p(ck|t)表示對于決策樹節(jié)點tt類別ckck的概率。這三種不純度的度量是等價的，在等概率分布是達到最大值揍魂。
為了判斷分裂前后節(jié)點不純度的變化情況桨醋，目標函數(shù)定義為信息增益（information gain）：
I(?)I(?)對應于決策樹節(jié)點的不純度，parentparent表示分裂前的父節(jié)點现斋，NN表示父節(jié)點所包含的樣本記錄數(shù)喜最，aiai表示父節(jié)點分裂后的某子節(jié)點，N(ai)N(ai)為其計數(shù)庄蹋，nn為分裂后的子節(jié)點數(shù)瞬内。
特別地，ID3算法選取熵值作為不純度I(?)I(?)的度量限书，則
cc指父節(jié)點對應所有樣本記錄的類別虫蝶；AA表示選擇的特征屬性，即aiai的集合倦西。那么能真，決策樹學習中的信息增益ΔΔ等價于訓練數(shù)據(jù)集中類與特征的互信息，表示由于得知特征AA的信息訓練數(shù)據(jù)集cc不確定性減少的程度扰柠。
在特征分裂后粉铐，有些子節(jié)點的記錄數(shù)可能偏少，以至于影響分類結果卤档。為了解決這個問題蝙泼，CART算法提出了只進行特征的二元分裂，即決策樹是一棵二叉樹裆装；C4.5算法改進分裂目標函數(shù)踱承，用信息增益比（information gain ratio）來選擇特征：
因而，特征選擇的過程等同于計算每個特征的信息增益哨免，選擇最大信息增益的特征進行分裂茎活。此即回答前面所提出的第一個問題（選擇較優(yōu)特征）。ID3算法設定一閾值琢唾，當最大信息增益小于閾值時载荔，認為沒有找到有較優(yōu)分類能力的特征，沒有往下繼續(xù)分裂的必要采桃。根據(jù)最大表決原則懒熙，將最多計數(shù)的類別作為此葉子節(jié)點。即回答前面所提出的第二個問題（停止分裂條件）普办。
決策樹生成：
ID3算法的核心是根據(jù)信息增益最大的準則工扎，遞歸地構造決策樹；算法流程如下：
如果節(jié)點滿足停止分裂條件（所有記錄屬同一類別 or 最大信息增益小于閾值）衔蹲，將其置為葉子節(jié)點肢娘；
選擇信息增益最大的特征進行分裂；
重復步驟1-2，直至分類完成橱健。
C4.5算法流程與ID3相類似而钞，只不過將信息增益改為信息增益比。
3. 決策樹剪枝
過擬合
生成的決策樹對訓練數(shù)據(jù)會有很好的分類效果拘荡，卻可能對未知數(shù)據(jù)的預測不準確臼节，即決策樹模型發(fā)生過擬合（overfitting）——訓練誤差（training error）很小、泛化誤差（generalization error珊皿，亦可看作為test error）較大网缝。下圖給出訓練誤差、測試誤差（test error）隨決策樹節(jié)點數(shù)的變化情況：
可以觀察到亮隙，當節(jié)點數(shù)較小時途凫，訓練誤差與測試誤差均較大垢夹，即發(fā)生了欠擬合（underfitting）溢吻。當節(jié)點數(shù)較大時，訓練誤差較小果元，測試誤差卻很大促王，即發(fā)生了過擬合。只有當節(jié)點數(shù)適中是而晒，訓練誤差居中蝇狼，測試誤差較小倡怎；對訓練數(shù)據(jù)有較好的擬合迅耘，同時對未知數(shù)據(jù)有很好的分類準確率。
發(fā)生過擬合的根本原因是分類模型過于復雜监署，可能的原因如下：
訓練數(shù)據(jù)集中有噪音樣本點颤专，對訓練數(shù)據(jù)擬合的同時也對噪音進行擬合，從而影響了分類的效果钠乏；
決策樹的葉子節(jié)點中缺乏有分類價值的樣本記錄栖秕，也就是說此葉子節(jié)點應被剪掉。
剪枝策略
為了解決過擬合晓避，C4.5通過剪枝以減少模型的復雜度簇捍。[2]中提出一種簡單剪枝策略，通過極小化決策樹的整體損失函數(shù)（loss function）或代價函數(shù)（cost function）來實現(xiàn)俏拱，決策樹TT的損失函數(shù)為：
其中暑塑，C(T)C(T)表示決策樹的訓練誤差，αα為調(diào)節(jié)參數(shù)锅必，|T||T|為模型的復雜度事格。當模型越復雜時，訓練的誤差就越小。上述定義的損失正好做了兩者之間的權衡分蓖。
如果剪枝后損失函數(shù)減少了尔艇，即說明這是有效剪枝。具體剪枝算法可以由動態(tài)規(guī)劃等來實現(xiàn)么鹤。
4. 參考資料
[1] Pang-Ning Tan, Michael Steinbach, Vipin Kumar,Introduction to Data Mining.
[2] 李航终娃，《統(tǒng)計學習方法》.
[3] Naren Ramakrishnan, The Top Ten Algorithms in Data Mining.
