（计算机应用技术专业论文）基于em算法的噪声数据分类模型构造问题研究.pdf

基于e m 算法的噪声数据分类模型构造问题研究摘要 论文题目：基于e m 算法的噪声数据分类模型构造问题研究 专业：计算机应用技术 姓名：秦松 导师：任江涛副教授 摘要 预测分类是数据挖掘中的一个重要的分支部分。它能够用来预测对象的数据 标签。目前，数据分类技术在很多领域都有着广泛的应用，如银行中的风险评估， 市场营销中的客户分类，文本检索分类等。 传统的分类算法主要是针对处理确定数据的情况。所谓确定数据是指数据集 中的每一个数据样本的每一属性维度的值都是唯一确定的。处理确定数据分类问 题的方法很多，如贝叶斯决策、s v m 支持向量机、决策树、神经网络等等。 本文主要研究对被“污染 的噪声数据如何做预测分类模型的构造。在现实 情况中，由于种种条件限制，所采集到的数据往往不是准确的值，而是加入了噪 声的数据。在这种情况下，如何使用这些被扰动的噪声数据构造分类模型，对未 知的准确数据进行分类从而使得分类精度尽可能增加，成为亟待解决的问题。 本论文选题就是研究针对处理这种噪声数据的分类模型构建方法。不同于传 统的确定数据，噪声数据理论上来说是不确定的值。针对这种噪声数据，本文首 先将其转换为一个范围数据对象，使得原始数据在理论上包围在范围数据对象之 内。在这种情况下，这些范围数据每一属性的值不是一个唯一确定的值，而是具 有确定上限值和下限值的范围值。在二维空问中，可以把这种数据对象形象的比 作“框数据 。在处理这样的范围数据分类问题上，本文共使用三种不同的方法 构造分类模型，首先分别采用均值法或者采点法。随后，本论文着重提出了框分 类算法k e m ，对范围数据推导积分公式，构造基于e m 算法的框数据的有限混 合模型，然后构造朴素贝叶斯分类器做分类预测。实验表明，框分类算法对噪 声数据的模型构建具备良好的分类稳定性。 关键词：噪声数据、分类、e m 、朴素贝叶斯 基予e m 算法的噪声数据分类模型构造问题研究 摘要 t i t l e ： m a j o r ： n a m e ： s u p e r v i s o r ： n 圮r e s e a r c ho ft h ec o n s t r u c t i o no ft h en o i s ed a t ac l a s s i f i c a t i o nm o d e l b a s e do nt h ee ma l g o r i t h m 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 s o n g q i n 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 c l a s s i f i c a t i o nf o rp r e d i c t i n gi sa ni m p o r t a n tb r a n c hi nt h er e a l mo fd a t am i n i n g i tc a nb eu s e dt of i g u r eo u tt h el a b e lo ft e s t i n gd a t a n o w a d a y s ，t h et e c h n i q u eo fd a t a c l a s s i f i c a t i o nh a sb e e nw i d e l yu s e di nm a n yp l a c e s ，i n c l u d i n gt h ee s t i m a t i o no f r i s ki n t h eb a n lt h ec l a s s i f i c a t i o no fc u s t o m e ri nm a r k e t i n g ，a n dt h et e x ts e a r c h i n gp r o b l e m 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 na l g o r i t h mi sd e s i g n e df o r t h ec a s eo fc e r t a i nd a t a , w h i c hm e a n st h a tt h ev a l u eo fe v e r ya t t r i b u t ei ne a c hd a t ai sd e t e r m i n a t e t h e r ea r e q u i t eaf e wm e t h o d st os o l v ec l a s s i f i c a t i o np r o b l e m , s u c ha sb a y e sp o l i c e s ，s v m , d e c i s i o nt r e ea n dn e u r a ln e t w o r ka n ds oo i l t h i sp a p e rm a i n | yf o c u so nt h ep r o b l e mt h a th o wt oc o n s t r u c tc l a s s i f i c a t i o n m o d e lb a s e do nt h en o i s e dd a t a s i n c ei nr e a ll i f e ，t h ed a t aw ea c q u i r ei su s u a l l y c o n t a m i n a t e db e c a u s eo fm a n yr e a s o n s i ns u c hc a s e ，t h ed a t aw ep r o c e s si sn o t d e t e r m i n a t ea n di ti sa nu r g e n tp r o b l e mt os o l v et h a th o wt ou s ec o n t a m i n a t e dd a t at o m a k ec l a s s i f i c a t i o nm o d e l i nt h i sp a p e r , w ed i s c u s st h em e t h o do f c o n s t r u c t i n gc l a s s i f i c a t i o nm o d e lb a s e d o nc o n t a m i n a t e dd a t a f o re a c hd a t as a m p l ew et r a n s f o r mi tt oar a n g ed a t ao b j e c t t h e ne a c hd a t ao b j e c ti sn o tas i n g l ev a l u e i n s t e a d , e a c ho b j e c to w n sau p p e rh o u n d a n dal o w e rh o u n d a ts u c hc a s e ，w ec a l lt h i sk i n do fd a t at h e r a n g ed a t a t h e nw e p r o p o s e dt h r e em e t h o d st os o l v es u c hp r o b l e m w ed i s c u s sa n dm a k et h ed e d u c t i o n a b o u tt h ek - e ma l g o r i t h mc o m i n gf i ? o mb a s i ce m a l g o r i t h mi nd e t a i l e d a n dw i t ht h e e x p e r i m e n t ，w ef i n di th a si t so w na d v a n t a g et od e a lw i t hc o n t a m i n a t e dd a t ap r o b l e m k e yw o r d ：u n c e r t a i nd a t ac l a s s i f i c a t i o ne mn a i v eb a y c s n 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：壅控 日 期：丝：笪! 三 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：磊本 日期：仍f 戽易月3 日 新繇仿 嗍沙衬月2 7 日 基于e m 算法的噪声数据分类模型构造问题研究第一章绪论 第一章绪论 随着网络技术的飞速发展，各种各样的信息也在急剧的膨胀。数据挖掘技术 就是针对新的数据类型和海量数据，将传统的数据分析方法与处理大量数据的复 杂算法相结合的分析方法。数据挖掘能够从海量的数据存储中提取人们所需要的 有用信息和构建相关的模型。 传统的数据挖掘方主要是针对确定的数据进行处理。在面对被“污染的不 确定噪声数据时往往不能得到很好的效果。根据噪声数据的产生原理，本文尝试 着通过构造基于噪声数据的范围数据对象，研究如何通过推导范围数据对象的 e m 算法：k e m 算法，构造范围数据的高斯混合有限模型来提高对准确数据的 分类精度的问题。在这一章中，将会先介绍本文研究的背景以及意义，概述不确 定噪声数据的概念以及数据分类的一般方法。最后，给出论文的整个结构安排。 1 1 背景与意义 近年来，信息产业界对数据挖掘产生了极大关注，由于存在大量的数据可以 广泛使用，并且迫切的需要将这些数据转化为有用的信息和知识。而计算机技术 的不断深入发展，极大的加快了数据挖掘在各个领域的应用。目前，数据分类预 测问题在许多领域都有着广泛的应用，在金融领域，如证券、基金、银行；在商 业领域，如零售、营销、市场推广，在教育领域，如学校、研究所等。数据挖掘 能够帮助解决许多大家所碰到的问题，典型的例子如数据库销售，客户群体划分， 交叉销售等市场分析行为，以及客户流失性分析，客户信用评分，欺诈发现等。 综合来说，数据挖掘整个过程可以被当成是数据库工业界进行处理数据两个 过程：( 1 ) 进行采集数据，对数据进行科学化的管理( 其中包括数据存储和提取 等工作) 。( 2 ) 数据分析与理解( 其中包括数据仓库以及数据挖掘) 。举例子来说， 进行数据库的新建并且开发相应的程序进行数据的收集工作，能够为稍后的数据 存储、数据分析等提供良好的支持。如果查询工作和数据的分析工作能够得到很 好的应用的时候，研究者将工作的重心转移到如何更好的对数据进行分析上来。 通过数据挖掘，许多重要的数据规则可以被发现。可以说，数据挖掘对商务决策、 基于e m 算法的噪声数据分类模型构造问题研究 第一章绪论 军事判断、科学研究和医疗诊断做出了巨大的贡献。 数据分类预测是数据挖掘的一个重要的分支。数据分类一般包括两个过程。 第一步是建立分类模型，这一步的主要目的是通过已知的训练数据形成对不同类 标签的数据的一个描述，并且通过分析不同类标签数据属性值的状况来构造模 型。在这里，为建立模型而被分析的数据被称为训练数据集。我们把训练数据集 中的每一个数据对象被称作训练样本，由于提供了每个样本的类标号，该步也可 以称为有指导的学习( 即构建分类模型时候，我们己知每个训练样本属于哪个类 的“指导) 。 第二步，使用模型进行分类。首先要进行评估模型的预测准确率。当对于每 个测试样本，将已知的类标号和该样本的学习模型预测比较。如果认为模型的准 确率可以接受，就可以用它对类标号未知的数据对象进行分类。 训级数据 m c 0 m e s a n d vj o n e s b i l l l e e c o u r t n e yf o x s u s a n c l a i r ep t 矗a s a n d r e b 黜 = 3 0 暑3 0 3 l 4 0 ) 4 0 4 0 3 l 4 a l o w l o w 扭曲 m e d r e e d 挞醢 f a i r 圜e l l 簋吐 僦e n 矗吐 敞 f a i r 口c 碰雠 图卜i 数据分类预测的过程 2 基于e m 算法的噪声数据分类模型构造问题研究 第一章绪论 数据分类学习过程为( a ) 学习：用分类算法分析训练数据，学习模型或分类法以 分类规则的形式提供。彻分类：测试数据用于评估分类规则的准确率。如果准 确率是可以接受的，则规则用于新的数据元组分类。 传统的数据分类问题面对的数据都是确定的准确数据，也就是说，每个样 本点的属性值为准确的数据值。目前，针对这一类问题的研究有着比较成熟的解 决方案。然而，随着技术的不断发展，目前有许多针对噪声数据的问题需要利用 数据挖掘工具来进行分析。此时，由于数据针对原始准确数据有着一定程度的偏 差，数据任一维属性的值不再是准确的。 1 2 主要应用领域 在现实生活领域，有相当多的这一类问题，主要是空间领域( 文献 2 到 3 ) 。 如( 1 ) 交通中的车辆定位问题。对于某一区域的所有车辆，由于成本所限或者是 技术瓶颈，在许多情况下我们并没有办法得知车辆的精确坐标，仅仅知道车辆坐 标的偏离值，如何应用这种偏离值数据来进行数据的建模，对未来的数据进行预 测就是噪声数据挖掘的应用。( 2 ) 医疗数据的预测问题。例如对病人医疗数据的 检测。由于个体在不同时刻的差异性，医疗检测的数据如血压等每次均会有差异， 但总体的值会在小范围内波动存在。利用此种有噪声的数据来进行数据建模也是 噪声数据挖掘的例子。 1 3 目前的解决办法以及相关研究 噪声数据是在原始数据上的偏离而产生的数据值，跟原始数据具备一定的相 关性。但是由于噪声偏离的不确定性，导致噪声数据也是不确定的。目前，针对 不确定性数据的分类预测，已经存在许多的研究工作。支持向量机方面m 】，如 y a n g ，j ，g u n n , s r 通过修改支持向量机的k e r n e l 函数来进行不确定数据的处理 【4 j ；s m i t ht s a n g ，b e nk a o 构造基于决策树的不确定数据分类模型8 】；b i nw a n g ， g a n gx i a o ，h a oy u 提出了基于距离的不确定数据轮廓检测【9 1 ：h a n s - p e t e r k r i e g e l ，m a r t i np f e i f l e 构造基于密度估计的不确定数据挖掘【1 0 1 。数学统计方面， 也有许多理论实践在进行这方面的研究讨论 1 2 - 1 5 ，如利用凸优化的方法来解决噪 声不确定数据的问题【巧】。综合来说，基本的方法是进行替换。通过替换法则， 3 基于e m 算法的噪声数据分类模型构造问题研究第一章绪论 将已知的范围数据转化为确定性的数据，再通过传统的方法对确定性的数据进行 处理建模，形成数据模型。然后，对每一个需要分类的不确定数据，都用同样的 替换法则将其转化为确定数据，代入数据模型中进行预测分类。 这一类的方法的关键部分在于替换法则的选取。可以说，不同的替换法则都 是对范围数据的某种程度上的模拟和近似。此类方法的好处是一旦完成近似的替 换，不确定的数据就变成确定的数据值。由于对确定数据的分类有相当多的比较 成熟的解决方案，因此很容易进行之后确定数据的建模和预测。 然而，由于替换仅仅是对范围数据的近似，无论采取何种法则，都无法完全 利用范围信息来进行数据建模。 1 4 本文主要的研究工作 在本文中，尝试对噪声数据进行数据分类模型的建模。由于现实中的噪声数 据主要是基于原始数据的高斯分布，因此本文尝试着根据此特征将噪声数据转化 为范围数据，使得原始数据存在于范围数据对象之中。然后对范围数据对象进行 分类模型的建模。本文重点推导了范围数据的e m 算法版本，即k e m 算法。实验 中，首先将噪声数据转化为包含准确数据的范围数据对象，然后利用k e m 算法构 造每一类范围数据的有限高斯混合模型，然后将每一类范围数据的有限高斯混合 分布作为类条件概率密度函数，代入朴素贝叶斯分类器，形成范围数据的朴素贝 叶斯分类模型。测试时，将准确的测试数据代入朴素贝叶斯分类模型中，得出测 试数据的标签。通过不同的数据集与质心法、采点法做比较实验，实验结果表明， k e m 算法针对噪声数据的建模比另外两种算法有着更好的效果。 1 5 论文组织 本文的主体分为以下几个部分： 第一部分绪论，介绍了噪声数据分类的背景和意义；简述了噪声数据挖掘 目前的研究成果等，最后列出了本论文的主要研究内容和结构。 第二部分数据挖掘基础以及分类模型。介绍了数据挖掘的基础，讨论了数 据挖掘领域的相关概念和方法，并重点介绍分类了数据挖掘中的主要分类算法： 贝叶斯理论以及朴素贝叶斯分类器等相关内容。 4 基于e m 算法的噪，钉数据分类模型构造问题研究 第一章绪论 第三部分详细讨论了e m 算法的原理，性质，有效性，局限性等。重点推导 了高斯混合模型的极大似然估计量的e m 框架。 第四部分噪声数据分类问题。进行噪声数据问题的介绍，目前的解决办法 等。重点提出了本文中的范围数据对象概念，尝试首先将噪声数据转化为范围数 据，使得范围数据包含原始数据，并且重点推导了范围数据下的积分方式e m 算 法。 第五部分相关比较实验，首先根据原始的数据集合产生噪声数据，然后将 噪声数据转化成为范围数据使得原始数据包含在范围数据当中。在多个实际数据 集以及模拟数据集下实验n o i s e l e v e l 逐步增加下的实验结果，进行质心法a c m 、采 点法s c m 以及本文重点提出的k e m 算法作对比。最后分析了三种方法的时间复杂 度以及局限性。 第六部分总结与展望，总结了本文的研究工作，并讨论了对该研究作了进 一部的深化和展望。 5 基于e m 算法的噪卢数据分类模型构造问题研究第二章数据挖掘基础以及分类模型 第二章数据分类模型基础 信息技术的发展突飞猛进，数据挖掘作为一个新兴的多学科交叉应用领域， 正在各行各业的决策支持活动中扮演愈来愈重要的角色。在日常工作中，科技的 进步使得数据的收集变得越来越便捷，数据量也随之增长。尽管存储介质不断的 变得越来越先进，然而，由于数据量变得越来越庞大，如何从浩如烟海的数据中 将人们感兴趣的信息提取出来常常让人困扰。很多时候，过于庞大的数据量使得 传统的数据分析工具和技术无法处理。并且，随着新的数据不断的呈现，出现了 一些具有新的特点的数据，这时候即使数据集不大，也需要研究用新的方法来进 行一些处理。在这种情况下，急需探索使用新的方法来进行数据处理工作。 数据挖掘就是在这种情况下提出来的，它将传统的分析方法与处理海量的、 无规则的数据的复杂算法相结合，用于从大量的数据中提取出研究者所期望的有 用的信息。本章内容就是介绍数据挖掘概念以及分类模型的基础知识。 2 1 数据挖掘基本定义 一般来说，数据库中的知识发现就被称为数据挖掘，它是一个从大量数据中 抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程。数据挖掘的全程定 义如图所示： 图2 1 数据挖掘的全过程 6 基于e m 算法的噪声数据分类模型构造问题研究 第二章数据挖掘基础以及分类模型 整个知识挖掘( 1 ( d d ) 的过程是由若干挖掘步骤组成的，数据挖掘只是其中 的个主要的步骤。整个知识挖掘的主要步骤包括： ( 1 ) 数据清洗( d a t ac l e a n i n g ) ，就是清除数据噪声和挖掘主题无关的数据 ( 2 ) 数据集成( d a t ai n t e g r a t i o n ) ，主要是将来自多数据源中的相关数据组合 到一起。 ( 3 ) 数据转换( d a t a t r a n s f o r m a t i o n ) ，其作用是将数据转化为易于进行数据 挖掘的数据存储形式。 ( 4 ) 数据挖掘( d a t am i n i n g ) ，知识挖掘的一个最主要步骤，其作用是利用 智能方法挖掘数据的一般规律和潜在的模式。 ( 5 ) 模式评估( p a t t e r ne v a l u a t i o n ) ，可以根据一定的评估标准，从挖掘结 果中筛选出满意的结果。 ( 6 ) 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ，其作用就是利用可视化和知识表 达技术，向用户展示所挖掘出来的相关知识。 2 2 数据挖掘任务 数据挖掘的任务是从大量的数据中提取对研究人员有用的规则信息，通常来说， 分为下面两类基本任务。 ( 1 ) 对目标信息进行预测工作。根据训练数据的属性值，构造预测的模型，当 遇到新的未知标签的数据的时候，通过将未知数据带入预测模型，可以得 到未知数据的预测标签结果。 ( 2 ) 对未知数据进行描述。目的是通过已知的数据分布情况，总结出所有数据 的潜在联系，具体包括数据的异常性检测、相关性检测以及数据的聚合性 等。 7 基于e m 算珐的噪声数据升党摩型构遗劓题研究 第= 章数据挖掘基础u 及分类模型 图2 - 2 数据挖掘的四项基本任务 更加细分的情况下，覆们可以把数据挖掘的目标归为以下的四类。 ( 1 ) 数据预测 预测主要目的是通过对己知的数据分析来对未知数据的属性或者分布趋势 做分析。总共可以分为两大类任务：分类( c l a s s i f i c a t i o n ) ，就是预测未知数据的 标签值；回归( r e g r e s s i o n ) ，对于分类来说，预测的是离散的值，而对于回归， 主要是预测连续的值的发展变化趋势。举例子来说，预测某个酒店客户是否会在 下一个月份来此酒店订房是一个分类问题，判断的标准时该目标变量是二值的。 然而，对油价的变化波动规律进行预测则是回归任务，判断的标准是油价具有连 续值属性。通过对已知的训练数据进行分析建模，构造分类模型，可以对目标的 测试数据进行标签的预测工作。数据挖掘主要通过各种各样的算法来似的测试数 据的预测标签与实际标签差异性最小。实际应用中预测工作可以用来判断信用卡 客户潜在的购物趋向，火山、海啸等地理活动，在医院中可以根据医生的诊断经 验判断病人的患病情况。 ( 2 ) 关联分析( a s c 缸i o n a r i a l y 西s ) 关联分析主要是用来提取所需要分析的数据集合中存在的一些关联性。通常 需要用蕴涵规则的形式来表示关联性的模式。关联分析的主要应用包括超市啤酒 尿布的销售关系，找出具有类似基因的植物苗种，分辨出用户使用服务的关联性 等等。 ( 3 ) 聚类预测( c l u s t e r a n a l y s i s ) 聚类预测也就是根据训练数据的属性值，将关联性较强的一些分为同一个组 基于e m 算法的噪声数据分类模型构造问题研究 第二章数据挖掘堆础以及分类模型 中，从而形成许多个不同的族群。通常使类间距尽可能的大，而类内距离尽可能 的小，使得聚类的类别问差异性明显。聚类的应用包括可用来通过成绩对学生的 情况进行分组、找出具有相同特征的客户群组，以及进行病人病症的归类等。 ( 4 ) 异常发现( a n o m a l yd e t e c t i o n ) 异常发现的主要任务是通过对大量数据的分析处理，从而发现一些远离主流 数据范围的点。我们把这些“非主流 的数据称为异常点。必须注意的是，由于 某些数据点在大量主流数据的边缘地区，很容易被错误的当成异常点的情况。我 们需要研究如何发现确实的异常点，又不会将一些边缘的正常点当作异常点处 理。异常检测的应用范围包括识别信用卡客户的还贷能力，生物细胞的突变性， 以及地理信息中的一些异常情况等。 2 3 分类预测遇到的挑战 数据分类预测作为数据挖掘的一个重要组成部分，在目前社会的各个领域都 得到了广泛的应用。然而，传统的数据分类技术常常遇到一些困难。在这里列举 数据分类所遇到的一些困难所在，它们引发了研究者对数据挖掘的研究。 ( 1 ) 伸缩要求 正如本文前面所述，随着技术的不断进步，人们需要处理的数据量愈来愈大， 数据集开始高速的膨胀起来。现在的数据挖掘算法如果希望处理这些海量数据 集，那么算法必须具备可伸缩性( s c a l a b l e ) 。另外，可能需要研究新的数据结构 来进行对个别记录的访问。 ( 2 ) 维度高 由于信息的指数级增长，目前常常遇到的数据集具有成百上千的维度，跟过 去的几十维属性的数据集相差甚远。比如在地图的测绘中，坐标的空间分量的数 据集具有很高的维度；气象学中，包含各个地区的所测量的温度的数据集，如果 将温度不断的进行重复测量和校对工作，则数据的维度会随着测量次数的增加而 愈来愈多，使得后期的工作量变得非常巨大。在这种情况下，传统的数据分析技 术由于是为低维数据准备的，常常在处理这样的高维数据时候不能得到一个满意 的效果。更加值得提出的是，针对某些算法，当维度增加时候，其计算复杂度也 会随之不断的向上增长。因此需要特定的方法进行高维数据的处理工作。 9 基于e m 算法的噪声数据分类模型构造问题研究 第二章数据挖掘基础以及分类模型 ( 3 ) 存在数据的异种性 过去的分析方法往往只需要处理包含相同类型属性的数据集，这样的数据的 好处是处理简单明了。而当数据挖掘在社会的各个领域的作用越来越明显，其应 用也随之深入到各个地方。这种情况下，越来越需要数据挖掘技术能够处理异种 属性。目前出现的异种的数据对象有空间信息数据，生物细胞基因组数据等。数 据挖掘的科研机构尝试着开发各种挖掘异种对象的技术。 ( 4 ) 分布式数据处理 传统的数据往往是整合在一个地方的。然而，现实生活中，需要分析的数据 有时候不是存放在同一个地方，而是可能存放在多个地区，有时候跨度会遍布全 球。分布式的数据挖掘在这种情况下被提出，分布式数据挖掘算法主要需要解决 的问题有( 1 ) 当分布在各个地区的数据处理的时候，异地的数据需要相互交流 通信，如何降低通信量的问题。( 2 ) 当得到处理结果后，需要将每个资源中的结 果整合起来。( 3 ) 数据再传输过程中安全需要得到保证。 ( 5 ) 非传统的分析模式 目前的分析模式主要是先假设，通过实验，然后利用假设的结果进行检验。 但是，由于这一过程需要花费非常大的时间成本，研究人员希望通过改进这一过 程来提高效率以提高实际的利用价值。具体的做法是希望能够自动地产生假设和 进行评估工作。 ( 6 ) 数据质量问题。许多时候研究人员需要从“污染 的数据中提取出所 需要的规则信息。 2 4 贝叶斯分类器介绍与应用范围 贝叶斯分类器在数据挖掘的分类预测中得到十分广泛的应用，其分类原理是 通过贝叶斯公式，从数据的先验概率和类条件概率中计算后验概率，得到该数据 的每一个类别标签的概率，即后验概率。查看哪个类别标签的概率值最大，然后 选择具有最大后验概率的类作为该数据所属的类。 贝叶斯分类器是一种对属性集和类变量的概率关系建模的方法。在本节中， 会首先介绍贝叶斯定理，它是一种把类的先验知识和从数据中收集的新证据相结 合的统计原理；然后解释贝叶斯定理在分类问题中的应用，接下来描述贝叶斯分 1 0 基于e m 算法的噪声数据分类模型构造问题研究 第二章数据挖掘基础以及分类模型 类器的实现：朴素贝叶斯分类。 2 4 1 贝叶斯定理 假设x ，y 是一对随机变量，它们的联合概率p ( x 毯y = ) ，) 是指x 取值x 且y 取值y 的概率，条件概率是指随机变量在另一随机变量取值已知的情况 下取某一特定值的概率。例如，条件概率p ( y = y i x = x ) 是指在变量x 取值x 的情 况下，变量y 取值y 的概率。x 和y 的联合概率和条件概率满足如下关系： p ( x ，聊= p ( r i x ) 奉尸( x ) = e ( x i y ) p ( y ) ( 2 1 ) 调整上式最后两个表达式得到下面的公式，称做贝叶斯定理： p ( yix ) ：e ( x i ly = ) p 一( y ) ( 2 2 ) p ( x 、 利用贝叶斯定理，可以解决很多实际中的预测问题。 2 4 2 贝叶斯定理在分类中的应用 首先，从统计学角度对分类问题加以形式化。设x 表示属性集，y 表示类变 量。如果类变量和属性之间的关系不确定，那么我们可以把x 和y 看作随机变量， 用p ( y i x ) 以概率的方式捕捉二者之间的关系。这个条件概率又称为y 的后验概 率，与之相对的，p ( 称为y 的先验概率。 在训练阶段，通过从训练数据中收集的信息，对x 和y 的每一种组合学习后 验概率p ( y i x ) 。知道这些概率后，通过找出使得后验概率p ( y i x ) 最大的类r 可 以对测试记录x 进行分类。准确的估计类标号和属性值的每一种可能的组合的 后验概率非常困难，因为即便属性数目不是很大，仍然需要很大的训练集。此时， 可以利用贝叶斯定理用先验概率p ( 的、类条件概率p ( x i y ) 和证据p ( x ) 来表示后 验概率： 刑i x ) = 掣铲 ( 2 - 3 ) 基于e m 算法的噪声数据分类模型构造问题研究第二章数据挖掘基础以及分类模型 在比较不同y 值的后验概率时，分母p ( 总是常数，因此可以忽略。先验概 率p ( y ) 可以通过计算训练集中属于每个类的训练记录所占的比例来估计。对类 条件概率p ( x l 的估计，主要有两种方式来实现：朴素贝叶斯分类器和贝叶斯 信念网络。下面主要介绍朴素贝叶斯分类器的实现方式。 2 4 3 朴素贝叶斯分类器 给定类标号y ，朴素贝叶斯分类器在估计类条件概率的时候假设属性之间条 件独立。条件独立假设可形式化地表述如下： p ( x i y = y ) 2 兀尸( 置tr = y ) 其中每个属性集x = 五，五，局) 包含d 个属性。 ( 2 - 4 ) 在有了条件独立的假设之后，就不必计算x 的每一个组合的类条件概率。只 需要对给定的y ，计算每一个置的条件概率。后一种方法更实用，因为它不需要 很大的训练集就能获得较好的概率估计。 分类测试记录时，朴素贝叶斯分类器对每个类y 计算后验概率： 刖旧：警 ( 2 - 5 ) 由于对于所有的y ，尸( x ) 是固定的，因此只要找出使得分尸( n u ：尸( 五iy ) 最大的类就可以了。若估计分类属性的条件概率，则根据类y 中属性值等于薯的 训练实例的比例来估计条件概率p ( z = 蕾iy = 力。若估计连续属性的条件概率， 则一般使用两种方法来估计连续属性的类条件概率： 1 2 基于e m 算法的噪声数据分类模型构造问题研究第二章数据挖掘基础以及分类模型 ( 1 ) 可以把每一个连续的属性离散化，然后用响应的离散区间替换连续的 属性值。这种方法把连续属性转换成序数属性。通过计算类y 的训练记录中落入 五对应区间的比例来估计条件概率p ( 五ly - y ) 。估计误差又离散区间的数目决 定。如果离散区间的数目太大，则就会因为每一个区间中训练记录太少而不能对 p ( xi y ) 做出可靠的估计。相反，如果区间数目太小，有些区间就会含有来自不 同类的记录，一次失去了正确的决策边界。 ( 2 ) 可以假设连续变量服从某种概率分布，然后使用训练数据估计分布的 参数。高斯分布通常被用来表示连续属性的类条件概率分布。该分布有两个参数， 均值和方差盯2 。对每个类乃，属性五的类条件概率等于 盹刮卜舻南p 首 ( 再一鳓) l ( 2 - 6 ) 其中，参数鳓可以用类乃的所有训练记录关于五的样本均值( i ) 来估计。 类似的，参数秀可以用这些训练记录的样本方差( s 2 ) 来估计。另外由于函数 是连续的，所以随机变量五取某一特定值的概率为0 。取而代之的是，计算置落 在区间五到k + s 的条件概率，其中占是一个很小的常数： 禹+ 0 尸( 薯五五+ 占i 】，2 乃) 2 。乃( 五；心，) 戤( 置；心，) 毒占 ( 2 7 ) 由于占是每个类的一个常量乘法因子，在对后验概率p ( rix ) 进行规范化的 时候就抵消掉了。因此，我们仍可以使用( 2 5 ) 来估计类条件概率p ( 五ly ) 。 综上，朴素贝叶斯分类器则进行分类主要有两个步骤。第一是对训练数据进 行分析，通过分析，从训练数据集合中得到每个类别数据的类条件概率函数。第 二阶段是构造完成的朴素贝叶斯分类器对未知标签的数据进行预测，通过计算得 到每个数据的每种标签的条件概率，选取最大概率的类别标签值作为其类别，对 数据进行分类。 1 3 基于e m 算法的噪声数据分类模型构造问题研究第二章数据挖掘基础以及分类模型 在本文中，对类条件概率的估计采用e m 算法迭代进行，通过构造每个类别 数据的高斯混合有限模型，将高斯混合有限模型作为类条件概率密度函数代入朴 素贝叶斯公式当中，对未知的测试数据进行分类处理。 2 4 4 朴素贝叶斯分类的特点 和决策树模型相比，朴素贝叶斯模型由于发源于古典数学理论，因此有着坚 实的数学基础，以及稳定的分类效率。同时，贝叶斯模型所需估计的参数相对较 少，对缺失数据不太敏感，算法也比较简单。理论上，贝叶斯模型与其他分类方 法相比具有最小的误差率。但是实际可能会有偏差，这是因为贝叶斯模型假设属 性之间相互独立，这个假设在实际应用中往往是不成立的，这给贝叶斯模型的正 确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，贝叶斯 模型的分类效率比不上决策树模型。而在属性相关性较小时，贝叶斯模型的性能 最为良好。 另外，贝叶斯分类的特点是并不把一个对象绝对的指派给某一类，而是通过 计算得出该数据应该划归于哪一个类别。在这种情况下，可以看到整个分类的过 程中所有的属性都会对最终的分类结果造成影响。而并不是一个或者几个属性决 定分类，是所有属性都参与分类。 2 5 小结 本章主要概述了数据挖掘的一些相关概念。明确数据挖掘的任务以及基本的 方法理论。主要展示了贝叶斯理论以及朴素贝叶斯分类器目前的研究现状和应用 范围等。 1 4 基于e m 算法的噪声数据分类模型构造问题研究第三章e m 算法及高斯混合模型概述 第三章e m 算法及高斯混合混合模型概述 e m 算法【海1 8 】是机器学习领域的一种经典算法。作为一种期望最大化算法，许 多文献均有描述。e m 算法的主要特征是并不直接对繁杂的后验分布进行极大化 计算，而是在目前已知数据的基础上加上一些“假定数据 ，这样使得已知的信 息增加，从而能够简化整个计算并且完成一系列简化的极大化的过程【1 9 1 。e m 算 法其实是一种从“不完全数据 中求解模型参数的极大似然方法。通俗的说，e m 算法就是这样，假设我们估计知道a 和b 两个参数，在开始状态下二者都是未知 的，并且知道了a 的信息就可以得到b 的信息，反过来知道了b 也就得到了a 。 可以考虑首先赋予a 某种初值，以此得到b 的估计值，然后从b 的当前值出发， 重新估计a 的取值，这个过程一直持续到收敛为止。 一般来说，主要有两种情况造成“不完全数据的产生。一种是由于技术手 段或者设备仪器方面的缺陷，使得在获取数据过程中产生的错误，造成得到的原 始数据的丢失或者不准确的情况；另外一种则是通过优化函数来计算参数值比较 困难。引入额外的隐藏的参数后，相对比较容易优化。e m 算法就是这样一种情 况，我们把原始数据加上额外的数据组成“完全数据，从而原始数据变成了“不 完全数据 。 3 1e m 算法原理 首先介绍一下经典酬算法的原理，设我们所能够观察到得数据为y ，而完全 数据x - ( y ，z ) ，z 是缺失数据，秒是模型参数，在这里假设9 关于y 的后验分 布p ( e iy ) 很复杂，统计计算会比较困难，那么如果我们能够假定已知一些无法 观察到的潜在数据，则可能得到一个关于秒的相对简单的添加后验分布 p ( o i l z ) ，利用p ( o i y ，z ) 的简单性方便进行各种统计计算。而在完成计算后， 在通过计算结果，对z 的种种假设进行验证并修订。如此进行，就可以将一个复 杂的极大化的问题转化为较简单的一个极大化问题。 1 5 基予e m 算法的噪卢数据分类模型构造问题研究 第三章e m 算法及商斯混合模型概述 e m 算法作为一种迭代算法主要是应用于求极大似然估计，我们定义以下的不 完全数据模型： 这里假定有两个样本空间x 和y ，x 是完全数据，而y 是不完全数据。定义 映射h ：x _ y 是x 到y 的多对一映射。设g ( o l 即表示0 的基于观察数据y 的后 验分布的密度函数，称此密度函数为观察后验分布。f ( oiy ，z ) 表示添加数据z 后得到的关于口的后验分布密度函数，称为添加后验分布。k ( zl 】，p ) 表示在给 定口和观察数据y 下潜在数据z 的条件分布密度函数，需要计算观察后验分布 g ( oy ) 的极大似然估计量。 于是e m 算法如下进行，设0 。为i + 1 次迭代开始时参数的估计值，则第i + 1 次开始的迭代的两步为： e 步：对f ( o i 】，z ) 或者l o g f ( o l 】，z ) 求条件期望。 即q ( 口，0 。) = 易 1 0 9 f ( o y ，z ) iy ，】- i l o g f ( o iy ，z ) k ( z iy ，0 ) 忽 ( 3 1 ) m 步：将o ( o ，) 极大化，找到一个点0 1 ，使得q ( o m , o ) = m a x q ( o ，0 ) 即= a r g m a x q ( o ，0 。) ( 3 2 ) 如此形成一次迭代，专口“1 ，设定阀值，将上述e 步和m 步反复迭代直到 渺一0 i + 1 l l 或者1 1 q ( + 1i ，n q ( i ，r l l ，j 、于等于阀值的时候停止。 3 2e m 算法的主要性质 e m 算法最重要的特点就是其简单性和稳定性。由于是迭代算法，e m 得到的 估计序列是否收敛非常重要。另外，收敛的话，结果是否就是我们所需要的原不 完全数据的极大似然估计量m l e 或者是它的对数似然函数的最大值或者局部最 大值也非常值得注意。为此，下面引用几个重要的结论来说明e m 算法的收敛性。 记e m 算法得到的收敛序列为 0 ，i = l ，2 z ( o l 功= l o ge ( o ly ) 定理1 ：e m 算法在每一次迭代后均提高( 观察数据) 后验分布的极大似然估 计量，即 1 6 基予e m 算法的噪声数据分类模型构造问题研究第三章e m 算法及高斯混合模型概述 尸( + 1ly ) 尸( l y ) ( 3 3 ) 如果e ( oi y ) 有上界，那么三( iy ) 可以收敛到z 。 推论l ：如果对任意的不属于f ，有三( “iy ) 三( 矿ly ) ，f 是似然函数 l 的稳定点集合。 定理2 ：如果q ( ，p ) 关于p 和都连续，则在关于l 的很一般的条件下，由 e m 算法得出的估计序列的收敛值0 + 是l 的稳定点。 事实上，酬算法具有局部最优的特性，其收敛值受到初始跚值的很大的影 响。在一般情况下，e m 算法的结果只能保证结果收敛到后验概率分布密度函数 的稳定点，但是我们无法得知算法的结果是否收敛到了极大值点。由于存在这种 局部最优的可能性，在实际操作当中，通常会选取多个初始值来进行e m 的迭代 运算，然后选择其中效果最好的那个。而e m 算法得到广泛应用的一个重要的原 因是由于其在m 步中，求极大值的方法与完全数据下求极大值的方法完全一样。 很多情况下这样的极大化有显示的表达式。然而，有时候我们找不到这样一个现 实的表达式来进行一个计算。那么，有时候要找一个使得q ( ，“) q ( ，0 ) ， 这种e m 算法称为广义的e m 算法，由于每一个迭代都隐含着一个映射，我们用 m ( o ) 来表示广义的e m 算法所隐含的映射，即对任意的口，有 q ( m ( p ) ，口) q ( o ，9 ) 。 定理3 ：对于广义的e m 算法，有l ( m ( o ) iy ) 三( 引y ) ，且当 q ( m ( p ) ，d = q ( 口，口) 和k ( zly ，m ( 秒) ) = k ( zi 】，9 ) 均成立时，等号成立。 推论2 ：假如对于任意的9 ，存在一些矿，存在( 矿l d l ( o l d ，那么有 l ( m ( o ) iy ) = 三( 口l 功，q ( m ( 矿) ，0 ) = q ( 口，矿) ，k ( z iy , m ( o 。) ) = k ( ziy ，0 。) ， 也就是说，如果朗算法收敛到一个全局最优解，则似然函数在这些点上的值是 不变的。 推论3 ：假如存在一些矿，对任意的0 矿，有l ( o iy ) l ( o l ”( 比如说 0 。可以是唯一的全局最优解) ，那么对于广义的e m 算法而言，有m ( o ) = 矿。也 1 7 基于e m 算法的噪声数据分类模型构造问题研究第三章e m 算法及高斯混合模型概述 就是说，如果e m 算法收敛到唯一的全局最优解，则参数秒在每一次迭代中均保 持不变，口= 矿。 3 3e m 算法的改进版本广义e m e m 算法存在局部最优，初始化问题以及收敛速度慢等缺点，目前研究领域存 在一些改进的方案，下面对其中的一个做简单介绍。 之所以e m 算法广泛应用于很多领域，一个很重要的原因是在m 步中求极大 化的方法与完全数据下求极大化的方法一样，很多情况下