第4章_分类：基本概念、决策树与模型评估分解.ppt

(C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002 (C) Vipin Kumar, Parallel Issues in Data Mining, VECPAR 2002 数据挖掘 分类：基本概念、决策树与模型评价 分类的是利用一个分类函数（分类模型、分类器），该模型能把数据库中的数据影射到给定类别中的一个。 分类 训练集：数据库中为建立模型而被分析的数据元组形成训练集。 训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。 一个具体样本的形式可为:( v1, v2, ..., vn; c );其中vi表示属性值,c表示类别。 测试集：用于评估分类模型的准确率 数据分类——一个两步过程 (1) 第一步，建立一个模型，描述预定数据类集和概念集 假定每个元组属于一个预定义的类，由一个类标号属性确定 学习模型可以用分类规则、决策树或数学公式的形式提供 数据分类——一个两步过程 (2) 第二步，使用模型，对将来的或未知的对象进行分类 首先评估模型的预测准确率 对每个测试样本，将已知的类标号和该样本的学习模型类预测比较 模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比 测试集要独立于训练样本集，否则会出现“过分适应数据”的情况 如果准确性能被接受，则分类规则就可用来对新数据进行分类 有监督的学习 VS. 无监督的学习 有监督的学习（用于分类） 模型的学习在被告知每个训练样本属于哪个类的“监督”下进行 新数据使用训练数据集中得到的规则进行分类 无监督的学习（用于聚类） 每个训练样本的类编号是未知的，要学习的类集合或数量也可能是事先未知的 通过一系列的度量、观察来建立数据中的类编号或进行聚类 分类模型的构造方法 1.机器学习方法： 决策树法 规则归纳 2.统计方法：知识表示是判别函数和原型事例 贝叶斯法 非参数法(近邻学习或基于事例的学习) 3.神经网络方法： BP算法,模型表示是前向反馈神经网络模型 4.粗糙集(rough set)知识表示是产生式规则 一个决策树的例子 决策树的另一个例子 用决策树归纳分类 什么是决策树？ 类似于流程图的树结构 每个内部节点表示在一个属性上的测试 每个分枝代表一个测试输出 每个树叶节点代表类或类分布 决策树的生成由两个阶段组成 决策树构建 开始时，所有的训练样本都在根节点 递归的通过选定的属性，来划分样本 （必须是离散值） 树剪枝 许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪去这种分枝 决策树的使用：对未知样本进行分类 通过将样本的属性值与决策树相比较 为了对未知数据对象进行分类识别，可以根据决策树的结构对数据集中的属性进行测试，从决策树的根节点到叶节点的一条路径就形成了相应对象的类别测试。决策树可以很容易转换为分类规则 决策树分类任务 一个决策树的例子 应用决策树进行分类 应用决策树进行分类 应用决策树进行分类 应用决策树进行分类 应用决策树进行分类 应用决策树进行分类 决策树分类 决策树 有许多决策树算法: Hunt算法 信息增益——Information gain （ID3） 增益比率——Gain ration（C4.5） 基尼指数——Gini index (SLIQ，SPRINT) Hunt 算法 设 Dt 是与结点 t相关联的训练记录集 算法步骤: 如果Dt 中所有记录都属于同一个类 yt, 则t是叶结点，用yt标记 如果 Dt 中包含属于多个类的记录，则选择一个属性测试条件，将记录划分成较小的子集。对于测试条件的每个输出，创建一个子结点，并根据测试结果将Dt中的记录分布到子结点中。然后，对于每个子结点，递归地调用该算法 Hunt算法 决策树 Hunt算法采用贪心策略构建决策树. 在选择划分数据的属性时，采取一系列局部最优决策来构造决策树. 决策树归纳的设计问题 如何分裂训练记录 怎样为不同类型的属性指定测试条件? 怎样评估每种测试条件? 如何停止分裂过程 决策树 Hunt算法采用贪心策略构建决策树. 在选择划分数据的属性时，采取一系列局部最优决策来构造决策树. 决策树归纳的设计问题 如何分裂训练记录 怎样为不同类型的属性指定测试条件? 怎样评估每种测试条件? 如何停止分裂过程 怎样为不同类型的属性指定测试条件? 依赖于属性的类型 标称 序数 连续 依赖于划分的路数 2路划分 多路划分 基于标称属性的分裂 多路划分: 划分数（输出数）取决于该属性不同属性值的个数. 二元划分: 划分数为2，这种划分要考虑创建k个属性值的二元划分的所有2k-1-1种方法. 基于序数属性的划分 多路划分: 划分数（输出