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

摘要 随着数据库技术的迅速发展及其广泛应用，在数据库中积累的数据量越来越多。激 增的数据背后隐藏着许多重要的信息，人们希望能够在已有的大量数据的基础上进行科 学研究、商业决策或企业管理等更高层次的分析，从中提取有价值的信息，从而为管理 和决策提供依据。数据挖掘就是从大量的、不完全的、有噪声的、模糊的数据中，提取 隐含的、人们事先不知道的、但又是潜在有用的信息和知识的过程。 本毕业设计的主要目标是研究发现多维数据间的关联性的有效方法。基于数据仓库 和o l a p 的多维数据分析法是以统计分析的方法对多维数据进行分析，而多维关联挖掘 算法是用知识发现的方法分析多维数据之间的关联性。本论文从这两方面进行了研究。 本文首先对基于数据仓库和o l a p 的多维数据分析法进行了研究，主要有数据仓库 的建模方法，利用o l a p 对数据仓库中的多维数据进行分析的方法。并在此研究的基础 上进行了高校毕业生就业状况分析数据仓库模型的设计，并利用o l a p 提供的切片、切 块、上卷和下钻等方法对高校毕业生就业状况进行了分析。 其次，本文在对关联挖掘方法及其发展状况进行了研究的基础上，提出了一个基于 s q l 查询的多维关联规则挖掘算法，该算法利用s q l 新标准中的c u b e 运算符，并结合了 s q l 强大的查询功能，能够对一定数据量的多维数据集进行高效的多维关联挖掘。为实现 对更大数据集的有效挖掘，采取分块挖掘的方式对算法进行了改进，本文对算法及其设 计思想进行了详细的论述，并给出了对算法的一些测试结果。分析和实验表明，算法简 单，易于实现，无需多遍扫描挖掘数据集，挖掘效率高。 最后，为便于用户利用本算法进行多维关联挖掘，还将s q ls e r v e r 数据库的强大 数据处理功能和c # 的面向对象的功能相结合，设计开发了可视化多维关联挖掘工具。 关键词：数据仓库o l a p多维数据挖掘关联规则c u b e a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fd a t a b a s et e c h n o l o g ya n di t sw i d ea p p l i c a t i o n ，t h ea m o u n t o fd a t ai sa c c u m u l a t e di nt h ed a t a b a s e t h e r ea r em a n yi m p o r t a n tm e s s a g e sb e h i n dt h e i n c r e a s e dd a t a p e o p l eh o p et od ot h eh i g h e rl e v e la n a l y s i so nt h es c i e n t i f i cr e s e a r c h ，b u s i n e s s d e c i s i o no re n t e r p r i s em a n a g e m e n tb a s e do nt h ev a s ta m o u n to fd a t a ，s o 弱t oo b t a i nt h e v a l u a b l ei n f o m a t i o na n dp r o v i d et h eg i s tf o rt h em a n a g e m e n ta n dd e c i s i o n m a k i n g d a t a m i n i n gi s t op i c k u pi m p l i e dm a s s a g e st h a tp e o p l ed on o tk n o wi na d v a n c ef r o mt h e i n c o m p l e t e ，n o i s e ，f u z z yd a t a ，b u ti sp o t e n t i a l l yu s e f u li n f o r m a t i o na n dk n o w l e d g ep r o c e s s t h em a i no b j e c t i v eo ft h i sp a p e ri st os t u d ya ne f f e c t i v ew a y t of o u n dt h ea s s o c i a t i o no f m u l t i d i m e n s i o n a ld a t a m u l t i d i m e n s i o n a ld a t aa n a l y s i sw h i c hb a s e do nt h ed a t aw a r e h o u s e a n do l a pi st oa n a l y s i sm u l t i d i m e n s i o n a ld a t ab yt h em e t h o do fs t a t i s t i c a la n a l y s i s ，a n d m u l t i d i m e n s i o n a la s s o c i a t i o nm i n i n ga l g o r i t h mi st oa n a l y s i sm u l t i d i m e n s i o n a ld a t ab yt h e m e t h o do fk n o w l e d g ed i s c o v e r y t h i sp a p e rw a ss t u d i e df r o mt h e s et w oa s p e c t s i nt h i sp a p e r , f i r s t l y , t h ea u t h o rd o e st h es t u d yo fm u l t i - d i m e n s i o n a ld a t aa n a l y s i sw h i c h b a s e do nd a t aw a r e h o u s ea n do l a p t h em a i np a r ti sd a t aw a r e h o u s em o d e l i n g ，a n dt h e m e t h o do fu s i n go l a pa n a l y z i n gm u l t i d i m e n s i o n a ld a t ai nt h ed a t aw a r e h o u s e o nt h eb a s i s 0 ft h es t u d y ，t h ea u t h o rm a k e sam o d e lo f “a n a l y s i ss y s t e mw h i c hb a s e do nw a r e h o u s ea n d o i _ a pt oa n a l y s i st h ee m p l o y m e n ts i t u a t i o no fc o l l e g eg r a d u a t e sd a t at f , a n da d o p ts l i c e ，d i c e ， r o l l u pa n dd r i l l d o w nt oa n a l y s e st h ee m p l o y m e n ts i t u a t i o no fc o l l e g eg r a d u a t e s ； s e c o n d l y , i nt h i sp a p e r , t h ea u t h o rm a k e sas t u d ya b o u ta s s o c i a t i o nm i n i n gm e t h o da n d t h ed e v e l o p m e n ts i t u a t i o n o nt h eb a s i so fi t ，t h ea u t h o rp r o v i d e st h em u l t i d i m e n s i o n a l a s s o c i a t i o nr u l em i n i n ga l g o r i t h mb a s e do nt h es q li tu s e sc u b eo p e r a t o r sa n dc o m b i n e s w i t hs q l p o w e r f u lq u e r i e sf u n c t i o n ，a n di tc a n m i n eac e r t a i nn u m b e ro fd a t as e t se f f i c i e n t l y i no r d e rt om a k ee f f e c t i v em i n i n ga b o u tg r e a t e rd a t as e t s ，a l g o r i t h mi si m p r o v e d i td i v i d e st h e l a r g ed a t as e ti n t os m a l l e ro n e s i nt h i sp a p e r , t h ea l g o r i t h ma n dd e s i g ni d e aa r ed i s c u s s e di n d e t a i l ，a n dg i v e ss o m eo ft h ea l g o r i t h mt e s tr e s u l t s a n a l y s i sa n de x p e r i m e n t ss h o wt h a t a l g o r i t h mi ss i m p l ea n de a s yt or e a l i z e ，w i t h o u ts c a n n i n gm i n i n gd a t as e t sm a n yt i m e s ，a n d h a v eh i g hm i n i n ge f f i c i e n c y f i n a l l y , i no r d e rt om a k et h eu s e r se a s i l yu s et h em u l t i - d i m e n s i o n a la s s o c i a t i o nm i n i n g a l g o r i t h mt om i n em u l t i m e n t i o n d a t a ，t h ea u t h o rd e s i g n sm u l t i d i m e n s i o n a la s s o c i a t i o n m i n i n gt o o l sb a s e do nt h ep o w e r f u l d a t ap r o c e s s i n go fs o ls e r v e rd a t a b a s ea n dc 襻 o b j e c t - o r i e n t e df u n c t i o n a li n t e g r a t i o n k e yw o r d s ：d a t aw a r e h o u s e ，o l a p , m u l t i - d i m e n s i o n a ld a t am i n i n g ，a s s o c i a t i o nr u l e s ， c u b e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得天津理工大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 、，7 学位论文作者签名：二矢l 、少墨签字日期： d 召年f 月77 日 学位论文版权使用授权书 本学位论文作者完全了解 墨盗墨兰盘堂有关保留、使用学位论文 的规定。特授权墨盗墨兰盘堂 可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 弛：关7 秀名： 角物 l 签字日期：众多年月? c 7 日 签字日期：峥群1月? 日 | 第一章绪言 1 1 本课题研究背景 第一章绪言 数据库的应用己经进入了成熟的阶段，数据库的应用迅速渗透到了社会数据处理的 各个层面。由于数据量的不断扩张，现今数据库的应用己经从原始的数据收集、存储以 及对联机事务处理的支持转向了大规模数据的重组、联机分析处理、数据仓库以及与此 相关的数据库知识发现( 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 a t am i n i n g ) 等等更 深层次利用数据的阶段。 k d d 一词是在1 9 8 9 年8 月于美国底特律市召开的第一届k d d 国际学术会议上正式形 成的。1 9 9 5 年在加拿大召开了第一届知识发现和数据挖掘国际学术会议心1 。由于数据库 中的数据被形象地喻为矿床，因此数据挖掘一词很快流传开来。数据挖掘是k d d 整个过 程中的核心部分，k d d 的过程也是围绕数据挖掘展开的。 目前比较经典的数据挖掘技术啼3 有：基于信息论的决策树方法i d 3 和i b l e ，基于集 合论的粗糙集方法，关联规则发现方法a p r i o r i 和f p 算法，公式发现的b a c o n 系统， 仿生物学的神经网络和遗传算法等。 关联规则挖掘的概念是r a k e s ha g r a w a l 等在1 9 9 3 年首次提出的，并给出了基于数 据库多趟扫描的a i s 算法h 3 ，之后a g r a w a l 又提出了改进的a i s 算法a p r i o r i ， a p r i o r i t i d 及a p r i o r ih y b r i d 晦。，成为众多关联规则算法的基础。然而在正如文献 5 和文献 6 所示试验结果，类a p r i o r i 算法在最初的两次数据库扫描时开销很大，导致 了算法的效率瓶颈出现。最近也有独立于a g r a w a l 的频集方法的工作“1 ，以避免大项集 方法的一些缺陷，探索挖掘关联规则的新方法。同时随着o l a p 技术的成熟和应用，将 o l a p 和关联规则结合哺儿刀也成了一个重要的方向。也有一些工作注重于对挖掘到的模式 的价值进行评估，他们提出的模型建议了一些值得考虑的研究方向。 国内对关联规则挖掘的研究还处于起步阶段，中科院计算所的欧阳为民首先引入国 外关联规则挖掘的概念和思想，并在基于a p r i o r i 算法的基础上提出了时态约束的关联 规则h 1 。近两年，国内的部分学者对关联规则挖掘进行了大量的研究，但提出的算法也 都是基于国外所提出算法的改进算法心1 。目前国内从事数据关联规则挖掘研究的人员主 要在大学，也有部分在研究所或公司。所涉及的研究领域很多，一般集中于学习算法的 研究、关联规则挖掘的实际应用以及关联规则挖掘理论方面的研究。如，中科院计算机 研究所的智能信息处理重点实验室研制开发的多策略数据挖掘平台m s m i n e r 系统，将关 联规则挖掘算法集成到此系统中。复旦大学研制开发的a r m i n e r 系统n 引，是专门针对智 能化的p o s 系统开发的关联规则挖掘工具，此系统的关联规则挖掘算法是基于a p r i o r i 的改进算法。虽然己经取得了相当的成功，但目前在处理极大数据量时，如何提高算法 第一章绪言 效率的问题：对于挖掘迅速更新数据的挖掘算法的进一步研究；在挖掘的过程中，提供 一种与用户进行交互的方法，将用户的领域知识结合在其中等都是尚待研究和解决的问 题。 1 2 本文研究的目的和意义 当前数据挖掘已经从传统的关系型数据库的挖掘发展到文本、多媒体、w e b 的数据 挖掘。数据挖掘已经成为数据仓库、决策支持系统的重要组成部分3 。大多数的研究 者对于维内、单层挖掘算法的研究相对较多，但是近年来人们对于在关系数据库或数据 仓库中存储的具有大规模、多维、多层特性挖掘的应用，尤其是关联规则挖掘应用的需 求日益增强。实现在一定范围内的多维关联规则研究、满足人们一定范围内的对多维属 性的要求，就是本课题研究的意义之所在。 本课题研究的是多维关联挖掘算法，主要目标是研究发现多维数据间的关联性的方 法。基于数据仓库和o l a p 的多维数据分析法是以统计分析的方法对多维数据进行分析， 而多维关联挖掘算法是用知识发现的方法分析多维数据之间的关联性。本文对基于数据 仓库和o l a p 的多维数据分析法和多维关联规则挖掘算法进行了研究。 1 3 本文的主要研究内容和结构安排 数据挖掘是数据处理的一个新的热点和前沿研究领域，它的研究目标是采用有效的 算法，从大量现有的数据集合中发现并找出最初未知，但最终可理解的有用知识，并用 简明的方式显示出来。关联规则( a s s o c i a t i o nr u l e s ) 挖掘是数据挖掘领域中一个重要 的研究方向。多维关联规则( m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e s ) 不仅考虑项集之 间的关联，而且将事件发生的环境信息( 如时间、位置等) 考虑进去。从而为传统规则挖 掘赋予新的含义，提供更为准确的参考信息，同时也提出新的挑战。本课题主要研究： 1 ) 数据仓库多维数据模型的创建、组织，用0 l a p 对数据仓库中的多维数据进行统 计分析。 2 ) 合适的高校毕业生就业信息指标的确定，多维数据模型的建立，合适的数据仓 库分析模式的组织。 3 ) o l a p 对高校毕业生信息的组织、多维数据挖掘，信息指标的数据分析，得出 分析表格，能利用旋转、切片或切块、向上归纳、向下钻取等操作剖析数据。 4 ) 设计实现多维关联规则挖掘算法，利用该算法设计实现多维数据分析、挖掘， 而且该算法的可操作性、易实现性、结果的可理解性要比较强。 本论文主体共分为血章： 第一章绪言。本章首先介绍了课题的背景；接着概括了课题具体所涉及的理论及 其相应的特点，总结了所涉及技术的发展和目前的研究成果等；最后列出了本论文的结 构。 第二章数据挖掘综述。本章首先介绍了数据挖掘的基本概念；然后讨论了数据挖 第一章绪言 掘算法的分类及其评价；最后主要从单维挖掘方法和多维挖掘方法两个角度来介绍的详 细介绍了数据挖掘中的关联规则挖掘方法。 第三章基于数据仓库和o l a p 挖掘的多维分析方法。本章主要介绍了数据仓库基本 知识及其建模方法，对多维数据模型的研究，对o l a p 数据分析方法的研究，并作了基 于数据仓库和o l a p 的高校毕业生就业状况分析系统，并利用切片、切块、上卷和下钻 对高校毕业生就业状况进行了分析。 第四章关联规则挖掘算法研究。本章主要对经典的单维关联规则挖掘算法a i s 算 法，h p r i o r i 算法、d h p 优化算法进行了分析研究，对它们的效率、精确性，主要特点 等进行了分析。 第五章多维关联规则挖掘算法设计与实现。本章主要从两个角度来分析多维关联 规则挖掘的必要性，又介绍了多维关联规则挖掘的相关基本概念，并提出了一种基于 s o l 的多维关联规则挖掘算法，并在该算法的基础上做了相应的改进，提出了增强的算 法，最后给出了算法的试验结果。 最后是对本文所完成的工作的总结和展望。 第二章数据挖掘综述 2 1 数据挖掘的概念 第二章数据挖掘综述 数据挖掘n 儿2 1 ( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的 实际应用数据中抽取隐含在其中的、人们事先不知道但又是潜在有用的信息和知识的过 程。数据挖掘的任务着重在知识发现的过程中揭示隐含的模式。数据挖掘是知识发现过 程中最根本的一个步骤。通常认为数据挖掘更强调其对象是大规模的数据集合，而不论 这些数据以何种方式存储和管理。数据挖掘的对象不仅是一般意义上的数据库，也可以 是数据仓库、文件系统，或其他任何组织在一起的数据集合，例如w w n 信息资源。因此， 从广义的角度说，数据挖掘就是在一些事实或观察数据的集合等大规模数据中发现有价 值的知识和寻找模式的决策支持过程。 数据挖掘就是从大量的数据中发现潜在规律、提取有用知识的方法和技术。又称为 数据库中的知识发现( 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 ) 晦m h 埔。k d d 一词首先 出现在1 9 8 9 年8 月美国底特律举行的第十一届国际联合人工智能学术会议上。从1 9 8 9 年到现在，k d d 的定义随着人们研究的不断深入也在不断完善，一个比较广泛数据挖掘 定义是：数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣 知识的过程。数据挖掘的主要功能包括，聚类( c l u s t e r i n g ) 、分类( c 1 a s s i f i c a t i o n ) 、 预测( p r e d i c t i o n ) 、关联分析( a s s o c i a t i o na n a l y s i s ) 、时间序列分析( t i m es e r i e s a n a l y s i s ) 等。 2 2 数据挖掘算法分类及评价 作为- - n 处理数据的新兴技术，数据挖掘有许多的新特征。首先，数据挖掘面对的 是海量的数据，这也是数据挖掘产生的原因。其次，数据可能是不完全的、有噪声的、 随机的，有复杂的数据结构，维数大。最后，数据挖掘是许多学科的交叉，运用了统计 学，计算机，数学等学科的技术。 2 2 1 数据挖掘算法、分类及主要规则 一、常见和应用最广泛的算法和模型主要有： ( 1 ) 传统统计方法：抽样技术：我们面对的是大量的数据，对所有的数据进行分 析是不可能的也是没有必要的，就要在理论的指导下进行合理的抽样。多元 统计分析：因子分析，聚类分析等。统计预测方法，如回归分析，时间序列 分析等。 第二章数据挖掘综述 ( 2 ) 可视化技术：用图表等方式把数据特征用直观地表述出来，如直方图等，这其 中运用的许多描述统计的方法。可视化技术面对的一个难题是高维数据的可视 化。 ( 3 ) 决策树：利用一系列规则划分，建立树状图，可用于分类和预测。常用的算法 有c a r t 、c h a i d 、i d 3 、c 4 5 、c 5 0 等。 ( 4 ) 神经网络：模拟人的神经元功能，经过输入层，隐藏层，输出层等，对数据进 行调整，计算，最后得到结果，用于分类和回归。 ( 5 ) 遗传算法：基于自然进化理论，模拟基因联合、突变、选择等过程的一种优化 技术。 ( 6 ) 关联规则挖掘算法：关联规则是描述数据之间存在关系的规则，形式为“a 1 八 a 2 八a n b 1 八b 2 八b n 。一般分为两个步骤：求出大数据项集。用大 数据项集产生关联规则。 除了上述的常用方法外，还有粗集方法，模糊集合方法，b a y e s i a nb e l i e f n e t o r d s ， 最邻近算法( k - n e a r e s tn e i g h b o r sm e t h o d ( i ( n n ) ) 等。 二、数据挖掘算法从不同的视角可分为不同的类别。 令根据挖掘任务分类 可分为分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依 赖关系或依赖模型发现、异常和趋势发现等等。 根据挖掘的数据库分类 数据挖掘基于的数据库类型有：关系型、事务型( t r a n s a c t i o n a l ) 、面向对象型、 主动型( a c t i v e ) ，空间型( s p a t i a l ) 、时间型( t e m p o r a l ) 、文本型( t e x t u a l ) 、多媒体 ( m u l t i m e d i a ) 、异质( h e t e r o g e n e o u s ) 数据库和遗留( 1 e g a c y ) 系统，还有基于数据仓库 的数据挖掘系统，及基于国际互连网( w w w ) 的数据挖掘系统等。 令根据采用的技术分类碑1 采用的技术本身从不同的描述角度：( 1 ) 根据用户参与的程度分为：自治系统，交 互探查系统和查询系统；( 2 ) 根据采用的数据分析的方法分为：面向数据库或数据仓库 的技术，机器学习，统计分析，可视化技术，模式识别，神经网络等等。 三、目前数据挖掘领域研究的几种主要的规则。 1 ) 特征规则( c h a r a c t e r i s t i cr u l e s ) 特征规则描述在目标数据集中存在的特征， 这些特征为数据集中大部分所共有。 2 ) 判别规则( d i s c r i m i n a n tr u l e s ) 判别规则通过总结出目标类的特征和性质，以 区分目标类和其它用于比较的类。例如，判别规则通过总结出某种疾病的特有 症状，可以说明该种疾病与其它疾病的区别。 3 ) 分类规则( c l a s s i f i c a t i o nr u l e s ) 分类规则是把数据集划分成规定的若干种类 的一组规则。例如，可以从一组有关某些疾病及其症状的数据中得出分类规则， 根据这些分类规则不同的疾病能够被归到不同的类。 4 ) 关联规则( a s s o c i a t i o nr u l e s ) 关联规则揭示了一组对象之间存在的联系规则， 例如“同时发生”或“从一个对象可以推出另一个对象”。其形式通常为a 1 八 第二章数据挖掘综述 a 2 八a i b l 八b 2 八a b j ，表示在目标数据中对象b 1 b j 倾向于和对象a 1 a i 一同出现。例如，关联规则可以描述某种疾病通常和其它几种疾病同时出现。 2 2 2 数据挖掘算法的评价标准 给出数据挖掘完整的比较和评价不是很容易的事情，但是仍然存在很多公共的原则 文献四儿1 0 1 中提出了一系列的衡量标准，是很全面的。数据挖掘总的有效性可以从以下三 个方面来衡量： 1 精确度：精确度的大小将直接影响到挖掘结果的准确性和可用性，精确度越高其 可用性就越强，就越有利于做出正确的决策。精确度将决定于算法的设计和历史数据量 以及用户的期望值，所以有些时候不得不在精度和速度之间折衷。 2 速度：虽然决策支持要操作海量的历史数据，速度不是主要的但是速度仍然是 需要考虑的因素，毕竟数据量在不停地膨胀。因此算法必须是实际可行的，数据处理的 并行、分布以及高效的数据分片都是提高速度的有效方法。 3 开销：开销将最终决定是否采用数据挖掘进行决策支持，好的算法不应该是开 销巨大的，应该有很好的可移植性，不依赖于特定的环境和硬件。 2 3 关联规则挖掘方法 关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 是数据挖掘研究的一个重要分支，关联 规则是数据挖掘的众多知识类型中最为典型的一种，该问题于1 9 9 3 年由a g r a w a l 瞳1 等人 在对市场购物篮问题( m a r k e tb a s k e ta n a l y s i s ) 进行分析时首先提出。用以发现商品销 售中的顾客购买模式。关联规则挖掘可以发现存在于数据库中的项目( i t e m s ) 或属性 ( a t t r i b u t e s ) 间的有趣关系，这些关系是预先未知的和被隐藏的，所发现的关系可以辅 助人们进行市场运作( m a r k e t i n g ) 、决策支持( d e c i s i o ns u p p o r t ) 及商业管理( b u s i n e s s m a n a g e m e n t ) ，网站设计( w e bs i t ed e s i g n ) 。由于关联规则挖掘形式简洁、易于理解和 解释并可以有效的捕捉数据间的重要关系，因此从大型数据库中挖掘关联规则的问题己 经成为近年来数据挖掘研究领域的一个热点。 2 3 1 关联规则研究现状 关联规则分为基于事务数据库的单维关联规则和基于关系数据库的多维关联规则。 其中多维关联规则又可分为维间多维关联规则和混合维关联规则心1 。关联规则挖掘性能 的关键主要体现在频繁项集的挖掘算法的性能上。由于关联规则是数据挖掘中一种重要 的模式，许多解决策略不断被提出。其中比较著名的是以连接和剪枝的方法获取候选集 进而获得频繁项集的a p r i o r i 算法，以及基于a p r i o r i 算法之上的一些改进算法，如划分 和事务压缩等方法u u m l 。 第二章数据挖掘综述 2 3 2 挖掘关联规则算法的一般步骤 关联规则挖掘算法可以分为如下的几个步骤n 们： 1 ) 预处理与挖掘任务有关的数据根据具体问题的要求对数据库做相应的操作从而构成 规格化的数据库d ； 2 ) 针对d 求出所有满足最小支持度的项集即大项集由于挖掘一般是针对大规模的数据 库所以此步是算法的核心； 3 ) 生成满足最小置信度的规则形成规则集r ； 4 ) 筛选规则集去掉没有意义的规则； 5 ) 解释并输出r 。 2 3 3 主要研究的方向和典型算法 关联规则已经形成了很多种算法，按照算法本身的思想可分为下面几类乜儿1 0 3 ： 1 ) 多循环方式挖掘：挖掘是以多次扫描整个事务数据库为基础包括a p r i o r i ， a p r i o r i t i d ，d h p ，p a r t i t i o n 等算法。 2 ) 增量式更新算法：主要研究在数据库或支持度和置信度发生变化时如何从己有的规 则集导出新的规则集。 3 ) 并行发现算法：主要集中于在并行计算机和多机系统中规则的获取方法。比如c d ， c a d ，d d ，p d m 等多种算法。 4 ) 多层关联规则挖掘算法：针对数据库中数据量少的情况下，从概念层次获取关联规 则的方法，c u m u l a t e ，s t r a t i f y 等属于此类。 2 3 4 多维关联规则挖掘方法 多维关联规则是涉及多个属性或谓词的规则。多维关联规则的挖掘不像单维关联规 则挖掘那干f 搜索的是频繁项集，在多维关联规则挖掘中，我们搜索频繁谓词集。k 一谓词 集是包含k 个合取谓词的集合。例如，在式( 3 2 ) 中的谓词集 a g e ，o c c u p a t i o n ，b u y s 是3 一谓词集。同样用l k 表示频繁k 谓词集的集合。多维关联规则挖掘方法可以根据它 们对量化属性的处理分为以下三种心蚓： 1 使用量化属性的静态离散化挖掘多维关联规则 即使用预定义的概念分层对量化属性离散化。这种离散化在挖掘之前进行，数值属 性的值用区间替代，如，”o 一2 0 ”，”2 1 3 0 ”，”3 1 4 0 ”等，替换属性原来的数值。如果任 务相关的结果数据存放在关系表中，则a p r i o r i 算法只需要稍加修改就可以找出所有的 频繁谓词，而不是频繁项集( 即通过搜索所有的相关属性，而不是仅搜索一个属性) 。 找出所有的频繁k 一谓词集将需要k 或k + 1 次表扫描。其它策略，如散列、划分和选样可 以用来改进性能。 第二章数据挖掘综述 2 挖掘量化关联规则 量化关联规则是多维关联规则，其中数值属性动态离散化，以满足某种挖掘标准。 这种方法是根据数据的分布，将量化属性离散化到“箱”。这些箱可能在挖掘过程 中进一步组合。如系统a r c s ( a s s o c i a t i o nr u l ec l u s t e r i n gs y s t e m ，关联规则聚类系 统) 使用的方法就是将量化属性对映射到满足给定分类属性条件的2 d 栅格上，然后搜 索栅格点的聚类，由此产生关联规则。 3 挖掘基于距离的关联规则 这种方法是量化属性离散化，以紧扣区间数据的语义，并不允许数据值的近似。这 一过程考虑到了数据点之间的距离，因此称为基于距离的关联规则。两遍算法可以用 于挖掘此类关联规则。第一遍使用聚类找出区间或簇。第二遍搜索频繁的一起出现的簇 组得到基于距离的关联规则。 2 4 本章小结 本章首先介绍了数据挖掘的基本概念、数据挖掘算法的分类，并从精确度、速度、 开销三个方面介绍了对数据挖掘总体有效性的影响，然后由重点介绍了关联规则挖掘算 法，主要从关联规则研究现状、挖掘关联规则算法的一般步骤、关联规则的主要研究方 向和典型算法方面对关联规则进行了介绍，最后简要论述了目前多维关联规则挖掘方 法。 第二章基于数据仓库和o l a p 挖掘的多维分析方法 第三章基于数据仓库和o l a p 挖掘的多维分析方法 3 1 数据仓库及其建模方法 3 1 1 数据仓库概念 数据仓库是一个面向主题的、集成的、与时间相关、稳定的数据集合，以便支持管 理决策m m l 。 “面向主题”的数据仓库要求进行数据库设计，而一些数据库设计者忽略了这一重 要环节，根本没有进行正规的数据库设计。他们简单地把原有数据库或者并非专为数据 仓库设计的现有决策支持系统( d s s ) 中的数据复制到数据仓库中。这样建立的不是良构 的、可独立维护的主题数据库。在数据仓库设计过程中，数据以所代表的业务内容划分， 而不是以应用划分。 “数据集成性”意味着数据仓库中的数据采用统一的格式和编码方式。在命名协议、 关键字、关系、编码和翻译中的一致性问题必须通过精心的设计取得。 “与时间相关 意味着数据仓库中的数据大都与时间相关。因此，数据仓库中的数 据组织方式要便于按时间段计算和提取数据。 “稳定的 是指数据仓库中的数据不进行实时更新。通常数据是以每天、每周或每 月为周期进行升级，这一升级的过程不是简单的拷贝，而是要经过复杂的提取、概括、 聚集和过滤等操作过程。数据一旦进入数据仓库，就不允许随便更新。 3 1 2 数据仓库的内涵 从数据仓库的基本概念及产生背景看来，数据仓库具有以下内涵n 帅射： ( 1 ) 数据仓库应支持多种数据源，不仅仅是数据库，还应有各种数据文件、文本文件、 应用程序等。 ( 2 ) 数据仓库中存放的应该不仅是供分析使用的数据，还应有在一定激发条件下能主 动起作用的处理规则、算法、甚至是过程。 ( 3 ) 传统的物理数据仓库方法并非唯一的选择，应根据需求的具体情况，建立虚拟数 据仓库的解决方案。 ( 4 ) 数据仓库中的数据并不完全是原始数据的简单归并和搬家，而应该是增值和统 一。因此“汇总并统一”是数据仓库的必须内涵描述。 3 1 3 数据仓库的基本组成 数据仓库d w ( d a t aw a r e h o u s e ) 既是一种结构和方法，又是一种技术n 引。各种信息 从不同信息源提取出来，然后将其转换成公共的数据模型并和仓库中已有的数据集成， 第三章基丁= 数据仓库和o l a p 挖掘的多维分析方法 当用户向仓库查询时，需要的信息已准备就绪，数据冲突、表达不一致等问题已经得到 解决，这样，决策查询更容易、更有效。作为一种满足数据仓库管理要求的特殊的数据 库系统，d w 具体包含以下五个基本功能部分n 小坦儿1 3 1 ： 数据定义：主要完成数据仓库的结构和环境的定义，包括：定义数据仓库中数据库 的模式、数据仓库的数据源和从数据源提取数据的一组规则或模型。 数据提取：数据提取部分负责从数据源提取数据，并对获得的源数据( s o u r c ed a t a ) 进行必要的加工处理，使其成为数据仓库可以管理的数据格式和语义规范。 数据管理：数据管理由一组系统服务工具组成，负责数据的分配和维护，支持数据 应用。数据分配完成获取数据的存储分布及分发到多台数据库服务器，维护服务完成数 据的转储和恢复、安全性定义和检测等。另外，用户直接输入系统的数据也由该部分完 成。 数据应用：数据仓库的数据应用除了一般的直接检索性使用外，还应当能够完成比 较常用的数据表示和分析，如图表表示、统计分析、结构分析等。对于涉及到众多数据 的综合性较强的分析，可以借助专业数据分析工具。在客户机朋务器体系结构下，这部 分功能可以放在客户端来完成，以便充分利用客户机上丰富的数据分析软件。这部分主 要包括了报表生成、o l a p 、数据挖掘、决策支持工具应用等方面，其中o l a p 和数据挖 掘是近年来研究的重点和热点。 3 1 4 数据仓库体系结构 数据仓库是储存、管理信息数据的一种组织形式，其物理实质仍是计算机存储数据的 系统，只是由于使用目的不同，其存储的数据在量和质以及前端分析工具上与传统信息系 统有所不同。数据仓库按照功能分为以下几部分： 1 、元( m e t 曲数据。元数据是数据仓库的核心，是关于数据的数据，是关于数据和信 息资源的描述信息。它通过对数据的内容，质量，条件和其他特征进行描述和说明，帮 助人们有效地定位、评论、比较、获取和使用相关数据。 2 、源数据。指分布在不同的应用系统中，存储在不同的平台和不同的数据库中的 大量的数据信息，是数据仓库的物质基础。 3 、数据变换工具。为了优化数据仓库的分析性能，源数据必须经过变换以最适宜 的方式进入数据仓库。变换主要包括提炼、转换。数据提炼主要指数据的抽取，并对抽 取数据删去不需要的运行信息，检查数据的完整性和相容性等；数据转换指统一数据编 码和数据结构、给数据加上时间标志、根据需要对数据集进行各种运算以及语义转换等。 数据变换工具为数据库和数据仓库之间架起了一座桥梁，使源数据得到了增值和统一， 最大限度地满足了数据仓库高层次决策分析的需要。 4 、数据仓库。源数据经过变换进入数据仓库。数据仓库以多维方式来组织数据和 显示数据。属性维和时问维是数据仓库反映现实世界动态变化的基础，他们的数据组织 方式是整个数据仓库技术的关键。 l 5 、数据分析工具。数据仓库系统的目标是提供决策支持，它不仅需要一般的统计 分析工具，更需要功能强大的分析和挖掘工具，是数据仓库系统的重要组成部分。分析 第三章基丁数据仓库和o l a p 挖掘的多维分析方法 工具主要实现对数据仓库中的数据进行分析和综合。挖掘工具负责从大量的数据中发现 数据的关系，找到可能忽略的信息，预测趋势和行为。 3 1 5 数据仓库的数据模型 最流行的数据仓库数据模型是多维数据模型。这种模型以星型模式、雪花模式或事 实星座模式形式存在。 星型模式( s t a rs c h e m a ) ：最常见的模型，其中数据库包括( 1 ) 一个大的包涵大批 数据和不含冗余的中心表( 事实表) ，( 2 ) 一组小的附属表( 维表) ，每维一个。这种模 式图像星星爆炸，维表围绕中心表很像星星爆发，维表围绕中心表显示在射线上。 雪花模式( s n o w f l a k es c h e m a ) ：雪花模式是星型模式的变种，其中某些维表是规范 化的，因而把数据进一步分解到附加的表中。结果，模式图形成类似于雪花的形状。 雪花模式和星型模式主要不同在于，雪花模式的维表可能是规范化形式，减少冗余。 这种表易于维护，并节省存储空间，因为当维结构当作列包含在内时，大维表可能非常 大。然而，与巨大的事实表相比，这种空间的节省可以省略。此外，由于执行查询需要 更多的连接操作，雪花结构可能降低浏览的性能。这样，系统地性能可能相对受到影响。 因此，在数据仓库设计中，雪花模式不如星型模式流行。 事实星座( f a c tc o n s t e l l l a t i o n ) ：复杂的应用可能需要多个事实表共享维表，这种模 式可以看作星型模式集，因此成为星系模式( g a l a x ys c h e m a ) ，或事实星座。 3 2 多维数据模型的研究 3 2 1 多维数据模型简介 模型是人们对客观世界的认识和理解，是对客观世界的近似描述，数据模型是对现 实世界的抽象，抽象程度的不同就形成不同抽象级别层次上的数据模型。在把现实世界 种的客观事物抽象为数据仓库中数据的过程中，可以分为现实世界、信息世界和机器世 界三个阶段，相应数据仓库数据模型的设计可分成三个不同的级别：概念模型、逻辑模 型和物理模型引。在数据仓库的设计中，概念模型是现实世界到机器世界的一个中间层， 人们首先将现实世界抽象为信息世界，然后再将信息世界转化为机器世界；逻辑模型处 于概念模型和机器模型之间，是对概念模型的细分和逻辑实现，物理模型是逻辑模型在 数据仓库中的实现，如数据存储方式、存储结构、存放位置等。 1 9 9 3 年e f c o d d 提出了1 2 条准则来描述o l a p 系统，其中明确地指出o l a p 操作具 有多维性，从此多维数据模型引起了学术界的重视，数据仓库概念模型设计的首选模型 是多维数据模型。 在多维数据模型中，通常用一系列属性集来描述某一主题，如商品销售这个主题可 用时间、地点、商品和销售量等属性来描述，有些用来描述人们观察主题的角度，如时 问、地点和商品，这些属性可以形成多维空间，因此称作维，而这些多维空间的单元包 含了该主题剩下属性的值，如销售量、销售额等；维属性往往有具有层次结构，度量数 第三章基于数据仓库和o l a p 挖掘的多维分析方法 据的值就放在这样一些有层次结构的维构成的多维空间中，这个多维空间就称作数据立 方体。 3 2 2 多维数据模型 数据模型是数据仓库研究的核心问题。虽然最近人们在数据仓库方面开展了大量的 研究工作，但研究表明，关系数据模型不能有效地表示数据仓库的数据结构和语义，也 难以有效地支持o l a p 标准( o l a p 操作具有多维性特征) ，因此，多维数据模型引起了人 们的注意。 最近几年，人们提出了多种多维数据模型n 儿5 儿6 儿1 2 1 。这些数据模型把数据集合视为 多维空间中的