（计算机应用技术专业论文）数据挖掘技术在处理交通流数据中的研究及应用.pdf

摘要 数据挖掘是信息领域发展最快的技术，很多不同领域的专家，比如统计学家、数 据库专家等，都从中获得了发展的空间，使得数据挖掘只益成为讨论的热门话题。数 据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其 中的、人们事先不知道的、但又有用的信息和知识的过程。是一个多学科交叉的 研究领域，它融合了数据库技术、人工智能、机器学习、统计学、知识工程、面向对 象方法、信息检索、高性能计算以及数据可视化等最新技术的研究成果，经过了十几 年的研究，产生了许多新概念和新方法。 数据挖掘的算法很多，例如分类算法、聚类算法、时间序列算法、关联规则算法 等等，本文主要研究的是聚类算法和时间序列算法。分别介绍了聚类算法和时间序列 算法中一些典型算法的原理以及应用方法。 在智能交通方面，交通流数据的分析在是非常重要的，如何智能的分析交通数据 一直以来是一个比较困难的问题，本文的核心内容有三部分，首先对数据进行必要的 预处理，使之能够成为被数据挖掘算法直接使用的数据形式；其次利用k - m e a n s 算法 对收费站进行了聚类，并用s p s sc l i m e n t i n e l l 1 聚类算法对聚类结果进行了验证； 最后利用m i c r o s o f t 时间序列算法对交通流数据进行了预测，实验表明预测的准确率 达到了8 0 以上。另外，在论文的最后对数据挖掘在交通方面的应用做出了总结及展 望。 关键词：交通流数据，数据挖掘，聚类，时间序列，预测 a b s t r a c t d a t am i n i n gi sap r o c e s st h a tc a l ld e r i v ei n f o r m a t i o nf r o ma b u n d a n td a t aw h i c hi s d i s i n t e g r a t e d ，d i s t u r b e d ，f u z z ya n dr a n d o m t h ei n f o r m a t i o na l w a y si sp o t e n t i a l l y u s e f u lb u t u n k n o w n e df o ru s i ti sa ni n t e r d i s c i p l i n a r yr e a c h i n gf i e l d ，w h i c hi n v o l v e dd a t a b a s e t e c h n i q u e ，a i ，m a c h i n el e a m i n g ，s t a t i s t i c s ，k n o w l e d g ee n g i n e e r i n g ，o p pm e t h o d ， i n f o r m a t i o ns e a r c h i n g ，h i g hp e r f o r m a n c ec o m p u t i n g ，d a t av i s u a l i z a t i o na n ds oo n t h i s s u b j e c tc r e a t e sm a n yn e wc o n c e p t sa n dm e t h o d si nr e c e n td o z e n so fy e a r s d a t am i n i n ga r i t h m e t i ci n c l u d e ss o r t i n ga l g o r i t h m ，c l u s t e r i n ga l g o r i t h m ，a r i t h m e t i c b a s e do nt h eo r d e ro ft i m e ，a s s o c i a t i o nr u l em i n i n ga l g o r i t h ma n ds oo n t h i sp a p e rm a i n l y f o c u s e so nc l u s t e r i n ga l g o r i t h ma n da r i t h m e t i cb a s e do nt h eo r d e ro ft i m e i ts y s t e m i c a l l y e x p l a i n st h ec l a s s i ct h e o r ya n da p p l i c a t i o nm e t h o d so ft h et w oa r i t h m e t i cm e n t i o n e da b o v e t r a f f i cf l o wd a t ai sv e r yi m p o r t a n ta tt h ef i e l do fi t s ( i n t e l l i g e n tt r a n s p o r t a t i o n s y s t e m s ) i ti sa l w a y sd i f f i c u l tt od e a lw i t ht r a f f i cd a t ai n t e l l i g e n t l y c o r ec o n t e n to ft h i s p a p e ri sc o m p o s e dw i t ht h r e ep a r t s a tf i r s t ，i ti sn e c e s s a r yt od i s p o s eo fd a t ai no r d e rt o m a s ki tw o r k a b l ef o rd a t am i n i n ga r i t h m e t i c t h e ni tm a k e su s eo fk m e a n sa r i t h m e t i ct o a s s o r tt h ef e es t a t i o n sa n dv e r i f i e st h er e s u l tb ys p s sc l i m e n t i n e11 1 c l u s t e r i n ga l g o r i t h m f i n a l l y , m i c r o s o f ta l g o r i t h mb a s e do nt h eo r d e ro ft i m ei st a k e nt of o r e c a s tt r a f f i cf l o wd a t a t h ee x p e r i e n c ep r o v e st h a ta c c u r a c yr a t eo ff o r e c a s t i n go v e r r u n s8 0 k e yw o r d s ：t r a f f i cd a t a ，d a t am i n i n g ，c l u s t e r i n ga l g o r i t h m ，a l g o r i t h mb a s e do nt h e o r d e ro ft i m e ，f o r e c a s t i i 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研究 工作所取得的成果。除论文中已经注明引用的内容外，对论文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任 何未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：弓薛磊 卅年卵锄 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等权 利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文或成 果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：袖 1 年 导师一彦永珲 媚瑰日 年r 只2 8 日 长安人学硕士毕业论文 1 1 研究背景及意义 第一章绪论弟一早三百t 匕 随着计算机、网络技术的发展，获得数据资料已经变得轻而易举，但是对于数量 大、涉及面宽的数据，所以依靠以往那种由简单汇总、按指定模式去分析的统计方法 是无法完成这类数据的分析。因此，一种智能化的、综合应用各种统计分析、数据库、 智能语言来分析庞大数据资料的技术就应运而生，这就是目前国际上统计最热门的话 题“数据挖掘 ( d a t am i n i n g ) 技术的市场需求和它的技术支持背景【l 】。数据挖掘的应 用领域非常广，交通自然也是其中的一个应用领域，近年来，随着我国经济建设持续 不断的高速发展和城市现代化进程的加快，高速公路建设和隧道建设取得了长足的发 展，此外，交通系统中也存在着大量的交通流数据，这就为数据挖掘技术在高速公路 及隧道交通领域中的发展提供了广泛的数据支持，不过与此同时交通数据的实时性和 复杂性也对数据挖掘技术的发展提出了严峻的挑战【2 l 。 随着我国智能交通系统概念的日益普及和应用的迅速发展，交通数据采集以及交 通事故检测已经成为智能交通系统的最要部分，因此得到了优先的发展。基础交通信 息和交通事故主要包括了车流量、车速、车间距、车辆类型、道路占有率、车辆违章 信息、交通事故检测等信息。采集交通流数据信息和交通事故检测一般采用感应线圈 来检测。 用新的数据挖掘技术来代替传统的数据分析和解释方法是非常有必要和有意义 的，针对交通信息、交通系统的不确定性，在传统的基于数据库、知识库和模型库的 决策支持系统的基础上，采用数据仓库、联机分析、数据挖掘以及专家系统的有关理 论和技术，构建新一代的数据分析系统，应用数据挖掘的方法( 分类算法、聚类算法、 决策树算法、时间序列算法、神经网络算法等) ，研究建立适合交通信息挖掘的具体 模型，来处理交通数据流信剧3 1 。数据流信息包括了各种传感器( c o v i 检测器、光 强检测器、车辆线圈检测器、风速风向检测器等) 动态采集到的信息，其中交通流量 又包括了车速、车流量、车道占有率等数据。但是在以前这些海量的数据并未得到有 效的组织和利用，进行深层次的加工处理，其中潜在的交通流量变化规律，以及各个 检测器数据之间的相互关系往往被忽略，或者没有被重视，这就造成了数据资源的浪 费，为了要更有效地处理海量的交通数据资源，从中得到有用的信息，就要选择一种 1 第一章绪论 有效的知识发现方法，数据挖掘就是一种很好的知识发现的方法，数据挖掘为我们提 供了一种发现知识、规律和信息的有效技术，通过这项技术，我们可以发现信息模式 及未来数据的发展趋势，为相关部门做出科学的决策提供理论基础。 目前，随着数据挖掘技术在各个领域的不断发展，人类发现知识的方式正在不断 的改变。目前交通流数据量非常巨大，大量的数据被认为是“数据丰富，但是信息贫 乏 ，快速增长的海量交通数据一般都存在于数据库中，那么怎样从这些海量数据中 通过数据挖掘得到有用的信息，怎么找到这些数据之间的内在联系就成了非常重要且 必要的问题，而数据挖掘技术在交通中的应用研究，也必将促进未来高速公路的发展。 所以研究数据挖掘技术在处理交通流数据中的应用是非常有意义的一项工作，随着数 据挖掘技术的不断发展，将数据挖掘技术科学合理的应用到交通领域必将能够科学、 高效的服务于交通。 1 2 国内外发展现状 1 2 1 数据挖掘技术发展 近十几年，随着科学技术不断的飞速发展，经济和社会都取得了极大的进步，与 此同时，在各个领域也相应的产生了大量的数据，如人类对太空的探索，以及银行每 天的巨额交易数据等。显然在这些数据中包含着大量丰富的信息，如何处理这些数据 得到有用的信息，人们对此进行了有益的探索。计算机技术的迅速发展使得处理数据 变为了，这就推动了数据库技术的极大发展，但是面对不断增加的海量的数据，人们 不再仅仅满足于数据库的查询功能，而进一步提出了更深层次问题，即能不能从数据 中提取信息或者知识，使之能为决策服务。就数据库技术而言已经显得无能为力了， 同样，传统的统计技术也面临了巨大的挑战。这就急需有新的方法来处理这些海量般 的数据。于是，人们结合统计学、数据库、机器学习等技术，提出用数据挖掘来解决 这一难题【4 1 。 数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能对过去的数据进行查 询和遍历，并且能够找出过去数据之间的潜在联系，从而促进信息的传递。数据挖掘 技术的三项基本技术现在已经基本发展成熟，即：海量数据搜集、强大的多处理器计 算机和数据挖掘算法。 数据挖掘是一个多学科交叉的研究领域，它融合了数据库技术、人工智能、机器 学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可视化等 2 长安大学硕士毕业论文 等最新技术的研究成果，经过了十几年的研究，产生了许多新概念和新方法。推动数 据挖掘技术的技术主要有三个：数据库、数据仓库和i n t e m e t 信息技术的发展，计算 机性能的提高和先进的体系结构的发展和统计学和人工智能等方法在数据分析中的研 究和应用。数据挖掘的发展前景非常好，它被誉为影响未来的十大关键技术之一，而 现在国内外的数据挖掘技术的发展主要围绕着以下几个问题展开【5 】： 1 数据挖掘技术与特定商业逻辑的平滑集成问题； 2 数据挖掘技术与特定数据存储类型的适应问题； 3 大型数据的选择与规范化问题； 4 数据挖掘系统的架构与交互式挖掘技术的发展； 5 数据挖掘语言与系统的可视化问题； 6 数据挖掘理论与算法的研究； 现在的数据挖掘技术主要应用在分类、聚类和预测上，即把已有的数据通过分类 或者聚类等一些数据挖掘的方法生成规则，之后用这些规则来预测数据的发展，得出 有用的知识。 数据挖掘的主要功能有分类、聚类、关联规则和序列模式发现、预测和偏差检测 等等，数据挖掘的功能十分强大，尽管数据挖掘功能强大，但是也面临着许多的问题， 这也为数据挖掘的未来的发展提供了更大的空间。 综上所述，数据挖掘只是一个工具，不是万能的，它可以发现一些潜在的用户； 但是不会告诉用户其原因，也不能保证这些潜在的用户会成为现实。数据挖掘的成功 要求对期望解决问题的领域有深刻的了解，理解数据，并且了解其过程，才能对数据 挖掘的结果找出合理的解释 9 , 1 0 】。 数据挖掘算法中的时间序列算法是数据挖掘非常重要的一个分支，常常被用来预 测交通流数据。时间序列数据挖掘是时态数据挖掘的一种，与时态数据挖掘的其他种 类挖掘不同，它所处理的数据是具有时间维的实数数据。时间序列挖掘是数据挖掘在 时间序列分析中一种典型运用。 时间序列是一种常见而重要的数据类型，在海量的时间序列中发现其背后隐藏的 知识对分析时间序列变化规律，科学地做出决策具有重要的意义。因此在数据挖掘概 念提出不久，就有不少研究人员把数据挖掘的思想运用至时间序列分析中来。序列模 式挖掘是序列挖掘中最为重要的部分之一，序列模式挖掘最早是由r a g r a w a l 等提出 的，并同时提出了其a p r i o r i a l l 和a p r i o r i s o m e 算法【】之后关于序列模式的挖掘只要 3 第一章绪论 有a p r i o r i a l l 、g s p 1 2 1 、p s p 13 1 、f p a m 等。其中影响最大的是a p r i o r i a n 和g s p 算法， 具体方法见第五章。 1 2 2 数据挖掘技术在交通方面的发展 数据挖掘在交通方面的应用主要是处理及预测交通流数据，通过对数据进行分析 得出数据的发展趋势，预测交通流的发展，利用预测的结论来指导交通。此外还可以 通过研究不同影响交通流数据相应关系的因素之间的联系，推测出各个因素对交通流 的影响程度，并利用这些研究成果科学地指导交通，为交通服务。 国内外关于交通流动态预测理论的研究目前还处于发展阶段，还没有较成熟的预 测理论。建立该模型的关键是对于具有相似历史趋势的工作日的分类。假如实时交通 数据没有集成或检测器数据不可靠，历史趋势模型可能是唯一的选择。虽然历史趋势 模型可以在一定程度内解决不同时间、不同时段里的交通流变化问题，但静态的预测 往往是不科学的，因为它不能解决突发的交通状况，如交通事故等等。 数据挖掘在许多城市的智能交通系统中得到了广泛的应用，现在使用数据挖掘技 术对车流量数据进行分析，已经较为普遍，所以数据挖掘技术在交通中的应用具有非 常好的前景。 1 3 本文研究内容及结构 本文主要研究数据挖掘算法在处理交通流数据方面的应用，其中包括了聚类算法 是如何应用到收费站车流量数据中来解决收费站分类的问题，以及聚类算法和时间序 列算法是如何应用到2 0 0 8 年上半年的收费站车流量数据中来解决车流量预测的问题。 本文第一章介绍了数据挖掘的背景、意义以及国内外发展的现状，并且简要地叙 述了数据挖掘技术在交通方面的发展。 第二章讨论了数据挖掘技术的任务、对象、流程及发展。 第三章主要介绍了数据挖掘之前数据预处理的理论及应用。 第四章详细介绍了数据挖掘聚类算法的原理，并利用聚类算法解决收费站的分类 问题。 第五章详细介绍了本文重点应用的数据挖掘算法时间序列算法的原理。 第六章详细介绍了时间序列算法在处理交通流数据中的研究及应用。 4 长安大学硕士毕业论文 2 1 数据挖掘概述 第二章数据挖掘技术 数据挖掘( d a t am i n i n g ) 是从大量的、不完全的、有噪声的、模糊的、随机的数据中 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。随着 信息技术的高速发展，人们积累的数据量急剧增长，动辄以t b 计，如何从海量的数 据中提取有用的知识成为当务之急。数据挖掘就是为顺应这种需要应运而生发展起来 的数据处理技术，是知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 的关键步骤。 数据挖掘技术是信息领域发展最快的技术，很多不同领域的专家，比如统计学家、 数据库专家等，都从中获得了发展的空间，使得数据挖掘日益成为企业界讨论的热门 话题。随着信息技术的发展，人们采集数据的手段日益丰富与高明，由此累积的数据 日益膨胀，数据达到了g b 甚至t b 级，而且高维数据也日益成为主流，这些海量数 据及其高维特征使得传统的数据分析手段相形见拙。计算机的性能日益更新，使人们 能够期望计算机帮助我们分析与理解数据，帮助我们以丰富的数据为基础做出正确的 决策，于是数据挖掘这一融合了多种分析手段，从大量数据中发现有用知识的方法就 应运而生，并在使用中得以蓬勃发展。 2 1 1 数据挖掘的任务 数据挖掘的任务主要是关联分析、聚类分析、分类、预测、时序模式和偏差分析 等。 1 关联分析 关联规则挖掘是由r a k e s ha p w a l 等人首先提出的。两个或两个以上变量的取值之 间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、可被发现 的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是找出数据库中 隐藏的关联网。一般用支持度和可信度两个阈值来度量关联规则的相关性，还不断引 入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。图2 1 就是购物篮关联分 析图，从图中可以看出各个食品的关联关系，以及它们之间关系的强弱。 5 第二章数据挖掘技术 圈2 1 购物篮关联分析圈 2 聚类分析 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同的类 中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可能的数 据属性之自j 的相互关系。图2 2 表现出了聚类的效果。 图22 寨娄 3 分类 分类就是找出一个类别的概念描述它代表了这类数据的整体信息，叩该类 6 长安人学硕七毕业论文 的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是利用 训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预测。 4 预测 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种类及 特征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。 5 时序模式 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一样，它 也是用己知的数据预测未来的数据，但这些数据的区别仅仅是变量所处时间的不同。 6 偏差分析 在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数据库 中数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结果与参照 之间的差别。 2 1 2 数据挖掘的对象 根据信息存储格式，用于挖掘的对象有关系数据库、面向对象数据库、数据仓库、 文本数据源、多媒体数据库、空间数据库、时态数据库、异质数据库以及m t e m e t 等。 2 1 3 数据挖掘流程 1 定义问题t 清晰地定义出业务问题，确定数据挖掘的目的。 2 数据准备：数据准备包括：选择数据，在大型数据库和数据仓库目标中提取数 据挖掘的目标数据集；数据预处理，进行数据再加工，包括检查数据的完整性及数据 的一致性，去噪声，填补丢失的域，删除无效数据等。 3 数据挖掘：根据数据功能的类型和和数据的特点选择相应的算法，在净化和转 换过的数据集上进行数据挖掘。 4 结果分析：对数据挖掘的结果进行解释和评价，转换成为能够最终被用户理解 的知识。 5 知识的运用：将分析所得到的知识集成到业务信息系统的组织结构中去。 2 1 4 数据挖掘的方法 1 神经网络方法 神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和高度 容错等特性，非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关注。 7 第二章数据挖掘技术 2 遗传算法 遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生全局 优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖 掘中被加以应用。 3 决策树方法 决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从中找到 一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别适合大规 模的数据处理。最有影响和最早的决策树方法是由q u i n l a n 提出的著名的基于信息熵 的i d 3 算法。 4 粗糙集方法 粗糙集理论是一种研究不精确、不确定知识的数学工具。粗糙集方法有几个优点： 不需要给出额外信息：简化输入信息的表达空间；算法简单，易于操作。粗糙集处理 的对象是类似二维关系表的信息表。 5 覆盖正例排斥反例方法 它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任 选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去，相反则 保留。按此思想循环所有正例种子，将得到正例的规则( 选择子的合取式) 。比较典 型的算法有m i c h a ls k i 的a q l1 方法、洪家荣改进的a q l 5 方法以及他的a e 5 方法。 6 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性关系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析可以采 用统计学方法，即利用统计学原理对数据库中的信息进行分析。 6 模糊集方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚 类分析。系统的复杂性越高，模糊性越强，一般模糊集合理论是用隶属度来刻画模糊 事物的亦此亦彼性的。 2 2 数据预处理 当今现实世界中的数据库极易受噪声数据、不一致数据等问题的干扰，因为数据 库太大，常常多达数千兆，甚至更多。所以如何预处理数据，提高数据的质量，从而 8 长安大学硕十毕业论文 提高数据挖掘的结果就显得尤为重要了。 数据预处理技术有很多，数据清洗可以去掉数据中的噪音，纠正不一致。数据集 成将数据由多个源合并成一致的数据存储，如数据仓库或数据立方体。数据变换( 如 规范化) 也可以使用。例如规范化可以改进涉及距离度量的数据挖掘算法的精度和有 效性。数据规约可以通过聚集、删除冗余特征或聚类等方法来压缩数据。这些数据处 理技术在数据挖掘之前使用，可以大大提高数据挖掘模式的质量，降低实际挖掘所需 要的时间。 数据挖掘的一般方法包括：数据清理、数据集成、数据归约和数据离散化。 2 2 1 数据预处理的必要性 存在不完整、含噪音的和不一致的数据是大型、现实世界数据库或数据仓库的共 同特点。不完整数据的出现可能有多种原因。有些感兴趣的属性，如销售事务数据中 的顾客的信息，并非总是可用的。其他数据没有包含在内，可能只是因为输入时认为 是不重要的。相关数据没有记录是由于理解错误，或者因为设备故障，此外，记录历 史或修改的数据可能被忽略。与其他数据不一致的数据可以删除。遗漏的数据，特别 是某些属性上缺少值的元组可能需要推导出来。 数据含噪音( 具有不正确的属性值) 可能有多重原因。收集数据的设备可能出故 障；人的或计算机的错误可能在数据输入时出现；数据传输中的错误也可能出现。这 些可能是由于技术的限制，如用于数据传输同步缓冲区大小的限制。不正确的数据也 可能是由命名或所用的数据代码不一致而导致的。重复元组也需要数据清理。 2 2 2 数据挖掘预处理的主要任务 数据预处理的主要任到1 4 】如下： 1 数据清洗 数据清洗从名字上也看的出就是把“脏”的“洗掉。因为数据仓库中的数据是 面向某一主题的数据的集合，这些数据从多个业务系统中抽取而来，而且包含历史数 据，这样就避免不了有的数据是错误数据，有的数据相互之间存在冲突。这些错误的 或有冲突的数据显然是不想要的，这将成为“脏数据”。通过按照一定的规则把“脏 数据”洗掉，这就是数据清洗。而数据清洗的任务是过滤那些不符合要求的数据，将 过滤的结果交给决策部门，而确认是否过滤掉，则应该由决策部门修正之后再进行处 理。不符合要求的数据主要是有不完整的数据、错误的数据及重复的数据三大类。 9 第二章数据挖掘技术 对于不完整的数据，这一类数据主要是些应该有的信息缺失，解决这种问题的 方法就是要为数据填写空缺值。方法【1 4 1 主要有以下几种： ( 1 ) 忽略元组，当类标号缺少时通常这样做，除非元组有多个属性缺少值，否则该 方法不是很有效。当每个属性缺少值占的百分比很高时，它的性能非常差。 ( 2 ) 人工填写空缺值，一般来说，该方法很费时，并且当数据集很大，缺少很多值 时，该方法可能行不通。 ( 3 ) 使用一个全局变量填充空缺值，即将遗漏的属性值用同一个常数替换。 ( 4 ) 使用属性的平均值填充空缺值。 ( 5 ) 使用与给定元组属同一类的所有样本的平均值。 ( 6 ) 使用最可能的值填充空缺值，可以使用像回归、贝叶斯形式化方法或判定树这 样的基于推理的方法来确定该填充的值。 对于错误的数据，这一类错误产生的原因是业务系统不够健全，在接收输入后没 有进行判断直接写入后台数据库造成的，比如数值数据输成全角数字字符、字符串数 据后面有一个回车操作、日期格式不正确、日期越界等。这一类数据也要分类，对于 类似于全角字符、数据前后有不可见字符的问题，只能通过写s q l 语句的方式找出来， 然后要求客户在业务系统修正之后抽取。日期格式不正确的或者是日期越界的这一类 错误会导致e t l 运行失败，这一类错误需要去业务系统数据库用s q l 的方式挑出来， 交给业务主管部门要求限期修正，修正之后再抽取。对于重复的数据特别是维表中会 出现某种情况，解决的办法则是将重复数据记录的所有字段导出来，让客户确认并整 理。 解决这两种问题就是要为数据去噪，去除噪声的方法【1 4 】主要有以下几点： ( 1 ) 分箱( b i n n i n g ) ( 等深或等宽分箱) 。首先排序数据，并将他们分到等深的“箱 中，然后可以按“箱 的平均值平滑，按“箱”中值平滑，按“箱 的边界值平滑。 ( 2 ) 聚类：检测并且去除孤立点( 如下图所示) 。 ( 3 ) 计算机和人工检查结合：计算机检测可疑数据，然后对他们进行人- r 笋j j 断。 ( 4 ) 回归：通过让数据适应回归函数来平滑数据，此方法对连续的数字型数据较好。 数据清洗是一个反复的过程，不可能在几天内完成，只有不断的发现问题，解决 问题。对于是否过滤，是否修正一般要求客户确认，对于过滤掉的数据，写入e x c e l 文件或者将过滤数据写入数据表，在e t l 开发的初期可以每天向业务单位发送过滤数 据的邮件，促使他们尽快地修正错误，同时也可以作为将来验证数据的依据。数据清洗 10 长安人学硕士毕业论文 需要注意的是对于每个过滤规则认真进行验证，不要将有用的数据过滤掉并要用户确 认。 2 数据集成 数据集成就是将多个数据源中的数据整合到一个一致的存储单位中存储。模式集 成是整合不同数据源中的元数据，实体识别问题：匹配来自不同数据源的现实世界中 相同的实体( 人工干预或利用字段的元信息，比较字段的描述性元信息，并比较它们 是否相同) 。检测并解决数据值的冲突：对现实世界中的同一实体，来自不同数据源 的属性值可能是不同的( 因为不同的数据表示或不同的度量) ，集成多个数据库时出 现冗余数据的主要原因是同一属性在不同的数据库中会有不同的字段名，以及一个属 性可以由另外一个表导出。有些冗余可以被相关分析检测到，检测各个属性之间的相 关性的方法可以事先根据其元数据或相关性分析对数据进行预处理，就能够减少或避 免结果数据中的冗余与不一致性，提高数据挖掘的质量。 数据集成的主要问题有三点【1 4 】： ( 1 ) 实体识别问题。例如，数据分析者或计算机如何才能确信一个数据库中的 c u s t o m e ri d 和另一个数据库中的o u s t n u m b e r 指的是一个实体，通常数据库和数据仓 库有元数据( 关于数据的数据) 。这种元数据可以帮助避免模式集成中的错误。 ( 2 ) 冗余问题。一个属性是冗余的，如果它能由另一个表“导出 ；如年薪。属性 或维命名的不一致也可能导致数据集中的冗余。 3 ) 数据值冲突的检测与处理。例如对于现实世界的同一实体，来自不同的数据源 属性值的可能不同。这可能是因为表示、比例或编码不同。仔细地将多个数据源中的 数据集成起来，能够减少或避免结果数据集中数据的冗余和不一致性。有助于提高其 后的精度和速度。 3 数据变换 数据变换将数据转换成适合于挖掘的形式。数据变换包括了以下内容【”】： ( 1 ) 平滑：去除数据中的噪声。 ( 2 ) 聚集：数据汇总，数据立方体的构建，数据立方体的计算物化( 一个数据立 方体在方体的最底层叫基本方体，基本方体就是已知存在的数据，对现有的数据按照 不同维度进行汇总就可以得到不同层次的方体，所有的方体联合起来叫做一个方体的 格，也叫数据立方体。数据立方体中所涉及到的计算就是汇总) 。 ( 3 ) 数据概化：沿概念分层向上汇总，数据立方体的不同的维之间可能存在着一个 1 】 第二章数据挖掘技术 概念分层的关系。 ( 4 ) 规范化：将数据按比例缩放，使这些数据落入到一个较小的特定的区间之内。 泛化的方法有：最小最大规范化、z s c o r e 规范化、小数定标规范化以及属性的构造， 即通过现有属性构造新的属性，并添加到属性集中。 4 数据归约 数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近地保持原数 据的完整性，这样，在归约后的数据集上挖掘将变得更有效，并产生相同( 或几乎相 同) 的分析结果。数据归约的主要策略有： ( 1 ) 数据方聚集：聚集操作用于数据方中的数据。 ( 2 ) 堆归约：可以检测并删除不相关、弱相关或冗余的属性或维。 ( 3 ) 数据压缩：使用编码机制压缩数据集。 ( 4 ) 数值压缩：用替代的、较小的数据表示替换或估计的数据，如参考模型( 只需 要存放模型参数而不是实际数据) 或非参数方法，如聚类、选样和使用直方图。 5 离散化和概念分层的产生 离散化是将连续属性的范围划分为区间，以减少所必需处理的数据的量。主要应 用于以下三类数据：名称型( 无序集合中的值) 、序数( 有序集合中的值) 和连续值 ( 实数) 。使用连续属性的范围的划分，使用某一范围的值来代替某一段的值。离散 化可以有效的规约数据( 基于判定树的分类挖掘) 。离散化是通过将属性域划分为区 间，减少给定连续属性值的个数，区间的标号可以代替实际的数据值。概念分层是通 过使用高层的概念来替代底层的属性值。数值型数据离散化的方法【1 4 1 主要有： ( 1 ) 分箱( b i n n i n g ) ：分箱技术递归的用于结果划分，可以产生概念分层。 ( 2 ) 直方图分析( h i s t o g r a m ) ：直方图分析方法递归的应用于每一部分，可以自动产 生多级概念分层。 ( 3 ) 聚类分析：将数据划分成簇，每个簇形成同一概念层上的一个节点，每个簇可 再分成多个子簇，形成子节点。 ( 4 ) 基于熵的离散化( 基于统计学的) 。 ( 5 ) 通过自然划分分段：将数值区域划分为相对一致的，易于阅读的，看上去更直 观或自然的区间。自然划分的3 4 5 规则：如果一个区间最高有效位上包含3 、6 、7 或9 个不同的值就将该区间划分为3 个等宽子区间；如果一个区间最高有效位上包含 2 、4 或8 个不同的值，就将该区间划分为4 个等宽的子区间；如果一个区间最高有效 12 长安大学硕十毕业论文 位上包含l 、5 或1 0 个不同的值，就将该区间划分为5 个等宽的子区间；再将该规则 递归的应用于每个子区间。( 对于数据集中出现的最大值和最小值的极端分布，为避 免上述方法出现的结果扭曲，可以在顶层分段时，选用一个大部分的概率空间 5 9 5 ) 。 分类数据指无序的离散数据，它有有限个值( 可能是很多个) ，分类数据的概念 分层生成方法：( 属性的序代表的是属性之间的一个包含关系，说明其在概念分层中 的层次的高低) 由用户或专家在模式级显式地说明属性的部分序。在定义数据库时就 注明属性之间的包含关系，在进行数据汇总时，直接找到该包含关系，利用此包含关 系进行数据向上汇总。通过显示数据分组说明分层结构的一部分。说明属性集，但不 说明它们的偏序，然后系统根据算法自动产生属性的序，构造有意义的概念分层。根 据实际的数据来自动的生成一个偏序的方法可以根据在给定的属性集中每个属性所包 含的不同值的个数，可以自动生成概念分层，不同值个数最多的属性将被放在概念分 层的最底层。对只说明部分属性集的情况，则可根据数据库模式中的数据语义定义对 属性的捆绑信息，来恢复相关属性。在定义数据库的同时定义一个捆绑信息，将存在 偏序关系的几个属性捆绑在一起。 概言之，现实世界的数据一般是“脏 的、不完整的和不一致的。数据预处理技 术可以改进数据的质量，从而有助于提高其后的挖掘过程的精度和性能。由于高质量 的决策必然依赖于高质量的数据，因此数据预处理是知识发现过程的重要步骤。检测 数据异常、尽早地调整数据，并归约待分析的数据，将在决策制定时得到高的回报。 2 3 本章小结 本章介绍了数据挖掘技术的任务、对象、流程和方法，并且较为详细地阐述了数 据预技术，以及数据预处理技术在数据挖掘中的重要作用，数据预处理不仅能提高算 法效率，而且能有效的提高最终模型的可理解度，数据预处理的主要任务包括数据清 理、数据集成、数据归约和数据离散化。本章简单地阐述了每个步骤的主要方法以及 作用，为之后的数据挖掘做了充分的数据准备。 1 3 第三章聚类算法 3 1 聚类算法概述 第三章聚类算法 聚类算法就是将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过 程。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相 似，与其他簇中的对象相异【1 1 。 聚类分析能作为一个独立的工具来获取数据的分布情况，观察每个簇的特点，集 中对特定的某些簇做进一步地分析，此外，聚类分析可以作为其它算法( 如特征和分 类等的预处理步骤) 的预处理算法，即在实施其他算法前先使用聚类算法来找到一些 潜在的关系( 本论文就用到了这种方法) ， 处理。获取的聚类质量直接影响分析结果， 如下： 也可以使用这些算法在所生成的簇上进行 因此数据挖掘对聚类算法性能要求基本 1 可伸缩性：在很多聚类算法中，数据对象在小数据集合上具有健壮性，而对于 包含几百万个数据对象的大规模数据库进行聚类时，又可能导致不同的偏差结果。这 就需要聚类算法具有高度的可伸缩性。 2 基于约束的聚类：在实际应用中可能需要在根据不同的约束条件进行聚类，故 既要找到满足特定的约束，又要具有良好聚类特性的数据分组是一项具有挑战性的任 务。 3 胄邑发现任意形状的聚类，使用欧几里德距离或者曼哈距离的许多聚类算法来确 定的聚类，趋向于发现具有近密度和尺寸的球状簇，但对于一个簇可能是任意开关的。 因此，提出能发现任意开关簇的算法是很重要的。 4 对输入顺序不敏感：一些聚类算法对于输入数据的顺序是敏感的，如对于同 一个数据集合，以不同的顺序提交给同一个算法时，可能产生差别很大的聚类结果。 5 数据处理的高维性：一个数据库可能含有若干维或者属性，很多聚类算法擅长 处理单维或低维数据，然而低维聚类质量难得到保证。通常在多维的情况下能够很好 地判断聚类的质量。因此需要聚类算法能处理高维数据。 6 抗干扰能力：在现实应用中绝大多数都包含了孤立点，未知数据、空缺或错误 的数据。因此聚类算法应能对这样的噪音数据具有抵抗能力，否则聚类结果质量不能 确保。 1 4 长安大学硕上毕业论文 3 2 经典的聚类算法 在数据挖掘领域中，聚类分析是一项重要的研究课题。它与分类有所不同，聚类 算法的目标是在没有任何先验知识的前提下，根据数据的相似性将数据聚合成不同的 簇( 或类) ，使得相同簇中的元素尽可能相似，不同簇中的元素差别尽可能大，所以 又被称为非监督分类。 对于一个给定的数据集，聚类就是将数据集中的对象划分为群或类，使得一个类 中的对象“类似 ，而不同的类中的对象“不类似。一般来说，评价相似性的角度 有三种，分别是基于距离的、基于密度的以及基于连接的。前两类通常适用于欧几里 得空间，第三类则适用于任意度量空间。 依据评价相似度的角度，聚类算法也可相应地分为三类【1 6 】：认为簇是由距离接近 的点组成的基于距离的聚类算法：认为簇是由相连的密集区域组成的基于密度的聚类 算法；认为簇是由强连接的边上的点组成的基于连接的聚类算法簇有多种表示方法， 比如代表点、核心点、单元等。基于距离的聚类算法大多采用代表点表示簇，可以只 使用一个点来表示一个簇，这个点可以是该簇的质心( 簇中所有点的平均值) ，也可以 是该簇中位置最接近中心的点，因此基于距离的聚类算法只能识别球形簇；也可以使 用多个点来表示一个簇，这些代表点比较真实地反映簇的边界情况，因而适合于非球 形簇的表示。基于密度的聚类算法大多采用核心点或单元表示簇，其中，n n 方法采 用核心点表示簇；而基于单元的方法采用密集单元表示簇，但由于单元只是对落入其 中的数据点的近似描述，因此只能近似反映簇的情况。 目前的聚类算法可以分为五大类：划分法、层次法、基于密度的方法、基于网格 的方法和基于模型的方法【l 们。下面简单的分别介绍这几类聚类算法。 3 2 1 划分聚类算法 划分聚类的开始是一个初始划分，通过优化一个评价函数把数据从初始划分分解 成若干子划分，因此可以把聚类问题转化为划分问题。划分聚类方法输出的是多个互 不相交的聚类集，如：k m e a n s 算法、c l a r a 算法、c l a r a s 算法。k m e a n s 算法 的思想【1 7 1 是一种迭代的聚类算法，迭代的过程中不端移动簇集中的对象直到得到理想 的簇集为止，每个簇用该簇中对象的平均值来表示。k - m e d o i d s 算法【1 8 】选取一个对象 m e d o i d 来代替聚类中心的作用，这样的一个m e d o i d 就标识了这个类。这种算法对于 脏数据和异常数据不敏感，但计算量要比k m e a n s 要大，一般只适合小数据量。c l r a r 15 第三章聚类算法 算法是一种基于采样的方法，能够处理大量的数据，算法思想就是用实际数据的抽样 来代替整个数据，然后在这些抽样的数据上利用k m e d o i d s 算法，c l r a r 算法的效 果取决于采样的大小和采样的方法，一般不太可能得到最好的结果。所以在c l r a r 算法的基础上，又提出了c l r a r s 算法。与c l r a r 算法不同的是：c l r a r 算法在 寻找最佳的m e d o i d s 的过程中，采样是不变的。而c l r a r s 算法在每一次循环过程中 所采用的采样都是不同的。 1 k _ 平均算法【1 7 】 k 一平均算法是一种迭代的聚类算法，迭代过程中不断移动簇集中的对象直到得到 理想的簇集为止，每个簇则用该簇中对象的平均值来表示。利用k 一平均算法得到的 簇，簇中对象的相似度很高，不同簇中对象之间的相异度也很高。处理过程如下算法： ( 1 ) 从n 个数据对象随机选取k 个对象作为初始簇的中心； ( 2 ) 计算每个簇的平均值，并用该平均值代表相应的簇； ( 3 ) 计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划 分； ( 4 ) 转第二步，重新计算每个( 有变化的) 簇的平均值。这个过程不断重复直到某个 准则函数不再明显变化或者聚类的对象不再变化为止： 一般，k 一平均算法的准则函数采用平方误差准则，定义为： 七 2 e = l p 一聊 ( 3 1 ) f _ i p e c j 其中，e 是数据集中所有对象与相应聚类中心的均方差之和，p 为给定的数据对 象，豫为聚类c ，的均值( p 和m 均是多维的) 。k 一平均算法对于大型数据库是相对 可伸缩的和高效的，算法的时间复杂度为0 ( t k n ) ，其中t 为迭代次数。一般情况下 结束于局部最优解。但是，k 一平均算法必须在平均值有意义的情况下才能使用，对分 类变量不适用，事先还要给定生成簇的个数，对噪声和异常数据比较敏感，不能对非 凸面形状的数据进行处理。 2 k 一中心点算法【1 9 】 p a m ( p a r t i t i o n i n ga r o u n dm e d o i d s ) 算法，也被称为k