（计算数学专业论文）数据挖掘在时间序列分析中的研究和应用.pdf

成都理工大学硕士学位论文 数据挖掘在时间序列分析中的研究和应用 作者简介：胡隽，男，1 9 8 1 年1 月出生于四川省成都市，1 9 9 9 年7 月毕业 于成都第二十中学。同年进入成都理工大学信息工程专业学习，于2 0 0 3 年7 月 毕业，2 0 0 4 年9 月考入成都理工大学计算数学研究生，主要研究方向为金融、 统计数学和数学建模，于2 0 0 7 年7 月毕业，获得硕士学位。 摘要 数据挖掘技术作为近年来迅速发展的时间序列分析方法之一，得到了越来越 多的科学工作者的关注和研究。如何对海量的时间序列数据进行有效的知识发 现，挖掘其内在的各种变化模式、并进行相似性搜索、关联规则发现等应用分析， 已经成为了一个挑战性的、具有重要意义的理论和实际应用课题。 本文在分析时间序列特点和实际应用需求的基础上，针对时间序列挖掘的相 似性查找和决策树生成模型进行了研究，具体所做的工作和创新成果体现在以下 三个方面： 1 ) 深入、系统的进行基础理论学习与分析。 本文在许多章节都安排了介绍性的基础理论，包括数据挖掘、时间序列、决 策树方法和微粒群算法，并对它们进行了深入、系统的学习和分析，为后面的研 究和创新工作做好铺垫。 2 ) 时间序列相似性搜索的研究 本文在第三章首先给出了用回归系数对时间序列进行维约简的方法，该方法 利用时间序列的趋势性对原序列进行了简化，然后研究了用相关性分析来进行相 似性搜索的可行性，最后进行了实证研究，实验结果表明用该方法对时间序列的 趋势性进行相似性搜索具有很高的实际意义。 3 ) 用微粒群算法改进生成决策树的模型研究 本文在第四章提出了一种新型的用微粒群算法改进生成决策树的模型。该模 型传承了经典的c 4 5 算法中使用信息增益率作为生成决策树的思想，结合改进 的微粒群优化算法，将信息增益率、建树错误率整合在了一起，最后的实验结果 说明本模型比较原有的c 4 5 算法在建树速度和精度上有一定的优势。 关键词：决策树时间序列微粒群算法c 4 5 算法相关性分析 t h e i n v e s t i g a t i o na n da p p l i c a t i o no fd a t am i n i n g i n t i m es e r i e s a b s t r a c t d a t am i n i n gh a sb e e nc o n s i d e r e da sai m p o r t a n tm e t h o d si nt h ea n a l y s i so ft i m e s e r i e s ，r e c e i v e dm o r ea n dm o r ea t t e n t i o na n dr e s e a r c hc a m ef r o ms c i e n t i s t s i ti s n e c e s s a r ya n dc h a l l e n g i n gs u b j e c tt or e s e a r c hh o wd i s c o v e r yv a l u a b l ek n o w l e d g ei n l a r g e s c a l et i m es e r i e sd a t a b a s e a n dh o w t os e a r c hb a s e d s i m i l a r i t yw h i l eu s e rg i v ea g r a p h i cq u e r yp a t t e r n t h i sp a p e rh a si n v e s t i g a t et h es i m i l a r i t yo ft i m es e r i e sa n d * - h em o d e l i n go f c o n s t r u c tad e c i s i o nt r e e ，w h i c hi sb a s e do nt h ea n a l y s i so fc h a r 孤t e r i s t i ca n d p r a c t i c a l l ya p p l i e dr e q u i r e m e n to f t i m es e r i e s t h em a i nw o r ka n di n n o v a t i o n sa r ea s f o l l o w s ： 1 ) d e e p l ya n dw i d e l ya n a l y s i so f ft h eb a s i ct h e o r y t h i sp a p e rh a sa r r a n g e dc o u p l e so fb a s i ct h e o r yi nm a n yc h a p t e r s ，i n c l u d ed a t a m i n i n g , t i m es e r i e s ，d e c i s i o n f l e ea n dp s oa l g o r i t h m ，a n di th a sd e e p l ya n dw i d e l y a n a l y s i so nt h o s eb a s i ct h e o r yw h i c h i san i o ei n t r o d u c t i o nf o rt h el a t e rc h a p t e r s 2 ) i n v e s t i g a t i o na b o u tt h es i m i l a r i t ys e a r c ho f t i m es e r i e s t h et h i r dp a r to ft h i sa r t i c l eh a sp r o p o s e dam e t h o df o rd i m e n s i o nr e d u c t i o na n d s i m i l a r i t ys e a r c hb a s e do nr e g r e s s i o nc o e f f i c i e n tw h i c hh a ss i m p l i f i e dt h eo r i g i n a l s e r i e si nu t i l i z i n gt h e f i e n do ft i m es e r i e s t h e ni th a sr e s e a r c h e dt h ef e a s i b i l i t yo f s i m i l a r i t ys e a r c hw h e nu s i n gc o r r e l a t ea n a l y s i s a n dh a sg i v e nae m p i r i c a lr e s e a r c hi n t h ee n dw h o s ec o n c l u s i o ns h o w st h e r ei sah i g h l yp r a c t i c a lm e a n i n go ft h ea b o v e w o r k 3 ) t h em o d e l i n go f c o n s t r u c tad e c i s i o n f l e eu s i n ga d v a n c e dp s oa l g o r i t h m t h ef o u r t hp a s to ft h i sa r t i c l eh a sp r o p o s e dan e wm o d e lo fc o n s t r u c tad e c i s i o n t r e e u s i n ga d v a n c e dp s oa l g o r i t h m t h em o d e l h a sf u s e dt h ei n f o r m a t i o n a u g m e n t a t i o nr a t i ou s e di nc 4 5a l g o r i t h ma n da d v a n c e dp s oa l g o r i t h mt ob u i l da d e c i s i o nt r e e t h ef i n a le x p e r i m e n td e c i s i o ni l l u m i n a t et h em o d e lh a ss o m e a d v a n t a g e so i lt h es p e e da n da c c u r a c yo fd e c i s i o nt r e ec o n s t r u c t i o nw h e nc o m p a r e w i t hc 4 5a l g o r i t h m k e yw o r d s ：d e c i s i o nf l e e 墙m es e r i e s c 4 5a l g o r i t h mp s oa l g o r i t h m c o r r e l a t i o na n a l y s i s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得瘗整理王太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意。 签名：碰奠嘲焦 2 7 年亭月j 矿 日 学位论文版权使用授权书 本学位论文作者完全了解盛叠堡王盘堂有关保留，使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盛嫠堡兰盔堂可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位淦文。 ( 保密的学位论文在解密后适用本授权书) 签名：吲德 工向年r 月霸日 第一章引言 第一章引言 在本章，我们首先从数据挖掘技术的起源和时间序列的实例分析了本课题的 研究背景和意义，然后综述了国内外相关研究现状，从中产生新的思路，进而提 出本文的研究和创新内容并给出了论文结构。 1 1 课题的研究背景和意义 早在1 9 8 2 年，趋势大师约翰奈斯比( j o h nn a i s b i t t ) 在他的首部著作大趋 势中就提到：“人类正被信息淹没，却饥渴于知识。”计算机硬件技术的稳定 进步为人类提供了大量的数据收集设备和存储介质；数据库技术的成熟和普及已 使人类积累的数据量正在以指数方式增长；i n t e m e t 技术的出现和发展已将整个 世界连接成一个地球村，人们可以穿越时空般地在网上交换信息和协同工作。在 这个信息爆炸的时代，面对着浩瀚无垠的信息海洋，人们呼唤着一个去粗取精、 去伪存真的能将浩如烟海的数据转换成知识的技术。可惜目前数据库系统所能做 到的只是对数据库中已有的数掘进行存取，无法发现数据背后隐藏的知识，导致 了“数据爆炸但知识贫乏”的现象。 在这种情况下，k d d ( 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 ) 帮d m ( d a t am i n i n g ) 技术i l 】应运而生。1 9 8 9 年1 月在美国底特律召开的第1 1 届国际人工智能联合会 议的专题讨论会上首次出现k d d 这个术语，并立刻引起了人们的兴趣。数据 挖掘方法的提出，让人们有能力晟终认识数据的真正价值，即蕴藏在数据中的信 息和知识，k d d 和d m 技术是目前国际上数据库和信息决策领域的最前沿研 究方向之一，引起了各界的广泛关注。例如美国政府开发s e q u o i a 2 0 0 0 项目作 为大规模数据库中先进的数据分析工具：国际上一些高级剐的工业研究实验室， 例如i b m a l m a d e n 和g t e 等众多的学术单位都在这个领域开展了各种各样 的研究，并且有许多软件公司开发了他们的数据挖掘软件产品；许多商业公司也 充分认识到了深层次地分析本公司业务数据库中的数据能够带来更多的商业机 会，例如银行和零售商店通过分析他们的业务数据，进一步掌握和了解顾客的信 誉、习惯和消费心理，相应地调整他们的市场策略，以拓宽更广泛的市场。在十 几年间，k d d 和d m 技术得以蓬勃发展，并越来越显示出其强大的生命力和广 阔的发展前景。 时间序列数据是一种非常广泛也非常重要的数据，它存在于社会的各个领 域，如科学研究记录：包括天文观测，气象图像等；金融和商业交易记录：如股 市每天的交易价格及交易量，超级市场每种商品的销售情况等：病历记录：包括 成都理工大学硕士学位论文 病人的每次看病的病情记录以及心电圈等扫描仪器的数据记录等。时问序列几乎 无处不在。随着科学技术的不断发展，计算机以及存储设备的存储容量日益增大， 时间序列数据库也越来越大，对其挖掘分析研究引起国内外很多学者的兴趣和注 意，目前己成为数据挖掘研究的一个重要分支和研究热点，其果已应用于金融、 生物医学、天文、气象等领域。 时间序列数据挖掘口j ( t i m es e r i e sd a t am i n i n g ，简称t s d m ) 是数据挖掘的 主要内容，统计中的时问序列分析 3 1 方法直接应用于数据挖掘存在一定的问题， 因为d m 技术要求最终用户只需要很少的训练就能掌握1 4 j ，同时d m 方法相对 于以模型为主的统计学而言，准则起着更为核心的作崩”j ，因为数据挖掘所继承 的学科如计算机科学及相关学科也是如此。数据挖掘的本质是实验性的，主要目 的是发现，它和确定性的统计分析有所差别，因此对时间序列模型过严的假定和 繁杂的分析自然就制约了数据挖掘的效率，以至这方面至今没有很好的解决方 案，在证券数据的研究中尤为困难，因为结果只能更好，不会有最好l 再加上金 融数据挖掘的适时性和快速反应要求和必须研究和防范的金融风险，都是我们无 法回避的问题。 本文主要将数据挖掘的思想和方法引入时间序列分析中，围绕数理统计方法 与挖掘技术的结合、时间序列维约简、用相关性分析进行相似性查找、用改进的 p s o 算法建立决策树等重点问题展开研究。 1 2 国内外研究现状综述 时间序列分析是统计学研究的一个重要分支。它直接以事物在不同时刻的状 态所形成的数据为研究对象，通过对时间序列数据的特征进行分析和研究，揭示 事物的发展变化规律。经典的时间序列分析方法有图表法、指标法和模型法。其 中模型法是目前对时间序列进行深层次分析和刻画的主要方法，一些经典的时 问序列分析模型如a r m a 、a r c h 和g a r c h 等已被广泛应用于自然和社会科 学领域。如美国经济学家e n g i c 就因其1 9 8 2 年针对金融时间序列所提出的 a r c h 模型而荣获2 0 0 3 年度诺贝尔经济学奖。 时间序列的数据挖掘技术早在e 个世纪9 0 年代已经有人提出，主要是对时 自j 序列的相似性搜索，此后在此基础上又出现了时间序列数据库中子序列匹配的 和整体匹配的研究。在这些相似性计算过程中都存在时间序列数据量过大的问 题，这将引起搜索效率的大大降低。因此时间序列的有教描述将是提高搜索效率 _ 6 - 9 1 的方法之一，由p a v l i d i s 1 0 1 最早提出分段线性化描述是用直线段来近似拟合原 始时间序列的形状，这样用直线段来代替原始数据将大大减少了数据量，此后 第一章引言 k e o g h 又作了进一步的研究，但是在文献中提到的分段线性化方法计算量较大， 需要多次迭代，这一缺点在数据量大时尤为明显，而且其中采用的相似性测量方 法对于时问轴按比例缩放的情况是敏感的，然而这一现象在实际时间序列中是经 常出现的，因此解决这一问题也是相当重要的。 在相似性的基础上，人们又发展出了许多模式识别的方法，如通过相似性计 算对时间序列进行分类【1 2 j 、聚类等。关于时问序列的数据挖掘技术除了相似性的 研究外，还有其他的一些更接近于人类思维方式的研究方法即模式挖掘方法，如 关联规则的抽取i l ”，可以得到形如“如果某一天m i c r o s o f t 上涨而且i m e l 下降， 则i b m 第二天上涨”的规则，而文献【1 4 】提出可以从时间序列中抽取分类规则， 但是这种方法有一个前提条件，即是必须对时l 、日j 序列进行预处理，从中预先抽取 静态模式，然后从模式中提取对时间序列影响较大的特征属性，对时间序列进行 趋势预测。这种分类规则的提取对于科学观测数据的分析以及金融经济的预测将 会提供有效的帮助。但是文献1 1 4 j 中采用的规则挖掘方法得到的预测精度比较低， 有待于研究更有效的、泛化能力更强的分类规则挖掘方法。我国的张保稳i l ”基于 t a k e n s 理论，提出了一种面向单一时序状态演化模式挖掘的框架。 相对于数摒挖搁较成熟的部分而言( 如关系数据库中关联规则和分类规则的 挖掘等) ，时间序列数据挖掘的研究是数据挖掘研究领域中的较新的一个分支， 目前国际上对于时间序列的数据挖掘的研究逐步成为一个新的热点，但国内在这 方面的研究文献尚不多见，比较重要的工作有1 9 9 8 年欧阳为民等曾经从理论框 架的角度对时态数据挖掘做过介绍和分析。 s a s 研究所认为数据挖掘足对数据进行选择，探索，调整和建模来揭示数据 中未知的模式，开发了图形界面的s a s e m 来进行数据挖掘： 1 、s a m p l e 抽样；从大量的数据中抽取与探索问题有关的数据子集， 这个样本应该包含足够的信息，又易于处理。 2 、e x p l o r e 探索：对数据子集进行探索，寻找出与期望的关系和未 知的模式。 3 、m o d i f y 调整：对数据进行探索后，有了初步的了解，就必须对数 据进行增减，选择，转化，量化保证有效进行。 4 、m o d e l 建模：应用分析工具，建立模型，进行预测。 5 、a s s e s s 评价：评价数据挖掘结果的有效性和可靠性。 s p s s 公司提出了5 a 的模型，进行数据挖掘，认为任何数据挖掘方法学都 由5 个基本元素组成： 1 、a s s e s s 正确、彻底的了解业务需求及数据 2 、a c c e s s 获取数据，做适当的调整 成都理工大学硕士学位论文 3 、a n a l y z e 选择适当的分析、验证方法和工具 4 、a c t 推荐性、有说服力的原型演示 5 、a u t o m a t e 提供优秀的自动化软件， 综上所述，国内外已经有不少的专家、学者开始从事于时间序列的数据挖掘 的研究，但是这项技术仍处于起步阶段，需要注入更多的新思路和方法对其进行 更深入的研究。据挖掘。最近，g a r t n e rg r o u p 的一次高级技术调查将数据挖掘和 人工智能列为“未来三到五年内将对工业产生深远影响的五大关键技术”之首， 并且还将并行处理体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前 两位。根据最近g a r t n e r 的h p c 研究表明，“随着数据捕获，传输和存储技术的 快速发展，大型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用 更为广阔的并行处理系统来创建新的商业增长点。” 1 3 本文的主要研究内容 通过对时间序列数据挖掘重要性的充分认识和对基础知识的认真学习，以及 对目前已有研究成果的仔细研究，本文着重从以下两个方面进行研究： 1 、结合数据挖掘思想和数理统计方法对时间序列进行相似性搜索研究 我们知道，传统的数理统汁分析方法与模型大多基于严格的统计数学和相关 的金融分析，并且已被广泛使用多年，因此在金融时间序列分析中发挥着不可替 代的作用。数据挖掘技术则为在海量的金融数据中快速、自动、智能化的发现备 种潜在的、有价值的规律提供了新的思路。我们认为这两种方法的结合将使得金 融时间序列分析领域与有更加广阔的前景。基于上述分析，本文总结出了1 种将 数理统计方法结合数据挖掘技术应用到金融时问序列分析的思路，进行研究：首 先用线性回归系数对时间序列进行维约简，然后采用相关性分析构造变量对维约 简后的时日j 序列进行相似性搜索研究。 2 、提出了一种将改进的p s o 算法与决策树c 4 5 算法相结合的模型 决策树是数据挖掘技术中应用最为广泛的方法之一，如何快速建立简单可靠 的决策树是个重要的问题。本文在4 2 2 节引入p s o 算法，并针对标准p s o 算 法易限于局部极小点的局限性的缺点，在保持p s o 算法结构简单可行特点的基 础上，引入惩罚函数和叉乘控制项，得到改进后的p s o 算法，再将改进的p s o 算 法引入到决策树建树方法中，产生新的建立决策树的算法，得到新的将改进p s o 算法与决策树相结合的模型，并与传统的决策树方法进行比较，验证其优越性。 第一章引言 1 4 论文的结构 本文采用理论研究与实证分析相结合的方法，利用数据挖掘技术、统计学、 微粒群算法、时间序列分析方法的相关理论，对数据挖掘技术在金融时间序列中 的应用问题提出了富有新意的解决办法，通过对国内外研究现状的了解和综合分 析，力求从他人的研究成果中得到启发、发现不足，从而得出有独特见树的方法 和模型。 本文共分为5 章，具体内容如下： 第一章引言 本章介绍了论文的研究背景和意义，分析了相关的国内外研究现状，从中受 到启发，阐明了本文的研究内容和结构框架。 第二章数据挖掘的基本理论 本章从以下几个方面介绍了数据挖掘的基础知识；数据挖掘的定义，分类、 方法、作用、实施步骤和决策树算法。 第三章数理统计方法在时间序列挖掘中的应用 本章首先给出了时间序列的基本概念和传统分析和挖掘方法，然后提出了结 合数理统计方法与数据挖掘技术进行时间序列挖掘的方法，最后进行实证研究以 验证其合理性。 第四章基于改进的p s o 算法快速生成决策树的模型研究 本章首先介绍了标准p s o 算法和改进的p s o 算法，然后进行用改进p s o 算法 结合c 4 5 算法生成决策树的模型研究，最后进行了实验验证。 第五章结论 本章全面总结了论文的总体结构与创新点，并提出了许多需要改进的地方和 值得今后深入研究的方向。 1 5 本章小结 本章阐述了论文课题的研究背景和研究意义，然后分析和研究了国内外相关 课题的研究现状，最后逐章对全文的内容和结构进行了总体介绍。 成都理工丈学硕士学位论文 第二章数据挖掘的基本理论 通常，我们把从庞大的数据集或数据库中提炼有用信息的科学称为数据挖 掘。它汇集了统计学、机器学习、模式识别、人工智能等学科的内容，是一门新 兴的交叉学科。这些学科都致力于数据分析的某一个方面，因此它们存在很多共 性但是每一学科又有其独有的特色，分别针对不同的问题和求解不同方式。 本章介绍数据挖掘的一些基本理论，包括它的定义、分类、方法、作用和 实施步骤，最后重点介绍了决策树方法的基本知识。 2 1 数据挖掘的定义和分类 数据挖掘的历史虽然较短，但从2 0 世纪9 0 年代咀来，它的发展速度很快， 加之它是多学科综合的产物，目前还没有一个完整的定义，人们提出了多种数据 挖掘的定义，如： s a s 研究所( 1 9 9 7 ) ：“在大量相关数据基础之上进行数据探索和建立相关模型 的先进方法”。 b h a v a n i ( 1 9 9 9 ) ：“使用模式识别技术、统计和数学技术，在大量的数据中发现 有意义的新关系、模式和趋势的过程”。 h a n d e t a l ( 2 0 0 0 ) ：“数据挖掘就是在大型数据库中寻找有意义、有价值信息 的过程0 总之，数据挖掘是指从大量的、不完全的、有噪声的，模糊的、随机的实际 应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程。这些信息和知识可表示为概念、规则、规律、模式等形式。数据挖 掘是帮助发现隐藏在数据中知识的有力工具，它通过选择数据，对数据进行检测， 建立挖掘分析模型，挖掘出深层次的信息和知识。其中挖掘模型或挖掘算法是关 键。 2 2 数据挖掘的方法和作用 2 2 1 数据挖掘的方法 l 、传统统计方法：( 1 ) 抽样技术：我们面对的是大量的数据，对所有的数据进 行分析是不可能的也是没有必耍的，就要在理论的指导下进行合理的抽样。( 2 ) 多元统计分析：因子分析，聚类分析等。( 3 ) 统计预测方法，如回归分析，时间 謦融分析等。 6 第二章数据挖掘的年：本理论 2 、决策树方法。利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信息 量的字段，建立决策树的一个结点，再根据字段的不同取值建立树的分支；在每个 分支子集中重复建立树的下层结点和分支的过程，即可建立决策树。国际上最有 影响和最早的决策树算法是q u i u l a n 研制的i d 3 方法，该算法的核心是在决策树各 结点上选择属性，用信息增益率傲为属性选择的标准，使得在每个非叶子结点测 试时，能获得被测试例子最大的类别信息。但是i d 3 存在很多缺陷，本文会给出 1 d 3 算法的改进形式c 4 5 算法并指出其缺陷，最后会提出了一种将改进的p s o 算法 与决策树算法相结合的新算法并进行实证分析其优越性。 3 、神经网络方法。它模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基础，用 神经网络连接的权值表示知识，其学习体现在神经网络权值的逐步计算上。目前 主要有3 大类多种神经网络模型：( 1 ) 前馈式网络。它以感知机、反向传播模型、 函数型网络为代表，可用于预测模式识别等方面。( 2 ) 反馈式网络。它以h o p f i e l d 的离散模型和连续模型为代表。分别用于联想记忆和优化计算。( 3 ) 自组织网络。 它以a r t 模型、k o h o l o n 模型为代表，用于聚类。 4 、遗传算法。这是模拟生物进化过程的算法，由3 个基本算子组成：( 1 ) 繁殖。 是从1 个旧种群( 父代) 选出生命力强的个体，产生新种群( 后代) 的过程。( 2 ) 交 叉( 重组) 。选择2 个不同个体( 染色体) 的部分基囚) 进行交换，形成新个体。( 3 ) 变异( 突变) 。对某些个体的某些基因进行变异( 1 变0 ，0 变1 ) 。这种遗传算法可 以起到产生优良后代的作用。这些后代需满足适应度值羟过若干代的遗传。将得 到满足要求的后代( 简题的解) 。遗传算法己在优化计算和分类机器学习方面显 示了明显的优势。 5 、模糊集方法。利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模 式识别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精确化能力 就越低，目p 模糊性就越强。这是z a d e h 总结出的互克性原理。 6 、可视化技术。可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖 析更清楚。例如，把数据库中的多维数据变成多种图形。这对揭示数据的状况、内 在本质及规律性起了很大作用。 2 2 - 2 数据挖掘的作用 图2 1 说明了数据挖掘的作用 成都理工大学硕士学位论文 数据挖掘 舞赖分丫薯类分y 喜异分y 其它 决策树，关联j 聚类分析数据li 异常检测，变i j 趋势分析，神 规则等 li 善总比较分析ii 化分析等il 霎霎誓。遗传il 等llli 算法等 圈：2 - 1 数据挖掘的作用 1 、依赖分析。典型的依赖知识是具有某种最小支持度与黄信度的项集间的关联 规则，该方法能采掘出客户购买不同的商品之问的行为关系，从而可以帮助促销那 些在消费者心中有某种依赖关系商品。如w a l m a r t 建立的“市场购物篮分析系 统”能分析出客户购买商品的模式及其关系，如它能发现如“腊肠芥末”的关联 规，该规则的含义是购买腊肠的大部分客户同时也购买芥末。依此商场将相关 商品在货檠上合理布置( 如腊肠和芥末在货架上邻近排放) ，使客户很容易发现需 要的商品。促进了商品的销售。 2 、聚类分析。聚类分析包括聚类和类识别。聚类在营销中可用于对客户的分类， 成熟的算法是统计分析中聚类分析算法。其思想是使生成的类内部最大相似。类问 最大差异。实际应用中，将由聚类分析算法得到的分类结果提交给业务行家。业务 行家利用领域知识进行评判后确定基本类型，每个客户属于某一类型。类识别即 某实例( 如客户) 归于已有的某类，可通过与类的距离长短来判别。 3 、差异分析。差异分析侧重于发现异常的变化。在相类似的客户类中，对客户异 常变化要给予密切关注。如信用卡公司一旦发现某客户的信爿j 购买量突然增大， 就要对客户的这种变化的原因进行调查。如果不是由于客户的欺诈行为，而是由 于客户状态的变化，比如客户找到一个薪水更高的职业或由于客户新购置了更大 的住房等，此时需要确认客户的这种变化，更新相应的档案，并提出针对性营销方 案，如主动提供一些如装修类商品或服务。 4 、其它。趋势分析主要用于发现变化的趋势。如根据客户的偏好趋势和商品特 第二章数据挖掘的基本理论 征间的关系，进行商品销售预测。人工神经网络方法和遗传算法是解决非线性的、 非结构化的十分复杂问题的强有力工具。尽管利用它们所得的结论有时难以解释 但它们的实际应用异常有效，是应用极为广泛的机器学习技术。 2 3 数据挖掘的实施步骤 数据挖掘的通用过程，一般由以下步骤组成，图2 - 2 给出了更直观的表达： 1 、数据清理：消除噪音或者不一致的数据。 2 、数据集成：将多种数据源组合在一起。 3 、数据选择：从数据库中检索与分析任务相关的数据。 4 、数据变换：数据变换或统一成适合挖掘的形式。 5 、数据挖掘：利用智能手段提取数据中的特征模式。 6 、模式评估：根据某种兴趣度度量，识别表达知识的有趣模式。 7 、知识表示：从模式中提取用户可以直接采用的知识。 首先将各种数据采集到数据库中，通过数据清理和集成把数据库中这些数据 有用的部分提取出来，然后放到一个大的数据仓库中；在数据仓库中根据挖掘的 目标选择或变换相关的数据集，采用某种挖掘算法对数据集进行挖掘，由挖掘得 出的模式数量一般很大，通过模式评估获得有趣的模式，最后从这些模式中提取 出人们用于决策或者研究的知识。 图2 - 2 数据挖掘的通用过程 成都理工文学硕上学位论文 2 , 4 决策树算法概述 人类认识事物从分类丌始，分类能力是人类智能的基础。在数据挖掘中，分 类的目的是提出一个分类函数或分类模型( 也常称为分类器) ，通过分类模型把 数据库中的数据项映射到给定类别中的某一个。 多年来，围绕分类问题进行了积极的研究并取得了许多成果，主要集中在知 识的模型表示上，如决策树、贝叶斯网络、神经网络、概念格和粗糙集合等。其 中决策树是一种常用的分类模型。与其它分类模型相比在构造决策树的过程中， 不需要除训练数据集之外的任何额外信息，训练速度比较快，生成的决策树的分 类精度比较高，且容易被人理解，因此决策树在实际中得到了广泛的应用。 决策树是一种倒立的树型结构，从一组无次序、无规则的事例中推理出树状 形式表示的分类规则。它采用自顶向下的递归方式，根据一定标准选取属性作为 决策树的内部节点，并根据该属性的不同取值构造不同的分支，在树的叶结点得 到结论，所以从根节点到叶结点的每一条路径就对应一条规则。 图2 - 3 分类步骤 例如，图2 3 是从某银行的借贷业务中得到的决策树。其中圆圈代表非叶 节点，方块代表叶了节点。从图中共可得到三条分类规则：规则l ：年薪低于2 万且学历为本科的同意受理其借贷请求；规则2 ：年薪低于2 万且学历不是本科 的拒绝其借贷请求：规则3 ：年薪超过2 万的同意其借贷请求。 总的来说，决策树的构造是一种自上而下，分而治之的归纳过程，本质上是 一种贪心算法。决策树上的各个分支是在对数据不断分组的过程中逐渐生长出来 的。首先，选择一个属性作为根节点，然后把该属性的每一个可能的值作为子节 点，这样就把整个训练集分成了几个子集，根节点属性的每个取值都对应着一个 子集，然后递归应用到每个子树上进行进一步划分，直到对所有数据的继续分组 o 第一二章数据挖掘的基本理论 不再有意义时，决策树的生长过程宣告结束，此时便生成了一棵完整的决策树。 其中，测试属性的选择是构建决策树的关键环节，不同的决策树算法在此使用的 技术都不尽相同。 2 4 ，1 i d 3 算法 1 、i d 3 基本思想 当前国际上最有影响的示例学习方法首推j r q u i n l a n 的i d 3 ( 1 m e m f i v e d i c e r m i s e r v e r s i o n 3 ) 。它的前身是c l s ( c o n c e p t l c a m i n g s y s t c m ) 。c l s 的工作 过程为，首先找出最有判别力的凼素，然后把数据分成多个子集，每个子集又选 择最有判别力的因素进行划分，一直进行到所有子集仅包含同一类的数据为止。 最后得到一裸决策树，可以用它来对新的样例进行分类。 j r q u i n l a n 的工作主要是引进了信息论中的互信息，他将其称为信息增益 ( i n f o r m a t i o ng a i n ) ，作为特征判别能力的量度，并且将建树的方法嵌在一个迭 代的外壳之中。 在实体世界中，每个实体都是用多个特征来描述。每个特征限于在一个离 散集中屈互斥的值。例如，设实体是某天早晨，分类任务是关于气候的类型，特 征如下： 天气取值为晴，多云，雨 气温取值为冷，适中，热 湿度取值为 高，正常 风取值为 有风，无风 某天早晨的气候描述如下： 天气 多云 气温冷 湿度正常 风 无风 它属于哪类气候呢? 要解决这个问题，需要用某个原则来判定，这个原则来 自于大量的实际例子，从例子中总结出原则，有了原则就可以判定任何一天的气 候了。 每个实体在世界中属于不同的类别，为简单起见，假定仪有两个类别，分别 为p ，n 。在这种两个类别的归纳任务中，p 类和n 类的实体分别称为概念的正 例和反例。将一些己知的正例和反例放在起便得到训练集。 表2 - 1 给出了一个训练集。用i d 3 算法得出一棵正确分类训练集中每个实体 的决策树，如图所示。 成都理工大学i 磺上学位论文 表2 - 1气候训练集 属性 n o 类别 天气气温湿度风 1 晴热高 无风n 2 睛热高 有风n 3 多云热高无风p 4 雨 适中高无风p 5 雨 冷 正常无风 p 6 雨 冷 正常 有风n 7 多云 冷 正常有风p 8晴 适中高无风n 9晴冷正常 无风 p 1 0 雨适中正常 无风 p 1 1 晴适中正常有风p 1 2 多云适中高有风p 1 3 多云热正常无风p 1 4 雨适中 高有风n 决策树叶子为类别名，即p 或者n 。其他结点由实体的特征组成，每个特征 的不同取值对应以分枝。若要对一实体分类，从树根开始进行测试，按特征的取 值分枝向下进入下层结点，对该节点进行测试，过程一直进行到叶结点，实体被 判为属于该叶结点所标记的类别。现用如图所示i d 3 决策树来判别本节开始处的 具体例子，得到该实体的类别为p 类。i d 3 就是要从表的训练集构造出如图所 示的决策树。 实际上，能正确分类训练集的决策树不止一棵。q u i n l a n 的i d 3 算法能得出 结点最少的决策树。 第二章数据挖掘的基本理论 圈2 4m 3 挟燕错 2 i d 3 算法介绍 ( 1 ) 主算法 主算法的具体步骤如下： 从训练集中随机选择一个既含正例又含反例的子集( 称为“窗口”) ； 用“建树算法”对当前窗口形成棵决策树； 对训练集( 窗口除外) 中例子用所得决策树进行类别判定。找出错判的例子： 若存在错判的例子，把它们插入窗口，重复步骤( 2 ) ，否则结束。 主算法中每迭代循环一次，生成的决策树将会不相同。 ( 2 ) 建树算法 建树算法的具体步骤如下： 对当前铡子集合，计算各特征的互信息； 选择互信息最大的特征札； 把在a k 处取值相同的例子归于同一子集，a k 取几个值就得几个子集； 对既含正例又含反例的子集，递归调用建树算法； 若子集仅含正例或反例，对应分枝标上的p 或n ，返回调用处。 2 4 2c 4 5 算法 i d 3 算法在数据挖掘中占有非常重要的地位。但是，在应用中，i d 3 算法存 在不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。 c 4 5 是在i d 3 基础上发展起来的决策树生成算法，由j r q u i n l a n 在1 9 9 3 年提出。 c 4 5 算法克服了i d 3 在应用中存在的不足，主要体现在以下几个方面： 成都理工夫学碗士学位论文 1 ) 用信息增益率来选择属性，它克服了用信息增益选择属性时偏向于选择 取值较多的属性的不足； 2 ) 在树构造过程中或者构造完成之后，进行剪枝； 3 ) 能够对不完整数据进行处理。 i 、构造决策树 设f 是数据集，类别集合为( q ，c 2 ，岛) ，选择一个属性矿把f 分成多个子 集。设矿有互不重台的”个取值f v ，v ：，以) ，则r 被分为一个子集五，疋，l ，这 里r 中的所有实例均为”。 令：i t j 为数据集r 的例子数，l 为v = v ，的例子数，忆l = f r e q ( c , 了1 ) ，为 c ，类的例子数，j c ，d 是r = 一例子中，具有c ，类别的例子数。 则有： 1 ) 类别q 的发生概率：p ( q ) = l c ，i ，吲= f r e q ( c j ，r ) z l r l 2 ) 属性v = v ，的发生概率：p v ，) = l r , m r l 3 ) 属性v = h 的例子中，具有类别c ，的条件概率： p ( c ，h ) = l c ，v | l 阿l q u i l l l a t l 在i d 3 中使用信息增益( g a i n ) 在选择属性，而c 4 5 则采用属性的 信息增益率( g a i nr a t i o ) 来选择属性， ( 1 ) 类别的信息熵 ：一渺吵军铷：c 够 ，i 工l 1 = 一；：! ! ! ! ! 萨- 。s z ( 。：! 生! ! 1 5 ；也) = t n r 。( r ) ( 2 ) 类别条件熵 按照属性v 把集合t 分割，分割后的类别条件熵为： 胛= 一手州手p 眄l v 川0 9 2 即h ) = v l r , 州l v c ：1 1 0 9 ：饼 = 喜罱x i n r 。c f ，= t n r 。c 丁， j 4 第：二辛数据挖掘的基本理论 ( 3 ) 信息增盏( g a i n ) ，即互信息 1 ( c ，v ) = h ( c ) 一h ( c i 矿) = i a f o ( t ) 一i n f o 。口) = g a i n ( v ) ( 4 ) 属性y 的信息熵 。堇詈譬北) i o g z ( p o d ) ) = - 料l o g ：蝌) = s p l i t _ i n f 们 ( 5 ) 信息增益率 9 g a n r a t i o = i ( c ，v ) l h ( v ) = g a i n ( v ) x p l i i i n f o ( v ) c 4 5 对i d 3 改进是用信息增益率来选择属性。理论和实践都已经证明，采 用信息增益率( c 4 ，5 方法) 确实克服了采用信息增益( i d 3 方法) 选择偏向于取 值多的属性的不足。 2 ，决策榭剪枝 由于噪声和随机因素的影响，决策树一般会很复杂。因此需要剪技操作。 ( 1 ) 什么时候剪枝 剪枝操作有两种策略：1 ) 在树生成过程中判断是否还继续扩展决策树。若 停止扩展，则相当于剪去该结点以下的分枝；2 ) 对于生成好的树剪去某些节点 和分枝。c 4 5 采用后者。 剪枝之后的决策树的时结点不再只包含一类实例。结点有一个类分布描述， 即该结点属于某类的概率。 ( 2 ) 基于误差的剪枝 决策树的剪枝通常是用叶结点替代一个或多个子树，然后选择出现概率最高 的类作为该结点的类别。在c 4 5 中，还允许用其中的树枝来代替子树。 如果使用叶结点或者树枝代替原来的子树之后，误差率能够下降，则可以使 用该叶结点或者树枝代替原来的子树。 ( 3 ) 误差率的判断 设一个叶结点覆盖个实例，其中三个为错误的。对于具有信任度c f 的实 例，计算一个2 项分布，“，( ，) ，该2 项分布，即实例的误判概率，那么 个实例判断错误的数目为c l ，( e ，) 。子树的错误数目为所有叶结点的总和。 例如： 成都理工丈学硕士学位论文 圈2 - 5剪枝简单示例 注：“( ) ”中为覆盖的实例数目 设c f = o 2 5 ，则： 该子树的实例判断错误数目为： 6 x ( o ，6 ) + 9 x u o2 5 ( 0 9 ) + l u l 2 5 ( 0 ，1 ) = 6 0 2 6 2 + 9 x 0 1 4 3 + 1 x 07 5 0 = 3 2 7 3 若以一个叶结点c 】代替该子树，则1 6 个子例中有一个错误( 6 3 ) ，误判实 例数目为： 1 6 u o i 5 ( 1 , 1 6 ) = 1 6 x 0 1 5 7 = 2 5 1 2 由于判断错误数目小于上述子树，则以该叶结点代替子树。 2 5 本章小结 本章主要介绍了数据挖掘的基本理论，重点介绍对象是决策树方法的i d 3 算法和c 4 5 算法。我们知道c 4 5 是i d 3 的改进算法，它在建立决羡树时使用的 分类指标是信息增益率而非信息增益，本文最后将提出一种新的适用微粒群算法 结合c 4 5 的核，f i , 信息增益率，建立一个新的生成决策树的模型，所以本章 内容为后面的模型建立起到了很好的铺垫作用。 6 第三章数理统计方法在时间序列挖抛中的应用 第三章数理统计方法在时间序列挖掘中的应用 当面对海量的时间序列数据时，许多经典的传统统计方法和挖掘方法也显得 黯淡无光，但是我们可以观察到时间序列具有一个非常重要的特性趋势变动 性，根据这个特性对原始数据