（计算机应用技术专业论文）数据挖掘技术与关联规则挖掘算法研究.pdf

摘要 数据挖撼是致力于数据分辑翻理瓣、揭示数据内部蕴藏知 识的技术，它成为未来信息技术应用的重凄目标之一。经过十 几年的努力，数据挖掘产生了许多新概念和方法。特剐是最近 几年，些基本摄念和方法憝于瀵壤，它灼研究正岛羞更深入 的方向发展。像其它新披术的发展历程一样，数据挖掘技术也 必须经过概念提出、概念接受、广泛研究和探索、逐步应用和 大蹩痊翔等除段。铁嚣葭戆骥状豢，大郝分学黉认为数据挖掘 的研究仍然处于广泛研究和探索阶段，追切需要在基础理论、 应用模式、系统构架以及挖掘算法和挖掘语畜等方面进行创 薪。关联筑潮挖掘是数据挖掇中成果簸丰嚣萎跑较活跃熬磷究 分支，瞬给研究者的是更深入的课题。面对大型数据瘁，关联 规则挖掘需要在挖掘效率、可用性、精确性等方面得到提升。 困诧，需要探索新静挖掘逢论和模壅；需瓣乖l 用孺户的约束等 聚焦挖掘旦标；嚣要对一些传统的算法进行改进：也嚣要研究 新的更有效的算法等。鉴于爵前数据挖掘技术和关联规则挖掘 研究的现状和发展趋势。在备类蘩金的支持下，我们选择了这 一课题汗震糖关王馋。 本文的研究主要包括数据挖掘应用系统体系结构、关联规 则挖掘理论及其算法等。关于数据挖掘应用系统体系结构研究 方嚣，我翻设计了一令数据挖掘瘦瘸系统戆器型体系续梅，系 统化地分析了知识发现的基本过程和系统的各部件功能。由于 不间的源数据类型、不同的应用冈标以及不同的挖掘策略对数 据挖摇系统鳃功能舔件蝥求不霞，这麓研究主罄是麸稚诱发现 的基本过程出发，探讨系统戍具餐的主要功能部件及其相互联 系等。在关联规则挖掘理论研究上，我们首次给出了项目序列 集格空闻，并置探讨了在这个空阀上静基本搡作算子。基予顼 耳序列集格空闽及冀操住，我们慈立了关联援则挖掘模型积算 法。在关联规则挖掘算法方面，设计了基于项目序列集操作理 论的关联规则挖掘算法i s s d m 、时态约束下的关联规则挖掘 彝法t i s s d m 、数据分裂下戆关联援剥撼掘算法p i s s 。d m 。 i s s d m 算法是建立在严格的项目序列集格理论及其操作基 础上，是一个一次数据库扫描的而鼠不使用候选集的高效算 j 匕京工业大掌工掌博士掌位论文 法。我们选择目前引用率较高的a p r i o r i 算法和i s s d m 进行 了对比实验。结果表明，i s s d m 执行时间整体上优于a p r i o r i 算法，而且随着数据量的增大i s s d m 执行时间的增长幅度也 小于a p r i o r i 算法。为了提高对大型数据集挖掘的适应性，将 时态约束应用到挖掘的预处理中，改进i s s d m 成t i s s d m 。 这部分工作还包括对时态区间、时态约束下的数据挖掘空间以 及时态区间操作等进行了形式化，它们是t l s s - d m 的理论基 础。对i s s d m 的另一个改进算法是p l s s d m 。它是针对大数 据集挖掘过程中对内存和c p u 等系统资源要求较高的情况被 提出和设计的，采用了数据分割的方法来减少资源的占用。本 文解决了数据分割下局部频繁项目序列集和全局频繁项目序 列集的转换等问题，是一个两次扫描数据库的算法。 总之，本文在分析、归类现有数据挖掘研究成果以及原型 系统的基础上，进行了数据挖掘应用系统体系结构、关联规则 挖掘理论模型以及算法方面的研究。在项目序列集格及其操 作、时态约束挖掘空间等方面具有较好的理论价值，所设计的 算法在挖掘效率和对大型数据库挖掘的可用性方面具有潜在 的应用前景。 关键词：数据挖掘，知识发现，关联规则，项目序列集， 时态约束，数据分割。 n a b s t r a c t d a t a m i n i n g i sat e c h n i q u et h a ta i m st o a n a l y z e a n d u n d e r s t a n dl a r g es o u r c ed a t aa n dr e v e a lk n o w l e d g eh i d d e n i nt h ed a t a 。i th a sb e e nv i e w e da sa ni m p o r t a n te v o l u t i o ni n i n f o r m a t i o n pr o c e s s i n g w h y t h er eh a v eb e e nm o r e a t t e n t i o n st ol tf r o mr e s e ar c h e r so rb u s i n e s s m e ni sd u et o t h ew i d ea v a i l a b i l i t yo fh u g ea m o u n t so fd a t aa n dj m m i n e n t n e e d sf or t u r n i n g s u c hd a t ai n t ov a l u a b l ei n f or m a t i o n d u r i n g t h e p a s t d e c a d eo ro v e r ，t h e c o n c e p t s a n d t e c h n i q u e so nd a t am i n i n gh a v eb e e np r e s e n t e d ，a n ds o m e o ft h e mh a v eb e e nd i s c u s s e di n h i g h e rl e v e l sf ort h el a s t f e w y e a r s d a t am i n i n g i n v o l v e sa n i n t e g r a t i o n o f t e c h n i q u e sf r o md 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 e l 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 er i n g o b j e c t - o r i e n t e d m 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 a n d v i s u a l i z a t i o n e s s e n t i a l l y ，d a t am i n i n g i s h i g h - l e v e l a n a l y s i st e c h n o l o g y a n di th a sa s t r o n gp ur p o s e f o r b u s i n e s spr o f i t i n g u n l i k eo l t pa p p l i c a t i o n s ，d a t am i n i n g s h o u l dp r o v i d ei n d e p t hd a t aa n a l y s i sa n dt h es u p p o r t sf o r b u s i n e s sd e c i s i o n s l i k et h eo t h e rn e w t e c h n i q u e s ， h o w e v e r d a t am i n i n gm u s td e v e l o pg r a d u a l l yf r o mc o n c e p t c r e a t i o n ，a c c e p t e di m p o r t a n c e ，w i d ed i s c u s s i o n ，f e wu s a g e a t t e m p t st o a l a r g ea p p l i c a t i o n s ，m o s te x p e r t sc o n s i d e r i t a st h e p h a s e o fw i d ed i s c u s s i o n t o d a y i t s t i l ln e e d s t h e o r e t i cs t u d i e sa n d a l g o r i t h me x p l o r i n g t h o u g h s o m e r e s u l t sh a v eb e e na c h i e v e d ，m o r et h e o r e t i cp r o b l e m sa r e k e p ti no n g o i n gr e s e a r c h e s i na d d i t i o n d a t am i n i n gi sf r o m r e a i a p p l i c a t i o n s a n dm u s tc o m b i n ew i t ht h e s p e c i f i c b u s i n e s s a p p l i c a t i o nl o g i c t os o l v et h e s p e c i f i cp r o b l e m ， t h l sj sb e c a u s et h a td l f f e r e n tb u s i n e s sf i e l d sh a v ed i f f e r e n t m i n i n g n e e d sa n d t a r g e t s t h e s u c c e s s f u ld a t a m i n i n g s y s t e m s a r et h ee x c e l l e n tc o m b i n a t i o no fd a t a m i n i n g t e c h n i q u e sa n dt h eb u s i n e s sl o g i c ，r a t h e rt h a n t o o l st h a t ar ed e s i g n e dt om a k ed a t am i n i n ga p p l i c a t i o nd e v e l o p m e n t i i i j 匕京工业大学工掌博士掌位论文 c o n y e n i e n t a s s o c i a t i o nr u l e m i n i n g i sa ni m p or t a n tbr a n c h o fd a t a m i n i n gt h a t i th a so b t a l n e d m a n yv a l u a b l er e s u i t s b u tt h er es t i l lar ead e a lo fm o r ec h a l l e n g i n g p r o b l e m st o d i s c u s sf o rl ar g ed a t a b a s e s ，t h er e s e ar c ho n i m p r o v i n g t h e m i n i n gp e r f o r m a n c ea n d p r e c i s i o ni sn e c e s s a r y ，s o m a n yf o c u s e so ft o d a yo na s s o c i a t i o nr u l em i n i n gar ea b o u t n e wm i n i n gt h e o r i e s ，a l g o r i t h m s a n d i m p r o v e m e n tt oo l d m e t h o d s int h i s p a p e r ，t h e m a i nr e s e ar c h e si n v o l v et h e a p p l i c a t i o na r c h i t e c t u r eo fd a t am i n i n g ，t h em i n i n gt h e or i e s f ora s s o c i a t i o nr u i e sa n dt h e d e s i g n o fn e we f f i c i e n t a l g o r i t h m s t h i sp a p e ra n a l y z e d t h eb a s i c p r o c e s s i n g p h a s e so fd a t am i n i n go rk d d ，a n dg i v e st h ec o m p o n e n t s o fad a t am i n i n ga p p i i c a t i o ns y s t e ma n dt h e irf u n c t i o n s i n t h e or e t i cr e s e a r c h ，w ef ir s td e f i n es e to fi t e ms e q u e n c e s ， a n dg i v es o m eo p e r a t o r so nt h i s a l g e b r a l a t t i c e a p p l y i n g s u c ht h e o r e t i cr e s u l t s ，w ed e s i g na n a l g o r i t h mf o rm i n i n g a s s o c i a t i o nr u l e sc a l l e dl s s d m w h i c hi se f f i c i e n tw i t ho n e p a s s t ot h ed a t a b a s ea n dw i t h o u t l a r g e c a n d i d a t e s g e n e r a t e da n ds t o r e d f o r m i n i n gl ar g e s c a l ed a t a b a s e s ，i t i ss m ar t s t r a t e g yt o m a k eu s eo fc o n s t r a i n sf o ri m p r o v i n g d a t a q u a l i t y a n d r e d u c i n g d a t a c a p a b i l i t y t h i sp a p e r i n t r o d u c e st h epr o b l e mo fd a t am i n i n gb a s e do nt e m p o r a l c o n s t r a i n s w ec r e a t et w on e w o p e r a t or so n t e m p o r a l i n t er v a l s p a c ea n dd e s i g na na l g o r i t h mc a l l e dt i s s d mb y m a k i n ga d v a n c eo ft h e s eo p e r a t o r s t i s s - d mm a y b es e e n a sa n i m p r o v e m e n t a l g o r i t h mt oi s s d m w h i c hc a n p r o c e s sm or es c a l ed a t a b a s e s i nf a c t ，r e c e n tr e s e ar c h e s h a v ep a i dm o r ea t t e n t i o nt or e d u c et h en u m b ero fp a s s e s o v e r d a t a b a s e s ( i 0c o s t ) ，m e m o r yu s a g e a n dc p u o v e r h e a d t h i s p a p e r a l s o g i v e s a n a l g o r i t h m c a l l e d p i s s d mw h i c h e m p l o y sd a t ap ar t i t i o n i n gt e c h n i q u e a n d o n l yh a st w op a s s e so v e rd a t a b a s e s e x p e r i m e n t a lr e s u l t s s h o w e dt h a tt h e s e a l g o r i t h m s h a v e h i g h e rm i n i n g e f f i c i e n c y i ne x e c u t i o n t i m e ，m e m o r yu s a g e a n dc p u u t i i i z a t i o nt h a nm o s tc ur r e n to n e sl i k ea pr i o r i n c o n c l u s i o n ，t h i s p a p e r a n a l y z e s ar c h i t e c t ur eo fd a t a m i n i n gs y s t e m s ，c r e a t e s a p p i i c a t i o n n e wm i n i n g t h e or e t i cm o d e l s ，a n d d e s i g a s as er i e so fn e wa l g or i t h m s b a s e do ns u c ht h e or i e s k e yw o r d s ：d a t am i n i n g ，k d d ( k n o w l e d g ed i s c o v er y i n d a t a b a s e s ) ，a s s o c i a t i o n r u l e s ，s e to f i t e m s e q u e n c e s ， t e m p o r a lc o n s t r a i n t ，d a t ap a r t i t i o n i n g v 第1 章绪论 数据挖掘( d a t am i n i n g ) 是一个多学科交叉研究领域，它融 合了数据库( d a t a b a s e ) 技术、人工智能( a r t i t i c i a l i 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 ) 、面向对象 方法( 0 b j e c t 一0 r i e n t e d m e t h o d ) 、信息检索( i n f o r m a t i o n r 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 ) 等最新技术的研究成果。经过 十几年的研究，产生了许多新概念和方法。特别是最近几年，一些 基本概念和方法趋于清晰，它的研究正向着更深入的方向发展。数 据挖掘之所以被称为未来信息处理的骨干技术之一，主要在于它以 一种全新的概念改变着人类利用数据的方式。二十世纪，数据库技 术取得了决定性的成果并且已经得到广泛的应用。但是，数据库技 术作为一种基本的信息存储和管理方式，仍然以联机事务处理 ( o l t p ：o n l i n et r a n s a c t i o np r o c e s s i n g ) 为核心应用，缺少对 决策、分析、预测等高级功能的支持机制。众所周知，随着数据库 容量的膨胀，特别是数据仓库( d a t aw a r e h o u s e ) 以及w e b 等新 型数据源的日益普及，联机分析处理( 0 l a p ：o n l i n ea n a l y t i c p r o c e s s i n g ) 、决策支持( d e c i s i o ns u p p o r t ) 以及分类 ( c l a s s i n g ) 、聚类( c l u s t e r i n g ) 等复杂应用成为必然。面对这 一挑战，数据挖掘和知识发现( k n o w l e d g ed i s c o v e r y ) 技术应运。 而生，并显示出强大的生命力。数据挖掘和知识发现使数据处理技 术进入了一个更高级的阶段。它不仅能对过去的数据进行查询，并 且能够找出过去数据之间的潜在联系，进行更高层次的分析，以便 更好地作出理想的决策、预测未来的发展趋势等。 1 1 研究背景 经过十几年的研究和实践，数据挖掘技术已经吸收了许多学 科的最新研究成果而形成独具特色的研究分支。勿容置疑，数据挖 掘研究和应用具有很大的挑战性。象其它新技术的发展历程一样， 数据挖掘也必须经过概念提出、概念接受、广泛研究和探索、逐步 应用和大量应用等阶段。从目前的现状看，大部分学者认为数据挖 掘的研究仍然处于广泛研究和探索阶段。一方面，数据挖掘的概念 已经被广泛接受。猩理论上，一批具有挑战性和前瞻性的问题被提 爨，吸弓l 越来越多静研究者。数据挖擒懿概念瓢二卡藿纪，十年代 被提出后，其经济价值已经显现出来，藤且救众多赢渡厂家所雄 崇，形成初步的市场。另一方面。县前的数据挖掘系统研制也决不 怒象一些商家为了鬟传自己商品新说的那样神奇，仍有许多闯题需 要硬究积撵索。把爨蔻数据摭握憋研突理状撼述梵游逡( c h a s m ) 阶段鼹比较准确的。所谓c h a s m 阶段是说数据挖掘技术在广泛 被应用之前仍有许多“满沟”需要攀越。例如，就黼前商家推出的 数据挖掘系绞褥言，宪镪熬楚一臻逮鼹鳃辕魏瑟发王吴。这攘工矮 只能给那些熟悉数据挖掘技术的专家兢高级技术人员使用，仅对专 业人员开发对应的应用起别加速或横向解决方案( h o r i z o n t a l s o l u t i o n ) 靛佟用。毽楚，数据撼掘来自予裔娩痰麓，两裔馥应羯 又会出于成用的领域不同面存在很大豢冥。大多数学者赞成这样的 观点：数据挖掘在商业上的成功不能期望通用的辅助开发工典，雨 瘦该燕数据挖擒概念与特定领域商盈逻辑相缩合豹缀淘解决方案 ( v e r t i c a ls o l u t i o n ) 。 分析目前的研究和_ 暾用现状，数据挖掘在如下几个方面需要重 点开袋工作： i 数据挖握技术冬特焱囊妊逻辑熬警港集成瓣题。宅毽摇领 域知识对行业或企业知识挖撅的约束与指捋、商业逻辑有 机嵌入数据挖掘过稷等关键课题。 羹 数据挖摇技术冬特定数括存镣类攫熬淹瘟 瓣震。不阏煞数 掇存储方式会影响数据挖掘的具体实现机制、啜标定位、 技术有效性等。指望一种通用的j 藏用模式邋合所有的数据 存储方式下发现有效鲡谈是不现实的。因诧，钎对不蠢数 搬存镶类型的特点，进褥针对性磺究是曩翦滚褥露鼠也是 将来一段时间所必须砸对的闭题。 数据挖掘系统的稳絮与交互式挖弼技术。擞然经过多年的 搽索，数据挖掇系绞匏豢本撼絮粒过理已经趋予明耀，健 怒受应用领域、挖掘数据类型以及知识表达模式等的影 响，在具体的实现枫制、技术路线以凝各阶段域部件( 如 数据清洗、矮谈形藏、模式译蘩祷) 豹功缝定经等穷霭仍 鬻细化和深入研究。由予数据挖掘是在大薰的源数据集中 发现潜在的、攀先并不知道的知识，鞠此和用户交甄式避 静探索性挖掘爨必然鹃。这耱交曩霹能发篷在数据挖掘豹 务个不同阶段，从不冠角度或不阏牲发进褥交曩。所以琵 第l 章j i e - 好的交互式挖掘( i n t e r a c t i o n m i n i n g ) 也是数据挖掘系 统成功的前提。 _ 数据挖掘语言与系统的可视化问题。对o l t p 应用来说， 结构化查询语言s q l 已经得到充分发展，并成为支持数据 库应用的重要基石。但是，对于数据挖掘技术而言，由于 诞生的较晚，加之它相比o l t p 应用的复杂性，开发相应 的数据挖掘操作语言仍然是一件极赋挑战性的工作。可视 化要求已经成为目前信息处理系统的必不可少技术。对于 一个数据挖掘系统来说，它更是重要的。可视化挖掘除了 要和良好的交互式技术结合外，还必须在挖掘结果或知识 模式的可视化、挖掘过程的可视化以及可视化指导用户挖 掘等方面进行探索和实践。 - 数据挖掘理论与算法研究。经过十几年的研究，数据挖掘 已经在继承和发展相关基础学科( 如机器学习、统计学 等) 已有成果方面取得了可喜的进步，探索出了许多独具 特色的理论体系。但是，这决不意味着挖掘理论的探索已 经结束，恰恰相反它留给了研究者丰富的理论课题。一方 面，在这些大的理论框架下有许多面向实际应用目标的挖 掘理论等待探索和创新。另一方面，随着数据挖掘技术本 身和相关技术的发展，新的挖掘理论的诞生是必然的，而 且可能对特定的应用产生推动作用。新理论的发展必然促 进新的挖掘算法的产生，这些算法可能扩展挖掘的有效 性，如针对数据挖掘的某些阶段、某些数据类型、大容量 源数据集等更有效：可能提高挖掘的精度或效率；可能融 合特定的应用目标，如c r m 、电子商务等。因此，对数 据挖掘理论和算法的探讨将是长期而艰巨的任务。 从上面的叙述，可以看出数据挖掘研究和探索的内容是及其 丰富和具有挑战性的。我们正是在这样的背景下，在以往的研究和 各类基金的支持下，开展相关研究工作的。 1 2 拟解决的问题 作为博士论文，我们在收集和整理大量的相关资料，弄清相关 的理论、方法、算法、体系结构( 原型系统) 等基础上，集中选取 了下面几个问题开展相关工作： 数据挖掘过程和系统构架研究。在分析现有的数据挖掘系 统( 原型系统) 的体系结构基础上，系统化研究了数据挖 掘系统的基本过程和功能部件。这些研究包括从数据挖掘 的基本过程来探讨系统应具备的主要功能部件及其相互联 系；不同的源数据类型对数据挖掘系统的功能部件要求； 不同的应用目标对数据挖掘系统的功能部件要求；数据挖 掘系统的主要功能部件的实现机制等。 数据挖掘理论探索。如前所述，数据挖掘已经建立了许多 独具特色的挖掘理论体系，但是不论是从应用范围、有效 性以及适应性等方面仍需新的挖掘理论的探索。因此，本 文对关联规则( a s s o c i a t i o nr u l e ) 挖掘理论和模型进 行了研究，建立了项目序列集格空间和基于项目序列集操 作的关联规则挖掘模型等。 关联规则挖掘算法设计。关联规则挖掘是数据挖掘中研究 较早而且至今仍最活跃的研究分支之一。影响关联规则的 挖掘效率的因素主要有数据库扫描的l ，o 代价、内存的需 求、c p u 的时间花费等。目前的关联规则挖掘算法仍然 需要在这些方面加以创新或改进。因此，我们选取了关联 规则挖掘算法进行了集中研究和实现，并通过系列的算法 设计和实现来验证我们新的挖掘理论和积累研制数据挖掘 系统的经验。 1 3 创新性工作 本文的创新性工作集中在数据挖掘理论和关联规则挖掘算法 设计两个方面。 1 3 1 数据挖掘理论研究 大多数文献中使用的项目集( i t e m s e t ) 是普通的集合概念 2 i 。我们使用术语“项目序列( i t e m s e q u e n c e ) ”来替代其它文 献中出现的“项目集”。所谓项目序列是指项目集中的元素是按特 定标准( 如出现次数、字典排序) 进行有序排列的。因此，我们首 次引入的项目序列集( s e to fi t e m s e q u e n c e s ) 概念可以用来表 示一类特定的项目序列集合( 如频繁项目序列集) 。 本文主要的理论研究和成果为： 第1 章绪论 ( 1 ) 基于项目序列集操作的挖掘模型 我们建立了项目序列集的代数空间描述，并探讨了在这个空间 上的基本操作算子。在此基础上，讨论了基于项目序列集操作的数 据挖掘模型( 详见第4 章) 。 ( 2 ) 约束条件下的数据挖掘理论 毫无疑问，引进约束条件可以加速数据挖掘的过程。但是，约 束条件的引入，必须解决诸如适合数据挖掘的约束条件的形式化表 示以及约束条件在数据挖掘特定阶段的使用方式等。本文针对时态 约束条件下的数据挖掘理论问题进行了探索。在时态区间代数空间 上定义了两个新的时态区间变量操作( 时态交n 和时态并t l t ) 。基 于这样的时态约束条件下的数据挖掘理论框架，我们可以扩展数据 挖掘工作到包括数据过滤( d a t af i l t r a t i n g ) 、时态区间合并等数据预 处理在内的更广泛的范畴中去( 详见第5 章) 。 ( 3 ) 数据分割下的数据挖掘理论 随着数据库容量的增大，使得通过对源数据集的分割来处理大容量 数据库的数据挖掘问题成为必要。本文就数据分割下的数据挖掘问 题进行了讨论，引入局部频繁项目序列集f l o c a lf r e q u e n ts e to f i t e m s e q u e n c e s ) 和全局项目序列集( g l o b a lf r e q u e n t s e to f i t e m s e q u e n c e s ) 等概念，并解决了局部频繁项目序列集和全局频繁项 目序列集转换等问题( 详见第6 章) 。 1 3 2 关联规则挖掘算法设计与实现 把上面的数据挖掘理论应用到关联规则的发现中，我们完成了 相应算法的设计，并且通过理论分析和实验模拟讨论了算法的性能。 第4 章介绍了基于项目序列集操作的i s s d m 算法。它是一个一次数 据库扫描并且不使用侯选集的高效算法。为了增强对大容量数据库 挖掘的适应性和可用性，第5 章设计了时态约束下的t i s s d m 算法。 它是对i s s d m 算法的改进，实验证明它具有较好的数据过滤和区间 合并效率，因而能在同样的处理环境下挖掘更大容量的数据库( 比 i s s d m ) 。第6 章提出了另一个i s s - d m 的改进算法p i s s d m 。它通 过对数据库的分割，减少了对内存和c p u 等系统资源的占用，而且 可以在两次数据库扫描的情况下完成挖掘工作。 j 匕京工业大学工学博士学位论文 1 4 本章小节 本章介绍了数据挖掘研究的意义和技术背景、论文的选题依 据、研究背景以及我们的主要研究内容等。数据挖掘作为二十世纪 信息处理的骨干技术之一，正以一种全新的概念改变着我们利用数 据的方式。经过十几年的研究和实践，数据挖掘技术已经融合了许 多学科的最新研究成果而形成独具特色的研究分支。目前的数据挖 掘研究正处于蓬勃发展时期，有许多具有挑战性的课题被提出。数 据挖掘的研究内容是极其丰富的。作为搏士论文，我们在充分了解 基本概念和主要技术发展状况的前提下，有选择地进行了重点研究。 这些研究包括数据挖掘系统的体系结构、关联规则挖掘理论和算法 等。 - 6 - 第2 章数据挖掘技术 数据挖掘作为一个只有十几年研究历史的较新研究领域，许 多概念和技术是逐步发展起来的。因此，本章将系统地介绍相关的 概念和技术，并力求从不同视点和流派来阐述数据挖掘的重要概 念、发展和应用情况。在2 1 节，我们介绍了数据挖掘技术产生的 商业和技术背景；在2 2 节，我们从不同视点阐述了数据挖掘的概 念和主要理论构架；在2 3 节，我们从多种角度对数据挖掘系统的 分类问题进行了概括；在2 4 节，我们从知识表示模式角度出发， 归纳了主要的数据挖掘技术及其研究成果；2 5 节对不同源数据组 织形式下的数据挖掘技术的特点和策略进行了剖析：2 6 节分析了 数据挖掘技术的应用现状和发展趋势。 2 1 数据挖掘技术的产生背景 2 1 1 数据挖掘技术的商业需求分析 数据挖掘之所以吸引专家学者的研究兴趣和引起商业厂家的 广泛关注，主要在于大型数据系统的广泛使用和把数据转换成有用 知识的迫切需要。6 0 年代，为了适应信息的电子化要求，信息技 术一直从简单的文件处理系统向有效的数据库系统变革。7 0 年 代，数据库系统的三个主要模式一一层次、网络和关系型数据库的 研究和开发取得了重要进展。8 0 年代，关系型数据库及其相关的 数据模型工具、数据索引及数据组织技术被广泛采用，并且成为了 整个数据库市场的主导。8 0 年代中期开始，关系数据库技术和新 型技术的结合成为数据库研究和开发的重要标志。从数据模型上 看，诸如扩展关系、面向对象、对象关系( o b j e c t r e l a t i o n ) 以 及演绎模型等被应用到数据库系统中。从应用的数据类型上看，包 括空间、时态、多媒体以及w e b 等新型数据成为数据库应用的重 要数据源。同时，事务数据库( t r a n s a c t i o nd a t a b a s e ) 、主动数 据库( a c t i v ed a t a b a s e ) 、知识库( k n o w l e d g eb a s e ) 、办公信 息库( i n f o r m a t i o nb a s e ) 等技术也得到蓬勃发展。从数据的分布 角度看，分布式数据库( d i s t r i b u t e dd a t a b a s e ) 及其透明性、并 发控制、并行处理等成为必须面对的课题。进入9 0 年代，分布式 数据库理论上趋于成熟，分布式数据库技术得到了广泛应用。目 前，由于各种新型技术与数据库技术的有机结合，使数据库领域中 的新内容、新应用、新技术层出不穷，形成了庞大的数据库家族。 但是，这些数据库的应用都是以实时查询处理技术为基础的。从本 质上说，查询是对数据库的被动使用。由于简单查询只是数据库内 容的选择性输出，因此它和人们期望的分析预测、决策支持等高级 应用仍有很大距离。 新的需求推动新的技术的诞生。数据挖掘的灵魂是深层次的 数据分析方法。数据分析是科学研究的基础，许多科学研究都是建 立在数据收集和分析基础上的。同时在目前的商业活动中，数据分 析总是和一些特殊的人群的高智商行为联系起来，因为并不是每个 平常人都能从过去的销售情况预测将来发展趋势或作出正确决策 的。但是，随着一个企业或行业业务数据的不断积累，特别是由于 数据库的普及，人工去整理和理解如此大的数据源已经存在效率、 准确性等问题。因此，探讨自动化的数据分析技术，为企业提供能 带来商业利润的决策信息而成为必然。 事实上，数据( d a t a ) 、信息( i n f o r m a t i o n ) 和知识 ( k n o w l e d g e ) 可以看作是广义数据表现的不同形式。毫不夸张 地说，人们对于数据的拥有欲是贪婪的，特别是计算机存储技术和 网络技术的发展加速了人们收集数据的范围和容量。这种贪婪的结 果导致了“数据丰富而信息贫乏( d a t ar i e h & i n f o r m a t i o n p o o r ) ”现象的产生。数据库是目前组织和存储数据的最有效方 法之一，但是面对日益膨胀的数据，数据库查询技术已表现出它的 局限性。直观上说，信息或称有效信息是指对人们有帮助的数据。 例如，在现实社会中，如果人均日阅读时间在3 0 分钟的话，一个 人一天最快只能浏览一份2 0 版左右的报纸。如果你订阅了1 0 0 份 报纸，其实你每天也不过只阅读了一份而已。面对计算机中的海量 的数据，人们也处于同样的尴尬境地，缺乏获取有效信息的手段。 知识是一种概念、规则、模式和规律等。它不会象数据或信息那么 具体，但是它却是人们一直不懈追求的目标。事实上。在我们的生 活中，人们只是把数据看作是形成知识的源泉。我们是通过正面的 或反面的数据或信息来形成和验证知识的，同时又不断地利用知识 来获得新的信息。因此，随着数据的膨胀和技术环境的进步，人们 对联机决策和分析等高级信息处理的要求越来越迫切。在强大的商 业需求的驱动下，商家们开始注意到有效地解决大容量数据的利用 问题具有巨大的商机；学者们开始思考如何从大容量数据集中获取 第2 章数据挖掘技术 有用信息和知识的方法。因此，在二十世纪八十年代后期，产生了 数据仓库和数据挖掘等信息处理思想。 2 1 2 数据挖掘产生的技术背景分析 任何技术的产生总是有它的技术背景的。数据挖掘技术的提 出和普遍接受是由于计算机及其相关技术的发展为其提供了研究和 应用的技术基础。 归纳数据挖掘产生的技术背景，下面一些相关技术的发展起 到了决定性的作用： 数据库、数据仓库和i n t er n e t 等信息技术的发展； 一计算机性能的提高和先进的体系结构的发展； 统计学和人工智能等方法在数据分析中的研究和应用。 数据库技术从二十世纪8 0 年代开始，已经得到广泛的普及和 应用。在关系型数据库的研究和产品提升过程中，人们一直在探索 组织大型数据和快速访问的相关技术。高性能关系数据库引擎以及 相关的分布式查询、并发控制等技术的使用，已经提升了数据库的 应用能力。在数据的快速访问、集成与抽取等问题的解决上积累了 经验。数据仓库作为一种新型的数据存储和处理手段，被数据库厂 商普遍接受并且相关辅助建模和管理工具快速推向市场，成为多数 据源集成的一种有效的技术支撑环境。另外，i n t e r n e t 的酱及也为 人们提供了丰富的数据源。据说，在美国电视达到5 0 0 0 万户大约 用了15 年，而i n t c r n e t 上网达到5 0 0 0 万户仅用了4 年。而且 i n t c r n e t 技术本身的发展，已经不光是简单的信息浏览，以w e b 计算为核心的的信息处理技术可以处理i n t e r n e t 环境下的多种信息 源。因此，人们已经具备利用多种方式存储海量数据的能力。只有 这样，数据挖掘技术才能有它的用武之地。这些丰富多彩的数据存 储、管理以及访问技术的发展，为数据挖掘技术的研究和应用提供 了丰富的土壤。 计算机芯片技术的发展，使计算机的处理和存储能力日益提 高。大家熟知的摩尔定律告诉我们，计算机硬件的关键指标大约以 每l8 个月翻一番的速度在增长，而且现在看来仍有日益加速的趋 势。随之而来的是硬盘、c p u 等关键部件的价格大幅度下降，使 得人们收集、存储和处理数据的能力和欲望不断提高。经过几十年 的发展，计算机的体系结构，特别是并行处理技术已经逐渐成熟和 普遍应用，并成为支持大型数据处理应用的基础。计算机性能的提 高和先进的体系结构的发展使数据挖掘技术的研究和应用成为可 能。 历经了十几年的发展，包括基于统计学、人工智能等在内的 理论与技术性成果已经被成功地应用到商业处理和分析中。这些应 用从某种程度上为数据挖掘技术的提出和发展起到了极大地推动作 用。数据挖掘系统的核心模块技术和算法都离不开这些理论和技术 的支持。从某种意义讲，这些理论本身发展和应用为数据挖掘提供 了有价值的理论和应用积累。数理统计是一个有几百年发展历史的 应用数学学科。然而它和数据库技术的结合性研究应该说最近十几 年才被重视。以前的基于数理统计方法的应用大多都是通过专用程 序来实现的。我们知道，大多数的统计分析技术是基于严格的数学 理论和高超的应用技巧的，这使得一般的用户很难从容地驾驭它。 数据挖掘技术是数理统计分析应用的延伸和发展，假如人们利用数 据库的方式从被动地查询变成了主动发现知识的话，那么概率论和 数理统计这一古老的学科可以为我们从数据归纳知识一一数据挖掘 技术提供理论基础。 人工智能是计算机科学研究中争议最多但是仍始终保持强大 生命的研究领域。机器学习应该说是得到了充分的研究和发展，并 且数据挖掘技术继承了机器学习解决问题的思想。专家系统 ( e x p e r ts y s t e m ) 曾经被认为人工智能向着实用性方向发展的最 有希望的技术，但是，这种技术也逐渐表现出投资大、主观性强、 应用面窄等致命弱点。例如，知识获取被普遍认为是专家系统研究 中的瓶颈问题。另外，由于专家系统是主观整理知识，因此这种机 制不可避免地带有偏见和错误。数据挖掘继承了专家系统的高度实 用性特点，并且以数据为基本出发点，客观地挖掘知识。因此，可 以说，数据挖掘研究在继承已有的人工智能相关领域的研究成果的 基础上，摆脱了以前象牙塔式研究模式，真正开始客观地从数据集 中发现蕴藏的知识。 2 2 数据挖掘概念 2 2 1 从商业角度看数据挖掘技术 数据挖掘从本质上说是一种新的商业信息处理技术。数据挖 掘技术把人们对数据的应用，从低层次的联机查询操作，提高到决 策支持、分析预测等更高级应用上。它通过对这些数据进行微观、 1 0 - 中观乃至宏观的统计、分析、综合和推理，发现数据间的关联性、 未来趋势以及一般性的概括知识等，这些知识性的信息可以用来指 导高级商务活动。 从决策、分析和预测等高级商业目的看，原始数据只是未被 开采的矿山，需要挖掘和提炼才能获得对商业目的有用的规律性知 识。这正是数据挖掘这个名字的由来。所以，以蔚监嗜度：看，藏密 挖掘就是按企业的既定业务目标对大量的金业数据进行深瑟次分 葫戳揭示稳藏的、未知的撬律性并将其模型纯扶两支持商业决策 抒动。从商业应用角度刻画数据挖掘，可以使我们更全面的了解数 据挖掘的真正含义。它有别于机器学习等其它研究领域，从它的提 出之日起就具有很强的商业应用目的。同时，数据挖掘技术只有面 向特定的商业领域才有应用价值。数据挖掘并不是要求发现放之四 海而皆准的真理，所有发现的知识都是相对的，并且对特定的商业 行为才有指导意义。 2 2 2 数据挖掘的技术含义 谈到数据