（计算机软件与理论专业论文）基于信息扩散的预测建模技术在数据挖掘中的应用.pdf

中山大学硕上学位论文 基于信息扩散的预测建模技术在数据挖掘中的应用 专业：计算机软件与理论 硕士生：赵晶 指导教师：高集荣 摘要 信息时代，谁掌握了信息，就掌握了机遇。在金融、商业、通信、军事、生 物、媒体等领域存在大量的信息，如何从这些浩如烟海的数据中发现有用的知识， 成为人们一直追求的目标。数据挖掘的诞生标志着人们开始能够发掘和利用知 识，不会在庞大的数据面前束手无策。大量的数据经过诸如清洗、整理、分类、 聚类、回归等数据挖掘操作之后，成为有效的信息提供载体，人们可以发现深层 次的数据关联，提取和发现由于海量数据而受到隐藏的模式和模型。数据挖掘中 的预测建模技术是一种有效手段，线性回归模型以及在其基础上发展起来的多元 回归、神经网络等均成为人们分析数据，描述数据的重要工具。然而，线性回归 模型由于其自身计算过程的约束，受到数据的粗差影响较大，结果不够稳定，需 要探求新的解决方案。 数据说到底是一种信息，在目前人类的认识手段还有限的情况下，并不可能 得到需要的所有样本，即样本具有非完备性，然而人们也并没有因此放弃对于客 观世界的研究，提出了很多行之有效的方案来解决这一问题，模糊信息理论就是 其中一种。在模糊信息论看来，每一个观测点不仅仅是一个有数值意义的观察值， 而且是具备一定模糊信息的信息扩散点，向“周围”发散信息，同时也从“周围” 接受信息，这就是所谓的信息扩散。这样，一组有限的观测向量成为一个蕴涵着 很多模糊信息的信息群体。这种直接从原始数据驱动获得信息的估计方式就是信 息扩散估计，它比起传统的参数估计方法有更广泛的应用，摆脱了对原始分布的 假设，对数据分类和预测的把握更加准确。 由此，将信息扩散理论引入数据挖掘领域，能够更好的解决实际问题，成为 人们决策参考时能够信任并使用的理论支撑和技术手段，从而以信息论的方法解 决大量信息载体的问题。 关键字：数据挖掘信息扩散原理信息扩散估计分类预测 中山大学硕士学位论文 t h ep r e d i c t i o nm o d e l i n gt e c h n o l o g yb a s e do ni n f o r m a t i o n d i f f u s i o na n di t sa p p li c a t i o ni nd a t am i n i n g m 砌o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：j i n gz h a o s u p e r v i s o r ：j i r o n gg a o a b s t r a c t i ni n f o r m a t i o na g e ，w h o e v e rf i r s to w n st h ei n f o r m a t i o na l s of i r s to w nt h eo p p o r t u n i t y t h e r ei s l a r g eq u a n t i t y o fi n f o r m a t i o ni nt h ef i e l d so ff i n a n c e ，c o m m e r c e ， c o m m u n i c a t i o n ，m i l i t a r y ，b i o l o g y ，m e d i aa n de t c o n ec h a l l e n g i n gg o a li sh o wt of i n d u s e f u lk n o w l e d g ef r o mt h eh u g ed a t a d a t am i n i n gc a nb er e g a r d e da sp o w e rm e t h o d t om i n ea n df i n dk n o w l e d g e t h e r ei sn os u c hs i t u a t i o nt h a tp e o p l ec a n n o td e a lw i t h m a g n a n i m o u sd a t a p e o p l ec a nt r a n s f e rd a t at oe f f i c i e n ti n f o r m a t i o nc a r r i e rb yd a t a m i n i n go p e r a t i o ns u c ha sc l e a n i n g ，t i d y i n g ，c l a s s i f i c a t i o n ，c l u s t e r ，r e g r e s s i o na n de t c ， f i n dt h ed e e pa s s o c i a t i o n sa m o n gd a t a ，d i s t i l la n da c q u i r et h eh i d d e np a t t e r na n d m o d e l n ep r e d i c t i o nm o d e l i n gi nd a t am i n i n gi sa na v a i l a b l et e c h n o l o g y 1 i n e a r r e g r e s s i o nm o d e la n di t se x t e n s i o n si n c l u d i n gm u l t i v a r i a t er e g r e s s i o n ，n e u r a ln e t w o r k a r eg o o dt o o l sf o rd a t aa n a l y s i sa n dd a t ad e s c r i p t i o n a tp r e s e n t ，l i n e a rr e g r e s s i o n m o d e lo f t e nb r i n go nv o l a t i l er e s u l t sd u et ot h ec o n s t r a i n t si t s e l fa n dt h ei m p a c to ft h e d a t ai n a c c u r a t e n e s s t h e r en e e db e t t e rs o l u t i o nt os o l v et h ep r o b l e m d a t ai sak i n do fi n f o r m a t i o ne s s e n t i a l l y p e o p l ec a n n o to b t a i nt h ee n t i r es a m p l eu n d e r c u r r e n tl i m i t e dc o g n i t i o nc a p a b i l i t y t h i si sc a l l e ds a m p l ei n c o m p l e t e n e s s p e o p l e h a v et h o u g h tu pm a n ym e a n st os o l y et h i sp r o b l e m o n eo fw h i c hi sf u z z yi n f o r m a t i o n p r i n c i p l e i ns u c hp r i n c i p l e ，e a c ho b s e r v a t i o np o i n ti sn o tan u m e r i c a lv a l u ep o i n t ，b u t a ni n f o r m a t i o nd i f f u s i o np o i n tt h a tc o n t a i n ss o m ef u z z yi n f o r m a t i o n i tc a nd e l i v e r i n f o r m a t i o nt o0 t h e rp o i n ta n da c c e p ti n f o r m a t i o nf r o mo t h e r si nt h em e a nt i m e w h i c h i sc a l l e di n f o r m a t i o nd i f f u s i o n t h e r e f o r e an u m b e r e do b s e r v a t i o np o i n ts e tb e c o m e s a ni a f o r m a t i o ng r o u pc o n t a i n i n gm u c hf u z z yi n f o r m a t i o n i n f o r m a t i o nd i f f u s i o n e s t i m a t i o ni ss u c has t y l et h a td i r e c t l yo b t a i n si n f o r m a t i o nf r o md a t as o u r c e i tg e t s m o r ea p p l i c a t i o nt h a nt r a d i t i o n a lp a r a m e t e re s t i m a t i o na n dg e tr i do ft h eh y p o t h e s i so f o r i 百n a ld i s t r i b u t i o n ，s o ，i t sc a p a b i l i t yf o rd a t ac l a s s i f i c a t i o na n dp r e d i c t i o ni sm o r e p r e c i s ea n de f f i c i e n t i nt h i so p i n i o n ，i n f o r m a t i o nd i f f u s i o np r i n c i p l ei sp r o p e rf o rd a t am i n i n gf i l e d i tc a n b ea p p l i e df o rs o l v i n gp r a c t i c a lp r o b l e m ，b e c o m eat r u s t e dr e f e r e n c et h e o r ya n d t e c h n o l o g yw h e np e o p l em a k ed e c i s i o n ，t h e nd e a lw i t hv a s ti n f o r m a t i o nc a r r i e r sb y i n f o r m a t i o nt h e o r y k e y w o r d ：d a t am i n i n g ，i n f o r m a t i o nd i f f u s i o np r i n c i p l e ，i n f o r m a t i o nd i f f u s i o n e s t i m a t i o n ，c l a s s i f i c a t i o n p r e d i c t i o n i i 中山大学硕士学位论文 1 1 研究背景 第1 章引言 上世纪八十年代，e e c o d d 提出的关系数据库思想广泛为人们所接受，随即 数据库技术得到了迅速发展，数据库管理系统广泛应用于各行各业，人们积累的 数据越来越多，我们产生和收集数据的能力已经迅速提高。当前，电子商务和电 子政务方兴未艾，网络经济产生了大量的文本，图像和视频数据，个人和企业管 理中出现各种类型的数据，“信息时代”已经到来，我们生活在一个数据的时代 里。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行深入细致的 分析，以便更好地利用这些数据作为决策支持的参考。同时也应当看到，这些数 据的数量相对于我们来讲过于庞大，依赖传统的数据库管理系统和人工手段不能 实现我们的预期，一种具备自动分析数据、分类数据、汇总数据、预测数据趋势、 标记异常、记录用户喜好的计算机辅助工具成为当前研发的热点。数据挖掘( d a t a m i n i n g ，d m ) 自然而然的站到了前沿科学的位置。 自1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上首先提出了知识 发现( 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 ) 的概念以来，迄今为止，k d d 的国际 研讨会已经召开了7 次，人数也由最开始的二三十人的专题讨论会发展到七八百 人的国际学术大会，研究重点由发现方法转向系统应用，侧重多种策略和技术集 成，涉及数据库，人工智能，信息处理，知识工程等诸多领域，数据挖掘和知识 发现成为当前计算机科学界的一大热点。 数据挖掘就是对观测到的数据集( 经常是很庞大的) 进行分析，目的是发现 未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结数据。“3 与 以往的数据库查询不同，数据挖掘的服务对象是高层的决策者，数据库是对客观 世界的组织和表现，数据挖掘是对归纳数据库的研究，其本质是为了更好的认识 客观世界，以满足人们的需求。现实中存在着大量的、不完全的、有噪声的、模 糊的、随机的数据，人们迫切希望数理统计和概率论的理论知识得到一种应用技 中山大学硕士学位论文 术的融合，数据挖掘能够很好的发挥它们的强大作用，比起以往的数据库技术功 能更加强大，数据归纳能力更高，从理论研究上来说，数据挖掘给了传统理论一 个更大的发展空间，这也是其得到很多学科学者关注的原因。 数据挖掘处理的是海量数据，对于数据量大的行业如银行、电信等，积累几 十上百g b 的数据并非难事，而对于另一些行业如加工制造业，积累一定规模的 数据需要一定的时间，这样，从时间跨度过长的数据中得到得知识往往不能紧随 当前趋势的发展，或者由于数据量庞大，现有的计算机处理能力有限，不能一次 完成全部数据挖掘，只能部分的处理数据，即所谓的增量挖掘，由此，人们产生 了对预测趋势的研究，期望从有限的当前数据中得到对将来形式合理有效的预测 分析。 本人正是在对数据挖掘和知识发现的学习研究过程中，对于数据挖掘中的预 测建模领域比较感兴趣，借鉴了同领域以往的研究成果，并学习了模糊信息论中 的部分知识，通过比较两者中处理问题的相似性，在数据挖掘中引入信息论中的 估计方法，完成对预测建模的改进并加以应用，实现了学位论文的写作。 1 2研究现状 前面提到越来越多的人加入到了数据挖掘和知识发现的研究中，学术团体的 扩大意味着理论知识的发展，数据挖掘历经十余年的发展，从最终完成的任务角 度来分，可以有概念描述，关联分析，分类，预测，聚类分析，时序分析等几个 大类的研究方向，涉及多学科技术的融合。 数据挖掘是为了发现数据中的模型，其建模技术分为描述建模和预测建模。 描述建模侧重对数据进行概括，描述数据的所有特征；预测建模根据已知的变量 值来预测其他的变量值，这其中又可以根据变量类型分为用于分类的预测建模 ( 离散、标称变量) 和用于回归的预测建模( 连续、有序变量) 。预测中用于输 入的变量称为预报变量( p r e d i c t o rv a r i a b l e ) ，被预测变量称为响应变量( r e s p o n s e v a r i a b l e ) 。相比之下，预测建模的目标更加明确，如给定某股票当前的市值来预 测其将来的市值和波动趋势。 预测分析方法常用回归统计技术。常用的模型有线性回归、多元回归和非线 2 中山大学硕士学位论文 性回归。线性回归、多元回归常用最小二乘法做回归处理，许多非线性问题都可 以通过预测变量上的变换，转换成为线性问题。 很多书籍包含回归技术，如。1 ，对线性回归和多元回归的最小二乘法做了很好 的讲述，提出j b o x j e n k i n s 自回归模型族，该模型把当前值y ( t ) 模拟成过去值y ( t k ) 的加权线性组合；新近的非线性回归模型包括投影追击。1 和多元回归的数据驱动 模型m a r s “1 ；当预测变量间存在许多较高阶依赖时，回归树“3 在性能上常常可 以与其他回归方法媲美；经典的“跳跃定界”算法可以高效的搜索回归模型中应该 包含的最佳变量子集”1 ；还存在基于规则的回归模型的有关技术“1 ，置于贝叶斯 框架之下的回归。1 ；有人对局部回归技术做了改进，依靠可适应的局部拟合来实 现非参数的回归模型。1 。 在应用方面，吕品使用线性回归技术对金融业款额进行了预测挖掘“，蔡章 利等设计了线性回归挖掘模型，应用于m d s s 系统的销售预测“。李邦云等利用 临近日和相似日的负荷一电价数据，根据不同情况进行加权回归，最后利用该回 归模型进行电价预测“；周强等应用偏最小二乘法在挖掘中发现异常数据“。时 念云等先使用属性分类得出简单的i f _ t h e n 规则，在利用多元线性回归模型剔除次 要属性，得到最优回归方程“。预测技术也可以与其他理论相结合来获得解决方 案，例如丁崧等提出基于n 阶转移概率矩阵的预测算法，并依据最小置信度和支 持度控制矩阵的大小“，牛芳给出了一种基于马尔可夫链的随机过程方法“。 工具方面，有很多软件支持多种曲线回归分析，包括线性、指数、对数、倒 数、二次、三次等，t i b e r i u s 基于神经网络方法，提供可视化工具使用户可以进 入黑盒内部观察神经元动作；s t a t i s t i c a 对线性回归的评价结果比较齐全，包 括a n o v a 表、相关系数矩阵与协方差矩阵、散布图显示、例外分析与残值分 析。微软的a n a l y s i ss e r v i c e 是一款不错的多维数据建模及挖掘工具，且提供 了功能齐全的接口可供用户自行开发自己的应用程序。a n g o s s 公司的k n o w l e d g e s e r v e r 提供了完整的数据挖掘操作，包括聚类、决策树、增益图、评分、可以对 多种数据源进行操作，执行速度快，结果可视化效果好。 数据挖掘以其对事物发展趋势更好的把握吸引了人们的注意，人们更加关心 数据挖掘对当前和今后的指导作用，而不是等待数据积累到一定规模再去做数据 挖掘，那样将丢失很多的时效信息，且对当前决策的支持不大，也许花费半天时 中山大学硕士学位论文 间对半年前的数据挖掘出的规则在今天看起来并无多大指导作用。纵观上述研 究，可以总结出如下问题： 1 数据挖掘中的模型通常是实验性的，可能没有包含理想预测所必须的所 有预测变量( 也存在变量不可测的情况) ，或者没有包含变量之间的某种 函数关系，而且每次的测量值会受到客观条件的限制而产生变化，所以 对于响应变量的预测都会存在着关联误差。 2 回归预测中通常假设预测变量的各个观测值相互独立，现实中预测变量 问是存在联系的，如股票，金融指数，所以简单的线性回归会忽略这部 分联系，构造出的模型并没有反映真实的情况。同时，建模集中在对原 始数据的分析，缺少对于已有的挖掘结果如关联规则的预测分析，从而 达到二次挖掘的目的。 3 现实数据存在大量的随机性和不确定性，单纯针对数据的操作很大程度 上受到数据的制约，所拟合的模型难免受到个别数据的影响，数据挖掘 中的孤立点分析能够给这个问题一个较好的解决方案，然而，我们是要 解决预测建模问题，而非模式识别，孤立点的存在对于预测建模存在很 大的干扰作用，如何在不进行数据清洗的前提下消除这一影响，需要一 个较好的解决方案。 可以看出，预测建模技术还有待进一步的研究和发现，采用其他领域的理论、 方法和技术来解决数据挖掘存在的问题是数据挖掘研究中的一种趋势。由此，本 人对上述问题做了有针对性地研究，借鉴信息论的理论成果，做了一些有意义的 工作。 i 3本文目的和创新点 针对上述数据挖掘中乃至统计中尚存在的问题，本文作者寄希望提出一种合 理有效的解决方案，回答上述问题。 人们认识世界，获得的是信息。数据是对客观世界的反映，数据库则是数据 的一种组织形式，那么数据挖掘则是要从数据中获取更多的信息，从这方面来说， 数据库或数据仓库是信息的集合体，统计分析从中获取一部分浅层次的信息，数 4 中山大学硕士学位论文 据挖掘和知识发现获取深层次的、不容易发现的信息。由此，用信息论的理论和 方法来解决问题是合理的方案之一。 本文将采用信息扩散原理来解决数据挖掘问题，它是基于模糊信息优化处理 理论的- - f 新原理，发展了信息分配方法。信息分配已被工程界广泛接受，信息 扩散以其作为理论框架，凭借其实用的扩散模型在很多领域有着重要的应用。本 文作者将其引入数据挖掘领域，不但是为了解决研究中发现的问题，而且还想起 到抛砖引玉的作用，希望在数据挖掘领域有更多信息理论的应用。 本文目的有二，一是将信息扩散估计在参数估计中的优势引入到数据挖掘 中，说明其有效性和高效性；二是对数据挖掘的一次结果( 如关联规则) 做信息 扩散的应用，达到预测分析的目的，实现二次挖掘。 本文的创新在于，信息扩散估计作为模糊信息的优化技术，对信息的估计和 预测比简单的数学方法拟合效果更好，而在数据挖掘领域，很多的计算更多的是 依赖数理统计的知识，计算的复杂度加大，对研究人员的理论素养和计算机硬件 条件要求都较高，学习周期长，不利于这门学科的发展壮大，那么，引入信息论 的内容，跟生活联系比较紧密，而且处理效果好，易于被人接受和掌握，能够更 好的促进数据挖掘的发展，同时提供了另一种角度来审视数据挖掘问题。 1 4 论文的组织结构 为了更好的说明上述问题，本文后续章节将按照以下内容组织和描述： 第二章是数据挖掘技术概论，主要是对数据挖掘的概念和发展进行概要的阐 述，并介绍和分析有关预测建模的研究现状，叙述理论原理和部分的算法实现， 目的在于对现有方法的总结和发现问题。 第三章是信息扩散的有关知识，将系统的介绍信息扩散原理和信息扩散估 计，并对它们的应用做简要介绍，为下文引入到数据挖掘领域做铺垫，了解其理 论意义和实际意义。 第四章介绍参数估计的内容，对当前数据挖掘中用到的几种主要参数估计的 方法做简要的介绍，同时用信息扩散估计和其中的e m 算法估计做一个对比，体 现信息扩散估计的正确性和高效性，从参数估计的角度入手解决数据挖掘问题。 中山大学硕士学位论文 第五章是本文的核心部分，主要是基于参数估计来解决前面讲到的增量挖掘 问题，将通过信息扩散估计来对数据挖掘的一次结果进行参数估计，达到二次挖 掘的目的。从而将这一方法应用到一个实际的时间序列数据挖掘任务中去，达到 预期的效果。 第六章是对全文的总结和展望，总结本文的特点和下一步的研究工作方向。 附录部分是对原型系统c a r n a t i o o n d m 的详细介绍，主要说明了开发过程和 已实现的功能，以及下一步的开发工作方向。 中山大学硕十学位论文 第2 章数据挖掘技术 2 1 数据挖掘综述 数据挖掘技术的产生是人们对于数据库技术不断研究和开发的结果，随着数 据的激增，人们希望得知其背后隐藏的重要信息，更好的利用数据。目前计算机 的数据库可以高效的实现数据录入、查询、访问、统计等功能，但是无法发现数 据的关联，其中存在的模式和规则、趋势都被其海量的规模隐藏了，数据挖掘技 术的三个支撑技术：海量数据搜集、多处理器计算机和数据挖掘算法都已发展成 熟，这为数据挖掘的发展奠定了基础。自从有了数据挖掘，人们就摆脱了“数据 爆炸但知识贫乏”的窘境。那么，什么是数据挖掘? 本节就从其概念入手来逐步 了解数据挖掘。 2 i 1 数据挖掘概念 不同的人对待同一事物有不同的看法，“盲人摸象”的典故说明了这一道理。 同样，数据挖掘是一个多学科交叉研究的领域，研究人员来自多个行业，学科， 自然看待数据挖掘的角度也不一样，数据挖掘的定义也不是一两句话就能概括 的。 从技术角度看，数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随 机的实际应用数据中，提取隐含在其中的、人们事先不知道的但又是潜在有用的 信息和知识的过程。这个定义包括几层含义： 1 ) 数据源必须是真实的、大量的、含噪声的 2 ) 发现的是用户感兴趣的知识 3 ) 发现的知识可接受、可理解、可运用 4 ) 仅支持特定的发现问题 这里提到了知识发现( 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 ，k d d ) ，并且近年 来有关数据挖掘和知识发现的国际会议越来越多，涉及范围也更广，包括 d m k d ( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) 的基础理论、发现算法、数据挖 7 中山大学硕士学位论文 掘与数据仓库及o l a p 的结合、可视化技术、知识表示方法、w e b 中的数据挖掘 等。i e e e ，a c m ，i f i s ，v l d b ，s i g m o d 等也纷纷把d m k d 列为会议议题或出版专刊， 成为当前国际上的研究热点。那么针对数据挖掘与知识发现的关系也有着几种不 同的观点“： 1 k d d 是数据挖掘的一个特例 这是早期文献比较流行的观点，认为数据挖掘可在多种数据组织形式中挖掘 知识，知识发现只是数据挖掘的一个方面，强调数据挖掘在源数据形式上的 多样性。 2 数据挖掘是k d d 过程的个步骤 f a y y d ，p i a t e t s k y s h a p i r o 和s m y t h 在1 9 9 6 年出版的论文集知识发现和 数据进展中给出二者的定义并加以区分，他们认为，k d d 是从数据中辨别有 效的、新颖的、潜在有用的、最终可理解的模式过程，数据挖掘是这一过程 中通过特定算法在可接受的计算限制效率内生成特定模式的一个步骤。这样 的看法有助于人们聚焦研究重点，有效地解决问题，因而得到了大多数学者 的认同。 3 k d d 与d a t am i n i n g 含义相同 在现今的一些技术综述中，两个术语仍不加区分使用着，有人认为他们是一 个概念，k d d 在人工智能界更流行，d m 在数据库界用的多。只是叫法不同而 已。 虽然观点有出入，但都没有离开其本质，仍然是从数据中挖掘知识，所以针 对d a t am i n i n g 和k d d 的区别大可不必产生争论，不同场合的侧重点不一样，能 够在不同层面上来理解就可以了。 从商业角度看，数据挖掘本质上是一种新的商业信息处理技术。按照企业的 既定业务目标，对大量的企业数据进行深层次分析以揭示隐藏的、未知的规律性 并将其模型化，从而支持商业决策活动。从这方面来看，数据挖掘有着很强的商 业应用目的，只有面向特定的商业领域才有应用价值。 数据挖掘从一开始就是面向应用的，是一种深层次的数据分析方法。同样是 处理数据对象，数据挖掘与统计方法有什么区别呢? 首先，笼统来说，两者的目 的不同，统计总是要解决某方面的问题去采集数据，而数据挖掘往往是针对这些 中山大学硕士学位论文 为了其他目的采集的数据再去做深入细致的分析处理，而不是专门去采集数据。 其次，两者处理的数据集大小不同。g b 级的数据库在数据挖掘中并不少见，而 传统的统计方法却无法处理。再者，数据往往包含多个变量，维度效应即数据随 着变量的个数的上升呈指数级增长，传统的统计能够处理的二维数据显然远远满 足不了需求。最后，数据是不断变化的，这也是本文关注的重点，如何从不断变 化的数据中提取模式，估计模型的参数，统计不会关注此类问题，这是数据挖掘 专门解决也是善于解决的问题。 至此，对于数据挖掘是什么的问题已经有了一个比较清晰的认识，那么下一 步的任务则是认识数据挖掘的结构。 2 1 2 数据挖掘构成 数据挖掘是面向应用的技术，其系统构成与一般的数据库系统并无大的差 异，差别在于使用的算法和针对的数据。传统的数据库系统功能集中在查询，修 改，更新，专注于更快的存取方式和良好的人机界面。如微软公司的数据库管理 系统s q ls e r v e r ，用户通过s q l 语句操控数据，能够完成基本的数据业务。 数据挖掘系统目的在于发现未知的模式，因而在核心部件数据挖掘引擎的设计上 要复杂的多，比起一般的数据库处理的数据量要大。操作方法也可以通过一种类 s q l 语言数据挖掘查询语言d m q l ( d a t am i n i n g q u e r yl a n g u a g e ) 来实现，例如， m i n ea s s o c i a t i o n sa sb u y i n g h a b i t s m a t c h i n gp ( x ：c u s t o m e r , w ) a q ( x ，y ) 一b u y s ( x ，z ) 该语句是描述客户购买习惯的关联规则挖掘。其中，x 是关系c u s t o m e r 的关键 字，p 和q 是谓词变量，可以作为任务相关数据的相关属性或维，w ，y ，z 是对象 变量，分别在对应的顾客x 的谓词上取值。 总体说来，一个普通的数据挖掘流程如图2 - i 所示。 中山大学硕士学位论文 图2 - 1 数据挖掘流程 从逻辑上来分，数据挖掘系统包括三个主要组成部分，即数据处理模块、数 据挖掘引擎模块和用户接口模块。如图2 2 所示。每一模块都具备独立的功能， 上层模块向下层模块提出任务要求，下层模块接受向上层模块请求并提供结果反 馈。每一层又由几个重要的组成要件构成，它们也是当前和今后研究的重点。 从图中的最底层可以看到，最终的数据库类型多种多样，可以根据数据库类 型来分类数据挖掘系统，可以有文本的，多媒体的，空间的，时间序列的，事务 的，w e b 的等数据挖掘系统。这涉及到数据挖掘分类的问题，下面的小节将介绍 这部分内容。 2 1 3 数据挖掘分类 由上节可知，数据挖掘可以根据挖掘的对象分类，亦存在其他分类方式。 根据挖掘的知识类型或者说数据挖掘的任务可以分为：分类或预测模型发 现，数据总结与聚类发现，关联规则发现，序列模式发现，相似模式发现，依赖 关系或依赖模型发现，异常和趋势发现等。 根据数据挖掘方法分为：机器学习方法，统计方法，聚类分析方法，神经网 络方法，遗传算法方法，数据库或数据仓库方法，粗糙集或模糊集方法等。 这些分类方法从不同角度描述了数据挖掘研究的方法和策略，是互相交叉又 互相补充的。 1 n 攀 中山大学硕+ 学位论文 i 一熬缴然篓基黝 事务数揪阵多媒体擞榭库 图2 - 2 2 1 4 数据挖掘发展趋势 文术数搬库 空阀教捌库 数据挖掘系统 前面在系统结构介绍的时候稍微提到了一些发展趋势的内容，如可视化数据 挖掘，复杂数据类型挖掘，其他的趋势还包括有特定应用的数据挖掘系统开发， 数据挖掘与数据库、数据仓库和w e b 数据库的集成，基于约束的挖掘和可视化， 中山大学硕士学位论文 算法的可伸缩性，数据挖掘语言的标准化，w e b 挖掘，数据挖掘中的隐私保护与 信息安全等，这些都是亟待解决的实际问题，有待人们进一步的研究和发现【2 。 数据挖掘处理的是海量数据，对机器的性能和存储方式、存储介质都有很高 的要求，随之带来的高成本也不是一般企业所能承受的，由此产生了对预测型知 识发现技术的研究，利用已有的观测值来预测发展趋势，对于感兴趣的模式继续 挖掘，而摒弃那些低于兴趣度的知识，既节约了成本，又为决策者提供了有价值 的参考。下一节将开始介绍预测建模技术。 2 2预测建模技术 预测建模的过程也就是发现预测型知识的过程，所谓预测型知识是指由历史 和当前的数据产生的并能推测未来数据趋势的知识。这类知识的挖掘可以借助经 典的统计方法、神经网络和机器学习等技术，其中，经典的统计学方法是基础， 也就是常用的回归分析技术。前面提到预测建模的两种用途，分类和回归。本文 的重点将以涉及有数值意义的预测模型数据为主，所以这里将针对回归预测建模 展开讨论。预测建模能够发现的模式大致有以下几种： 1 趋势预测模式，主要是针对具有时序属性的数据，如股票等，或是序列 项目的数据，如工龄和退休金的对照等，发现长期的趋势变化。1 1 阶移 动平均值、n 阶加权移动平均值、最小二乘法、徒手法等统计学方法可 以用于这类的挖掘。 2 周期分析模式，对那些数据分布和时问的依赖性很强的数据进行周期模 式的挖掘，如服装在某季节或所有季节的销售周期。存在挖掘局部周期 的最大自模式匹配集方法1 2 1 1 。 3 序列模式，针对历史时间发生次序的分析形成预测模式来对未来行为进 行预测。这方面主要的工作有序列模式挖掘方法。”和称为f r e e s p a n 的高 效序列模式挖掘算法。“。 4 神经网络，大量的时间序列是非平稳的，其特征参数和数据分布随时间 的推移而发生变化。仅仅通过对某段历史数据的训练来建立单一的神经 网络预测模型，还无法完成准确的预测任务。当预测模型不适用于当前 中山大学硕士学位论文 数据时，还可以用统计学的再训练方法对模型重新训练，获得新的权重 参数，建立新的模型。 回归预测中存在多种回归模型和技术手段，最基本的就是线性回归模型，其 它回归模型多是在其基础上衍变而来，这一类回归技术在数据挖掘中得到了很广 泛的应用。 2 2 1 线性回归模型 线性回归是最简单的回归形式。这种模型的最简单形式得到的响应变量y 的 预测值岁也是预报变量z i 的线性组合： 妒”善甲， ( 2 1 ) 实际上并不可能得到y 的理想值，而是预测出y 在预报变量的每个向量位置 所取的均值，y 是对y 在x = x ，。) 点的均值的预测性估计。最简单的情况下 p = 1 ，仅有一个预报变量( 单一回归) ，得到一条回归直线，一般情况下是多重 回归，这时是一个回归平面。这种模型应用范围很广，n n 甜：n a ，一是简单 的加权求和易于计算且易于理解：二是它在很多情况下都可以达到很好的性能。 使用线性模型得到最好的简单近似。 由前面论述这种模型存在的问题可知，观测值和预测值必然存在着差异( 残 差) ，表示为e 。 y a ) = 萝o ) + e o ) = n 。+ 善la j x j ( i ) + e o ) ，1 s is n(2-2) 用向量y 表示训练样本中的n 个对象的观测值，用，l ( p + 1 ) 矩阵x 表示测量n 个对象得到的p 种预报变量值，上式采用矩阵表示为： y 。x a + e ( 2 - 3 ) 其中，y 是：n x l 的响应值矩阵，a = 0 。，痒。) 表示( p + 1 ) x l 的参数值向量， e = 0 ( 1 ) ，e 0 ) ) 是包含残差的n 1 向量。很明显，参数向量的取值对于模型预测 中山大学硕士学位论文 精度有很大影响。人们设计了很多用来衡量精度的不同尺度，这些尺度就是用来 比较不同模型的评分函数。这其中，误差平方和评分函数是目前为止最流行的方 法。因此，可以通过2 - 4 式求得使e 中的元素最小化的参数向量a 。 喜e g ，2 = 砉( ) ，g ，一薹以，x ，o ，) 。 c z 一 以单个预测变量为例说明最小二乘法的过程，多元回归原理与其一致。线性回归 方程设为y = a 。4 - g 1 x ，令 q 2 善e ( f ) 22 善( y ( i ) - a o - a l x ( i ) ) 2 ( 2 5 ) 最小摊( 1 e a s ts q u a r e sm e t h o d ) 要求系数口。，n 。使得q 达到极小值，分别对n 。，d ， 求偏导数，并令其为0 ，得到 詈2z 渺) - a o - a l x ( i ) ) - l j ( 2 - 6 ) 詈= 2 耋( y ( f ) - a o - a 。x 晰) _ o ( 2 - 7 ) 口。= 歹一口，i ( 2 8 ) a ：壁竺：型! 薹竺：鲨鲨1 1 = 型- l 一= 旦f 一 善。o ) 2 一善。( f 声善。( ) 一i ) 2 ( 2 9 ) 对于多个预报变量情形，设( ( f ) ，墨( i ) ，z ，( f ) ) = q 薯( f ) ，z ，( f ) ) 是p 维预报变 量向量。使用矩阵形式表示使2 4 式最小化的参数值a 为： a = 一1 x 1 y 将得到的回归系数a 代入公式2 1 求y 值的预测值y 。 陀- 1 0 ) 1 4 中山大学硕上学位论文 一 昌 。 一 如 一 鞴 廿 总体模式的线性关系 051 0 1 52 02 5 工作年数 图2 3 毕业年数与年薪的线性关系 图2 3 显示了大学生毕业后工作年数与年薪的关系，总体上来看是呈线性增长。 该模型的参数就可以直接利用最小二乘法求出( 图中已显示) ，具体计算过程不 再列出。同样，对于多响应变量的情况也适用。 2 2 2 广义线性回归 线性回归用于对连续值函数进行建模，借助广义线性模型的理论，同样也能 够对于离散值变量建模，用于预测类标号。广义线性模型具有三个主要的特征： 1 y o ) o = 1 ，n ) 是独立的随机变量，服从相同的指数族分布1 。 2 预报变量是以v ( i ) 2 4 ，( f ) 的形式组合的，称为线性预报量( 1 i n e a r p r e d i c t o r ) ，参数是通过这种形式进入模型的。 3 给定的预报向量的均值p ( f ) 和2 中的线性组合是通过连接函数 g ( o ) ) = v o ) ；n ，z j o ) 联系起来的。 第一和第三条中对分布连接函数并未做任何限制，这样可以放宽要求，得到 其他种的回归模型。对于多重回归，连接函数就是恒等式；对于l o g i s t i c 回归， 指数族指正态、泊松、伯努里和二项分布。 1 5 踟 加 0 中山大学硕士学位论文 分布是伯努里分布，连接函数为分对数( 1 0 百c ) 连接函数g ) ：l o g 士；对于泊松 回归，分布为泊松分布，连接函数是对数连接函数g ) = l o g ( u ) 。 下面以l o g i t s t i c 回归为例，介绍一种扩展的线性回归模型。在很多情况下， 响应变量并不是连续的，而是一个比例，如投掷一枚硬币是正面的比例，是一个 二值的观测量，也就是取值为0 或1 的随即变量。假定第i 个个体取值为1 的概 率为p ( f ) ，而且不同个体的响应是独立的，这意味着对第i 个个体的响应服从伯 努里分布： p ( y ( i ) = y ( f ) ) = p ( f ) y ( o ( 1 一p ( f ) ) 1 ( 2 - 1 1 ) 其中_ ) ，( f ) 0 m 。 目标很明显，是建立一个可以预测变量为x 的对象取值为1 时的概率的模型。 线性模型不符合条件，因为可以取小于0 或大于1 的情况，修改模型引入非线性 的特征。一种合适的函数就是l o g i s t i c 连接函数： 似y _ 1 i 砌_ 1 0 9 然 ( 2 - 1 2 ) 由于p 是在0 到1 之间变化的，所以l o g ( p 1 一p ) 是在( 一0 0 ，0 0 ) 中变化，符合 g ( p ) = a j x ) 的潜在范围。 关于l o g i s t i c 模型的应用可以找到很多的例子，例如对8 6 年挑战者号航天飞 机部件的损害概率与温度的关系分析，如果事先分析了所有的飞行数据，则有可 能避免航天飞机失事的厄运。 2 2 3 多项式回归 在基本的线性模型上添加多项式项，多项式回归可以用于建模。通过对变量 进行变换，将非线性模型转换成线性的，虽后用最小二乘法求解。 考虑下式的多项式关系： y = 口+ b x + c x 2 + 蠲3 ( 2 - 1 3 ) 定义新变量x 。= x ，x ：= x2 ，x ，= x 3 ，则可将上式转换为线性方程求解。 中山大学硕士学位论文 2 2 4 人工神经网络 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 是属于高度参数化的统计模型， a n n 理论起源于上世纪5 0 年代，在上世纪8 0 年代以前，受限于专家系统( e x p e r t s y s t e m ) 是当时最流行的人工智能基础，以及a n n 理论不成熟，故未受到广泛重 视。一直到上世纪8 0 年代之后，h o p f i e l d 提出神经网络理论，再加上专家系统 发展遇到瓶颈，a n n 理论才逐渐受到重视。有关a n n 的新架构及新理论，至今仍 不断被学者提出并加以完备，应用层面也随之扩展而更为广泛。 a n n 的主要组成部分是人工神经元，人工神经元的主要运算类似于前述的广 义线性模型，先对预报变量进行线性组合，然后对组合结果做非线性变换，由此 构成一个基本的神经元，如图2 4 所示。 图2 4 人工神经元结构 若干个这样的神经元构成一个层，多个层之问再相互连接构成网络。对于在 输入变量x 和输出变量y 之间仅有一个隐藏层的网络来说，可以用下式表示 炉莩丘【y k 0 q 1 4 ) a n n 有一个输入层，多个隐藏层，一个输出层。一个层的输出线性组合的转 换结果作为下一层的输入。输入层神经元的数目与输入变量的个数有关，隐藏层 数量的多寡，会随着分析复杂程度及输入变量的差异而有不同，输出层负责结果 表示。根据数据的流动方向，a n n 又可以分为“前向式”和“回馈式”两种。 a n n 的最初形式是使用阈值l o g i s t i c 单元作为非线性变换：如果输入的加权 和小于某个阈值那么输出为0 ，否则为i 。应用中两种常用的形式是对加权和进行 中山大学硕士学位论文 l o g i s t i c 变换，o ) = e 。1 + e 和正切双曲线f ( x ) = t a n h ( x ) 变换。 a n n 的预测过程就是不断的通过训练样本学习，调节连结权重的过程，学习 结果的好坏取决于预测变量输出结果与目标值的差异，当两者的误差变化很小 时，a n n