1决策树学习是以实例为基础的归纳学习。
决策树学习采用的是自顶向下的递归方法,决策树的每一层节点依照某一属性向下分子节点,待分类的实例在每一节点处与该节点相关的属性进行比较,根据不同的比较结果向响应的子节点扩展,这一过程在到达决策树的叶节点时结束,此时得到结论。
决策树学习最大的优点是它可以自学习。
2 决策树是描述分类的一种数据结构从上端的根节点开始,各种分类原则被引用进来,并以 这些分类原则见根节点的数据集划分为子集,这一划分过程直到某种约束条件满足而结束。
3 构造一棵决策树要解决的4个问题;
(1)收集待分类的数据,这些数据的所有属性应该是完全标注的。
(2)设计分类原则,即数据的哪些属性可以用来分类,以及如何将该属性量化。
(3)分类原则的选择,在众多的分类准则中,每一步选择哪一准则是最终的树更令人满意。
(4)设计分类停止条件。通用分类目标是整棵树的熵的总量最小。
4自信息量:设信源X发出a的概率p(a),在收到符号a之前,收信者对a的不确定性定义为a的自信息量I(a)=-logp(a)。
信息熵:自信息量只能反映符号的不确定性,而信息熵用来度量整个信源整体的不确定性,定义为:H(X)= 求和(p(ai) I(ai))
条件熵:设信源为X,收信者收到信息Y,用条件熵H(X|Y)来描述收信者收到Y后X的不确定性的估计。
平均互信息量:用平均互信息量来表示信息Y所能提供的关于X的信息量的大小。
互信息量I(X|Y)=H(X)-H(X|Y) 下边的ID3算法就是用到了每一个属性对分类的信息增益大小来决定属性所在的层次,信息增益越大,则越应该先作为分类依据。
5 ID3算法
下边的例子转自新浪博客,很详细,讲的不错。
还有一个老外的例子,也很不错,http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm。
决策树是数据挖掘中应用较广的一种算法,下面我将用一个例子来对较早出现的ID3算法探索应用一下,从而复习下昨天所学的知识,由于是刚接触,理解有限,有一些问题还得高手们解答一下;
世界杯期间我和同学一起去吃了几回大排档,对那种边凑热闹边看球的氛围感觉很不错,但虽然每个夏天我都会凑几回这种热闹,但肯定并不是所有人都喜欢凑这种热闹的,而应用决策树算法则能有效发现哪些人愿意去,哪些人偶尔会去,哪些人从不愿意去;
变量如表1所示,自变量为年龄、职业、性别;因变量为结果(吃大排档的频率)。
表1 数据表
年龄A
|
职业B
|
性别C
|
结果
|
20-30
|
学生
|
男
|
偶尔
|
30-40
|
工人
|
男
|
经常
|
40-50
|
教师
|
女
|
从不
|
20-30
|
工人
|
女
|
偶尔
|
60-70
|
教师
|
男
|
从不
|
40-50
|
工人
|
女
|
从不
|
30-40
|
教师
|
男
|
偶尔
|
20-30
|
学生
|
女
|
从不
|
20以下
|
学生
|
男
|
偶尔
|
20以下
|
工人
|
女
|
偶尔
|
20-30
|
工人
|
男
|
经常
|
20以下
|
学生
|
男
|
偶尔
|
20-30
|
教师
|
男
|
偶尔
|
60-70
|
教师
|
女
|
从不
|
30-40
|
工人
|
女
|
偶尔
|
60-70
|
工人
|
男
|
从不
|
计算过程:
1、首先计算结果选项出现的频率:
表2 结果频率表
从不p1
|
经常p2
|
偶尔p3
|
0.375
|
0.125
|
0.5
|
2、计算因变量的期望信息:
E(结果)=-(p1*log2(p1)+p2*log2(p2)+p3*log2(p3) )
=-(0.375*log2(0.375)+0.125*log2(0.125)+0.5*log2(0.5) )
=1.406
注:这里Pi对应上面的频率
3、计算自变量的期望信息(以年龄A为例):
E(A)=∑count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) ))
3.1公式说明:
Count(Aj):年龄A第j个选项个数; j是下面表3五个选项任一
表3 年龄记录数量表
选项
|
20-30
|
20以下
|
30-40
|
40-50
|
60-70
|
数量
|
5
|
3
|
3
|
2
|
3
|
Count(A):年龄总记录数
p1j =count(A1j)/count(Aj) :年龄A第j个选项在结果中选择了“从不”的个数占年龄A第j个选项个数的比例;
p2j =count(A2j)/count(Aj) :年龄A第j个选项在结果中选择了“偶尔”的个数占年龄A第j个选项个数的比例;
p3j =count(A3j)/count(Aj) :年龄A第j个选项在结果中选择了“经常”的个数占年龄A第j个选项个数的比例;
3.2公式分析
在决策树中自变量是否显著影响因变量的判定标准由自变量选项的不同能否导致因变量结果的不同决定,举例来说如果老年人都从不去大排档,中年人都经常去,而少年都偶尔去,那么年龄因素肯定是决定是否吃大排档的主要因素;
按照假设,即不同年龄段会对结果产生确定的影响,以表3年龄在20以下的3个人为例,假设他们都在结果中选择了“偶尔”选项,此时:
p2j =count(A2j)/count(Aj)=1,
p1j =count(A1j)/count(Aj)=0、
p3j =count(A3j)/count(Aj)=0;
(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )→0;
具体说来:
LIM(p2j→1) p2j*log2(p2j) →LIM(p2j→1) 1*0→0
LIM(p1j→0) p1j*log2(p1j) →LIM(p1j→0) log2(p1j) /(1/ p1j) →LIM(p1j→0) p1j* log2(e) →0
LIM(p3j→0) p1j*log2(p3j) →LIM(p3j→0) log2(p3j) /(1/ p3j) →LIM(p3j→0) p3j* log2(e) →0
(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )→0+0+0=0
可见,如果每个年龄段都对结果有确定影响,那么各年龄段的不加权的期望信息(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) )就很小,从而E(A)就很小甚至趋近0了;
4、自变量的期望信息计算
4.1、E(A)计算
从表4看,有两个年龄段对结果产生了不同影响,计算如下:
E(30-40)= count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) ))
=3/16*(-(2/3* log2(2/3) +1/3*log2(1/3) ))
=0.172
E(20-30)= count(Aj)/count(A)* (-(p1j*log2(p1j)+p2j*log2(p2j)+p3j*log2(p3j) ))
=5/16*(-(1/5* log2(1/5)+3/5* log2(3/5) +1/5*log2(1/5) ))
=0.428
最终算得:
E(A)= E(30-40)+ E(20-30)=0.172+0.428=0.6
表4 年龄信息表
年龄A
|
结果
|
60-70
|
从不
|
60-70
|
从不
|
60-70
|
从不
|
40-50
|
从不
|
40-50
|
从不
|
30-40
|
经常
|
30-40
|
偶尔
|
30-40
|
偶尔
|
20以下
|
偶尔
|
20以下
|
偶尔
|
20以下
|
偶尔
|
20-30
|
偶尔
|
20-30
|
偶尔
|
20-30
|
从不
|
20-30
|
经常
|
20-30
|
偶尔
|
5、信息增益的计算
年龄变量的信息增益计算为:
Gain(A)=E(结果)-E(A)= 1.406-0.6=0.806
同理可以计算Gain(B)、Gain(C);
注:信息增益大说明较好的降低了划分前的无序程度,因此决策树的第一次划分就看哪个变量的信息增益大就按哪个划分;
6、划分过程
如果是像上例那样变量选项比较少的决策树来讲,假设年龄变量的信息增益最大,那么第一部划分就是:
40-70岁 从不去光顾
20岁以下 偶尔
20-30岁 数据再按照职业和性别计算信息增益找出规则
30-40岁 数据再按照职业和性别计算信息增益找出规则
实际划分是按分割阈值的标准:
A、数值型变量——对记录的值从小到大排序,计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。
B、分类型变量——列出划分为两个子集的所有可能组合,计算每种组合下生成子节点的异质性。同样,找到使异质性减小程度最大的组合作为最佳划分点。
注两个问题:根节点一定要产生两个子集吗,要是产生三个子集、四个子集呢,产生多少子集有什么标准呢?我猜测是不是多个子集之间的结果两两差异显著就可以继续进行拆分,如果新的子集不能和原来任一子集的结果都有显著差异就停止划分呢?如何构建这个阈值的统计量呢?
7、划分停止的标准
满足以下一个即停止生长。
(1) 节点达到完全纯性;
(2) 数树的深度达到用户指定的深度;
(3) 节点中样本的个数少于用户指定的个数;
(4) 异质性指标下降的最大幅度小于用户指定的幅度。
剪枝:完整的决策树对训练样本特征的描述可能“过于精确”(受噪声数据的影响),缺少了一般代表性而无法较好的用对新数据做分类预测,出现 ”过度拟合“。
——移去对树的精度影响不大的划分。使用 成本复杂度方法,即同时度量错分风险和树的复杂程度,使二者越小越好。
剪枝方式:
A、 预修剪(prepruning):停止生长策略
B、后修剪(postpruning):在允许决策树得到最充分生长的基础上,再根据一定的规则,自下而上逐层进行剪枝。
分享到:
相关推荐
《决策树ID3算法实验详解——以广工实验为例》 决策树ID3算法是一种经典的机器学习算法,常用于分类任务。本实验报告基于广东工业大学(广工)的人工智能课程,通过具体案例——UCI标准数据集Car-Evaluation,详细...
PPT部分应该涵盖了决策树的基本概念、构建过程、常见算法如ID3、C4.5、CART的原理,以及剪枝策略,如预剪枝和后剪枝,以防止过拟合。此外,可能还会讨论到集成方法,如随机森林和梯度提升机,这些方法通过组合多棵...
ID3(Iterative Dichotomiser 3)算法是决策树构建的一种早期方法,由Ross Quinlan在1986年提出。它基于信息熵和信息增益的概念来选择最优特征进行节点划分,主要应用于分类问题。 **1. ID3算法的基本原理** ID3...
### 决策树算法原理详解 #### 一、信息熵(Entropy) 信息量是指一个样本或事件所包含的信息量。若一个事件的发生概率较高,则该事件携带的信息量相对较少。例如,“太阳从东方升起”这一事件是确定性的,因此不...
ID3(Iterative Dichotomiser 3)是最早的一种决策树算法,由Ross Quinlan提出。它以信息增益作为特征选择的依据,构建出能够模拟决策过程的树形结构。 1. **信息熵**:信息熵是衡量数据集纯度的一个指标,其值越大...
在这个“决策树源代码合集.rar”中,包含的是ID3决策树的实现及相关资料,ID3(Iterative Dichotomiser 3)是由Ross Quinlan在1986年提出的,它是早期的基于信息熵和信息增益的分类算法之一。 1. **ID3算法基础** ...
人工智能和机器学习之回归算法:决策树回归:ID3算法详解.docx
#### 三、决策树算法详解 ##### 3.1 ID3算法 ID3算法是最简单的决策树算法之一,它使用信息增益作为特征选择的标准。具体步骤如下: 1. **计算信息熵**:首先计算整个数据集的信息熵。 2. **计算信息增益**:对于...
除了绘制树部分代码有借鉴,其他代码都是自己亲手完成,历时2天时间,过程稍微痛苦,当看到运行结果出现在...由于更喜欢C++编程,所以使用python类来完成~~~~,个人感觉面向对象更容易和更适合实现生成决策树的软件系统
相关PPT
### 文档机器学习决策树-ID3算法的源代码 #### ID3算法简介 ID3(Iterative Dichotomiser 3)算法是由Ross Quinlan在1986年提出的一种用于分类问题的决策树算法。它通过递归地选择最佳特征来分割数据集,并以此...
常用的决策树算法有ID3、C4.5和CART等。ID3算法基于信息熵或信息增益来选择最优属性,而C4.5则是ID3的改进版,它用信息增益率来避免过早偏向于取值较多的属性。CART(分类与回归树)则用于处理连续值和分类值,既能...
### 第八章-决策树-ID3算法 #### 算法概述 ID3算法是一种基于信息增益的决策树构建算法。它最早由J. Ross Quinlan在1986年提出,作为Iterative Dichotomiser 3(简称ID3)的一种迭代决策树构建方法。该算法通过...
**see5.0决策树分析算法详解** **一、引言** See5.0是一款基于C4.5决策树算法的开源软件,主要用于数据挖掘和机器学习中的分类任务。它由Ross Quinlan开发,是C4.5算法的一个早期版本,尽管现在已经被更新的工具如...
【决策树算法详解】 决策树是一种在机器学习领域广泛应用的监督学习算法,它主要用于分类问题。决策树构建的模型能够直观地表示出特征与类别之间的关系,使得模型解释性极强。以下是关于决策树的详细知识: 1. **...
### 机器学习决策树算法ID3 #### 一、决策树与ID3算法概述 决策树是一种常用的机器学习方法,特别是在分类任务中表现突出。它通过构建一棵树形结构来进行决策,其中每个内部节点表示一个特征上的测试,每个分支...
【决策树J48算法详解】 决策树是一种广泛应用的机器学习算法,主要用于分类和回归问题。J48算法是C4.5决策树算法在Weka数据挖掘平台上的实现,它由Ross Quinlan开发。本文主要围绕基于Weka平台的J48决策树算法进行...
#### 三、决策树算法详解 **1. CLS算法** - **概述**:CLS算法是最早的决策树生成算法之一,主要用于生成二叉决策树。 - **特点**:算法简单直观,但容易过拟合。 **2. ID3算法** - **信息量大小的度量**:ID3...