精华内容
下载资源
问答
  • 决策树算法

    2017-03-12 14:48:14
    决策树算法  决策树是一种基本的分类与回归算法,其实就是if-then的集合。  主要包括三个部分:  (1) 特征选择  (2) 决策树的生成  (3) 决策树的剪枝    决策树由结点和有向边组成。结点有两种类型...

                      决策树算法

      决策树是一种基本的分类与回归算法,其实就是if-then的集合。

      主要包括三个部分:

      (1)    特征选择

      (2)    决策树的生成

      (3)    决策树的剪枝

     

      决策树由结点和有向边组成。结点有两种类型:内部结点和叶子结点。内部结点表示一个特征或者属性。叶子结点表示一个类。决策树学习的损失函数通常是正则化的极大似然函数。

      常用的算法有ID3,C4.5,CART算法。

     

    ID3

      ID3算法只能适应于离散属性,不能用于连续属性。

      特征选择的方式是信息增益。 不确定性减少的程度

      信息增益=经验熵-经验条件熵。

      即g(D/A)=H(D)-H(D/A)

      迭代终止条件:

      (1)    所有的特征都用了,没有特征可以继续来进行特征选择

      (2)    当前特征集中的最大的信息增益小于我们设定的阈值。

      ID3算法使用了信息增益。信息增益的缺点是:对取值数目比较多的属性有偏好。一个特征的信息增益越大,表明属性对样本熵减少的能力越强,不确定性变成确定性的能力越强。用信息增益训练出来的决策树深度很浅的树。

     

    C4.5

      与ID3不同之处就是:特征选择使用的是信息增益比,同时可以对连续属性进行处理。

      1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足;

      2) 在树构造过程中进行剪枝;

      3) 能够完成对连续属性的离散化处理;

      4) 能够对不完整数据进行处理。

      连续属性的一般处理方式:

      将连续属性的属性值进行排序,如[x1,x2,x3....xn],将连续属性离散化,最简单的方式就是取相邻两个值的终点作为属性划分点,即[(x1+x2)/2, (x2+x3)/2....]。每次划分的时候对划分点进行遍历,选取最佳的划分点。


    CART

      回归树:损失函数:最小均方误差。

      回归树基本流程:

      (1)    选择最优变量与最优切分点。使得均方误差最小

      (2)    确定每个区域的输出值

      (3)    继续对划分的两个子区域调用(1)(2),直到满足停止条件。

      (4)    将输入空间划分成M个区域,生成决策树。


      分类树:分类树使用基尼指数选择最优特征,同时决定该特征的最优二值切分点。

      CART算法分类流程:

      输入:训练数据集,停止计算的条件

     (1)    计算现有特征对该数据集的基尼指数。

     (2)    选择基尼指数最下的特征及其对应的最好的切分点。

     (3)    递归调用(1)(2),直到满足停止条件

     (4)    生成CART决策树。

      算法停止计算的条件是:结点中样本个数小于预定阈值,或者样本集的基尼指数小于预定阈值,或者没有更多的特征。 如果此时该叶子结点的纯度还不是很高,只能使用多数表决法。

      CART剪枝算法基于代价复杂度思想:就是不断剪枝,构造出不同的子树序列,对不同的子树序列交叉验证,判断出好的子树序列。


    总结:

      决策树停止条件:

      (1)特征集合都用完了。

      (2)当前集合最大信息增益/信息增益比/基尼指数小于阈值。

      (3)当前节点中的样本数目已经小于限定的最小值。

      决策树的优缺点:

      相对于其他数据挖掘算法,决策树在以下几个方面拥有优势: 

      •    决策树易于理解和实现人们在通过解释后都有能力去理解决策树所表达的意义。

      •    对于决策树,数据的准备往往是简单或者是不必要的 . 其他的技术往往要求先把数据一般化,比如去掉多余的或者空白的属性。

      •    能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。

      •    在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

      •    对缺失值不敏感

          可以处理不相关特征数据

      •    效率高,决策树只需要一次构建,反复使用,每一次预测的最大计算次数不超过决策树的深度


    决策树的缺点

    1)连续性的字段比较难预测。

    2)对有时间顺序的数据,需要很多预处理的工作。

    3)当类别太多时,错误可能就会增加的比较快。

    4)一般的算法分类的时候,只是根据一个字段来分类。

    5)在处理特征关联性比较强的数据时表现得不是太好


    决策树的学习策略:正则化的极大似然估计

    决策树损失函数:对数似然损失


    决策树进行特征选择的三种方式:信息增益,信息增益比,基尼指数。分别用在不同的算法中,信息增益与信息增益比的联系与区别。






    展开全文
  • I . 决策树模型 II . 决策树模型 示例 III . 决策树算法列举 IV . 决策树算法 示例 V . 决策树算法性能要求 VI . 决策树模型创建 ( 递归创建决策树 ) VII . 决策树 树根属性 选择



    I . 决策树模型



    1 . 决策树 : 决策时基于 “树” 结构 , 这也是模拟人在进行决策时采用的策略 ;


    2 . 决策树组成 : 根节点 , 内部节点 , 叶子节点 , 这些节点都是数据的 属性 ( 特征 ) ;


    ① 根节点 : 最初始判定的属性 , 判定区域是全局的数据集 ;

    ② 内部节点 : 中间的判定属性 , 判定区域是符合某些特征的子数据集 ;

    ② 叶子节点 : 决策结果 , 位于决策树的最底层 , 每个叶子节点都是一个决策结果 ;


    3 . 决策树模型过程 :


    ① 训练过程 : 使用训练集数据确定决策时使用的属性 , 确定根节点 , 内部节点 , 叶子节点 的属性划分 , 训练决策树模型 ;

    ② 预测过程 : 从根节点特征开始 , 根据决策树中的判定序列依次从根节点向下判定 , 直到一个叶子节点 ;



    II . 决策树模型 示例



    1 . 需求场景 :


    ① 需求 : 电商网站为用户进行分类 , 目的是确定该用户是否有可能购买某件商品 , 然后为其推送指定商品的广告 ;

    ② 决策树使用 : 如何对用户进行分类 , 这里就用到了决策树模型 , 将用户分成不同的类别 ;


    2 . 数据集 : 决策过程中 , 根据每个节点所处理的数据集的特征 , 将其划分到不同的子节点中进行处理 ; 如数据集中是 100 个用户的信息 ;


    3 . 决策树构成 :


    ① 根节点决策 : 根节点 处理年龄特征 , 小于 30 岁的用户划分到一组 , 大于 30 岁的用户划分到另一组 ;

    ② 内部节点决策 : 然后在 小于 30 岁的用户中继续判定 , 学生划分成一组 , 非学生划分成一组 ;

    ③ 叶子节点决策结果 : 学生会买电脑 , 非学生不会买电脑 ;

    在这里插入图片描述



    III . 决策树算法列举



    1 . 常用的决策树算法 :


    ① CLS 算法 : 这是第一个决策树算法 , 1966 年提出 ;

    ② ID3 算法 : 该算法使决策树称为机器学习主流技术 , 1979 年提出 ;

    ③ C4.5 算法 : 最常用的决策树算法 ; 1993 年提出 ;

    ④ 区别 : 上述三个算法五个组件基本一致 , 唯一的区别是确定属性划分时的策略不同 , 即将哪个属性放在树根 , 将哪个属性放在内部节点上 , 内部节点的属性所在层级如何设置 ;


    2 . 属性划分策略 :


    ① ID3 算法属性划分策略 : ID3 使用信息增益策略 ;

    ② C4.5 算法属性划分策略 : C4.5 使用的是增益率策略 ;


    3 . CART 算法 : 既可以用于分类任务 ( 结果是离散值 ) , 也可以用于回归任务 ( 结果是连续值 ) ;


    4 . FR 算法 : 随机森林算法 ; 使用了数据挖掘 , 机器学习中的集成思想 ; 有很多差的分类器 , 准确率都很低 , 但是多个分类器集成起来 , 准确率就很高 ;



    IV . 决策树算法 示例



    1 . 需求场景 :


    ① 需求 : 电商网站为用户进行分类 , 目的是确定该用户是否有可能购买某件商品 , 然后为其推送指定商品的广告 ;

    ② 决策树使用 : 如何对用户进行分类 , 这里就用到了决策树模型 , 将用户分成不同的类别 , 买的一类 , 和不买的一类 ;


    2 . 模拟数据集 : 给出一组数据集 , 后面的所有计算都是基于该数据集进行的 ;

    需求 : 根据 年龄 , 收入水平 , 是否是学生 , 信用等级 , 预测该用户是否会购买商品 ;


    年龄 收入水平 是否是学生 信用等级 是否购买商品
    小于 30 岁 高收入 不是 一般 不会
    小于 30 岁 高收入 不是 很好 不会
    31 ~ 39 岁 高收入 不是 一般
    40 岁以上 中等收入 不是 一般
    40 岁以上 低收入 一般
    40 岁以上 低收入 很好 不会
    31 ~ 40 岁 低收入 不是 很好
    小于 30 岁 中等收入 不是 一般 不会
    小于 30 岁 低收入 一般
    40 岁以上 中等收入 一般
    小于 30 岁 中等收入 很好
    31 ~ 39 岁 中等收入 不是 很好
    31 ~ 39 岁 高收入 一般
    40 岁以上 中等收入 不是 很好 不会

    3 . 决策树模型 :

    建立模型 : 将上述数据集的 属性 ( 特征 ) 转换为树状的模型 ;

    确定树根 : 首先要确定哪个属性作为树根 , 这个选择是有一定要求的 , 不能随意指定一个任意的特征作为树根 ;


    4 . 决策树 属性划分 :

    属性划分策略 : 根据一定的策略 , 确定哪个属性作为树根 , 然后每个子树 , 在确定剩余的哪个属性作为子树的树根 , 这是递归问题 ;

    属性划分的算法性质 : 递归算法 ;

    如何决定树根属性 : 确定总树的树根 , 及每个子树的树根 , 要求根据数据的 属性 ( 特征 ) 进行的决策次数尽量能做到最少 ;

    在这里插入图片描述



    V . 决策树算法性能要求



    1 . 决策树的高度 :


    ① 决策树最大高度 : 决策属性的个数 ; ( 每个属性都要决策一次 , 才能预测出结果 )

    ② 决策时最小高度 : 1 ; ( 只需要决策一次 , 就可以预测出结果 )


    2 . 决策树性能 : 决策树越矮越好 , 即预测某特征 , 进行的决策次数越少越好 ;


    3 . 树根属性 : 越重要的属性 , 其越能将数据最大可能拆分开 , 将重要的属性放在树根 ;



    VI . 决策树模型创建 ( 递归创建决策树 )



    1 . 决策树模型创建 : 决策树模型创建的核心就是选择合适的树根 , 将重要的属性放在树根 , 然后子树中 , 继续选择子树中重要的属性放在子树的树根 , 依次递归 , 最终得到决策结果 ( 叶子节点 ) ;


    2 . 决策树创建算法 ( 递归 ) : 使用递归算法 , 递归算法分为递归操作 和 递归停止条件 ;


    3 . 递归操作 : 每个步骤先选择属性 , 选择好属性后 , 根据 总树 ( 子树 ) 的树根属性划分训练集 ;


    ① 选择属性 : 递归由上到下决定每一个节点的属性 , 依次递归构造决策树 ;

    ② 数据集划分 : 开始决策时 , 所有的数据都在树根 , 由树根属性来划分数据集 ;

    ③ 属性离散化 : 如果属性的值是连续值 , 需要将连续属性值离散化 ; 如 : 100 分满分 , 将 60 分以下分为不及格数据 , 60 分以上分为及格数据 ;


    4 . 递归停止的条件 :


    ① 子树分类完成 : 节点上的子数据集都属于同一个类别 , 该节点就不再向下划分 , 称为叶子节点 ;

    ② 属性 ( 节点 ) 全部分配完毕 : 所有的属性都已经分配完毕 , 决策树的高度等于属性个数 ;

    ③ 所有样本分类完毕 : 所有的样本数据集都分类完成 ;



    VII . 决策树 树根属性 选择



    1 . 属性选择方法 : 树根属性选择的方法很多 , 这里介绍一种常用的方法 , 信息增益 ;


    2 . 信息增益 : 信息增益 效果越大 , 其作为树根属性 , 划分的数据集分类效果越明显 ;


    3 . 信息 和 熵 : 涉及 信息论 的知识点 , 建议有空就去 B站 刷一下信息论课程 ;


    ① 信息 与 熵 的关系 : 信息 会 消除 熵 , 熵 代表了不确定性 , 信息用来消除不确定性 ;

    ② 信息增益 : 信息增益大的属性 , 能最大消除熵的不确定性 ;


    4 . 决策树中的信息增益 : 属性的 信息增益 越大 , 就越能将分类效果达到最大 ;

    如 : 想要从用户数据集中找到是否能买奢侈品的用户 , 先把高收入群体划分出来 , 将低收入者从数据集中去除 , 这个收入水平的属性 ( 特征 ) , 信息增益就很大 ;

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,916
精华内容 7,966
关键字:

决策树算法