前言

在上篇文章中介绍了决策树的一些基本概念，在这篇文章中，将介绍决策树ID3和C4.5算法的代码实现以及一些优化。

ID3实现

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征，递归地构建决策树，算法伪代码在上篇文章中给出了。在这里将给出其代码实现。

代码

import pandas as pd
from math import log

def load(filename):
    '''
        input: 文件
        output: DataFrame数据
    '''
    df = pd.read_csv(filename)
    return df

def calEnt(df):
    '''
        input: 数据集
        output: 熵
        descripion: 计算给定数据集的熵
    '''
    # 返回数据行数
    numEntries = df.shape[0]
    # 字典，用于保存每个标签（label）出现次数
    labelCounts = {}
    cols = df.columns.tolist()
    # 获取标签
    classlabel = df[cols[-1]].tolist()
    # 对每组特征向量进行统计
    for currentlabel in classlabel:
        if currentlabel not in labelCounts.keys():
            labelCounts[currentlabel] = 1
        else:
            labelCounts[currentlabel] += 1

    Ent = 0.0
    # 计算熵
    for key in labelCounts:
        prob = labelCounts[key]/numEntries
        Ent -= prob*log(prob, 2)

    return Ent

def splitDatsSet(df, axis, value):
    '''
        input: 数据集，所占列，选择值
        output: 划分数据集
        description: 按照给定特征划分数据集；选择所占列中等于选择值的项
    '''
    cols = df.columns.tolist()
    axisFeat = df[axis].tolist()
    # L = []
    # L.append(axis)

    # retDataset = df[list(set(cols)-set(L))]
    retDataset = pd.concat([df[feaVec] for feaVec in cols if feaVec != axis], axis=1)

    i = 0
    # 需要丢弃的行
    dropIndex = []
    for feaVec in axisFeat:
        if feaVec != value:
            dropIndex.append(i)
            i += 1
        else:
            i += 1
    # 划分数据集
    newDataset = retDataset.drop(dropIndex)
    return newDataset.reset_index(drop=True)


def chooseBestFeatureToSplit(df):
    '''
        input: 数据集
        output: 最优特征和信息增益
    '''
    # 获取特征数量
    numFeatures = len(df.columns) - 1
    # 计算熵
    Ent = calEnt(df)
    # 信息增益
    bestInfoGain = 0.0
    # 最优特征索引值
    bestFeature = -1
    cols = df.columns.tolist()
    # 遍历所有特征
    for i in range(numFeatures):
        # 获取第i个特征的所有不同的取值
        equalVals = set(df[cols[i]].tolist())
        # 经验条件熵
        newEnt = 0.0
        # 计算信息增益
        for value in equalVals:
            # 获取划分后的子集
            subDataset = splitDatsSet(df, cols[i], value)
            # 计算子集概率
            prob = subDataset.shape[0] / df.shape[0]
            # 根据公式计算条件熵
            newEnt += prob * calEnt(subDataset)
        infoGain = Ent - newEnt
        print(cols[i], infoGain)
        # 更新信息增益，找到最大的信息增益
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = cols[i]
    return bestFeature, bestInfoGain



def majorityCnt(classList):
    '''
        input: 类别列表
        output: 子节点的分类
        description: 数据集已经处理了所有属性，但是类标签依然不是唯一的，
          采用多数判决的方法决定该子节点的分类
    '''
    classCount = {}
    # 统计classList中每个元素出现的次数
    for clas in classList:
        if clas not in classCount.keys():
            classCount[clas] = 0
        classCount[clas] += 1
    # 根据字典值降序排列
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reversed=True)
    return sortedClassCount[0][0]

def createTree(df, dropcol):
    '''
        input: 数据集和需删除特征
        output: 决策树
        description: 递归实现决策树构建
    '''
    # cols = df.columns.tolist()[:-1]
    # 取分类标签
    classList = df[df.columns.tolist()[-1]].tolist()

    # 若数据集中所有实例属于同一类，将Ck作为该节点的类标记
    if classList.count(classList[0]) == len(classList):
        return classList[0]

    # 若特征集为空集，将数据集中实例数最大的类Ck作为该节点的类标记
    if len(df[0:1]) == 0:
        return majorityCnt(classList)

    # 获取最优特征与信息增益
    bestFeature, bestInfoGain = chooseBestFeatureToSplit(df)

    print('特征集和类别:',df.columns.tolist())
    print('bestFeature:',bestFeature)
    # 根据最优特征的标签生成树
    myTree = {bestFeature:{}}
    # 得到最优特征的属性值
    featValues = df[bestFeature]
    # 去掉重复属性值
    uniqueVals = set(featValues)
    # 遍历创建决策树
    for value in uniqueVals:
        myTree[bestFeature][value] = createTree(splitDatsSet(df, bestFeature, value), bestFeature)
    return myTree

def main():
    filename = "data.csv"
    dataset = load(filename)
    dropCol = []
    myTree = createTree(dataset, dropCol)
    print(myTree)

if __name__ == '__main__':
    main()

输入

输入选取统计学习方法中给出的数据集

age,work,hourse,loan,class
青年,否,否,一般,否
青年,否,否,好,否
青年,是,否,好,是
青年,是,是,一般,是
青年,否,否,一般,否
中年,否,否,一般,否
中年,否,否,好,否
中年,是,是,好,是
中年,否,是,非常好,是
中年,否,是,非常好,是
老年,否,是,非常好,是
老年,否,是,好,是
老年,是,否,好,是
老年,是,否,非常好,是
老年,否,否,一般,否

输出

age 0.08300749985576883
work 0.32365019815155627
hourse 0.4199730940219749
loan 0.36298956253708536
特征集和类别: ['age', 'work', 'hourse', 'loan', 'class']
bestFeature: hourse
age 0.2516291673878229
work 0.9182958340544896
loan 0.47385138961004514
特征集和类别: ['age', 'work', 'loan', 'class']
bestFeature: work
{'hourse': {'是': '是', '否': {'work': {'是': '是', '否': '否'}}}}

ID3算法的缺点

1. ID3算法对于缺失值没有进行考虑
2. 没有考虑过拟合的情况
3. ID3没有考虑连续特征
4. 上篇文章中有提到，ID3以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。
5. ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。

C4.5实现

C4.5就是在上面提出ID3的缺点中的第4条进行的改正，大部分代码都相同，除了在划分数据集的时候以信息增益比为划分标准，这在上篇文章中也提到过。

def chooseBestFeatureToSplit(df):
    '''
        input: 数据集
        output: 最优特征和信息增益
    '''
    # 获取特征数量
    numFeatures = len(df.columns) - 1
    # 计算熵
    Ent = calEnt(df)
    # 信息增益
    bestInfoGain = 0.0
    splitInfo = 0.0
    # 最优特征索引值
    bestFeature = -1
    cols = df.columns.tolist()
    # 遍历所有特征
    for i in range(numFeatures):
        # 获取第i个特征的所有不同的取值
        equalVals = set(df[cols[i]].tolist())
        # 经验条件熵
        newEnt = 0.0
        # 计算信息增益
        for value in equalVals:
            # 获取划分后的子集
            subDataset = splitDatsSet(df, cols[i], value)
            # 计算子集概率
            prob = subDataset.shape[0] / df.shape[0]
            # 根据公式计算条件熵
            newEnt += prob * calEnt(subDataset)
            # 计算特征熵
            splitInfo += -prob * log(prob, 2)
        infoGain = Ent - newEnt
        print(cols[i], infoGain)
        # 计算信息增益比
        infoGainRatio = infoGain / splitInfo
        # 更新信息增益比，找到最大的信息增益比
        if infoGainRatio > bestInfoGain:
            bestInfoGain = infoGainRatio
            bestFeature = cols[i]
    return bestFeature, infoGainRatio

结语

这篇文章给出了ID3与C4.5的代码实现，同时也提到了其中的一些缺点，对于缺点2中提到的过拟合现象，我们可以通过剪枝来简化模型，从而降低这一现象的产生。对于剪枝的实现及介绍，将在后面介绍CART算法时再讲述。

参考：

1. 《统计学习方法》——李航
2. 《机器学习实战》
3. 鱼佬的文章 https://zhuanlan.zhihu.com/p/30352406
4. https://blog.csdn.net/jiaoyangwm/article/details/79525237