使用ID3算法实现决策树（Python）

使用ID3算法实现一棵完整的树

今天，我来和大家分享一下最近学会的使用ID3算法来实现整个决策树。

直接上码

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


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': ...}


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


# 选取当前数据集下，用于划分数据集的最优特征
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 # 初始化最优信息增益和最优的特征
    # 循环特征（列）
    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   # 条件熵
        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)
        print( '信息熵为:' + str(ent) )
        print( '第' + str(i) + '列的条件熵为:' + str(newEnt) )
        gain = ent - newEnt
        print( '第' + str(i) + '列的信息增益为:' + str(gain) )
        #gain1 = gain
        #print( '第' + str(i) + '列的信息增益比为:' + str(gain1) )
        if (gain > bestGain):
            # 比较每个特征的信息增益，只要最好的信息增益
            bestGain = gain
            bestFeatureID = i
    return bestFeatureID


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]


# 生成决策树的总方法
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

我们来测试一下上面的代码

测试语句：

dataSet,labels = createDataSet()
tree = createTree( dataSet,labels,max_depth=300 )
tree

可以得到结果：

由此成功的创建了一棵树。

之前在我的前两个博客中已经为大家详解了 ID3 算法的原理与实现 ，此代码只是使用ID3代码进一步完成了整个决策树的建立，创建树的总方法createTree()我在代码中做了详细注释，对于前面的ID3算法实现的代码若有疑惑可以参照我的前两篇文章。

决策树算法原理（三种最优属性划分方法）：

https://blog.csdn.net/LA401088242/article/details/89034077

决策树ID3算法的代码实现（Python）：

https://blog.csdn.net/LA401088242/article/details/89052398

希望可以帮到大家。