定义4.1（分类）：给定数据库D＝｛t1,t.pptVIP

本讲目录 　一　概述 二　预备知识 三　决策树生成(Building Decision Tree 分 类 分类的目的是构造一个分类函数或分类模型（分类器），该模型能把数据库中的数据项映射到某一个给定类别。 定义4.1（分类）：给定数据库D＝｛t1,t2,…,tn｝，元组ti?D，类的集合C＝｛C1,……,Cm｝，分类问题定义为从数据库到类集合的映射f：D?C，即数据库中的元组ti分配到某个类Cj中，有Cj ＝｛ti|f(ti) = Cj，1≤i≤n，且ti∈D｝。 本讲目录 　一　概述 二　预备知识 三　决策树生成(Building Decision Tree 训练集与测试集 训练集：数据库中为建立模型而被分析的数据元组形成训练集。 训练集中的单个元组称为训练样本,每个训练样本有一个类别标记。一个具体样本的形式可为:( v1, v2, ..., vn; c );其中vi表示属性值,c表示类别。 测试集：用于评估分类模型的准确率。 分类的两个阶段 a.模型训练阶段 训练集 b.使用模型 分类阶段 评估准确率（测试集） 对类标号未知的新 数据分类 分类模型的构造方法 机器学习方法： 决策树法知识表示是决策树 规则归纳知识表示是产生式规则 统计方法：知识表示是判别函数和原型事例 贝叶斯法 非参数法(近邻学习或基于事例的学习) 神经网络方法： BP算法,模型表示是前向反馈神经网络模型 粗糙集(rough set)知识表示是产生式规则 本讲目录 　一　概述 二　预备知识 三　决策树生成(Building Decision Tree 决策树 内部节点上选用一个属性进行分割 每个分支代表一个测试输出 叶子节点表示一个类分布 使用决策树进行分类 1 建立决策树，利用训练样本生成决策树模型。 开始，数据都在根节点 递归的进行数据分片 2 修剪决策树 去掉一些可能是噪音或者异常的数据 3 使用决策树对未知数据进行分类 按照决策树上采用的分割属性逐层往下，直 到一个叶子节点 信息增益度度量(ID3/C4.5) 任意样本分类的期望信息： I(s1,s2,……,sm)=－∑Pi log2(pi) (i=1..m) 其中，数据集为S，m为S的分类数目， Pi Ci为某分类标号，Pi为任意样本属于Ci的概率， si为分类Ci上的样本数 由A划分为子集的熵： E(A)= ∑(s1j+ ……+smj)/s * I(s1j+ ……+smj) A为属性，具有V个不同的取值 信息增益：Gain(A)= I(s1,s2,……,sm) － E(A) ID3的基本思想 构造决策树，决策树的每个节点对应一个非类别属性，每条边对应该属性的每个可能值。以信息熵的下降速度作为选取测试属性的标准，即所选的测试属性是从根到当前节点的路径上尚未被考虑的具有最高信息增益的属性。 训练集(举例) 使用信息增益进行属性选择 分类C1: 买电脑 = “是” 分类C2:买电脑 = “否” I(C1, C2) = I(9, 5) =0.940 计算年龄的增益: 因此 相似地 Decision Tree (结果输出) 习题 美国著名的国家篮球队NBA的教练，利用IBM公司提供的数据挖掘工具临场决定替换队员。想象你是NBA的教练，你靠什么带领你的球队取得胜利呢？当然，最容易想到的是全场紧逼、交叉扯动和快速抢断等具体的战术和技术。但是今天，NBA的教练又有了他们的新式武器：数据挖掘。大约20个NBA球队使用了IBM公司开发的数据挖掘应用软件Advanced Scout系统来优化他们的战术组合。例如Scout就因为研究了魔术队队员不同的布阵安排，在与迈阿密热队的比赛中找到了获胜的机会。　　系统分析显示魔术队先发阵容中的两个后卫安佛尼.哈德卫(Anfernee Hardaway)和伯兰.绍(Brian Shaw)在前两场中被评为－17分，这意味着他俩在场上，本队输掉的分数比得到的分数多17分。然而，当哈德卫与替补后卫达利尔.阿姆斯创(Darrell Armstrong)组合时，魔术队得分为正14分。　　在下一场中，魔术队增加了阿姆斯创的上场时间。此着果然见效：阿姆斯创得了21分，哈德卫得了42分，魔术队以88比79获胜。魔术队在第四场让阿姆斯创进入先发阵容，再一次打败了热队。在第五场比赛中，这个靠数据挖掘支持的阵容没能拖住热队，但Advanced Scout毕竟帮助了魔术队赢得了打满5场，直到最后才决出胜负的机会。 * * 商业自动化 主讲教师：陈冬林 第十五讲　DM之决策树武汉理工大学经济学院陈冬林* 　2.现有五种商品的交易记录表，用Apri