机器学习算法之决策树(二)

前言

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

定义数据

假设以下数据

N1N2X
IITRUE
TITRUE
ITTRUE
CIFALSE
TTTRUE
ICFALSE
EIFALSE
CTFALSE
TCFALSE
IEFALSE
ETFALSE
TEFALSE

其中N1N2为我们的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'}}}}

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

决策树可视化

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

请输入图片描述

请输入图片描述

有一群人,在和你一样的并肩努力着,要把这样的陪伴铭记于心,把自己坚持的路走下去

文章名: 《机器学习算法之决策树(二)》
文章链接:http://hrhr7.cn/index.php/archives/8/
联系方式:tensor7@163.com
除特别注明外,文章均为Cupidr原创,转载时请注明本文出处及文章链接
Last modification:November 22nd, 2019 at 08:00 pm
如果觉得我的文章对你有用,请随意赞赏

2 comments

  1. 刘俊娇

  2. 刘俊娇

Leave a Comment