机器学习系列（六）：决策树（附Python实现西瓜书决策树代码）

• 决策树
• • 一、ID3决策树
  • • 1.1 信息熵
    • 1.2 信息增益
    • 1.3 数据集
    • 1.3 ID3决策树代码实现
  • 二、C4.5决策树
  • • 2.1 增益率
    • 2.2 C4.5决策树基础代码实现
  • 三、CART决策树
  • 四、剪枝

根据划分方法不同可以分为ID3、CART、C4.5三种决策树

决策树算法的关键在于如何选择最优划分属性。一般而言，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即其纯度越高越好。

通常，使用信息熵（information entropy）来作为度量样本纯度的标准，计算公式为：
E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k l o g 2 p k Ent(D) = -displaystylesum_{k=1}^{|y|}p_klog_2p_k Ent(D)=−k=1∑∣y∣​pk​log2​pk​
其中 ∣ y ∣ |y| ∣y∣表示有几类， p k p_k pk​表示第 k k k类样本的占比

信息熵值越小，纯度则越高

举个例子：对于二分类，假设现在划分节点使得样本分类各占一半，则根据上述公式，信息熵为 E n t = − 0.5 ∗ l o g 2 ( 0.5 ) ∗ 2 = 1.00 Ent = -0.5*log_2(0.5)*2 = 1.00 Ent=−0.5∗log2​(0.5)∗2=1.00

而当划分节点使得样本按照91开分为2类时，根据上述公式，信息熵为 E n t = − 0.1 ∗ l o g 2 ( 0.1 ) ∗ − 0.9 ∗ l o g 2 ( 0.9 ) = 0.469 Ent = -0.1*log_2(0.1)*-0.9*log_2(0.9) = 0.469 Ent=−0.1∗log2​(0.1)∗−0.9∗log2​(0.9)=0.469

根据我们的定义， E n t Ent Ent的值越小纯度越高，即当划分数据越倾向一类越好，当数据均分时纯度较低。

对于某一个属性 a a a而言，它有 V V V个可能的取值 { a 1 , a 2 , . . . , a V } {a^1,a^2,...,a^V} {a1,a2,...,aV}，如果使用这个属性对数据进行划分，则会产生 V V V个节点，其中第 v v v个节点包含了原始数据集中所有在属性 a a a上取值为 v v v的样本（包括所有类别），记为 D v D^v Dv。我们可以先计算按照属性值 v v v划分的信息熵，然后根据样本数量的不同给与不同的权重 ∣ D v ∣ / ∣ D ∣ |D^v|/|D| ∣Dv∣/∣D∣，可计算出属性 a a a对样本集 D D D进行划分所获得的“信息增益”，用公式表述为：
G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a) = Ent(D)-displaystylesum_{v=1}^Vfrac{|D^v|}{|D|}Ent(D^v) Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)
其中 ∣ ⋅ ∣ |·| ∣⋅∣表示样本数量

很显然，这个公式表示使用属性 a a a划分之后信息熵下降了多少，即纯度提升了多少。因此，我们可以使用信息增益作为决策树的划分属性选择。而ID3决策树就是以信息增益为准则来划分属性的。

使用数据集：周志华《机器学习》 第76页表4.1 西瓜数据集2.0，已经使用pandas处理为csv格式，请自取：

西瓜数据集（csv格式）：百度网盘 提取码：dy4c

根据决策树算法，可知I3D决策树的算法流程如下：

1. 先根据最大信息增益选取一个特征作为根节点
2. 以根节点特征的取值作为分支递归生成节点，在递归中注意：
   • 每次取特征值时需要删除之前取过的数据
   • 当当前样本只有一类时，返回该类别作叶子结点，即分类结果
   • 当当前所有样本的特征值都一样时，选样本最多的类作为叶子结点
3. 使用测试特征测试决策树预测能力

以下为python代码实现：

import pandas as pd
import numpy as np

#计算信息熵
def cal_information_entropy(data):
    data_label = data.iloc[:,-1]
    label_class =data_label.value_counts() #总共有多少类
    Ent = 0
    for k in label_class.keys():
        p_k = label_class[k]/len(data_label)
        Ent += -p_k*np.log2(p_k)
    return Ent

#计算给定数据属性a的信息增益
def cal_information_gain(data, a):
    Ent = cal_information_entropy(data)
    feature_class = data[a].value_counts() #特征有多少种可能
    gain = 0
    for v in feature_class.keys():
        weight = feature_class[v]/data.shape[0]
        Ent_v = cal_information_entropy(data.loc[data[a] == v])
        gain += weight*Ent_v
    return Ent - gain

#获取标签最多的那一类
def get_most_label(data):
    data_label = data.iloc[:,-1]
    label_sort = data_label.value_counts(sort=True)
    return label_sort.keys()[0]

#挑选最优特征，即信息增益最大的特征
def get_best_feature(data):
    features = data.columns[:-1]
    res = {}
    for a in features:
        temp = cal_information_gain(data, a)
        res[a] = temp
    res = sorted(res.items(),key=lambda x:x[1],reverse=True)
    return res[0][0]

##将数据转化为（属性值：数据）的元组形式返回，并删除之前的特征列
def drop_exist_feature(data, best_feature):
    attr = pd.unique(data[best_feature])
    new_data = [(nd, data[data[best_feature] == nd]) for nd in attr]
    new_data = [(n[0], n[1].drop([best_feature], axis=1)) for n in new_data]
    return new_data

#创建决策树
def create_tree(data):
    data_label = data.iloc[:,-1]
    if len(data_label.value_counts()) == 1: #只有一类
        return data_label.values[0]
    if all(len(data[i].value_counts()) == 1 for i in data.iloc[:,:-1].columns): #所有数据的特征值一样，选样本最多的类作为分类结果
        return get_most_label(data)
    best_feature = get_best_feature(data) #根据信息增益得到的最优划分特征
    Tree = {best_feature:{}} #用字典形式存储决策树

    for item in drop_exist_feature(data,best_feature): #根据特征值的不同递归创建决策树
        Tree[best_feature][item[0]] = create_tree(item[1])
    return Tree

#预测，在编程中，以字典的形式存储决策树，当往下递归时，结果是字典则表示还可以往下寻找结果，当不是字典表示以找到叶子结点，即分类结果
def predict(Tree , test_data):
    first_feature = list(Tree.keys())[0]
    second_dict = Tree[first_feature]
    input_first = test_data.get(first_feature)
    input_value = second_dict[input_first]
    if isinstance(input_value , dict): #判断分支还是不是字典
        class_label = predict(input_value, test_data)
    else:
        class_label = input_value
    return class_label

if __name__ == '__main__':
    #读取数据
    data = pd.read_csv('data_word.csv')
    
    #创建决策树
    dicision_Tree = create_tree(data)
    
    #测试数据
    test_data_1 = {'色泽':'青绿','根蒂':'蜷缩','敲声':'浊响','纹理':'稍糊','脐部':'凹陷','触感':'硬滑'}
    test_data_2 = {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑'}
    result = predict(dicision_Tree,test_data_2)
    print('分类结果为'+'好瓜'if result == 1 else '坏瓜')

最后得到的决策树模型，以字典形式存储：

{'纹理': {'清晰': {'根蒂': {'蜷缩': 1, '稍蜷': {'色泽': {'青绿': 1, '乌黑': {'触感': {'硬滑': 1, '软粘': 0}}}}, '硬挺': 0}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}

随后使用测试数据进行预测：

test_data_1 = {'色泽': '青绿','根蒂' : '蜷缩','敲声' :'浊响','纹理':'稍糊','脐部':'凹陷','触感':'硬滑'}
test_data_2 = {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑'}

预测结果分别为：坏瓜、好瓜

信息增益的缺点在于对取值数目较多的属性有所偏好，举个例子：

如果把上述数据集中的编号作为一组特征，在最开始划分根节点的时候进行计算信息增益会得到如下结果：

可以看到序号作为特征信息增益远超过其他特征，因为它有17中可能的取值，每一种取值只有一个样本，即纯度达到最大（计算一下便可得信息熵为0），特征的信息增益直接等于原始数据的信息熵 E n t （ D ） Ent（D） Ent（D）达到最大。

很显然，这样的偏好是及其不合理的，“序号”这样的特征根本不能作为分类依据，为了减少这种偏好带来的负面影响，C4.5决策树算法不直接使用信息增益，而是使用增益率(gain ratio)来选择最优划分属性，用公式表述为：
G a i n _ r a t i o n ( D , a ) = G a i n ( D , a ) I V ( a ) Gain_ration(D,a) = frac{Gain(D,a)}{IV(a)} Gain_ration(D,a)=IV(a)Gain(D,a)​
其中， G a i n ( D , a ) Gain(D,a) Gain(D,a)同上文中的信息增益，而
I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ IV(a) = -displaystylesum_{v=1}^Vfrac{|D^v|}{|D|}log_2frac{|D^v|}{|D|} IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​
被称为特征 a a a的固有值(intrinsic value)，属性 a a a的取值越多，则 I V ( a ) IV(a) IV(a)越大，则 G a i n _ r a t i o n Gain_ration Gain_ration越小，举例：

a a a有两个取值且各占一半时， I V ( a ) = 1 IV(a) = 1 IV(a)=1， a a a有四个取值且各占四分之一时， I V ( a ) = 2 IV(a) = 2 IV(a)=2

注意，显然增益率会对可取值数目较小的特征有偏好，为了避免这个问题，C4.5并不是直接使用增益率的大小进行划分特征，而是先从候选划分特征中找出信息增益高于平均水平的属性，再从中选择增益率最高的那个特征。

在使用信息率后，上述表格变为：

在信息增益排序中，仅“序号”和“纹理”两个特征高于平均水平，随后比较两者的增益率，“纹理”的增益率高于“序号”，则在遇到“序号”这种离谱的特征时，增益率算法还是能一定程度地选择正确的特征

基本上和ID3一样，只是特征选取部分需要修改

注意我们这里是基础实现，尚未涉及到剪枝，数据集同上

import pandas as pd
import numpy as np

#计算信息熵
def cal_information_entropy(data):
    data_label = data.iloc[:,-1]
    label_class =data_label.value_counts() #总共有多少类
    Ent = 0
    for k in label_class.keys():
        p_k = label_class[k]/len(data_label)
        Ent += -p_k*np.log2(p_k)
    return Ent

#计算给定数据属性a的信息增益
def cal_information_gain(data, a):
    Ent = cal_information_entropy(data)
    feature_class = data[a].value_counts() #特征有多少种可能
    gain = 0
    for v in feature_class.keys():
        weight = feature_class[v]/data.shape[0]
        Ent_v = cal_information_entropy(data.loc[data[a] == v])
        gain += weight*Ent_v
    return Ent - gain

def cal_gain_ratio(data , a):
    #先计算固有值intrinsic_value
    IV_a = 0
    feature_class = data[a].value_counts()  # 特征有多少种可能
    for v in feature_class.keys():
        weight = feature_class[v]/data.shape[0]
        IV_a += -weight*np.log2(weight)
    gain_ration = cal_information_gain(data,a)/IV_a
    return gain_ration

#获取标签最多的那一类
def get_most_label(data):
    data_label = data.iloc[:,-1]
    label_sort = data_label.value_counts(sort=True)
    return label_sort.keys()[0]

#挑选最优特征，即在信息增益大于平均水平的特征中选取增益率最高的特征
def get_best_feature(data):
    features = data.columns[:-1]
    res = {}
    for a in features:
        temp = cal_information_gain(data, a)
        gain_ration = cal_gain_ratio(data,a)
        res[a] = (temp,gain_ration)
    res = sorted(res.items(),key=lambda x:x[1][0],reverse=True) #按信息增益排名
    res_avg = sum([x[1][0] for x in res])/len(res) #信息增益平均水平
    good_res = [x for x in res if x[1][0] >= res_avg] #选取信息增益高于平均水平的特征
    result =sorted(good_res,key=lambda x:x[1][1],reverse=True) #将信息增益高的特征按照增益率进行排名
    return result[0][0] #返回高信息增益中增益率最大的特征

##将数据转化为（属性值：数据）的元组形式返回，并删除之前的特征列
def drop_exist_feature(data, best_feature):
    attr = pd.unique(data[best_feature])
    new_data = [(nd, data[data[best_feature] == nd]) for nd in attr]
    new_data = [(n[0], n[1].drop([best_feature], axis=1)) for n in new_data]
    return new_data

#创建决策树
def create_tree(data):
    data_label = data.iloc[:,-1]
    if len(data_label.value_counts()) == 1: #只有一类
        return data_label.values[0]
    if all(len(data[i].value_counts()) == 1 for i in data.iloc[:,:-1].columns): #所有数据的特征值一样，选样本最多的类作为分类结果
        return get_most_label(data)
    best_feature = get_best_feature(data) #根据信息增益得到的最优划分特征
    Tree = {best_feature:{}} #用字典形式存储决策树

    for item in drop_exist_feature(data,best_feature): #根据特征值的不同递归创建决策树
        Tree[best_feature][item[0]] = create_tree(item[1])
    return Tree

def predict(Tree , test_data):
    first_feature = list(Tree.keys())[0]
    second_dict = Tree[first_feature]
    input_first = test_data.get(first_feature)
    input_value = second_dict[input_first]
    if isinstance(input_value , dict): #判断分支还是不是字典
        class_label = predict(input_value, test_data)
    else:
        class_label = input_value
    return class_label

if __name__ == '__main__':
    #读取数据
    data = pd.read_csv('data_word.csv')
    data.insert(0,'序号',np.arange(0,17))
    cal_information_gain(data,'序号')
    #创建决策树
    dicision_Tree = create_tree(data)
    #测试数据
    test_data_1 = {'色泽':'青绿','根蒂':'蜷缩','敲声':'浊响','纹理':'稍糊','脐部':'凹陷','触感':'硬滑'}
    test_data_2 = {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑'}
    result = predict(dicision_Tree,test_data_2)
    print('分类结果为'+'好瓜'if result == 1 else '坏瓜')

待更

待更