（计算机软件与理论专业论文）数据立方梯度的联机挖掘.pdf

华中科技大学硕士学位论文 摘要 数据立方梯度是关联规则在数据立方上的推广和一般化，它描述了立方元组因维 值的变化所导致的度量变化，能够支持更复杂、更广泛的假设分析。 为了克服传统的梯度挖掘算法从基表开始、象生成数据立方一样计算出立方梯度 造成的巨大计算代价，提出了数据立方梯度的联机挖掘m c g o 算法。由于数据立方中 蕴含了所有的立方梯度，并且在联机分析处理中通常会预先计算数据立方以加速查询 响应，因此m c g o 算法利用联机分析处理查询得到所需的立方元组，再通过维值匹配 和梯度约束判断生成立方梯度，这样不但节省了计算代价，也避免了同时保存立方元 组和立方梯度的冗余。将梯度挖掘与联机分析处理集成，也符合用户在浏览数据立方 时产生的挖掘兴趣。 数据立方的巨大尺寸有可能使得保存和维护一个经过完全计算的数据立方变得不 切实际，而浓缩数据立方则可以大大节省存储空间，并且可以在其上构建c u b o i d t r e e 索引，提高查询效率。在此基础上提出了基于浓缩数据立方的梯度联机挖掘m c g o b c 算法。注意到浓缩数据立方的本质是将那些由相同基表元组集合聚集得到的立方元组 浓缩到一条基本单元组，并且在c u b o i d t r e e 索引中具有相同单值维集的基本单元组被 组织在一起构成虚小方，m c g o b c 算法采取了虚小方查询修剪和基本单元组定向扩展 的优化策略，保证了每个虚数据小方都只被查询一次，基本单元组也仅在泛化、具体 化和突变方向上进行扩展，从而有利于减少查询开销，提高算法性能。 在研究了联机分析处理与数据挖掘集成的联机分析挖掘系统基础上，设计了基于 达梦联机分析处理服务器的数据立方梯度联机挖掘工具d mm c g o b c o 关键词：数据立方，浓缩数据立方，数据立方梯度，梯度联机挖掘，基本单元组 i 华中科技大学硕士学位论文 一= = = = ；= = = = ；= = = = = = = 2 = = = = = = = = = = 一 a b s t r a c t c u b eg r a d i e n t sa r eg e n e r a l i z a t i o no fa s s o c i a t i o nr u l e s w h i c hr e p r e s e n th o was e to f m e a s u r e si sa f f e c t e db ym o d i f y i n gac u b ec e l l sd i m e n s i o n s c u b eg r a d i e n t sa r es i g n i f c a n t l y m o r ee x p r e s s i v et h a na s s o c i a t i o nr u l e si nc a p t u r i n gt r e n d sa n dp a t t e r n si nd a t a ，w h i c hc a l l s u p p o r ts o p h i s t i c a t e d ”w h a ti f a n a l y s i st a s k s i no r d e rt oo v e r c o m et h eg r e a t ec o m p u t ec o s tc a s e db yt h ed o m i n a t i n gc u b eg r a d i e n t m i n i n ga l g o r i t h m sw h i c hu s u a l l yc o m p u t ea l lp o s s i b l e c u b eg r a d i e n t sf r o ms r o u c et a b l e d i r e c t l y ，t h ea l g o r i t h mo fm i n i n gc u b eg r a d i e n to n l i n e ，m c g oi sp r o p o s e d b e c a u s ea l lc u b e g r a d i e n t s a r ec o n t a i n t e di nd a t ac u b et h a th a sb e e nm a t e r i a l i z e di no n l i n e a n a l y t i c a l p r o c e s s i n gs e r v e r st oa c c e l e r a t et h er e s p o n s e ，m c g of i r s ta c q u i r e sc u b ec e l l sb yq u e r i e st o d a t ac u b e ，a n dt h e nc o m p u t e sc u b eg r a d i e n t sf r o mt h ec u b ec e l l sb yt h ed i m e n s i o nv a l u e m a t c h i n ga n dg r a d i e n tc o n s t r a i n t sj u d g i n g i tn o to n l ys a v e st h eg r e a t ec o m p u t ec o s t ，b u ta l s o g e tr i do f t h er e d u n d a n c i e sb e t w e e nc u b eg r a d i e n t sa n dc u b ec e l l s t h a tt h em i n i n go fc u b e g r a d i e n t i s i n t e g r a t e di n t o o n l i n ea n a l y t i c a i p r o c e s s i n g a l s oa c c o r d sw i t hu s e r s i n t e r e s t a r i s i n gw h e nb r o w s i n g t h ed a t ac u b e t h eh u g es i z eo fd a t ac u b em a ym a k et h es t o r a g ea n dm a i n t e n a n c eo fd a t ac u b eb e c o m e u n p r a c t i c a l ，w h i l ec o n d e n s e dc u b ec a ns a v es t o r a g es p a c eg r e a t l y , b a s e do i lw h i c h t h ec u b e i n d e xc u b o i d t r e ec a r li m p r o v eq u e r ye f f i c i e n c y t h ea l g o r i t h mo fm i n i n gc u b eg r a d i e n t o n l i n eb a s e do nc o n d e n s e dc u b e ，m c g o b ci s p r o p o s e d n o t i c e dt h ef a c tt h a tt h o s ec u b e t u p l e sa g g r e g a t e df r o m t h es a m eb a s et u p l es e ta r ec o n d e n s e di n t oo n e p h y s i c a lt u p l ea n d t h e b a s es i n g l et u p l e sw i t hs a m es i n g l ed i m e n s i o ns e ta r eo r g a n i z e di n t oav i r t u a lc n b o i di n c u b o i d t r e e ，m c g o b cp r u n e s v i r t u a lc u b o i d q u e r i e s a n d e x p a n d s b a s e s i n g l et u p l e s d i r e c t i o n a l t h o s em e a s u r e sa s s n r et h a tt h ev i r t u a lc u b o i do n l yb eq u e r i e do n c ea n db a s e s i n g l et u p l e so n l yb ee x p a n d e do u ta l ip o s s i b l en e e d e dc u b ec e i l s w h i c hh e l p st os a v eq u e r y s p e n d i n ga n di m p r o v e t h ea l g o r i t h mp e r f o r m a n c e a f t e rt h eo n l i n ea n a l y t i c a lm i n i n gm o d e li ss t u d i e d ，a no n l i n ec u b eg r a d i e n tm i n i n gt o o l i i 华中科技大学硕士学位论文 d m _ m c g o b c i sd e s i g n e db a s e do nt h eo n l i n ea n a l y t i c a lp r o c e s s i n gs e r v e rd m o l a p k e yw o r d s ：d a t ac u b e ，c o n d e n s e dc u b e ，c u b eg r a d i e n t ，m i n i n gc u b eg r a d i e n to n l i n e ，b a s e s i n g l et u p l e i i l 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：互挥 日期：2 口。中年5 月f o 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于， 不保密曰。 ( 请在以上方框内打“4 ”) 学位论文作者签名 互拜 日期：z d d 中年r 月f o 日 指导撕签名：沃碳 日期：2 0 0 牛年r 月f 2 ，日 华中科技大学硕士学位论文 1 1 课题背景 1 绪论 随着我国社会信息化进程的飞速发展，成千上万的大型数据库已经被广泛地应用 在企业、政府和科研等等部门。如何充分利用这些日益积累起来的大量数据资源，发 现隐藏在其中的有用知识，更好地把握未来发展趋势，成为迫切的需要。目前通常采 用建立决策支持系统( d e c i s i o ns u p p o r t i n gs y s t e m ，d s s ) ，以及面向分析的数据仓库( d a t a w a r e h o u s e ，d w ) ，通过联机分析处理( o n l i n ea n a l y t i c a lp r o c e s s i n g ，o l a p ) 年 i 数据挖掘 ( d a t am i n i n g ，d m ) 工具来挖掘其中的有用知识。 数据仓库是一个面向主题的、集成的、非易失的且随时间变化的数据集合 1 1 。随 着企业业务的扩大和时间的增加，数据仓库中的数据量会不断增加，用户在使用基于 o l a p 的手工分析方法如切片( s l i c e ) 、下钻( d r i l l - d o w n ) 时也就难以做到对数据完整、彻 底的分析。而数据挖掘工具能够自动的挖掘和发现数据之间潜在的联系和变化趋势， 这使得用户能够在挖掘结果的基础上进行更加有效的决策分析。 由于数据仓库一般采用数据立方口】来描述所存储的数据，因此基于数据立方的数据 挖掘引起研究者的广泛关注1 4 ，5j 。数据立方梯度挖掘是数据挖掘领域的一个新的、重要 的课题 6 i ，它是数据挖掘中的关联规则在数据立方上的推广。关联规则挖掘 7 】胄够从存 储在数据库中的大量数据中挖掘出有价值的描述数据项之间相互联系的知识，它的一 个典型应用实例就是市场购物分析，即从大量的商业交易记录中发现顾客的购买倾向 与模式。商场管理人员可以利用这些知识进行有针对性的促销以及合适的货架商品摆 放等。而数据立方梯度由于充分利用了数据立方中的聚集信息，比起关联规则更富于 表达性，因而能够支持更复杂、更广泛的假设分析( w h a t i f ) 。 在华中科技大学数据库与多媒体研究所承担的科技部电子政务工程中，科技部信 息数据仓库需要提供整个科技部内的面向主题的、集成的、稳定的数据系统，搭建面 向决策支持的数据分析环境。本课题在此背景下，进行数据立方梯度挖掘系统的研究 和开发，用以支持该项目数据分析功能。 华中科技大学硕士学位论文 1 2 国内外概况 1 2 1 数据挖掘模型与系统 数据挖掘删，又称为数据库中知识发现( k n ow i e d g ed i s c o v e r yf r o md a m b a s e ，k d d ) ， 它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的复杂过程， 有机地结合了来自多学科的技术，其中包括：数据库、数理统计、机器学习、高性能 计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理、空间数据分 析等。 倒1 1 数据挖掘过程模型 数据挖掘过程的一般性模型是由u m f a y y a d 等人提出的【9 , 1 0 ，如图1 1 所示。整个 挖掘过程的可分成三个主要的过程：数据预处理、数据挖掘、结果解释和评价。它是 个不断循环和反复的过程，因两可以对挖掘出来的知识不断求精和深化并且使这些 知识易于理解。其中数据预处理过程包括数据清洗( d a t ac l e a n i n g ) 、数据集成( d a t a i n t e g r a t i o n ) 、数据转换( d a t at r a n s f o r m a t i o n ) ；而数据挖掘过程根据挖掘的任务或目的决 定所使用的算法，得到用户寻求的数据模式或规律知识；结果解释和评价过程则按一 定评估标准从挖掘结果中筛选出有意义的模式知识，利用可视化和知识表达技术向用 户展示所挖掘出的相关知识。 目前市场上已出现许多数据挖掘的商业软件工具，大致可分为专用的数据挖掘工 具和通用的数据挖掘工具。 专用的数据挖掘工具针对某个特定领域的问题提供解决方案，因而在设计算法的 2 华中科技大学硕士学位论文 时候，充分考虑到数据、需求的特殊性，并作了优化。例如，i b m 公司的a d v a n c e d s c o u t 系统# i - x 十n b a 的数据，帮助教练优化战术组合；加州理工学院喷气推进实验室与天文 科学家合作开发的s k i c a t 系统，帮助天文学家发现遥远的类星体；芬兰赫尔辛基大 学计算机科学系开发的t a s a ，帮助预测网络通信中的警报。 而通用的数据挖掘工具不区分具体数据的含义，采用通用的挖掘算法，处理常见 的数据类型，一般提供六种模式，由用户根据自己的应用来进一步选择。通用的数据 挖掘工具有i b m 公司a l m a d e n 研究中心开发的q u e s t 系统，s g i 公司开发的m i n e s e t 系统，加拿大s i m o n f r a s e r 大学开发的d b m i n e r 系统等。 1 2 2 关联规则 关联规则挖掘( a s s o c i a t i o nn i l em i n i n g ) 问题一直是数据挖掘领域的一个研究热点。 关联规则挖掘就是从给定的数据集发现频繁出现的项集模式知识( 又称为关联分析， a s s o c i a t i o na n a l y s i s ) ，它最初是由r a g r a w l 等人【7 j 为获得超市交易数据库中的顾客的 购买模式而提出的。一个典型的关联规则例子就是“7 0 的客户在购买啤酒的同时也 会购买尿布，而购买了啤酒的交易占全部交易的2 ”。关联规则挖掘目前已被广泛应 用于电信、医疗、保险等领域。 关联规则的一般性描述是：设i = 0 1 , i 2 ，i m ) 是t n 个不同项目的集合，d 是交易数 据库，其中每一个交易j c i ，一条关联规则可表示为x j y ，其中x 、y c _ i ，x n y = o ， x 称为规则的前提，y 称为规则的结果。如果d 中c 的包含x 的交易同时也包含y ， 称关联规则在d 中以c 的可信度( c o n f i d e n c e ) 成立，如上例中的7 0 ：如果d 中s 的 交易包含x u y ，称关联规则在d 中具有s 的支持度( s u p p o r t ) ，如上例中的2 。满足 最小支持度的项目集称之为频繁项目集，反之，称为非频繁项目集，包含k 个元素的 频繁项目集表示为l k ，那些有可能成为频繁项目集的项目集称之为候选项目集，包含k 个元素的候选项目集表示为c k 。 对于给定的交易数据库d ，关联规则挖掘问题就是生成所有具有用户指定的最小 支持度和最小可信度的关联规则。关联规则挖掘过程可分为频繁项集和生成关联规则 这两个步骤。 步骤一将从数据库中找出所有的频繁项集，根据定义，这些项集的频度至少应等 华中科技大学硕士学位论文 于( 预先设定的) 最小支持频度。步骤- - n 根据所获得的频繁项集，产生满足最小信 任度的关联规则。 由于步骤二中的相应操作极为简单，因此关联规则挖掘的整个性能就由步骤一挖 掘频繁项集算法决定，这方面的研究工作吸引了众多的研究者的注意力。 a p r i o r i “1 是关联规则挖掘的经典快速算法之，它利用了有关频繁项集特性的先 验知识来完成频繁项集的挖掘工作。该算法使用个层次顺序搜索的循环方法：首先 找出频繁1 一项集即l - ：然后利用l l 来挖掘l 2 频繁项集，如此不断循环下去直到无法 发现更多的频繁k 项集为止。每挖掘一层k 就需要扫描整个数据库一遍。为提高层次 搜索并产生频繁项集的处理效率，a p r i o r i 算法用先验知识“频繁项集中任一子集也应 是频繁项集”的a p r i o r i 性质来缩小频繁项集的搜索空间。针对a p r i o r i 算法在生成l 2 过程中会产生大量的候选项c 2 的缺点，j s ，p a r k 等人在1 9 9 5 年采用h a s h 表技术1 1 2 】， 有效地减少了c 2 占用的存储空间，提高了算法的效率。此外，a s a v a s e r e 等人提出分 区技术( p a r t i t i o n i n g ) 、s b r i n 等人提出动态项目集记数技术f d y n a m i c i t e m s e t c o u n t i n g ) 1 4 1 等等。近年来出现了一些与a p r i o r i 算法框架截然不同的挖掘算法，如在文 献 1 5 中提出的f p t r e e 算法。该算法直接生成频繁项目集，避免了候选项目集的生 成，在频繁项较长的情况下算法效率远远高于a p r i o r i 类型算法。 在经典关联规则模型的基础上，研究者进行了不同的扩展提出了很多新的挖掘模 型，代表性的模型有1 9 9 5 年r a g r a w a l 等人提出的序列模式挖掘( s e q u e n t i a lp a t t e r n m i n i n g ) 川、h 。m a n n i l a 等人提出的事件挖掘( e s p i s o d e sm i m n g ) 川、k ，k o p e r s k i 等人提出 的空间关联规则挖j n ( s p a t i a la s s o c i a t i o nr u l e s ) 1 8 1 、b o z d e n 等人提出的循环关联规则挖 掘( c y c l i c a s s o c i a t i o n r u l e s ) ”叭、a s a v a s e r e 等人提出的负关联规则挖掘( n e g a t i v e a s s o c i a t i o nr u l e s ) 2 0 】、j h a n 等人提出的多层关联规则挖掘( m u l t i l e v e la s s o c i a t i o nr u l e s ) 2 1 】 等，这些模型往往是针对实际的不同应用提出的，例如序列模式最初是应用于商场销 售领域的，现在该模型的一个比较有前途的应用领域是生物学中d n a 序列计算。 关联规则与数据库的集成以及查询语言研究直受到高度关注，代表性的查询语 言有j h a n 提出的d m q l f 2 2 ，2 3 1 、r m e r o 提出的类s q l 语言( s q l 1 i k 2 4 1 、t m i e l i n s k i 等人提出的m s q l 等【2 5 1 。 4 华中科技大学硕士学位论文 1 2 3 数据立方 数据立方也被称作多维数据集( m u l t i d i m e n s i o n a l d a t as e t ) ，它强调提供用户数据的 多维视图，即允许用户从各个角度观察和分析感兴趣的数据。d r j i mg r a y 等人于1 9 9 6 年提出了c u b e 算子9 1 的概念，c u b e 算子是传统的g r o u pb y 算子的多维扩展，用 于计算c u b eb y 子句中各属性的所有可能组合所对应的g r o u pb y 。从那以后，高 效的数据立方计算方法一直是研究的重点。i b m a l m a d e n 研究中心的s a g a r w a l 等以及 w i s c o n s i n 大学的r m d e s h p a n d e 等在他们的联合论文 2 6 1 中分析和总结了数据立方计 算中各种可能的优化技术，大大加快了数据立方计算算法的研究步伐。 联机分析服务器的体系结构有多维型( m u l t i d i m e n s i o n a l ) 年l l 关系型( r e l a i o n a l ) 之分， 使得处于其中的数据立方的数据组织方式也不同，数据立方计算算法也因此可分为多 维数据立方计算算法和关系数据立方计算算法两类。d r j i mg r a y 等在提出c u b e 算予 的同时提出了一种计算多维数据立方的2 “算法。但d r y z h a o 等人提出的基于多维数 t t ( a r r a y ) 的多维数据立方计算a r r a y c u b e 2 7 】算法被认为更具有实际意义。而关系数据立 方计算算法中有s a r a w a g i 等提出的p i p e s o r t 算法、p i p e h a s h 算法和p r a s a dm d e s h p a n d e 提出的o v e r l a p 算法等。其中，p i p e s o r t 算法是第一个使用立方格l 羽( c u b e l a t t i c e ) 描述 数据立方计算问题的算法，基于立方格图描述数据立方计算的问题被后来的数据立方 计算算法所广泛接受。 按照立方格图中数据立方的各个分组维集的计算顺序，数据立方计算算法又町归 纳为自顶向下( t o p d o w n ) 和自底向上( b o t t o m u p ) 两类。绝大多数算法都属于第一类，自 底向上类型的算法仅有文献 2 8 1 中首次提出的b u c ( b o t t o m u p c u b e ) 算法。b u c 算法采 用了共享划分的优化技术，并结合了特别适合于稀疏数据立方( 如果基表中的元组数 目远远小于其属性域基数的笛卡尔积，称此基表是稀疏的，由此计算得到的数据立方 办是稀疏数据立方) 计算的单元组优化方法，是目前为止最适合于计算稀疏数据立方 的算法。 通常情况下完整计算的数据立方的尺寸是非常巨大的，这导致了o l a p 中数据立 方维护、更新的困难以及响应o l a p 查询时不菲的i o 代价。为了从根本上解决数据立 方巨大尺寸导致的许多问题，国内外学者进行了一系列的研究工作，以寻求数据立方 华中科技大学硕士学位论文 方大尺寸问题的适当解决方案。文献 2 9 1 从部分计算数据立方的角度探讨了数据小方 ( c u b o i d ) 选择计算问题，文献【3 0 】从体系结构方面讨论了数据压缩技术的应用和影响， 文献f 3 1 从近似查询处理方面着手，提出了可以快速提供近似查询结果的大纲数据结构 ( s y n o p s i sd a t as t r u c t u r e ) ，但这些技术所能满足的o l a p 查询结果都是部分的或近似的。 而d r w a n g 年1 1 d r f e n g 等- 人在i c d e 0 2 中首次提出的浓缩数据立方( c o n d e n s e d c u b 3 2 1 ， 在缩小数据立方尺寸的同时保持了数掘立方的完整语义，不需即时计算即可响应数据 立方的查询，而且度量值是精确的而非估计的，是解决数据立方大尺寸问题的种有 效解决方案。继浓缩数据立方之后又有两种类似方法被提出，此后相关研究工作得到 了迅速的发展。其中y s i s m a n i s 等人提出了以前缀树的方式组织数据的d w a r t | i j 数据 立方，而v s l a k s h m a n a n 等人则提出q u o t i e n tc u b e d 4 1 。 作为加速查询响应的一种有效手段，索引机制始终都是数据库界学者研究工作的 重点，对数据立方索引机制的研究工作也同样如此。文献【3 5 】中提出了c u b e t r e e 来作为 数据立方的存储抽象。文献【3 6 】提出了尤其有利于对数据立方进行点查询的层次分裂立 方森林( h i e r a r c h i c a ls p l i tc u b ef o r e s t s ) 。不过，它是一个高度冗余的数据结构，这使得它 不适合于大型数据库。而d lj a o r e n s t e i n 等人将空间填充曲线z o r d e r 和b t r e e 相结 合，提出了z k d b t r e e p 7 j 索引。进而d r r b a y e r 等提出z k d b t r e e 的一个改进的变体 u b - t r e e 口“。而文献【3 9 】基于数据立方的范围查询可分解为对某些数据小方的范围查询 这一观察，提出了将数据小方编码与z o r d e r 编码相结合的c u b o i d t r e e 索引。 文献 4 0 结合了缩小数据立方尺寸和加速数据立方查询响应这两方面的需求，在 b u - b s t 浓缩数据立方之上构建了高效的c u b o i d t r e e 索引，有利于对数据立方进行范 围查询，并可减小存储代价，可视为o l a p 服务中数据立方存储、组织的一种有效解 决方案。 】，2 4 基于数据立方的数据挖掘 我们将基于数据立方的数据挖掘简称为数据立方挖掘。如何将数据挖掘技术与 o l a p 技术更好的集成是当前数据立方挖掘中的一个热点研究问题，目前己涌现出一批 研究成果。其中j h m = l 等人提出在线分析挖掘技术m ”( o nl i n ea n a l y s i s m i n i n g o l a m ) ，将传统的经典挖掘模型和算法与数据立方模型相结合。与j h a n 不同， 6 华中科技大学硕士学位论文 d r s s a r a w a g i 等提出了一种新的基于数据立方的发现驱动探测1 4 ( d i s c o v e r y d r i v e n e x d l o r a t i o n ) 数据挖掘模型。它利用预先计算出来的异常指示符，帮助用户在浏览数据立 方的过程中发现数据中感兴趣的异常，以及采取哪种o l a p 操作如上卷，下钻等来深入 追踪观察浚异常。d r s s a r a w a g i 等在后续的研究中提出三种新的分析操作d i f f 、 r e l a x ，s u r p r i s e ，进一步完善了发现驱动探测模型【4 “5 1 。 数据立方挖掘中另一个重要的工作是数据立方梯度( d a t ac u b eg r a d i e n t ) ： g 掘的研 究。数据立方梯度挖掘是由d r t 1 m i e l i n s k i 等首次提出的 6 1 ，它是关联规则挖掘在数据 立方上的推广和一般化。数据立方梯度表征了多维空问里数据的变化趋势，能够支持 更复杂、更广泛的假设分析( w h a t - i o 以及趋势分析等。通常情况下，数据立方梯度的结 果集比较大，为了方便用户查看挖掘结果，d r t i m i e l i n s k i 等人还提出了一种新的数据 立方梯度查询语言c u b e g r a d e q l 。在d r t i m i e l i n s k i 等人工作的基础上，d r g o n g 和 d r h a n 等人提出了约束性数据立方梯度挖掘用来从数据立方中挖掘出用户感兴趣数据 立方梯度m 】。约束性数据立方梯度可以看作是数据立方梯度问题的精简版本，用于挖 掘满足给定约束的梯度探测元组对。而文献 4 7 则在此基础上进一步提出了基于浓缩 数据立方的约束性梯度挖掘算法。 1 3 课题研究工作 目前的数据立方梯度挖掘研究都着重于挖掘算法的效率，由于通常情况下完整计 算的数据立方的尺寸都非常巨大，给更新、维护工作带来了许多困难，因此现有的主 要的梯度挖掘算法假设数据立方尚未实化，都从零开始、象生成数据立方一样计算出 所需的数据立方元组和其中蕴涵的立方梯度。 但一方面实际中的联机分析服务通常都需要预先计算数据立方以加速对用户 o l a p 查询的响应，另一方面国内外学者已提出了多种压缩数据立方或缩小数据立方尺 寸的方法，使得联机分析服务中的预先计算数据立方成为可能。因此，在将数据立方 梯度挖掘集成到联机分析服务中时，就有必要考虑利用o l a p 中预先计算好的数据立 方来挖掘立方梯度，从而避免上述挖掘算法即时计算立方元组的高昂代价。 本课题是科技部电子政务科技信息决策支持系统中一个子课题：“数据立方梯度的 联机挖掘”。由于科技信息决策支持系统中的联机分析处理器d mo l a p 采用浓缩数据 7 华中科技大学硕士学位论文 立方作为数据立方存储结构，并以高效的数据立方索引机制c u b o i d t r e e 来存储、组织 实化的浓缩数据立方。因此本课题主要研究利用实化数据立方进行立方梯度的联机挖 掘问题，并在此基础上着重研究基于浓缩数据立方的梯度联机挖掘问题，设计基于联 机分析处理服务器d mo l a p 的数据立方梯度联机挖掘工具。 本课题的主要工作是： 1 ，研究和比较国内外主要的数据立方梯度挖掘算法，包括这些算法的主要思想、 结合的优化技术、优缺点、适用的范围等： 2 研究数据立方梯度挖掘集成到o l a p 的联机挖掘问题，设计数据立方梯度的联 机挖掘一般算法； 3 重点研究基于浓缩数据立方的立方梯度联机挖掘问题，设计基于浓缩数据立方 的立方梯度联机挖掘算法。针对浓缩数据立方的性质和存储组织特点，采取相应的优 化措施，提高算法效率； 4 ，研究联机分析处理挖掘系统，结合科技信息决策支持系统，设计基于联机分祈 处理服务器d m o l a p 的数据立方梯度联机挖掘工具。 8 华中科技大学硕士学位论文 2 数据立方梯度的联机挖掘 数据立方梯度表征了多维空间罩数据的变化趋势，用户通过对感兴趣的数据立方 梯度的分析能更好的进行决策活动。本章将着重研究数据立方梯度联机挖掘的一般问 题，首先介绍了数据立方梯度挖掘问题，接下来对现有的主要的梯度挖掘算法逐一进 行分析。然后根据联机分析服务通常预先计算数据立方这一实际情况，提出数据立方 梯度联机挖掘m c g o 算法。最后对算法进行了测试，并探讨了算法的扩展问题。 2 1 数据立方梯度挖掘 数据立方梯度挖掘是基于数据立方的数据挖掘研究中的一个重要分枝。数据立方 梯度挖掘问题最初是由d lt i m i e l i n s k i 等提出【6 1 ，它是关联规则在数据立方上的推广和 一般化，能够支持更复杂、更广泛的假设分析( w h a t i 旬以及趋势分析等。 2 1 1 数据立方 j i mg r a y 等人于1 9 9 6 年提出了数据立方p 】的概念，它将数据仓库中的数据组织成 多维形式，用以直观地支持联机分析处理所需的复杂多维分析。数据立方算子c u b e b y 是传统的g r o u pb y 算子的多维扩展，用于计算c u b eb y 子句中各属性的所有 可能组合所对应的g r o u pb y 。以基本关系表s a l e s ( d a t e ，p r o d u c t ，c u s t o m e r ，a m o u n t ) 为例，对属性a m o u n t 求和聚集计算的c u b eb y d a t e ，p r o d u c t ，c u s t o m e r 语句将会得到 d a t e ，p r o d u c t 和c u s t o m e r 的所有组合对应的g r o u pb y 。这里整个计算结果被称为一 个数据立方，记为c u b e ( d a t e ，p r o d u c t ，c u s t o m e r , a m o u n t ) ，而每个g r o u pb y 也被称作 一个数据小方( c u b o i d ) ，类似地，对应( d a t e ，p r o d u c t ) 的数据小方记为c u b o i d ( d a t e ，p r o d u c t ， a m o u n t ) 。在o l a p 术语中，c u b e b y 子旬中各属性又被称作维( 观察数据的角度) ， 如d a t e ：而被聚集计算的属性则被称作度( 或度量，考察目标) ，如a m o u n t 。 注意到数据立方的多维特性，在对o l a p 中为加快查询响应而预先计算好的数据 立方构建索引时，一种常用的方法就是先选取适当的多维填充曲线把多维空间映射到 一维空间，然后使用成熟的一维索引技术进行索引。其中把多维填充曲线中的z o r d e r 9 华中科技大学硕士学位论文 曲线和传统b t r e e 结合起来的多维索引z k db t r e e ”】，它的基本思想就是利用z o r d e r 将多维空间映射到一维空间，然后利用b t r e e 对一维空间进行索引。 而文献 3 9 1 根据数据立方的范围查询可分解为对某些数据小方的范围查询这一基 本观察，将数据小方编码与空间扫描曲线z o r d e r 相结合，提出了c u b o i d t r e e 索引。 它首先对每个数据小方分配一个唯一标识c u b o i d l d ，并对其中的立方元组建立一棵的 z k db t r e e ，然后再以c i d 为k e y 索引各个数据小方的z k db t r e e 的根，由此构建成整 棵的c u b o i d t r e e 。与直接建立的整棵z k db t r e e 相比较，c u b o i d t r e e 不但有利于降低 树的高度，还有利于节省存储空f 日j ，提高查询性能。 2 1 2 立方梯度挖掘问题的提出 d lt i m i e l i n s k i 等在文献【6 】中首次从多维空间角度来阐释关联规则，以寻求隐藏 在数据立方中的各种数据变化趋势，帮助用户进行更加有效的决策分析。关联规则的 直观意义就是客户在购买某些商品的同时有多大的倾向也会购买另外一些商品，以“9 0 的客户在购买面包和黄油的同时也会购买牛奶，而同时购买了面包和黄油的交易占 全部交易的o 6 ”这一关联规则为例，对应的概率规则的前件( a n t e c e d e n t ) i 由面包和黄 油构成，后件( c o n s e q u e n t ) 贝0 由牛奶单独构成。事实上，支持度0 6 就是面包和黄油同 时被购买的概率，可信度9 0 j j 是在已经购买了面包和黄油的前提下，再购买牛奶的 概率，也就是牛奶的条件概率。如果将上述的“面包”、“黄油”等看成是“销售数据 立方”中不同的维，上述关联规则可以看成有关下述变化的陈述：表示规则前件的数 据立方元组( 面包，黄油，支持度) ，当在加上规则后件而具体化成为数据立方元组( 面包， 黄油，牛奶，支持度) 时，它的度量值( 即支持度) 的变化。这里数据立方元组( 面包， 黄油) 以及( 面包，黄油，牛奶) 的支持度实际上都是通过聚集函数c o u n t 计算而来，两者 支持度的差表现为可信度。如果把聚集函数c o u n t 换成其它的聚集函数，例如m a x ， m i n ，s u m 和a v g 等等，那么就可以推而广之，获得类似表达因数据立方元组发生变 化而引起的各种度量变化。这就是数据立方梯度的基本思想。 为了规则易于解释以及避免搜索空间过大，目前数据立方梯度只考虑下述引发数 据立方元组发生变化的操作( 如图2 1 ) ：具体化( s p e c i f i c a t i o n ，即o l a p 术语中的下 钻) ，泛化( g e n e r a l i z a t i o n ，即o l a p 术语中的上卷) ，和突变( m u t a t i o n ，即仅仅改变 1 0 华中科技大学硕士学位论文 数据立方元组在某一维的值) 。显然，数据立方梯度要比关联规则更富于表达性，能够 支持更复杂、更广泛的假设分析。 在 图2 1 泛化、具体化和突变 2 1 2 约束性立方梯度挖掘 尽管数据立方中蕴涵了数量众多的立方梯度，但是用户只会对满足一定条件的立 方梯度感兴趣。根据用户指定的约束条件挖掘出与之相关的立方梯度，此即为文献f 4 6 1 中提出的约束性梯度挖掘。用户要考察的立方元组被称为探测元组( p r o b ec e l l ) ，与它一 起构成数据立方梯度的另一立方元组被称为梯度元组( g r a d i e n tc e l l ) 。约束条件可分为三 类，限定探测元组在维上、度量上的取值条件被分别称为探测约束c 。r b ( p r o b ec o n s t r a i t ) 、 意义约束c 。( s i g n i f i c a n t c o n s t r a i n t ) ，限定探测元组与梯度元组之间的度量差异的约束 条件被称为梯度约束c g r a d ( g r a d i e n te o n s t r m n t ) 。一般情况下，用户通过c 吣和c 。瑭来确 定对要考察的探测元组集，用c g r a d 来确定所要观察的立方梯度在度量上的变化大小。 在梯度联机挖掘环境中，用户在浏览数据立方过程中，只会对引起其注意力的立 方元组进行梯度挖掘，以进一步分析感兴趣的数据变化趋势。因而本文所研究的立方 梯度联机挖掘亦是约束性立方梯度挖掘。 2 2 现有算法分析 目前主要的约束性数据立方梯度挖掘算法有文献 4 6 中提出的a 1 1 s i g n i f i c a n t p a i r s 算法( 简称a s p 算法) 、l i v e s e t 算法和文献 4 7 中提出的e l i v e s e t 算法。其中l i v e s e t 华中科技大学硕士学位论文 是在a s p 算法的基础上改进而来，而e l i i v e s e t 是l i v e s e t 在浓缩数据立方之上的推广。 它们的一个共同点就是从零丌始、象生成数据立方一样计算出数据立方梯度来。 2 2 1a s p 算法 a s p 算法比较直观，首先利用如b u c 或h c u b i n g 算法【4 8 1 等数据立方计算算法从 给定的关系表r 中计算出满足意义约束c 。和探测约束c 。f b 的探测元组集p ，然后再对 p 中的每个探测元组c 。，利用数据立方计算与梯度约束c g r a d ( c g ，c p ) 计算出c p 的梯度元组 集。如果梯度约束c g 。d ( c g ，c p ) 是反单调的( 指如果数据立方元组c 不满足约束，则c 的 后代也不会满足该约束) ，就再利用梯度约束c g 。d ( c g ，c p ) 和c 。的度量值优化梯度元组的 计算过程。 当探测元组之间在某些维上的取值相同时，由于泛化、突变操作的性质，这些探 测元组可能会共享某些梯度元组。a s p 算法分别计算每一个探测元组c 。的梯度元组集， 就会造成共享梯度元组的重复计算，某些隋况下将导致严重的计算开销。 2 2 2l i v e s e t 算法 l i v e s e t 算法由a s p 算法改进而来，它对所有