使用C4.5算法实现决策树（Python）_c4.5决策树图 python

使用C4.5算法实现一棵完整的树

决策树的构建需要找到最优特征列对树的节点进行层层划分，而找寻最优特征列常用的有ID3，C4.5，CART三种方法，今天我给大家讲解一下如何使用C4.5算法来找到最优特征列来建立决策树。

1.首先我们创建一组数据，该数据组一共由8组数据组成，共2列特征列，1列标签列

from math import log
import operator
 
def createDataSet():
    dataSet = [[1,1,'yes'],
               [1,1,'yes'],
               [1,0,'yes'],
               [0,1,'no'],
               [0,1,'no'],
               [0,0,'no'],
               [0,0,'yes'],
               [0,0,'no']]
    labels = ['是否有房产','是否有车']
    return dataSet,labels

2.使用ID3算法，需计算信息熵，我们先创建calcShannonEnt方法计算信息熵

注：熵的计算公式为   参照公式理解代码更加简单。

def calcShannonEnt(dataSet):
    num = len(dataSet)    # 总共有多少行数据   8
    shannonEnt = 0.0  #初始化信息熵
    labelCounts = {}
    for item in dataSet:   # 遍历整个数据集，每次取一行
        label = item[-1]  #取该行最后一列的值  即标签
        if label not in labelCounts:  # 在字典中这个label是否存在
            labelCounts[label] = 0
        labelCounts[label] += 1    #{ 'yes':2,'no':3 }
    for key in labelCounts:
        p = float(labelCounts[key]/num)    # 即每个标签所占的比重
        #print( p )
        shannonEnt -= p * log(p,2)  #log base 2 计算信息熵  
    return shannonEnt     # 返回根节点信息熵
    # labelCounts  {'yes': ..., 'no': ...}

我们来测试一下这个方法

dataSet,labels = createDataSet()
shan = calcShannonEnt( dataSet )
print( shan )
'''
熵值越高，则混合的数据越多
'''
# 下面再增加一个分类
dataSet[7][-1] = '不确定'
shan = calcShannonEnt( dataSet )
print( shan )

运行上面代码得到结果

3. 接下来，我们创建一个splitDataSet方法来对我们的数据集进行切割

注：实际上就是将每一行的第二列特征列和标签列切分出来，以方便后面的计算

def splitDataSet( dataSet,axis,value ):
    result = []
    for item in dataSet:     #  item:  [1,1,'yes']
        if item[axis] == value:
            r = item[:axis] + item[axis+1:]  # []+[1,'yes'] => r=> [1,'yes']
            # r = item[-1:]  #TODO: 只作熵运算的话，只用保留最后一列的值即可
            result.append(r)
    return result

我们再来测试一下代码，看看其实现效果如何

dataSet,labels = createDataSet()
result = splitDataSet( dataSet,0,1 )
print(result)
result = splitDataSet( dataSet,0,0 )
print(result)
result = splitDataSet( dataSet,1,1 )
print(result)
result = splitDataSet( dataSet,1,0 )
print(result)

运行上面代码得到结果

4. 到了我们最重要的一步，通过信息熵计算信息增益率来求出划分数据集的最优特征

注：信息增益的计算公式为

       信息增益率的计算公式为

       其中  

# 选取当前数据集下，用于划分数据集的最优特征
def chooseBestFeatures(dataSet):
    # 1. 特征总数  2
    numFeatures = len(dataSet[0]) -1  # 获取当前数据集的特征个数，最后一列是分类标签    2
    # 2. 计算信息熵   1
    ent = calcShannonEnt(dataSet) # 计算当前数据集的信息熵    (根节点信息熵)
    # 3. 最佳信息熵
    bestGain = 0.0;
    # 4. 最佳特征号 (0,1)
    bestFeatureID = -1 # 初始化最优信息增益和最优的特征
    # 5.最佳信息增益率
    infogain = 0.0;
    # 循环特征（列）
    for i in range(numFeatures):
        list1 = [line[i] for line in dataSet] # 获取数据集中当前特征下的所有值
        uniqueValues = set(list1)  # 每一列去重后的值， set可以去重 set(list) 将list列表强制转换为set  {0,1}
        #print( uniqueValues )
        newEnt = 0.0   # 条件熵
        s = 0.0
        for value in uniqueValues:
            # 调用splitDataSet ( 列,set中的值 ) -> 得到子集
            subDataSet = splitDataSet(dataSet,i,value)      # (dataSet,0,0) (dataSet,0,1) (dataSet,1,0) (dataSet,1,1)  
            # 计算概率
            prob = len(subDataSet)/float(len(dataSet))      #       5/8          3/8           4/8           4/8
            # 计算熵
            newEnt += prob * calcShannonEnt(subDataSet)
            s -= prob * log(prob, 2);
        print( '信息熵为:' + str(ent) )
        print( '第' + str(i) + '列的条件熵为:' + str(newEnt) )
        gain = ent - newEnt
        print( '第' + str(i) + '列的信息增益为:' + str(gain) )
        infogain = gain/s   # 求该列的信息增益比
        print( '第' + str(i) + '列的信息增益比为:' + str(infogain) )
        if (infogain > bestGain):
            # 比较每个特征的信息增益比，只要最好的信息增益比
            bestGain = infogain
            bestFeatureID = i
    return bestFeatureID

在代码中，s 即为公式中的 IV(a)

测试一遍上面代码计算信息增益和信息增益率

dataSet,labels = createDataSet()
index = chooseBestFeatures( dataSet )
print(index)

得到结果

5. 建立一个classNum()方法（为构建决策树做准备）

注：该方法实际上就是将传入的离散型数据按出现的频率进行降序排列，并返回第一个键名

def classNum( classList ):
    '''
    classList: 分类的名称
    '''
    classCount = {}    # 存各种分类出现的频率 : {'yes',1,'no',2}
    for label in classList:
        classCount[label] = classCount.get(label,0) + 1
    # 对字典进行排序
    sortedClassCount = sorted( classCount.items(),key=operator.itemgetter(1),reverse=True )
    print( sortedClassCount )
    return sortedClassCount[0][0]

对此方法进行测试

classNum( ['yes','no','no','yes','no'] )

得到结果

6. 下面我们开始根据我们得到的最优特征来构建决策树

# 生成决策树的总方法
def createTree(dataSet,labels,depth=0,max_features=None,max_depth=None):
    # 求出 dataSet 中的样本所属的类别，即递归停止的条件一
    # 返回当前数据集下标签所有的值
    classList = [example[-1] for example in dataSet]  # ['yes','yes','yes','no','no','no','yes','no']
    # 终止条件1： 可以加上判断 这个classList是否纯净
    if classList.count(classList[0]) == len(classList):
        # 纯净的意思就是此数据中所有特征都相等
        # 当整个dataSet中的类别完全相同时类别已经纯净了，则停止继续划分，直接返回该类标签
        return classList[0]  
    # 终止条件2： 列中的取值种类   <=max_features 时.   max_features 即划分时考虑的最大特征数  默认为 None
    if max_features == None:
        max_features = 1
    if len( dataSet[0] )<=max_features:
        return classNum( classList )   # 返回数量多的那一个 标签
    
    #  max_depth  树的最大深度,也就是说当树的深度到达max_depth的时候无论还有多少可以分支的特征,决策树都会停止运算
    
    if max_depth!=None:
        if depth>=max_depth:
            return classNum(classList)
        depth = depth + 1
    
    # 获取最好的分类特征索引
    # dataSet = [1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'yes'], [0, 1, 'no'], [0, 1, 'no'], [0, 0, 'no'], [0, 0, 'yes'], [0, 0, 'no']
    bestFeat = chooseBestFeatures(dataSet)    # bestFeat: 0      bestFeat: 0
    #print( 'bestFeat:',bestFeat )
    
    # 获取该特征的名字
    # labels = ['是否有房产', '是否有车']
    bestFeatLabel = labels[bestFeat]
    #print( 'bestFeatLabel:',bestFeatLabel )   # bestFeatLabel: 是否有房产    bestFeatLabel: 是否有车
    
    # 这里直接使用字典变量来存储树信息，这对于回执树形图很重要
    myTree = {bestFeatLabel:{}}    # 当前数据集选取最好的特征存储在bestFeat中
    del(labels[bestFeat])    # 删除已经在选取的特征  此时  labels = ['是否有车']
    
    # 取出最优列的值
    featValues = [example[bestFeat] for example in dataSet]
    # featValues: [1, 1, 1, 0, 0, 0, 0, 0]      featValues: [1, 1, 0, 0, 0]
    #print( 'featValues:',featValues )    
    # 去重
    uniqueVals = set(featValues)   # [1,0]
    # 根据这个列的这个 uniqueVals值来切分树的节点
    for value in uniqueVals:
        #  myTree  -> 房产 -> 1
        #             房产 -> 0 
        subLabels = labels[:]
        #print( 'subLabels:',subLabels )
        temp = splitDataSet( dataSet,bestFeat,value )
        #print( 'temp:',temp )
        myTree[bestFeatLabel][value] = createTree(temp,subLabels,depth=depth,max_features=max_features,max_depth=max_depth)
    return myTree

我们来看看我们构建的决策树

 

该决策树共进行两次分类，第一次由‘是否有房产’进行一次划分，第二次由‘是否有车’进行一次划分

由于我们建立的数据并不合理，所以看上去我们建立的决策树并不可观，大家可以试试更多数据构建新的决策树

注：此文章为代码实现，看起来可能有些费解，大家可以参照本人的另一篇博客https://blog.csdn.net/LA401088242/article/details/89034077 了解其原理，以便大家更好的了解代码