用方法是回归分析
数据分类——一个两步过程 (1)

第一步，也成为学习步，目标是建立描述预先定义的数 据类或概念集的分类器
分类算法通过分析或从训练集“学习”来构造分类器。
训练集由数据库元组（用n维属性向量表示）和他们相对
应的类编号组成；假定每个元组属于一个预定义的类
训练元组：训练数据集中的单个元组
第一步——建立模型
分类算法 训练数 据集
NAME RANK M ike M ary B ill Jim D ave Anne A ssistan t P ro f A ssistan t P ro f P ro fesso r A sso ciate P ro f A ssistan t P ro f A sso ciate P ro f
决策树的基本原理
预测变量 目标变量 类标号属性
记录 样本
类别集合：Class={―优”，“良”，“差”}
根节点 分裂属性 分裂谓词
叶子节点
每一个叶子节点都被确定一个类标号

每一个节点都代表了一个数据集。
根节点1代表了初始数据集D 其它节点都是数据集D的子集。 例如，节点2代表数据集D中年龄小于40岁的那部分样本组成 的数据集。 子节点是父节点的子集。
3.1 决策树概述
决策树(Decision

Tree) 一种描述概念空间的有效的归纳推理办法。 基于决策树的学习方法可以进行不相关的 多概念学习，具有简单快捷的优势，已经 在各个领域取得广泛应用。 决策树是一种树型结构，其中每个内部结 点表示在一个属性上的测试，每个分支代 表一个测试输出，每个叶结点代表一种类 别。
学习模型可以用分类规则、决策树或数学公式的形式提
供
数据分类——一个两步过程 (2)

第二步，使用模型，对将来的或未知的对象进行分类
首先评估模型的预测准确率 对每个测试样本，将已知的类标号和该样本的学习模型类预测比 较 模型在给定测试集上的准确率是正确被模型分类的测试样本的百 分比 测试集要独立于训练样本集，否则会出现“过分拟合”的情况
分类和预测---示例
分类
银行贷款员需要分析数据，来弄清哪些贷款申请
者是安全的，哪些是有风险的（将贷款申请者分 为“安全”和“有风险”两类）
我们需要构造一个分类器来预测类属编号，比如预测
顾客属类
预测
银行贷款员需要预测贷给某个顾客多少钱是安全
的
构造一个预测器，预测一个连续值函数或有序值，常
根结点

树是由节点和分枝组成的层 次数据结构。节点用于存贮 信息或知识，分枝用于连接 各个节点。树是图的一个特 例，图是更一般的数学结构， 不会吱吱叫 如贝叶斯网络。 决策树是描述分类过程的一 种数据结构，从上端的根节 点开始，各种分类原则被引 用进来，并依这些分类原则 将根节点的数据集划分为子 集，这一划分过程直到某种 约束条件满足而结束。
数据预测的两步过程
Biblioteka 数据预测也是一个两步的过程，类似于前面描述的数据分类 对于预测，没有“类标号属性” 要预测的属性是连续值，而不是离散值，该属性可简称 “预测属性” E.g. 银行贷款员需要预测贷给某个顾客多少钱是安全 的 预测器可以看作一个映射或函数y=f(X) 其中X是输入；y是输出，是一个连续或有序的值 与分类类似，准确率的预测，也要使用单独的测试集
3.2 ID3、C4.5与C5.0
熵，是数据集中的不确定性、突发性或随机性的 程度的度量。 当一个数据集中的记录全部都属于同一类的时候， 则没有不确定性，这种情况下的熵就为0。 决策树分裂的基本原则是，数据集被分裂为若干 个子集后，要使每个子集中的数据尽可能的 “纯”，也就是说子集中的记录要尽可能属于同 一个类别。如果套用熵的概念，即要使分裂后各 子集的熵尽可能的小。



决策树学习采用的是自顶向下的递归方法。 决策树的每一层节点依照某一属性值向下分为子节点，待 分类的实例在每一节点处与该节点相关的属性值进行比较， 根据不同的比较结果向相应的子节点扩展，这一过程在到 达决策树的叶节点时结束，此时得到结论。 从根节点到叶节点的每一条路经都对应着一条合理的规则， 规则间各个部分（各个层的条件）的关系是合取关系。整 个决策树就对应着一组析取的规则。 决策树学习算法的最大优点是，它可以自学习。在学习的 过程中，不需要使用者了解过多背景知识，只需要对训练 例子进行较好的标注，就能够进行学习。如果在应用中发 现不符合规则的实例，程序会询问用户该实例的正确分类， 从而生成新的分枝和叶子，并添加到树中。
第3章
分类与预测
主要内容
分类与决策树概述
ID3、C4.5与C5.0
CART
分类 VS. 预测




分类和预测是两种数据分析形式，用于提取描述重要数据类或预测未来 的数据趋势 的模型 分类： 预测类对象的分类标号（或离散值） 根据训练数据集和类标号属性，构建模型来分类现有数据，并用 来分类新数据 预测： 建立连续函数值模型 比如预测空缺值，或者预测顾客在计算机设备上的花费 典型应用 欺诈检测、市场定位、性能预测、医疗诊断 分类是一种应用非常广泛的数据挖掘技术 分类与预测的区别： 当估计的属性值是离散值时，这就是分类； 当估计的属性值是连续值时，这就是预测。

数据集D被按照分裂属性“年龄”分裂为两
个子集D1 和D2
信息增益: Gain(D,年龄)= H(D)–[P(D1)×H(D1)+ P(D2)×H(D2)]
显 然 ， 如 果 D1 和 D2 中 的 数 据 越
“纯”，H(D1)和H(D2)就越小，信 息增益就越大，或者说熵下降得越 多。
监督学习 VS. 无监督学习
监督学习（用于分类）
模型的学习在被告知每个训练样本属于哪个类的
“指导”下进行 新数据使用训练数据集中得到的规则进行分类
无监督学习（用于聚类）
每个训练样本的类编号是未知的，要学习的类集
合或数量也可能是事先未知的 通过一系列的度量、观察来建立数据中的类编号 或进行聚类


决策树学习是以实例为基础的归纳学习。 从一类无序、无规则的事物（概念）中推理出决策树表示的分类规 则。 概念分类学习算法：来源于 Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习 单个概念。 1979年, J.R. Quinlan 给出ID3算法，并在1983年和1986年对 ID3 进行了总结和简化，使其成为决策树学习算法的典型。 Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的 决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算 法。 1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高 了效率。 1993年，Quinlan 进一步发展了ID3算法，改进成C4.5算法。 另一类决策树算法为CART，与C4.5不同的是，CART的决策树 由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习 实例的正例与反例。 其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子 节点处的熵值为零，此时每个叶节点中的实例都属于同一类。
按照这个方法，测试每一个属性的信
息增益，选择增益值最大的属性作为 分裂属性。
信息熵计算举例

令C1对应“是”，C2对应“否”。那么C1有9个样 本，C2有5个样本，所以数据集D的熵为： 9 9 5 5 I ( s1 , s 2 ) I (9,5) log 2 ( ) log 2 ( ) 0.9406 14 14 14 14
YEARS TENURED 3 7 2 7 6 3 no yes yes yes no no
分类规则
IF rank = ‘professor’ OR years > 6 THEN tenured = ‘yes’
第二步——用模型进行分类
分类规则
测试集
未知数据 (Jeff, Professor, 4)


决策树是指具有下列三个性质的树：
每个非叶子节点都被标记一个分裂属性Ai；
每个分支都被标记一个分裂谓词，这个分裂谓
词是分裂父节点的具体依据； 每个叶子节点都被标记一个类标号Cj∈C。
任何一个决策树算法，其核心步骤都是为
每一次分裂确定一个分裂属性，即究竟按 照哪一个属性来把当前数据集划分为若干 个子集，从而形成若干个“树枝”。
NAME Tom M erlisa G eorge Joseph
RANK Y E A R S TE N U R E D A ssistant P rof 2 no A ssociate P rof 7 no P rofessor 5 yes A ssistant P rof 7 yes
Tenured?
更令人满意。
设计分类停止条件，实际应用中数据的属性很多，真正有分类意义的属性
往往是有限几个，因此在必要的时候应该停止数据集分裂：
该节点包含的数据太少不足以分裂， 继续分裂数据集对树生成的目标(例如ID3中的熵下降准则)没有贡献， 树的深度过大不宜再分。

通用的决策树分裂目标是整棵树的熵总量最小，每一步分裂时，选择使熵减小 最大的准则，这种方案使最具有分类潜力的准则最先被提取出来

鼠 鼠 短 长 鹿
个子大 脖子短 鼻子长 可能是大象
在陆地 上 可能是犀 牛
可能是大 在 水象 里 可能是河 马

构造一棵决策树要解决四个问题：
收集待分类的数据，这些数据的所有属性应该是完全标注的。 设计分类原则，即数据的哪些属性可以被用来分类，以及如何将该属性量
化。
分类原则的选择，即在众多分类准则中，每一步选择哪一准则使最终的树