精华内容
下载资源
问答
  • 利用该概念在决策树构造过程中选择划分属性,设计了基于离散度的决策树构造算法DSD.DSD 算法可以解决WMR方法在实际应用中的局限性.在UCI 数据集上的实验表明,该方法构造的决策树精度与基于信息熵的方法相近,而时间...
  • 决策树构造过程

    千次阅读 2020-05-16 17:37:37
    决策树构造过程 决策树的基本概念 我们这里介绍一下一个比较简单的机器学习系统----决策树. 它的概念最容易理解, 因为人类的许多决策实际上就是一个决策树. 通常使用的分类回归树(class and regress tree)是一个...

    决策树构造过程

    决策树的基本概念

    我们这里介绍一下一个比较简单的机器学习系统----决策树. 它的概念最容易理解, 因为人类的许多决策实际上就是一个决策树.
    通常使用的分类回归树(class and regress tree)是一个二叉树。它的形式一般为:
    在这里插入图片描述
    每个方框代表一个节点. 每个非叶子节点有2个分支, 一个是判定True, 一个判定False. 分别走两个不同的分支. 叶子节点具有决策权. 任何一个输入从root出发, 总是会达到且唯一到达一个叶子节点. 这就是决策树的工作原理。
    决策树有两种节点: 中间节点和叶子节点。
    1.每个中间节点有4个参数:
    a) 判定函数。 是一个特征的取值。 当特征小于等于这个值得时候决策路径走左边, 当特征大于这个值得时候决策树走右边。
    b) 不纯度值(impurity value). 是当前节点的不纯度值. 关于不纯度值得意义后面会讲到. 他反应了当前节点的预测能力.
    c) 覆盖样本个数(n_samples). 是指参与此节点决策的样本个数. 父亲节点§和两个孩子节点(l,r)的样本个数的关系为: n_samples§ = n_samples(l) + n_samples® 覆盖样本个数越多, 说明判定函数越稳定. 实际上很容易看出来, 所有的叶子节点所对应的样本是总样本的一个划分.
    d) 节点取值(node value). 节点取值是一个数组. 数组的长度为类目个数. value = [997, 1154] 表示在2151个样本数中, 有997个属于class1, 1154属于class2. (这是分类树的意义, 会归数的取值规则后面会讲.)
    2.每个叶子节点有3个参数. 除了没有决策函数之外, 其他参数意义一样.

    不纯度函数(impurity function)

    决策树最重要的概念就是不纯函数(I)的概念. 当一个节点需要分割的时候, 实际上就是找到一个合适的特征的一个合适的取值作为阈值(thresh)进行分割. 那么问题来了, 怎么找到那个合适的特征的合适的取值呢? 主要的依据就是不纯度的变化(delta I). 首先我们给出不纯度函数的定义. 不纯度函数不是一个具体的函数, 它是满足一系列约束的函数的总称.
    根据输出实例的取值范围不同. 决策树有不同的种类. 如果输出实例是离散的, 那么决策树是一个分类树; 如果输出实例是连续的, 那么决策树是一个回归树.如果决策树是分类树. 那么输出空间定义为输出实例所有取值的集合. 这个集合是有限集合. 不失一般性, 使用{1,…,k}这可个取值. 不纯度函数(I)的定义为:
    在这里插入图片描述
    每一项其实就是属于类目c_i的概率, 记为p_i.
    如上公式可以看出不纯度函数的定义域是长度为k的向量, 向量每个数的取值为0~1, 且加和为1. 第i个数是特征矩阵中属于类别i的特征向量个数在整个样本个数(n_sample)的占比.且必须满足如下约束:
    1.当所有样本都属于同一类时候I取最小值. 即I在点(1,0,…,0),(0,1,…,0),…,(0,…,0,1)(1,0,…,0),(0,1,…,0), …, (0,…,0,1)(1,0,…,0),(0,1,…,0),…,(0,…,0,1)取最小值.
    2.当样本中每个类目下样本个数相同时I取最大值. 即I在点(1/k,…,1/k)取最大值.
    3.I对于定义域中每个取值p_1,…,p_k是对称的. 即I(p_1, p_2,…,p_k) = I(p_2,p_1,…,p_k)等. 从函数图像的角度理解, 就是函数一定是关于值坐标轴对称.
    4.I必须是绝度凸函数(strickly concave)即设p和p’(注意这里是一个长度为k的向量)为定义域下两个可能的取值. 那么
    在这里插入图片描述
    另外一个概念是不纯度变化(impurity reduction).
    我们回到决策树的结构, 每个父节点的两个子节点都是对父节点的划分. 那么如何评价这次划分呢? 于是我们引入了不纯度变化(impurity reduction)的概念. 我们看着公式来理解:
    考虑一般性我们设X_1,X_2…X_s是特征空间X的一个划分. 不纯度变化定义为:
    在这里插入图片描述
    这个公式很好理解,令s=2, 那么 X_1,X_2是对于原空间的一个划分. 按理说, 一个好的划分应该让不纯度变低, 以便让类目归属更加清晰. 公式后面一个累加和实际上就是这两个划分的不纯度的期望. 原不纯度减去划分后的不纯度的期望就是减少的不纯度的差值. 显然这个差值越大说明划分让子节点的纯度更"纯".
    另外, 需要强调一点, 根据不纯度函数的第三个约束, 即不纯度函数是定义域下的凸函数, 可以保证不纯度变化(impurity reduction) 大于等于0.当且仅当所有划分的样本数相当取0.
    可这么说,分类决策树节点划分的依据是找到一个特征的一个取值, 根据这个划分是的不纯度缩减量最大.
    下面我们介绍两个常用不纯度函数, 信息熵(info entropy)和基尼指数(gini index).

    信息熵(info entropy)

    首先介绍一下信息熵的概念. 我们把样本抽取过程当做一次随机试验A, 那么A有k个可能的输出A_1,A_2,…,A_k . 对应于k个分类. 那么A的信息熵定义为:
    在这里插入图片描述
    信息熵满足不纯度函数的定义. 所以我们定义:
    在这里插入图片描述

    把这个不纯度函数的定义带入到不纯度函数的公式中就可以得到相应的不纯度变化函数.
    在这里插入图片描述

    当不纯度函数为信息熵时不纯度变化又叫做信息增益(info gain).

    基尼指数(Gini Index)

    在这里插入图片描述
    这里强调一下不管是信息熵还是基尼指数, 他们都是不纯函数的一种表达, 不纯度变化的计算没有任何变化. 我们也可以自己撰写不纯度函数. 当k=2时候, 我们可以吧信息熵和基尼指数在二维坐标上图形画出来.
    在这里插入图片描述
    可以看出来这两个方法的区别很小. 实际过程中使用哪个方法作为不纯度函数效果不会有太大变化.
    我们现在了解了分类决策树在每次分割过程中如何评价分割的好坏, 一遍每次找到最佳分割点. 下面我们继续介绍回归数是如何定义不纯度函数的.

    回归树

    我们考虑一下会归树的构建过程. 当决策树只有一个节点的时候(root节点), 这个节点包含所有待测试样本. 如果我们需要选择一个数来预测函数的取值, 我们会选哪个? 由于我们没有任何多余的信息, 根据最大似然原则, 我们取所有样本取值的均值, 作为预测值.
    同样的道理随着决策树的建立, 所有的叶子节点是root节点的一个划分. 每个叶子节点都充当一个预测器的角色. 每个叶子节点的预测值是每个节点包含的样本取值的均值.
    那么对于回归决策树来说, 我们的任务是如何有效的划分让每个叶子节点更具有代表性. 如果让一个叶子节点更具有代表性, 我们直观的感受是这个节点的样本都趋同于均值(期望), 实际上就是方差较小. 这正是回归决策树不纯度函数的定义的理论依据.
    对于给定的训练集:
    在这里插入图片描述
    Y是连续变量. 考虑如何生成回归数.考虑一颗分类树, 每个叶子节点都对应一组概率值, 表示达到这个叶子节点的样本分到每个类目下的概率. 回归数基本结构和分类数一样, 不同的是每个叶子节点都表示对于到达这个叶子节点的样本的预测值(f(x)). f(x)等于这个叶子节点所有输入实例x_i对应的输出y_i的均值.有的叶子节点是对样本的一个划分R_1, R_2, …, R_m。
    在这里插入图片描述
    举例说明:
    在这里插入图片描述
    这颗回归树是对抛物线y=1-x^2 ( -1 <x< 1)模拟, 我们把原函数和预测函数花在同一个坐标系统.
    在这里插入图片描述
    我看观察图形可以看出, 回归树的特点是使用连续的折线来拟合曲线. 因为在每个叶子节点的取值是固定的, 而这颗回归树只有8个叶子节点.
    回归树的构建和分类数构建方法类似. 同样是需要找个一个划分, 使得不纯函数的缩减最大. 但是上面所介绍的不纯度函数是根据分类树定义的. 我们需要定义适应回归树的不纯度函数.
    在回归数中每个非叶子节点都是样本空间的一个子集的处理单元. 某个子集为X_m每个样本x有2个属性, 一个是实际输出y, 另一个是预测输出hat(y). 上面介绍过hat(y)是通过这个节点下所有y的均值算出来的, hat(y)是这个节点下所有y的期望. 反应的是总体上的拟合程度. 那么另外一个衡量集合稳定性的指标是方差, 它衡量hat(y)的代表性. 方差越小, 说明hat(y)越具有代表性. 因此我们可以定义一种不纯度函数, 就是这个节点下输出值的方差.
    在这里插入图片描述
    同样的带入不纯度变化的公式, 经过必要的化简我们得到:
    在这里插入图片描述
    值得注意的是, 公式中有2处对于当前节点来说是常数. 只有最小二乘有实际意义. 我们最大化不纯度变化, 就是最小化最小二乘函数.
    一般的教科书直接写成这样的公式:
    在这里插入图片描述
    这种方法又叫做"最小二乘法".

    小结

    上面介绍了决策树一个重要概念, 不纯函数. 不纯函数不仅是分类树的概念, 也是回归树的概念. 它们在形式上是统一的. 这点很有意义, 下面我们分析sklearn源码时候可以发现, 在设计决策树时候没有区分分类和回归树, 他们的不同都被封装在不纯函数的定义和计算节点的输出中了.

    决策树的构建

    上面一章介绍了分类和回归数在某个节点如何选择合适的特征和特征取值进行分裂. 这一章介绍决策树的构建方法, 即如何决定每步应该分裂的节点. 决策树的构建一般有2种方法:
    在这里插入图片描述
    不管是深度优先还是广度优先, 决策树算法都需要知道什么时候一个节点应该作为叶子节点. 如果没有约束决策树会一直建设下去知道节点只有一个类目(或者只有一个取值)才停止. 这样会导致决策树变得非常庞大, 引发过拟合问题.
    一般来说, 当如下条件其中之一满足的时候, 当前节点停止构建, 作为决策树的叶子节点.
    在这里插入图片描述
    这些控制条件可以控制数的规模, 因为根据不纯度变化的定义, 将所有的节点都放在唯一的叶子节点(这样每个叶子节点不纯度都是0)中不纯度变化最大. 这显然不是我们想要的.

    决策树的预测

    通过上述的说明, 决策树的预测就非常的简单了. 决策树中只有叶子节点有预测功能. 一个测试样本从root出发选择正确的路径, 一定会走到一个叶子节点. 叶子节点的值即为决策树对这个>样本的预测.
    如果是分类树. 叶子节点给出每个类别的占比. 概率最大的类别作为这个叶子节点的预测值. 其概率值为置信度.
    如果是回归树. 叶子节点的所有样本的输出的平均值作为这个测试样本的预测值.

    决策树的深度思考

    • 为什么决策树不需要数据归一化?
      一般来说, 机器学习都需要特征归一化, 目的是让特征之间的比较可以在同一个量纲上进行. 但是从数据构建过程来看, 不纯函数的计算和比较都是单特征的. 所有决策树不需要数据的归一>化. 但是有点需要注意, 从上文中对splitter的源码分析中可以看出, 决策树为了加速遍历没有真正遍历所有取值, 当特征的绝对值太小的时候会导致相邻值的间隔小于step, 因此尽量让特>征值不要太小(大于0.01比较保险).

    • 如何正确的选择不纯度函数?
      在gini函数小节中我们比较了gini和entroy在两元下的图形. 可以看到基本上没有区别. 有研究表明不同的不纯度函数对决策树产生的影响在2%以内[1].
      事实上很少有实际案例说明选择不纯度函数有显著的作用. 所以对于分类决策树选择gini, 对于回归选择MSE, 这样的默认配置可以满足绝大多数的需求.

    • 决策树哪些参数最重要?
      决策树的重要参数都是防止过拟合的. 我认为2个参数一定要设置:
      min_samples_leaf 这个sklearn的默认值是1. 经验上必须大于100, 如果一个节点都没有100个样本支持他的决策, 一般都被认为是过拟合.
      max_path 这个参数控制树的规模. 决策树是一个非常直观的机器学习方法. 一般我们都会把它的决策树结构打印出来观察, 如果深度太深对于我们的理解是有难度的. max_path也是防止>过拟合的有效手段.

    • 决策树为什么选择二叉树?
      我们回到不纯度函数变化公式的本身:
      在这里插入图片描述
      我们假设决策树每个节点可以有多个子树. 举个极端的例子, 某一个特征的所有取值都不相同, 那么可以找到一个划分方法(只要足够多的子树)可以让每个子树都有唯一的类别. 那么此时公>式的后半段为0. 这样不纯度变化取到最大值. 很明显这是一个算法上的偏见, 已经形成了过拟合。
      但是如果是二叉树就可以有效的避免这个问题. 他迫使特征有多个取值这样的优势无效.

    • 决策树的局限性有哪些?
      决策树的主要问题是容易形成过拟合. 如果我们通过各种剪枝和条件限制, 虽然可以避免过拟合, 但是会牺牲特征的有效性. 举个例子:
      样本有1w个测试记录
      feature的数量是1k个
      为了保证模型的有效性, 规定每个叶子节点包含的最少样本数为100
      在构造决策树的过程中我们可以断言节点个数不会超过100个, 这样很多feature不仅没有多次分裂, 甚至有些特征根本无法参与决策.

    展开全文
  • 利用该概念在决策树构造过程中选择划分属性,设计了基于离散度的决策树构造算法DSD. DSD算法可以解决WMR方法在实际应用中的局限性.在UCI数据集上的实验表明,该方法构造的决策树精度与基于信息熵的方法相近,而时间...
  • 基于欧氏距离的支持向量机决策树构造方法
  • 大多数决策树构造方法在每个节点上只检验单个属性,这种单变量决策树忽视了信息系统中广泛存在的属性间的关联作用,而且修剪时往往代价很大。针对以上两点,提出了一种基于主成分分析的多变量决策树构造方法,提取...
  • 文章给出稳态环境和置信bba的相关定义,运用置信bba来描述训练集的不确定类别,研究了基于置信bba的信念决策树构造,包括bba距离、属性选择方法、分类策略、终止规则及叶结构和树构造流程;最后,给出一个算例以阐述基于...
  • 将隐私保护引入决策树构造过程中。对于数据集的3种不同分布情况,即数据仅分布在单方、数据水平分布和数据垂直分布,分别讨论了在保护隐私的前提下构造决策树的方法。
  • 针对ID3算法构造决策树复杂、分类效率不高问题,基于粗糙集理论提出一种决策树构造算法。该算法采用加权分类粗糙度作为节点选择属性的启发函数,与信息增益相比,能全面地刻画属性分类的综合贡献能力,并且计算简单...
  • 应用粗糙集理论,提出了一种利用新的启发式函数构造决策树的方法。该方法以属性重要性评价指标作为信息熵函数,对条件属性进行选择,充分考虑了属性...实例表明该方法是正确有效的,而且明显优于传统的决策树构造方法。
  • 决策树构造实例 有如下表格的数据,是近两周(14天)的打球情况,特征为天气表现、温度、适度、是否有风4种不同的环境,目标:构造决策树。 问题:拿哪个特征作为根节点? 有4种划分方式如下: 判断依据:...

    决策树构造实例

    有如下表格的数据,是近两周(14天)的打球情况,特征为天气表现、温度、适度、是否有风4种不同的环境,目标:构造决策树。

    问题:拿哪个特征作为根节点?

    有4种划分方式如下:

    判断依据:信息增益。

    (1)求熵。

    在14天的数据中,有9天有打球,5天没有打球。所以此时的熵为:

    -\frac{9}{14}*log2\frac{9}{14} - \frac{5}{14}*log2\frac{5}{14} = 0.940

    (2)对四个特征进行分析(以下举例outlook特征):

    【1】outlook的特征:

     

    【2】根据统计的数据,outlook取值分别为sunny,overcast,rainy的概率分别是:5/14,4/14,5/14。

    【3】当outlook作为根节点时

    熵值计算:新的熵值为:5/14 * 0.971 + 4/14 * 0 + 5/14 * 0.971 = 0.693

    增益:0.940 - 0.693 = 0.247。

    【4】同样的方式可以计算出其他特征的信息增益,则选择最大的即可。相当于遍历了一遍特征,找出大哥,然后在其余中继续通过信息查找二哥。

     

    展开全文
  • Dtree-一种简单的纯Python决策树构造算法 概述 给定训练数据集,它可以构建决策树,以单批或增量地进行分类或回归。 它从CSV文件加载数据。 它期望CSV中的第一行是标题,每个元素都符合模式“ name:type:mode”。...
  • 第三章 决策树 3.1决策树构造

    千次阅读 2016-12-15 21:55:25
    决策树构造与应用。一些基本知识。

    http://cn.akinator.com/  “神灯猜名人”这个游戏很多人都玩过吧,问很多问题,然后逐步猜测你想的名人是谁。决策树的工作原理与这个类似,输入一系列数据,然后给出游戏答案。决策树也是最经常使用的数据挖掘算法。书上给了一个流程图决策树,很简单易懂。


    这里,椭圆形就是判断模块,方块就是终止模块。kNN 方法也可以完成分类任务,但是缺点是无法给出数据的内在含义。决策树的主要优势就在于数据形式容易理解。

    ==============================================================================

    决策树

    优点:计算复杂度不高,输出结果容易理解,对中间值缺失不敏感,可以处理不相关特征数据。

    缺点:可能会产生过度匹配问题。

    适用数据类型:数值型和标称型。


    伪代码:

    creatBranch():
    	if so return 类标签:
        else:
            寻找划分数据集的最好特征
            划分数据集
            创建分支节点
                for 每个划分的子集
                    调用函数 creatBranch() 并增加返回结果到分支节点中
            return 分支节点

    可以看出这是一个递归函数,在里面直接调用了自己。

    ==============================================================================

    决策树的一般流程:

    • 收集数据:可以使用任何方法
    • 准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化。
    • 分析数据:可以使用任何方法,构造树完成以后,我们应该检查图形是否符合预期。
    • 训练算法:构造树的数据结构。
    • 测试算法:使用经验树计算错误率。
    • 使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。

    一些决策树算法采用二分法,我们不用这种方法。我们可能会遇到更多的选项,比如四个,然后创立四个不同分支。本书将使用 ID3 算法划分数据集。


    ==============================================================================

    信息增益:

    划分数据集的大原则是:将无序的数据变得更加有序。

    在划分数据集之前之后信息发生的变化称为信息增益

    集合信息的度量方式称为香农熵或者简称为熵。熵定义为信息的期望值。公式略过不表。


    给一段代码,计算给定数据集的熵:

    # -*- coding:utf-8 -*-
    from math import log
    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) # 以 2 为底求对数
        return shannonEnt


    然后自己利用 createDataSet() 函数来得到35页表 3-1 的鱼类鉴定数据集。


    def createDataSet():
        dataSet = [[1,1,'yes'],
                    [1,1,'yes'],
                    [1,0,'no'],
                    [0,1,'no'],
                    [0,1,'no']]
        labels = ['no surfacing','flippers']
        return dataSet, labels

     最后来运行一下试试,我们建立一个 run_trees.py

    # -*- coding:utf-8 -*-
    # run_trees.py
    import trees
    myDat,labels = trees.createDataSet()
    print myDat
    print trees.calcShannonEnt(myDat)


    熵越多高,说明混合数据越多。这里添加一个 “maybe” 分类,表示可能为鱼类。

    测试:

    # -*- coding:utf-8 -*-
    import trees
    myDat,labels = trees.createDataSet()
    print myDat
    print trees.calcShannonEnt(myDat)
    print '*********************************'
    myDat[0][2] = 'maybe' # 0 指的是dataSet第一个[],-1 指[]里面倒数第一个元素
    print myDat
    print trees.calcShannonEnt(myDat)

    结果:


    ====================================================================================================

    3.1.2 划分数据集

    分类算法除了需要测量信息熵,还要划分数据集。

    我们对每个特征划分数据集的结果计算一次信息熵,然后判断按照哪个特征划分数据集是最好的方式。

    按照给定特征划分数据集,代码接着 trees.py 写:

    def splitDataSet(dataSet, axis, value):
        retDataSet= [] # 创建新的 list 对象
        for featVec in dataSet:
            if featVec[axis] == value:
                # 抽取
                reducedFeatVec = featVec[:axis]
                reducedFeatVec.extend(featVec[axis+1:])
                retDataSet.append(reducedFeatVec)
        return retDataSet

    注意 append() 和 extend() 的区别:

        >>>a = [1,2,3]
        >>>b = [4,5,6]
        >>>a.append(b)
        >>>a
        [1,2,3,[4,5,6]]


        >>>a = [1,2,3]
        >>>a.extend(b)
        >>>a
        [1,2,3,4,5,6]


    =============================================================================================

    现在可以在前面的简单样本数据上测试函数 splitDataSet()

    在 run_trees.py 里面加些代码:

    # -*- coding:utf-8 -*-
    # run_trees.py
    import trees
    myDat,labels = trees.createDataSet()
    print '>>> myDat'
    print myDat
    print '>>> trees.calcShannonEnt(myDat)'
    print trees.calcShannonEnt(myDat)
    print '*********************************'
    myDat[0][2] = 'maybe' # 0 指的是dataSet第一个[],-1 指[]里面倒数第一个元素
    print '>>> myDat'
    print myDat
    print '>>> trees.calcShannonEnt(myDat)'
    print trees.calcShannonEnt(myDat)
    print '*********************************'
    reload(trees)
    myDat,labels = trees.createDataSet()
    print '>>> myDat'
    print myDat
    print '>>> trees.splitDataSet(myDat,0,1)'
    print trees.splitDataSet(myDat,0,1)
    print '>>> trees.splitDataSet(myDat,0,0)'
    print trees.splitDataSet(myDat,0,0)
    结果如下:


    =======================================================================

    接下来我们要遍历整个数据集,循环计算香农熵和 splitDataSet() 函数,找到最好的特征划分方式。熵计算将会告诉我们如何划分数据集是最好的组织方式。

    加代码:

    def chooseBestFeatureToSplit(dataSet):
        numFeatures = len(dataSet[0]) - 1
        baseEntropy = calcShannonEnt(dataSet)
        bestInfoGain = 0.0; bestFeature = -1
        for i in range(numFeatures): # 遍历数据集中的所有特征
            # 创建唯一的分类标签列表
            featList = [example[i] for example in dataSet]
            uniqueVals = set(featList) # set 是一个集合
            newEntropy = 0.0
            for value in uniqueVals: # 遍历当前特征中的所有唯一属性值
                # 计算每种划分方式的信息熵
                subDataSet = splitDataSet(dataSet, i, value)
                prob = len(subDataSet)/float(len(dataSet))
                newEntropy += prob * calcShannonEnt(subDataSet) # 对所有唯一特征值得到的熵求和
            infoGain = baseEntropy - newEntropy
            if (infoGain > bestInfoGain):
                # 计算最好的收益
                bestInfoGain = infoGain
                bestFeature = i
        return bestFeature

    这段代码就是选取特征,划分数据集,计算得出最好的划分数据集的特征。

    在 run_trees.py 里面加些代码:

    print '*********************************'
    reload(trees)
    print '>>> myDat, labels = trees.createDataSet()'
    myDat, labels = trees.createDataSet()
    print '>>> trees.chooseBestFeatureToSplit(myDat)'
    print trees.chooseBestFeatureToSplit(myDat)
    print '>>> myDat'
    print myDat

    结果如下:


    代码的意义在于,告诉我们第0个特征(不浮出水面是否可以生存)是最好的用于划分数据集的特征。


    如果不相信这个结果,可以修改 calcShannonEnt(dataSet) 函数来测试不同特征分组的输出结果。

    ===============================================================================

    3.1.3 递归构建决策树

    从数据集构造决策树算法所需要的子功能模块,原理如下:得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分。第一次划分后,数据将被乡下传递到树分支的下一个节点,在这个节点上,我们可以再次划分数据。我们可以采用递归的原则处理数据集。

    在添加代码前,在 trees.py 顶部加上一行代码:

    import operator

    然后添加:

    def majorityCnt(classList):
        classCount = {} # 创建键值为 classList 中唯一值的数据字典
        for vote in classList:
            if vote not in classCount.keys():classCount[vote] = 0
            classCount[vote] += 1 # 储存了 classList 中每个类标签出现的频率
        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:
            # 为了保证每次调用函数 createTree() 时不改变原始列表类型,使用新变量 subLabels 代替原始列表
            subLabels = labels[:] # 这行代码复制了类标签,并将其存储在新列表变量 subLabels 中
            myTree[bestFeatLabel][value] = createTree(splitDataSet\
                                    (dataSet,bestFeat,value),subLabels)
        return myTree

    下一步开始创建树,使用 字典 类型来保存树的信息,当然也可以声明特殊的数据类型储存树,但是这里没有必要。

    当前数据集选取的最好特征存储在变量 bestFeat 中,得到列表包含的所有属性值。

    现在运行代码,在 run_trees.py 里面添加:

    print '*********************************'
    reload(trees)
    print '>>> myDat, labels = trees.createDataSet()'
    myDat, labels = trees.createDataSet()
    print '>>> myTree = trees.  createTree(myDat, labels)'
    myTree = trees.  createTree(myDat, labels)
    print '>>> myTree'
    print myTree
    结果:

    变量 myTree 包含了很多代表树结构信息的嵌套字典。



    展开全文
  • 一种基于分类规则树和信息熵的决策树构造方法,刘宁,,随着网络技术和硬件技术的发展,面临数据的海量增长,数据规模由于过于庞大不便于存储,这对传统分类算法提出了挑战。为此,文中
  • 行业分类-物理装置-基于列存储的决策树构造方法、装置、设备及存储介质.zip
  • 决策树构造方法详细过程

    千次阅读 2019-07-15 15:41:06
    决策树(decision tree)(一)——构造决策树方法 转载自:https://blog.csdn.net/u012328159/article/details/70184415 说明:这篇博客是看周志华老师的《机器学习》(西瓜书)的笔记总结,虽然自己写了很多总结...

    决策树(decision tree)(一)——构造决策树方法

     

    转载自:https://blog.csdn.net/u012328159/article/details/70184415 说明:这篇博客是看周志华老师的《机器学习》(西瓜书)的笔记总结,虽然自己写了很多总结性文字包括一些算法细节,但博客中仍有部分文字摘自周老师的《机器学习》书,仅供学习交流使用。转载博客务必注明出处和作者,谢谢。

    决策树系列博客:

     

            决策树算法起源于E.B.Hunt等人于1966年发表的论文“experiments in Induction”,但真正让决策树成为机器学习主流算法的还是Quinlan(罗斯.昆兰)大神(2011年获得了数据挖掘领域最高奖KDD创新奖),昆兰在1979年提出了ID3算法,掀起了决策树研究的高潮。现在最常用的决策树算法是C4.5是昆兰在1993年提出的。(关于为什么叫C4.5,还有个轶事:因为昆兰提出ID3后,掀起了决策树研究的高潮,然后ID4,ID5等名字就被占用了,因此昆兰只好让讲自己对ID3的改进叫做C4.0,C4.5是C4.0的改进)。现在有了商业应用新版本是C5.0link

    一、决策树的基本概念

            顾名思义,决策树就是一棵树,一颗决策树包含一个根节点、若干个内部结点和若干个叶结点;叶结点对应于决策结果,其他每个结点则对应于一个属性测试;每个结点包含的样本集合根据属性测试的结果被划分到子结点中;根结点包含样本全集,从根结点到每个叶子结点的路径对应了一个判定测试序列。下面直接上个图,让大家看下决策树是怎样决策的(以二元分类为例),图中红线表示给定一个样例(表中数据)决策树的决策过程:

     

    该图为原创

     

    二、如何生成决策树

    • 信息增益

            决策树学习的关键在于如何选择最优的划分属性,所谓的最优划分属性,对于二元分类而言,就是尽量使划分的样本属于同一类别,即“纯度”最高的属性。那么如何来度量特征(features)的纯度,这时候就要用到“信息熵(information entropy)”。先来看看信息熵的定义:假如当前样本集D中第k类样本所占的比例为 为类别的总数(对于二元分类来说,)。则样本集的信息熵为:

     

    的值越小,则D的纯度越高。(这个公式也决定了信息增益的一个缺点:即信息增益对可取值数目多的特征有偏好(即该属性能取得值越多,信息增益,越偏向这个),因为特征可取的值越多,会导致“纯度”越大,即ent(D)会很小,如果一个特征的离散个数与样本数相等,那么Ent(D)值会为0)。再来看一个概念信息增益(information gain),假定离散属性  有 个可能的取值,如果使用特征  来对数据集D进行划分,则会产生V个分支结点, 其中第v(小v)个结点包含了数据集D中所有在特征  上取值为 的样本总数,记为。因此可以根据上面信息熵的公式计算出信息熵,再考虑到不同的分支结点所包含的样本数量不同,给分支节点赋予权重,即样本数越多的分支节点的影响越大,因此,能够计算出特征  对样本集D进行划分所获得的“信息增益”:

           一般而言,信息增益越大,则表示使用特征  对数据集划分所获得的“纯度提升”越大。所以信息增益可以用于决策树划分属性的选择,其实就是选择信息增益最大的属性,ID3算法就是采用的信息增益来划分属性。

    下面来举个例子说明具体是怎样操作的,只贴公式没多大意义,还是有不利于大家理解。举例子用的数据集为:

        显然该数据集包含17个样本,类别为二元的,即。则,正例(类别为1的样本)占的比例为:,反例(类别为0的样本)占的比例为:。根据信息熵的公式能够计算出数据集D的信息熵为:

     

     

    从数据集中能够看出特征集为:{色泽、根蒂、敲声、纹理、脐部、触感}。下面我们来计算每个特征的信息增益。先看“色泽”,它有三个可能的离值:{青绿、乌黑、浅白},若使用“色泽”对数据集D进行划分,则可得到3个子集,分别为:(色泽=青绿)、(色泽=乌黑)、(色泽=浅白)。共包含6个样本{1,4,6,10,13,17},其中正例占,反例占包含6个样本{2,3,7,8,9,15},其中正例占,反例

    包含了5个样本{5,11,12,14,16},其中正例占,反例占。因此,可以计算出用“色泽”划分之后所获得的3个分支结点的信息熵为:

     

     

    因此,特征“色泽”的信息增益为:

     

    同理可以计算出其他特征的信息增益:

    比较发现,特征“纹理”的信息增益最大,于是它被选为划分属性。因此可得:

    第二步、继续对上图中每个分支进行划分,以上图中第一个分支结点{“纹理=清晰”}为例,对这个结点进行划分,设该结点的样本集 {1,2,3,4,5,6,8,10,15},共9个样本,可用特征集合为{色泽,根蒂,敲声,脐部,触感},因此基于  能够计算出各个特征的信息增益:

    比较发现,“根蒂”、“脐部”、“触感”这3个属性均取得了最大的信息增益,可以随机选择其中之一作为划分属性(不防选择“根蒂”)。因此可得:

     

    第三步,继续对上图中的每个分支结点递归的进行划分,以上图中的结点{“根蒂=蜷缩”}为例,设该结点的样本集为{1,2,3,4,5},共5个样本,但这5个样本的class label均为“好瓜”,因此当前结点包含的样本全部属于同一类别无需划分,将当前结点标记为C类(在这个例子中为“好瓜”)叶节点,递归返回。因此上图变为:

    第四步,接下来对上图中结点{“根蒂=稍蜷”}进行划分,该点的样本集为 {6,8,15},共有三个样本。可用特征集为{色泽,敲声,脐部,触感},同样可以基于 计算出各个特征的信息增益,计算过程如下(写的比较详细,方便大家弄懂):

    (注:该图片版权所有,转载或使用请注明作者(天泽28)和出处)

    不妨选择“色泽”属性作为划分属性,则可得到:

    继续递归的进行,看“色泽=青绿”这个节点,只包含一个样本,无需再划分了,直接把当前结点标记为叶节点,类别为当前样本的类别,即好瓜。递归返回。然后对递归的对“色泽=乌黑”这个节点进行划分,就不再累述了。说下“色泽=浅白”这个节点,等到递归的深度处理完“色泽=乌黑”分支后,返回来处理“色泽=浅白”这个节点,因为当前结点包含的样本集为空集,不能划分,对应的处理措施为:将其设置为叶节点,类别为设置为其父节点(根蒂=稍蜷)所含样本最多的类别,“根蒂=稍蜷”包含{6,8,15}三个样本,6,8为正样本,15为负样本,因此“色泽=浅白”结点的类别为正(好瓜)。最终,得到的决策树如下图所示:

    注:上图红色框起来的部分,是西瓜书印刷错误,上图已改正。周老师在他的勘误网站也有说明,详见勘误网站

     

    说了这么多,下面就来看看用决策树算法跑出来的效果,本人主要用weka的ID3算法(使用的信息增益),以供大家参看,后面还会放出自己实现的版本,后面再说。(之所以不要sklearn库里的决策树,是因为sklearn库里的决策树提供的是使用Gini指数优化后的CART,并不提供ID3和C4.5算法)。

    由于新版本weka里已经不再提供ID3算法了,只能下载另外的安装包,把下载方法也贴出来吧,打开weka的Tools->package manager在里面找到包simpleEducationalLearningSchemes安装即可。安装好后就可以把西瓜数据集2.0来测试了,不过要想在weka中构建模型,还要先把.txt格式转换为.arff格式,转换的代码以及转换好的数据集,详见github。另外simpleEducationalLearningSchemes提供的ID3并不像J48那样支持可视化,因此参考链接基于以前weka老版本写的可视化,但该代码在新版本中无法使用,我修改了下整合到ID3上了,现在可以支持可视化了,测试西瓜数据集,生成的可视化树如下,具体代码也放到了github上,有兴趣的可以看看。

     

     

     

    但信息增益有个缺点就是对可取数值多的属性有偏好,举个例子讲,还是考虑西瓜数据集,如果我们把“编号”这一列当做属性也考虑在内,那么可以计算出它的信息增益为0.998,远远大于其他的候选属性,因为“编号”有17个可取的数值,产生17个分支,每个分支结点仅包含一个样本,显然这些分支结点的纯度最大。但是,这样的决策树不具有任何泛化能力。还是拿西瓜数据集2.0来测试下,如果考虑编号这一属性,看看ID3算法会生成一颗什么样的决策树:

    显然是生成了一颗含有17个结点的树,这棵树没有任何的泛化能力,这也是ID3算法的一个缺点。另外补充一下ID3算法的详细情况:

    • Class for constructing anunpruned decision tree based on the ID3 algorithm. 
    • Can only deal with nominal attributes. No missing values allowed. 
    • Empty leaves may result in unclassified instances. For more information see: R. Quinlan (1986). Induction of decision trees. Machine Learning. 1(1):81-106.

    由于ID3算法的缺点,Quinlan后来又提出了对ID3算法的改进C4.5算法(在weka中为J48),C4.5使用了信息增益率来构造决策树,此外C4.5为了避免过拟合,还提供了剪枝的功能。C4.5还能够处理连续值与缺失值。剪枝与连续值和缺失值的处理在下一篇博客中再介绍。先来看看信息增益率:

    • 信息增益率

    信息增益比的定义为:

    其中:

     

     称为属性  的“固有值”,属性  的可能取值数目越多(即V越大),则的值通常会越大。例如还是对西瓜数据集,IV(触感)=0.874(v=2),IV(色泽)=1.580(V=3),IV(编号)=4.088(V=17)。但增益率也可能产生一个问题就是,对可取数值数目较少的属性有所偏好。因此,C4.5算法并不是直接选择使用增益率最大的候选划分属性,而是使用了一个启发式算法:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择信息增益率最高的。来看看C4.5在西瓜数据集上构造的决策树:

    来看下混淆矩阵(Confusion Matrix)

     

    有两个样本被误分类了。

    另外还可以用基尼指数来构造决策树,像CART就是用基尼指数来划分属性的,来看下基尼指数:

    • 基尼指数

            基尼指数(Gini index)也可以用于选择划分特征,像CART(classification and regression tree)决策树(分类和回归都可以用)就是使用基尼指数来选择划分特征。基尼值可表示为:

     

    注:上面这个公式的推导可以写一下:

    反应了从数据集D中随机抽取两个样本,其类别标记不一致的概率,因此, 越小,则数据集D的纯度越高。则属性  的基尼指数定义为:

     

    所以在候选属性集合中国,选择那个使得划分后基尼指数最小的属性作为最优划分属性。

    下面是用python的scikit-learn库中提供的CART在西瓜数据集上的测试效果:

    17个样本全部拿来当做训练集:

     

    拿出25%的样本当做测试集:

    欢迎大家留言交流讨论。

    展开全文
  • 转载 :目前基于符号处理的方法是解决分类规则提取问题...给出了具体的决策树构造算 法。同时为了提高神经网络所隐含关系的提取效果,提出了关系强化约束的概念并建立了具体的模型。实际应用结果证 明了算法的有效性。
  • 讨论了动态模糊决策树的属性算法,通过动态模糊二叉决策树的介绍,给出了动态模糊决策树中各结点以及各层对实例集划分之间的关系。由于划分格是对论域的划分,进一步定义了动态模糊划分格,给出了关于动态模糊决策树...
  • 构造决策树的过程中,分类属性选择的标准直接影响分类的效果。本文基于粗糙集的理论,提出了在核中应用分类贡献函数来选择分类属性的新方法。利用UCI提供的数据集对该算法和基于信息熵的算法C4.5,以及基于加权平均...
  • 决策树(decision tree)(一)——构造决策树方法

    万次阅读 多人点赞 2017-04-18 16:44:56
    决策树(decision tree) 说明:这篇博客是看周志华老师的《机器学习》(西瓜书)的笔记总结,博客中有大段文字摘自周老师的《机器学习》书,仅供学习交流使用。转载博客务必注明出处和作者,谢谢。 决策树算法起源...
  • 决策树构造 我的微信公众号: s406205391; 欢迎大家一起学习,一起进步!!! ​ 有一个二十个问题的小游戏,游戏规则很简单:参与游戏的一方在脑海了想某个事物,其他参与者向他提出问题,只允许提问20个问题,...
  • 决策树构造决策树(一)

    千次阅读 2018-12-19 19:50:14
    决策树时一种常用的数据挖掘算法,其优势在于数据形式非常容易理解,缺点在于很可能产生过度匹配的问题(即过拟合问题,如何解决过拟合问题待续.......)。决策树的一个重要任务就是为了理解数据中所蕴含的数据信息...
  • 决策树构造

    2016-11-21 10:40:31
    3.1、摘要  在前面两篇文章中,分别介绍和讨论了朴素贝叶斯分类与...相比贝叶斯算法,决策树的优势在于构造过程不需要任何领域知识或参数设置,因此在实际应用中,对于探测式的知识发现,决策树更加适用。
  • 决策树(Decision Tree)是一种基本的分类与回归方法。本文会讨论决策树中的分类树与回归树,后续文章会继续讨论决策树的Boosting和Bagging的相关方法。决策树由结点和有向边组成。结点有两种类型:内部结点和叶结点...
  • 决策树-离散连续值如何构造决策树

    千次阅读 2019-06-26 11:05:51
    决策树的详细说明:...决策树分为分类树和回归树两种,分类树对离散变量做决策树,回归树对连续变量做决策树。 2, 一棵决策树的生成过程主要分为以下3个部分: 特征选...
  • 决策树

    2019-05-14 20:11:17
    决策树 决策树基于二分类思想,类似于编程语言中的if-else,决策树通常会有两个阶段:构造和剪枝。...预剪枝是指在决策树构造时进行剪枝。在构造过程中对节点进行评估,如果对某个节点进行划分,在验证...
  • 机器学习——决策树

    2018-06-02 21:24:19
    决策树构造过程: 选择不同属性对决策树进行分裂(生长),让叶子节点中更纯 属性分裂-影响 属性类型: 属性字段类型: Norminal(类别型) Ordinal(有序型) Continiuous(连续型) 分叉数量: ...
  • 【摘要】本文简要介绍了数据挖极技术在犯罪分析上的应用和用算法构造决 策树的方法, 并结合一个涉嫌犯罪人员样本数据, 采用决策树分析方法进行了分类, 给出 了一个较为成功的挖掘思路和模式。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,552
精华内容 13,820
关键字:

决策树的构造