精华内容
下载资源
问答
  • 龙源期刊网http://www.qikan.com.cn决策树CART算法的Clementine与Python实现比较作者:杜婵来源:《大经贸》2018年第01期【摘要】近年来,信息社会中丰富的数据对数据分析工具需求加大,数据挖掘技术应运而生,决策...

    龙源期刊网

    http://www.qikan.com.cn

    决策树

    CART

    算法的

    Clementine

    Python

    实现比较

    作者:杜婵

    来源:《大经贸》

    2018

    年第

    01

    【摘

    要】

    近年来,信息社会中丰富的数据对数据分析工具需求加大,数据挖掘技术应运

    而生,决策树方法以其速度快、精度高、生成的模式简单等优点受到许多研究者关注,已成功

    应用于医疗诊断、金融分析、身份识别等许多应用领域,一般情况下决策树分类器具有良好的

    准确率。本问旨在使用银行营销数据通过

    Clementine

    python

    两种方法构造决策树

    CART

    法下的模型,分别得出影响客户办理银行定期存款业务的各因素的重要程度,以及通过模型对

    输出变量

    y

    预测的精度,从而进行两个结果的对比分析,找出两种方法存在的差异。

    【关键词】

    决策树

    CART

    算法

    Clementine

    Python

    预测精度

    一、数据介绍

    本次报告中使用的

    Bank Marking

    (银行营销)数据是通过

    UCI

    数据库下载获得,该数据

    共涉及

    45211

    条客户信息,包含

    17

    个变量,其中输出变量为是否办理了定期存款业务,是本

    次研究的目标。

    二、方法执行过程与结果

    1.spss

    Clementine

    的实现

    1

    )数据准备:将赋值好的

    SPSS

    数据导入

    Clementine

    ;而后设置数据类型:将前

    16

    自变量设为输入变量,而将客户是否办理定期存款业务

    “y”

    设置为输出变量;接着进行数据分

    区,需要将数据集分为训练集与测试集,数据比例设置为

    8

    2

    ,通过

    80%

    的数据进行训练来

    构造模型,剩余

    20%

    的数据将作用于该模型来进行预测。

    2

    )建模:做好数据准备后执行决策树的

    CART

    算法,为了防止过度拟合进行先剪枝,

    将最大树状图深度设置为

    5

    ,并选用

    Gini

    系数作为分解属性的标准,而后开始训练模型。由模

    型输出的变量重要性排序可得,对输出变量影响较大的前四位依次为:与客户最后一次联系的

    时长、以前的营销活动的结果、与客户最后一次联系的月份,以及通讯方式关系较大,可以重

    点关注这四方面。

    3

    )评估与分析结果:①训练与测试的预测精度:训练集数据的预测正确率为

    89.81%

    通过用训练样本所构造的模型来验证测试样本,预测结果正确的有

    8115

    个,占总测试样本

    9028

    中的

    89.89%

    ,预测精确度较高,效果较好。②累计收益图:该算法所得的累计收益曲线

    展开全文
  • CART算法的数学详细计算步骤,以及CART算法生成决策树的过程,可以详见:【机器学习】【决策树CART算法,用样本集一步一步详解如何求:基尼指数,最优特征,最优切分点本章仅提供CART算法python实现代码,以...

    CART算法的数学详细计算步骤,以及CART算法生成决策树的过程,可以详见:

    【机器学习】【决策树】CART算法,用样本集一步一步详解如何求:基尼指数,最优特征,最优切分点

    本章仅提供CART算法的python实现代码,以python类面向对象方式实现~

    代码写的好艰难,完全一行一行码出来了,还是写出来了,现在已经凌晨0:13了。

    1.样本数据集

    def create_samples():  
        ''''' 
        提供训练样本集 
        每个example由多个特征值+1个分类标签值组成 
        比如第一个example=['youth', 'no', 'no', '1', 'refuse'],此样本的含义可以解读为: 
        如果一个人的条件是:youth age,no working, no house, 信誉值credit为1
        则此类人会被分类到refuse一类中,即在相亲中被拒绝(也可以理解为银行拒绝为此人贷款)
        每个example的特征值类型为: 
        ['age', 'working', 'house', 'credit'] 
        每个example的分类标签class_label取值范围为:'refuse'或者'agree' 
        '''  
        data_list = [['youth', 'no',  'no',   '1', 'refuse'],  
                     ['youth', 'no',  'no',   '2', 'refuse'],  
                     ['youth', 'yes', 'no',   '2', 'agree'],  
                     ['youth', 'yes', 'yes',  '1', 'agree'],  
                     ['youth', 'no',  'no',   '1', 'refuse'],  
                     ['mid',   'no',  'no',   '1', 'refuse'],  
                     ['mid',   'no',  'no',   '2', 'refuse'],  
                     ['mid',   'yes', 'yes',  '2', 'agree'],  
                     ['mid',   'no',  'yes',  '3', 'agree'],  
                     ['mid',   'no',  'yes',  '3', 'agree'],  
                     ['elder', 'no',  'yes',  '3', 'agree'],  
                     ['elder', 'no',  'yes',  '2', 'agree'],  
                     ['elder', 'yes', 'no',   '2', 'agree'],  
                     ['elder', 'yes', 'no',   '3', 'agree'],  
                     ['elder', 'no',  'no',   '1', 'refuse']]
        feat_list = ['age', 'working', 'house', 'credit']  
        return data_list, feat_list

    2.运行结果-cart决策树的字典

    max_n_feats = 3时

    tree_dict = {
             house :{
                     yes :  agree
                     no :{
                             working : {'yes': 'agree', 'no': 'refuse'}
                             }
                     }
             }

    3.运行结果-决策树的绘制图形

    max_n_feats = 3时


    4.核心代码讲解

    核心代码是:类class CCartTree(object)中的work()接口和create_tree()接口

        work()是cart算法,生成最优特征,最优切分点,最优叶节点等等

        create_tree()是递归生成cart决策树字典

    树的限制递归生成阈值:

        max_n_feats,当剩下的样本集的特征数少于max_n_feats,将不再进行继续生成。

        也可以提供gini阈值~

    5.代码

    # -*- coding: utf-8 -*-
    """
    @author: 蔚蓝的天空Tom
    Aim:给定样本集和特征列表,计算每个特征的基尼指数,选取最优特征,选取最优分切点
    Aim:生成CART决策树的字典形式
    Aim:根据决策树字典绘制CART决策树图形
    cart_dtree.py
    """
    
    import matplotlib.pyplot as plt
    
    def print_dict(src_dict, level, src_dict_namestr=''):
            '''
            逐行打印dict  
            :param self:类实例自身  
            :param src_dict:被打印的dict  
            :param level:递归level,初次调用为level=0  
            :param src_dict_namestr:对象变量名称字符串  
            '''    
            if isinstance(src_dict, dict):    
                tab_str = '\t'    
                for i in range(level):
                    tab_str += '\t'
                if 0 == level:    
                    print(src_dict_namestr,'= {')    
                for key, value in src_dict.items():    
                    if isinstance(value, dict):    
                        has_dict = False    
                        for k,v in value.items():    
                            if isinstance(v, dict):
                                has_dict = True    
                        if has_dict:    
                            print(tab_str,key,":{")    
                            print_dict(value, level + 1)    
                        else:    
                            print(tab_str,key,':',value)    
                    else:    
                        print(tab_str,key,': ',value,)    
                print(tab_str,'}')
                
    '''
    裁剪规格简介
    
    #每个样本example的特征列表
    feature_type_list = ['youth','work','hourse','credit']
    
    即每个样本=[age_value, work_value, housr_value, crdit_value, class_label]
    
    如下一个样本集:
    samples_list = [ ['youth', 'work_no', 'house_no', '1', 'refuse']
                     ['youth', 'work_no', 'house_no', '2', 'refuse']
                     ['youth', 'work_yes', 'house_no', '2', 'agree']
                     ['youth', 'work_yes', 'house_yes', '1', 'agree']
                     ['youth', 'work_no', 'house_no', '1', 'refuse']
                     ['mid', 'work_no', 'house_no', '1', 'refuse']
                     ['mid', 'work_no', 'house_no', '2', 'refuse']
                     ['mid', 'work_yes', 'house_yes', '2', 'agree']
                     ['mid', 'work_no', 'house_yes', '3', 'agree']
                     ['mid', 'work_no', 'house_yes', '3', 'agree']
                     ['elder', 'work_no', 'house_yes', '3', 'agree']
                     ['elder', 'work_no', 'house_yes', '2', 'agree']
                     ['elder', 'work_yes', 'house_no', '2', 'agree']
                     ['elder', 'work_yes', 'house_no', '3', 'agree']
                     ['elder', 'work_no', 'house_no', '1', 'refuse'] ]
    
    
    假设已经通过信息增益选出此样本集的决策树的最优根节点为特征housre
    
    如果想求子决策树的最优根节点的话,就需要对原始样本集进行裁剪了,然后用新的样本集筛选新的最优根节点
    
    #通过如下规则得到新的样本集
    step1:删除hourse特征值为house_yes所在的所有行
    step2:然后再删除hourse特征值列
    '''
    class CTailorSamples(object):
        '''裁剪样本集'''
        def __init__(self, data_list, feat_type_list, feat_type_index, feat_value):
            self.data_list = data_list
            self.feat_type_list = feat_type_list
            self.feat_type_index_tailed = feat_type_index
            self.feat_value_tailed = feat_value
    
            self.tailer_work()#裁剪
    
        def get_samples(self):
            '''
            返回裁剪后的样本集,特征类型列表
            '''
            return self.data_list, self.feat_type_list
    
        def get_all_indexs(self, src_list, dst_value):
            '''
            返回给定值的所有元素的下标
            src_list = [10,20,30,30,30,50]
            e = 30
            indexs_list = tailor.get_all_indexs(src_list, e)
            print(indexs_list) #[2, 3, 4]
            '''
            dst_val_index = [i for i,x in enumerate(src_list) if x == dst_value]
            return dst_val_index
    
        def tailer_work(self):
            '''裁剪得到新的特征列表'''
            del self.feat_type_list[self.feat_type_index_tailed]
    
    
            '''裁剪数据集'''
            #摘取被删除的特征列
            colum_to_del = self.feat_type_index_tailed
            self.feat_value_list = [example[colum_to_del] for example in self.data_list]
        
            #找出含有self.feat_value_tailed特征值的所有样本所在行的下标
            rows_to_del = self.get_all_indexs(self.feat_value_list, self.feat_value_tailed)
    
            #删除row_index_list中行下标对应的self.src_data_list的行
            #技巧:从大的行下标开始依次删除
            #for row in list(reversed(rows_to_del)):
            #for row in rows_to_del[::-1]:
            rows_to_del.reverse()
            for row in rows_to_del:
                del self.data_list[row]
    
            #删除给定的特征列
            for row in range(len(self.data_list)):
                del self.data_list[row][colum_to_del]
    
            return self.data_list, self.feat_type_list
    
    class CCartTree(object):
        def __init__(self, samples, feat_list, div_label, max_n_feats):
            self.samples = samples
            self.feat_list = feat_list
            self.div_label = div_label
            self.max_n_feats = max_n_feats
            self.tree_dict = {}
            self.create_tree()
        
        def get_tree_dict(self):
            return self.tree_dict
            
        def work(self, samples, feat_list, div_label, max_n_feats):
            '''
            给定样本数据集+特征列表,找出最优特征,最优切分点,最优叶节点,次优切分点
            :param samples:样本数据集
            :param feat_list:特征列表, 比如['age','work','house','credit']
            :return 样本集的最优特征,最优切分点最优叶节点
            :Note,每个样本=[ageVal, workVal, houseVal, creditVal, classLabel]
            '''
            stat, n_samples = {}, len(samples)
            class_vals = [e[-1] for e in samples]
            class_set = set(class_vals)
            for i in range(len(feat_list)):
                f, stat[f] = feat_list[i], {}#feature
                for e in samples:
                    v,c = e[i], e[-1] #feature's value, feature value's class label
                    if v not in stat[f].keys():
                        stat[f][v],stat[f][v]['n'],stat[f][v]['p'] = {},0,0.0
                        stat[f][v][c],stat[f][v][c]['n'],stat[f][v][c]['p'] = {},0,0.0
                    elif c not in stat[f][v].keys():
                            stat[f][v][c],stat[f][v][c]['n'],stat[f][v][c]['p']={},0,0.0
                    stat[f][v]['n'] += 1
                    stat[f][v]['p'] = stat[f][v]['n']/n_samples
                    stat[f][v][c]['n'] += 1
                    #update stat[f][v][every c]['p']
                    for x in class_set:
                        if x not in stat[f][v].keys():
                            stat[f][v][x],stat[f][v][x]['n'],stat[f][v][x]['p']={},0,0
                        stat[f][v][x]['p'] = stat[f][v][x]['n']/stat[f][v]['n']
                        p = float(stat[f][v][x]['p'])
                        stat[f][v][x]['gini'] = 2*p*(1-p)
                    #update stat[f][v]['gini']
                    d1_p, d2_p= stat[f][v]['p'], 1-stat[f][v]['p']
                    prob = (class_vals.count(div_label)-stat[f][v][div_label]['n'])/(n_samples-stat[f][v]['n'])
                    d1_gini, d2_gini=stat[f][v][div_label]['gini'], 2*prob*(1-prob)
                    stat[f][v]['gini'] = d1_p*d1_gini + d2_p*d2_gini
            #选取最优特征,最优切分点, 最优叶子节点
            min_v_gini, bf_bv= 9527,[]
            for i in range(len(feat_list)):
                f = feat_list[i]    #visit every feature
                for v in set([e[i] for e in samples]):  #visit every value of feature
                    if min_v_gini > stat[f][v]['gini']:
                        min_v_gini, bf_bv= stat[f][v]['gini'],[(f,v)]
                    elif min_v_gini == stat[f][v]['gini']:
                        bf_bv.append((f,v))
            min_c_gini, bf, bv, bc= 9527,None,None,None #best
            for (f,v) in bf_bv: #存在多个相等gini的特征时,需要比较更细的条件进行筛选出一个最优特征
                for c in class_set:
                    if min_c_gini > stat[f][v][c]['gini']:
                        min_c_gini = stat[f][v][c]['gini']
                        bf, bv, bc= f, v, c
                    elif min_c_gini == stat[f][v][c]['gini']:
                        if stat[f][v][c]['p'] > stat[bf][bv][bc]['p']:
                            bf,bv,bc = f,v,c
            #找最优特征的次优分切点
            min_c_gini, better_v = 9527,None#better value
            bf_v_set = set([e[feat_list.index(bf)] for e in samples])
            bf_v_set.remove(bv)
            for v in bf_v_set: #存在多个相等gini的特征时,需要比较更细的条件进行筛选出一个最优特征
                if min_c_gini > stat[bf][v]['gini']:
                    min_c_gini, better_v = stat[bf][v]['gini'], v
            #找最优特征的次优分切点的最优叶节点
            min_c_gini, better_c = 9527, None
            for c in class_set:
                if min_c_gini > stat[bf][better_v][c]['gini']:
                    min_c_gini, better_c= stat[bf][better_v][c]['gini'], c
                elif min_c_gini == stat[bf][better_v][c]['gini']:
                    if stat[bf][better_v][c]['p'] > stat[bf][better_v][better_c]['p']:
                        better_c = c
            return bf, bv, bc, better_v, better_c, stat
    
        def create_tree(self):
            if len(self.feat_list) < self.max_n_feats:
                return None
            #get current tree
            bf, bv, bc, better_v, better_c, stat = self.work(self.samples, 
                                                   self.feat_list, 
                                                   self.div_label, 
                                                   self.max_n_feats)
            root, rcond, rnode, lcond, lnode = bf, bv, bc, better_v, better_c
            print('better_c:', better_c)
            #get child tree, first to tailor samles
            tailor = CTailorSamples(self.samples,
                                    self.feat_list,
                                    self.feat_list.index(bf),
                                    bv)
            new_samples, new_feat_list= tailor.get_samples()
            
            cart = CCartTree(new_samples,
                             new_feat_list, 
                             self.div_label,
                             self.max_n_feats)
            child_node = cart.get_tree_dict()
            print('child_node',child_node)
            #update current tree left-child-tree
            if child_node != None and child_node != {}:
                lnode = child_node
            
            #current tree dict
            self.tree_dict = {}
            self.tree_dict[root] = {}  
            self.tree_dict[root][rcond] = rnode
            self.tree_dict[root][lcond] = lnode
            return self.get_tree_dict()
    
            
    #定义判断结点形状,其中boxstyle表示文本框类型,fc指的是注释框颜色的深度
    decisionNode = dict(boxstyle="round4", color='r', fc='0.9')
    #定义叶结点形状
    leafNode = dict(boxstyle="circle", color='m')
    #定义父节点指向子节点或叶子的箭头形状
    arrow_args = dict(arrowstyle="<-", color='g')
    def plot_node(node_txt, center_point, parent_point, node_style):
        ''' 内部函数,外部不要调用
        绘制父子节点,节点间的箭头,并填充箭头中间上的文本
        :param node_txt:文本内容
        :param center_point:文本中心点
        :param parent_point:指向文本中心的点
        '''
        createPlot.ax1.annotate(node_txt, 
                                xy=parent_point,
                                xycoords='axes fraction',
                                xytext=center_point,
                                textcoords='axes fraction',
                                va="center",
                                ha="center",
                                bbox=node_style,
                                arrowprops=arrow_args)
    
    def get_leafs_num(tree_dict):
        '''内部函数,外部不要调用
        获取叶节点的个数
        :param tree_dict:树的数据字典
        :return tree_dict的叶节点总个数
        '''
        #tree_dict的叶节点总数
        leafs_num = 0
        if len(tree_dict.keys()) == 0:
            print('input tree dict is void!!!!!')
            return 0
        #字典的第一个键,也就是树的第一个节点
        root = list(tree_dict.keys())[0]
        #这个键所对应的值,即该节点的所有子树。
        child_tree_dict =tree_dict[root]
        for key in child_tree_dict.keys():
            #检测子树是否字典型
            if type(child_tree_dict[key]).__name__=='dict':
                #子树是字典型,则当前树的叶节点数加上此子树的叶节点数
                leafs_num += get_leafs_num(child_tree_dict[key])
            else:
                #子树不是字典型,则当前树的叶节点数加1
                leafs_num += 1
        #返回tree_dict的叶节点总数
        return leafs_num
    
    def get_tree_max_depth(tree_dict):
        ''' 内部函数,外部不要调用
        求树的最深层数
        :param tree_dict:树的字典存储
        :return tree_dict的最深层数
        '''
        #tree_dict的最深层数
        max_depth = 0
        if len(tree_dict.keys()) == 0:
            print('input tree_dict is void!')
            return 0
        #树的根节点
        root = list(tree_dict.keys())[0]
        #当前树的所有子树的字典
        child_tree_dict = tree_dict[root]
        for key in child_tree_dict.keys():
            #树的当前分支的层数
            this_path_depth = 0
            #检测子树是否字典型
            if type(child_tree_dict[key]).__name__ == 'dict':
                #如果子树是字典型,则当前分支的层数需要加上子树的最深层数
                this_path_depth = 1 + get_tree_max_depth(child_tree_dict[key])
            else:
                #如果子树不是字典型,则是叶节点,则当前分支的层数为1
                this_path_depth = 1
            if this_path_depth > max_depth:
                max_depth = this_path_depth
        #返回tree_dict的最深层数
        return max_depth
    
    def plot_mid_text(center_point, parent_point, txt_str):
        '''内部函数,外部不要调用: 计算父节点和子节点的中间位置,并在父子节点间填充文本信息
        :param center_point:文本中心点
        :param parent_point:指向文本中心点的点
        '''
        x_mid = (parent_point[0] - center_point[0])/2.0 + center_point[0]
        y_mid = (parent_point[1] - center_point[1])/2.0 + center_point[1]
        createPlot.ax1.text(x_mid, y_mid, txt_str)
        return
    
    def plotTree(tree_dict, parent_point, node_txt):
        '''内部函数,外部不要调用:绘制树
        :param tree_dict:树
        :param parent_point:父节点位置
        :param node_txt:节点内容
        '''
        leafs_num = get_leafs_num(tree_dict)
        root = list(tree_dict.keys())[0]
        #plotTree.totalW表示树的深度
        center_point = (plotTree.xOff+(1.0+float(leafs_num))/2.0/plotTree.totalW,plotTree.yOff)
        #填充node_txt内容
        plot_mid_text(center_point, parent_point, node_txt)
        #绘制箭头上的内容
        plot_node(root, center_point, parent_point, decisionNode)
        #子树
        child_tree_dict = tree_dict[root]
        plotTree.yOff=plotTree.yOff-1.0/plotTree.totalD
        #因从上往下画,所以需要依次递减y的坐标值,plotTree.totalD表示存储树的深度
        for key in child_tree_dict.keys():
            if type(child_tree_dict[key]).__name__ == 'dict':
                plotTree(child_tree_dict[key],center_point,str(key))
            else:
                plotTree.xOff=plotTree.xOff+1.0/plotTree.totalW
                plot_node(child_tree_dict[key],
                          (plotTree.xOff,plotTree.yOff),
                          center_point,leafNode)
                plot_mid_text((plotTree.xOff,plotTree.yOff),center_point,str(key))
        #h绘制完所有子节点后,增加全局变量Y的偏移
        plotTree.yOff=plotTree.yOff+1.0/plotTree.totalD
        return
    
    def createPlot(tree_dict):
        '''唯一对外函数:绘制决策树图形
        :param tree_dict
        :return 无
        '''
        #设置绘图区域的背景色
        fig=plt.figure(1,facecolor='white')
        #清空绘图区域
        fig.clf()
        #定义横纵坐标轴,注意不要设置xticks和yticks的值!!!
        axprops = dict(xticks=[], yticks=[])
        createPlot.ax1=plt.subplot(111, frameon=False, **axprops)
        #由全局变量createPlot.ax1定义一个绘图区,111表示一行一列的第一个,frameon表示边框,**axprops不显示刻度
        plotTree.totalW=float(get_leafs_num(tree_dict))
        plotTree.totalD=float(get_tree_max_depth(tree_dict))
        if plotTree.totalW == 0:
            print('tree_dict is void~')
            return
        plotTree.xOff=-0.5/plotTree.totalW;
        plotTree.yOff=1.0;
        plotTree(tree_dict, (0.5,1.0), '')
        plt.show()
    
    def create_samples():  
        ''''' 
        提供训练样本集 
        每个example由多个特征值+1个分类标签值组成 
        比如第一个example=['youth', 'no', 'no', '1', 'refuse'],此样本的含义可以解读为: 
        如果一个人的条件是:youth age,no working, no house, 信誉值credit为1
        则此类人会被分类到refuse一类中,即在相亲中被拒绝(也可以理解为银行拒绝为此人贷款)
        每个example的特征值类型为: 
        ['age', 'working', 'house', 'credit'] 
        每个example的分类标签class_label取值范围为:'refuse'或者'agree' 
        '''  
        data_list = [['youth', 'no',  'no',   '1', 'refuse'],  
                     ['youth', 'no',  'no',   '2', 'refuse'],  
                     ['youth', 'yes', 'no',   '2', 'agree'],  
                     ['youth', 'yes', 'yes',  '1', 'agree'],  
                     ['youth', 'no',  'no',   '1', 'refuse'],  
                     ['mid',   'no',  'no',   '1', 'refuse'],  
                     ['mid',   'no',  'no',   '2', 'refuse'],  
                     ['mid',   'yes', 'yes',  '2', 'agree'],  
                     ['mid',   'no',  'yes',  '3', 'agree'],  
                     ['mid',   'no',  'yes',  '3', 'agree'],  
                     ['elder', 'no',  'yes',  '3', 'agree'],  
                     ['elder', 'no',  'yes',  '2', 'agree'],  
                     ['elder', 'yes', 'no',   '2', 'agree'],  
                     ['elder', 'yes', 'no',   '3', 'agree'],  
                     ['elder', 'no',  'no',   '1', 'refuse']]
        feat_list = ['age', 'working', 'house', 'credit']  
        return data_list, feat_list
    
    if __name__=='__main__':
        data_list, feat_list = create_samples()
        #由CART算法得到决策树字典
        cart = CCartTree(data_list, feat_list, 'agree', 3)
        tree_dict = cart.get_tree_dict()
        print_dict(tree_dict, 0, 'tree_dict')
        #绘制决策树
        createPlot(tree_dict)
        
        

    enjoy it ~

    (end)

    展开全文
  • 决策树算法是机器学习中的经典算法1.决策树(decision tree)决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。假设小明去看电影,影响看电影的外部...

    决策树算法是机器学习中的经典算法

    1.决策树(decision tree)

    决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。

    假设小明去看电影,影响看电影的外部因素有 时间 电影类型 评分 三个情况,目前已知的样本数据如下

    63517e8aa4bd

    根据以上样本数据,整理成tree形结构如下

    63517e8aa4bd

    2.决策树算法中熵的概念

    1948年香农提出了“信息熵(entropy)”的概念

    一条信息的信息量大小和它的不确定性有直接,信息量的度量就等于不确定性的多少,我们用bit(比特)来衡量信息量的多少

    信息熵的计算公式如下,以log2为底,取对数,然后把每一种情况相加,当每种情况下概率相等时,取最大值,为n/2 -1 ,即变量的不确定性越大,则信息熵也越大

    63517e8aa4bd

    3.决策树归纳算法

    策树归纳算法是J.Ross.Quinian在19世纪70年代提出的的ID3算法.

    上面小明看电影实例中,总的信息量(单位为bit)为

    63517e8aa4bd

    同理,我们可以计算不同电影类型的信息熵,结果为0.65bits

    63517e8aa4bd

    此处解释下为什么根节点从电影类型开始划分,判断应该用哪个类型划分节点,可以依据如下公式判定

    Gain(A) = info(D) - Info_A(D)

    即总的信息量减除以特定节点的信息获取量,如果此值越大,说明获取的信息量越多,据此可以作为根节点

    以type为节点的信息获取量:

    Gain(type) = 0.991 - 0.65 = 0.341 (bits)

    依次类推,也可以计算出以time 和 grade获取的信息量,在此不一一计算了。因为此处以type为节点获取的信息量最大,所以根节点以type区分

    其它算法

    c4.5: (Quinlan)

    cart: Classification and Regression Trees (L.Breiman, J.Friedman, R.Olshen, C.Stone)

    以上两个算法c4.5和cart以及前面介绍的entropy都是贪心算法,主要区别在于属性的度量方法不同.

    tips

    决策树算法,直观,便于理解,试用于小规模的数据,对连续型变量处理不好,如果要处理,需要做到离散化。如果类型分得太细,可能会造成train较好,但是predict不好,为避免此种情况的overfitting,一般采取减枝

    代码实现

    本文以python为例,讲解代码的实现,本文会用到机器学习中常用的python库sklearn

    下面直接看代码

    其中用到了sklearn库中的DictVectorizer(转换成sklearn所能接受的类型用), csv(处理csv格式文件用), preprocessing(预处理数据,只能是数值类型),tree(决策树), StringIO(sklearn中的IO处理)

    from sklearn.feature_extraction import DictVectorizer

    import csv

    from sklearn import preprocessing

    from sklearn import tree

    from sklearn.externals.six import StringIO

    接下来,首先读取本读的csv数据,数据样本如第一张图片

    allFilmsData = open(r'/Users/max/Desktop/seeFilm.csv', 'rb')

    reader = csv.reader(allFilmsData)

    headers = reader.next()

    接着,我们对数据进行处理

    # 特征数组

    featureList = []

    # 标签数组

    labelList = []

    for row in reader:

    labelList.append(row[len(row) - 1])

    rowDict = {}

    for i in range(1, len(row) - 1):

    rowDict[headers[i]] = row[i]

    featureList.append(rowDict)

    # vetoarize feature

    vec = DictVectorizer()

    #DictVectorizer实例化

    dummyX = vec.fit_transform(featureList).toarray()

    #转化成dummy viable格式的

    通过以上转化,得到的数据结构如下

    dumyX:[

    [ 1. 0. 0. 0. 1. 0. 0. 1. 0.]

    [ 0. 0. 1. 1. 0. 0. 0. 0. 1.]

    [ 0. 0. 1. 1. 0. 0. 1. 0. 0.]

    [ 1. 0. 0. 1. 0. 1. 0. 0. 0.]

    [ 1. 0. 0. 0. 1. 0. 0. 0. 1.]

    [ 0. 1. 0. 1. 0. 0. 1. 0. 0.]

    [ 0. 1. 0. 0. 1. 0. 0. 0. 1.]

    [ 1. 0. 0. 0. 1. 0. 1. 0. 0.]

    [ 0. 0. 1. 1. 0. 0. 0. 1. 0.]

    ]

    同时,我们可以查看feature_names和labelList

    feature_names格式如下:

    ['grade=high', 'grade=low', 'grade=middle', 'time=weekend', 'time=workday_night', 'type=art', 'type=crime', 'type=love', 'type=science_fiction']

    labelList格式如下:

    labelList:['see', 'no', 'see', 'see', 'no', 'no', 'no', 'see', 'see']

    把labelList转化,代码如下

    # vectorize class labels

    lb = preprocessing.LabelBinarizer()

    dummyY = lb.fit_transform(labelList)

    print("dummy:" + str(dummyY))

    接下来,我们可以查看树结构

    clf = tree.DecisionTreeClassifier(criterion='entropy')

    '''

    上述采用的信息熵的差作为度量标准,即ID3

    如果此处不传,默认采用的是gini,即是cart算法

    '''

    clf = clf.fit(dummyX, dummyY)

    print("clf:" + str(clf))

    with open("/Users/max/Desktop/allFilmInfoGainOri.dot", 'w') as f:

    f = tree.export_graphviz(clf, feature_names=vec.get_feature_names(), out_file=f)

    我们把上面结果存储为allFilmInfoGainOri.dot的文件,可以看到文档信息如下,打开本地文件,可以看到文件结构如下

    63517e8aa4bd

    当然为了更加直观的查看以上部分数据结构,我们可以用Graphviz工具转换成树形结构的形式便于阅读,转换后的属性结构如下

    63517e8aa4bd

    最后,我们用代码预测

    例如:我们修改第一行的数据,预测代码如下

    oneRowX = dummyX[0, :]

    newRowX = oneRowX

    newRowX[0] = 0

    newRowX[7] = 1

    ['grade=high', 'grade=low', 'grade=middle', 'time=weekend', 'time=workday_night', 'type=art', 'type=crime', 'type=love', 'type=science_fiction']

    labelList:['see', 'no', 'see', 'see', 'no', 'no', 'no', 'see', 'see']

    newRowX[0] = 0, 表示评分高为0

    newRowX[7] = 1, 表示是love类型电影

    predictedY = clf.predict([newRowX])

    以上代码执行后,我们会得到predictedY为[1], 即说明此中情况下,小明会去看电影

    展开全文
  • 决策树之ID3算法及其Python实现,具体内容如下主要内容决策树背景知识决策树一般构建过程ID3算法分裂属性的选择ID3算法流程及其优缺点分析ID3算法Python代码实现1. 决策树背景知识决策树是数据挖掘中最重要且最常用...

    决策树之ID3算法及其Python实现,具体内容如下

    主要内容

    决策树背景知识

    决策树一般构建过程

    ID3算法分裂属性的选择

    ID3算法流程及其优缺点分析

    ID3算法Python代码实现

    1. 决策树背景知识

    决策树是数据挖掘中最重要且最常用的方法之一,主要应用于数据挖掘中的分类和预测。决策树是知识的一种呈现方式,决策树中从顶点到每个结点的路径都是一条分类规则。决策树算法最先基于信息论发展起来,经过几十年发展,目前常用的算法有:ID3、C4.5、CART算法等。

    2. 决策树一般构建过程

    构建决策树是一个自顶向下的过程。树的生长过程是一个不断把数据进行切分细分的过程,每一次切分都会产生一个数据子集对应的节点。从包含所有数据的根节点开始,根据选取分裂属性的属性值把训练集划分成不同的数据子集,生成由每个训练数据子集对应新的非叶子节点。对生成的非叶子节点再重复以上过程,直到满足特定的终止条件,停止对数据子集划分,生成数据子集对应的叶子节点,即所需类别。测试集在决策树构建完成后检验其性能。如果性能不达标,我们需要对决策树算法进行改善,直到达到预期的性能指标。

    注:分裂属性的选取是决策树生产过程中的关键,它决定了生成的决策树的性能、结构。分裂属性选择的评判标准是决策树算法之间的根本区别。

    3. ID3算法分裂属性的选择——信息增益

    属性的选择是决策树算法中的核心。是对决策树的结构、性能起到决定性的作用。ID3算法基于信息增益的分裂属性选择。基于信息增益的属性选择是指以信息熵的下降速度作为选择属性的方法。它以的信息论为基础,选择具有最高信息增益的属性作为当前节点的分裂属性。选择该属性作为分裂属性后,使得分裂后的样本的信息量最大,不确定性最小,即熵最小。

    信息增益的定义为变化前后熵的差值,而熵的定义为信息的期望值,因此在了解熵和信息增益之前,我们需要了解信息的定义。

    信息:分类标签xi 在样本集 S 中出现的频率记为 p(xi),则 xi 的信息定义为:−log2p(xi) 。

    分裂之前样本集的熵:E(S)=−∑Ni=1p(xi)log2p(xi),其中 N 为分类标签的个数。

    通过属性A分裂之后样本集的熵:EA(S)=−∑mj=1|Sj||S|E(Sj),其中 m 代表原始样本集通过属性A的属性值划分为 m 个子样本集,|Sj| 表示第j个子样本集中样本数量,|S| 表示分裂之前数据集中样本总数量。

    通过属性A分裂之后样本集的信息增益:InfoGain(S,A)=E(S)−EA(S)

    注:分裂属性的选择标准为:分裂前后信息增益越大越好,即分裂后的熵越小越好。

    4. ID3算法

    ID3算法是一种基于信息增益属性选择的决策树学习方法。核心思想是:通过计算属性的信息增益来选择决策树各级节点上的分裂属性,使得在每一个非叶子节点进行测试时,获得关于被测试样本最大的类别信息。基本方法是:计算所有的属性,选择信息增益最大的属性分裂产生决策树节点,基于该属性的不同属性值建立各分支,再对各分支的子集递归调用该方法建立子节点的分支,直到所有子集仅包括同一类别或没有可分裂的属性为止。由此得到一棵决策树,可用来对新样本数据进行分类。

    ID3算法流程:

    (1) 创建一个初始节点。如果该节点中的样本都在同一类别,则算法终止,把该节点标记为叶节点,并用该类别标记。

    (2) 否则,依据算法选取信息增益最大的属性,该属性作为该节点的分裂属性。

    (3) 对该分裂属性中的每一个值,延伸相应的一个分支,并依据属性值划分样本。

    (4) 使用同样的过程,自顶向下的递归,直到满足下面三个条件中的一个时就停止递归。

    A、待分裂节点的所有样本同属于一类。

    B、训练样本集中所有样本均完成分类。

    C、所有属性均被作为分裂属性执行一次。若此时,叶子结点中仍有属于不同类别的样本时,选取叶子结点中包含样本最多的类别,作为该叶子结点的分类。

    ID3算法优缺点分析

    优点:构建决策树的速度比较快,算法实现简单,生成的规则容易理解。

    缺点:在属性选择时,倾向于选择那些拥有多个属性值的属性作为分裂属性,而这些属性不一定是最佳分裂属性;不能处理属性值连续的属性;无修剪过程,无法对决策树进行优化,生成的决策树可能存在过度拟合的情况。

    5. ID3算法Python代码实现

    # -*- coding: utf-8 -*-

    __author__ = 'zhihua_oba'

    import operator

    from numpy import *

    from math import log

    #文件读取

    def file2matrix(filename, attribute_num): #传入参数:文件名,属性个数

    fr = open(filename)

    arrayOLines = fr.readlines()

    numberOfLines = len(arrayOLines) #统计数据集行数(样本个数)

    dataMat = zeros((numberOfLines, attribute_num))

    classLabelVector = [] #分类标签

    index = 0

    for line in arrayOLines:

    line = line.strip() #strip() 删除字符串中的'\n'

    listFromLine = line.split() #将一个字符串分裂成多个字符串组成的列表,不带参数时以空格进行分割,当代参数时,以该参数进行分割

    dataMat[index, : ] = listFromLine[0:attribute_num] #读取数据对象属性值

    classLabelVector.append(listFromLine[-1]) #读取分类信息

    index += 1

    dataSet = [] #数组转化成列表

    index = 0

    for index in range(0, numberOfLines):

    temp = list(dataMat[index, :])

    temp.append(classLabelVector[index])

    dataSet.append(temp)

    return dataSet

    #划分数据集

    def splitDataSet(dataSet, axis, value):

    retDataSet = []

    for featvec in dataSet: #每行

    if featvec[axis] == value: #每行中第axis个元素和value相等 #删除对应的元素,并将此行,加入到rerDataSet

    reducedFeatVec = featvec[:axis]

    reducedFeatVec.extend(featvec[axis+1:])

    retDataSet.append(reducedFeatVec)

    return retDataSet

    #计算香农熵 #计算数据集的香农熵 == 计算数据集类标签的香农熵

    def calcShannonEnt(dataSet):

    numEntries = len(dataSet) #数据集样本点个数

    labelCounts = {} #类标签

    for featVec in dataSet: #统计数据集类标签的个数,字典形式

    currentLabel = featVec[-1]

    if currentLabel not in labelCounts.keys():

    labelCounts[currentLabel] = 0

    labelCounts[currentLabel] += 1

    shannonEnt = 0.0

    for key in labelCounts:

    prob = float(labelCounts[key])/numEntries

    shannonEnt -= prob * log(prob, 2)

    return shannonEnt

    #根据香农熵,选择最优的划分方式 #根据某一属性划分后,类标签香农熵越低,效果越好

    def chooseBestFeatureToSplit(dataSet):

    baseEntropy = calcShannonEnt(dataSet) #计算数据集的香农熵

    numFeatures = len(dataSet[0])-1

    bestInfoGain = 0.0 #最大信息增益

    bestFeature = 0 #最优特征

    for i in range(0, numFeatures):

    featList = [example[i] for example in dataSet] #所有子列表(每行)的第i个元素,组成一个新的列表

    uniqueVals = set(featList)

    newEntorpy = 0.0

    for value in uniqueVals: #数据集根据第i个属性进行划分,计算划分后数据集的香农熵

    subDataSet = splitDataSet(dataSet, i, value)

    prob = len(subDataSet)/float(len(dataSet))

    newEntorpy += prob*calcShannonEnt(subDataSet)

    infoGain = baseEntropy-newEntorpy #划分后的数据集,香农熵越小越好,即信息增益越大越好

    if(infoGain > bestInfoGain):

    bestInfoGain = infoGain

    bestFeature = i

    return bestFeature

    #如果数据集已经处理了所有属性,但叶子结点中类标签依然不是唯一的,此时需要决定如何定义该叶子结点。这种情况下,采用多数表决方法,对该叶子结点进行分类

    def majorityCnt(classList): #传入参数:叶子结点中的类标签

    classCount = {}

    for vote in classList:

    if vote not in classCount.keys():

    classCount[vote] = 0

    classCount[vote] += 1

    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)

    return sortedClassCount[0][0]

    #创建树

    def createTree(dataSet, labels): #传入参数:数据集,属性标签(属性标签作用:在输出结果时,决策树的构建更加清晰)

    classList = [example[-1] for example in dataSet] #数据集样本的类标签

    if classList.count(classList[0]) == len(classList): #如果数据集样本属于同一类,说明该叶子结点划分完毕

    return classList[0]

    if len(dataSet[0]) == 1: #如果数据集样本只有一列(该列是类标签),说明所有属性都划分完毕,则根据多数表决方法,对该叶子结点进行分类

    return majorityCnt(classList)

    bestFeat = chooseBestFeatureToSplit(dataSet) #根据香农熵,选择最优的划分方式

    bestFeatLabel = labels[bestFeat] #记录该属性标签

    myTree = {bestFeatLabel:{}} #树

    del(labels[bestFeat]) #在属性标签中删除该属性

    #根据最优属性构建树

    featValues = [example[bestFeat] for example in dataSet]

    uniqueVals = set(featValues)

    for value in uniqueVals:

    subLabels = labels[:]

    subDataSet = splitDataSet(dataSet, bestFeat, value)

    myTree[bestFeatLabel][value] = createTree(subDataSet, subLabels)

    return myTree

    #测试算法:使用决策树,对待分类样本进行分类

    def classify(inputTree, featLabels, testVec): #传入参数:决策树,属性标签,待分类样本

    firstStr = inputTree.keys()[0] #树根代表的属性

    secondDict = inputTree[firstStr]

    featIndex = featLabels.index(firstStr) #树根代表的属性,所在属性标签中的位置,即第几个属性

    for key in secondDict.keys():

    if testVec[featIndex] == key:

    if type(secondDict[key]).__name__ == 'dict':

    classLabel = classify(secondDict[key], featLabels, testVec)

    else:

    classLabel = secondDict[key]

    return classLabel

    def main():

    dataSet = file2matrix('test_sample.txt', 4)

    labels = ['attr01', 'attr02', 'attr03', 'attr04']

    labelsForCreateTree = labels[:]

    Tree = createTree(dataSet, labelsForCreateTree )

    testvec = [2, 3, 2, 3]

    print classify(Tree, labels, testvec)

    if __name__ == '__main__':

    main()

    以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

    展开全文
  • 决策树优点:- 计算复杂度不高,易于理解和解释,甚至比线性回归更直观;- 与人类做决策思考的思维习惯契合;- 模型可以通过树的形式进行可视化展示;- 可以直接处理非数值型数据,不需要进行哑变量的转化,甚至可以...
  • 决策树算法Python实现

    万次阅读 多人点赞 2018-08-09 16:39:25
    1 什么是决策树 决策树(Decision Tree)是一种基本的分类与回归方法,本文主要讨论分类决策树决策树模型呈树形结构,在分类问题中,表示基于特征对数据进行分类的过程。它可以认为是if-then规则的集合。每个内部...
  • 1. 前言本文主要讲解CART决策树代码实现的细节,对于想了解决策树原理的同学建议可以去观看台大林轩田教授的视频,他对于决策树以及接下来要利用决策树生成的随机森林算法都讲解的非常好,下面附上链接。...
  • 本文是周志华老师的《机器学习》一书中第4章...本文主要是不进行剪枝的CART决策树的实现,预剪枝与后剪枝的CART决策树实现分别可见Python编程实现预剪枝的CART决策树Python编程实现后剪枝的CART决策树。如果发现文...
  • 主要介绍了决策树剪枝算法python实现方法,结合实例形式较为详细的分析了决策树剪枝算法的概念、原理并结合实例形式分析了Python相关实现技巧,需要的朋友可以参考下
  • 2019独角兽企业重金招聘Python工程师标准>>> ...
  • 决策树CART算法原理及python实现

    万次阅读 2017-05-30 15:10:12
    机器学习,决策树CARTpython实现
  • Cart(Classification and regression tree)分类与回归树,是一种可以用来分类或者回归(属性可以是连续值,标签必须离散)的决策树(二叉树)。对回归树使用平方误差最小化准则,对分类树使用基尼系数最小化准则。该...
  • 机器学习:决策树cart算法构建回归树
  • 先说明一下在看《统计学习方法》Cart回归的时候懵懵的,也没又例子。然后发现《机器学习实战》P162有讲到这个,仔细看了一下。 所以这下面是《机器学习实战》的代码,但书上没有什么原理,如果不太懂原理的话,会...
  • python 实现CART算法决策树

    千次阅读 2019-04-28 20:32:52
    有用请点赞,没用请差评。 欢迎分享本文,转载请保留出处。 本次代码是基于上一节决策树ID3\...# Decision tree by cart决策树cart算法,算法参考李航《统计学习方法》P71 #author:Tomator import numpy a...
  • CART算法引言1、概述2、CART算法2.1 CART生成2.1.1 回归的生成2.1.2 分类的生成2.2 CART剪枝2.2.1 剪枝,形成一个子树序列2.2.2 在剪枝得到的子树序列T0,T1,T2,T3......TnT_0,T_1,T_2,T_3......T_nT0​,T1​,T2...
  • 决策树算法python实现

    万次阅读 多人点赞 2017-06-13 11:48:21
    1 什么是决策树 决策树(Decision Tree)是一种基本的分类与回归方法,本文主要讨论分类决策树决策树模型呈树形结构,在分类问题中,表示基于特征对数据进行分类的过程。它可以认为是if-then规则的集合。每个内部...
  • 和之前介绍的ID3和C4.5一样,CART算法同样是决策树模型的一种经典的实现。决策树这个模型一共有三种实现方式,前面我们已经介绍了ID3和C4.5两种,今天刚好补齐这最后一种。 算法特点 CART称为分类回归树,从名字上...
  • 决策树算法Python实现

    2020-07-14 11:29:49
    转载请注明作者和出处: http://blog.csdn.net/c406495762 运行平台: Windows Python版本: Python3.x IDE...
  • 1.CART生成 CART假设决策树是二叉树,内部结点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右...CART算法由以下两步组成: 决策树生成:基于训练数据集生成决策树,生成的决策树要尽量大; 决...
  • 首先我们学习经典而有效的分类算法决策树分类算法。 1、决策树算法 决策树用树形结构对样本的属性进行分类,是最直观的分类算法,而且也可以用于回归。不过对于一些特殊的逻辑分类会有困难。典型的如异或(XOR)...
  • 决策树算法是一类算法的集合,决策树顾名思义是在一棵树上进行决策的方法,称之为决策树算法决策树首先是一棵树,树的每一个节点表示对一个特征的判断,每一个叶子节点表示一种判断的结果,下面的例子生动地解释了...
  • 决策树CART分类算法

    2020-04-21 15:40:25
    决策树算法可以用作分类回归,两者差异在于构造树时节点分裂规则的不同。分类算法用Gini系数分裂,回归则是计算方差。 决策树分类: 假设存在数据集(X, Y),Y包含0和1两中标签 Num X0 ...
  • 本文实例讲述了决策树剪枝算法python实现方法。分享给大家供大家参考,具体如下: 决策树是一种依托决策而建立起来的一种树。在机器学习中,决策树是一种预测模型,代表的是一种对象属性与对象值之间的一种映射...
  • 决策树的原理决策树是属于机器学习监督学习分类算法中比较简单的一种,决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值...
  • 决策树分为分类树和回归树两种,分类树对离散变量做决策树,回归树对连续变量做决策树,分类树是从ID3算法开始,改进成C4.5,随后又出现了cart算法cart算法可以生成分类树,也可以生成回归树,每个决策树之所以...
  • 机器学习笔记(4)——ID3决策树算法及其Python实现

    万次阅读 多人点赞 2018-09-27 16:07:37
    决策树是一种基于树结构来进行决策...最经典的决策树算法有ID3、C4.5、CART,其中ID3算法是最早被提出的,它可以处理离散属性样本的分类,C4.5和CART算法则可以处理更加复杂的分类问题,本文重点介绍ID3算法。 举个...
  • 决策树的核心算法就是对可能的决策树空间进行自上而下的贪心搜索。特征选择,怎么选特征:熵的解释:信息论中对熵的解释就是熵是对S任一成员的分类信息进行编码所需的最少的bit数量。如果\(p\)是1,那么接收器知道是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,322
精华内容 2,128
关键字:

决策树cart算法python

python 订阅