一.C4.5算法的簡(jiǎn)介：

C4.5并不是單單一個(gè)算法而是一套算法，主要用于對(duì)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中的分類問題。它是一種有監(jiān)督的學(xué)習(xí)，也就是說(shuō)對(duì)于該算法我們需要先給它們提供一個(gè)數(shù)據(jù)集，這個(gè)數(shù)據(jù)集包含多個(gè)實(shí)例，每個(gè)實(shí)例都包含多個(gè)屬性，該實(shí)例用這些屬性描述，根據(jù)屬性取值的不同被劃分到不同的互斥類中。

C4.5算法就是從提供的數(shù)據(jù)集中學(xué)習(xí)到如何將不同屬性值的實(shí)例劃分到不同類的映射，當(dāng)我們提供一套全新的屬性值的時(shí)候，它能夠通過(guò)學(xué)到的映射對(duì)新的屬性進(jìn)行分類。

C4.5是決策樹算法的一種。決策樹算法作為一種分類算法，目標(biāo)就是將具有p維特征的n個(gè)樣本分到c個(gè)類別中去。相當(dāng)于做一個(gè)投影，c=f(n)，將樣本經(jīng)過(guò)一種變換賦予一種類別標(biāo)簽。決策樹為了達(dá)到這一目的，可以把分類的過(guò)程表示成一棵樹，每次通過(guò)選擇一個(gè)特征pi來(lái)進(jìn)行分叉。

那么怎樣選擇分叉的特征呢？每一次分叉選擇哪個(gè)特征對(duì)樣本進(jìn)行劃分可以最快最準(zhǔn)確的對(duì)樣本分類呢？不同的決策樹算法有著不同的特征選擇方案。ID3用信息增益，C4.5用信息增益率，CART用gini系數(shù)。

下面主要針對(duì)C4.5算法，我們用一個(gè)例子來(lái)計(jì)算一下。

二.C4.5算法原理：

C4.5算法是一種經(jīng)典的決策樹學(xué)習(xí)算法，它是ID3算法的一種改進(jìn)和優(yōu)化。與ID3算法相比，C4.5算法具有以下幾個(gè)改進(jìn)：

1. 用信息增益率代替信息增益作為選擇劃分屬性的標(biāo)準(zhǔn)，解決了信息增益容易偏向取值比較多的屬性的問題。

2. 能夠處理連續(xù)型屬性數(shù)據(jù)，不需要對(duì)連續(xù)型屬性進(jìn)行離散化處理。

3. 能夠處理缺失屬性值，利用缺失屬性值的樣本進(jìn)行決策樹的訓(xùn)練。

C4.5算法的基本思想是將數(shù)據(jù)集遞歸地劃分為小的子集，直到子集中樣本的所有特征屬性均相同或無(wú)法繼續(xù)劃分為止。得到的決策樹就是基于訓(xùn)練集構(gòu)建的分類模型。

C4.5算法的具體步驟如下：

1. 選擇當(dāng)前節(jié)點(diǎn)的最優(yōu)劃分屬性，即使得信息增益率最大的屬性，如果不存在則該節(jié)點(diǎn)為葉子節(jié)點(diǎn)。

2. 對(duì)選擇的最優(yōu)屬性的每個(gè)取值，分別構(gòu)建一個(gè)子節(jié)點(diǎn)，并將樣本點(diǎn)分配到這些子節(jié)點(diǎn)中。

3. 對(duì)每個(gè)子節(jié)點(diǎn)，遞歸地執(zhí)行步驟1-2，直至滿足終止條件，即到達(dá)葉子節(jié)點(diǎn)或無(wú)法繼續(xù)劃分。

4. 構(gòu)建好決策樹，用它進(jìn)行測(cè)試數(shù)據(jù)的分類預(yù)測(cè)。

C4.5算法在構(gòu)建決策樹時(shí)，采用了自上而下遞歸的方法，每次選擇最優(yōu)劃分屬性進(jìn)行劃分，并在該屬性的每個(gè)取值上遞歸地劃分?jǐn)?shù)據(jù)集。這樣，就能得到一個(gè)覆蓋了訓(xùn)練集所有樣本的決策樹模型，并可用來(lái)對(duì)新的測(cè)試樣本進(jìn)行分類預(yù)測(cè)。

三.C4.5案例分析：

例如，如圖1，這組訓(xùn)練數(shù)據(jù)，屬性值包括是否有房，婚姻狀況，年收入，所有的實(shí)例被劃分為兩類，也就是 是否是拖欠貸款者。我們的目的就是從訓(xùn)練數(shù)據(jù)中學(xué)到一個(gè)映射，這個(gè)映射可以用于對(duì)于在圖中未出現(xiàn)的實(shí)例屬性取值情況進(jìn)行有效分類。

也就是說(shuō)，假如有一個(gè)有房、單身、年收入為50X的人（圖中未出現(xiàn)），推測(cè)出這個(gè)人是否是拖欠貸款者

?Figure 1

3.1決策樹構(gòu)建：

a.將所有訓(xùn)練數(shù)據(jù)集放在根節(jié)點(diǎn)上；

b.遍歷每種屬性的每種分割方式，找到最好的分割點(diǎn)；

c.根據(jù)2中找出的最好分割點(diǎn)將根節(jié)點(diǎn)分割成多個(gè)子節(jié)點(diǎn)（>=2）；

d.對(duì)剩下的樣本和屬性重復(fù)執(zhí)行步驟2/3，直到每個(gè)節(jié)點(diǎn)中的數(shù)據(jù)都屬于同一類為止。

C4.5算法是采用信息增益率來(lái)進(jìn)行節(jié)點(diǎn)的分裂

注意：C4.5算法并不直接選擇增益率最大的候選劃分屬性，而是使用了一個(gè)啟發(fā)式：

先從候選劃分屬性中找出信息增益高于平均水平的屬性，再?gòu)闹羞x擇增益率最高的。

3.2信息增益率：

增益率是用前面的信息增益Gain(D, a)和屬性a對(duì)應(yīng)的"固有值"(intrinsic value)的比值來(lái)共同定義的。屬性 a 的可能取值數(shù)目越多(即 V 越大)，則 IV(a) 的值通常會(huì)越大。

3.3計(jì)算

根據(jù)是否有房、婚姻狀況、年收入三個(gè)屬性來(lái)判斷類別標(biāo)簽拖欠貸款者（是、否）

對(duì)于離散屬性的處理：（有無(wú)房、婚姻狀況）

a.計(jì)算類別信息熵

????????類別信息熵表示的是所有樣本中各種類別出現(xiàn)的不確定性之和。根據(jù)熵的概念，熵越大，不確定性就越大，把事情搞清楚所需要的信息量就越多。

總體信息熵樣本10個(gè)，是拖欠貸款者有3個(gè)，不是拖欠貸款者有7個(gè)。

b.計(jì)算每個(gè)屬性的信息熵

每個(gè)屬性的信息熵相當(dāng)于一種條件熵。他表示的是在某種屬性的條件下，各種類別出現(xiàn)的不確定性之和。屬性的信息熵越大，表示這個(gè)屬性中擁有的樣本類別越不“純”

c.計(jì)算信息增益

? ? ? ? 信息增益的 = 熵 - 條件熵，在這里就是 類別信息熵 - 屬性信息熵，它表示的是信息不確定性減少的程度。如果一個(gè)屬性的信息增益越大，就表示用這個(gè)屬性進(jìn)行樣本劃分可以更好的減少劃分后樣本的不確定性，當(dāng)然，選擇該屬性就可以更快更好地完成我們的分類目標(biāo)。
?

d.計(jì)算屬性分裂信息度量
? ? ? ? 用分裂信息度量來(lái)考慮某種屬性進(jìn)行分裂時(shí)分支的數(shù)量信息和尺寸信息，我們把這些信息稱為屬性的內(nèi)在信息（instrisic information）。信息增益率用信息增益/內(nèi)在信息，會(huì)導(dǎo)致屬性的重要性隨著內(nèi)在信息的增大而減?。ㄒ簿褪钦f(shuō)，如果這個(gè)屬性本身不確定性就很大，那我就越不傾向于選取它），這樣算是對(duì)單純用信息增益有所補(bǔ)償。
?

e.計(jì)算信息增益率

? ? 從屬性中找出信息增益高于平均水平的屬性，再?gòu)闹羞x擇增益率最高的作為分割點(diǎn)

對(duì)于連續(xù)性屬性的處理：（年收入）

a.對(duì)年收入屬性的各個(gè)值進(jìn)行升序排序

b.選取分裂節(jié)點(diǎn)，對(duì)于連續(xù)性屬性，它的分裂節(jié)點(diǎn)是任意相鄰兩個(gè)取值的中點(diǎn)，最后得到所有分裂點(diǎn)的信息熵，選擇信息熵最小，即信息增益最大 的作為分裂點(diǎn)。

注意：這里用信息增益最大而不是信息增益率最大

最終得到所有屬性的信息增益率，選取信息增益率最大的屬性作為分裂屬性，

若分裂之后，發(fā)現(xiàn)子結(jié)點(diǎn)都是“純”的，因此子節(jié)點(diǎn)均為葉子節(jié)點(diǎn)，

選擇“不純“的結(jié)點(diǎn)繼續(xù)分裂 重復(fù)以上步驟

下面解釋一下子結(jié)點(diǎn)是“純”的意思

子節(jié)點(diǎn)是純的情況指的是一個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)都只包含同一類別的樣本，此時(shí)就無(wú)需再進(jìn)行劃分而可以直接將該節(jié)點(diǎn)作為葉節(jié)點(diǎn)。

以C4.5算法生成決策樹過(guò)程中包含連續(xù)數(shù)值屬性的處理為例，假設(shè)我們的數(shù)據(jù)集中有以下數(shù)據(jù)：

首先，我們需要將連續(xù)的數(shù)值屬性轉(zhuǎn)化為離散值?？梢赃x擇根據(jù)某個(gè)閾值來(lái)將其二元化，例如將年齡屬性以 30 為閾值，將年收入屬性以 high、medium 和 low 三個(gè)值進(jìn)行離散化。 轉(zhuǎn)換后的數(shù)據(jù)如下所示：

接下來(lái)，我們需要找到最佳屬性進(jìn)行劃分。C4.5算法采用信息增益率作為劃分屬性的選擇標(biāo)準(zhǔn)。在劃分屬性時(shí)，假設(shè)我們選擇了年齡age屬性作為劃分屬性，然后將它二元化為<=30和>30兩個(gè)離散值。根據(jù)年齡屬性劃分的子節(jié)點(diǎn)數(shù)據(jù)如下：

• 子節(jié)點(diǎn) 1，年齡 <= 30：樣本 2 個(gè)，均屬于同一類別（不購(gòu)買電腦），該子節(jié)點(diǎn)為純節(jié)點(diǎn)。
• 子節(jié)點(diǎn) 2，年齡 > 30：樣本 3 個(gè)，其中有 2 個(gè)屬于同一類別（購(gòu)買電腦），該子節(jié)點(diǎn)非純。

顯然，第一個(gè)子節(jié)點(diǎn)已經(jīng)是一個(gè)純節(jié)點(diǎn)，不需要再繼續(xù)劃分；而對(duì)于第二個(gè)子節(jié)點(diǎn)，我們需要對(duì)其進(jìn)行進(jìn)一步劃分。

本題具體步驟如下（忽略潦草的字體）：

?

?

?

?

?接下來(lái)對(duì)于年收入<=97.5的樣本計(jì)算

?

?所以對(duì)于<=97.5的結(jié)點(diǎn)接下一步以婚姻狀況作為葉子結(jié)點(diǎn)繼續(xù)分裂，后面同理直到發(fā)現(xiàn)子結(jié)點(diǎn)都是純的

四.python代碼

import pandas as pd
import numpy as np
from math import log2

# 讀入數(shù)據(jù)集
data = {'have_house': ['yes', 'no', 'no', 'yes', 'no', 'no', 'yes', 'no', 'no', 'no'],
        'marital_status': ['single', 'married', 'single', 'married', 'divorced', 'married', 'divorced', 'single', 'married', 'single'],
        'annual_income': [125, 100, 70, 120, 95, 60, 220, 85, 75, 90],
        'late_payment': ['no', 'no', 'no', 'no', 'yes', 'no', 'no', 'yes', 'no', 'yes']}
df = pd.DataFrame(data)

# 將文本屬性轉(zhuǎn)為數(shù)值屬性
df['have_house'] = df['have_house'].apply(lambda x: 1 if x == 'yes' else 0)            # 如果有房產(chǎn)，轉(zhuǎn)換為1，否則轉(zhuǎn)換為0
df['marital_status'] = df['marital_status'].map({'single': 0, 'married': 1, 'divorced': 2})  # 將婚姻狀況轉(zhuǎn)換為0-2的數(shù)字，表示單身、已婚和離異
df['late_payment'] = df['late_payment'].apply(lambda x: 1 if x == 'yes' else 0)       # 如果拖欠貸款，轉(zhuǎn)換為1，否則轉(zhuǎn)換為0

# 定義C4.5算法所需的函數(shù)
def calc_entropy(data):
    """計(jì)算信息熵"""
    counts = data.value_counts()  # 統(tǒng)計(jì)各類別樣本的數(shù)量
    probs = counts / len(data)    # 計(jì)算各類別樣本的概率
    entropy = -sum(probs * np.log2(probs))  # 根據(jù)公式計(jì)算信息熵
    return entropy

def calc_conditional_entropy(data, feature, threshold):
    """計(jì)算條件熵"""
    low_subset = data[data[feature] < threshold]['late_payment']  # 獲取年收入小于閾值的目標(biāo)變量列
    high_subset = data[data[feature] >= threshold]['late_payment']  # 獲取年收入大于等于閾值的目標(biāo)變量列
    prob_low = len(low_subset) / len(data)   # 計(jì)算前一部分的出現(xiàn)概率
    prob_high = len(high_subset) / len(data)  # 計(jì)算后一部分的出現(xiàn)概率
    entropy = prob_low * calc_entropy(low_subset) + prob_high * calc_entropy(high_subset)  # 計(jì)算條件熵
    return entropy

def calc_information_gain(data, feature):
    """計(jì)算信息增益"""
    base_entropy = calc_entropy(data['late_payment'])                # 計(jì)算全局信息熵
    sorted_values = sorted(data[feature].unique())                   # 對(duì)連續(xù)屬性的取值進(jìn)行排序
    thresholds = [(sorted_values[i] + sorted_values[i+1]) / 2 for i in range(len(sorted_values)-1)]  # 計(jì)算各個(gè)分割點(diǎn)的閾值
    info_gains = []
    for threshold in thresholds:
        cond_entropy = calc_conditional_entropy(data, feature, threshold)
        info_gain = base_entropy - cond_entropy
        info_gains.append(info_gain)
    best_threshold_index = np.argmax(info_gains)   # 找到信息增益最大的分割點(diǎn)
    best_threshold = thresholds[best_threshold_index]  # 找到對(duì)應(yīng)的閾值
    return info_gains[best_threshold_index], best_threshold

def select_best_feature(data, features):
    """選擇最佳特征"""
    info_gains = [calc_information_gain(data, feature) for feature in features]   # 計(jì)算每個(gè)特征的信息增益和最佳分割點(diǎn)
    best_feature_index = np.argmax([gain for gain, threshold in info_gains])     # 找到信息增益最大的特征
    best_feature = features[best_feature_index]                                 # 找到對(duì)應(yīng)的屬性名
    best_threshold = info_gains[best_feature_index][1]                          # 找到對(duì)應(yīng)的最佳分割點(diǎn)
    return best_feature, best_threshold

def create_tree(data, features):
    """創(chuàng)建決策樹"""
    target = data['late_payment']
    # 如果所有樣本都屬于同一類別，則停止劃分，返回該類別
    if len(target.unique()) == 1:
        return target.iloc[0]
    # 如果沒有屬性可用于劃分，則停止劃分，返回樣本數(shù)最多的類別
    if len(features) == 0:
        return target.value_counts().idxmax()
    # 選擇最佳特征進(jìn)行劃分
    best_feature, best_threshold = select_best_feature(data, features)
    tree = {best_feature: {}}
    low_subset = data[data[best_feature] < best_threshold].drop(columns=best_feature)
    high_subset = data[data[best_feature] >= best_threshold].drop(columns=best_feature)
    sub_features = [f for f in features if f != best_feature]
    if len(low_subset) > 0:
        low_subtree = create_tree(low_subset, sub_features)
        tree[best_feature]['<{}'.format(best_threshold)] = low_subtree
    if len(high_subset) > 0:
        high_subtree = create_tree(high_subset, sub_features)
        tree[best_feature]['>={}'.format(best_threshold)] = high_subtree
    return tree

# 構(gòu)建決策樹模型
features = ['have_house', 'marital_status', 'annual_income']  # 特征集合
tree = create_tree(df, features)
print(tree)

輸出結(jié)果為：

{'annual_income': {'<97.5': {'marital_status': {0: 1, 1: {'have_house': {0: 0, 1: 1}}, 2: 1}}, '>=97.5': {'have_house': {0: 1, 1: 0}}}}

{'annual_income': {'<97.5': {'marital_status': {0: 1, 1: {'have_house': {0: 0, 1: 1}}, 2: 1}}, '>=97.5': {'have_house': {0: 1, 1: 0}}}}

五.優(yōu)點(diǎn)與改進(jìn)
? ? ? ? C4.5算法是用于生成決策樹的一種經(jīng)典算法，是ID3算法的一種延伸和優(yōu)化。C4.5算法對(duì)ID3算法主要做了一下幾點(diǎn)改進(jìn)：

? ? ? ? （1）通過(guò)信息增益率選擇分裂屬性，克服了ID3算法中通過(guò)信息增益傾向于選擇擁有多個(gè)屬性值的屬性作為分裂屬性的不足；

? ? ? ? （2）能夠處理離散型和連續(xù)型的屬性類型，即將連續(xù)型的屬性進(jìn)行離散化處理；

? ? ? ? （3）構(gòu)造決策樹之后進(jìn)行剪枝操作；

? ? ? ? （4）能夠處理具有缺失屬性值的訓(xùn)練數(shù)據(jù)。 C4.5算法訓(xùn)練的結(jié)果是一個(gè)分類模型，這個(gè)分類模型可以理解為一個(gè)決策樹，分裂屬性就是一個(gè)樹節(jié)點(diǎn)，分類結(jié)果是樹的結(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都有左子樹和右子樹，結(jié)點(diǎn)無(wú)左右子樹。

? ? ? ? （5）C4.5采用二分法處理連續(xù)特征，將連續(xù)特征進(jìn)行排列，將連續(xù)兩個(gè)值的中間值作為分裂節(jié)點(diǎn)，將小于該值和大于該值的樣本分為兩個(gè)類別，找到信息增益最大的分裂點(diǎn)，本質(zhì)上還是用的離散特征。需注意的是，與離散屬性不同，若當(dāng)前節(jié)點(diǎn)劃分屬性為連續(xù)屬性，該屬性還可作為其后代節(jié)點(diǎn)的劃分屬性。

? ? ? ? （6）在屬性值缺失的情況下劃分屬性，將數(shù)據(jù)集分成兩部分：沒有缺失值的部分、有缺失值的部分。對(duì)每個(gè)樣本設(shè)置一個(gè)權(quán)重，將沒有缺失值的部分按照占據(jù)總樣本的比例計(jì)算信息增益率，并乘上所占比例。

? ? ? ? （7）給定劃分屬性，若樣本在該屬性上缺失時(shí)，若樣本x在劃分屬性a上的取值未知，則將x同時(shí)劃入所有子節(jié)點(diǎn)，且樣本權(quán)值按所占比例和樣本權(quán)值進(jìn)行調(diào)整。直觀地看，這就是讓同一個(gè)樣本以不同的概率劃入到不同的子節(jié)點(diǎn)中。

缺點(diǎn)
信息增益率采用熵的計(jì)算，里面有大量耗時(shí)的對(duì)數(shù)計(jì)算。
多叉樹的計(jì)算效率不如二叉樹高。
決策樹模型容易過(guò)擬合，所以應(yīng)該引入剪枝策略進(jìn)行處理。

六參考文獻(xiàn)：

[1] Quinlan, J.R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers. ISBN 1-55860-238-0.

[2] 周志華. 機(jī)器學(xué)習(xí). 北京：清華大學(xué)出版社，2016.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-478108.html

到了這里，關(guān)于機(jī)器學(xué)習(xí) C4.5算法原理 + 決策樹分裂詳解（離散屬性+連續(xù)屬性） 附python代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！