决策树4：构建算法之ID3、C4.5

0x01 ID3算法介绍

1.1 简介

ID3算法是一种分类预测算法，算法以信息论中的“信息增益”为基础。核心是通过计算每个特征的信息增益，每次划分选取信息增益最高的属性为划分标准，递归地构建决策树。

ID3相当于用极大似然法进行概率模型的选择。

具体方法是：

从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。
由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；
最后得到一个决策树。

从ID3的构建树过程而言，它可以看成使用贪心算法得到近似最优的一颗决策树，它无法保证是最优的。

1.2 构建流程

以递归的方式构建一棵决策树，其算法流程如下：

代码语言：javascript复制

算法：createTree(dataSet,featList,bestFeatLists)。由给定的训练数据产生一棵判定树。输入：    dataSet：训练数据集    featList：分类属性标签    bestFeatLists：存储选择的最优特征标签输出：    myTree：一棵判定树。方法：createTree(dataSet,featList,bestFeatLists)1）从传入的数据集dataSet中切割出分类标签，yList2）如果yList中只有同一种标签，说明已经递归到分类边界了，则返回该标签3）如果已经处理了dataSet中所有属性（列），但是类标签依然不是唯一的，采用多数判决的方法决定该子节点的分类4）找出dataSet最优划分（信息增益最大）的特征所在位置bestFeatVec5）在分类属性标签featList找出该位置所对应的特征值bestFeatLabel，并将该特征值存储到bestFeatLists中6）将最优划分特征值作为当前（子）树的根节点，生成初始决策树myTree（用字典表示一个树结构）7）在featList中删除当前已经使用过的特征标签（因为每次选择特征作为条件，dataSet会删掉这一列，形成新的子类，因此对应的featList中的值也要删掉）8）确定子树分支：获取已选择的最优划分特征所对应的值分类categories（如“年龄”是最优特征，则“老”“中”“青”三个子类）9）遍历每一个当前特征下的子类，在每个子类中，递归地调用创建决策树的方法，将递归调用的结果作为当前树节点的一个分支（构建树的方法是：特征作为字典的key，所得到的分类结果作为value；子树进行嵌套）

0x02 代码实例

现在我们以银行贷款申请业务为例，模拟四个特征，分别是：年龄、有工作、有房子、信贷情况。

代码语言：javascript复制

"""函数说明：数据集已经处理了所有属性，但是类标签依然不是唯一的,采用多数判决的方法决定该子节点的分类        即统计yList中出现次数最多的元素（类标签）Parameters：    yList：类标签列表Returns：    sortedClassCount[0][0]：出现次数最多的元素（类标签）"""def majorityCnt(yList):    yCount={}    #统计yList中每个元素出现的次数    for vote in yList:        if vote not in yCount.keys():            yCount[vote]=0        yCount[vote] =1        #根据字典的值降序排列        sortedYCount=sorted(yCount.items(),key=operator.itemgetter(1),reverse=True)    return sortedYCount[0][0]
"""函数说明：创建决策树
Parameters:    dataSet：训练数据集    featList：分类属性标签    bestFeatLists：存储选择的最优特征标签Returns：    myTree：决策树"""def createTree(dataSet,featList,bestFeatLists):    # 取训练数据集最后一列，即分类标签    yList=[example[-1] for example in dataSet]        # 如果类别完全相同，则停止继续划分，    # 即yList中所有类别都是同一数据值（该类别数值个数等于列表长度）    if yList.count(yList[0])==len(yList):        # 返回该类别数值        return yList[0]            # 数据集已经处理了所有属性，但是类标签依然不是唯一的，    # 则采用多数判决的方法决定该子节点的分类    # 为什么要如此判断？dataSet的列是不断减少的，dataSet某一行的长度，就是列    if len(dataSet[0])==1:        return majorityCnt(yList)        # 选择最优划分的特征index    bestFeatVec = optimalPartition(dataSet)    # 最优特征index所对应的分类标签，作为树的根节点    bestFeatLabel=featList[bestFeatVec]    # 存储选择的最优特征标签    bestFeatLists.append(bestFeatLabel)        # 将最优划分特征值作为当前（子）树的根节点，生成初始决策树（用字典表示一个树结构）    myTree={bestFeatLabel:{}}        # 删除已经使用的特征标签（del删除变量，解除引用）    # 因为每次选择特征作为条件，dataSet会删掉这一列，形成新的子类，因此对应的featList中的值也要删掉    del(featList[bestFeatVec])    print('featList: ',featList)            # 得到训练集中所有最优特征那一列所对应的值    featValues=[example[bestFeatVec] for example in dataSet]    # 去掉重复的属性值，得到最优特征下的子类    categories=set(featValues)        # 遍历最优特征列所对应的值，创建决策树    # 如“年龄”是最优特征，则遍历“老”“中”“青”三个子类    for category in categories:        # 根据当前数据集、最优划分的特征index以及每个分类（条件）得到（条件下的子集）        subDataSet = np.array(currentConditionSet(dataSet,bestFeatVec,category))        # 递归地调用创建决策树的方法，将递归调用的结果作为当前树节点的一个分支        myTree[bestFeatLabel][category]=createTree(subDataSet,featList,bestFeatLists)    return myTree
if __name__=='__main__':    #print('featLabels',featLabels)    bestFeatLists = []    myTree=createTree(dataSet,featList,bestFeatLists)    print(myTree)

输出：第0个特征的增益为0.083第1个特征的增益为0.324第2个特征的增益为0.420第3个特征的增益为0.363最佳的划分为第2个特征，是”有自己的房子“，信息增益为0.420第0个特征的增益为0.252第1个特征的增益为0.918第2个特征的增益为0.474最佳的划分为第1个特征，是”有工作“，信息增益为0.918{'有自己的房子': {0: {'有工作': {0: 0, 1: 1}}, 1: 1}}

解读结果：