前言

上篇文章介绍了决策树(Decision Tree)的原理和实现决策树算法，如果对这些不懂的，可以移步上篇文章，本文章完成的是用ID3算法实现决策树。

定义数据

假设以下数据

其中N1、N2为我们的featrues ， X为我们的label。决策目标是X的值，TRUE或者FALSE。

定义以下数据:

def load_data():
    data=[
        ['I','I','TRUE'],
        ['T','I','TRUE'],
        ['I','T','TRUE'],
        ['C','I','FALSE'],
        ['T','T','TRUE'],
        ['I','C','FALSE'],
        ['E','I','FALSE'],
        ['C','T','FALSE'],
        ['T','C','FALSE'],
        ['I','E','FALSE'],
        ['E','T','FALSE'],
        ['T','E','FALSE']
        ]
    features=["N1","N2"]
    return data,features

计算熵

由上数据得，共有12个样本，共有4个TRUE和8个FALSE，那么熵的计算公式就是

def cal_entropy(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        label = featVec[-1]
        if label not in labelCounts.keys():
            labelCounts[label] = 0
        labelCounts[label] += 1
    entropy = 0.0
    for key in labelCounts.keys():
        p_i = float(labelCounts[key] / numEntries)
        entropy -= p_i * log(p_i,2)#log(x,10)表示以10 为底的对数
    return entropy

选择信息增益

选择最大的信息增益对应的feature。信息增益的解释在上篇博客。

def choose_best_to_split(data):
    '''
    根据每个特征的信息增益，选择最大的划分数据集的索引特征
    '''
    count_feature=len(data[0])-1#特征个数2
    # print(count_feature) #2
    entropy=cal_entropy(data) #原数据总的信息熵
    # print(entropy) #0.9182958340544896
    
    max_info_gain=0.0 #信息增益最大
    split_fea_index = -1 #信息增益最大，对应的索引号
    # 遍历每个feature
    for i in range(count_feature):
        
        feature_list = [fe_index[i] for fe_index in data] #获取该列所有特征值
        # print(feature_list)
        '''
            print('feature_list')
            ['I', 'T', 'I', 'C', 'T', 'I', 'E', 'C', 'T', 'I', 'E', 'T']
            0.6666666666666666
            0.2516291673878229
        '''
        unqval = set(feature_list) #去除重复
        Pro_entropy=0.0 #特征的熵
        for value in unqval: #遍历改特征下的所有属性
            sub_data = split_data(data,i,value)
            pro = len(sub_data) / float(len(data))
            Pro_entropy += pro * cal_entropy(sub_data)
            # print(Pro_entropy)
        info_gain = entropy-Pro_entropy
        # print(info_gain)
        '''
            N1的info_gain：0.2516291673878229
            N2的info_gain：0.2516291673878229
            两者一样,说明根决策点选择哪个feature都跟最终结果没有影响。
        '''
        if(info_gain > max_info_gain):
            max_info_gain = info_gain
            split_fea_index = i
    return split_fea_index       

通过输出每个feature的信息增益，发现每个feature对整个信息的影响程度都相同，所以无论选取哪个feature作为根决策点，都对结果没有影响，文章末尾可以通过决策树可视化来说明。

划分数据

划分数据集，选择最大的信息增益之后，划分数据集，为下一层的划分做准备

def split_data(data,feature_index,value):
    '''
    划分数据集
    feature_index：用于划分特征的列数
    value:划分后的属性值
    '''
    data_split=[]#划分后的数据集
    for feature in data:
        if feature[feature_index]==value:
            reFeature=feature[:feature_index]
            reFeature.extend(feature[feature_index+1:])
            data_split.append(reFeature)
    return data_split

构建决策树

利用多重字典来构建决策树， 字典的key用来存节点信息，分支和叶子节点存放值。

建树的过程是一个递归的过程。

def build_decesion_tree(dataSet,featnames):
    featname = featnames[:]
    classlist = [featvec[-1] for featvec in dataSet]  #此节点的分类情况
    if classlist.count(classlist[0]) == len(classlist):  #全部属于一类
        return classlist[0]
    if len(dataSet[0]) == 1:         #就剩下一个属性了
        return classlist 
    # 选择一个最优特征进行划分
    bestFeat = choose_best_to_split(dataSet)
    bestFeatname = featname[bestFeat]
    del(featname[bestFeat])     # 删除元素
    DecisionTree = {bestFeatname:{}} # 决策树的节点
    # 创建分支,先找出所有属性值,即分支数
    allvalue = [vec[bestFeat] for vec in dataSet]
    specvalue = sorted(list(set(allvalue)))  #字典序排序
    for v in specvalue:
        copyfeatname = featname[:]
        DecisionTree[bestFeatname][v] =  build_decesion_tree(split_data(dataSet,bestFeat,v),copyfeatname)
    return DecisionTree

返回结果:

{'N1': {'C': 'FALSE', 'E': 'FALSE', 'I': {'N2': {'C': 'FALSE', 'E': 'FALSE', 'I': 'TRUE', 'T': 'TRUE'}}, 'T': {'N2': {'C': 'FALSE', 'E': 'FALSE', 'I': 'TRUE','T': 'TRUE'}}}}

如果选取N2作为根决策点，输出的结果:

{'N2': {'C': 'FALSE', 'E': 'FALSE', 'I': {'N1': {'C': 'FALSE', 'E': 'FALSE', 'I': 'TRUE', 'T': 'TRUE'}}, 'T': {'N1': {'C': 'FALSE', 'E': 'FALSE', 'I': 'TRUE', 'T': 'TRUE'}}}}

说明对于此数据(其他数据除外)，特征的选择顺序对决策的结果没有影响。

决策树可视化

对于两种决策树进行可视化的结果如下: