Data Mining 笔记Classification之决策树 | idouba

Data Mining 笔记Classification之决策树

一、算法概述

是一种类似于流程图的树结构;其中,每个内部结点表示在一个属性上的测试,每个分枝代表一个测试输出;每个树叶结点存放一个类标号。

基本算法

通过递归的方式从上向下,开始的所有训练集中的数据都在根节点。样本数据的属性可以被分类(如果是联系的数据,需要事先离散化)。样本数据基于选定的属性进行分开,通过information gain等统计指标来选择样本考察的属性。

算法终止条件

  • 一个节点上的样本属于一个相同的分类;
  • 没有剩余的属性需要再分割数据
  • 所有样本都考察完毕

三、算法伪代码

四、算法示例

训练集如下,根据训练集数据建立决策树。并判断顾客,有这样四种属性(青年,低收入,非学生,中等信用度) 是否有购买电脑的倾向

id? 年龄? 收入? 学生? 信用? 购买?
1 ? ? ? ? ?
2 ? ? ? ? ?
3 ? ? ? ? ?
4 ? ? ? ? ?
5 ? ? ? ? ?
6 ? ? ? ? ?
7 ? ? ? ? ?
8 ? ? ? ? ?
9 ? ? ? ? ?
10 ? ? ? ? ?
11 ? ? ? ? ?
12 ? ? ? ? ?
13 ? ? ? ? ?
14 ? ? ? ? ?

开始训练集中14条数据都在根节点,执行算法,观察待分类的“购买”一列,并不是所有数据都属于一个分类“是”或者“否”,因而执行算法的下下面一个分支:

选择年龄为测试条件(关于其中最重要的属性选择办法,为什么先选择年龄而不是其他收入、学生等属性?参考下篇博文中描述),根据年龄分为三个子节点。根据训练集的数据分别构造自己的decision tree(递归的),开始时候训练集中所有的数据都各自的根节点下。如下图,老年的一个根节点,包含4、5、6、10、14记录,中年 的根节点包含3、7、12、13记录,青年根节点包括1、2、8、9、11记录。

构造决策树示例

构造决策树示例

然后对每个子decision-tree递归执行算法,“老年”子树的记录不属于一个分类(购买列有“是”和“否”),则需要选择属性继续分隔(选择哪个属性,需要根据当前的样本情况进行计算,参考下篇博文中描述),同样的“青年”子树也需要选择下一个属性,继续分隔。而“中年”子树中所有样本记录都属于一个分类(全部是“是”),则根据算法

只用把该子树用“是”标记即可。另外两个子树分别再构造。“青年”子树选择“是否学生”属性来判定,最终得到了“是学生”的子树都属于一个分类“购买:否”,“不是学生的”子树都属于““购买:是”,则该子树构建结束;同样的“老年”子树选择“信用”属性来考察,在引用为“优”和“中”的分别落到一个分类,则分类结束。

我的注解:在递归构造构造decision tree子树,要选择一个前面没有用过的属性来分裂节点时,都要结合当前待分裂的子节点的样本情况,对所有未使用的属性计算一个指标,以选择一个合适的属性来分裂节点。如例子中“青年”子树选择“是否学生”属性,而“老年”子树选择“信用”属性。即属性选择是在每次构造中都要对训练集的当前节点子集计算一次,而不是原来理解的只是对整个记录集中计算一次,获得一个类似“年龄,学生,信用等级,收入”这样顺序,每个子树都是按照这个顺序来做

结果为:

dessiion-tree result

决策树结果

完。

原创文章。为了维护文章的版本一致、最新、可追溯,转载请注明: 转载自idouba

本文链接地址: Data Mining 笔记Classification之决策树


, ,

No comments yet.

发表评论