基本介紹
- 中文名：C4.5算法
概述,改進表現,優缺點,算法描述,屬性選擇度量,其它特徵,
概述
C4.5是一系列用在機器學習和數據挖掘的分類問題中的算法。它的目標是監督學習：給定一個數據集，其中的每一個元組都能用一組屬性值來描述，每一個元組屬於一個互斥的類別中的某一類。C4.5的目標是通過學習，找到一個從屬性值到類別的映射關係，並且這個映射能用於對新的類別未知的實體進行分類。
C4.5由J.Ross Quinlan在ID3的基礎上提出的。ID3算法用來構造決策樹。決策樹是一種類似流程圖的樹結構，其中每個內部節點（非樹葉節點）表示在一個屬性上的測試，每個分枝代表一個測試輸出，而每個樹葉節點存放一個類標號。一旦建立好了決策樹，對於一個未給定類標號的元組，跟蹤一條有根節點到葉節點的路徑，該葉節點就存放著該元組的預測。決策樹的優勢在於不需要任何領域知識或參數設定，適合於探測性的知識發現。
從ID3算法中衍生出了C4.5和CART兩種算法，這兩種算法在數據挖掘中都非常重要。
改進表現
用信息增益率來選擇屬性。ID3選擇屬性用的是子樹的信息增益，這裡可以用很多方法來定義信息，ID3使用的是熵（entropy， 熵是一種不純度度量準則），也就是熵的變化值，而C4.5用的是信息增益率。
在決策樹構造過程中進行剪枝，因為某些具有很少元素的結點可能會使構造的決策樹過適應（Overfitting），如果不考慮這些結點可能會更好。
對非離散數據也能處理。
能夠對不完整數據進行處理。
優缺點
C4.5算法優點：產生的分類規則易於理解，準確率較高。
缺點：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致算法的低效。此外，C4.5隻適合於能夠駐留於記憶體的數據集，當訓練集大得無法在記憶體容納時程式無法運行。
算法描述
C4.5並不一個算法，而是一組算法—C4.5，非剪枝C4.5和C4.5規則。下圖中的算法將給出C4.5的基本工作流程：
Input:an attibute-valued dataset D
1:Tree={}
2:if D is "pure"OR other stopping criteria met then
3: terminate
4: end if
5:for all attribute a∈ D do
6: Compute inforation-theoretic criteria if we split on a
7:end for
8:a(best)=Best attribute according to above computed criteria
9: Tree=Create a decision node that tests a(best) in the root
10:D(v)=Induced sub-datasets from D based on a(best)
11:for all D(v) do
12: Tree(v)=C4.5(D(v))
13: Attach Tree(v) to the corresponding branch of Tredd
14:end for
15:return Tree
屬性選擇度量
屬性選擇度量又稱分裂規則，因為它們決定給定節點上的元組如何分裂。屬性選擇度量提供了每個屬性描述給定訓練元組的秩評定，具有最好度量得分的屬性被選作給定元組的分裂屬性。目前比較流行的屬性選擇度量有--信息增益、增益率和Gini指標。
先做一些假設，設D是類標記元組訓練集，類標號屬性具有m個不同值，m個不同類Ci(i=1,2,…，m)，CiD是D中Ci類的元組的集合，|D|和|CiD|分別是D和CiD中的元組個數。
（1）信息增益
信息增益實際上是ID3算法中用來進行屬性選擇度量的。它選擇具有最高信息增益的屬性來作為節點N的分裂屬性。該屬性使結果劃分中的元組分類所需信息量最小。對D中的元組分類所需的期望信息為下式：
Info(D)又稱為熵。
現在假定按照屬性A劃分D中的元組，且屬性A將D劃分成v個不同的類。在該劃分之後，為了得到準確的分類還需要的信息由下面的式子度量：
息增益定義為原來的信息需求（即僅基於類比例）與新需求（即對A劃分之後得到的）之間的差，即
我想很多人看到這個地方都覺得不是很好理解，所以我自己的研究了文獻中關於這一塊的描述，也對比了上面的三個公式，下面說說我自己的理解。
一般說來，對於一個具有多個屬性的元組，用一個屬性就將它們完全分開幾乎不可能，否則的話，決策樹的深度就只能是2了。從這裡可以看出，一旦我們選擇一個屬性A，假設將元組分成了兩個部分A1和A2，由於A1和A2還可以用其它屬性接著再分，所以又引出一個新的問題：接下來我們要選擇哪個屬性來分類？對D中元組分類所需的期望信息是Info(D) ,那么同理，當我們通過A將D劃分成v個子集Dj(j=1,2,…,v)之後，我們要對Dj的元組進行分類，需要的期望信息就是Info(Dj),而一共有v個類，所以對v個集合再分類，需要的信息就是公式（2）了。由此可知，如果公式（2）越小，是不是意味著我們接下來對A分出來的幾個集合再進行分類所需要的信息就越小？而對於給定的訓練集，實際上Info(D)已經固定了，所以選擇信息增益最大的屬性作為分裂點。
但是，使用信息增益的話其實是有一個缺點，那就是它偏向於具有大量值的屬性。什麼意思呢？就是說在訓練集中，某個屬性所取的不同值的個數越多，那么越有可能拿它來作為分裂屬性。例如一個訓練集中有10個元組，對於某一個屬相A，它分別取1-10這十個數，如果對A進行分裂將會分成10個類，那么對於每一個類Info(Dj)=0，從而式（2）為0，該屬性劃分所得到的信息增益（3）最大，但是很顯然，這種劃分沒有意義。
（2）信息增益率
正是基於此，ID3後面的C4.5採用了信息增益率這樣一個概念。信息增益率使用“分裂信息”值將信息增益規範化。分類信息類似於Info(D)，定義如下：
這個值表示通過將訓練數據集D劃分成對應於屬性A測試的v個輸出的v個劃分產生的信息。信息增益率定義：
選擇具有最大增益率的屬性作為分裂屬性。
（3）Gini指標
Gini指標在CART中使用。Gini指標度量數據劃分或訓練元組集D的不純度，定義為：
其它特徵
在決策樹的創建時，由於數據中的噪聲和離群點，許多分枝反映的是訓練數據中的異常。剪枝方法是用來處理這種過分擬合數據的問題。通常剪枝方法都是使用統計度量，剪去最不可靠的分枝。
剪枝一般分兩種方法：先剪枝和後剪枝。
先剪枝方法中通過提前停止樹的構造（比如決定在某個節點不再分裂或劃分訓練元組的子集）而對樹剪枝。一旦停止，這個節點就變成樹葉，該樹葉可能取它持有的子集最頻繁的類作為自己的類。先剪枝有很多方法，比如（1）當決策樹達到一定的高度就停止決策樹的生長；（2）到達此節點的實例具有相同的特徵向量，而不必一定屬於同一類，也可以停止生長（3）到達此節點的實例個數小於某個閾值的時候也可以停止樹的生長，不足之處是不能處理那些數據量比較小的特殊情況（4）計算每次擴展對系統性能的增益，如果小於某個閾值就可以讓它停止生長。先剪枝有個缺點就是視野效果問題，也就是說在相同的標準下，也許當前擴展不能滿足要求，但更進一步擴展又能滿足要求。這樣會過早停止決策樹的生長。
另一種更常用的方法是後剪枝，它由完全成長的樹剪去子樹而形成。通過刪除節點的分枝並用樹葉來替換它。樹葉一般用子樹中最頻繁的類別來標記。
