新精品课程完整课件(第8讲)---数据分类-决策树.ppt

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