第9章_决策树算法
9.2.2.1 C4.5的分裂属性选择度量
ID系列的算法为什么会产生归纳偏置呢? 归纳偏置是一系列前提,这些前提与训练 数据一起演绎论证未来实例分类。如果给 定一个训练数据集,那么通常有很多决策 树与这些样例一致。所以,要描述ID系列 算法的归纳偏置,应找到它从所有一致假 设中选择一个的根据。
第9章 决策树算法
SplitI A ( D) = ∑
j =1 v
er D
× log 2 (
er D
)
第9章 决策树算法
25
9.2.2.1 C4.5的分裂属性选择度量
增益比率的公式如下所示:
Gain( A) GainRatio( A) = SplitI ( A)
第9章 决策树算法
26
9.2.2.2 C4.5对连续数据的处理
只要生成了决策树后,就可以把树转换成 一个IF-THEN规则的集合。当然,每种算法 生成的决策树都可以转换成相应的if-then规 则,C4.5算法处理规则与其他算法不同在 于它把规则存储在一个二维数组中,每一 行都代表着树中的一个规则,即从树根到 叶子之间的一个路径 .
第9章 决策树算法
30
9.2.3 CART算法
第9章 决策树算法
24
9.2.2.1 C4.5的分裂属性选择度量
为了避免这个偏置,弥补ID系列算法的不足就要 舍弃信息增益这个度量而选择别的决策属性作为 度量标准。Quinlan在他1986年中的论文中提出 了一种可以使用的度量标准:增益比率。 增益比率通过加入一个被称为分裂信息(split information)的项来惩罚类似Date这样的属性, 分裂信息用来衡量属性分裂数据的广度和均匀性, 它由如下公式所示:
第9章 决策树算法 31
9.2.3 CART算法
Gini指标主要是度量数据划分或训练数据 集D的不纯度为主,系数值的属性作为测试 属性,Gini值越小,表明样本的“纯净度” 越高。Gini指标定义为如下公式:
Gini ( D ) = 1 ∑ pi2
i =1
m
第9章 决策树算法
32
9.2.3 CART算法
ID3算法最初的定义是假设属性值是离散值, 但在实际环境中,有很多属性是连续的, 不能够用一个确定的标准来对其进行划分。 C4.5使用下面的一系列处理过程来对连续 的属性划分成离散的属性,进而达到能够 建立决策树的目的。
第9章 决策树算法
27
9.2.2.2 C4.5对连续数据的处理
Step1 根据训练数据集D中各个属性的值对该训 练数据集进行排序; Step2 利用其中各属性的值对该训练数据集动态 地进行划分; Step3 在划分后的得到的不同的结果集中确定一 个阈值,该阈值将训练数据集数据划分为两个部 分; Step4 针对这两边各部分的值分别计算它们的增 益或增益比率,以保证选择的划分使得增益最大。
工作过程:
决策树分类模型的工作过程图
第9章 决策树算法 6
9.1 决策树算法原理
定义 9.1 给定一个训练数据集D=,其中每 个实例,称为例子,训练数据集中包含以 下属性A=。同时给定类别集合C。对于训 练数据集D,决策树 决策树是指具有以下性质的树: 决策树 每个内部节点都被标记一个属性Ai。 每个弧都被标记一个值,这个值对应于相 应父结点的属性。 每个叶节点都被标记一个类Cj。
第9章 决策树算法 7
9.1 决策树算法原理
定义9.2 分裂准则 定义为在决策树算法中 定义 将训练数据集D中的元组划分为个体类的最 好的方法与策略,它告诉我们在节点N上测 试哪个属性合适,如何选择测试与测试的 方法,从节点N上应该生长出哪些分支。 定义9.3 分裂属性 分裂属性Xi定义为决策树中每个内 定义 部节点都对应的一个用于分裂数据集的属 性。Xi A= { A1 , A2 ,L , Ah }
第9章 决策树算法
11
9.1 决策树算法原理
X ∈Y
i
颜色 ∈ { 红 , 绿 }
图9-4
按照分裂子集划分而成的决策树(只能是二叉树)图与相关的具体例子图
第9章 决策树算法
12
9.1 决策树算法原理
目前主要使用如下几个量化评估标准 (1)预测准确性 (2)模型强健性 (3)描述的简洁性 (4)计算复杂性 (5)处理规模性
23
9.2.2.1 C4.5的分裂属性选择度量
ID系列的搜索策略为:(1)优先选择较短 的树而不是较长的;(2)选择那些信息增 益高的属性离根节点较近的树。 结论:ID系列算法的归纳偏置是因为它在 选的时候较短的树比较长的树优先所产生 的,也就是那些信息增益高的属性更靠近 的根节点将会有优先生成树的特权。
由于二叉树不易产生数据碎片,精确度往往也会高于多叉 树,所以在CART算法中,统计学家们采用了二元划分, 在分支节点上进行Gini值的测试,如果满足一定纯度则划 分到左子树,否则划分到右子树,最终生成一棵二叉决策 树。 在只有二元分裂的时候,对于训练数据集D中的属性A将 D分成的D1和D2,则给定划分D的Gini指标如下公式所示:
第9章 决策树算法
18
9.2.1 ID3算法
假设训练数据集D中的正例集PD和反例 集ND的大小分别为p和n,则ID3基于下面 两个假设给出该决策树算法中信息增益的 定义,因为信息是用二进制编码的,所以 在下面的公式定义中都用以2为底的对数。 (1)在训练数据集D上的一棵正确决策树 对任意例子的分类概率同D中正反例的概率 一致;(2)一棵决策树能对一个例子做出 正确类别判断所需的信息量如下公式所示:
设训练数据集D一共有m类样例,每类样例数为: pi , i = 1,2,L, m 。 同样以属性A作为决策树的根,具有v个值 v1 , v 2 , L v v ,它将D分为v 个子集 {e1 , e2 ,L, ev } ,假设子集中任意元组属于类C的概率 p i 用表 示,并用 Ci ,D / D 估计。那么,该子集的信息量定义如下所示:
第9章 决策树算法 4
9.1 决策树算法原理
传统的数据分类操作通常有以下两个步骤: 模型训练阶段:根据给定的训练集,找到 合适的映射函数H:→C的表示模型。 使用上一步训练完成的函数模型预测数据 的类别,或利用该函数模型,对数据集中 的每一类数据进行描述,形成分类规则。
第9章 决策树算法
5
9.1 决策树算法原理
第9章 决策树算法
13
9.2 常用决策树算法
ID3算法
ID3是Quinlan于1986年提出的,是机器学习中一种 广为人知的一个算法,它的提出开创了决策树算法的先河, 而且是国际上最早最有影响的决策树方法,在该算法中, 引入了信息论中熵的概念,利用分割前后的熵来计算信息 增益,作为判别能力的度量。
I (er ) = ∑ p i log 2 ( p i )
那么以A为根分类后所需的信息期望如下面公式所示:
i =1 m
E ( A) = ∑
j =1
v
er D
× I (e r )
21
第9章 决策树算法
9.2.2 C4.5算法
(1)分裂 (2)连续数据 (3)缺失数据 (4)规则
第9章 决策树算法
22
第9章 决策树算法
14
9.2.1 ID3算法
定义9.6 信息熵 定义 自信息量只能反映符号的不确定性,而信息熵可以用 来度量整个信源X整体的不确定性。设某事物具有n种相互 独立的可能结果(或称状态):x1 , x 2 , L, x n ,每一种结果出现 的概率分别为 P( x1 ), P( x2 ),L P( xn ), 且有: (9.1) 9.1 ∑ p(x ) = 1
第9章 决策树算法 8
9.1 决策树算法原理
定义9.4 如果Xi是连续属性,那么分裂准则 定义 的形式为Xi,其中,就称为节点n的分裂点 分裂点。 分裂点 定义9.5 如果Xi是离散属性,那么的形式为, 定义 其中,就称为节点n的分裂子集 分裂子集。 分裂子集 注意: 注意:分裂准则与分裂属性、分裂点、分裂 子集并不等同,它们是四个不同的概念, 并且分裂子集分裂点分裂属性分裂准则
第9章 决策树算法 16
9.2.1 ID3算法
Quinlan的首创性工作主要是在决策树的学 习算法中第一次引入了信息论中的互信息 (称之为信息增益),以之作为属性选择 的标准,并且将建树的方法嵌入在其中, 其核心是在决策树的各级节点上选择属性, 用信息增益作为属性选择标准
第9章 决策树算法
17
9.2.1 ID3算法
第9章 决策树算法
9
9.1 决策树算法原理
将上面的定义结合实际的决策树例子可得 决策树图如下图9-1,图9-2,图9-3所示, 图中设X为分裂属性,是属性X的已知值。
图9-2 按照分裂点划分而成的决策树图与相关的具体例子图
第9章 决策树算法 10
9.1 决策树算法原理
图9-3 按照分裂子集划分而成的决策树图与相关的两个具体例子图
E ( A) = ∑
i =1
v
p i + ni I ( p i , ni ) p+n
因此,以A为根的信息增益如下公式所示:
gain ( A) = I ( p, n) E ( A)
第9章 决策树算法
20
9.2.1 ID3算法
上面给出的ID3中的信息论的相关定义主要是在两类分类 问题的前提下,下面给出将其扩展到多类后的相关定义描 述。
第9章 决策树算法
3
9.1 决策树算法原理
优点: 使用者不需要了解很多背景知识,只要训练事例 能用属性→结论的方式表达出来,就能用该算法 学习; 决策树模型效率高,对训练集数据量较大的情况 较为适合; 分类模型是树状结构,简单直观,可将到达每个 叶结点的路径转换为IF→THEN形式的规则,易于 理解; 决策树方法具有较高的分类精确度。