（计算机应用技术专业论文）用于ranking的bayesian分类器研究.pdf

摘要 分类( c l a s s i f i c a t i o n ) 是数据挖掘和机器学习中最重要的问题之一。因为贝叶 斯( b a y e s i a n ) 算法具有坚实的数学理论基础，所以它有着很好的分类效果，并且 一直是分类算法中的重要算法。但是在数据挖掘和机器学习的实际应用中，对数 据仅有一个准确的分类是远远不够的。一个准确的排列( r a n k i n g ) 算法在实际应 用中往往是需要的，并且其重要性甚至超过了一个准确的分类算法。因此，将贝 叶斯方法应用于r a n k i n g 的研究是一项有趣的工作，并且具有十分重要的意义。 本文在w e k a 试验平台的基础上搭建了用于r a n k i n g 实验的实验平台。在这个 平台上实现了朴素贝叶斯( n b ) ，树扩张贝叶斯( t a n ) ，贝叶斯树( n b t r e e ) ， 隐藏贝叶斯( h n b ) 和a o d e 分类算法。通过对这些分类器的r a n k i n g 效果的比 较我们发现，由于没有充分考虑非类属性相对于类属性之间的重要程度，a o d e 分类器在某些数据集合上r a n k i n g 的效果不太理想。w a o d e 算法通过增加权值的 办法，克服了a o d e 分类算法的缺陷，改善了a o d e 算法的分类效果。于是本文 尝试将w a o d e 分类算法应用于r a n k i n g 。 在r a n k i n g 实验平台的基础上，本文对上述六种算法进行了试验。试验结果表 明，在3 5 个u c i 标准数据集合上，w a o d e 算法( a o d e 的拓展分类算法) 在 r a n k i n g 上的效果确实要优于a o d e 算法，尤其是在大数据集合的情况下，这种优 势更加明显。并且w a o d e 分类算法在实验中的表现是上述六种分类算法中最好 的。 关键词：数据挖掘；分类器；贝叶斯网络；a u c ；w a o d e ；排序；w e k a 分类号：t p 2 7 4 j b 塞交道太堂亟堂位论塞 星垒至壁! a bs t r a c t c l a s s i f i c a t i o ni so n eo ft h em o s ti m p o r t a n ti s s u e si nd a t am i n i n ga n dm a c h i n e l e a r n i n g b a y e s i a na l g o r i t h m sh a v eas o l i dt h e o r e t i c a lf o u n d a t i o no fm a t h e m a t i c s ，s o t h e ya r ee f f i c i e n to nc l a s s i f i c a t i o n s a n dh a v eb e e ni m p o r t a n ta l g o r i t h m so ft h e c l a s s i f i c a t i o na l g o r i t h m s h o w e v e r , i np r a c t i c a la p p l i c a t i o no fd a t am i n i n ga n dm a c h i n e l e a r n i n g , o n l yo n e a c c u r a t ec l a s s i f i c a t i o na l g o r i t h mo nd a t ai sn o te n o u g h a na c c u r a t e r a n k i n ga l g o r i t h mi so f t e nn e e d e d ，a n di t i se v e nm o r ei m p o r t a n tt h a naa c c u r a t e c l a s s i f i c a t i o na l g o r i t h m t h e r e f o r e ，t h er a n k i n gr e s e a r c hb a s e do l lb a y e si si n t e r e s t i n g a n di so fg r e a ts i g n i f i c a n c e w eb u i l da ne x p e r i m e n t a lp l a t f o r mo nw e k af r a m e w o r k o nt h i sp l a t f o r m ，w e i m p l e m e n tn a i v eb a y e s ( n b ) ，t r e ea u g m e n t e dn a i v eb a y e s ( t a n ) ，n b t r e e ，h i d d e n n a i v eb a y e s ( h n b ) a n da g g r e g a t i n go n e - d e p e n d e n c ee s t i m a t o r s ( a o d e ) c l a s s i f i e r a l g o r i t h m s b yt h ec o n t r a s tw i t ht h e s ec l a s s i f i c a t i o n sw ef o u n d ，t h er e s u l t so fa o d e c l a s s i f i e ro ns o m ed a t as e ta l en o ta sg o o da sw ee x p e c t e db yt h er e a s o nt h a tw ed i d n t f h l l vc o n s i d e rt h ei m p o r t a n t a n c eo ft h er e l a t i o n sb e t w e e nn o n - c l a s sa t t r i b u t e sa n dc l a s s a t t r i b u t e b yt h ew e i g h t e dv a l u e so nt h ec l a s s i f i e ro fa o d e ，w a o d ec l a s s i f i e r o v e r c o m e sd e f i c i e n c i e sa n di m p r o v e st h ee f f i c i e n c yo ft h ec l a s s i f i c a t i o n s o ，w et r yt o a p p l yt h ew a o d ea l g o r i t h mo nr a n k i n g o nt h er a n k i n gp l a t f o r m ，w ed oe x p e r i m e n t so ns i xa l g o r i t h m sa b o v e t h er e s u l t s s h o wt h a to n3 5u c id a t as e tw a o d ec l a s s i f i e ra l g o r i t h m ( t h ee x p a n dc l a s s i f i e r a l g o r i t h mo fa o d e ) i sb e t t e rt h a na o d ec l a s s i f i e ra l g o r i t h me s p e c i a l l yo nb i gd a t a s e t s a n dt h ew a o d ea l g o r i t h mi st h eb e s ti nt h es i xa l g o r i t h m sa b o v e k e y w o r d s ：d a t am i n g ；c l a s s i f i e r ：b a y e s i a nn e t w o r k ；a u c ；w a o d e ；r a n k i n g ； w e k a c l a s s n o ：t p 2 7 4 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 专盛 签字日期：磁年二月g 日 导师签名：删 签字日期：) 9 睁6 月弓日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 砖谚 签字日期： 2 的g 年石月3 日 6 7 致谢 在论文结束之际，我要特别感谢我的导师林友芳对我的关心和帮助。在课题 的选择、资料的查找、方案的论证乃至最后的论文修改等方面林老师都给予了我 极大的帮助和支持。同时，林老师严谨认真的治学态度、勤勤恳恳的工作作风、 敏锐的思维方式、渊博的专业知识也给了我极大的教诲，使我受益匪浅。在此， 我再次对我的导师林友芳表示敬意和真挚的感谢。 衷心感谢黄厚宽和田盛丰教授，两位教授宽广豁达的长者风范、以及严谨的 治学态度始终让我深深地敬仰他们在此期间对我的关心和鼓励让我深受感动。 同时要感谢田凤占老师，他在平时学习和生活中给予我极大地帮助，对我们 的项目进行指导，使我的实际动手能力有了极大提高。 我要感谢和我一起参加讨论班的博士生和硕士生：刘大伟、王丽丽、王春锋、 韩洪光、冯奇、王银利、张颜锋、李广群等，通过我们在讨论班的学习和积极讨 论，使我对很多问题有了更深入的了解和理解。他们给了我很多好的建议，同时 也拓宽了我的视野，接触到了很多其他领域的相关知识。感谢大家在各个方面给 予了我很大的帮助。我祝愿你们以后取得更大的成绩。同时也要特别感谢一起参 加项目开发的刘大伟、王丽丽、王春锋等同学，通过实际开发，让我对f j a v a 知识 更加巩固。感谢谢作将等同学给予我w e k a 系统下算法实现的帮助。 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业。 最后，真诚的感谢在百忙之中，抽出时间审阅本论文的各位老师和专家，恳 请各位老师多多批评指正，并提出宝贵的意见。 1 引言 1 1 课题背景 从二十世纪8 0 年代开始，随着计算机应用的普及和数据库技术不断发展，数 据库管理系统的应用领域越来越广泛。尤其是最近1 0 年来，数据库中存储的数据 量急剧增大，致使数据库的规模日益扩大，与此同时，大容量、高速度、低价格 的存储设备也相继问世，管理大量数据的数据库管理系统以及各类数据仓库已经 能够支持存储、检索如此规模的数据。但是如何才能从海量的数据信息中提取有 价值的知识，进一步提高信息的利用率? 由此，数据挖掘技术应运而生。 数据挖掘就是从海量数据中提取人们感兴趣的、隐含的、事先未知的、又潜 在有用的信息。数据挖掘对海量数据有六种分析方法：分类、估值、预言、相关 性分组或关联规则、聚类、描述和可视化1 1 , 4 j 。 分类是数据挖掘和机器学习领域中最重要的一个任务之一。经典的分类算法 的学习过程就是用一批带有分类标记的训练数据去构造一个具有预测能力的分类 模型的过程。分类算法应用于测试数据集上的分类精度常常被用来评估分类算法 的优劣。然而，在许多现实的数据挖掘与机器学习应用中，光有一个分类的算法 是远远不够的的。一个准确的排列( r a n k i n g ) 算法往往是需要的，甚至超过一个 准确的分类算法。例如，在某一个商品促销活动中，生产商需要对所有的用户做 一个排列，然后根据客户的排名不同制定不同的促销计划。又如，在某一项贷款 活动中，银行经理需要对所有申请贷款的客户的信誉度和偿还能力做一个排列， 然后再来确定贷款对象和强度。显然，要解决这样一系列的问题，仅仅预测所有 潜在客户的”买与不买”或”贷或不贷”是远远不够的。切实可行的办法是对这些潜在 的客户做一个准确的排列，然后再根据每个客户的排名制定不同的促销和贷款策 略。 从最近几年的研究论文来看，关于r a n k i n g 的研究，许多学者都取得了一些可 喜的成绩，大部分的学者都选用决策树来做r a n k i n g 。代表性的论文有：p r o v o s t i l l j 通过改进传统的c 4 5 算法得到了用于排列的决策树算法c 4 4 ；之后s e a r - t e s c h a n s k y 提出了一种叫做改进b o o t s t r a p 一坦】的学习算法去提高c 4 4 算法的排列性能；等 等。还有一部分学者研究过基于人工神经网络和支持向量机的排列算法，比 ! t 1 ：r a n k n e t t 4 8 】和r a n k s v m t 4 9 。而基于贝叶斯网络的排列算法的研究论文主要来自 加拿大的h a r r yz h a n g 教授领导下的数据挖掘小组。 1 2 本文所完成的工作 在数据挖掘领域中，分类是一种非常重要的技术，在金融、证券、科学、工 程等领域有着广泛的应用。将分类器用于r a n k i n g ，是最近几年来数据挖掘领域研 究的热点之一。贝叶斯分类器r a n k i n g 是分类器r a n k i n g 领域的重点内容。朴素贝 叶斯( n a i v eb a y e s ) 分类器是一种最典型的限制性的贝叶斯分类器，但是其条件 独立性假设在实际情况中难以完全满足，从而影响了其在r a n k i n g 和分类中的效 果。树扩张型朴素贝叶斯( t r e ea u g m e n t e dn a i v eb a y e s ) 分类裂2 s 】放松了其条件 独立性假设，改进了朴素贝叶斯分类器分类性能。在t a n 的基础之上，2 0 0 5 年 w e b b 等提出了a o d e ( a g g r e g a t i n go n e d e p e n d e n c ee s t i m a t o r s ) 3 ) 类算澍4 0 l ，结合 了l b r 4 3 】和s p t a n 的优点，a o d e 在不降低准确率的情况下提高了分类的效率。 但是a o d e 的同等对待所有非类属性的缺陷和实际情况并不十分吻合。在这种基 础上l j i a n g 和h z h a n g 提出了w a o d e ( w e i g h t i l ya v e r a g e do n e - d e p e n d e n c e e s t i m a t o r s ) 算法【4 2 】用于改进a o d e 算法的分类性能。同样，a o d e 的缺陷也影响 了其在r a n k i n g 方面的效果。 本文首先在w e k a 数据挖掘实验平台的基础上搭建了用于r a n k i n g 的实验平 台。在这个平台的基础上比较了a o d e ，h n b ，n b t r e e ，n b 和t a n 分类器用于 r a n k i n g 的效果。并将w a o d e 分类器用于r a n k i n g 以改进a o d e 分类器在r a n k i n g 中的效果。经过同其他分类器的实验对比，发现w a o d e 算法确实是一种非常优 秀的r a n k i n g 算法( 实验结果见第五章) 。本文完成的工作主要有： 首先，介绍分类以及r a n k i n g 的相关概念，包括分类器进行r a n k i n g 的概 念、步骤、构造方法。 其次，叙述了本文所涉及到的r a n k i n g 的分类器之间的评价标准，探讨了 r o c 曲线，二类a u c 和多类a u c ，并在此基础上给出了一个具体的计 算a u c 的方法m m e a s u r e 算法。 然后，介绍了几种比较流行的贝叶斯分类器，分析了朴素贝叶斯分类器、 t a n 分类器、a o d e 、h n b ( h i d d e nn a i v eb a y e s ) 和n b t r e e 分类器的理论 基础和分类器结构，比较各个算法的优缺点。并在w e k a 数据挖掘平台的 基础上搭建了r a n k i n g 实验平台，将上述分类算法应用于r a n k i n g 实验， 发现a o d e 分类器由于没有考虑其每种非类属性的重要程度，导致其有 时并不符合现实情况。 w a o d e 算法在a o d e 算法的基础上进行了加权计算，改善了a o d e 算 法等同对待所有属性的缺陷，提高了a o d e 算法的分类精度。所以本文 借鉴了w a o d e 算法的优势，将之应用于r a n k i n g 。并将其和上述5 种分 2 类算法一同应用于3 5 个u c i 标准数据集上进行实验。 最后得出结论，w a o d e 分类器是一种很优秀的r a n k i n g 算法，能够在大 多数数据集上提高r a n k i n g 的准确度。尤其在大数据集合的情况下，对 a o d e 算法有一定的提高。 1 3 论文的组织安排 本文的主要框架和结构如下： 第2 章是全文的理论基础，介绍了分类的理论和相关知识，包括分类的概念 和分类器的构造方法；叙述了将分类器应用于r a n k i n g 的基本概念，r a n k i n g 的评 价标准a u c 以及将分类器用于r a n k i n g 的思想和算法的流程。 第3 章介绍了近年来贝叶斯主流分类器的发展情况，其中包括朴素贝叶斯， t a n ，h n b ，并且介绍了决策树和贝叶斯相结合的n b t r e e 算法。然后我们重点介 绍了近年来的贝叶斯分类器新的研究成果a o d e ，这些为我们后面的研究提供了 理论支持。 第4 章是本文的核心部分，详细叙述了将w a o d e 分类器用于r a n k i n g 的情 况，包括程序的流程，怎样搭建w a o d e 分类器，怎样对试验集合进行排序，以 及为什么选用w a o d e 作为r a n k i n g 用分类器，同a o d e 相比它有什么优点和缺 点。介绍了r a n k i n g 实验平台的流程和架构，最后对我们的分析做了一个小结。 第5 章给出了本文的实验过程和结果。首先分析了w e k a 3 】平台的大致结构， 介绍了r a n k i n g 实验平台在w e k a 中的搭建情况，然后给出了w a o d e 算法在w e k a 中的具体实现，接着叙述了实验方法，描述了实验数据集，在数据集上进行实验 并记录实验结果，最后对结果进行比较和分析。 第6 章总结全文，对本课题研究做了分析和总结，分析了算法的不足之处， 并给出了本课题将来的研究内容和方向。 3 2 分类及r a n k i n g 理论概述 分类是数据挖掘领域内一项十分重要的技术，也是一种重要的数据分析形式。 分类就是在已有数据的基础上学习一个分类函数或构造出一个分类模型。该函数 或模型能够把数据纪录映射到给定类别中的某一个，从而可以应用于数据分类或 者是数据预测。如何将分类器应用于排序是近年来比较热点的问题，国外许多学 者都做过这方面的研究。实际上分类器排序就是利用分类器对类的概率估测对数 据集进行排序。 本章首先介绍了分类技术的一些基本概念，然后探讨了将分类器算法用于排 序的基本流程，最后介绍了r o c 2 】和a u c 2 的概念以及用于对不同分类器的排序 效率进行评价。 2 1 分类 2 1 1 分类技术 分类是数据挖掘中的一个非常重要的课题，数据分类就是在大量数据中找出 一组对象的共同特征，并将数据按照分类模型划分成不同的类的过程。该分类模 型即分类器。它代表了这类数据的整体信息，即该类的内涵描述。该模型能够把 某个数据元组映射到给定类别集中的某一个类。 分类的目的是分析输入数据，通过在训练集中的数据表现出来的特性，为每 一个类找到一种准确的描述或者模型。描述常常用谓词表示。由此生成的类描述 用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的， 但我们仍可以由此预测这些新数据所属的类。但对新数据所属的类仅仅是预测， 而不是肯定。也可以由此对数据中的每一个类有更好的理解。也就是说，我们获 得了对这个类的知识。 用于分类的描述或者模型叫做分类器，其构造和使用如图2 1 所示。分类器的 构造需要输入数据，或称训练集( t r a i n i n gs e t ) ，是一条条的数据库记录( r e c o r d ) 组成。每一条记录包含若干条属性( a t t r i b u t e ) ，组成一个特征向量。训练集的每 条记录还有一个特定的类标签( c l a s sl a b e l ) 与之对应。该类标签是系统的输入， 通常是以往的一些经验数据。一个具体样本的形式用样本向量如l ，口2 ，a n ；c 来表示。其中嘶表示字段值，c 表示类别。训练集是分类器的基础。 4 圉一 怔一 图2 1 分类器的构造和使用 f i g u r e2 - 1c o n s t r u c t i o na n du s i n go ft h ec l a s s i f i e r 分类任务的完成依赖两个步骤：建立模型和利用模型进行分类，这两个过程 如图2 2 所示。 图2 - 2 分类的基本步骤 f i g u r e2 - 2b a s i cs t e p so fc l a s f i f y i n g 1 ) 建立模型 建立模型【2 】是为了描述预定的数据类集或概念集的分类器，通常这一步骤也被 称作为训练( t r a i n i n g ) 或者是学习( l e a r n i n g ) 。分类算法通过分析由属性描述的 训练例、训练样本或者是实例来构造模型。其中每一条训练例属于其中一个预定 义的类，由一个称作类标签属性( c l a s sl a b e la t t r i b u t e ) 的属性确定。训练数据集就 是用来建立分类模型所使用的训练数据的集合。训练数据集中的单条训练数据称 作训练样本，并随机地由样本群选取。由于提供了每个训练样本的类标号，所以 该步也称作有监督的学习，即模型的学习在被告知每个训练样本属于哪个类的“指 5 导 f 进行。它不同于另外一种无监督的学习，也称作聚类，此时每个样本的类 标签是未知的，要学习的类的个数或者集合也可能事先不知道，也就是没有类标 签作为学习的“指导”。一般的，学习模型用决策树、分类规则或其他数学公式的 形式来表示，学习模型使用的形式不用，学习出来的分类模型性能也有差别，所 给例子采用的是分类规则的形式建立模型。 模型和分类器的概念并不完全一样，分类器的产生依赖于两个条件，一个是 模型，另一个是训练数据集，两者缺一不可。如果只存在模型，而没有数据来训 练它，只能称之为分类器算法，当有了训练数据进行训练学习之后，才产生能够 用于对新数据进行分类的分类器。因此，分类器是模型和训练数据集的产物，受 模型和训练数据的影响。 分类的第二个步骤是使用模型进行分类【2 】。评价分类模型，有三种评估或比较 尺度： 1 ) 预测准确度：预测准确度是用得最多的一种比较尺度，特别是对于预测型 分类任务，目前公认的方法是l o 重分层交叉验证法。 2 ) 计算复杂度：计算复杂度依赖于具体的实现细节和硬件环境，在数据挖掘 中，由于操作对象是巨量的数据库，因此空间和时间的复杂度问题将是非 常重要的一个环节。 3 ) 模型描述的简洁度：对于描述型的分类任务，模型描述越简洁越受欢迎， 例如，采用规则表示的分类器构造法就更有用，而神经网络方法产生的结 果就难以理解。 评估模型的正确率或错误率有很多种方法，保持( h o l d o u t ) 方法是一种使用 类标签样本测试集的简单方法【3 】。这些样本随机选取，并独立于训练样本。模型在 给定测试集上的准确率是正确被模型分类的测试样本的百分比，错误率则是被模 型错误分类的测试样本的百分比。对于每个测试样本，将己知的类标签与该样本 的学习模型预测的结果相比较。 如果模型的准确率或错误率是根据训练数据集评估，那么评估的结果可能是 乐观的，因为分类模型倾向于过度拟合数据。也就是说，分类模型可能并入训练 数抛中某些特别的异常，这些异常不出现在总体样本群中。因此，评估分类模型 效果时，使用测试集效果会更好。 但是，分类的效果一般是和数据集的特点有关，有些数据集噪声大，有些数 据集含有缺损值，而有些数据集数据分布稀疏，还有些数据集数据字段或属性间 相关性强。对于数据集上的属性来说，有些数据是离散的，有些数据是连续的或 者是混合式的。各种各样的数据集之间有各自的特点，目前普遍认为不存在某种 方法能适合于各种特点的数据集。 6 评估结果出来后如果认为，模型的准确率和计算复杂度可以接受，就可以用 它对类标签未知的测试例进行分类，这些测试例也称为未知的或先前未知的数据。 2 1 2 分类器构造方法 构造分类器的方法有多种，比较常见的主要有决策树方法、贝叶斯方法、k 最近邻方法、后向传播分类以及粗糙集方法等方法。这几种构造方法构造的分类 器各自有各自的特点，适用范围也不一样。 1 ) 贝叶斯分类器 贝叶斯分类是统计学分类方法。贝叶斯分类器可以预测类成员关系的可能性， 如给定样本属于个特定类的概率。目前，贝叶斯分类方法已经在文本分类、字 母识别、经济预测等领域获得了成功的应用。贝叶斯方法正在以其独特的不确定 性知识表达形式、丰富的概率表达能力、综合先验知识的增量学习等特性成为众 多数据挖掘方法中最引人注目的焦点之一。 贝叶斯分类器的核心是贝叶斯定理。贝叶斯定理建立起了先验概率和后验概 率的联系。先验概率是指根据历史资料或主观判断确定的各事件发生的概率，由 于没有经过事实证实，属于检验前的概率，所以称为先验概率。后验概率是指利 用贝叶斯定理，结合调查等方式获取了新的附加信息，对先验概率进行修正后得 到的更符合实际的概率。 贝叶斯定理中的贝叶斯公式也称后验公式，有几种不同的形式。通常采用事 件形式或随机变量形式表示。其定理形式为如公式2 1 。 p ( hix ) ：p ( x ih ) p ( h ) ( 2 1 ) 尸( 彳) 。 设x 是类标签未知的数据集，日为某种假定，如果数据样本x 属于某特定的 类c 。对于分类问题，我们希望确定e ( n x ) 。p ( h l x ) 就是给定观测数据样本石，假 定日成立的概率。p ( 功是先验概率，p ( h p o 贝l i 是给定条件日下，x 的后验概率。后 验概率p ( h i x ) t l 先验概率p ( 邡拥于更多的信息。贝叶斯定理给了一个由已知的先 验概率转换成后验概率的有效途径。 朴素贝叶斯分类器是贝叶斯分类器最简单的情况【l o l ，它假定了训练集上各个 属性之间在给定类条件下是独立的，简化了计算量。一般认为，只有在满足类条 件独立的情况下，朴素贝叶斯分类器才能获得精确最优的分类效果，而在属性相 关性较小的情况下，能获得近似最优的分类效果。在实际应用中，朴素贝叶斯分 类器因为其简单高效健壮的特点得到了广泛的应用。朴素贝叶斯方法的薄弱环节 7 在于实际情况下，类别总体的概率分布和各类样本的概率分布函数( 或密度函数) 常常是不知道的。为了获得它们，就要求样本足够大。另外，朴素贝叶斯方法要 求各个属性之间相互独立，这样的条件在实际中一般很难满足，因此该方法往往 在效果上难以达到理论上的最大值。 2 ) 决策树分类器 决策树是一种类似流程图的树结构。树中的每个非叶子结点( 包括根结点) 对应 于训练样本集中一个非类别属性的测试，非叶子结点的每一个分枝对应属性的一 个测试输出，每个叶子结点则代表一个类或类分布。树的最项层节点是根节点。 从根结点到叶子结点的一条路径形成一条分类规则。树的最项层节点是根节点。 决策树的生成一般是一个两步过程：生成和剪枝。决策树的基本生成算法是一种 贪婪算法，自项向下递归地构造一棵尽量简单而又蕴涵更多信息的决策树。一个 典型的决策树如图2 3 所示。 决策树的基本算法是贪心算法，采用自项向下的递归方式构造决策树。h u n t 等人于1 9 6 6 年提出的概念学习系统c l s 是最早的决策树算法，以后的许多决策树 算法都是对c l s 的改进或者由c l s 衍生而来。q u i n l a n 于1 9 7 9 年提出了著名的i d 3 算法【5 】。以i d 3 为蓝本的c 4 5 算法是一个能处理连续属性的算澍6 1 。其他决策树 方法还有i d 4 和i d 5 等。强调数据挖掘中有伸缩性的决策树算法有s l i q 、s p r i n t 、 r a i n f o r e s t 等算法【7 ，8 一。 图2 - 3 决策树分类器 f i g u r e2 - 3d e c i s i o nt r e ec l a s s i f i e r 3 ) k 一最近邻分类器( k - n e a r e s tn e i g h b o r ) 由c o v e r 和h a r t 于1 9 6 8 年提出的k n n 法，即k 最近邻法，是一个理论上比 较成熟的方法。 最近邻分类基于类比学习，训练样本用r 维数值属性描述。每个样本代表 维空间的一个点。这样，所有的训练样本都存放在，l 维模式空间中。给定一个未 知样本，七一最近邻分类法搜索模式空间，找出最接近未知样本的k 个训练样本。 这k 个训练样本是未知样本的k 个近邻。点之间的临近性用欧几里德距离定义，其 中两个点片仿l ，砣，) 和y = ( y l ，妮，蛐) 的欧几里德距离是 r 一 d i s t ( x ，】，) = ( x ，一y i ) 2 ( 2 2 ) yi = 1 未知样本被分配到k 个最近邻中最公共的类。当k = - i 时，未知样本被指定到 模式空间中与之最临近的训练样本的类。 k n n 方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的 相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外， 由于k n n 方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所 属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，k n n 方法较其他 方法更为适合。 该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到 全体己知样本的距离，才能求得它的k 个最近邻点。目前常用的解决方法是事先 、j 已知 羊本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种r e v e r s e k n n 法，能降低k n n 算法的计算复杂度，提高分类的效率。该算法比较适用于 样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比 较容易产生误分。 4 ) 粗糙集方法器 粗糙集合理论可以用于分类，发现不准确数据或噪声数据内在的联系。它用 于离散值属性。因此，连续值属性必须在处理之前离散化。 c 的下近似 c 、 i 缫酗。 挚”麓 、劳， ? ”ar琶彩? 。 翳， 爹霞 、 - ：“ ， 矿 - 錾，髦：“ 您i红、。 爹、姑冬 、? 0 “ 。j _ _ - _ _ d 戮：璇。象施。嗲# 。施箍i 磊锄篪1 磊& ；。氟? 北砬秘哟 似 图2 5 粗糙集示意图 f i g u r e2 - 5r o u g hs e ts k e t c h 粗糙集理论基于给定训练数据内部的等价类的建立。形成等价类的所有数据 样本是不加区分的，即对于描述数据的属性，这些样本是等价的。给定现实世界 9 数据，通常有些类不能被可用的属性区分。粗糙集可以用来近似或粗略地定义这 种类。给定类c 的粗糙集定义用两个集合近似：c 的下近似和c 的上近似。c 的 下近似由一些这样的数据样本组成，根据关于属性的知识，它们毫无疑问属于c 。 c 的上近似由所有这样的样本组成，根据相关属性的知识，它们不可能被认为不属 于c 。类c 的下近似和上近似如图2 5 。其中每个矩形区域代表一个等价类。判定 规则可以对每个类产生。通常，适用决策表表示这些规则。 粗糙集也可以用于属性选择和相关分析。找出可以描述给定数据集中所有概 念的最小属性子集问题是n p - 困难的。所以，现在已提出了一些降低计算强度的算 法。例如，有一种方法使用识别矩阵存放每对数据样本属性之间的差别，而不是 在整个训练集上搜索。 5 ) 后向传播分类器 后向传播是一种神经网络学习算法。神经网络最早是由心理学家和神经生物 学家提出的，旨在寻求开发和测试神经的计算模拟。粗略地说，神经网络是一组 连接的输入输出单元，其中每个连接都与一个权相关联。在学习阶段，通过调整 神经网络的权，使得能够预测输入样本的正确类标签来学习。由于单元之间的连 接，神经网络学习又被称作是连接者学习。 输入层隐藏层输出层 图2 - 4 多层前馈神经网络 f i g u r e2 - 4m u l t i l a y e rf e e d f o r w a r dn e u r a ln e t w o r k 最流行的神经网络算法是2 0 世纪8 0 年代提出的后向传播算法。该算法在多 层前馈( m u l t i l a y e rf e e d f o r w a r d ) 神经网络上进行学习。这种网络的如图2 4 所示。 输入对应于对每个训练样本度量的属性。输入同时提供给称作输入层的单元层。 这些单元的加权输出依次同时地提供给称作隐藏层的类神经元的第二层；该隐藏 层的加权输出可以输入到另一个隐藏层；如此下去。隐藏层的数量是任意的，尽 管实践中通常只用一层。最后一个隐藏层的加权输出作为构成输出层的单元输入。 输出层发布给定样本的网络预测。 1 0 o 后向传播通过迭代地处理一组训练样本，将每个样本的网络预测与实际直到 的类标签比较，进行学习。对于每个训练样本，修改权值，使得网络预测和实际 类之i 、h j 的均方误差最小。这种修改“后向 进行，即由输出层，经由每个隐藏层， 到第一个隐藏层。因此称作后向传播。尽管不能保证权最终能够收敛，但是一般 情况下，权还是能够收敛，学习过程也将停止。 2 2r a n k i n g 技术 分类是数据挖掘和机器学习领域中最重要的一个任务之一。然而，在许多现 实的数据挖掘与机器学习应用中，光有一个准确的分类算法是远远不够的。一个 准确的分类算法往往是需要的，并且其重要性甚至超过一个准确的分类算法【0 3 1 。 例如，在某个商品促销活动中，生产商需要对所有的客户做一个排列，然后根据 客户的排名不同制定不同的促销计划。显然，要解决这样一些现实的问题，仅仅 彳r 分类是不够的，切实可行的办法是对这些潜在客户做一个准确的排列，然后再 根据每个客户的排名制定不同的促销计划。 但是摒弃对分类问题研究的所有积累，从零开始进行普通意义上的r a n k i n g 算法的研究又是不可能的( 因为只有一批仅仅带有类标记的训练数据) ，经过对分 类进行了很长时间的研究，人们发现，包括贝叶斯网络分类器在内的许多分类器， 不光是能够预测分类，它们也能够产生对类的概率估测，即预测某一实例属于某 一类的概率。于是我们就产生了将概率预测用于排序的想法。1 3 1 。 基于分类器r a n k i n g 的过程是：首先根据一个测试集合构建一个分类器；然后 对一个数据集进行分类，得到每个实例的概率估测；最后用此估测对数据集进行 排序。如图2 6 所示。 图2 - 6 分类器排序 f i g u r e2 - 6r a n k i n go ft h ec l a s s i f i e r 具体来讲分类器r a n k i n g 的基本流程和分类器分类比较相似，大致也分为两 步，第一步是用测试数据集建立分类器，第二步是用此分类器计算每个实例的概 率估测，然后用此估测进行排序。 分类器r a n k i n g 和传统排序最大的不同在于他们的衡量指标。传统的排序方式 基本上是以排序的效率作为衡量的指标，这种效率包括时间复杂度和空间复杂度。 这种排序基本上不会牵扯到排序是否正确的问题，如果一个排序算法排出来的集 合根本不正确，那么这根本就不是一个合格的排序算法。 但是，分类器排序则不然，由于分类的不确定性，排序出来的结果有可能是 错误的，也有可能是正确的，也就是排序是否正确成了一个比较重要的指标。比 如有一次比赛，需要对选手做一次排序，得到最终选手的排名，这种排序就是一 种预测性的排序，我们只能是从过去的比赛的结果最为依据，得到一个分类器， 然后用这个分类器去计算每个选手的分类概率，最后得到一个数值，然后用这个 值进行排序，但是排序的结果并不一定是j 下确的，是一种预测性质的排序。而实 际中有的时候又确实需要这样的排序结果。 在国内，从近几年发表的研究论文来看，关于排列算法的研究几乎是一片空白。 关于贝叶斯网络方面的论文大都是关于分类算法及其应用方面的。在国外，关于 排列算法的研究，许多学者取得了一些可喜的成绩，但绝大多数学者的选模都集 中在决策树( d e c i s i o nt r e e ) 上。代表性的论文如：p r o v o s t 】通过改进传统的c 4 5 【2 0 】 算法得到了用于排列的c 4 4 ；之后s a a r - t s e c h a n s k y 忆】提出了一种叫做b o o t s t r a p l v 的主动学习方法去提高c 4 4 算法的排列性能；c x l i n g t l 3 】提出了另外一种新的算 法去改进决策树的排列性能。此外h a r r yz h a n g 和他的博士b i nw a n g ，j i a n gs u 相 继提出了一些决策树排列算法【1 4 以。当然，也有部分学者研究过基于人工神经网 络和支持向量机的排列算法，比如：r a n k n e t 硌】和r a n k s v m 1 9 1 。而基于贝叶斯网 络的排列算法的研究主要主要有n a i v eb a y e s 2 2 1 ，n b l r e e ，a o d e ，和h n b 2 l 】等。 2 3r a n k i n g 评价标准a u c 2 3 1r o c 曲线 当我们的目标是应用或者改进这些能够产生类概率估测的分类器来做排列的 时候，分类精度无疑不能再用来作为算法的评估标准。那么用来度量这种用于 r a n k i n g 的分类算法的标准是什么呢? 答案就是r o c 曲线。r o c ( r e c e i v e r o p e r a t i n gc h a r a c t e r i s t i c s ) 曲线能够在整个类分布和误差分布代价范围内比较分类 器的爿 列性能【2 1 。2 4 1 。 r o c 是受试者工作特征( r e c e i v e ro p e r a t i n gc h a r a c t e r i s t i c ) 或相对工作特征 ( r e l a t i v eo p e r a t i n gc h a r a c t e r i s t i c ) 的缩写【2 5 1 。r o c 分析【2 5 】起源于统计决策理论，用 来说明分类器命中率和误报警率之间的关系，最早在第二次世界大战中应用于雷 达信号观察能力的评价，后来使用在晶体管的相关研究。六十年代中期大量成功 地用于实验心理学和心理物理学研究。l u s t e d 在1 9 8 8 年首次提出了r o c 分析可 1 2 用于医疗决策评价，自从八十年代起该方法广泛用于医疗诊断性能的评价。 s p a c k m a n 2 叼将r o c 分析技术最早引用到机器学习领域中，他说明了r o c 曲线的 值估计和比较算法。 序号输出概睾序弓输：l l概半 1t r u eo 9 5l lt r u eo 4 5 2t r u eo 8 51 2f a l s eo 3 8 3f a l s eo 7 51 3t r u eo 3 7 4 t r u eo 6 51 4f a l s eo 3 6 5t r u eo 6 01 5t r u e0 3 5 6f a l s eo 5 51 6t r u eo 3 4 7 f a l s eo 5 41 7f a i s eo 3 3 st r e eo 5 21 8f a l s eo 3 0 9f 越s eo 5 1 51 9t r e eo 2 0 1 0f a l s eo 5 12 0f a l s oo 1 0 图2 7r o c 曲线图 f i g u r e2 - 7r o c c u r v e 图2 7 就是一个r o c 曲线的例子，表示一个有2 0 个实例的测试集，其中包括 l o 个正例，1 0 个负例。图2 7 左表描述了分类器在该测试集上的输出，以输出概 率排序。图2 7 右图显示了通过设置递减阈值得到的r o c 曲线。 r o c 曲线显示了给定模型的真正率或灵敏度( j 下确识别的正元组的比例) 与 假正率( 不正确识别为正元组的负元组的比例) 之间的比较平定。也就是说，给 定一个二类问题，我们可以对检验集的不同部分，显示模型可以正确识别“y e s ” 实例的比例与模型将“r i o ”实例错误的识别为“y e s ”的比例之间的比较平定。 要明白r o c 曲线，首先我们要理解r o c 曲线图的一些概念定义：1 ) 真正( t r u e p o s i t i v e ，t p ) 代表被模型预测为正的