（计算机应用技术专业论文）基于规则的数据分类算法在铁路运输信息中的应用.pdf

堕玺堡曼三查耋三兰塑圭兰堡兰兰 基于规则的数据分类算法在铁路运输信息中的应用 摘要 随着我国铁路信息化建设的快速发展，铁路运输中产生的信息数据的 规模迅速膨胀，且数据类型纷繁复杂，对铁路运输管理技术人员提出了全新 的挑战。然而，目前铁路运输信息系统却只能提供一些常规查询和统计功 能，还不具备对铁路运输信息进行实时分析和预测的能力，故无法完全满足 铁路运输的实际需要。如何有效地组织和利用海量的铁路运输信息数据，揭 示隐藏在数据背后本质联系，为铁路运输管理提供更为准确、直观的指导方 案是铁路信息化建设亟待解决的重要课题，同时也是本论文研究的主旨所 在。 本文系统的介绍了数据挖掘领域的发展概况，阐述了基于统计的数据 分类的一般内容。在充分比较分析了基于朴素贝叶斯和支持向量机两种统计 分类算法的基础上，针对将它们应用于铁路运输信息数据分类时存在的一些 问题进行了深入剖析。通过研究发现，当类别之间交叉现象比较严重时( 即 类间的特征重复较多时) ，分类器的精度会大大下降，尤其是在多层分类 中，有些子类之间的特征交叉更为严重，即使在大类别基本正确的情况下， 子类的分类精度也会大幅度降低，严重影响对子类数据进行进一步预测分 析，从而导致整体预测结果失效。 针对基于统计的分类方法的上述不足，本文进一步提出了新的基于规 则的铁路运输信息数据分类方法。该方法结合统计分类方法，通过定制面向 铁路信息系统的行业分类规则，设计出基于专家规则的分类器，并构建出具 有高准确性的分类模型。此外，进一步将本研究所提出的分类策略应用于铁 路运输管理信息系统的数据分类中，进行实际系统测试，取得了较好的分类 性能。 最后，本文还对于基于统计的各种分类方法所得到的结果进行了比较 分析，结果表明，由于铁路运输信息数据的特殊性( 强周期和季节性等) ， 只有在基于统计的分类方法基础上引入专家规则，使二者有机结合，才能取 得较好的分类结果。同时，本文所提出的基于规则的分类器的泛化和扩展能 力方面也优于基于统计的分类方法，故在铁路运输信启、管理领域有着广泛的 应用前景。 关键词数据分类：贝叶斯分类；支持向量机；特征交叉 堕玺堡些三查耋三兰塑圭兰竺丝兰 a p p l i c a t i o no f d a t ac l a s s i f ym e t h o db a s e do nr u l ei n r a i lt r a n s p o r ti n f o r m a t i o n a b s t r a c t a l o n gw i t ht h er a p i dd e v e l o p m e n to f c h i n ar a i l w a yi n f o m a t i o n i z i n g c o n s t r u c t i o n ( c r i c ) ，t h es c a l eo fd a t ap r o d u c e db yr a i l w a yt r a n s p o r tp r o c e s s e x p e n d se x t r e m e l ya n dt h ed a t at y p e sa r ee x c e e d i n g l yc o m p l i c a t e d ，w h i c hb r i n g n e wc h a l l e n g e st om a n a g e r so fr a i ls y s t e m h o w e v e gc u r r e n tr a i l w a yt r a n s p o r t m a n a g ei n f o r m a t i o ns y s t e m ( r t m i s ) ，w h i c ho n l yp r o v i d es o m eo r d i n a r yq u e r y a n ds t a t i s t i c sf u n c t i o n sa n dw i t h o u tt h ec a p a b i l i t yf o rr e a l - t i m ea n a l y s i sa n d p r e d i c t i o no nr a i l w a yt r a n s p o r ti n f o r m a t i o n ，c o d ln o tm e e tt h en e e d so fr a i l w a y t r a n s p o r tp r a c t i c e t h e r e f o r e ，h o wt oo r g a n i z ea n du t i l i z e t h em a s sr a i l w a y t r a n s p o r td a t ai na ne f f i c i e n tw a yt od i s c o v e rt h ei n t r i n s i cr e l a t i o n sa m o n gt h e m a n dt h e n ，p r o v i d em o r ea c c u r a t ea n dd i r e c t i n s t r u c tt o r a i l w a yt r a n s p o r t m a n a g e m e n t ，b e c o m e sa ni m p o r t a n tt a s kt ob es o l v e di nc r i ca n di s a l s ot h e r e s e a r c hp u r p o s eo ft h i sp a p e r i nt h i sp a p e r ，w ei n t r o d u c et h ep r o g r e s so fd a t am i n i n ga n dd e s c r i p ts o h l e g e n e r a lc o n t e n t sa b o u ts t a t i s t i c sb a s e dc l a s s i f i c a t i o n ( s b c ) b ya n a l y z i n gt v , 7 0 m e t h o d sb a s e do nn a i v eb a y e s i a na n ds u p p o r tv e c t o rm a c h i n e ( s v m ) ，w e i n v e s t i g a t ec h i e fd e f e c t so c c u r r e di nt h e i ra p p l i c a t i o n st ot h ec l a s s i f i c a t i o no f r a i l w a yt r a n s p o r td a t a t h er e s u l ts h o w st h a t ，w h e nt h e r ea r es e r i o u so v e r l a p s a m o n gc l a s s e s ，t h ep r e c i s i o no fc l a s s i f i e rw i l ld e s c e n d e s p e c i a l l y ，i nh i e r a r c h i c a l c l a s s i f i c a t i o n ，t h ef e a t u r e so fd i f f e r e n ts u b c l a s s e si so v e r l a p p e d ，t h ec l a s s i f i c a t i o n a c c u r a c yo ns u b c l a s s e si sd a m a g e de v e nt h o u g hf a t h e r c l a s s e s f i r ec l a s s i f i e d c o r r e c t l y ，w h i c hc a ni m p e d ef u t u r ec l a s s i f i c a t i o ni nt h en e x tl a y e ra n df i n a l l y c a u s et h er e s u l to fg l o b a lc l a s s i f i c a t i o nb e c o m e si n v a l i d t oa d d r e s st h ea b o v ep r o b l e m so fs t a t i s t i c a lc l a s s i f i c a t i o nm e t h o d s ，w e p r o p o s ean o v e lr u l eb a s e dc l a s s i f i e rf o rr a i l w a yt r a n s p o r ti n f o r m a t i o n i nt h i s m e t h o d ，b ye s t a b l i s h i n gr a i l w a yt r a n s p o r tp r o f e s s i o n a lr u l e st od e s i g n an i l e 堕堡鎏竺三查兰三兰堡圭兰堡丝兰 b a s e dc l a s s i f i e r ，ar o b u s tc l a s s i f i c a t i o nm o d e li sb u i l d f u r t h e r m o r e ，w ec a r r yo u t at e s tb ya p p l y i n gt h i sm o d e lt or t m i sa n dg e ts a t i s f i e dr e s u l t ， f i n a l l y , w em a k eac o m p a r a t i v ea n a l y s i so fd i f f e r e n tm e t h o d s t h er e s u l t i n d i c a t e st h a t ，d u et ot h e s p e c i a lc h a r a c t e r s ( i e s t r o n gp e r i o d i c i t ya n d s e a s o n a l i t y ) ，t oo b t a i na ne x c e l l e n tc l a s s i f i c a t i o nr e s u l t ，o n em u s ti n c o r p o r a t e d e x p e r tr u l e si n t os b c m o d e la n dc o m p l e m e n t se a c ho t h e lb e s i d e s ，t h ep r o p o s e d r u l eb a s e dc l a s s i f i c a t i o nm o d e li sp r o v e dt op o s s e s so u t s t a n d i n gg e n e r a l i z a t i o n a n de x t e n s i v ea b i l i t yc o m p a r e dt ot h es t a t i s t i cb a s e do n e sa n dt h e r e f o r eh a sa p e r s p e c t i v ef u t u r ei nr a i l w a yt r a n s p o r ti n f o r m a t i o nm a n a g e m e n ta p p l i c a t i o n k e y w o r d s d a t a c l a s s i f i c a t i o n ；b a y e s i a nc l a s s i f i c a t i o n ；s u p p o r t v e c t o r m a c h i n e ；f e a t u r eo v e r l a p v 1 1 课题背景 第1 章绪论 数据库系统特别是关系数据库系统的成功，使我们有了强有力的事务处理 工具。在计算机的帮助下，我们可以将传统的事务处理做得更好。不满足现状 是社会前进的动力，人类当然不会满足于让计算机仅仅做事务处理，试图将数 据库技术应用到更广泛的领域，新的应用导致对新的数据模型的需求，从而激 发了扩充关系的、面向对象的、对象一关系的、演绎的等新数据模型和数据库 系统的研究和开发。各种各样的数据库系统的开发，使得更多的数据以前所未 有的速度收集在计算机中。当然，我们不会满足于对这些数据的简单查询。从 信息处理的角度，我们更希望计算机帮助我们分析数据、理解数据、帮助我们 基于丰富的数据做出决策，做人力所不能及的事情。于是，数据挖掘从大 量数据中用非平凡的方法发现有用的知识就成了一种自然需求。正是这种需求 引起了人们的广泛关注，导致了数据挖掘研究的蓬勃发展川。 在现代科学和工程研究领域，“首要原则模型( f i r s t - p r i n c i p l em o d e l s ) ”已 经被广泛应用于对物理、生物和社会系统等问题的描述和求解。换句话说，我 们往往要用实验数据来验证基本的“首要原则模型”，并对一些难以直接测量 或者根本不可能直接测量的参数进行评估。但是在许多领域，基本的“首要原 则模型”往往是未知的，并且由于待研究系统的高度复杂性经常会导致研究人 员难以直接用数学方法来对问题进行求解【2 j 。 随着计算机的广泛应用，对于复杂系统生成的海量数据，即使在无法满足 “首要原则模型”所要求的前提条件的情况下，我们也可以利用某些易得的可 用数据，通过对系统变量之间可以利用的关系( 即未知的输入输出相关性) 进 行评估来导出模型。实际上，传统的建模方法是基于“首要原则模型”的分析 方法和建模技术，与直接对数据进行相应分析的方法之间普遍存在着范型变 换。如何对大型的、复杂的、信息分赴的数据集进行有效理解，是所有的商 业、科学、工程等领域相关研究亟待解决的关键课题之一口】。 当今国际竞争的日趋激烈，有效吸取隐藏在各种纷繁复杂的数据后面的有 用知识，并充分利用这些知识的能力变得愈加重要。为了解决这些问题，人们 丌始将目光转向一个新兴的信息技术数据挖掘( d m ，d a t am i n i n g ) 。 数据挖掘是一个多学科交叉领域，这同样是很自然的事。一方面，先要以 非平凡的方法发现蕴藏在大量数据集中的有用知识，数据挖掘必须从数据库技 术、人工智能、机器学习、神经网络、统计学、模式识别、知识库系统、知识 获取、信息提取、高性能计算和数据可视化等学科领域吸取营养。另一方面， 这些学科领域也需要发展，也在从不同角度关注数据的分析和理解，数据挖掘 也为这些学科领域的发展提供了新的机遇和挑战f 5 】。 1 2 数据挖掘的发展概况 近年来，数据挖掘技术引起了信息产业界的极大关注，其主要原因是存在 大量数据可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知识。 获取的信息和知识可以广泛应用于各种应用，包括商务管理、生产控制、市场 分析、工程设计、和科学预测等。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的数据中， 提取隐含的、人们事先不知道的、但又是潜在的有用信息和知识的过程。它可 以为海量数据处理问题提供有效的解决方案。通常，人们把原始数据看作是形 成知识的源泉，知识的挖掘过程就好似从矿石中提炼金属。在数据挖掘过程 中，原始输入数据可以是结构化的，也可以是半结构化的，甚至是分布在网络 不同节点上的异结构型数据源。知识发现的方法可以是数学的，也可以是非数 学的；可以是演绎的，也可以是归纳的。所发现的知识可以被运用于信息管 理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此， 数据挖掘是一门很广意义上的交叉科学，它汇集了来自不同领域的最新研究成 果，其研究往往需要各领域研究人员的相互协作，尤其是数据库、人工智能、 数理统计、可视化、并行计算等方面的学者和技术人员。数据挖掘技术从一开 始就是面向应用的。它的研究目的不仅仅是实现面向特定数据库的简单的检索 查询调用，而且要进一步对这些数据进行微观或宏观的统计、分析、综合和推 理，直到实现对实际问题的求解，并通过对所发现的事件间本质关联的建模， 来达到利用已有的数据对未来的活动进行预测的最终目的【7 j 【引。 数据挖掘是信息技术自然演化的结果，演化过程的见证是数据库业界开发 以下功能( 见图1 1 ) ：数据收集和数据库创建，数据管理( 包括数据存储和检 索，数据库事务处理) ，以及分析和理解( 涉及数据仓库和数据挖掘) 。例如， 数据收集和数据库创建机制的早期开发已成为稍候数据存储和检索、查询和事 务处理有效机制开发的必备慕础。随着提供查询和事务处理的大量数据库系统 广泛付诸实践，数据分析和理解自然成为下一个目标一j 。 矍筌堡矍三查兰三耋堡圭兰堡篁兰 图l - 1 数据库技术的演化 f i g u r e 卜1d e v e l o p m e n to f d a t a b a s et e c h n o l o g y 自2 0 世纪6 0 年代以来，数据库和信息技术已经系统地从原始的文件处理 演化到复杂的、功能强大的数据库系统。自7 0 年代以来，数据库系统的研究 和丌发已经从层次和网状数据库系统发展到开发关系数据库系统、数据建模工 哈尔滨理工大学工学硕士学位论文 具、索引和数据组织技术。此外，用户通过查询语言、用户界面、优化的查询 处理和事务管理，可以方便、灵活的访问数据。联机事务处理( o l t p ) 将查 询看作只读事务，对于事物的发展和广泛地将关系技术作为大量数据的有效存 储、检索和管理的主要工具做出了重要的贡献。 8 0 年代中期以来，数据库技术的特点是广泛接受关系技术，研究和开发新 的、功能强大的数据库系统。这些使用了先进的数据模型，如扩充关系模型、 面向对象模型、对象关系模型和演绎模型。包括空间的、时间的、多媒体 的、主动的和科学的数据库、知识库、办公信息库在内的面向应用的数据库系 统。设计分布性、多样性和数据共享问题被广泛研究。 现在，数据可以存放在不同类型的数据库中。最近出现的一种数据库结构 是数据仓库。这是一种多个异种数据源在单个站点以统一的模式组织的存储， 以支持管理决策。数据库技术包括数据清理、数据集成和联机分析处理 ( o l a p ) 。o l a p 是一种分析技术，具有汇总、合并和聚集功能，以及从不同 的角度观察信息的能力。尽管o l a p - v 具支持多维分析和决策，对于深层次的 分析、如数据分类、聚类和数据随时间变化的特征，仍需要其他分析工具【l 。 数据挖掘涉及多种科学技术的集成，包括数据库技术、统计学、机器学 习、高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号 处理和空间数据分析。在本文讨论数据挖掘时，我们采用数据库观点。即着重 强调大型数据库中有效的和可伸缩的数据挖掘技术。一个算法是可伸缩的，如 果给定内存和磁盘空间等可利用的系统资源其运行时间应当随数据库大小线 性增加。通过数据挖掘，可以从数据库提取有用的知识、规律或高层信息，并 可以从不同角度观察和浏览。发现的知识可以用于决策、过程控制、信息管 理、查询处理，等等。因此，数据挖掘被信息产业界认为是数据库系统最重要 的前沿之一，是信息产业最有前途的交叉学科。 数据挖掘可粗略地理解为三部曲：数据准备( d a t ap r e p a r a t i o n ) 、数据挖 掘，以及结果的解释评估( i n t e r p r e t a t i o na n de v a l u a t i o n ) 【l 1 。 根据数据挖掘的任务分，有如下几种：数据分类、预测模型、数据总结、 数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和 趋势发现等等1 12 】。 根据数据挖掘的对象分，有如下若干种数据源：关系数据库、面向对象数 据库、空间数据库、时态数据库、文本数据源、多媒体数据、异质数据库、遗 产( 1 e g a c y ) 数据库以及w e b 数据源【l 。 根据数据挖掘的方法分，可粗分为：统计方法、机器学习方法、神经网络 哈尔滨理工大学工学硕士学位论文 方法和数据库方法。统计方法中，可细分为：回归分析( 多元回归、自回归 等) 1 4 】、判别分析( 贝叶斯判别、费歇尔判别、非参数判别等) f i ”、聚类分析 ( 系统聚类、动态聚类等) 1 6 q s 、探索性分析( 主元分析法、相关分析法 等) 、以及模糊集、粗糙集、支持向量机等。机器学习中，可细分为：归纳学 习方法( 决策树、规则归纳等) 、基于范例的推理c b r , 遗传算法、贝叶斯信 念网络等。神经网络方法，可细分为：前向神经网络( b p 算法等) 、自组织神 经网络( 自组织特征映射、竞争学习等) 等。数据库方法主要是基于可视化的 多维数据分析或o l a p 方法，另外还有面向属性的归纳方法【1 9 】f 2 。 1 3 数据分类技术的发展概况 1 3 1 数据分类的标准 数据分类标准的选择与特定的数据分类任务密切相关，应该依据当前的分 类任务去选择分类标准，可能在下次分类的任务中也许要选择完全不同的分类 标准。 类应该具有类内高凝聚性和类问凝聚性的特点。在进行分类时，要求类内 的对象之间具有很高的相似性，极高凝聚性，而不同类的对象则具有很大的差 异，即低凝聚性。如何衡量相似性程度，不同的分类方法采用不同的标准。如 在聚类分析中一般采用对象之间的欧式距离来判别对象之间的相似程度。而在 基于概念的面向属性归纳的分类方法中，不同的对象如果能够抽象为同一概 念，则认为他们是相似的，否则为不相似。有些对象要经过多次抽象才可能成 为同一概念。这样做简化了问题。 分类的标准还与具体的分类任务有关，对同样的数据既可以采用不同的分 类标准来满足不同的分类任务。对于相同的数据集的不同的分类任务要选择不 同的数据概念层次，设定不同的类门限值，选择不同的分类属性，这样就会产 生不同的分类结果 2 1 q 3 j 。 1 32 数据分类的研究方法 数据分类( d a t ac l a s s i f i c a t i o n ) 是一个两步过程。 第一步，建立一个模型描述预定的数据集或概念集。通过分析由属性描述 的数据库元组来构造模型。对于分类，数据元组也称作样本、实例或对琢。为 哈尔滨理工大学工学硕士学位论文 建立模型而被分析的数据元组成训练数据集。训练数据集中的单个元组称作训 练样本，并随机的由样本选取。通常，学习模型由分类规则、判定树或数学公 式的形式提供。 第二步，使用模型进行分类。首先评估模型( 分类法) 的预测准确率。保 持方法是一种使用类标号样本测试集的简单方法，这些样本随机选取，并独立 于训练样本。模型在给定的测试集上的准确率是正确被模型分类的测试样本的 百分比。 对于每个测试样本，将已知的类标号与该样本的学习模型类预测比较。如 果模型的准确率根据训练的数据集评估，可能评估是乐观的，因为学习模型倾 向于过分适合数据。如果认为模型的准确率可以接受，那么就可以对他的类标 号未知的数据元组或对象进行分类，由此可见分类的准确性是何等关键【2 4 1 。 目前，数据分类的主要研究方法都是基于统计的方法并取得了可喜成果。 其主要算法有：k 近邻法( k n n ) 胆”，朴素贝叶斯法( n a i v eb a y e s ) 1 2 6 j ，贝叶斯 网络 2 7 l ，神经网络算法 2 8 1 ( 如：b p 算法等) ，支持向量机口9 ( s u p p o r tv e c t o r m a c h i n e ) ，e m 算法【j ，s o m t “1 算法。 基于这些算法，人们研究了应用于各个系统的分类器，系统中的分类器的 作用就是：根据特征提取其得到特征向量来给一个被测对象赋一个类别标记。 一般的任务是确定每一个可能类别的概率。有输入数据特征向量表示所提供的 抽象，使得建立大规模领域独立的分类理论成为可能。 1 3 3 数据分类方法存在的问题 基于统计的分类方法，根据训练数据，得到各类别的模板，进而通过模板 进行分粪。其优点是训练简单方便，一般情况下分类精度高，但也不可避免存 在一些问题，其缺点主要有两点： 1 基于统计的分类方法存在过学习问题，在存在样本集的时候，数据分 类测试比较准确，但是其分类规则存在风险，如果完全依赖于这种方法，当类 别之间交叉现象比较严重，也就是说两个类别有较多的特征重复，这时以这种 分类方法所设计的分类器的精度会大大下降，会因为分类条件相似或相近而无 法判断数据的类别，会导致数据分类错误过多，无法进行预测，导致分类不准 确，更严重会使数据分类陷入死循环，最后导致分类的失败。 2 如果数据对训练数据的数量与质量均有较严要求，那么基于小样本的 统计分类方法步能够及时进行调整，数据分类的准确度将会大大降低，尤其是 哈尔滨理工大学工学硕士学位论文 具有专业规则的行业数据，分类器在分类时，无法进行准确分析，使分类结果 不可用。 1 4 课题的提出及本项目研究的意义 1 4 1 问题的提出 本课题韵研究内容是建立在铁路运输管理信息系统数据的基础上，虽然铁 路运输信息系统的数据是海量的，但实际应用中只是简单的查询、统计，很多 数据没有被真正运用起来，如何更好的并合理的运用这些数据被提到日程上 来。我们根据铁路运输信息系统数据的实际情况，提出了进行数据挖掘的想 法，想从这些海量的数掘中提取有用的信息( 知识基) ，做出分析和预测模 型，更好地为铁路运输服务，而在数据分析处理的过程中，在关键步骤数据分 类时发现，如果我们采用的分类方法是基于统计的，那么当类别之间交叉现象 比较严重时( 两类之间的特征重复较多) ，分类器的精度会大大下降，尤其是在 多层分类中，有些子类之间的特征交叉更为严重，因此在大类别基本正确的情 况下，子类的分类精度却大大下降，严重影响我们对子类数据进行预测分析 从而导致整体预测的非可用。我们应该及时调整分类方法，也就是分类法不能 是简单的基于统计的，而应该结合以特征，也就是分类规则，重新开发分类 器，这样才能使我们的分类更加准确，使我们的预测模型更加接近实际，更好 的投入实际运用。 1 4 2 本课题的研究意义 通过我们在铁路运输系统的数据的研究，在数据分类过程中，存在特征交 叉即类或子类存在特征重复时，若我们采用基于统计的分类法进行分类，那么 分类的准确度会大大降低，从而影响分析和预测模型。我们就此问题进行深入 研究，提出了基于规则的分类法，并结合统计分类法，做出规则分类器，从而 可以提高数据分类的准确度，根据相对准确的数据分类，就可以做出更加贴近 实际的数据模型，使分析和预洲更为精确。 本课题的研究具有理论和现实的双重意义，它可在己经获得成功的基于统 计的分类算法的基础上更好地解决特征重复数据的分类问题，很好地解决了数 据挖掘关键步骤的准确性。这一研究成果，不仅仅适用于铁路运输系统，更适 堕堡堡塞三查兰三兰堡圭兰篁篁兰 用于各种拥有海量数据的大型新新系统，使各系统能准确地对数据进行分类 更好地进行数据模型的预测，从而增加模型的可信度，和可用度。 1 5 本课题主要研究内容 本文系统的介绍了数据挖掘和数据分类领域的技术发展概况，并对数据分 类的标准及方法进行了深入的探讨。在充分比较分析了基于统计的数据分类算 法( 如朴素贝叶斯、支持向量机) 的基础上，剖析了基于统计的数据分类算法 存在的一些问题，针对各类方法在分类准确率方面的不足，结合数据挖掘技术 提出了新的基于规则的数据分类方法。该方法结合统计分类方法，通过定制面 向铁路信息系统的行业分类规则，设计出基于专家规则的d c s 分类器，并构 建出具有高准确性的分类模型。最后，进一步将本研究所提出的分类策略应用 于铁路运输管理信息相关数据实际分类中，并进行了实际性能测试。 此外，本文还对于基于统计的各类分类方法所得到的结果进行了比较分 析，对所构造的分类器的泛化能力及导致分类性能差异的本质原因进行了深入 探讨，给出了保证预测模型准确性的最佳策略，从而为铁路运输信息预测提供 了关键技术支持及全面解决方案。 第2 章数据挖掘中分类算法的研究与分析 2 1 引言 在绪论中本文对数据挖掘以及数据分类现状做了简要介绍，并就本课题的 具体研究方向和研究内容进行了概括。而本章的主要内容是对数据挖掘中基于 统计的分类法的研究与探讨。 本章将着重介绍两种目前比较成熟的基于统计的分类方法，朴素贝叶斯和 支持向量机，并就他们分类结果进行分析，也就是分类准确度。从而研究基于 统计的分类算法问题与不足。为我们接下去的研究工作进行准备。 2 2 数据分类的数学描述 设s 是j 个数据样本的集合。假定类标号属性具有m 个不同值，定义m 个不同类c ，0 = 1 ，圳。假设毋是类g 中的样本数。对一个给定的样本分 类所需的期望信息由下式给出： i ( s i ，s 2 ，一，) = 一主1 0 92 ( p f ) ( 2 1 ) i = 1 其中，a 是人一样本属于c i 的概率，并用s s 估计。注意，对数函数以2 为底，因为信息用二进位编码。 设属性a 具有v 个不同值( 口l ，口：，口，) 。可以用属性a 将s 划分为v 个子 集 s 。，s ：，s ，) ；其中s j 包含s 中这样的一些样本，它们在a 上a n n a ，。 如果a 选作测试属性( 即最好的分列属性) ，则这些子集对应于由包含集合s 的节点省长出来的分枝。设。口是子集s ，中类c ，的样本数。根据由a 划分成子 集的熵( e n t r o p y ) 或期望信息由下式给出： e ( 爿) = 士” 1 + s ”vr ， l s ， j 。 项鱼二专二蔓充当第，个子集的权，并且等于子集( 即爿值为口，) 中的 样本个数除以s 中的样本总数。熵值越小，子集划分的纯度越高。注意，对于 给定的子集西， 地j 2 j ) = 一p fl 0 9 2 ( n ) ( 2 3 ) 其中，p 。= 晶是与中样本属于类c 的概率。 6 j 在a 上分枝将获得的编码信息是 g a m ( a ) = i ( s l ，s 2 ，s 。) 一e ( a )( 2 - 4 ) 换言之，g 口加妙是由于知道属性a 的值而导致熵的期望压缩。 算法计算每个属性的信息增益。具有最高信息增益的属性选择给定集合s 的测试属性。创建一个节点，并以该属性标记，对属性的每个值创建分枝，并 据此划分样本。 2 3 基于统计的数据分类算法研究 2 3 1 朴素贝叶斯分类 通常来说有5 种贝叶斯分类器：朴素树，扩张朴素树，贝叶斯扩张朴素 树，贝叶斯多树及通用贝叶斯网。 幽2 1 朴素信度网结构 f i g u r e2 1 n a y v eb e l i e fn e t w o r ks t r u c t u r e 图2 1 就是朴素信度网结构图，它的结构简单，仅有一个父结点，再没有 哈尔滨理工大学工学硕士学位论文 其它的连接。虽然它的结构简单，它的分类效果并不差。与其它的分类器相比 有以下优点。首先它的构造很简单。只要给出一个父结点就可以了，并不要通 过学习来得到结构。其次分类过程是非常高效的。不过这两个特点是在假设所 有的特征之间是条件独立的情况下得出来的。虽然是这样，如果在特征之间不 是非常相关的条件下朴素信度网分类器比其它许多复杂的分类器的效果好【3 2 】。 扩展朴素信度网分类器通过允许属性值之间形成树结构来扩展朴素信度网 中各个特征之间的完全独立性。在图2 2 中x 1 ，x 2 ，x 3 ，x 4 形成了一个 树，这种结构的信度网可以通过c h o w - l i u 算法 3 3 i 。 图2 - 2 扩展信度网 f i g u r e2 - 2e x t e n d e db e l i e f n e t w o r k 贝叶斯扩展朴素信度网分类器通过允许属性值之间可以形成任何图形结 构，已不再仅仅是树结构。但是这种结构学习起来很费时，可以采用最d , 钡j j 度 方法，和c l 算法 3 4 j 。 蚓2 - 3 贝1 1 - 1 + 斯扩展朴素信度网 f i g u r e2 - 3b a y e s i a ne x t e n d e dn a f v eb e l i e f n e t w o r k 贝叶斯多网分类器将类别属性取不同值时分别对应一个网络。( 见图2 4 ) 贝叶斯多网可以看作是一个一般化的贝叶斯扩展朴素信度网。不论类别取什么 值，贝叶斯扩展信度网都保持属陛之间的关系不变，而贝叶斯多网在类别l ：j c 小 哈尔滨理工大学工学硕士学位论文 同值时，可以改变属性之间的关系。既然每一个局部网络与一个类别值相连， 在某种意义上类节点可以看作是所有特征的父结点【3 5 】。与朴素信度网、扩展朴 素信度网、贝叶斯扩展朴素信度网相比，贝叶斯多网是较普遍的形式，它给属 性之间更大的自由空间。因此它是一种无限制的贝叶斯分类器。并且它并不一 定比贝叶斯扩展朴素信度网复杂。因为按类取值分解时，局部网络要比类值不 分解时要简单。在类值不分解时，局部网要表达所有的关系。 c = e 。 c 。g 图2 4 简单的贝计斯多网 f i g u r e2 - 4s i m p l eb a y e s i a nm u l t i - n e t w o r k s 通用信度网是另一种非限制性的信度网分类工具。朴素信度网、扩展朴素 信度网、贝叶斯扩展朴素信度网、贝时斯多网的共同特点是类结点被看作是 所有属性节点的父结点。而通用信度网将类节点看作是一个普通的节点1 3 6 j 口”。 通用信度网是认为在数据集下存在一个联合概率密度分布，而贝叶斯多网认为 在一个数据集下存在多个联合概率密度分布。采用哪一种分类器取决于实际的 数据情况。我们可以看到非限制信度网分类器要好于限制性的信度网。 图2 。5 通用信度网 f i g u r e2 - 5g e n e r a lb e l i e f n e t w o r k 学习非限制性的信度网可以采用三阶段学习法来学习贝叶斯多网和通用信 度网的结构。 1 起草应用c h o w l i u 定理学习 2 ，添边向图中加入边 哈尔滨理工大学工学硕士学位论文 3 确认对图中的边重新进行确认 只要训练样本集足够大，我们就可以得出一个满意的信度网结构。下面是 通用信度网的学习流程： 1 输入训练集 2 利用c l 定理学习结构 3 得到马尔科夫子集 4 删除在马尔科夫子集以外的节点 5 学习参数输出通用信度网的结构图 如果我们有大量的样本数据后，经过训练我们可以得到马尔科夫子集，可 以帮助我们看清楚那些特征对我们诊病有帮助，这样可以帮助图像特征提取， 确定那个特征重要，忽略一些无关紧要的特征。 下面是贝叶斯多网的学习流程： 1 输入训练集 2 按照类节点的取值将训练集分为几个子集 3 对于每一个训练子集调用c l 算法 4 学习每个局部网络的参数 5 输出每个局部网络结构和类节点的类节点的概率分布 在学习这两种类型的信度网的时候，因为它的结构没有限制，所以会出现 学习后的结构过分的适应了输入的训练集，而失去了一般性。这就是一种过适 应现象。这就是学习后的结构不能对训l 练集以外的数据产生很好的分类效果。 23 2 支持向量机分类 我们先来研究什么是最优化分类超平面，通常用一个实值函数 厂：吖斗锨来表示这样的操作：如果厂( ；) 0 时，输入向量 r = ( x ，z ：，z 。) 。就归入正类，否则归入负类。考虑厂( x ) ，x 是线性函数的 情况，函数可以写成为： ，( ；) = p ；+ 6 = 窆w + 6 ( 2 - 5 ) j = l 这里( 品，6 ) 9 i ”贸是控制函数的参数，决策规则由厂( ；) 的符号决定，即 哈尔滨理工大学工学硕士学位论文 s i g n ( f ( x ) ) 给，我们规定s 谚z ( o ) = 1 我们的学习方法意味着一定要从数据中 定义函数间隔：n = y ，( 乍刁+ 6 ) 。几何间隔：归一化线性函数 喃谚一矧了脚糯，谶耵输入蜘啪艇恢触肭眠 数。如果一w 是权重向量，要在正点x + 和负点z 一上实现函数间隔为1 ，可以计算 ( 茹i ) + 6 = + 1 ( 2 - 6 ) ( ；z ) + b - - 1 ( 2 - - 7 ) 为计算几何间隔，必须归一化；。 一 镢t i ) _ 铺z ) _ 瘕眵( 品砂阿1 c z 叫 因此，几何间隔将成为1 州品| | 。得出如下的叙述：给定一个线性可分训练 ，i i 2 样本：s ：嘛幽j e ，_ ) ，：j ，e ，y f ) ) ，求解优化问题： m i n t 。( w 功( 2 - - 9 ) “”；i ) + 6 ) ， ( 2 - 1 0 ) 哈尔滨理工大学工学硕士学位论文 面。 可以得到超平面每，6 ) ，它实现了几何问隔为y = 1 i i 叫f ：的最大间隔超平 原始的拉格朗日函数为： 三( _ ，。，苫) = 土2 ( ；功一喜嚷l ；i ) + 6 ) 一z 】 ( 2 一- - ) 这里口，0 是拉格朗日乘子。上式的对偶式子为： 警响= 警悟咖夏) c z 吨， 通过对相应的；和6 求偏导数，可以得到： 驾捌：oj 品：壹鹏，一x i ( 2 1 3 ) d 1 l = l 旦蚓：o j 圭y 。口，：o( 2 1 4 ) o b 智“。 、 。 带入到原始拉格朗日函数，得到 三矗6 ，磊) = 三2 ( 磊功一喜q p ，；i ) + a ) 一， = 丢毫y 以q 口，仁i ) 一i 圭, j = l y 乃q 仁i ) + 喜( 2 - - 1 5 ， = 酗t i i 善ty i y i g i 口j ( x u i ) b 的值没有出现在对偶问题中，利用原始约束一定可以找到b ： 。：一竺竺! ：l ( 1 三：三2 2 ：2 1 ：! ：! ( 三：三2 2 。：一。， k a r u s h k u h n t u c k e r 互补条件提供了关于解结构的有用信息。条件要求最优解 口+ ，( w + ，6 ) 必须满足： 哈尔滨理工大学工学硕士学位论文 口： y ，“i ：乏) + 。) 一 = 。，= - ，z ，z ( 2 - - 1 7 ， 这意味着仅仅是函数间隔为1 的输入点x ，也就是最靠近超平面的点所对应的 口? 非零，所有其它点对应的参数口? 为零。因此在权重向量的表达式中，只有 这些点包括在内，我们称之为支持向量f 3 8 “。 到目前为止，我们讨论的都是数据集线性可分的情况，然而，这种情况比 较少。有两种方法来泛化问题，都是依赖于问题的先验知识和数据噪声的估 计。一种情况是期望超平面能够正确的分离数据，另一种是引进附加代价函 数，这个代价函数和错误分类相关。为了使最优化分类超平面方法泛化， c o r t e s 提出了非负变量毒0 和损失函数。 f c = 第 盯 d ( 2 1 8 ) i = 1 其中 是错误分类的度量。现在优化问题变成了最小错误率问题。对于线 性不可分的情况，限制条件为： l f i 一、 i y ，l p z ，j + 6 l 1 一直 f = 1 ，2 ，- 一，( 2 1 9 ) 专0 。最优化分类超平面由向量刁决定，最小化下面的函数 中= 捌2 + c 喜喜( 2 - - 2 0 ， c 是任意给定的一个值。解上面的条件优化问题，其拉格朗日函数为： l ( _ 6 ，手，苫，万) = 圭每品) + c 善参一喜q 侈，陆石) + 。卜+ 毒 一喜卢尚( 2 - - 2 1 ) 口，尼是拉格朗日乘子。关于wb 善，使拉格朗日函数l 最小，关于口，屈，使 拉格朗日函数最大。其对偶问题为： n 咿3 _ a x = 鼍茅 臻0 ( 2 - - 2 2 ， 求导数，得： 哈尔滨理工大学工学硕士学位论文 叠圃o b ：o 等圭邝。：o ( 2 - 2 3 ) 智“。 、 蓝錾到：oj ；壹q 功， ( 2 叫) u w i - 1 蓝霉劐：oj 屈：c ( 2 - 2 5 ) 彪 将上面几个式子带入对偶问题中，得： t 警矿o ) = n 一圭喜妻q 屈弘乃e i ) + 孝( 2 - - 2 6 ) 因此，问题得解可以由下面得式子给出： 云= a r s 哩n 吉妻喜雹岛儿y ，e i ) 一喜( 2 - - 2 7 ， 被下面得式子限制： 0 口。c ，i = 1 , 2 ，- t ，( 2 - 2 8 ) 口，咒= 0 ( 2 2 9 ) 2 33 分类法准确率评估 评估分类法的准确度是很重要的，这使得我们可以评估一个分类法对未来 数据即( 未经分类法处理的数据) 的正确标号的准确率。 由于学习算法( 或模型) 对数据的过分特化，使用训练数据导出分类法， 然后评估分类法，然后评估分类法，可能错误地导致过于乐观的估计。保持和 k 一折交叉确认是两种基于给定数据随机选样划分的、常用的评估分类法准确率 的技术。 在保持方法中，给定数据随机地划分成两个独立的集合：训练集和测试 集。通常，三分之二的数据分配到训练集，其余三分之一分配到测试集。使用 训练集导出分类法，其准确率用测试及评估。评估是保守的，因为只有一部分 初始数据用于导出的分类法。随即予选样是保持方法的一种变形，他将保持方 法重复k 次。总体准确率估计取每次迭代准确率的平均值。 在k 一折交叉确认( k f o l dc r o s s - v a l i d a t i o n ) 中，初始数据被划分成k 个互不 相交的自己或“折”s ，最，瓯，每个折的大小大致相等。训练和测试