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

第4讲数据分类 决策树 目录 基本概念决策树ID3算法决策树C4 5算法 2 本周学习目标 1 掌握数据分类的基本原理和评价指标2 了解两种决策树算法 3 4 PartI数据分类的基本概念 定义 数据分类是指把数据样本映射到一个事先定义的类中的学习过程即给定一组输入的属性向量及其对应的类 用基于归纳的学习算法得出分类分类问题是数据挖掘领域中研究和应用最为广泛的技术之一 如何更精确 更有效地分类一直是人们追求的目标数据分类的任务通过学习得到一个目标函数f 把每个属性集x映射到一个预先定义的类标号y 5 分类的示例 两类分类示例银行业 区分高端信用卡和低端信用卡医疗诊断 区分正常细胞和癌细胞互联网 区分正常邮件和垃圾邮件多类分类示例油气传输 区分行人走过 汽车碾过 镐刨 电钻等行为文字识别 区分不同的字符 其中汉字识别是一个大类别问题 社会网络 区分中心用户 活跃用户 不活跃用户 马甲用户等 6 示例数据集 数据集包含多个描述属性和一个类别属性一般来说描述属性 连续值或离散值类别属性 只能是离散值 目标属性连续对应回归问题 7 分类问题的形式化描述 8 分类的过程 9 获取数据 预处理 分类决策 分类器设计 获取数据 数值型数据病例中的各种化验数据空气质量监测数据描述性数据人事部门档案资料图片型数据指纹 掌纹自然场景图片很多情况下 需要将上述数据统一转换为数值型数据序列 即形成特征向量 特征提取 10 预处理 为了提高分类的准确性和有效性 需要对分类所用的数据进行预处理去除噪声数据对空缺值进行处理数据降维 特征选择 PCA LDA 11 分类器设计1 划分数据集 给定带有类标号的数据集 并且将数据集划分为两个部分训练集 trainingset 测试集 testingset 划分策略随机抽取法2 1 训练集 测试集 8 1十交叉验证法 10 foldvalidation 将数据集随机地划分为10组之后执行10次循环 在第i次循环中 将第i组数据样本作为测试集 其余的9组数据样本作为训练集 12 分类器设计2 分类器构造 利用训练集构造分类器 分类模型 通过分析由属性描述的每类样本的数据信息 从中总结出分类的规律性 建立判别公式或判别规则在分类器构造过程中 由于提供了每个训练样本的类标号 这一步也称作监督学习 supervisedlearning 13 分类器设计3 分类器测试 利用测试集对分类器的分类性能进行评估 具体方式是首先 利用分类器对测试集中的每一个样本进行分类其次 将分类得到的类标号和测试集中数据样本的原始类标号进行对比由上述过程得到分类器的分类性能 如何评价 14 分类决策 在构造成功分类器之后 通过测试 则可以利用该分类器实际执行分类 15 分类的评价准则 约定和假设 16 分类的评价准则 指标1 精确度 accuracy 是最常用的评价准则代表测试集中被正确分类的数据样本所占的比例反映了分类器对于数据集的整体分类性能 17 分类的评价准则 指标2 查全率 recall 第j个类别的查全率 召回率 表示在本类样本中 被正确分类的样本占的比例代表该类别的分类精度 18 分类的评价准则 指标3 查准率 precision 第j个类别的查准率表示被分类为该类的样本中 真正属于该类的样本所占的比例代表该类别的分类纯度 19 分类的评价准则 指标4 F measure可以比较合理地评价分类器对每一类样本的分类性能它是查全率和查准率的组合表达式其中参数 是可以调节的 通常取值为1 20 分类的评价准则 指标5 几何均值 G mean 它能合理地评价数据集的整体分类性能是各个类别查全率的平方根 当各个类别的查全率都大时才增大同时兼顾了各个类别的分类精度 21 延伸阅读 Jin MaoWei Xiao JieYuan etal Anovelmeasureforevaluatingclassifiers ExpertSystemswithApplications 37 2010 3799 3809 22 关于数据分类的小结 所谓分类即是使用某种分类模型 以对象的若干维描述属性为输入 经过计算输出该对象所属类别的过程数据分类的两个关键步骤是分类器训练 选定合适的分类模型及参数分类器测试 利用合适的指标检验分类器有效性目前已有一些成熟的分类器可供使用决策树支持向量机最近邻 k 近邻 23 24 PartII决策树ID3算法 决策树 是一种以给定的数据样本为基础的归纳学习方法在给定已知类标号的数据集的情况下 采用自顶向下的递归方式来产生一个类似于流程图的树结构树的最顶层节点是根节点最底层节点是叶节点 代表样本的类别根节点和叶节点之间的节点是内部节点决策树方法在根节点和内部节点上根据给定的度量标准来选择最适合的描述属性作为分支属性并根据该属性的不同取值向下建立分支 25 决策树示例 购买保险 26 保险决策树 解决了哪类人更倾向于购买保险的问题 27 年龄 信誉度 公司职员 c1 c1 c2 c1 c2 40 41 50 50 是 否 良 优 决策树向程序语言的转化 if 年龄50 信誉度为良 买保险if 年龄 50 信誉度为优 不买保险 28 ID3算法的原理 核心思想在选择根节点和各个内部节点上的分支属性时 采用信息增益 informationgain 作为度量标准特别说明创建根节点时 X是最初给定的所有数据创建内部节点时 X是上层节点的某个分支对应的数据集 29 ID3算法的原理 期望信息 30 什么情况下信息量更大 分布更平均 vs分布更极端 分布更集中 VS分布更疏散 ID3算法的原理 熵熵值E Af 越小 表示属性Af对数据集划分的纯度越高 31 ID3算法的原理 信息增益 32 ID3算法原理 选择具有较高信息增益的描述属性作为给定数据集X的分支属性 从而创建决策树中的一个节点根据该描述属性的不同取值再创建分支之后对各个分支中的样本子集递归调用上述方法建立下一级子节点当某个分支上的所有数据样本都属于同一个类别时划分停止 形成叶节点或者当某个分支上的样本不属于同一个类别 但是又没有剩余的描述属性可以进一步划分数据集时也形成叶节点 并且用多数样本所属的类别来标记这个叶节点 33 ID3算法示例 该样本集中共包含4个描述属性和1个类别属性 空间容量为14目标是利用ID3思想构建一棵可用于新样本分类的决策树 34 第1步 计算对训练集分类所需的期望信息 已知total 14c1 买保险 的样本数量是n1 9c2 不买保险 的样本数量是n2 5所以P c1 9 14P c2 5 14根据期望信息公式可得 35 第2步 计算A1 公司职员 的熵 A1包含两种取值 是 和 否 利用A1可将X划分为两个子集X1和X2X1中的数据样本都是公司职员 7个 标号为c1的有6个 n11 6标号为c2的有1个 n21 1则可得p11 6 7p21 1 7 36 第2步 计算A1 公司职员 的熵 利用A1可将X划分为两个子集X1和X2X2中的数据样本都不是公司职员 7个 标号为c1的有3个 n12 3标号为c2的有4个 n22 4则可得p12 3 7p22 4 7 37 第2步 计算A1 公司职员 的熵 则计算出A1划分训练集所得的熵为 38 第3步 计算A1 公司职员 的信息增益 39 第4步 求出其他描述属性的信息增益 Gain A2 0 246Gain A3 0 029Gain A4 0 048经比较可知Gain A2 最大 所以选择A2 年龄 作为决策树的根节点进一步将树划分为3个分支 40 第5步 根据根节点划分数据集 年龄 40的子集在此子集内继续检查Gain A1 Gain A3 Gain A4 选取信息增益最大的描述属性作为内部节点 41 第5步 根据根节点划分数据集 年龄41 50的子集该子集中所有样本的类别标号都一样 所以无需继续划分可将它标注为一个叶节点 而且叶节点的类标号为c1 42 第5步 根据根节点划分数据集 年龄 50的子集在此子集内继续检查Gain A1 Gain A3 Gain A4 选取信息增益最大的描述属性作为内部节点 43 ID3算法小结 使用ID3算法的基本思想是采用自顶向下的递归方式 将原始样本空间划分成若干更小的样本空间再对他们单独进行处理其中 选择哪一个描述属性作为新建节点 依据是考察该描述属性的信息增益是否最大 44 45 PartIIIC4 5算法 ID3的不足 1 2 使用信息增益作为属性选择依据带有倾向性 倾向于选择取值较多的属性 为什么 一种可能的解释是 对于较难分类的集合 优先将样本分割到尽可能多的分支中将极大简化分类工作 46 ID3的不足 2 2 无法处理未知值的样本对于个别样本缺失了某项描述属性的情况 无法处理无法处理连续值的样本对于描述属性是连续值的情况 无法处理 47 变化一 使用信息增益比 48 变化二 处理未知值的训练样本 1 2 思想将未知值用最常用的值来替代 较容易 或 依据现有取值的概率分布来估计未知值 较真实 显然 依据思想一 在已知样本中年龄的三个区间分布是50 5人则可以直接指定未知值为 50 49 变化二 处理未知值的训练样本 2 2 思想将未知值用最常用的值来替代 较容易 或 依据现有取值的概率分布来估计未知值 较真实 显然 依据思想二 在已知样本中年龄的三个区间分布是50 5人考虑未知值样本后 分布更新为50 5 5 13人 50 变化三 处理连续值的训练样本 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 的数据样本 显然划分共有total 1种方式从total 1个分割点中选择最佳分割点 对于每一个分割点划分数据集的方式 计算其信息增益比 从中选择信息增益比最大的分割点来划分数据集 51 变化三 处理连续值的训练样本 2 10 示例求利用C4 5算法在连续值描述属性A上的最佳分割点解 第0步 将A的取值升序排列 65 70 70 70 75 78 80 80 80 85 90 90 95 96 第1步 计算vi 65时的信息增益比 52 变化三 处理连续值的训练样本 3 10 解 第1步 计算vi 65时的信息增益比 53 变化三 处理连续值的训练样本 4 10 解 第1步 计算vi 65时的信息增益比 54 变化三 处理连续值的训练样本 5 10 解 第2步 计算vi 70时