分类决策树_ID3算法

《分类决策树_ID3算法》由会员分享，可在线阅读，更多相关《分类决策树_ID3算法（51页珍藏版）》请在金锄头文库上搜索。

1、决策树 决策树基本概念 决策树算法 主要内容 决策树基本概念 决策树算法 决策树基本概念 关于分类问题 分类 Classification 任务就是通过学习获得一个目标函数 TargetFunction f 将每个属性集x映射到一个预先定义好的类标号y 分类任务的输入数据是纪录的集合 每条记录也称为实例或者样例 用元组 X y 表示 其中 X是属性集合 y是一个特殊的属性 指出样例的类标号 也称为分类属性或者目标属性 决策树基本概念 关于分类问题 X y 分类与回归 分类目标属性y是离散的 回归目标属性y是连续的 决策树基本概念 解决分类问题的一般方法 分类技术是一种根据输入数据集建立分类模型

2、的系统方法 分类技术一般是用一种学习算法确定分类模型 该模型可以很好地拟合输入数据中类标号和属性集之间的联系 学习算法得到的模型不仅要很好拟合输入数据 还要能够正确地预测未知样本的类标号 因此 训练算法的主要目标就是要建立具有很好的泛化能力模型 即建立能够准确地预测未知样本类标号的模型 分类方法的实例包括 决策树分类法 基于规则的分类法 神经网络 支持向量级 朴素贝叶斯分类方法等 决策树基本概念 解决分类问题的一般方法 通过以上对分类问题一般方法的描述 可以看出分类问题一般包括两个步骤 1 模型构建 归纳 通过对训练集合的归纳 建立分类模型 2 预测应用 推论 根据建立的分类模型 对测试集合进

3、行测试 决策树基本概念 解决分类问题的一般方法 学习算法 学习模型 模型 应用模型 训练集 类标号已知 检验集 类标号未知 归纳 推论 决策树基本概念 决策树 决策树是一种典型的分类方法 首先对数据进行处理 利用归纳算法生成可读的规则和决策树 然后使用决策对新数据进行分析 本质上决策树是通过一系列规则对数据进行分类的过程 决策树基本概念 决策树的优点1 推理过程容易理解 决策推理过程可以表示成IfThen形式 2 推理过程完全依赖于属性变量的取值特点 3 可自动忽略目标变量没有贡献的属性变量 也为判断属性变量的重要性 减少变量的数目提供参考 主要内容 决策树基本概念 决策树算法 决策树算法 与

4、决策树相关的重要算法 1 Hunt Marin和Stone于1966年研制的CLS学习系统 用于学习单个概念 2 1979年 J R Quinlan给出ID3算法 并在1983年和1986年对ID3进行了总结和简化 使其成为决策树学习算法的典型 3 Schlimmer和Fisher于1986年对ID3进行改造 在每个可能的决策树节点创建缓冲区 使决策树可以递增式生成 得到ID4算法 4 1988年 Utgoff在ID4基础上提出了ID5学习算法 进一步提高了效率 1993年 Quinlan进一步发展了ID3算法 改进成C4 5算法 5 另一类决策树算法为CART 与C4 5不同的是 CART的

5、决策树由二元逻辑问题生成 每个树节点只有两个分枝 分别包括学习实例的正例与反例 CLS ID3 C4 5 CART 决策树算法 假定公司收集了左表数据 那么对于任意给定的客人 测试样例 你能帮助公司将这位客人归类吗 即 你能预测这位客人是属于 买 计算机的那一类 还是属于 不买 计算机的那一类 又 你需要多少有关这位客人的信息才能回答这个问题 决策树的用途 谁在买计算机 年龄 学生 信誉 青 中 老 否 是 优 良 决策树的用途 决策树算法 谁在买计算机 年龄 学生 信誉 青 中 老 否 是 优 良 决策树的用途 决策树算法 决策树算法 决策树的表示 决策树的基本组成部分 决策结点 分支和叶子

6、 年龄 学生 信誉 青 中 老 否 是 优 良 决策树中最上面的结点称为根结点 是整个决策树的开始 每个分支是一个新的决策结点 或者是树的叶子 每个决策结点代表一个问题或者决策 通常对应待分类对象的属性 每个叶结点代表一种可能的分类结果 在沿着决策树从上到下的遍历过程中 在每个结点都有一个测试 对每个结点上问题的不同测试输出导致不同的分枝 最后会达到一个叶子结点 这一过程就是利用决策树进行分类的过程 利用若干个变量来判断属性的类别 ID3 决策树算法 ID3算法主要针对属性选择问题 是决策树学习方法中最具影响和最为典型的算法 该方法使用信息增益度选择测试属性 当获取信息时 将不确定的内容转为确

7、定的内容 因此信息伴着不确定性 从直觉上讲 小概率事件比大概率事件包含的信息量大 如果某件事情是 百年一见 则肯定比 习以为常 的事件包含的信息量大 如何度量信息量的大小 ID3 信息量大小的度量 决策树算法 Shannon1948年提出的信息论理论 事件ai的信息量I ai 可如下度量 其中p ai 表示事件ai发生的概率 假设有n个互不相容的事件a1 a2 a3 an 它们中有且仅有一个发生 则其平均的信息量可如下度量 ID3 信息量大小的度量 决策树算法 上式 对数底数可以为任何数 不同的取值对应了熵的不同单位 通常取2 并规定当p ai 0时 0 信息增益用来衡量给定的属性区分训练样例

8、的能力 中间 间接 表示属性ID3算法在生成树的每一步使用信息增益从候选属性中选择属性用熵度量样例的均一性 决策树算法 信息增益用熵度量样例的均一性熵刻画了任意样例集合S的纯度给定包含关于某个目标概念的正反样例的样例集S 那么S相对这个布尔型分类 函数 的熵为信息论中对熵的一种解释 熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数 熵值越大 需要的位数越多 更一般地 如果目标属性具有c个不同的值 那么S相对于c个状态的分类的熵定义为 决策树算法 用信息增益度量熵的降低程度属性A的信息增益 使用属性A分割样例集合S而导致的熵的降低程度Gain S A 是在知道属性A的值后可以节省的二进

9、制位数例子 注意是对当前样例集合计算上式 理解信息熵 1 信息熵是用来衡量一个随机变量出现的期望值 一个变量的信息熵越大 那么它出现的各种情况也就越多 也就是包含的内容多 我们要描述它就需要付出更多的表达才可以 也就是需要更多的信息才能确定这个变量 2 信息熵是随机变量的期望 度量信息的不确定程度 信息的熵越大 信息就越不容易搞清楚 杂乱 3 一个系统越是有序 信息熵就越低 反之 一个系统越是混乱 信息熵就越高 信息熵也可以说是系统有序化程度的一个度量 4 信息熵用以表示一个事物的非确定性 如果该事物的非确定性越高 你的好奇心越重 该事物的信息熵就越高 5 熵是整个系统的平均消息量 信息熵是信

10、息论中用于度量信息量的一个概念 一个系统越是有序 信息熵就越低 反之 一个系统越是混乱 信息熵就越高 6 处理信息就是为了把信息搞清楚 实质上就是要想办法让信息熵变小 理解信息增益 熵 表示随机变量的不确定性 条件熵 在一个条件下 随机变量的不确定性 信息增益 熵 条件熵 表示在一个条件下 信息不确定性减少的程度 例如 假设X 明天下雨 的信息熵为2 不确定明天是否下雨 Y 如果是阴天则下雨 的条件熵为0 01 因为如果是阴天就下雨的概率很大 信息就少了 信息增益 2 0 01 1 99 信息增益很大 说明在获得阴天这个信息后 明天是否下雨的信息不确定性减少了1 99 是很多的 所以信息增益大

11、 也就是说阴天这个信息对下雨来说是很重要的 ID3 信息量大小的度量 决策树算法 Gain S A 是属性A在集合S上的信息增益Gain S A Entropy S Entropy S A Gain S A 越大 说明选择测试属性对分类提供的信息越多 决策树算法 第1步计算决策属性的熵 决策属性 买计算机 该属性分两类 买 不买S1 买 641S2 不买 383S S1 S2 1024P1 641 1024 0 6260P2 383 1024 0 3740I S1 S2 I 641 383 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9537 决策树算法 第2步

12、计算条件属性的熵 条件属性共有4个 分别是年龄 收入 学生 信誉 分别计算不同属性的信息增益 决策树算法 第2 1步计算年龄的熵 年龄共分三个组 青年 中年 老年青年买与不买比例为128 256S1 买 128S2 不买 256S S1 S2 384P1 128 384P2 256 384I S1 S2 I 128 256 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9183 决策树算法 第2 2步计算年龄的熵 年龄共分三个组 青年 中年 老年中年买与不买比例为256 0S1 买 256S2 不买 0S S1 S2 256P1 256 256P2 0 256I

13、S1 S2 I 256 0 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 决策树算法 第2 3步计算年龄的熵 年龄共分三个组 青年 中年 老年老年买与不买比例为257 127S1 买 257S2 不买 127S S1 S2 384P1 257 384P2 127 384I S1 S2 I 257 127 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9157 决策树算法 第2 4步计算年龄的熵 年龄共分三个组 青年 中年 老年所占比例青年组384 1025 0 375中年组256 1024 0 25老年组384 1024 0 375计

14、算年龄的平均信息期望E 年龄 0 375 0 9183 0 25 0 0 375 0 9157 0 6877G 年龄信息增益 0 9537 0 6877 0 2660 1 决策树算法 第3步计算收入的熵 收入共分三个组 高 中 低E 收入 0 9361收入信息增益 0 9537 0 9361 0 0176 2 决策树算法 第4步计算学生的熵 学生共分二个组 学生 非学生E 学生 0 7811年龄信息增益 0 9537 0 7811 0 1726 3 决策树算法 第5步计算信誉的熵 信誉分二个组 良好 优秀E 信誉 0 9048信誉信息增益 0 9537 0 9048 0 0453 4 决策树算

15、法 第6步计算选择节点 年龄信息增益 0 9537 0 6877 0 2660 1 收入信息增益 0 9537 0 9361 0 0176 2 年龄信息增益 0 9537 0 7811 0 1726 3 信誉信息增益 0 9537 0 9048 0 0453 4 决策树算法 年龄 青年 中年 老年 买 不买 买 买 不买 叶子 决策树算法 青年买与不买比例为128 256S1 买 128S2 不买 256S S1 S2 384P1 128 384P2 256 384I S1 S2 I 128 256 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9183 决策树算

16、法 如果选择收入作为节点分高 中 低 平均信息期望 加权总和 E 收入 0 3333 0 0 5 0 9183 0 1667 0 0 4592Gain 收入 I 128 256 E 收入 0 9183 0 4592 0 4591 I 0 128 0比例 128 384 0 3333I 64 128 0 9183比例 192 384 0 5I 64 0 0比例 64 384 0 1667 注意 决策树算法 年龄 青年 中年 老年 学生 买 信誉 叶子 否 是 优 良 买 不买 买 不买 买 叶子 叶子 叶子 决策树算法 ID3决策树建立算法1决定分类属性 2对目前的数据表 建立一个节点N3如果数据库中的数据都属于同一个类 N就是树叶 在树叶上标出所属的类4如果数据表中没有其他属性可以考虑 则N也是树叶 按照少数服从多数的原则在树叶上标出所属类别5否则 根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性6节点属性选定后 对于该属性中的每个值 从N生成一个分支 并将数据表中与该分支有关的数据收集形成分支节点的数据表 在表中删除节点属性那一栏如果分支数据表非空 则运用以上算法