【毕业学位论文】（Word原稿）基于ROC分析的分类器性能评估-计算机科学与技术

本科毕业设计（论文）说明书 基于 析的分类器性能评估 学 院 计算机科学与工程 专 业 计算机科学与技术 学生姓名 指导教师 提交日期 2010年 5 月 26日 华 南 理 工 大 学 毕 业 设 计 （论文） 任 务 书 正文小四号宋体，行距为固定值 20 磅 兹发给 2006 级计科 (2) 班学生 毕业设计（论文）任务书，内容如下： 文）题目： 基于 析的分类器性能评估 （ 1） （ 2） （ 3） （ 4） （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） 文）任务书于 年 月 日发出，应于 年 月 日前完成， 然后提交毕业考试委员会进行答辩。 专业教研组（系）、研究所负责人 审核 年 月 日 指导教师 签发 年 月 日 毕业设计（论文）评语： （ 应包括平时表现、论文质量、答辩 表 现等内容 ） 毕业设计（论文）总评成绩： 毕业设计（ 论文）答辩负责人签字： 年 月 日 基于 析的分类器性能评估 摘要 I 摘要 分类器评估是数据挖掘与机器学习领域的一个研究热点和难题。研究人员不断地寻找更有效的分类器评估方法，准确性标准 目前分类器性能的主要评估标准，但准确性评估标准存在着很多缺点。近年来， 试者操作特征） 曲线分析方法越来越多的应用到数据挖掘与机器学习中，成为分析和预测机器学习算法的一个有效工具。理论证明，基于 析的 法是优于准 确率评估方法的。首先，它能考虑到类的不同分布，当存在数据不平衡的情况时，不同的数据分布，将得到不同的分类结果，而准确率评估默认所有的数据集都是平衡数据集；其次，它能考虑到不同种类的错误分类代价，而准确率评估默认了所有的错误代价都是相同的。但是 估方法只适用在二类分类问题。如何进行多类分类器评估是个难点。本文提出利用纠错输出码 原理，将多个问题转换成多个二类分类问题，然后计算每个二类分类器的 ，再求其平均值，得到的评价 ，用 作为多类分类器性能 评估 的标准。 关键词： 分类 算法； 试者操作特征 ； 能评估 基于 析的分类器性能评估 I is a a in of to is of of to an in OC is of of it of is in of to a as it of UC is to to is to to UC of UC is of a 于 析的分类器性能评估 目录 目 录 第一章 绪论 . 1 析的研究背景 . 1 析的研究意义 . 2 文主要工作 . 2 容安排 . 3 第二章 分类算法的介绍及其性能评估标准 . 1 类算法的介绍 . 1 类的概念和目的 . 1 要的分类方法 . 2 统分类器评估方法 . 2 类器的评估标准 . 2 何评估分类算法的准确率 . 4 统评估方法的局限性 . 5 第三章 析介绍 . 7 析的基础 . 7 类器评价标准 . 12 法的优势 . 14 类分类器的 算方法 . 16 第四章 基于二类分类器的 线生成算法 . 17 于离散分类器的 线生成算法 . 17 于概率分类器的 线生成算法 . 18 种分类器的比较与分析 . 20 第五章 多类问题转化成二类问题 . 22 码介绍 . 22 码方法概述 . 23 全码编码原理 . 23 用完全码求解 . 24 第六章 实验结果与说明 . 25 验平台构建 . 25 于分类器的输出评估其性能 . 25 基于 析的分类器性能评估 目录 估离散分类器的输出结果 . 25 估概率分类器的输出结果 . 26 基准数据库上评估分类器 . 27 准数据集评估二类分类器 . 27 准数据集评估多类分类器 . 34 章小结 . 36 第七章 结论 . 37 参考文献 . 38 致谢 . 39 基于 析的分类器性能评估 绪论 1 第一章 绪论 析的研究背景 机器学习是人工智能的核心研究领域之一，它利用经验改善系统自身的性能。机器学习起源于人工智能对人类学习能力的追求，传统的研究几乎完全局限在人工智能这一领域中，而现在机器学习已经开始进入了计算机科学的不同领域，甚至其他学科。 由于近 20年的快速发展，机器学习已经具备了一定的解决实际问题的能力，在众多的学科领域都得以应用，我们日常可以见到的应用如防火墙、生物信息、搜索引擎等。这些应用的支撑技术都来自于机器学习。现阶段对机器学习的研究可能不再过多地强调模拟人的学习能力，而是把机器学习真正当成一种支持技术，为其它领域服务 1 传统的机器学习技术基本上只考虑平衡数据，假设测试数据上的样例分布与训练数据具有同分布 其是在统计学，医疗诊断，模式识别，决策理论等领域。其次，目前的机器学习技术主要基于假设：处理第 一类错误 (弃真错误 )和第二类错误 (取伪错误 )的代价相同。然而在实际应用中我们会发现“错误”之间是存在区别的，大多数领域中的错误代价都不一样。以乳腺癌诊断为例，“将病人误诊为健康人的代价”与“将健康人误诊为病人的代价”是不同的。以信用卡盗用检测为例，“将盗用误认为正常使用的代价”与“将正常使用误认为盗用的代价”是不同的。但是传统机器学习技术基本上只考虑相同代价。 这些数据特征往往被传统机器学习算法忽略，为了使机器学习方法得到更广泛的应用，需要反思过去机器学习领域中的基本假设，基本概念和学习算法等。首先应该是对 学习方法优劣度量标准的重新思考。 价不敏感，直观以及可理解性等在评价和比较分类器问题上的优势足以使它在代价敏感等学习领域代替正确率成为更好的度量标准。 基于 析的分类器性能评估 绪论 2 析的研究意义 监督学习中的分类算法一直是机器学习研究的核心主题。分类学习算法从带有类标的训练集上构造一个拥有预测功能的分类器，它用于提取描述重要数据类别的模型或预测未来的数据趋势，为电信、银行、保险、零售、医疗等诸多行业提供科学决策支持。 在国内， 应用在医疗领域应用已经很成熟，但是在机器学习领域还很少看到关于 研究成果。 析主要应用环境如代价敏感学习，集成学习，决策支持敏感应用已经开始受到广泛重视。 0 世纪 50 年代起源于统计决策理论 ,用来说明分类器命中率和误报警率之间的关系 ,最早在第二次世界大战中应用于雷达信号观察能力的评价 ,后来使用在晶体管和心理物理学等的相关研究中。 1960年由后 1980 年前后 ,此时 ,而且被导入了核医学成像领域 ,随后被用于诊断放射学实验室医疗癌症的筛选和精神病的诊断尤其是医疗影像诊断准确性的评价。 等的研究成果为近十年来 ,在人工智能的一些领域也有相关地引进 ,如 :机器学习 ,多代理系统 ,智能决策支持和专家系统等。 (1989)最早将 他证明了 文主要工作 本文首先 介绍了 析的研究背景和研究意义，介绍了 析的发展历程，并说明了 析技术在评价和比较分类器上的优势。同时， 本为阐述了正确率分析方法的发展历程，以及正确率分析方法的局限性，在此基础上引出 析方法的优势，并分析其发展形势。本文全面介绍了 析方法的基础，并在 有的局限性即只能处理两类别的数据上，提出了一种有效的解决办法，以处理多类别数据。目前存在的多类别方法主要有三类，第一类方法是直接扩展二维 间到多维空间，通过改变坐标轴位置或者改变表示方法等手 段来扩展，但这种方法难以表述和理解，并且计算复杂度非常的高；第二类就是扩展 概念；第三类就是把多类别转化成个二类别问题，将多类别 化成基于 析的分类器性能评估 绪论 3 多个二类别 估。本文在 机器学习平台 件上开发。 容安排 本文共分为六章，第一章介绍了 析方法的发展背景及其研究的背景意义，第二章介绍了分类算法及其性能的评估标准，第三章主要介绍了 析技术，使用数据环境和衡量理论两方面阐述了 为评价标准的优越性，分析了多类 量技术目前的研究概况，并说明了现有方法的优势 和不足。第四章介绍了几种将多类问题转化为二类问题的方法 ， 将 于多类 量的方法 ，并说明如何使用完全码编码求解 五章在基准数据库上评估各种分类器的性能，并给出评估结果。第六章总结并指出将要做的工作。基于 析的分类器性能评估 分类算法的介绍及其性能评估标准 1 第二章 分类算法的介绍及其性能评估标准 类算法的介绍 监督学习中的分类算法一直是机器学习研究的核心主题。分类学习算法从带有类标的训练集上构造一个拥有预测功能的分类器，它用于提取描述重要数据类别的模型或预测未来的数据趋势 4，为电信、银行、保险、零售、医疗等诸多行业提供科学决策支持。分类学 习的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每一个类别找到一种准确的描述或者模型。由此生成的类别描述用来对未来测试数据进行分类。尽管这些未来的测试数据的类别标签是未知的，我们仍可以由此预测这些新数据所属的类别。我们也可以由此对数据中的每一个类别有更好的理解。也就是说我们获得了对这个类别的知识。 用于学习分类模型的传统算法有很多，如决策树方法，神经网络，贝叶斯分类， 为本文的实验主要基于决策树方法，本文将主要介绍决策树算法。同时分类算法还与其它智能算法的经验结合发展出基于粗 糙集的分类方法，基于遗传算法的分类算法等 类的概念和目的 分类是数据挖掘三大核心技术 (关联规则、分类、聚类 ) 之一 ,其实质是产生一个目标函数 f ,该函数将输入数据集的属性集 x 映射到已经定义的类标签 y 上。该目标函数通常也被称为分类模型或分类器。当前 , 分类在很多领域都得到了应用和推广。迄今为止 ,已经发展了很多种分类器。例如 , 决策树、朴素贝叶斯、神经网络、支持向量机等。这些分类器分别采用不同的学习算法建立模型 ,该模型应尽量拟合输入数据集的属性集与类别之间的关系。第一阶段 ,采用学习算法 ,通过对训练集进行归 纳学习得到分类模型 ; 第二阶段 , 将已经学习得到的分类模型用于测试集 , 对测试集中未知类别的实例进行分类 ,即问号处最终会取得训练集中类别的某个值。很显然 ,通过训练集产生的分类模型未必是最佳的 ,这就导致对测试集的分类可能产生错误。而人们希望尽量得到性能最佳的分类模型 , 这使得对分类器性能的评价至关重要。只有通过优秀的评价标准才能选择出性能更好的分类器。 基于 析的分类器性能评估 分类算法的介绍及其性能评估标准 2 要的分类方法 决策树方法以其易被人理解、需要信息少、效率及准确率较高等优点在机器学习领域占据着重要地位。决策树方法从产生至今，先后涌现出多种算法，包括 于人机交互的方法等。他们的共同特点是对训练样本集进行训练后都会生成一棵形如二叉或多叉的决策树。树的叶子节点代表某一类别，非叶 子 节点 (内节点 )包括根节点代表某个一般属性 (非类别属性 )的一个测试，测试的结果形成非叶 子 节点的一个分枝。从根节点到叶子节点的一条路径形成一条分类规则，一棵决策树能够很方便的转化为若干条分类规则。人们可以依据分类规则直观地对未知类别的样本进行预测。其中，选择测试属性和划分样本集是构建决策树的关键环节。不同的决策树算法在此使用的 技术不尽相同。 目前在数据挖掘软件中运用的最早也是最多的分类算法是神经网络，它具有对非线性数据快速建模的能力，通过对训练集的反复学习来调节自身的网络结构和连接权值，并对未知的数据进行分类和预测。但是，神经网络从某种意义上说是一种启发式的学习机，本身有很大经验的成分，为了克服传统神经网络方面不可避免的难题， 出了一种新的神经网络支持向量机。 一种基于统计的学习方法，它是对结构化风险最小归纳原则的近似，其理论基础是统计学习理论。为了最小化期望风险的上界， 固定学习机经验风险的条件下最 小化 信度。 支持向量机通过某种事先选择的非线性映射 (核函数 )将输入向量映射到一个高维特征空间，在这个空间中构造最优分类超平面。因此，使用 行数据集分类工作的过程为：首先，通过预先选定的一些非线性映射将输入空间映射到高维特征空间，使得在高维属性空间中有可能对训练数据实现超平面的分割，避免了在原输入空间中进行非线性曲面分割计算。 据集形成的分类函数具有这样的性质：它是一组以 持向量 )为参数的非线性函数的线性组合，因此分类函数的表达式仅和 独立与空间的维度。在处理高维输入空间 的分类时，这种方法尤其有效。 统分类器评估方法 类器的评估标准 目前 ,分类器性能评价标准很多 ,其中比较常用的主要有准确 率 或错误率、查全率、查准率和 5。为了清楚地认识这些评价标准 ,首先介绍一下混合矩阵。 基于 析的分类器性能评估 分类算法的介绍及其性能评估标准 3 在运用分类器对测试集进行分类时 ,有些实例被正确分类 ,有些实例被错误分类 ,这些信息可以通过混合矩阵反映出来。表 1 是一个两类问题下混合矩阵的例子。 预测类别 + - 实际类别 + 正确的正例 误的负例 错误的正例 确的负例 1：两类问题的混淆矩阵 在混 合矩阵中 , 主对角线上分别是被正确分类的正例个数 ( ) 和被正确分类的负例 的 个数 ( ) ,次对角线上依次是被错误分类的负例 的 个数 ( ) 和被错误分类的正例个数 ( ) 。那么 ,实际正例数 ( P) = 实际负例数 ( N) = 实例总数 ( C) = P +N 。很显然 ,一个混合矩阵已经能够显示出评价分类器性能的一些必要信息 , 但是 , 为了更方便地比较不同分类器的性能 ,从混合矩阵中总结得出上述一些常用的数字评价标准。 1) 准确度（ 义 为正确分类的测试实例个数占测试实例总数的比例，即， 2) 错误率（ 定义 为错误分类的测试实例个数占测试实例总数的比例，即， 3) 查准率（ 义为正确分类的正例个数占分类为正例的实例个数的比例，即， 4) 查全率（ 义为正确分类的正例个数占实际正例个数的比例，即， 5) 即是查全率与查准率的调和平均数 ，即， 使用这些评价标准可以对分类器进行评估 ,尤其是其中的准确度或错误率 ,是比较常用的分类器性能评价标准。但是 ,所有这些性能评价标准都只在一个操作点有效 ,这 个操作点即是选择使得错误概率最小的点 6。而且 ,其中大部分评价标准都有一个共同的弱点 ,即它们对于类 的 分布的改变显得不够强壮 7。当测试集中正例和负例的比例改变时 ,它们可能不再具基于 析的分类器性能评估 分类算法的介绍及其性能评估标准 4 有良好的性能 ,有时甚至不能被接受。 何评估分类算法的准确率 一般认为可以从三个方面来评价分类器：预测正确率，计算复杂度，模型描述的简洁度。当然模型结果的可理解性，算法的可扩展性针对特殊应用也是非常重要。几乎所有的领域，都希望越准越好，提高泛化能力是永远的追求。估计分类器的正确率显然是分类器指标中最重要的，它使得我们可以估计一个给 定的分类算法对未见数据正确分类的正确率。例如，如果先前的数据用于训练分类算法，以便预测顾客的购物行为，我们希望估计该分类算法预测未来顾客购物行为的正确率。正确率也可以用来比较不同的分类算法。 由于学习算法对数据过分特化，使用训练数据导出分类算法，然后评估分类算法，可能错误地导致过于乐观的估计，下面我们将介绍一些评估分类算法正确率的方法。 保持 (在保持方法中，给定数据随机地划分成两个独立的集合：训练集和测试集。通常三分之二的数据分配到训练集，其余三分之一分配到测试集。使用训练集导出分类算法 模型，其正确率用测试集评估。评估是保守的，因为只有一部分促使数据用于导出分类模型，随机子选样是保持方法的一种变形，它将保持方法重复 K 次，总体正确率估计取每次迭代正确率的平均值。这种方法适用于大量的数据条件下。 K 折交叉验证 假定一个算法 A 和一个小数据集 S，当 A 在一个与 S 具有相同大小的新的训练集上训练时， A 产生的分类器的正确率是多少？ 出用分层 10 折交叉验证方法计算算法的正确率。在这种情况下，它能产生相当好的估计。需要注意的是在任何重复采样方法中，我们不能在一个大小和 S 精确相同的训练集上训练 A，相 反，我们在样例个数明显少一些的数据集上训练， (例如 10 折交叉验证中使用 S 全部大小的 90%)并且基于学习算法性能随着训练数据大小连续变化的假设。这个假设通过执行额外的交叉验证研究被实验证实成立，甚至在非常小的数据集也成立。但是假设成立的条件与训练集 S 的大小并不直接相关，在某些情况下，学习曲线形状的结果显示，这种正确率连续变化的假定不一定成立。然而在许多实际应用中，这种假设是合理的。 K 折交叉验证 (也称 K 折交叉确认 )方法首先将初始数据被划分成 K 个互不相交的子集或“折” ， 个折的大小大致相等。 训练和测试进行 K 次。在第 i 次迭代， 余的子集都用于训练分类模型。即是，第一次迭代的分类法在子集 ，训练，而在 测试，第二次迭代在的分类法在子集 ， 训练，而在测试；如此下去。正确率估计是 K 次迭代正确分类数除以初始数据中样本总数。在分层交叉确认中，折被分层，使得每个折中样本的类分布与在初始数据中大致相同。评估分基于 析的分类器性能评估 分类算法的介绍及其性能评估标准 5 类法正确率的其它方法包括引导 (留一交叉验证 ( 前者使用一致的、带回放的选样，选取给定的训练实例；后者是 K折交叉确认，这里 K 为初始样本数 S。一般地，建议使用调整的 10 折交叉确认，因为它具有相对低的偏置和方差。使用这些技术评估分类算法的正确率增加了总体的计算时间，但是对于由多个分类算法中选择一个好的分类算法仍然是有用的。 K 折交叉确认适用于中量的数据集而 适用于小量的数据集。 统评估方法的局限性 分类学习算法从带有类标识的训练集上构造一个拥有预测功能的分类器 ,它用于提取描述重要数据类别的模型或预测未来的数据趋势 4,它们的预测能力通常用在 测试集上预测正确率 (来衡量 ,这类度量标准在当前的实际应用中发现了很多限制和不足。主要出现在以下两种情况 : (1) 在数据不平衡的情况下 ,即数据的类别分布比例相差很大时 ,正确率并不能准确表达分类器的性能。在实际应用中 ,类分布比例在 10 和 102 刻度上十分普遍 ,甚至在某些领域达到了 106,如正确率达到 分类算法可能比随机猜测所有的信用卡都是“正常使用”的正确率还要低 ,此时很高的正确率并不能够充分说明分类器性能的好坏 ;或者当正确率用在动态环境 ,诸如网页信息获取 ,查询到的不相关网页的数量大 大的超过想要查询的网页数量 ,并且随着时间的推移 ,这个比例随着网页数量还会稳步地增加。此时 ,测试集和训练集上的类别分布变化 ,如果用正确率评价 ,一些在训练集中正确率很高的分类器性能可能会急剧下降 ,这显然会影响对算法的客观评价。 (2) 当分类错误代价不相等时 ,正确率只能保证出现错误的数量最小 ,但是并不能保证是总体代价最小。例如“将信用卡盗用误认为正常使用”对于银行发生的损失是将“正常使用误认为盗用”的很多倍 ,甚至在一些与人身生命安全相关的重要决策中 ,这种错误代价的关系往往无法具体衡量。从实用角度 讲 ,分类学习算法 应该尽量地减少代价高的错误出现 ,而不是着重于减少错误数量。此外 ,因为错误代价的不同 ,在典型信息获取过程中 ,需要高的准确度 (在医疗影像诊断中 ,需要高的召回率 (这些应用中并不需要以正确率作为选择合适算法的标准。另外在越来越多的应用中 ,需要有些分类器能够提供分类的可靠性 ,相似度或者对每个样例分类质量的数值估计。也就是说不仅希望模型为每个样例预测出一个类别 ,而且希望它能为每次预测提供一个可靠性估计。因此在当前的应用中 ,正确率已经显示出了很多的不足和缺陷 ,它已不再能够充分描述分类 器的性能或者比较多个分类算法的优劣。 析对类别分布、错误代价不敏感、直观以及可理解性等特性 ,逐渐使它代替正基于 析的分类器性能评估 分类算法的介绍及其性能评估标准 6 确率成为更好的度量方法。 基于 析的分类器性能评估 析介绍 7 第三章 析介绍 早将 析技术引用到机器学习领域中，他说明了 线的值估计和比较算法。 析技术在最近几年越来越多的应用到机器学习领域中全面度量分类算法的性能。 析技术不仅是一种通用图形化性能的方法，而且 线的独特属性使它在类别分布不平衡或者分类错误代价不相等的领域，这使它在类别分布未知的领域和代价敏感学习中变得越来越重要 。此外， 的 另外一个重要的特征就是它也可以给出清楚的解释，在多类 题中我们将更加深刻的领会这个特征的重要。 析对类别分布、代价不敏感，直观以及可理解性等在评价和比较分类器问题上的优势足以使它代替正确率成为更好的度量标准。 析的基础 对于二类别分类器，给定一个分类器和一个实例，存在着四种这样的可能的输出：实例是正的，并且分类器的预测也是正的，那么 1，如果分类器的预测是负的，那么 1，实例是负的并且分类器的预测也是负的，那么 1，如果分类器预测是正的，则 1。 所以给定一个二类分类器和测试数据集，我们可以构造一个 2 2 的混淆矩阵来表示分类算法的分类结果。 定义分类算法将负例误分为正例的个数与所有负例的比值为 将正例分为正例的个数与所有正例的比值为 是以 横轴，以 纵轴的二维图。即 绘制 间的关系。如果 正例相对于负例在测试集上的比例发生了变化，分类器在 个特征表明 对类分布不敏感。 算法分类器中包含两种分类器，一种是硬分类器（ 者离散分类器，另一种是软分类器（ 1） 硬分类器（ 硬分类器的输出结果仅仅是一个类别标签。这样的分类器在对数据集进行分类的时候，仅仅产生一个混淆矩阵，因此一个算法对应 间上的一个点 。在 间上，有几个基于 析的分类器性能评估 析介绍 8 重要的点，一个是左下的点（ ， ），意味将每一个实例都预测为负例，这个点称为负分类点；一个是右上方的点（ ， ），意味着讲每一个实例都预测为正例，这个点橙味正分类点；点（ ， ）是最理想的分类点，代表最理想的分类器，它的分类是完全正确的。 一般来说，位于 间上左上位置的分类器，其性能较其它分类器好。 在 左边靠近 X 轴的分类器 (如图 的 法 )行为比较保守，算法严格检验正例，使他们的 小，但是他们经常也会拒绝接受正例，因此会产生低的 右上的分类器，如图 的 法，则比较激进，他们对正例检查很弱，因此分类结果大多是正例，但是他们也经常有高的 有大量负例的实际应用数据中，在 更左边的分类器性能会较好，而且这种情况相对比较多，如搜索引擎命中的网页往往与用户要求一致的比例很小。 中对角线 Y=X 描述了一个随机猜测的分类器。例如，如果分类器以 概 率 随机猜测为正例，那么将有一半的正例和负例分类正确。这个分类器在 间中对 应 的点为 (如果以 概率猜测， 那么分类结果的 于 么这个分类器对应 (因此随机分类器将产生一个在对角线上 以 它猜测正例概率的 。为了远离对角线进入上三角