第4讲数据分类-决策树.ppt

1、第4讲 数据分类-决策树,目录,基本概念 决策树ID3算法 决策树C4.5算法,本周学习目标,1.掌握数据分类的基本原理和评价指标 2.了解两种决策树算法,Part I 数据分类的基本概念,定义,数据分类 是指把数据样本映射到一个事先定义的类中的学习过程 即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类 分类问题是数据挖掘领域中研究和应用最为广泛的技术之一，如何更精确、更有效地分类一直是人们追求的目标 数据分类的任务 通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y,分类的示例,两类分类示例 银行业：区分高端信用卡和低端信用卡 医疗诊断：区分正常细胞和癌

2、细胞 互联网：区分正常邮件和垃圾邮件 多类分类示例 油气传输：区分行人走过、汽车碾过、镐刨、电钻等行为 文字识别：区分不同的字符（其中汉字识别是一个大类别问题） 社会网络：区分中心用户、活跃用户、不活跃用户、马甲用户等,示例数据集,数据集包含多个描述属性和一个类别属性 一般来说 描述属性：连续值或离散值 类别属性：只能是离散值（目标属性连续对应回归问题）,分类问题的形式化描述,分类的过程,获取数据,预处理,分类决策,分类器设计,获取数据,数值型数据 病例中的各种化验数据 空气质量监测数据 描述性数据 人事部门档案资料 图片型数据 指纹、掌纹 自然场景图片 很多情况下，需要将上述数据统一转换为数

3、值型数据序列，即形成特征向量（特征提取）,预处理,为了提高分类的准确性和有效性，需要对分类所用的数据进行预处理 去除噪声数据 对空缺值进行处理 数据降维（特征选择）-（PCA、LDA）,分类器设计1-划分数据集,给定带有类标号的数据集，并且将数据集划分为两个部分 训练集（training set） 测试集（testing set） 划分策略 随机抽取法 2/1训练集/测试集8/1 十交叉验证法（10-fold validation） 将数据集随机地划分为10组 之后执行10次循环，在第i次循环中，将第i组数据样本作为测试集，其余的9组数据样本作为训练集,分类器设计2-分类器构造,利用训练集构造

4、分类器（分类模型） 通过分析由属性描述的每类样本的数据信息，从中总结出分类的规律性，建立判别公式或判别规则 在分类器构造过程中，由于提供了每个训练样本的类标号，这一步也称作监督学习（supervised learning）,分类器设计3-分类器测试,利用测试集对分类器的分类性能进行评估，具体方式是 首先，利用分类器对测试集中的每一个样本进行分类 其次，将分类得到的类标号和测试集中数据样本的原始类标号进行对比 由上述过程得到分类器的分类性能（如何评价？）,分类决策,在构造成功分类器之后（通过测试），则可以利用该分类器实际执行分类,分类的评价准则-约定和假设,分类的评价准则-指标1,精确度（acc

5、uracy） 是最常用的评价准则 代表测试集中被正确分类的数据样本所占的比例 反映了分类器对于数据集的整体分类性能,分类的评价准则-指标2,查全率（recall） 第j个类别的查全率（召回率）表示在本类样本中，被正确分类的样本占的比例 代表该类别的分类精度,分类的评价准则-指标3,查准率（precision） 第j个类别的查准率表示被分类为该类的样本中，真正属于该类的样本所占的比例 代表该类别的分类纯度,分类的评价准则-指标4,F-measure 可以比较合理地评价分类器对每一类样本的分类性能 它是查全率和查准率的组合表达式 其中参数是可以调节的，通常取值为1,分类的评价准则-指标5,几何均值

6、（G-mean） 它能合理地评价数据集的整体分类性能 是各个类别查全率的平方根，当各个类别的查全率都大时才增大 同时兼顾了各个类别的分类精度,延伸阅读,Jin-Mao Wei, Xiao-Jie Yuan, et al. A novel measure for evaluating classifiers, Expert Systems with Applications, 37(2010):3799-3809,关于数据分类的小结,所谓分类即是使用某种分类模型，以对象的若干维描述属性为输入，经过计算输出该对象所属类别的过程 数据分类的两个关键步骤是 分类器训练：选定合适的分类模型及参数 分类器

7、测试：利用合适的指标检验分类器有效性 目前已有一些成熟的分类器可供使用 决策树 支持向量机 最近邻/k-近邻,Part II 决策树ID3算法,决策树,是一种以给定的数据样本为基础的归纳学习方法 在给定已知类标号的数据集的情况下，采用自顶向下的递归方式来产生一个类似于流程图的树结构 树的最顶层节点是根节点 最底层节点是叶节点：代表样本的类别 根节点和叶节点之间的节点是内部节点 决策树方法在根节点和内部节点上根据给定的度量标准来选择最适合的描述属性作为分支属性 并根据该属性的不同取值向下建立分支,决策树示例-购买保险,保险决策树,解决了哪类人更倾向于购买保险的问题,年龄,信誉度,公司职员,c1,

8、c1,c2,c1,c2,=40,4150,50,是,否,良,优,决策树向程序语言的转化,if (年龄50 & 信誉度为良) 买保险 if (年龄50 & 信誉度为优) 不买保险,ID3算法的原理,核心思想 在选择根节点和各个内部节点上的分支属性时，采用信息增益（information gain）作为度量标准 特别说明 创建根节点时，X是最初给定的所有数据 创建内部节点时，X是上层节点的某个分支对应的数据集,ID3算法的原理,期望信息,什么情况下信息量更大？ 分布更平均？vs 分布更极端？ 分布更集中？VS 分布更疏散？,ID3算法的原理,熵 熵值E(Af)越小，表示属性Af对数据集划分的纯度越

9、高,ID3算法的原理,信息增益,ID3算法原理,选择具有较高信息增益的描述属性作为给定数据集X的分支属性，从而创建决策树中的一个节点 根据该描述属性的不同取值再创建分支 之后对各个分支中的样本子集递归调用上述方法建立下一级子节点 当某个分支上的所有数据样本都属于同一个类别时划分停止，形成叶节点 或者当某个分支上的样本不属于同一个类别，但是又没有剩余的描述属性可以进一步划分数据集时也形成叶节点，并且用多数样本所属的类别来标记这个叶节点,ID3算法示例,该样本集中共 包含4个描述 属性和1个类别 属性，空间容量 为14 目标是利用ID3 思想构建一棵 可用于新样本 分类的决策树,第1步：计算对训练

10、集分类所需的期望信息,已知 total=14 c1(买保险)的样本数量是n1=9 c2(不买保险)的样本数量是n2=5 所以 P(c1)=9/14 P(c2)=5/14 根据期望信息公式可得,第2步：计算A1（公司职员）的熵,A1包含两种取值：“是”和“否” 利用A1可将X划分为两个子集X1和X2 X1中的数据样本都是公司职员（7个） 标号为c1的有6个，n11=6 标号为c2的有1个，n21=1 则可得 p11=6/7 p21=1/7,第2步：计算A1（公司职员）的熵,利用A1可将X划分为两个子集X1和X2 X2中的数据样本都不是公司职员（7个） 标号为c1的有3个，n12=3 标号为c2的

11、有4个，n22=4 则可得 p12=3/7 p22=4/7,第2步：计算A1（公司职员）的熵,则计算出A1划分训练集所得的熵为,第3步：计算A1（公司职员）的信息增益,第4步：求出其他描述属性的信息增益,Gain(A2)=0.246 Gain(A3)=0.029 Gain(A4)=0.048 经比较可知Gain(A2)最大，所以选择A2（年龄）作为决策树的根节点 进一步将树划分为3个分支,第5步：根据根节点划分数据集,年龄=40的子集 在此子集内继续检查Gain(A1)、Gain(A3)、Gain(A4) 选取信息增益最大的描述属性作为内部节点,第5步：根据根节点划分数据集,年龄4150的子集

12、 该子集中所有样本的类别标号都一样，所以无需继续划分 可将它标注为一个叶节点，而且叶节点的类标号为c1,第5步：根据根节点划分数据集,年龄50的子集 在此子集内继续检查Gain(A1)、Gain(A3)、Gain(A4) 选取信息增益最大的描述属性作为内部节点,ID3算法小结,使用ID3算法的基本思想是 采用自顶向下的递归方式，将原始样本空间划分成若干更小的样本空间 再对他们单独进行处理 其中，选择哪一个描述属性作为新建节点，依据是考察该描述属性的信息增益是否最大,Part III C4.5算法,ID3的不足（1/2）,使用信息增益作为属性选择依据 带有倾向性，倾向于选择取值较多的属性 为什么

13、？ 一种可能的解释是：对于较难分类的集合，优先将样本分割到尽可能多的分支中将极大简化分类工作,ID3的不足（2/2）,无法处理未知值的样本 对于个别样本缺失了某项描述属性的情况，无法处理 无法处理连续值的样本 对于描述属性是连续值的情况，无法处理,变化一：使用信息增益比,变化二：处理未知值的训练样本（1/2）,思想 将未知值用最常用的值来替代（较容易） 或，依据现有取值的概率分布来估计未知值（较真实） 显然：依据思想一，在已知样本中年龄的三个区间分布是 50，5人 则可以直接指定未知值为“50”,变化二：处理未知值的训练样本（2/2）,思想 将未知值用最常用的值来替代（较容易） 或，依据现有取

14、值的概率分布来估计未知值（较真实） 显然：依据思想二，在已知样本中年龄的三个区间分布是 50，5人 考虑未知值样本后，分布更新为 50，5+5/13人,变化三：处理连续值的训练样本（1/10）,思想 将所有数据样本按照连续型描述属性Ac的具体取值，由小到大进行升序排列，得到的属性值取值序列A1c,A2c,.,Atotalc 在A1c,A2c,.,Atotalc中生成total-1个分割点，第i个分割点的取值设置为vi=(Aic+A(i+1)c)/2或者vi=Aic 该分割点将数据集划分为两个子集，即描述属性Ac的取值在区间A1c,vi的数据样本和在区间(vi,Atotalc的数据样本，显然划分

15、共有total-1种方式 从total-1个分割点中选择最佳分割点。对于每一个分割点划分数据集的方式，计算其信息增益比，从中选择信息增益比最大的分割点来划分数据集,变化三：处理连续值的训练样本（2/10）,示例 求利用C4.5算法在连续值描述属性A上的 最佳分割点 解： 第0步，将A的取值升序排列 65,70,70,70,75,78,80,80,80,85,90,90,95,96 第1步，计算vi=65时的信息增益比,变化三：处理连续值的训练样本（3/10）,解： 第1步，计算vi=65时的信息增益比,变化三：处理连续值的训练样本（4/10）,解： 第1步，计算vi=65时的信息增益比,变化三：处理连续值的训练样本（5/10）,解： 第2