（计算机软件与理论专业论文）时间序列数据挖掘及应用研究.pdf

中国科学技术大学博士学位论文 时间序列数据挖掘及应用研究 摘要 数据挖掘( d a t am i n i n g ，d m ) 和数据库中知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e k d d ) 是当今人工智能和数据库等研究领域中活跃的具有广阔应用 前景的研究方向。它涉及到人工智能、统计学、机器学习、数据库等多个领域。 时间序列数据挖掘是数据挖掘研究中的重要方向之一，它的研究包括时间序 列相似搜索、聚类、分类、关联分析、事件检测、离群值发现、预测等。 时间序列是复杂类型的数据。它往往具有高维性、含有噪声、以及存在诸如 平移、幅度伸缩、时间轴上的伸缩和线性漂移等多种变形。这些是时间序列数据 挖掘工作的困难因素。本文讨论基于小波分析的时间序列数据挖掘的有关问题， 特别地详细研究了时间序列相似度量和相似搜索算法。主要从三方面开展了研究 工作。第一方面，利用小波独有的多分辨分析能力，提取序列的特征，并用这些 特征表示时间序列，然后在特征上进行相似搜索。第二方面，利用小波变换的模 极大值从时间序列中检测异常事件。第三方面，可视化技术可加强数据挖掘的过 程，小波分析和可视化技术的结合，可以有效支持时间序列数据挖掘的整个过程。 本文共分四大部分。 第一、二章是第一部分。这部分先综述了k d d 和数据挖掘有关问题 包括它 们的过程、任务、方法和应用等，然后详细讨论了时间序列数据挖掘技术，包括 时间序列相似度量、检索技术、索引技术和子序列匹配，最后介绍了小波分析的 基本理论，包括富里叶变换、短时富里叶变换、连续小波变换、离散小波变换、 二进小波变换和多分辨分析。 第二部分包括第三章到第六章。提出几个基于小波分析的时间序列数据挖掘 技术。讨论了时间序列维数约简算法和基于欧氏距离的相似标准；提出一个基于 编辑距离和小波变换的多分辨多层次的时间序列相似搜索算法；提出一个新的 相似度量模型，这个模型把时间序列的极值点作为关键点和序列的特征，用它们 来逼近表示原始序列，将极值点序列转换为二叉树，如果两个序列的二叉树是一 致的则称它们是相似的，并给出一个基于这模型的多分辨聚类和相似搜索算法； 研究了基于小波变换模极大值的时间序列异常事件检测方法。 第七章是第三部分。我们讨论数据的可视化和可视化数据挖掘技术。提出一 个基于小波分析的时间序列可视化挖掘模型v i s t s m i n e r 。该模型由5 部分组成： 原始数据的可视化、可视化预处理、可视化约简，可视化模式发现和结果模式可 视化。该模型应用小波实现数据的多层次可视化表示、数据约简和多尺度模式发 现。它可以帮助用户观察高维数据，理解中间结果和解释发现的模式。 最后一部分，即第八章，对全文进行总结，并提出进一步的工作。在理论方 面，将用提升方法和支持向量机等理论研究时间序列数据挖掘技术，在实践方面， 中辫科学技术大学撼士学位论文 对超穿列数据挖搬及应雳研究 将实现基予小波分援敬酎阙序列霹援化挖掇模型v i s - t s m i n e r 。 本文的创新之触如下： ( 1 ) 剥矮小波变换的多分辨性壤，以编辑鼹裹戈度量标准，提出一秘多分辨多 层次的时间序列相似模式搜索算法。它可以在多个尺度上搜索相似模式，支持 平移、幅度 串缩。 ( 2 ) 提戡一秘叛毂樱 娃度燕方法，它支持琴移、堰度l 孛绩秘时闯辘上傍缭；菸 给出一个多分辨的时间序列聚类算法和相似发现算法。 ( 3 ) 采用小波变换模极大值对时间序捌迸行多尺度奇髯事件检测。 ( 4 ) 提爨基予小波分辑数时闽謦列援化数据挖掘模型，支持太燕数据瓣多分 辨的数据可视化、挖掘过稷的可视化、结果模式的可视化。 关键词：数据挖掘知识发现时间序列厂l 稿卸飞小波分析髯常事舻、 检测 h 中国科学技术大学博士学位论文时间序列数据挖掘及应用研究 a b s t r a c t n o w a d a y s ，d a t am i n i n g ( d m ) a n dk n o w l e d g ed i s c o v e r y i nd a t a b a s e ( k d d ) a r et w oo f t h em o s ta c t i v ed i r e c t i o n s i ns o m ef i e l d ss u c ha sa r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s ea n dw i l lb e u s e dw i d e l yi nt h en e a rf u t u r e t h e ya r ea l s ot h eo v e r l a p p i n gp a n so f s o m er e s e a r c hf i e l d ss u c ha s a r t i f i c i a li n t e l l i g e n c e ，s t a t i s t i c s ，m a c h i n el e a r n i n ga n dd a t a b a s e t i m es e r i e sd a t am i n i n 9 1 ( t s d - a 3i s o n eo fi m p o r t a n td a t am i n i n gr e s e a r c h i t st o p i c s i n c l u d et i m es e r i e ss i m i l a r i t ys e a r c h ，c l u s t e r i n g ，c l a s s i f i c a t i o n ，a s s o c i a t i o n ，e v e n td e t e c t i o n ，o u t l i e r d i s c o v e r y , p r e d i c t i o ne t c t i m es e r i e sa r e c o m p l e xt y p e so fd a t a t h e yo f t e nh a v eh i 【g hd i m e n s i o n a l i t y , n o i s ea n d v a r i o u sd i s t o r t i o n ss u c ha so f f s e tt r a n s l a t i o n ，a m p l i t u d es c a l i n g ，s t r e t c h i n go rc o m p r e s s i n gi nt h e t i m e a x i s ，l i n e a rd r i f ta n d d i s c o n t i n u i t i e s t h e s ea r ed i f f i c u l tf a c t o r sf o rd a t am i n i n go i lt i m e s e r i e s i nt h i s d i s s e r t a t i o n ，p r o b l e m s r e l a t e dt ot s d mb a s e do nw a v e l e ta n a l y s i s ，e s p e c i a l l y t i m es e r i e ss i m i l a r i t ym e a s u r ea n ds i m i l a r i t y s e a r c ha l g o r i t h m s ，a r es t u d i e di nd e t a i l r e s e a r c h i sc o n d u c t e di nt h r e ea s p e e m f i r s t , b yu s i n gt h em u l t i r e s o l u t i o np r o p e r t yo fd i s c r e t ew a v e l e t t r a n s f o r m ，t h ef e a t u r e so f t i m es e r i e sa r ee x t r a c t e df r o mr a w d a t aa n d t h e yr e p r s e n tt h es h a p eo f t h et i m es e r i e s s i m i l a r i t y s e a r c hp e r f o r m sb a s e do nt h e s ef e a t u r e s s e c o n d ，b yu s i n gw a v e l e t t r a n s f o r mm o d u l u sm a x i m a ，t h e a b e r r a n te v e n t sa r ed e t e c t e df r o mt i m e s e r i e s t h i r d ， v i s u a l i z a t i o nt e c h n i q u e s c a ne n h a n c et h ep r o c e s s e so fd a t am i n i n g v i s u a l i z a t i o nt e c h n i q u e s c o m b i n e dw i t hw a v e l e ta n a l y s i s c a ns u p p o r tt h ew h o l e p r o c e s so f t s d me f f e c t i v e l y t h e r ea r ef o u r p a r t si nt h i sd i s s e r t a t i o n c h a p t e r1 & 2 a r et h ef i r s tp a r t a tt h e b e g i n n i n go f t h i sp a r t ，a ni n t r o d u c t i o ni sg i v e nt o k d da n dd a t am i n i n g i n c l u d i n gt h e i rp r o c e s s e s ，t a s k s ，m e t h o d sa n da p p l i c a t i o n s t h e n t i m e s e r i e sd a t am i n i n gt e c h n i q u e s ，i n c l u d i n gs i m i l a r i t ym e a s u r e ，r e t r i e v a lt e c h n i q u e s ，i n d e xt e c h n i q u e s a n ds u b s e q u e n c em a t c h i n g ，a r ed i s c u s s e di nd e t a i l f i n a l l yt h e f u n d a m e n t a l t h e o r yo f w a v e l e t s a n a l y s i s i si n t r o d u c e d i n c l u d i n g f o u r i e r t r a n s f o r m a t i o n ， s h o r t - t i m ef o u r i e r t r a n s f o r m a t i o n ，c o n t i n u o u sw a v e l e tt r a n s f o r m a t i o n ，d i s c r e t ew a v e l e tt r a n s f o r m ，d y a d i cw a v e l e t t r a n s f o r ma n dm u l t i r e s o l u t i o na n a l y s i s c h a p t e r3t h r o u g hc h a p t e r6a r et h e s e c o n dp a r t s o m et s d m t e c h n i q u e s b a s e do n w a v e l e t s a n a l y s i s a r e p r o p o s e d f i r s t ，t i m e s e r i e s d i m e n s i o n a l i t y r e d u c t i o nm e t h o d s b y w a v e l e ta n ds i m i l a r i t ym e a s u r em e t h o db a s e do ne u c l i dd i s t a n c ea r ed i s c u s s e d s e c o n d ，a m u l t i - r e s o l u t i o na n dm u l t i - l e v e lt i m es e r i e s s i m i l a r i t y s e a r c h t e c h n i q u e b a s e do nw a v e l e t t r a n s f o r m a t i o n sa n de d i td i s t a n c ei s p r o p o s e d t h i r d ，an o v e ls i m i l a r i t y m e a s u r em o d e li s p r e s e n t e d i n t h em o d e l ，t i m es e r i e se x t r e m u mp o i n t sa r ec o n s i d e r e da sc r i t i c a l p o i n t sa n d f e a t u r e so ft h es e q u e n c e t h e s ep o i n t sa r et h e a p p r o x i m a t i o nr e p r e s e n t a t i o no f r a wd a t a i i i 串蘅科擎按术大学博士学位论文时间序列数据挖掘艇应用研究 t h e y c a l lb et r a n s f o r m e di n t oab i n a r yt r e e ，t w ot i m es e r i e sa r es i m i l a ri f t h et w ob i n a r yt r e e s ， w h i c hr e s u l tf r o mt h e mb yt h i sm e t h o d ，a r ei d e n t i c a l 。m u l t i r e s o l u t i o nc l u s t e r i n ga n ds i m i l a r i t y s e a r c ht e n i q u ea r ea l s op r e s e n t e db a s e do nt h em o d e l 。f i n a l l yt h em e t h o do fa b e r r a n te v e n t d e t e c t i o nb a s e do nw a v e l e tt r a n s f o i t f lm o d u l u sm a x i m aa r es t u d i e d c h a p t e r 7i st h et h i r dp a r t d a t av i s u a l i z a t i o na n dv i s u a ld a t am i n g t e c h n i q u ea r ed i s c u s s e d a m o d e lv i s - t s m i n e rb a s e do nw a v e l e t a n a l y s i sf o r v i s u a ld a t am i n i n go nt i m es e r i e si s p r o p o s e d t h em o d e l c o n s i s t so ff i v e c o m p o n e n t s ：o r i g i n a l d a t av i s u a l i z a t i o n ，v i s a u ld a t a p r e p r o c e s s ，v i s u a l d a t a r e d u c t i o n ，v i s u a lp a a e md i s c o v e r y a n d p a r e r n v i s u a l i z a t i o n b y w a v e l e t st h em o d e l p e r f o r m s h i e r a r c h i c a l r e p r e s e n t a t i o n o ft i m es e r i e sd a t a s e tf o r v i s u a l i z a t i o n ，d a t ar e d u c t i o na n d m u l t i - s c a l ep a t l e m d i s c o v e r y t h i s m o d e lc a nh e l pu s e r s v i e wt h e h i g h d i m e n s i o n a ld a t a ，u n s t a n dt h ei n t e r m e d i a t er e s u l t s ，a n d i n t e r p r e t t h e d i s c o v e r e dp a t t e r n s c h a p t e r8i s t h el a s t p a r t s u m m a r y o nt h i sw h o l et e x ti sm a d ea n ds o m e p o i n t sf o r f u t u r ew o r ka 特s u g g e s t e d 。t h e o r e t i c a l l yt i m es e r i e sd a t am i n i n g t e c h n i q u e sw i l l b es t u d i e db y u s i n gl i f ts c h e m ea n ds u p p o r tv e c t o rm a c h i n ee t c ，p r a c t i c a l l y t h em o d e lv i s - t s m i n e rb a s e d o nw a v e l e t a r i a l y s i sf o r v i s u a ld a t a m i n i n g o nt i m es e r i e sw i l lb e i m p l e m e n t e d t h e r ea r ef o u rn e wi d e , a si nt h i sd i s s e r t a t i o n ： ( 1 ) am u l t i r e s o l u t i o na n dm u l t i l e v e lt i m es e r i e ss i m i l a rp a t t e r n ss e a r c ht e c h n i q u e ，w h i c h c a n s u p p o r t o f f s e tt r a n s l a t i o na n d a m p l i t u d es c a l i n g ( 2 ) an o v e l s i m i l a r i t ym e a s u r em o d e lw h i c hc a ns u p p o r to f f s e tt r a n s l a t i o n ，a m p l i t u d e s c a l i n g a n d s t r e t c h i n g o r c o m p r e s s i n g i nt h et i m e - a x i sa n da m u l t i r e s o l u t i o n c l u s t e r i n g a n ds i m i l a r p a t t e r ns e a r c ht e c h n i q u e b a s e do nt h i sm o d e l ， ( 3 ) a b e r r a n te v e n t sd e t e c t i o no f t i m es e r i e sb a s e do nw a v e l e tt r a n s f o r mm o d u l u sm a x i m a ， ( 4 ) am o d e lb a s e do nw a v e l e t a n a l y s i sf o r v i s u a ld a t am i n i n go i lt i m es e r i e s ，w h i c h s u p p o r t sm u l t i - r e s o l u t i o nv o l u m ed a t av i s u a l i z a t i o n ，d a t am i n i n gp r o c e s s v i s u a l i z a t i o n a n dr e s u l tp a t t e r n sv i s u a l i z a t i o n k e y w o r d s ：d a t am i n i n g ，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 ，t i m es e r i e s s i m i l a r i t y , w a v e l e t a n a l y s i s ， a b e r r a n te v e n t sd e t e c t i o n i v 笫一章综述 第一章综述 1 1 数据挖掘概述 1 1 1 数据挖掘的背景 数据库技术的发展以及数据库的大量应用使得数据库的规模日益扩大，数据 库中存储的数据量急剧增大，而目前对这些数据进行分析处理的工具很少，并有 局限性。目前的数据库系统只能对数据进行存取，通过这种方式所获得的信息量 仅仅是整个数据库所包含信息量的很少一部分。然而隐藏在这些数据内部的更重 要的信息是关于这些数据之间的关联性、归类性以及对数据整体特征的描述和对 其发展趋势的预测，这些信息在决策生成的过程中具有重要的参考价值。因此， 迫切需要有新的更为有效的技术和工具对各种数据信息资源进行开采以发挥其 应用潜能。数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t ab a s e ，k d d ) 正 是在这样的应用需求背景下产生并迅速发展起来的，已经成为当前一个重要的研 究领域。 定义1 1 ：数据库中的知识发现( k d d ) 是指从数据库的数据中抽取出其中隐含 的、新颖的、有用的信息的非平凡过程 f a y y a de ta l ，1 9 9 6 。 数据挖掘( d a t am i n i n g ，简称d m ) 是k d d 的核心步骤，指的是用人们可以 接受的计算效率，找出数据源中的模式或模型。知识、规则或高层次信息等都可 以从包括关系数据库、数据仓库、交易数据库、空间数据库、时态数据库、时间 序列数据库、文本数据库、多媒体数据库、w o r l dw i d ew e b 数据等各种数据源 中挖掘，其中后面几种都属于复杂类型的数据挖掘的对象( h a i l , 2 0 0 1 ) 。数据挖 掘能从各种角度对它们进行进行分析和应用，从而为人们从事科研和经济实践提 供了丰富的知识库。 国际上首次关于数据挖掘与知识发现的研讨会是于1 9 8 9 年6 月在美国底 特律召开的。从1 9 9 5 年召开的第一届国际k d d 大会开始至今，已召开了数届国 际k d d 学术大会，k d d 2 0 0 2 大会已于今年7 月召开，这些都在国际上产生了很大 的影响。从9 7 年开始，k d d 有了自己的专门杂志。此外，还有一些这一主题的 地区性国际大会，如亚太地区数据挖掘与知识发现国际大会( p a k d d ) 等。所有 这些大会和研讨会都对该领域的兴起和蓬勃发展起了巨大的推动作用，大大促进 了多领域多学科的交叉和渗透，在世界上逐渐形成了k d d 的研究热点和高潮。 1 1 2 知识发现的一般过程 k d d 是一个多阶段的处理过程，一般包括下面的几个步骤，如图1 1 所示， 具体内容如下： ( 1 ) 数据准备与数据选择：了解k d d 相关领域的情况，熟悉有关的背景知识；根 据用户的要求，选取一个数据集或一个数据采样的子集，k d d 主要就是在这些 第一章综述 数据上进行的。 ( 2 ) 数据预处理：主要是对选择产生的数据集进行再加工，检查数据的完整性与 一致性，除去数据中的噪声，对丢失的数据进行填补。 ( 3 ) 数据约简：对经过数据预处理的数据，根据知识发现的任务目标，寻求能表 示数据的有用特征，利用属性约筒或变换方法对其操作，以减少数据量。 ( 4 ) 确定k d d 的目标：根据用户的要求，确定k d d 要发现何种类型的知识，因 为对k d d 的不同要求会在具体的知识发现过程中采用不同的知识发现算法。 ( 5 ) 确定知识发现算法：根据所确定的任务，选择合适的知识发现算法，这包 括选择合适的模型和参数，并使得知识发现算法与整个k d d 的评判标准相一致。 ( 6 ) 数据挖掘：运用特定的知识发现算法，从数据集中搜索用户所需要的感兴趣 的模式，如分类规则、关联规则、回归模型、聚类或预测模型等。 ( 7 ) 模式解释：对所发现的模式进行解释，可利用可视化等技术直观地解释所发 现的模式或知识。 ( 8 ) 知识评价：将所发现的知识以用户能了解的方式呈现给用户。这期间也包含 对知识的一致性的检查，以确保所发现的知识不与已有的知识相冲突。 图1 1 数据挖掘过程 在上述的过程中，在某几个阶段之间可以重复进行，也可以在整个流程中进 行循环，以确保所发现的知识准确可靠。 1 1 3 知识发现任务的类型 目前，人们已经从各种不同的角度用不同的方法对k d d 进行了许多令人感兴 趣的研究。这里按照数据挖掘的知识类型，简要论述知识发现的任务类型： ( 1 ) 关联分析( a s s o c i a t i o n ) 它是数据对象属性项之间的相互依赖关系。一个关联规则的形式为： 2 第一章综述 a l a 2 a m b l b 2 八b 。 如果b l ，b 2 ，b 。出现，那么a l ，a 2 ，a 。一定出现，这表明a l ，a 2 ，a 。和b l ，b 2 b 。有着某种联系。关联规则是1 9 9 3 年由a g r a w a l ，r 等人提出的 a g r a w a le ta i 1 9 9 3 b 1 ，然后扩展到从关系( r e l a t i o n a l ) 数据库、空间( s p a t i a l ) 数据库和多媒 体数据库中挖掘关联关系 k o p e r s k i ，1 9 9 5 ；z a i a n e ，1 9 9 8 ，并且要求挖掘通用的、 多层次的 h a r t & f u ，1 9 9 5 、用户有兴趣的关联规则。随着应用和技术的发展， 几年来对挖掘关联规则技术提出了更新的要求，如在线挖掘( a g g a r w a l & y u ，1 9 9 8 ，【h i d b e r , 1 9 9 9 ，【a g g a r w a l & y u ，2 0 0 1 1 ) 、提高挖掘大型数据库的计算效 率 a g r a w a l & y u ，1 9 9 4 3 、减小i o 开销、挖掘定量型关联规则等 a g g a r w a l & y u ，1 9 9 9 】。 ( 2 ) 分类和预测( c l a s s i f i c a t i o n ) 根据数据的不同特征，将其划归为不同的类，这些类是事先利用训练数据建 立起来的。现有的分类方法主要有基于决策树分类法 q u i n l a n ， 1 9 8 6 ；q u i n l a n ，1 9 9 3 ；c h e ne ta l ，1 9 9 6 、统计分类方法 e l d e r ，1 9 9 6 1 、神经网络方法 【l u ，1 9 9 6 ；b a n s a l ，1 9 9 8 、b a y e s i a n 分类 h e c k e r m a n ，1 9 9 6 1 等。在d m 中这些方法 均遇到数据规模的问题，即大多数方法能有效解决小规模数据库的数据挖掘问 题，但应用于大数据量的数据库时，会出现性能恶化、精度下降的问题。 ( 3 ) 聚类分析( c l u s t e r i n g ) 根据所处理的数据的一些属性，对这些数据进行分类。经过分类以后的数据，在 各类之间其相似程度小，而在某一类内部，其数据的相似度大。分类结束后，每 类中的数据由唯一的标志进行标识，各类数据的共同特征也被提取出来，用于对 该类的特征描述。提高聚类效率、减少时间和空间开销以及如何在高维空间进行 有效数据聚类是d m 聚类研究中的主要问题 j a i n & d u b e s ，1 9 8 8 。采用方法有基 于层次方法：有b i r c h z h a n g e ta l ，1 9 9 6 ，c u r e g u h a ，1 9 9 8 ；基于密度的方法 有：d b s c a n e s t e r e ta l 1 9 9 6 ，o p t i c s a n k e r s t e ta l ，1 9 9 9 b ，d e n c l u e ( h i n n e b u r g & k e i m ，1 9 9 8 ，c l i q u e ( a g r a w a l e ta l1 9 9 8 】) ：基于网格方法 ( w a n ge ta l1 9 9 7 】， s h e i k h o l e s l a m ie ta l ，1 9 9 8 ) ， s h e i k h o l e s l a m ie ta l ，1 9 9 8 】 提出一个基于小波的多分辨聚类算法；基于模型的方法 f i s h e r , 1 9 8 7 。 ( 4 ) 序贯模式( s e q u e n t i a lp a t t e r n s ) 给定一个事务数据库，一个事务序列是一组按事务时间排列的事务，每个事 务是一个项的集合，需要发现所有不小于指定的最小支持度阈值的序贯模式。序 贯模式( a g r a w a l & s f i k a n t ，1 9 9 5 ， s r i k a n t & a g r a w a l ，1 9 9 6 ， s e n o & k a r y p i s ，2 0 0 2 ) 的发现方法与关联规则类似，但关联规则描述的是交易内部的项集 之间的关联，序贯模式描述的是交易之间的关联。 ( 5 ) 多层次数据概括( h i e r a r c h i c a ld a t aa b s t r a c t ) 第一章综述 在数据库的大量相关数据集中，对低层的、原始的概念进行抽象，称为高层 的概念，表现为逐层抽象、提炼的概念。目前这方面技术有数据立方技术( 或称 o l a p ：o n 1 i n ea n a l y t i c a lp r o c e s s i n g ) 和面向属性归纳技术( 或称在线概括数据 分析) 。 f 6 1 预测( p r e d i c t i o n ) 预测是通过些属性的数据和训练数据集，根据先验知识的假设来预测另外 一些属性的数值。预测指的是获取数值数据的值，与分类明显不同。 ( 7 ) 离群分析( o u t l i e ra n a l y s i s ) 给定一个数据库，离群数据是那些在某些特征上与数据库中的大部分数据有 着显著不同的数据。离群分析方法主要有：基于统计的离群检测f b a r n e t t & l e w i s ，1 9 9 4 】、基于距离的离群检狈l j k n o r r & n g ，1 9 9 8 】、基于偏差的离群检测 【a r n i n ge ta l ，1 9 9 6 】。离群数据的发现可以应用在信用卡使用、金融欺诈、医 学数据分析等领域中。 f 8 1 偏差检测( d e v i a t i o nd e t e c t i o n ) 数据库中的数据常有一些异常记录，从数据库中检测这些偏差 a r n i n ge t a l ，1 9 9 6 ：艮有意义。偏差包括很多潜在的知识，偏差检测的基本方法是寻找观 测结果与参照值之间有意义的差别。偏差检测的数据模式有极值点、断点、拐点、 零点和边界等不同的偏差对象。 k d d 所处理数据的特点对数据挖掘技术提出了挑战和苛刻要求，如：应发展 适应各种不同的数据库类型的d m 技术；发展适应大型数据库的d m 技术；提取有 用的、确定的和易懂的知识；使用多种方式( 语言、图、表等) 表达d l 的结果； 知识交互和保密等。目前，研究和发展新的d m 技术，采用和集成各种领域的新 技术进行有效的数据挖掘是当今的主流研究方法和发展方向。 1 1 4 知识发现的方法 由于k d d 的应用领域十分广泛，因此产生了多种数据挖掘的算法和方法，如 b a y e s i a n 网络 h e c k e r m a n ，1 9 9 6 ；c h e e s e m a n ，t 9 9 6 、演绎逻辑规划( i l p ) d z e r o s k i ，1 9 9 6 、粗集理论 p a w l a k ，1 9 9 1 、决策树方法 q u i n l a n ，1 9 9 3 、神经 网络方法 l u ，1 9 9 6 ；b a n s a l ，1 9 9 8 等。有时对于某一数据库很有效的算法对另一 数据库有可能完全无效，因此，针对具体的挖掘目标和应用对象而设计不同的算 法。这里我们讨论具有代表性的几类方法： ( 1 ) 决策树和规则归纳 决策树表示形式简单，所发现的模型也易于为用户理解。迄今，许多机器学 第一章综述 习和统计学的文献都讨论了大量的决策树和规则归纳的算法 b r e i m a n ，1 9 8 4 ；q u i n l a n ，1 9 9 3 】，这些算法是基于可能性模型的方法。基于修剪规 则和树增长结构的贪心搜索法通常被用于在指数复杂度的可能的模型空间搜索。 决策树和规则归纳主要被用于构造预测类的模型 a p t e & h o n g ，1 9 9 6 ，但也可 用于构造描述型的模型。 ( 2 ) 神经网络方法 由于神经网络有许多十分吸引人的特点，并行处理、分布存储、高度容错、 自组织等，因此它是k d d 中重要的新技术与新方法。如，结合a r t 网络，提出 了一种神经网络规则学习的规范模型；从神经网络对噪音的鲁棒性以及非线性函 数逼近的特性出发【l u ，1 9 9 6 1 ，提出了规则提取的神经网络方法。在2 0 0 0 年，国 际一级杂志i e e et r a n s a c t i o n so nn e u r a ln e t w o r k s ) ) 为神经网络在k d d 中的应 用专门出版了一期专题“n e u r a ln e t w o r k sf o rd a t am i n i n ga n dk n o w l e d g e d i s c o v e r y ”。 ( 3 ) 粗糙集方法 粗糙集用在知识发现过程中，属性依赖分析和分类是较为成熟的方法。粗糙 集方法可以容易地进行假设检测和发现属性取值之间的关联。k e n t k e n t ，1 9 9 3 提出采用粗糙集方法来描述一个集合的特征，h u h u ，1 9 9 5 在粗糙集框架内研究 了面向属性的知识发现技术。粗糙集通常是与规则推导、分类、聚类等方法一起 组合使用。 ( 4 ) 基于范例的方法 运用已有的实例来构造一个近似模型，或者说是根据已有的类似例子对新的 问题进行预测求解。基于范例的方法要求提供一个评价数据之间距离的度量标准 【k o l o d n e r , 1 9 9 3 】。此外，该方法和非线性回归方法一样，具有很强的近似表示能 力。 一般地，c b r 用在d m 中有两个方法，一是使用c b r 技术作为知识发现过 程的环境以用于数据挖掘操作，二是向c b r 过程提供信息以便取得更好的挖掘 效果。 ( 5 ) 可能依赖图模型 图模型使用一个图结构确定一个特定模型中的可能依赖关系 w h i t t a k e r ，1 9 9 0 】。通常这些模型适用于分类和离散型数据。这类方法最早在专家 系统的框架内被采用。最近几年，人工智能和统计学界都做了大量的研究工作， 使得它们可用于从数据库中学习模型的结构和参数。图模型的搜索由贪心法组 成，已有的知识( 例如：基于因果关系的偏序) 对于缩小搜索空间是相当有用的。 由于图模型的方法直观容易理解，因此，这类方法引起了知识发现研究者的极大 兴趣。 第一章综述 ( 6 ) 模糊技术 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别、模 糊分类分析( m e n d e s e t a l ，2 0 0 i ) 和模糊关联分析( t h a n & a u ，1 9 9 7 】， k u o ke ta l ，1 9 9 8 ) 。模糊性是客观存在的，系统的复杂性越高， 精确化能力就越低，也就意味着模糊性越强。当输入有不确定性时，模糊系统就 是一种强有力的模型方法。 ( 7 ) 统计分析方法 在数据库中，字段之间存在着多种关系，利用统计方法可以对它们进行分析 处理，比如有回归分析，相关分析，主成分分析。b a y e s 方法也是属于这一种。 利用数据例子，通过学习自动生成b a y e s 网，其中的学习算法包括两类：一类是 采用类似神经网络的学习算法，另一类是基于统计分析，一般假定b a y e s 网参数 成正态分布。 ( 8 ) 遗传算法 遗传算法是模拟生物进化过程的算法。这种思想符合“适者生存，劣者淘汰” 的进化原则。遗传算法可用于数据挖掘 m e n d e se ta l ，2 0 0 1 ，以构造变量之 间的依赖性假设，其形式可以是关联规则或其它内部机制。 1 1 5 知识发现的应用 目前对知识发现研究的浓厚兴趣与知识发现在现实世界中大量成功的应用 是分不开的。下面我们分别从实际开发的知识发现系统、工具和研究机构来介绍 知识发现的应用。 ( 1 ) 知识发现工具及产品 目前的知识发现工具一般分为三类： ( i ) 一般单任务类。这类工具已经开发出许多，主要采用决策树、神经网络、范 例推理、基于规则等的方法，发现任务大多属于分类范畴。在具体应用中，主要 用于知识发现过程中的数据挖掘步骤，而且需要相当工作量的预处理和后处理。 ( i i ) 通用多任务类。这类工具可以执行多个领域的知识发现任务，一般集成了分 类、可视化、聚类和约简等多项发现策略。 ( i i i ) 面向专门领域类。它仅支持特定领域，用户不需要了解发现方法和过程。 下面介绍几个典型的数据挖掘工具产品。 ( i ) d b m i n e r ：它是加拿大s i m o nf r a s e r 大学开发的一个k d d 系统 ( h t t p ：d b c s s f u c a ) 。系统设计的目标是以面向属性的多级概念为基础发现各种 6 第一章综述 知识，系统具有如下特点：能完成多种规则的发现：泛化规则、关联规则、分 类规则、偏离知识等；综合了多种数据挖掘技术：璇向属性的归纳、统计分析、 元规则引导发现等方法；能与关系数据库集成起来，提出了一种交互式的类 s q l 语言数据挖掘查询语言；并实现了基于客户服务器体系结构的u n i x 与 p c ( w i n d o w s n t ) 版本。 ( i i ) c l e m e n t i n e ：由i n t e g r a ls o l u t i o n sl t d h t t p ：w w w i s l c o u k 开发。这是一个属于 通用多任务类的工具，它采用了神经网络、c 4 5 、规则归纳、可视化等技术，可 以构造预测、估计、分类、诊断和决策支持等模型。它对用户是开放的，从而用 户可以根据实际情况对它进行配置。可视化技术使得它界面友好，易于为用户掌 握。它的应用领域众多，如市场份额预报、金融欺诈行为的探测、金融风险评估、 故障诊断和预报、科学数据分析等等。 ( i i i ) q u e s t ：它是i b m 公司a l m a d e n 研究中心开发的个多任务k d d 系统 f h t t p ：w w w a l m a d e n i b m c o r n c s q u e s t ) ，目的是为新