（计算机软件与理论专业论文）大数据库中频繁模式挖掘算法研究及应用.pdf

山东师范大学硕士学位论文 大数据库中频繁模式挖掘算法研究及应用 摘要 随着信息技术的高速发展和互联网的迅速普及，导致在各个应用领域的数据 库中存储了大量的数据，这些数据集中包含着很多有用的知识，因此如何从各种 大型或密集数据库中发现所隐藏的、预先未知的信息，显的尤为重要，这正是数 据挖掘所要完成的任务。 关联规则挖掘是数据挖掘领域中成果显著而且比较活跃的研究分支。其主要 研究目的就是从大型数据集中发现隐藏的、有趣的、属性间的规律，即关联规则。 由于形式简单、易于理解而且是从大型数据库中提取知识的主要手段，因此，关 联规则挖掘成为数据挖掘中的热点问题。 关联规则挖掘过程包括：首先是将现有的数据库转换成事务数据库的形式 ( t r a n s a c t i o nd a t a b l e ) ，然后采用适当的算法从事务数据库中挖掘出所有的频繁模 式，最后由频繁模式生成有价值的关联规则。其中的第二阶段发现频繁模式是关 键，它将决定关联规则挖掘的正确性和挖掘的效率。因此，大部分研究都集中在 频繁模式的产生上。目前的频繁模式挖掘算法都过分的依赖于大量的计算，进而 导致对内存空间的依赖，当参数需要调整时，造成重复的f o 扫描。这都无法满 足对大型数据库挖掘的要求。因此寻求减少对内存空间的依赖，降低重复聃d 扫 描次数的新方法就成为文章的研究内容。 通过研究发现，影响频繁模式挖掘算法效率的因素主要有两个：1 数据库中 事务布局方式的不合理；2 算法本身存在的问题。所以本文主要从这两个方面进 行改进。具体工作体现在以下三个方面： 1 、敏感性分析在数据挖掘中的应用研究：数据挖掘被视为一种把数据转化 为信息，把信息转化为行为，把行为转化为价值或利润的过程。最近的研究大都 集中在静态环境中利润的挖掘。敏感性分析方法能够预测模型输出结果的变化 率。本文研究了利用敏感性分析这一方法在动态环境中对利润挖掘所起的作用， 最后给出了应用该方法对利润挖掘的执行步骤。 2 、在研究了传统的事务数据库布局方式：水平布局方式和垂直布局方式的 不足之处，提出种新的事务在数据库中的布局方式一交叉布局方式。该布局方 式能够有效减少i o 重复扫描的次数，特别是当参数经常改变时。从而提高查找 频繁模式的效率，进而提高关联规则挖掘的效率。 3 、提出一种新的频繁模式挖掘算法一q f p 算法。该算法利用了交叉布局方式 的数据存储结构，首先对每一个频繁项建立一棵q f p 树，然后根据条件对每棵树 进行挖掘，直到找出符合条件的频繁模式。此算法能够减少条件子树的生成数量， 山东师范大学硕上学位论文 降低对内存空间的依赖和c p u 的计算时阃，从而提高关联规则挖掘的效率。 关键词：敏感性分析；利润挖掘；| 兴趣挖掘；交叉布局；q f p ； 分类号：t p 3 1 1 山东师范大学硕士学位论文 r e s e a r c ho fm i n i n gf r e q u e n tp a t t e r na l g o r i t h ma n di t sa p p l i c a t i o n i nl a r g ed a t a b a s e a b s t r a c t a l o n gw i t ht h ei n f o r m a t i o nt e c h n o l o g yh i g h s p e e dd e v e l o p m e n ta n dw w w a p p l i c a t i o n s ，m a s s i v ea m o u n t so fd a t ah a v e b e e nc o n t i n u o u s l yc o l l e c t e di nt h e d a t a b a s eo fm a n ya p p l i c a t i o na r e a s ，w h i c hc o n t a i nm u c hu s e f u lp a t t e r n s ，a n di ti sv e r y i m p o r t a n tt of i n dt h eh i d d e na n dp r e v i o u s l yu n k n o w ni n f o r m a t i o nf o rt h e s ea r e a s d a t am i n i n ga i m sa tt h et a s ko ft h ea b o v ew o r k a s s o c i a t i o nr u l em i n i n gi sa l li m p o r t a n tb r a n c ho fd a t am i n i n gt h a ti th a so b t a i n e d m a n yv a l u a b l er e s u l t s t h ea i mi s t od i s c o v e r p r e v i o u s l yu n k n o w n ，i n t e r e s t i n g r e l a t i o n s h i p sa m o n ga t t r i b u t e sf r o ml a r g ed a t a b a s e d u et oi t ss i m p l ef o r ma n db e i n g e a s yt ou n d e r s t a n d ，a s s o c i a t i o nr u l em i n i n gh a sb e c o m eah o tt o p i ci nd a t am i n i n g t h es t e po f m i n i n ga s s o c i a t i o nr u l ei n c l u d i n g ：t r a n s f o r mt h ed a t a b a s ei n t o t r a n s a c t i o nd a t a b a s e s e c o n du s et h es u i t a b l ea l g o r i t h mt om i n ea l lf r e q u e n tp a t t e r n s f r o mb u s i n e s sd a t a b a s e a tl a s tp r o d u c e st h ev a l u a b l ea s s o c i a t i o nr u l eb yt h ef r e q u e n t p a t t e r n s e c o n ds t a g ei sk e y i tw i l ld e c i d et h ea c c u r a c ya n de f f i c i e n c yo fa s s o c i a t i o n r u l em i n i n g m o s to ft h er e s e a r c ha t t e n t i o ni sf o c u s e do ne f f i c i e n tm e t h o d so ff i n d i n g f r e q u e n ti t e m s e t s t h ee x i s t i n gf r e q u e n tp a t t e r n sm i m n ga l g o r i t h md e p e n dh e a v i l yo n m a s s i v ec o m p u t a t i o n a n dt h e nc a u s eh i 曲d e p e n d e n c yo nt h em e m o r ys i z e ，w h e n t u n i n gp a r a m e t e r s ，i tw i l lc a u s er e p e a t e df o ，a n dn o ts u f f i c i e n tf o rm i n i n ge x t r e m e l y l a r g ed a t a b a s e t h e r e f o r es e e kn o td e p e n do nr e p e a t e df os c a n sa n dl e s sr e l i a n to n m e m o r ys i z eb e c o m et h ec o n t e n to ft h i sp a p e r t h r o u g ht h er e s e a r c h ，w ef i n dt h e r ea r et w of a c t o r se f f e c tt h ee f f i c i e n c yo ff r e q u e n t p a t t e r n sm i n i n ga l g o r i t h m s ：1t h et r a n s a c t i o n sl a y o u ti nd a t a b a s ei su n r e a s o n a b l e ；2 t h ep r o b l e mo fa l g o r i t h m s t h e r e f o r et h i sp a p e rw i l ld oi m p r o v e m e n t m a i n l yf r o mt h i s t w o t h ec o n c r e t ew o r km a n i f e s t si nf o l l o w i n gt h r e ea s p e c t s ： 1 、h a sr e s e a r c h e dt h es e n s i t i v i t ya n a l y s i sm e t h o da n di t si nt h ed a t am i n i n g a p p l i c a t i o n o nt h i sb a s i c , w ep r o p o s e dt h em e t h o dt h a tu n i f i e st h es e n s i t i v ea n a l y s i s a n dt h en e u r a ln e t w o r km o d e la p p l yi n t ot h ei n t e r e s tm i n i n ga n dp r o f i tm i n i n go fd a t a m i n i n g f i n a l l yp r o d u c e st h em i n i n gs t e p 2 、i nv i e wo ft r a d i t i o n a lt r a n s a c t i o ni nd a t a b a s el a y o u t ，h o r i z o n t a l l a y o u ta n d v e r t i c a ll a y o u td e f i c i e n c y t h i sp a p e rd e s i g n so n ek i n do fn e wt r a n s a c t i o ni nt h e d a t a b a s el a y o u t o v e r l a p p i n gl a y o u t t h i sl a y o u tc a nr e d u c et h en u m b e rt i m e so fi o 山东师范大学硕士学位论文 r e p e t i t i o ns c a n n i n g , e s p e c i a l l yw h e nt h ep a r a m e t e rc h a n g ef r e q u e n t l y t h u se n h a n c e t h ee f f i d e n c yo fs e a r c hf r e q u e n tp a t t e r n 3 、t h i sp a p e rp r o p o s e so n ek i n do fn e wf r e q u e n tp a t t e r nm i n i n ga l g o r i t h m - q f p a l g o r i t h m t h i sa l g o r i t h mh a su s e dt h e , d a t as t o r es t r u c t u r eo fc r o s s i n gl a y o u tw a y f i r s te s t a b l i s h e sat r e ef o re a c hf r e q u e n ti t e m ( t h eq f pt r e e ) ，t h e nm i n i n ge a c ht r e e a c c o r d i n gt ot h ec o n d i t i o n ，u n t i ld i s c o v e r st h ef r e q u e n tp a t t e r nt h a tc o n f o r m st ot h e c o n d i t i o n t h i sa l g o r i t h mc a nr e d u c et h en u m b e ro fc o n d i t i o nt r e e ，t h ed e p e n d e n c yo f m e m o r ys p a c e ，a n dt h ec o m p u t i n gt i m eo fc p u t h u se n h a n c e m e n t t h ee f f i c i e n c yo f a s s o c i a t i o nr u l em i n i n g k e y w o r d s ：s e n s i t i v i t ya n a l y s i s ；p r o f i tm i n i n g ；i n t e r e s tm i n i n g ；c r o s s i n gl a y o u t ；q f p c l a s s i f i c a t i o n ：t p 3 1 1 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名：j 否岩， 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权刳童可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：一磊毒， 导师签字： 签字日期：2 0 0 1 年上t 月三7 日 签字日期：2 0 07 年午月2 7 日 山东师范大学硕士学位论文 1 1 研究背景 第一章绪论 近年来随着信息技术的迅猛发展，数据库技术的成熟和数据应用的普及，人 类积累的数据量正在以指数速度迅速增长。面对“堆积如山”的数据信息，传统 的数据分析方法受到了巨大的挑战。例如简单的数据查询和统计方法，它只能获 得数据的表面信息，满足低层次的需求。很难对其进行深层次的处理，无法获得 数据中隐藏的重要的有价值的知识。这样使得人们面对大量数据的同时又感到 “信息的贫乏”，从而形成一种“丰富的数据，贫乏的知识”的现象。如何从这 些海量的数据中发现信息，变被动的数据为主动的知识，如何快速获得有价值的 信息，指导人们的决策，获得更大的经济效益和社会效益，人们迫切的需要一种 有效的数据分析手段对各种数据矿藏进行有效的挖掘以发挥它们的应用潜能。 在这样的背景下，数据挖掘技术应运而生了。1 9 8 9 年8 月召开的第l l 届 国际人工智能联合会议上首次提出了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 s ， 数据库中的知识发现) 概念，而数据挖掘是它的核心。它的出现为自动和智能地 把海量数据转化为有用的信息和知识提供了手段。它能自动从数据中提取出人们 感兴趣的、潜在的可用信息和知识，并将提取出来的信息和知识表示成概念、规 则、规律和模式。因此，它能帮助人们发现隐藏在数据库中的有用的信息，以帮 助人们正确理解和认识数据，进行科学决策。数据挖掘作为一门新兴的边缘学科， 它融合了数据库( d a t a b a s e ) 技术、人工智能( a r t i f i c i a li n t e l l i g e n c e ) 、机器学 习( m a c h i n el e a r n 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 b j e c t o r i e n t e dm e t h o d ) 、信息检索( i n f o r m a t i o nr e t r i e v a l ) 、高 性能计算( h i g h p 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 n ) 等最新技术的研究成果。目前数据挖掘技术以成为国际国内数据库和信息决策领 域的最前沿研究方向之一。 1 2 数据挖掘研究现状及其发展趋势 数据挖掘和知识发现是今年来一个十分活跃的研究领域。迄今为止，由美国 人工智能协会主办的k d d 国际研讨会已经召开了7 次，规模由原来的专题讨论会 发展到国际学术大会，人数由二三十人到七八百人，平均会议代表年增长率为 4 0 ，从事数据挖掘研究的人员遍布世界8 0 个国家，研究重点也逐渐从发现方 法转向系统应用，从实验室原型走向商品化阶段。并且注重多种发现策略和技术 的集成，以及多种学科之问的相互渗透。其他内容的专题会议也把数据挖掘和知 识发现列为议题之一，成为当前计算机科学界的一大热点。世界上研究数据挖掘 山东师范大学硕士学位论文 的组织、机构或大学很多。比较著名的如卡内基梅隆大学( 有机器制造d m 、多 媒体数据库d m 、互连网d m 三个研究中心) 、斯坦福大学、麻省理工学院。著 名研究机构如：a c m ( a c ms p e c i a lh l t c r c s tg r o u po nk n o w l e d g ed i s c o v e r yi nd a t a a n dd a t am i n i n g ) 、k d n e t ( t h ee u r o p e a nk n o w l e d g ed i s c o v e r yn e t w o r ko f e x c e l l e n c e ) 、n c d mf f h en a t i o n a lc e n t e rf o rd a t am i n i n g ( n c d m ) a t t h eu n i v e r s i t y o fi l l i n o i sa tc h i c a g o ( u i c ) ) 。 当前，数据挖掘研究正方兴未艾，研究焦点可能会集中到以下几个方面：研究 专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准 化；寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理解，也 便于在知识发现过程中的人机交互；研究在网络环境下的数据挖掘技术，特别是 在i n t e r n e t 上建立数据挖掘服务器，与数据库服务器配合。实现数据挖掘；加强对各 种非结构化数据的挖掘，如文本数据、图形图像数据、多媒体数据。但是。无论怎 样，需求牵引，市场驱动是永恒的，数据挖掘将首先满足信息时代用户的急需，大量 基于数据挖掘的决策支持软件工具产品将会问世。 1 3 课题目的和意义 关联规则挖掘是数据挖掘技术中非常重要和有应用前景的一种技术。所谓关 联规则挖掘，就是说发现大量数据中项集之间的有用的关联或相关联系，从大量 事务记录中发现有用的关联关系，可以帮助许多商务决策的制定。 近几年，由于数据的大量增加，数据库的规模也在不断增大，现有的挖掘算 法的效率大都不能满足用户的要求，提高挖掘算法的效率势在必行。 研究关联规则挖掘理论发现，其主要有两大步骤组成： 1 根据给定的最小支持度生成频繁模式集： 2 在频繁模式的基础上，根据给定的最小置信度产生用户要求的强关联规 则。 理论证明，一种关联规则挖掘算法性能的好坏主要取决于其第一步的运行效 率，因此，大量的对关联规则挖掘算法的研究都集中在频繁模式挖掘上。 针对目前数据库日益增大的现状，设计出一种高效的频繁模式挖掘算法就显 得尤为重要，它很大程度上决定了关联规则挖掘的效率，提高频繁模式的挖掘算 法主要有以下途径： 1 改善现有事务数据库的布局方式，从而降低重复扫描数据库的次数； 2 降低算法对内存的依赖，从而提高算法执行的效率； 本课题就是在这样的背景下产生的，着眼于现有算法的不足以及主要缺陷来 进行改进，旨在进一步提高频繁模式挖掘算法的性能。 2 山东师范大学硕t 学位论文 1 4 本文的主要研究内容 如前所述，数据挖掘竹：为- f l 新兴的交叉学科提出了很多具有挑战性的研究 课题，其涉及的内容、研究的方向广泛而又丰富。本文的研究工作主要是针对大 型数据库中如何提高频繁模式挖掘算法的效率，从而提高关联规则的挖掘效率。 本文的创新点主要包括以f j l 个部分： 1 敏感性分析在数据挖掘中的应用研究：数据挖掘被视为一种把数据转化为 信息，把信息转化为行为，把行为转化为价值或利润的过程。最近的研究大都集 中在静态环境中利润的挖掘。敏感性分析方法能够预测模型输出结果的变化率。 本文研究了利用敏感性分析这一方法在动态环境中对利润挖掘所起的作用，最后 给出了应用该方法对利润挖掘的执行步骤。 2 在研究了传统的事务数据库布局方式：水平布局方式和垂直布局方式的不 足之处，提出一种新的事务在数据库中的布局方式一交叉布局方式。该布局方式 能够有效减少i ，o 重复扫描的次数，特别是当参数经常改变时。从而提高查找频 繁模式的效率，进而提高关联规则挖掘的效率。 3 提出一种新的频繁模式挖掘算法q f p 算法。该算法利用了交叉布局方式 的数据存储结构，首先对每一个频繁项建立一棵q f p 树，然后根据条件对每棵 树进行挖掘，直到找出符合条件的频繁模式。此算法能够减少条件子树的生成数 量，降低对内存空间的依赖和c p u 的计算时间，从而提高关联规则挖掘的效率。 本文的内容是这样组织的： 第一章概要阐述了本文的研究背景、数据挖掘研究现状及其发展趋势、课题 目的和意义、本文的创新点和主要内容。 第二章介绍了数据挖掘的相关概念、技术、面临的问题和发展趋势。以及本 文的第一个创新工作敏感性分析在数据挖掘中的应用研究。 第三章介绍了关联规则的概念、性质、技术和方法。 第四章重点介绍了频繁模式挖掘的概念、研究现状及方法。并对经典的 a p r i o r i 算法和f p g r o w t h 算法进行了分析研究。 第五章重点介绍了本文研究的主要内容：交叉布局方式和q f p 算法。通过 实验对f p g r o w t h 算法和q f p 算法进行了比较分析，最后得出结论。 第六章对全文做了总结，列举了论文的主要研究内容和存在的问题，并探讨 了进一步研究方向 山东师范大学硕士学位论文 2 1 数据挖掘概念 第二章数据挖掘技术 知识发现( k d d ) 被认为是从数据中发现有用知识的整个过程。数据挖掘 ( d m ) 被认为是k d d 过程中的一个特定步骤，它用专门算法从数据中抽取模 式( p a t t e r n s ) 。数据挖掘( d a t am i n i n 曲就是从大量的、不完全的、有噪声的、模 糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程。数据挖掘流程图如2 1 所示： 图2 1 数据挖掘流程图 数据：一个有关事实f 的集合，它是用来描述事务有关方面的信息，是我们 进一步发现知识的原材料。 新颖：经过数据挖掘提取出的模式必须是新颖的，至少对系统来说应该是如 此。 潜在有用：提取出的模式应该是有意义的，可以用某些函数的值来衡量。 可被人理解：数据库中隐含的模式通过数据挖掘过程要以容易的被人理解的 形式表现出来，帮主人们更好的理解数据库中饱含的信息。 模式：对于集合f 中的数据，可以用语言l 来描述其中数据的特性。表达 式e el ，e 所描述的数据是集合f 的一个子集。只有当e 比列举的所有子集中 元素的描述方法更为简单时，才可称之为模式。“若成绩 8 0 则成绩优良”可称 为一个模式，而“若成绩8 2 、8 3 、则成绩优良”不能称之为一个模式。 数据挖掘把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知 识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据 库技术、人工智能技术、数理统计、可视化技术并行计算等方面的学者和工程技 术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 2 2 数据挖掘的步骤 数据挖掘的过程可粗略的分为：问题定义、数据收集和预处理、数据挖掘算 法的执行，以及挖掘结果的解释和评估【2 , 9 1 。 4 山东师范大学坝l 学位论文 1 问题定义：数据挖掘的目的是为了在大量数据中发现有用的令人感兴趣的 信息，因此发现何种知识就成为整个过程中第一个也是最重要的一个阶段。在问 题定义过程中，数据挖掘人员必须和领域号家以及最终用户密切协作，一方面明 确实际工作对数据挖掘的要求；另一方面通过对各种学习算法的对比确定可用的 学习算法。 2 数据的收集和预处理：数据的准备分三个步骤：数据选取、数据预处理和 数据变换。数据选取的目的是确定发现任务的操作对象，即目标数据，它是根据 用户的需要从原始数据库中抽取的一组数据。数据预处理一般包括消除噪声、推 倒计算缺值数据、消除重复记录、完成数据类型转换。当数据开采的对象是数据 仓库时，一般来说，数据预处理已经在生成数据仓库时完成了。数据变换的主要 目的是消减数据维数，即从初始特征中找到真正有用的特征以减少数据开采时要 考虑的特征或变量个数。 3 数据挖掘算法的执行：数据挖掘算法执行阶段首先根据对问题的定义明确 挖掘的任务或目的，如数据总结、分类、聚类、关联规则发现或序列模式发现等。 确定了挖掘任务后，就要决定是用什么样的挖掘算法。同样的任务可以用不同的 算法来实现，选择挖掘算法有两个考虑因素：一是不同的数据有不同的特点，因 此需要用于此相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户可 能希望获取描述型的、容易理解的知识，而有的用户或系统的目的是获取预测准 确度尽可能高的预测型知识。 4 结果的解释和评价：数据挖掘阶段发现出来的模式，经过评估，可能存在 冗余或无关的模式，这时需要将其删除：也有可能模式不满足用户的需求，这时 则需要整个发现过程回退到前一阶段，如重新选取数据、采用新的数据变换方法、 设定新的参数值，甚至换一种挖掘算法等。 2 3 数据挖掘的任务 根据挖掘任务，数据挖掘可分为概念描述、聚集发现、关联规则发现、分类 发现、回归发现和序列模式发现等。在选择使用某种数据挖掘技术之前，首先要 将待解决的商业问题转化成正确的数据挖掘任务，然后根据挖掘任务来选择具体 使用某一种或几种挖掘模式。下面具体的分析每一种挖掘任务应使用哪些挖掘模 式。 1 概念描述 概念描述是描述型数据挖掘的最基本形式。它以简洁汇总的形式描述给定的 任务相关数据集，提供数据的有趣的一般特性。通常，用户指定类的数据通过数 据库查询收集。数据特征的输出可以用多种形式提供，包括饼图、条图、曲线、 多维数据立方体和包括交叉表在内的多维表。进行概念描述挖掘时一般采用面向 山东师范大学硕上学位论文 数据库的方法，另外还可以采用机器学习方法的基于范例学习技术。与机器学习 方法相比，面向数据库的概念描述导致在大型数据库和数据仓库中的有效性和可 伸缩性。 2 聚类发现 聚类是把整个数据库分成不同的群组，使得群与群之间差别很明显，而同一 个群之间的数据尽量相似。与分类不同，在开始聚类之前你不知道要把数据分成 几组，也不知道怎么分( 依照哪几个变量) 。因此在聚集之后要有一个对业务很熟 悉的人来解释这样分群的意义。很多情况下一次聚类你得到的分群对你的业务来 说可能并不好，这时你需要删除或增加变量以影响分群的方式，经过几次反复之 后才能最终得到一个理想的结果。聚类在电子商务上的典型应用是帮助市场分析 人员从客户基本数据库中发现不同的客户群，并且用购买模式来刻画不同客户群 的特征。此外聚类分析可以作为其它算法( 如分类等) 的预处理步骤，这些算法再 在生成的簇上进行处理。 3 关联规则发现 关联分析是寻找在同一个事件中出现的不同项的相关性，比如在一次购买活 动中所买不同商品的相关性。序列模式与此类似，它寻找的是事件之间时间上的 相关性，如对股票涨跌的分析。以市场货篮这个典型例子分析关联规则。“在购 买面包和黄油的顾客中，有9 0 的人同时也买了牛奶”( 面包+ 黄油分牛奶) 。用 于规则发现的对象主要是事务型数据库，分析的是售货数据，也称货篮数据。关 联分析是目前是数据挖掘中应用最广泛的一种，它具有一定的研究价值。 4 分类发现 分类要解决的问题是为一个事件或对象归类。设有一个数据库和一组具有不 同特征的类别( 标记) ，该数据库中的每一个记录都赋予一个类别的标记，这样的 数据库称为示例数据库或训练集。分类分析就是通过分析示例数据库中的数据， 为每个类别做出准确的描述或建立分析模型或挖掘出分类规则，然后用这个分类 规则对其它数据库中的记录进行分类。在电子商务中分类分析可以预测客户响 应，如哪些客户最倾向于对直接邮件推销做出回应，又有哪些客户可能会换他的 手机服务提供商，或进行商店定位，如按成功的商店、一般商店和失败商店排列 得出这3 类商店各自具有的属性。然后选择包含位置属性的地理数据库，分析每 一预期的商店位置属性，以确定预期的商店定位属于哪一类。只有那些符合成 功一类要求的商店位置才作为商店定位的候选。用于分类分析的典型方法有统计 方法的贝叶斯分类、机器学习的判定树归纳分类、神经网络的后向传播分类等。 另外还有一些其它分类方法，包括k 最临近分类、m b r 、遗传算法、粗糙集和 模糊集方法。目前，尚未发现有一种方法对所有数据都优于其它方法。 5 回归发现 6 山东师范大学硕i ：学位论文 回p 是通过具有已知值的变量来预测其他变量的值。它与分类类似，差别在 于前者的预测值是连续的，而后者是离散的。在最简单的情况下，回归采用的是 像线性 归这样的标准统计技术。但在大多数现实世界中的问题是不能用简单的 线性回9 j 所能预测的。如商品的销售量、股票价格、产品合格率、利润的大小等， 很难找到简单有效的方法来预测，因为要描述这些事件的变化所需的变量以上百 计，且这些变量本身往往都是非线性的。为此人们又发明了许多新的手段来试图 解决这个问题，如逻辑回归、决策树、神经网络等。一般同一个模型既可用于回 归也可用于分类，如c a r t 决策树算法既可以用于建立分类树，也可建立回归 树，神经网络也是如此。 6 序列模式发现 、 序列模式分析和关联分析类似，其目的也是为了挖掘数据之间的联系，但序 列模式分析的侧重点在于分析数据问的前后序列关系。它能发现数据库中形如 “在某一段时间内，顾客购买商品a ，接着购买商品b ，而后购买商品c ，即序 列a b c 出现的频率较高”之类的知识。序列模式分析描述的问题是：在给定交易 序列数据库中，每个序列是按照交易时间排列的一组交易集，挖掘序列函数作用 在这个交易序列数据库上，返回该数据库中出现的高频序列。在进行序列模式分 析时，同样也需要有用户输入最小值信度c 和最小支持度s 。另外关联规则挖掘 中采用的a p d o r i 特性可以用于序列模式的挖掘，另一类挖掘此类模式的方法是 基于数据库投影的序列模式生长技术。 总之在选择一种数据挖掘技术我们应根据商业问题的特点来决定采用哪种 数据挖掘形式比较合适。应选择符合数据模型的算法，确定合适的模型和参数。 只有选择好正确的数据挖掘工具，才能真正发挥数据挖掘的作用，使企业在激烈 的市场竞争中做出正确的决策，保持有力的竞争优势，以便达到我们的挖掘任务。 2 4 数据挖掘的方法 原有的数据库技术只是将数据有效地组织和存储在数据库中，并对这些数据 作一些简单的分析，大量的隐藏在数据内部的有价值的信息我们无法得到，而机 器学习、统计学、模式识别等领域却有大量的提取知识的方法，但没有和实际应 用中的海量数据结合起来。数据挖掘从一个新的角度将数据库技术、机器学习、 统计学、模式识别等领域节合起来，从更深层次中发觉数据中的内在模式。由此， 数据挖掘方法主要有以下几种： 1 统计学方法：适用这些方法一般是首先建立一个数学模型或统计学模型， 然后根据这种模型提取出有关的知识。例如，可由i jr i 练数据建立一个b y e s i a n 网， 然后，根据该网的一些参数及联系权重提取有关知识。 2 机器学习：大多数机器学习方法用人类的认识模型模仿人类的学习方法 7 山东师范大学硕上学位论文 从数据中提取知识，由于机器学习经过多年的研究，已经取得了一些较满意的成 果。因此，在数据挖掘重可以利用目前成熟的机器学习方法。 3 面向数据库地方法：随着数据库技术的发展，其中的一些数据处理方法 不断完善并趋于成熟，在数据挖掘中利用现有的一些数据库技术和某些专业针对 数据库的一些启发式方法，可以提取出数据库中的一些特征知识。 4 模糊方法：模糊集合和模糊推理是模糊方法的数学基础，模糊集理论以 不确定性的事务为研究对象，是经典集合理论的扩展。模糊逻辑系统已用于许多 特别是基于规则的分类领域，包括医疗和财经。在基于规则的分类系统中引入模 糊逻辑，就可以定义“模糊”阈值或边界，可以避免原系统固有的缺陷( 对于连 续值有陡峭的截断1 从而可能获得一个更好的分类结果。 5 粗糙集理论：粗糙集是一种研究不完整、不确定知识和数据的表达、学 习和归纳的理论方法。它可用于分类，发现不准确的数据或噪声数据内在的联系， 找出可以描述给定数据集中所有概念的最小属性子集是个n p 难问题。在给定的 现实世界数据中，往往有些类不能可用的属性区分，那么可以用粗糙集来近似地 定义这些类。 6 云理论【5 】：云理论是李德毅教授于1 9 9 5 年提出的用于处理不确定性的一 种心理论。在数据挖掘中云理论研究的是数据的模糊性和随机性。为定量定性间 的不确定性的转换提供原型。 7 遗传算法：遗传算法易于并行，以广泛用于分类和优化问题。在数据挖 掘中，还可以用于评估其他挖掘算法的适合度 3 1 。 其他方法。如最邻近技术、归纳学习、证据理论等方法也是数据挖掘中常用 的方法。 2 5 数据挖掘的应用和研究方向 数据挖掘能够自动发现以前未知的模式，自动预测未来趋势和行为。从数据 库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许多 方面以及金融、市场营销、信用保险、化工医药等许多领域。帮助企事业单位 定位市场、预测销售趋势、优化营销策略、监督交易活动、发现交易规则等等。 数据挖掘是一个年轻而非常活跃的研究领域，目前面临的问题，除了基础理 论和技术方面的外，更重要的是开发和应用。当前数据挖掘的主要研究方向有： 1 加强应用研究，针对不同数据挖掘任务的专用数据挖掘系统。不同的应用 领域可能使用多种类型数据和数据库，知识发现系统应当能够对不同类型的数据 和数据库进行有效的数据挖掘。 2 高效率挖掘算法。为能从大量数据中有效的抽取信息，数据挖掘算法必须 是高效的，即算法的运行时间必须是可预测的和可接受的，带有指数或中间多项 8 山东师范人学硕i 擘位论文 式的算法是没有实际使用价值的。 3 提高数据挖掘结果的有效性、确定性和可表达性。 4 数据挖掘结果的可视化。 5 多源数据挖掘。网络将许多数据源连接在一起，形成巨大的分布式异构数 据库，同时促进了并行和分布式数据挖掘算法的研究。 6 数据挖掘的安全性和保密性。 6 数据挖掘面临的主要问题 本文提出的数据挖掘的主要问题，考虑挖掘方法、用户交互、性能和存储的 各种数据类型问题。 挖掘方法与用户交互问题。这类问题涉及所挖掘的知识类型、在多粒度上挖 掘知识的能力、领域知识的使用，特定的挖掘和知识显示。 1 在数据库中挖掘不同类型的知识：由于不同的用户可能对不同类型的知识 感兴趣，数据挖掘系统应当覆盖范围很广的数据分析和知识发现任务，包括数据 特征化、区分、关联、分类、聚类、趋势和偏差分析以及类似性分析这些任务可 能以不同的方式使用相同的数据库，并需要开发大量数据挖掘技术。 2 多个抽象层的交互知识挖掘：由于很难准确地知道能够在数据库中发现什 么，因此需要数据挖掘的过程具有交互性。对于包含大量数据的数据库，应当使 用适当的抽样技术，进行交互式数据探查交互式挖掘允许用户聚焦搜索模式，根 据返回的结果提出和精炼数据挖掘请求。用户通过交互地在数据空间和知识空间 下钻来挖掘知识，以不同的粒度和从不同的角度观察数据和发现模式。 “ 3 结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现过 程，并使得发现的模式以简洁的形式在不r 3 的抽象层表示。数据库的领域知识， 如完整性约束和演绎规则可以帮助聚焦和加快数据挖掘过程。 4 数据挖掘查询语言和特定的数据挖掘：关系查询语言( 如s q l ) 允许用户提 出特定的数据检索查询。同样需要开发高级数据挖掘查询语言，使得用户通过说 明分析任务相关的数据集、领域知识、所挖掘的数据类型、被发现的模式必须满 足的条件和约束，描述特定的数据挖掘任务。高级数据挖掘查询语言应当与数据 库或数据仓库查询语言集成，并且对于有效的、灵活的数据挖掘是优化的。 5 数据挖掘结果的表示和显示：数据挖掘中发现的知识应当用高级语言、可 视化或其它的形式表示，使得知识易于理解，能够直接被用户使用，这对于交 互式的数据挖掘系统尤为重要。它要求系统采用有表达能力的知识表示技术，如 树、表、规则、图、图表、交叉表、矩阵或曲线等。 6 处理噪声和不完全数据：存放在数据库中的数据可能反映噪声、异常情况 或不完全的数据对象。这些对象可能搞乱分析过程，导致数据与所构造的知识模 9 山东师范丈学硕士学位论文 型过分适应，使得所发现的模式的精确性很差。需要处理数据噪声的数据处理方 法和数据分析方法，以及发现和分析异常情况的孤立点挖掘方法。 7 模式评估：数据挖掘系统可能发现数以千计的模式，对于给定的用户，许多 模式不是有趣的，它们表示公共知识缺乏新颖性。开发模式兴趣度的评估技术， 特别是关于给定用户类，基于用户的信赖或期望，评估模式价值的主观度量是一 个极具挑战性的问题。 性能问题，包括数据挖掘算法的有效性、可伸缩性和并行处理。 1 数据挖掘算法的有效性和可伸缩性：数据挖掘一个重要的特点是产生假 设，但并不去验证假设【6 】。为了有效地从数据库的大量数据中提取信息，数据挖 掘算法必须是有效的和可伸缩的。即对于大型数据库，数据挖掘算法的运行时 间必须是可预计的和可接受的1 7 j 。 2 并行、分布式和增量挖掘算法：数据库的大容量、数据广泛和一些数据挖 掘算法的计算复杂性促使开发和研究了并行、分布式和增量挖掘算法。这些算法 将数据划分成多个部分，这些算法可以并行处理，然后将各个处理结果合并。数 据挖掘过程的高花费导致了对增量数据挖掘算法的需要，增量算法与数据库更 新结合在一起，而不必随着数据库的更新重新挖掘全部数据，算法渐增地进行知 识更新，修正和加强先前业已发现的知识。 关于数据库的多样性问题 1 关系的和复杂的数据类型的处理：数据库和数据仓库可能包含复杂的数据 对象、超文本和多媒体数据、空间数据、时间数据或事务数据。由于数据类型的 多样性和数据挖掘目标的不同，指望一个系统挖掘所有类型的数据是不现实的。 为挖掘特定类型的数据，应当构造特定的数据挖掘系统。大多数数据挖掘系统缺 少共享的底层挖掘语言，使得数据挖掘产品的标准化和在不同的数据挖掘系统之 间进行交互操作比较困难，制定数据挖掘的标准是十分重要的。 2 由异种数据库和全球信息系统挖掘信息：局域网和广域网连接了多种数据 源，形成了庞大的、分布式的和不同的数据库。从具有不同数据语义的结构化的、 半结构化的和非结构化的不同数据源发现知识，对数据挖掘提出了巨大挑战。数 据挖掘可以发现多个异种数据库中的数据规律，这些规律多半难以被简单的查询 系统发现：数据挖掘并可以改进异种数据库的信息交换和互操作性。w e b 挖掘发 现关于w e b 内容、w c b 使用和w e b 动态情况的有趣知识，成为数据挖掘的一个 非常具有挑战性的领域。 l o 山东师范大学硕士学位论文 2 7 敏感性分析在数据挖掘中的研究 2 7 1 引言 数据挖掘经常涉及到从大型的数据库中提取有趣的信息或者是有趣的模式。 目前的数据挖掘研究中存在两个主要的方面：模式和兴趣。模式发现技术包括分 类、关联和聚类。兴趣关系到该模式在商业应用中是否能产生效用或有某种程度 的意义。数据挖掘也被视为一种把数据转化为信息，把信息转化为行为，把行为 转化为价值或利润的过程。在文献【8 】中提到，对数据挖掘中规则兴趣度的研究 有三种不同的研究方向。一个重要的衡量兴趣度的标准是：规则是否能在商业决 策制定过程中增加商业利润。最近的研究【9 ，1 0 ，1 2 】大都集中在静态环境中研究利 润的挖掘。然而，有关在动态环境中利润挖掘的