（计算机应用技术专业论文）基于组合分类器的数值型不确定性数据分类方法研究.pdf

基于组合分类器的数值型不确定性数据分类方法研究摘要 论文题目： 专业： 姓名： 导师： 基于组合分类器的数值型不确定性数据分类方法研究 计算机应用技术 严日强 任江涛副教授 摘要 传统的分类算法主要是针对处理确定性数据分类的情况，确定性数据是指训 练数据集和测试数据集中的每一个数据样本的每一属性值都是唯一确定的。处理 确定数据分类问题的方法很多，如c 4 5 决策树、s v m 支持向量机和贝叶斯分类 等。但现实情况中所采集到的数据往往是不确定的，不确定性数据具体表现为数 据样本每一维度的值都是在一定范围内服从某种分布的数据的集合。传统的分类 算法在处理这一类的不确定数据的分类问题时会由于自身固有的局限性，直接导 致分类精度的下降。 因为不确定数据每一属性值都不是一个唯一确定的值，而是一个以【a ，b 】的 形式表示符合一定分布的取值区间，因此每一个不确定性数据样本，在高维空间 不再是单个确定的点，而是高维空间上的一团点。针对处理这样的不确定性数据 分类问题，本文提出了四种算法：分别是基于期望值的a v g 算法、基于采样的 u s m 算法、基于采样的组合分类器e u s 算法和基于权重采样的e w s 算法。a v g 算法和u s m 算法分别通过期望点和采样点把原不确定性数据分类转化为传统确 定数据分类问题；e u s 算法是通过采样的方法，引入组合分类器的思想，对不 确定数据对象按其密度分布函数进行采样，通过采集不同的训练集来构造不同的 子分类器，从而组成组合分类器来解决不确定数据的分类问题。e w s 算法是在 基于采样的组合分类器e u s 算法基础上的改进，引入a d a b o o s t 思想和置信度概 念，减少对置信度高的样本采样，增加对置信度低的样本采样，更加关注那些容 易被错分的不确定数据对象，构造组合分类器来解决不确定数据的分类问题。 最后，本文通过对u c i1 4 个数据集进行实验验证了e u s 算法及e w s 算法 的良好性能。 关键词：不确定性数据、分类、组合分类器、a d a b o o s t 、置信度 基于组合分类器的数值型不确定性数据分类方法研究 a b s t r a c t t i t l e ：，n l er e s e a r c ho ne n s e m b l ec l a s s i f i c a t i o no f n u r n e r i e a lu n c e r t a i nd a t a m a j o r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：r i q i a n gy a n s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rj i a n g t a or e n a b s t r a c t g e n e r a l l y , t h er e s e a r c h e so fd a t a - m i n i n ga r eu s u a l l yf o c u s e do nt h ed e t e r m i n a t e d a t as a m p l e ，w h o s ev a l u eo fe a c ha t t r i b u t ei sc o n s t a n t t h et r a d i t i o n a lc l a s s i f i c a t i o n a l g o r i t h m ss u c ha sc 4 5d e c i s i o nt r e e ，s u p p o r tv e c t o rm a c h i n e ，b a y e sm o d e la r e t h es o l u t i o n so fd e t e r m i n a t ed a t ac l a s s i f i c a t i o n b u ti no u rd a i l yl i f e ，w eo f t e nh a v et o h a n d l es o m ed a t aw h o s ev a l u ei su n c e r t a i n ，t h a tm e a n st h ev a l u eo fad a t ai t e mi sn o t r e p r e s e n t e db yas i n g u l a rv a l u eb u tb yap r o b a b i l i t yd i s t r i b u t i o n i nt h i sc a s e ，t h e t r a d i t i o n a lc l a s s i f i c a t i o na l g o r i t h m sa r en ol o n g e rs u i t a b l et os o l v et h i sk i n do f p r o b l e m t h eu n c e r t a i nd a t a s a m p l e sv a l u e sa l eu s i n gar a n g eo b e y i n gac e r t a i n d i s t r i b u t i o nt od e s c r i b eb u tn o tas i n g l ec e r t a i nv a l u e t h ev a l u eo fe a c ha t t r i b u t ei s b e t w e e nt h el o w e rb o u n daa n dt h eu p p e rb o u n db ，u s u a l l ye x p r e s s e di n a ，b 】 t e r m t h a tm e a n st h ev e r ys i n g l es a m p l ei nt h eh i g h e rd i m e n s i o n a ls p a c ei s1 1 0l o n g e r p r e s e n t e db yas i n g l ep o i n t ，b u tac l o u do fp o i n t s i nt h i sp a p e r , w ep r o p o s e df o u r k i n d so fa l g o r i t h m st os o l v et h i sk i n do fp r o b l e m t h e r ea r ea v g 、u s m 、e u sa n d e w sa l g o r i t h m s t h ea v ga l g o r i t h mi sb a s eo ne x p e c t a t i o nv a l u e ，u s i n gt h e e x p e c t a t i o nv a l u et or e p r e s e n tt h eu n c e r t a i nv a l u e ；t h eu s ma l g o r i t h m i s u s i n g s a m p l i n gt or e s o l v et h eu n c e r t a i nd a t ec l a s s i f i c a t i o n ；t h ee u sa l g o r i t h mi se m p l o y t h ee n s e m b l em e t h o dt oh a n d l et h eu n c e r t a i nc l a s s i f i c a t i o np r o b l e m ，u s i n gt h e s a m p l i n gd a t a s e t st ob u i l dt h es u b - c l a s s i f i e rt oc o n s t r u c tt h ee n s e m b l ec l a s s i f i e r a n dt h ee w sa l g o r i t h mi sa ni m p r o v e m e n to fe u sa l g o r i t h m e w sa l g o r i t h mi s i n t r o d u c i n gt h ea d a b o o s tt h e o r yi n t os o l v i n gt h eu n c e r t a i nd a t ac l a s s i f i c a t i o np r o b l e m t h ee w sa l g o r i t h mu s i n gt h ec o n f i d e n c eo fe a c hu n c e r t a i ns a m p l et op a ym o r e n 基于组合分类器的数值型不确定性数据分类方法研究 a b s t r a c t a t t e n t i o nt ot h o s es a m p l e sw h i c hi se a s yt ob ew r o n gc l a s s i f i e d c o m p a r ew i t ht h e e u sa l g o r i t h m ，t h ee w s a l g o r i t h mh a sh i g h e rc l a s s i f ya c c u r a c ya n dl e s sc o s to f t i m e a n ds p a c e a tl a s t ，w ed e s i g nt h ee x p e r i m e n to ff o u ra l g o r i t h m su s i n g14u c id a t a s e t st o p r o v et h ee u sa n de w s sw e l lp e r f o r m a n c e k e yw o r d s ：u n c e r t a i nd a t a 、c l a s s i f i c a t i o n 、e n s e m b l e 、a d a b o o s t 、c o n f i d e n c e i i i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除本文已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：季日弓致 e in ：乃白年石月3e l 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 一繇尹臼翘跏戤禽叫香 日期：五i 口年6 月3e 1 日期：川。年6 月了 e l 基于组合分类器的数值型不确性数据分粪方法研r 第一蜡论 第一章绪论 数据挖掘是指在信息爆炸的时代下，从指数级增长的数据中发掘出有用信息 和知识的- - 1 综合性学科。在各个领域、各个行业中，数据挖掘越来越受到重视 并得到了广泛的应用。而数据挖掘技术在解决具体实际的应用问题的时候，所面 对的数据源往往是带有噪声，具有不确定性的。本文将研究如何引入a d a b o o s t 思想，利用组合分类器来解决不确定数据的分类问题，提高对不确定数据的分类 精度。本章将首先介绍本文研究的背景和意义，并概述不确定数据分类问题及组 合分类器相关领域的研究工作，车章的最后将对本文的结构安排进行介绍。 1 1 背景和意义 进八信息时代，人们所获取的数据正以指数级速度进行增长，如何对这些海 量的数据进行处理，从中挖掘出有用的信息，实现数据的价值，将是数据挖掘面 临的最重要的问题。在处理实际问题的应用中，按数据挖掘的任务来划分，有以 下几种：数据分类或预测模型数据挖掘、数据聚类、关联规则发现、序列模式发 现、依赖关系或依赖模型发现和网络挖掘等。 数据挖掘是从大量的数据中自动地发现有用信息的过程【l 2 j 。通常情况下， 从数据中发现挖掘知识一般有以下几个步骤：( 1 ) 数据的采集：( 2 ) 数据的预处理， 包括数据清理、数据集成、数据选择和数据变换等；( 3 ) 数据挖掘，包括预测建 模、聚类分析、关联分析和异常检测等：( 4 ) 数据后处理；( 5 ) 结果展示。整个数 据挖掘、知识发现的过程如图卜1 所示。 阁卜1 数据挖掘过程 2 基于组合分类器的数值型不确定性数据分类方法研究 第一章绪论 数据挖掘是是- 1 7 涉及面很广的交叉学科，综合了多个学科的研究成果，包 括机器学习、人工智能、数理统计、神经网络、数据库、模式识别、粗糙集、模 糊数学等相关技术和相关应用领域的背景知识。 其中，数据分类( c l a s s i f i c a t i o n ) 是数据挖掘中一个非常重要的研究领域，通 常分类是利用数据中带有类别标签的样本( 也称“训练样本 ) ，训练构造出一个 数据分类模型( 也称“分类器) ，通过构建出来的数据分类模型，对外来的未带 标签的数据样本( 也称“测试样本”) 的类别标签进行预测。数据分类技术在很多领 域都有广泛的应用。例如在面向客户的市场营销中，利用客户历史的过往销售记 录、交易行为及客户的基本资料，构建一个分类模型来对客户群进行细分，将客 户分成不同的类别，并根据不同的客户类别来制定精准的客户营销及个性化的客 户服务；在银行信用卡业务中，通过数据分类技术来对信用卡业务进行风险防范 和风险控制。根据过往的历史海量信息卡数据信息，构建分类模型，对客户进行 信用分级，区分“高风险”信用卡业务、“低风险 信用卡业务、“次级 客户和 “优质”客户；在医疗领域中，可以通过对医疗数据进行分析，建立亚健康状态 判断模型并对其临床特征进行研究，对患者是否属于亚健康状态进行评判。下面 对数据分类的流程做个简要的描述。 数据分类的流程包括两个过程：( 1 ) 训练，通过带标签的训练样本训练构造 分类模型( 分类器) ；( 2 ) 分类，通过构建出来的分类模型( 分类器) 对未带标签的数 据进行标签预测、分类。训练和分类的具体流程如图1 2 和图1 3 。 图1 2 训练过程 图l 一3 分类过程 在对数据分类的效果评估中，我们通常采用分类精度来对所构造的分类模型 评价。所谓分类精度就是分类器对测试样本中的类别判定分类的准确度。 2 基于组合分类器的数值型不确定性数据分类方法研究第一章绪论 由于数据分类在数据挖掘领域的重要性，相关学者对数据分类的模型进行了 大量的研究。迄今为止，人们提出了很多构建分类模型的算法，例如基于决策树 模型的分类方法( 如i d 3 t 2 1 ，c 4 5 t 3 1 ) ，基于概率统计的贝叶斯模型【4 1 ，基于线性判别 函数的支持向量机模型( s v m 支持向量机【5 】) ，基于数据拟合方法( 如l o g i c s t i c 拟合 法 6 】) ，还有结合图模型的产出式分类方法( g r a p h i c a lm o d e l 7 1 ) 。具体应该选用哪种 分类算法要结合不同的应用背景，有些分类算法适合于处理大规模的数据集，有 些分类算法适用于当指标是连续属性的情况，有些算法适合于有时序特性的数 据，有些分类算法思想直观、简单明了，有些算法则有着严谨的数学公式证明推 导。各种不同的分类算法，都是为了更高效，更可靠地从不同途径对数据集进行 分类预测。 但是，传统的数据分类算法多是处理样本数据是唯一确定情况，即数据样本 的值是精准且无差错的情况，在现实生活中，我们经常要遇到处理数据不是确定 唯一的情况，这时的数据不是精确没有差错的，而是不确定的。例如一些医疗样 本数据，像心率、血压这些医疗属性，每一个病人每一次测量的值都应该是有所 不同的，这些属性值是在一定的范围内按一定的分布存在的。如何对这些不确定 性数据进行分析分类，是对不确定性数据挖掘提出的新的要求。 在处理不确定性数据分类问题时，具体来说，数据的不确定性主要分成两种 不同的类型，一种是元组对象级别的不确定性，即存在性不确定性，另一种是 属性级别的不确定性，即样本属性值不确定性【盯。第一种不确定性是指数据样本、 数据对象的是否存在具有不确定性，例如在关系数据库中，一个元组是以一定概 率存在，并且该元组存在的概率也与其他元组相互关联们。第二种是样本属性 值的不确定性，是指数据样本中的每个属性的值是一个可能的取值区域范围，可 能取值区域范围的边界及取值由一个概率密度函数p d f ( p r o b a b i l i t yd e n s i t y f u n c t i o n ) 表示t 1 1 】。在本文中所解决的不确定性数据分类问题，是指解决第二种属 性值不确定的数据分类问题。 数据属性值的不确定性是由多种原因引起的【1 2 以4 1 ，主要有： ( 1 ) 由于现有技术设备的约束，采集数据的仪器设备存在固有的误差和偏差， 导致采集的数据样本偏离真实的取值； ( 2 ) 所观测的样本值是动态变化的，而所采集的数据值是历史某一时点的值； ( 3 ) 收集的数据存有缺省值或估计值； 3 基于组合分类器的数值型不确定性数据分类方法研究 第一章绪论 ( 4 ) 在数据存储过程，预处理、合并、清洗过程中加入的噪声。 传统的分类算法在处理这些不确定性数据分类时，往往要先将不确定性数据 转换成确定性数据( 例如用不确定性数据的期望值代表整个不确定数据的a v g 算法和利用采样的u s m 算法) ，这样虽然可以对不确定性数据进行分类，但并不 能取得很好的效果。而不确定性数据中包含了一些额外的数据信息，我们可以通 过一定的方法利用这些信息提高我们分类器的分类精度。在本文中，我们将利用 不确定性数据中所包含的额外信息，引入组合分类器的思想来提升对不确定数据 的分类效果，进而在组合分类的基础上利用引入a d a b o o s t 思想来进一步提升解 决不确定数据的分类的精度。通过实验，我们发现基于采样的组合分类器算法和 引入a d a b o o s t 思想的基于权重采样的组合分类器在不确定性数据分类问题上对 比其他算法在分类精度上有比较明显的提升。 1 2 相关研究 1 2 1 不确定数据的研究现状 本文涉及的研究课题主要与不确定性数据挖掘和组合分类器相关。最近，对 不确定性数据挖掘的研究越来越受到研究人员的关注和重视。在不确定性数据的 研究热点中，主要有以下三个方面：( 1 ) 不确定性数据在数据库中的建模和表示 1 5 - 1 7 】。在对不确定性数据的研究中，一个重要的研究方向就是如何对不确定数据 进行建模以及如何在数据库中表示不确定性数据进行处理，通过这样处理，就能 在数据库中采集到有用的信息，能在数据库中从根本上保存不确定数据的错综复 杂性。( 2 ) 对不确定数据的管理，在这个研究方向中，研究者希望通过采用传统 的数据库来管理存储不确定性数据。例如对不确定性数据的连接、合并、查询和 索引等处理【1 s - 2 5 。( 3 ) 不确定性数据的数据挖掘。对不确定性数据挖掘的研究， 主要集中在模糊聚类 2 6 - 2 引、不确定性数据分类 2 9 - 3 1 】、离群点检n 3 2 1 、关联规则 挖掘【3 3 。4 】和数据流挖掘【3 5 - 3 6 等方向。 在对不确定性数据分类的研究领域中，文献 3 0 ，3 1 提出了一种基于支持向量 机( s v m ) 模型框架下处理不确定数据分类的算法，s v m 支持向量机的算法主要 4 基于组合分类器的数值型不确定性数据分类方法研究第一章绪论 是基于一个建立在最小化结构风险的判别模型方法，用不确定数据的数据群来建 造分类的边界；文献 2 9 】扩展了决策树算法，在决策树模型的构建过程中将概率 密度函数( p d f ) 考虑进来，并提出了多种剪枝的算法来提高算法的效率。本文中 所提出的基于采样的组合分类器和引入a d a b o o s t 思想的基于权重采样的组合分 类器算法将与文献 2 9 】中所提出的u d t ( u n c e r t a i nd e c i s i o nt r e e ) 算法进行分类精 度的对比分析。 1 2 2 组合分类器的研究现状 由于本文是结合了组合分类器的方法来解决不确定性数据分类的问题，在这 里简单叙述组合分类器分类算法的研究现状。一般的分类技术都是通过对训练集 进行训练学习，从而得到一个分类的模型( 分类器) ，再通过这个分类器来对未带 类别标签的测试集进行标签的预测，这种单一分类器往往在精度和泛化能力上表 现的不好。而组合方法( e n s e m b l e ) ，也叫分类器组合( c l a s s i f i e rc o m b i n a t i o n ) 方法， 是通过构建一组基分类器( b a s ec l a s s i f i e r ) ，集合多个基分类器，用多个基分类器 的预测结果进行投票进行分类，从而有效提高分类算法对未知样本的分类精度和 泛化能力。 组合分类器作为一种新兴的分类方法获得了广泛的关注和研究。一般构建组 合分类器由两个步骤所组成：( 1 ) 构建基分类器( 子分类器) ；( 2 ) 对子分类器的预测 分类结果进行组合。目前组合分类器的研究热点主要集中于上面这两方面的研究 之上：如何构造基分类器和如何对基分类器的预测结果进行组合。 在如何构建基分类器上，一般有两种不同的架构思想：第一种是通过分类器 的扰动来构造不同的基分类器，例如我们在同一个数据训练集中利用人工神经网 络或者生成树等不稳定的构造分类模型的算法时，可以通过设置、初始化不同的 参数来建立差异化基分类器。例如r a n d o mf o r e s t s l 3 7 1 就是通过利用一个随机向量 来构造不同的决策树，每一棵决策树作为一个子分类器，以及文献 3 8 】中的组合 人工神经网络方法。同样地，采用不同的分类算法对同样的训练集构建基分类模 型也属于分类器扰动的框架，例如我们可以通过分别采用c 4 5 决策树，s v m 支 持向量机，贝叶斯分类器等不同的分类方法对同一训练集构建子分类器。第二种 是通过样本扰动来构造基分类器。划分样本空间和划分属性空间分别是样本扰动 基于组合分类器的数值型不确定性数据分类方法研究第一章绪论 的两种不同的策略。通过划分样本空间或划分属性空间可以生成不同的训练样本 集，通过不同的训练样本集可以建立差异化的基分类器。如b a g g i n g t 3 9 】以及 a d a b o o s t 4 0 1 都是属于通过划分样本空间来构造基分类器的策略，a d a b o o s t 是通过 序列的生成方法，a d a b o o s t 中的每个子分类器都是在上一次迭代的子分类的基础 上再进行更新学习的。而b a g g i n g 是属于并行生产方式，是通过建立互相独立的 训练集，同时构建各个子分类器。 在对子分类器的预测分类结果进行组合的问题上，常见的组合子分类器结果 的研究包括：对分类器的选择【4 1 1 ，对子分类器的预测结果投票的策略包括多数 投票【4 2 1 、带权值多数投票( w m v ) 【4 3 1 ，还有组合选择m 】，决策模板( d t ) 【4 5 1 ，n a i v e b a y e s i a nf u s i o n ( n b f ) t 4 6 1 ，以及增量式、装袋、模糊积分等多种方法。 本文将组合分类器的思想及方法引入到解决不确定性数据的分类问题中，而 本文构建组合分类器中的子分类器的策略主要是采用了通过对样本空间进行扰 动，采集生成不同训练集来构建子分类器。 1 3 本文主要工作 本文主要研究应用组合分类算法解决不确定性数据的分类问题。为此本文首 先从数据挖掘的角度介绍各种类型的数据分类方法，对各种分类算法作出相关的 介绍，然后详细介绍组合分类器的相关算法，例如对本文有很大启发意义的 a d a b o o s t 算法、b a g g i n g 算法等。通过对这些相关的基础知识进行介绍后，本文 着重分析研究对不确定性数据的分类算法，首先提出通过采样的方法来采集不同 的训练样本集来构造组合分类器的方法，用以对不确定性数据分类，继而对构建 组合分类器的采样策略进行改进，引入a d a b o o s t 思想来采集生成训练样本，按 不确定数据对象的权重采样来构造组合分类器。最后通过u c i 上1 4 个真实的数 据集进行大量的实验证明本文所提出的算法与其他两个不确定性分类基线算法 相比在分类精度上有更好的性能。 本文的主要创新点在于：( 1 ) q i 入组合分类思想到不确定数据分类问题中，提 出基于采样的组合分类器算法e u s ( e n s e m b l eu n i f o r ms a m p l i n g ) 算法。( 2 ) 在e u s 算法上进行改进，提出基于权重采样的组合分类器算法e w s ( e n s e m b l eu n i f o r m 6 基于组合分类器的数值型不确定性数据分类方法研究第一章绪论 s 锄p l i n 曲算法。e w s 算法引入了a d a b o o s t 中更关注易错分对象的思想，计算每 个不确定对象的置信度权重，根据不同的权重设定每个不确定对象的采样规模， 使得所构造的分类器更加适合于不确定性数据的分类。( 3 ) 在e u s 算法中，提出 了不确定对象置信度度量的方法，并且提出了按权重确定采样规模的计算公式。 1 4 论文的组织结构 本文的主体分为以下几个部分： 第一部分绪论，介绍了课题的背景和意义，概括了课题具体所涉及的理论 及相应的特点；简述了所涉及技术的发展和目前的研究成果等，最后列出了本论 文的主要研究内容和结构。 第二部分传统确定数据分类算法概述，重点介绍传统确定型数据挖掘中经 典的分类算法，介绍传统分类算法的主要思想及算法框架，最后对分类结果的评 价方法进行了讨论。 第三部分组合分类器算法概述，将分别介绍组合分类算法相关的知识，特 别地，将详细介绍一些对本文算法有启发意义的具有代表性的算法，例如 a d a b o o s t 、b a g g i n g 算法等。 第四部分不确定性数据分类问题的研究，这章对不确定性数据分类进行研 究，将介绍本文算法的核心思想，并从算法框架开始，逐步细化算法每步的实现。 首先提出基于采样的组合分类器解决不确定性数据分类问题，进而引入a d a b o o s t 的思想对采样的策略进行改进，提出基于权重采样的组合分类器算法。 第五部分实验过程及效果分析，设计实验实现第四部分中所提出来的算法， 并通过对u c i 中的1 4 个真实数据集进行大量的实验，对实验结果进行分析，验证 算法的性能。 第六部分总结与展望，总结了本文的研究工作，并讨论了对不确定数据分 类问题研究进一步深化的展望。 7 基于组合分类器的数值型不确定性数据分类方法研究第二章传统确定数据分类算法概述 第二章传统确定数据分类算法概述 传统的分类算法都是针对数据属性唯一确定情况下的分类问题，为了更好地 对不确定数据分类进行研究，在本章将着重介绍典型的几种传统数据分类算法。 通过对传统的分类算法的认识，为解决不确定数据分类提供启发。由于在后续章 节组合分类器策略中的子分类器的选取离不开传统的数据分类算法，通过对传统 分类算法的分析，为组合分类器子分类器构造算法的选取提供有力的理论基础。 在数据挖掘中，分类( c l a s s i f i c a t i o n ) 是通过对带有类别标签的数据样本进行 学习，构建出一个数据分类模型，对未带标签的数据进行标签类别的判定。分类 分析是数据挖掘中重要的任务之一。通常来说，分类算法包括两个步骤：( 1 ) 建 立一个描述已知数据集类别或概念的模型；该模型是通过对数据集中各数据对象 的分析而获得的。每一数据行都可认为是属于一个确定的数据类别，其类别值是 由一个属性描述( 被称为类别标记属性) 。分类学习方法所使用的数据集称为训练 样本集合，因此分类学习又可称为监督学习( 1 e a r n i n gb ye x a m p l e ) ，它是在已知训 练样本类别情况下，通过学习建立相应模型；( 2 ) 利用上一步所获得的模型进行 分类操作，对未知类别标签的数据进行类别的预测。主要通过准确率来对分类算 法进行评价。 目前分类与预测方法已被广泛应用于各行各业，在信用评估、医疗诊断、性 能预测和市场营销等都有实际应用。例如可以构造一个分类模型来对银行贷款进 行风险评估( 安全或危险) ；也可建立一个预测模型以利用顾客收入与职业( 参数) 预测其可能用于购买计算机设备的支出大小。机器学习、专家系统、统计学和神 经生物学等领域的研究人员已经提出了许多具体的分类预测方法。 下面将分别对分类算法中几种重要的模型进行介绍，如贝叶斯分类、决策树 模型、支持向量机等。 2 1 朴素贝叶斯分类 贝叶斯( b a y e s ) 决策分类是基于概率统计的一种分类算法，其算法的核心思 8 基于组合分类器的数值型不确定性数据分类方法研究第二章传统确定数据分类算法概述 想就是依据b a y e s 后验概率公式，可以通过贝叶斯分类器预测每一个数据对象属 于某个类别的概率。简单贝叶斯( 也称基本贝叶斯分类器、朴素贝叶斯分类器) 在 处理大规模数据库时表现出较高的分类准确性和分类精度。 朴素贝叶斯分类器( n a i v eb a y e s i a nc l a s s i f i e r s ) 假设一个指定类别中各属性的 取值都是相互独立的，即类别条件独立( c l a s sc o n d i t i o n a li n d e p e n d e n c e ) ，这一假 设可以帮助有效减少在构造贝叶斯分类器时所需要的计算量。下面首先介绍贝叶 斯分类器的理论基础。 2 1 1 贝叶斯定理 设x 为一个类别未知的数据样本，日为某个假设，若数据样本彳属于一个 特定的类别c ，那么分类问题就是决定p ( 日ix ) ，即在获得数据样本x 时，日假 设成立的概率。由于p ( x ) 、尸( 日) 和尸( x 1 日) 的概率值都可以从训练集数据中 得到，贝叶斯定理则描述了如何根据p ( x ) 、p ( i - i ) 和p ( x1 日) 计算获得 p ( hf 彳) ，有关的具体公式如下： p ( h i x ) = 警 ( 2 - 1 ) 2 1 2 朴素贝叶斯分类算法 朴素贝叶斯分类器的进行分类的操作处理的步骤如下： ( 1 ) 每个数据样本均是由一个n 维特征向量表示，x = ，而， 来描述n 个属性的具体取值。 ( 2 ) c l ，c 2 ，巳是表示数据集中的m 个不同的类别。在基本贝叶斯分类器中， 当且仅当： 尸( cix ) p ( c ，ix ) 对于1 j m ，j i 也就是取j p ( eix ) 值最大时。其中类别c f 就称为最大事后概率的假设。根据公 式2 1 可得： 粥= 警 ( 2 2 ) 9 基于组合分类器的数值型不确定性数据分类方法研究第二章传统确定数据分类算法概述 ( 3 ) 由于p ( 彳) 对于所有的类别都是相同的，因此只需要计算p ( x i g ) 尸( c ：) 的 最大值即可。 ( 4 ) 对于给定包含多个属性的数据集，直接计算p ( xe ) 的运算量是非常大 的。t x 寸p ( xe ) 进行估值，基本贝叶斯分类器通常都假设各自类别都是相互 独立的，就会有： p ( x i e ) = 兀p ( x k ic ，)( 2 3 ) k = l ( 5 ) 对一个未知样本x 的类别进行预测，可对每个类别g 估算相对应 p ( x i g ) 尸( g ) ，样本x 归属类别e ，当且仅当： 尸( clx ) 尸( c jx )对于1 j m ，f 贝叶斯分类方法是建立在贝叶斯定理理论上，通过数学运算得出数据样本最 大概率可能的分类标签，从数学上来讲，其理论推断十分完美。但在应用中，确 受制于很多实际情况的约束。贝叶斯定理理论所规定的条件只是一个理想情况， 实际应用上数据属性很难做到完全相互独立，并且很难得知数据的全部分布信 息。因此只能通过某些假设来满足贝叶斯定理中所规定的条件。 2 2 决策树模型 决策树模型时经典的数据分类算法之一，具有简单且直观的特点。所谓决策 树就是一个类似流程图的树型结构，在决策树的每个内部结点作为对一个属性 ( 取值) 的测试条件，其分支就代表通过这个测试后的一个测试结果；而树的每个 叶子结点就代表一个类别的数据样本。其中决策树的最高层结点就是根结点。图 2 3 是一个决策树的示意描述图，该决策树描述了一个购买手机的分类模型，利 用这一模型可以对一个学生是否会在本活动中购买手机进行分类预测。内部结点 表示判断条件，叶子结点表示分类结果。 l o 基于组合分类器的数值型不确定性数据分类方法研究第二章传统确定数据分类算法概述 图2 - 3 决策树不葸描述 为了对未知数据对象进行分类识别，可以根据决策树的结构对数据集中的属 性值进行测试，从决策树的根结点到叶结点的一条路径就形成了对相应对象的类 别预测。决策树可以很容易转换为分类规则。并且所形成的分类规则简单且十分 直观。 决策树的构造是一个贪心的、从上而下的递归的过程。决策树构造算法的关 键在于对属性的评价标准和划分节点所采用的形式。选择最佳划分的度量通常是 根据划分后子女结点不纯性的程度。不纯程度越低，类分布就越倾斜。通常对信 息增益、不纯性度量的方法有： c - 1 e n t r o p y ( t ) = - p ( iit ) l 0 9 2p ( iif ) ( 2 - 4 ) f l g i n i ( t ) = 1 - 【p ( 印) 】2 ( 2 5 ) c l a s s i f i c a t i o ne r r o r ( t ) = 1 - m a x p ( if ) 】 ( 2 6 ) j 决策树有分单变量划分的决策树和基于多变量划分的决策树。经典的决策树 算法有i d 3 ，c 4 5 和j 4 8 等。下面通过对i d 3 算法进行介绍来说明决策树算法的思 路。i d 3 决策树算法在对属性的评价标准上，是采用信息增益方法来帮助确定生 成每个结点时所选用的合适的属性。这就可以通过选择具有最高信息增益( 熵减 少的程度最大) 的属性作为当前结点的测试属性，这样就使之后所划分获得的训 练样本子集进行分类所需的信息最小。 i d 3 1 2 1 决策树算法概述： 基于组合分类器的数值型不确定性数据分类方法研究第二章传统确定数据分类算法概述 算法2 - l ： g e n e r a t e _ d e c i s i o n _ t r e e e h 给定的训练集数据产生一棵决策树 输入：训练样本集( s a m p l e ) ，各属性均取离散数值，候选属性集a t t r _ l i s t 输出：决策树 处理流程： ( 1 ) 创建一个结点n ； ( 2 ) 如果该结点中的所有样本s a m p l e 均属于同一类别c ，则 返回n 作为一个叶子结点并标志为类别c 。 ( 3 ) 如果a t t r _ l i s t 为空，则 返回n 作为一个叶结点并标记为该结点所含样本中类别个数最多的类别； ( 4 ) 从a t t r _ l i s t 选择一个信息增益最大的属性t e s t _ a t t r ； ( 5 ) 并将结点n 标记为t e s ta t t r ； ( 6 ) 对于t e s t _ a t t r 中的每一个已知取值q ，准备划分结点n 所包含的样本集； ( 7 ) 根据t e s t _ a t t r = a i 条件获得的样本集合，从结点n 产生相应一个分支，以表示 该测试条件； ( 8 ) 设s i 为t e s t a t t r = q 条件所获得的样本集合； ( 9 ) 如果s f 为空，则将相应叶结点标志为该结点所包含样本中类别个数最多的 类别。 ( 1 0 ) 否贝l j 将叶结点标志为g e n e r a t e - d e c i s i o n l r e e ( s i ，a t t rl i s t ，t e s t _ a t c r ) 返回值。 以上就是决策树建模生成的过程，i d 3 ，c 4 5 及j 4 8 的主要区别在于属性选择 时信息增益的度量公式和剪枝策略的不同。i d 3 算法的优点是：算法理论清晰， 且结构方法简单，学习能力强。 通过上面我们了解到，决策树学习是一种逼近离散值函数的算法，适合于处 理离散值数据。另外决策树学习方法对噪声数据有着很好的健壮性，并且通过决 策树建模能够学习析取到分类规则的表达式。正因为决策树模型能对噪声数据有 良好的健壮性，在后面章节我们讨论用组合分类器来解决不确定性进行分类时所 采用的子分类器构造的算法就选择了用决策树分类学习方法。 1 2 基于组合分类器的数值型不确定性数据分类方法研究第二章传统确定数据分类算法概述 2 3s v m 支持向量机 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 建立在计算学习理论的结构风险 最小化原则之上，有坚实的统计学理论基础。s v m 支持向量机中最独特的特点 是，它使用训练实例中的一个子集来表示决策边界，而用来表示决策边界的子集 称为支持向量( s u p p o r t v e c t o r ) 。s v m 支持向量机能够很好地应用于高维数据，能 够避免维灾难。 支持向量机的本质就是通过寻找最大边缘的决策超平面来获取对测试样本 的最好的泛化能力。二类数据集投射到高维空间中，在数据线性可分的情况下， 存在着无数个超平面把其中一类划分到这一超平面的一侧，另一类划分到这一超 平面的另一侧。而所谓的最大边缘决策超平面是指该超平面与最近的两类数据样 本距离最大时的决策超平面。 一个线性s v m 是通过寻找具有最大边缘的超平面，因此也称为最大边缘分类 器。下面对线性分类器的决策边界和边缘进行进一步的讨论。 考虑一个包含n 个训练样本的二元分类问题。数据中的每个样本用一个二元 组( 薯，咒) ( f = 1 ，2 ，) 来表示。其中x j = ( 薯。，一2 ，妇) r 是对应于第i 个样本的属 性集。一个线性分类器的决策边界可以写成如下形式： w x + b = 0 ( 2 7 ) 其中w 和b 是模型的参数。令见= - 1 ，1 表示数据的类别标签。则对于任何测试 样本z 有 f 1 i f w z + b 0 j ，= i 1奸wz+6 o 5 t h e n 8 重置样本权值w = w ，= 1 n l j = 1 ，2 ，n 返回步骤3 9 e n di f m q = 丢m 半 l1 更新训练集中样本权值w ，= w ， p 1 矿( q _ = 乃 。 ip 毋纩( c f ( ) 乃) 1 3 f o r 每一个测试数据样本x td o 1 4 c * ( x ) = a r g m a x ) - ，q 万( q ( x ) = j ，) y 1 5 e n df o r 3 2 3 其他组合分类算法 组合分类器除了上面b a g g i n g 和a d a b o o s t 两种经典算法外，近年来引起了 基于组合分类器的数值型不确定性数据分类方法研究 第三章组合分类器算法概述 很多学者的关注并提出了很多新的组合分类方法。下面简单叙述如下： 在2 0 0 1 年，b r e i m a nl 在文献 3 7 】中提出了r a n d o mf o r e s t 算法，在r a n d o m f o r e s t 算法中，通过随机向量采集决策树的训练样本集，生成一组决策树的子分 类器来组成随机森林。r a n d o mf o r e s t 与a d a b o o s t 相比，a d a b o o s t 算法更集中于 关注那些容易错分的样本，不断地迭代调节每个样本的权重大小，而r a n d o m f o r e s t 算法采用一个固定的概率分布来产生随机向量。r a n d o mf o r e s t 的泛化误 差与所生成的子决策树相关性相关，当随机森林子树数目足够大的时候，其泛化 误差收敛于式( 3 5 ) e i t 。r p ( 1 _ - 广s z ) ( 3 - 5 ) 5 其中p 为决策树之间的平均相关系数，s 为评价决策树的一个参量。同时 r a n d o mf o r e s t 算法不同于a d a b o o s t 算法的迭代生成，可以独立地并行生成，运 行速度相比a d a b o o s t 有很大的提高。随机森林的算法流程示意图如下m ( 3 1 ) ： 步骤2 ：使用随机向量 建立多诀策树 众众aa 图3 1 随机森林算法流程示意图 在2 0 0 6 年，i k u n c h e v a 在文献【5 0 】提出了旋转森林算法。在旋转森林算法中， 先把训练样本随机地分成n 个子集，然后对划分后的子集分别进行p c a 主成分 分析，用主成分p c a 分析后的属性代替原属性。即对k 个子训练集作降维处理， 基于组合分类器的数值型不确定性数据分类方法研究第三章组合分类器算法概述 最后用降维处理后的子训练集构建子分类器。由于经过降维处理后的训练集所构 造的子分类器相比相异度更大，因此旋转森林的分类准确率要比a d a b o o s t 和 b a g g i n g 要更为优秀。在2 0 0 8 年，c h u n x i az