当前位置：文档之家 › 决策树算法及应用拓展教材ppt

决策树算法及应用拓展教材ppt

  • 格式：ppt
  • 大小：278.00 KB
  • 文档页数：5

下载文档原格式

  / 5

合集下载

决策树分析方法ppt

决策树分析方法ppt

全局最优
通过剪枝等技术来优化决 策树，以获得全局最优解 （最小损失函数值）。
决策树的预测原理
特征选择
使用训练好的决策树模型对新 的样本进行预测时，需要根据 模型中保存的特征选择规则进
行预测。
路径搜索
从根节点开始，根据模型中保存 的分裂准则和分裂点信息，沿着 树结构向下搜索，直到到达叶子 节点或无法继续分裂的节点。
CART算法步骤
划分数据集、对每个属性计算其划分能力、选择划分能力最大的属性、生成决策 节点、递归生成决策树。
随机森林算法
随机森林算法原理
基于多棵决策树的投票策略，通过训练多棵决策树，然后对 结果进行投票，以得到更加准确的结果。
随机森林算法步骤
数据集随机化、生成多棵决策树、对结果进行投票、选择票 数最多的结果作为输出。
01
02
03
04
总结词：差异对比、应用场景
线性回归是一种基于因变量和 一个或多个自变量之间关系的 预测模型，通常适用于连续目 标变量。
决策树是一种基于自上而下的 贪心搜索算法，将数据集划分 成若干个不相交的子集，每个 子集对应一个决策节点，从而 形成一棵树状结构。
在回归问题上，决策树不如线 性回归表现稳定，但在分类问 题上，决策树表现更优秀，可 以很好地处理非线性关系和异 常值。
C4.5算法
C4.5算法原理
在ID3算法的基础上，增加了剪枝、处理缺失值和连续属性等处理，以得到 更加准确的决策树。
C4.5算法步骤
计算各个属性的信息增益率、选择信息增益率最大的属性、生成决策节点、 递归生成决策树、剪枝处理。
CART算法
CART算法原理
基于二叉树的贪心策略，将数据集划分为两个子集，然后对每个子集递归生成决 策树。

决策树算法(PPT36页)

决策树算法(PPT36页)
第七章 决策树和决策规则
本章目标 分析解决分类问题的基于逻辑的方法的特
性. 描述决策树和决策规则在最终分类模型中
的表述之间的区别. 介绍C4.5算法. 了解采用修剪方法降低决策树和决策规则
的复杂度.
决策树和决策规则是解决实际应用中分类 问题的数据挖掘方法。
一般来说，分类是把数据项映射到其中一 个事先定义的类中的这样一个学习函数的 过程。由一组输入的属性值向量(也叫属性 向量)和相应的类，用基于归纳学习算法得 出分类。
单按上面方式计算。下面先介绍一下C4.5 算法中一般包含3种类型的检验结构：
1.离散值的“标准”检验，对属性的每个可 能值有一个分枝和输出。
2.如果属性Y有连续的数值，通过将该值和阈 值Z比较，用输出Y≤Z和Y＞Z定义二元检验。
3.基于离散值的更复杂的检验，该检验中属 性的每个可能值被分配到许多易变的组中， 每组都有一个输出和分枝。
7.2 C4.5算法：生成一个决策树
C4.5算法最重要的部分是由一组训练样本 生成一个初始决策树的过程。决策树可以 用来对一个新样本进行分类，这种分类从 该树的根节点开始，然后移动样本直至达 叶节点。在每个非叶决策点处，确定该节 点的属性检验结果，把注意力转移到所选 择子树的根节点上。
例如，如图7-3a为决策树分类模型，待分 类有样本如图7-3b所示，由决策树分类模 型可得出待分类样本为类2。(节点A,C,F(叶 节点))
=0.694
相应的增益: Gain(x1)=0.94-0.694=0.246
按属性3分区可得子集的熵的加权和：
infox2(T)=6/14(-3/6log2(3/6)-3/6log2(3/6)) +8/14(-6/8log2(6/8)-2/8log2(2/8))

高中信息技术浙教版：决策树教学课件(共27张PPT)

高中信息技术浙教版：决策树教学课件(共27张PPT)
第五步：使用Python库测试结果可视化
第一步：收集数 据
第三步：向Python导入 数据
第四步：使用Python库sklearn训练
第二步：分割数据
课堂小结
一、2017年度重点工作项目完成情况
1 决策树分类概念 2 构建决策树
3 举例说明：鸢尾花分类
备未用来：的深深度度学学习习：人工智能
展望与挑战
“温度”是多余的特点
如何判断某一天游客是否会来游乐场游玩？
天气、温度、湿度
2.4.1决策树分类概念
建立决策树的过程 选择一个属性值，基于这个属性对样本集进行划分，得到子集划分结果。
再选择其他属性，对得到的划分结果进行划分，直至最后所得划分结果中每 个样本为同一个类别。
2.4.2构建决策树
构建决策树来解决实际生活中的问题时，需按照一定的顺序选择划分属 性。通常，性能好的决策树随着划分不断进行，决策树分支节点的“纯度” 会越来越高，即其所包含样本尽可能属于相同类别。为了逐次选出最优属 性，可以采用信息增益(informationgain)这一指标。
2.4.2构建决策树
练一练： 1.计算表2.4.1中温度高低、湿度大小、风力强弱三个气象特点的信息增益。
思考： 将天气状况、温度高低、湿度大小、风力强弱作为分支点来构造图2.4.1决策
树时，是否信息增益大的气象特点离根节点越近?
【练一练】： 如下表所示，每朵鸢尾花有萼片长度、萼片宽度、花瓣长度、花瓣宽度四个
4个属性 1个标签 1 Label 4 Features 用来标记种类
序号 Index 0-149， 一共150个样本
基于鸢尾花数据集
例：鸢尾花数据集是常用的分类实验数据集，由Fisher1936收集整理。 Iris也称鸢尾花卉数据集，是一类多重变量分析的数据集。数据集包含 150个数据样本，分为3类，每类50个数据，每个数据包含4个属性。可通 过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性预测鸢尾花卉属于 （Sentosa 0，Versicolor 1，Virginia 2）三个种类中的哪一类。

决策树算法演示文稿

决策树算法演示文稿
Step4 针对这两边各部分的值分别计算它们的增益或增
益比率，以保证选择的划分使得增益最大。
第9章 决策树算法
28 第28页，共65页。
9.2.2.3 C4.5对缺失数据的处理
为了评估属性A是否是决策节点n的最佳测试属性，要计算决策树 在该节点的信息增益Gain(D,A)。假定< , c( )>是S中di的一d个i 训
将要介绍的算法的共同点也是在于都是利 用了相同的属性度量标准Gini指标。
第9章 决策树算法
31 第31页，共65页。
9.2.3 CART算法
Gini指标主要是度量数据划分或训练数据 集D的不纯度为主，系数值的属性作为测试 属性，Gini值越小，表明样本的“纯净度” 越高。Gini指标定义为如下公式：
6 第6页，共65页。
9.1 决策树算法原理
定义 9.1 给定一个训练数据集D＝，其中每 个实例，称为例子，训练数据集中包含以 下属性A=。同时给定类别集合C。对于训 练数据集D，决策树是指具有以下性质的树：
每个内部节点都被标记一个属性Ai。
每个弧都被标记一个值，这个值对应于相 应父结点的属性。
9.2.2.1 C4.5的分裂属性选择度量
为了避免这个偏置，弥补ID系列算法的不足就要舍弃
信息增益这个度量而选择别的决策属性作为度量标准。
Quinlan在他1986年中的论文中提出了一种可以使用 的度量标准：增益比率。
增益比率通过加入一个被称为分裂信息（split information）的项来惩罚类似Date这样的属性，分
第9章 决策树算法
19 第19页，共65页。
9.2.1 ID3算法
I ( p, n)
p p n log2

决策树ppt课件

决策树ppt课件
建设小工厂投资280万元，如销路好，3年后扩建，扩 建需要投资400万元，可使用7年，每年赢利190万元。 不扩建则每年赢利80万元。如销路不好则每年赢利60 万元。
试用决策树法选出合理的决策方案。 经过市场调查， 市场销路好的概率为0.7，销路不好的概率为0.3。
15
680万元 2
建大厂
该承包商过去也承包过与A、B类似的工程，根 据统计资料，每种方案的利润和出现的概率如 下表所示。投标不中时，则对A损失50万元， 对B损失100万元。根据上述情况，试画出决 策树
11
方案 A高 A低 B高 B低
效果
优 一般 赔 优 一般 赔 优 一般 赔 优 一般 赔
可能的利润(万元)
5000 1000 -3000 4000 500 -4000 7000 2000 -3000 6000 1000 -1000
10
例2
某承包商拥有的资源有限，只能在A和B两个工 程中选A或B进行投标，或者对这两项工程都不 参加投标。
但根据过去该承包商投标经验资料，他对A或B 投标又有两种策略:一种是投高标，中标的机会 是0.3；另一种是投低标，中标的机会是0.5。 这样共有A高、A低、不投、B高和B低五种方 案。
叫做方案枝； C、在每个方案枝的末端画一个圆圈，这个圆
圈称为概率分叉点，或自然状态点； D、从自然状态点引出代表各自然状态的分枝，
称为概率分枝； E、如果问题只需要一级决策，则概率分枝末
端画三角形，表示终点 。
3
1
决策 结点
概率分叉点
(自然状态点) 概率枝
方案分枝 2
概率枝
方案分枝
概率枝
益期望值分别为125、0、620和1100。 至此，承包商可做出决策，如投A工程，

决策树分析方法PPT课件( 39页)

决策树分析方法PPT课件( 39页)
• 提供快捷、口径一致的分析模式
• 适用于对银行盈利能力数量分析，根据影响指 标相关要素的数量变化，探求各要素变化的原 因以及影响程度
• 同样的方法也可运用于银行其他情况的分析
2019/6/23
3
目录
1. 概念和作用 2. 决策树体系结构 3. 决策树运用基本要素 4. 决策树运用示例 5. 决策树运用示例分析结论
本季度
上季度
第一步 第二步 第三步
初步判断：处于平均水平
2019/6/23
22
分析结论一─对当期盈利分析
• 计算数据显示该银行的盈利比率为 1.28%，同类型银行的平均数为1.29% ，表明该银行居于同类型银行的中间位 置
• 该银行的百分比排名为51，表示在同类 型银行中，有49%高于该行的1.28%比 率，而有51%低于该比率
时间点 平均资产 净收入 同类型银行数
该银行 同类型 百分比排名
边际分析 指标对各类平 均资产百分比
贷款分析 指标对各类平 均资产百分比
流动性分析
资本分析
增长比率
2019/6/23
12
分析过程
• 由概要指标开始分析 • 鉴别差异 • 分析差异的原因 • 考虑所有的影响要素 • 深究细节 • 确定问题的根本原因
决策树分析方法─非现
场数据分析法
2019/6/23
1
目录
1. 概念和作用 2. 决策树体系结构 3. 决策树运用基本要素 4. 决策树运用示例 5. 决策树运用示例分析结论
2019/6/23
2
概念和作用
• 决策树分析是数量分析方法
• 决策树是一种树状结构，其分析由树根节点开 始逐层展开，每一分支树枝前后节点具有数量 逻辑关系

决策树ppt课件

决策树ppt课件
决策树在分类问题中应用
分类问题背景介绍
分类问题是机器学习中一类重要 的问题，旨在将数据划分为不同
的类别。
在现实世界中，分类问题广泛存 在，如垃圾邮件识别、疾病诊断、
信用评分等。
分类算法的目标是通过学习训练 数据中的特征与类别之间的关系， 从而对新的未知数据进行类别预
测。
决策树在分类问题中优势
直观易理解
决策树在处理缺失值和异常值时容易受到干扰，可能导致模型性能下降。可以通过数据 预处理等方法减少缺失值和异常值对模型的影响。
CART算法实例演示
实例背景
假设有一个关于信用卡欺诈的数据集，包含多个特征（如交 易金额、交易时间、交易地点等）和一个目标变量（是否欺 诈）。我们将使用CART算法构建一个分类模型来预测交易 是否属于欺诈行为。
构建决策树时间较长
C4.5算法在构建决策树时需要计算每 个特征的信息增益比，当数据集较大 或特征较多时，构建决策树的时间可 能会较长。
C4.5算法实例演示
数据集介绍
以经典的鸢尾花数据集为例，该数据集包含150个 样本，每个样本有4个特征（花萼长度、花萼宽度、 花瓣长度、花瓣宽度）和1个标签（鸢尾花的类 别）。
建造年份等特征。
选择合适的决策树算法 （如CART、ID3等），
对数据进行训练。
模型评估与优化
采用均方误差等指标评 估模型性能，通过调整 参数、集成学习等方法
优化模型。
结果展示与解读
展示决策树图形化结果， 解释每个节点含义及预
测逻辑。
08
CATALOGUE
总结与展望
决策树模型总结回顾
模型原理
决策树通过递归方式将数据集划分为若干个子集，每个子 集对应一个决策结果。通过构建树形结构，实现分类或回 归任务。

决策树培训讲义(PPT 49页)

决策树培训讲义(PPT 49页)

Married 100K No
Single 70K
No
Married 120K No
Divorced 95K
Yes
Married 60K
No
Divorced 220K No
Single 85K
Yes
Married 75K
No
Single 90K
Yes
3. samples = { 2,3,5,6,8,9,10 } attribute_list = { MarSt, TaxInc }
选择TaxInc为最优分割属性：
Refund
Yes
No
NO < 80K
Single TaxInc
MarSt
Married Divorced
>= 80K
NO
YES
▪ 问题1：分类从哪个属性开始？
——选择分裂变量的标准
▪ 问题2：为什么工资以80为界限？
——找到被选择的变量的分裂点的标准（ 连续变量情况）
分类划分的优劣用不纯性度量来分析。如果对于所有
分支，划分后选择相同分支的所有实例都属于相同的类，
则这个划分是纯的。对于节点m，令 N m 为到达节点m的训练
实例数，
个实例中
N
i m
个属于Ci
类，而
N
i m
Nm 。如果一
个实例到节点m，则它属于 类的概率估i 计为：
pˆ (Ci
|
x, m)
pmi
N
i m
10
Single 125K No
Married 100K No
Single 70K
No
Married 120K No

决策树(完整)ppt课件

决策树(完整)ppt课件

留出法：将数据集D划分为两个互斥的集合：训练集S和测试集T
DST且 ST
;.
18
;.
19
预剪枝
训练集：好瓜 坏瓜 1,2,3,6,7,10,14,15,16,17
1,2,3,14
4,5,13 (T,T,F)
6,7,15,17
8,9 (T,F)
精度：正确分类的样本占所有 样本的比例
验证集：4,5,8,9,11,12,13
三种度量结点“纯度”的指标： 1. 信息增益 2. 增益率 3. 基尼指数
;.
6
1. 信息增益 信息熵
香农提出了“信息熵”的概念，解决了对信息的量化度量问题。 香农用“信息熵”的概念来描述信源的不确定性。
对于二分类任务 y 2
;.
7
假设我们已经知道衡量不确定性大小的这个量已经存在了，不妨就叫做“信息量”
用“编号”将根结点划分后获得17个 分支结点的信息熵均为：
E n t( D 1 ) E n t(D 1 7 ) ( 1 1 lo g 2 1 1 1 0 lo g 2 1 0 ) 0
则“编号”的信息增益为：
G a in (D ,编 号 ) E n t(D )1 71E n t(D v) 0 .9 9 8
;.
30
1. 属性值缺失时，如何进行划分属性选择？（如何计算信息增益） 2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
（对于缺失属性值的样本如何将它从父结点划分到子结点中）
D : D : 训练集
训练集中在属性a上没有缺失值的样本子集
D D v :
被属性a划分后的样本子集
D D k :
;.
2
二分类学习任务 属性 属性值

决策树学习培训讲义(PPT38张)

决策树学习培训讲义(PPT38张)

Attrib2 Large Medium Small Medium Large Medium Large Small Medium Small
Attrib3 125K 100K 70K 120K 95K 60K 220K 85K 75K 90K
Class No No No No Yes No No Yes No Yes
Attrib2 Small Medium Large Small Large
Attrib3 55K 80K 110K 95K 67K
Class ? ? ? ? ?
演绎
测试集
9
决策树应用
测试数据 从根节点开始
R e f u n d M a r it a l S t a t u s N o M a r r ie d T a x a b le h e a t In c o m e C 8 0 K ?
T a x a b le In c o m e 125K 100K 70K 120K 95K 60K 220K 85K 75K 90K
C heat No No No No Yes No No Yes No Yes
基本算法
Don’t Cheat
1 2 3 4
Yes No No Yes No No Yes No No No

i 1
其中p是在S中正例的比例，pΘ是在S中负例的比例。在有关熵的所 有计算中我们定义0log0为0。
22
例子
C 1 C 2
C1 C2
0 6
1 5
Entropy = -(0/6)log(0/6)-(6/6)log(6/6)=0
Entropy = 1-(1/6)log(1/6)-(5/6)log(5/6)=0.650

决策树课件PPT精品文档61页

决策树课件PPT精品文档61页
Clementine的决策树
主要内容
决策树算法概述 从学习角度看，决策树属有指导学习算法 目标：用于分类和回归
C5.0算法及应用 分类回归树及应用 CHAID算法及应用 QUEST算法及应用 模型的对比分析
决策树算法概述：基本概念
得名其分析结论的展示方式类似一棵倒置的树
C5.0算法：熵
例如：二元信道模型
P(u1|v1) P(u1|v2)
P P((u u2 2||vv12))P P 1 12 1P P 2 21 2
C5.0算法：熵
先验不确定性：通信发生前，信宿对信源的状态具 有不确定性
后验不确定性：通信发生后，信宿收到发自信源的 信息，先验不确定性部分被消除，信宿对信源仍有 一定程度的不确定性 后验不确定性等于先验不确定性，表示信宿没有 收到信息； 后验不确定性等于零，表示信宿收到了全部信息 信息是用来消除随机不确定性的，信息量的大小 可由所消除的不确定性大小来计量
C5.0算法：熵
信息熵是信息论(C.E.Shannon,1948)中的基本概 念。信息论主要用于解决信息传递过程中的问题 ，也称统计通信理论
信息论的基本出发点认为：
信息传递通过由信源、信道和信宿组成的传递 系统实现
信源(发送端) 信道
信宿(接收端)
C5.0算法：熵
信息论的基本出发点认为： 传递系统存在于一个随机干扰环境之中 将发送的信息记为U，接收的信息记为V，那么 信道可看作为信道模型，记为P(U|V)
决策树算法概述：核心问题
第一，决策树的生长 利用训练样本集完成决策树的建立过程
第二，决策树的剪枝 利用测试样本集对所形成的决策树进行精简
决策树算法概述：树生长

《决策树算法》课件

《决策树算法》课件
决策树的构建过程是从根节点开始，根据训练数据集中每个 特征属性的信息增益或基尼指数等指标，选择最佳划分属性 ，生成左、右子树，直至达到终止条件（如叶子节点包含的 样本都属于同一类别或达到预设的分类精度）。
决策树算法的优缺点
优点
决策树算法具有直观易懂、分类效果好、易于理解和解释等优点。它能够处理 非线性关系和连续属性，对数据预处理要求较低，且能够处理缺失值和异常值 。
习竞赛中都取得了优异的成绩。
05
决策树算法的应用案例
分类问题案例
信用卡欺诈识别
利用决策树算法对信用卡交易数据进 行分析，识别出异常交易，预防欺诈 行为。
疾病诊断
根据患者的症状、体征等数据，利用 决策树算法进行分类，辅助医生做出 准确的疾病诊断。
回归问题案例
要点一
股票价格预测
利用历史股票数据，通过决策树回归算法预测未来股票价 格走势。
03
决策树算法的实践
数据集的准备
数据清洗
处理缺失值、异常值和重复数据，确保数据质量 。
数据转换
对连续型特征进行分箱处理，将连续值划分为离 散区间。
ABCD
特征选择
选择与目标变量相关的特征，去除无关或冗余特 征。
数据平衡
处理类别不均衡问题，通过过采样、欠采样或使 用合成数据来平衡各类别的样本数量。
数据挖掘
决策树算法是数据挖掘领域中常用的算法之一，常与其他 算法结合使用，如随机森林、梯度提升决策树等，以提高 分类和回归任务的准确性和稳定性。
回归任务
除了分类任务外，决策树算法也可用于回归任务，如预测 房价、股票价格等连续值。通过构建回归决策树模型，可 以对连续目标变量进行预测。
可解释性
由于决策树算法具有直观的树形结构和易于理解的规则， 因此在某些需要解释性强的场景中具有优势，如医疗诊断 、金融风控等领域。

第四章-决策树PPT课件

第四章-决策树PPT课件

34
可解释性
➢ 决策边界是平行坐标轴的 ➢ 对于过于复杂的问题，会导致很多小的划分
35
总结
优点
生成可理解的规则
分类时计算代价很小
能够选出对分类比较重要的属性
对长方形分布的样本处理很好
缺点
+++----------------+++----------------+++--------+++-------- ++++++++---++++++++------++++++++------+++++++++++++++----+++----++++----+++----+++++++----++++
纹理(15个样本) :{1, 2, 3, 4, 5, 6, 7, 9, 11, 12, 13, 14, 15, 16, 17} 稍糊(5个样本): {7,9,13,14,17} 清晰(7个样本): {1,2,3,4,5,6,15} 模糊(3个样本): {11,12,16} 缺失纹理属性取值的样本：{8,10}
• Wikipedia page for decision tree: /wiki/Decision_tree_learning
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

I(s1,s2,……,sm)=－∑Pi log2(pi) (i=1..m)
其中，数据集为S，m为S的分类数目， Pi
| Si
|
|S |
Ci为某分类标号，Pi为任意样本属于Ci的概率，
si为分类Ci上的样本数 由A划分为子集的熵：
E(A)= ∑(s1j+ ……+smj)/s * I(s1j+ ……+smj)
基本思想： 用途：提取分类规则，进行分类预测
input 判定树分类算法 output 训练集
决策树
使用决策树进行分类
决策树
一个树性的结构 内部节点上选用一个属性进行分割 每个分叉都是分割的一个部分 叶子节点表示一个分布
决策树生成算法分成两个步骤
树的生成 开始，数据都在根节点 递归的进行数据分片
属性选择的统计度量
信息增益——Information gain (ID3/C4.5)
所有属性假设都是种类字段 经过修改之后可以适用于数值字段
基尼指数——Gini index (IBM IntelligentMiner)
能够适用于种类和数值字段
信息增益度度量(ID3/C4.5)
任意样本分类的期望信息：
31…40 medium no excellent
31…40 high
yes fபைடு நூலகம்ir
>40 medium no excellent
buys_computer no no yes yes yes no yes no yes yes yes yes yes no
使用信息增益进行属性选择
Class P: buys_computer = “yes”
Class N: buys_computer = “no”
E(age) 5 I(2,3) 4 I(4,0)
14
14
5 I(3,2) 0.971 14
Hence
I(p, n) = I(9, 5) =0.940 G( a a ) g iI(p n e ,n ) E ( a)g
Compute the entropy for age:
gin(iT) 1
n
p2j
j1
如果集合T分成两部分 N1 and N2 。那么这个分割的
Gini就是 gisn p(T l) ii tN N 1gi(T n 1 ) iN N 2gi(T n 2 )i
提供最小Ginisplit 就被选择作为分割的标准(对于每个 属性都要遍历所有可以的分割方法).
决策树算法及应用拓展教材ppt
决策树算法及应用拓展
内容简介：
概述 预备知识
决策树生成(Building Decision Tree) 决策树剪枝(Pruning Decision Tree)
捕捉变化数据的挖掘方法 小结
决策树算法及应用拓展教材ppt
概述(一)
传统挖掘方法的局限性
只重视从数据库中提取规则，忽视了库中 数据的变化
(如, information gain)
停止分割的条件
一个节点上的数据都是属于同一个类别 没有属性可以再用于对数据进行分割
伪代码(Building Tree)
Procedure BuildTree(S) 用数据集S初始化根节点R 用根结点R初始化队列Q While Q is not Empty do { 取出队列Q中的第一个节点N if N 不纯 (Pure) { for 每一个属性 A 估计该节点在A上的信息增益 选出最佳的属性，将N分裂为N1、N2 } }
树的修剪 去掉一些可能是噪音或者异常的数据
决策树使用: 对未知数据进行分割
按照决策树上采用的分割属性逐层往下，直到一个叶子节点
决策树算法
基本算法（贪心算法）
自上而下分而治之的方法 开始时，所有的数据都在根节点 属性都是种类字段 (如果是连续的，将其离散化) 所有记录用所选属性递归的进行分割 属性的选择是基于一个启发式规则或者一个统计的度量
编码所需二进位最少的树即为“最佳剪枝 树”
<=30 ov30e.r.c4a0st
student?
yes
>40 credit rating?
no
yes
no
yes
excellent fair
no
yes
基尼指数 Gini Index (IBM
IntelligentMiner)
集合T包含N个类别的记录，那么其Gini指标就是
pj 类别j出现的频率
age pi
<=30 2
30…40 4
>40
3
ni I(pi, ni) 3 0.971 00 2 0.971
Similarly
Gai(inncom )e0.029 Gai(sntude)nt0.151 Gai(cnred_irt atin)g0.048
Decision Tree (结果输出)
age?
挖掘所用的数据来自稳定的环境，人为干 预较少
概述(二)
捕捉新旧数据变化的目的：
挖掘出变化的趋势
例：啤酒——尿布
阻止/延缓不利变化的发生
例：金融危机——银行的信贷策略
差异挖掘算法的主要思想：
合理比较新/旧数据的挖掘结果，并清晰的 描述其变化部分
预备知识一(Building Tree)
A为属性，具有V个不同的取值 信息增益：Gain(A)= I(s1,s2,……,sm) － E(A)
训练集(举例)
ID3算法
age income student credit_rating
<=30 high
no fair
<=30 high
no excellent
30…40 high
no fair
预备知识二(Pruning Tree)
目的：
消除决策树的过适应(OverFitting)问题 实质：消除训练集中的异常和噪声
两种方法：
先剪枝法(Public 算法) 后剪枝法(Sprint 算法)
两种剪枝标准
最小描述长度原则(MDL)
思想：最简单的解释最期望的 做法：对Decision-Tree 进行二进位编码，
>40 medium no fair
>40 low
yes fair
>40 low
yes excellent
31…40 low
yes excellent
<=30 medium no fair
<=30 low
yes fair
>40 medium yes fair
<=30 medium yes excellent