（计算机应用技术专业论文）网格环境下的关联规则挖掘算法研究.pdf

中文摘要 舢舢f f f f f i 川川f f f f 舢f f f f f 删 、t17 8 9 513 网格是建立在i n t e r n e t 上的一种新兴的高性能计算平台，能够将各种计算资源整合 起来，转化为一种随处可得的、可靠的、经济的计算能力，具有分布性和异构性、共享 性和动念性、虚拟性等特点。数据挖掘是从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的潜在有用的信息或知识的非平凡过 程。关联规则是数据挖掘中的一种主要研究内容，体现了事物与事物之i 廿j 存在的相互依 存性和关联性，具有广泛的应用价值。本文，采用网格作为分布式计算平台，对关联规 则的分布式挖掘算法进行了研究。其主要的研究成果如下： 第一、网格环境下的频繁模式挖掘算法g r i d d m f 。该算法首先，在各站点分别独 立的挖掘出局部频繁项目集，归并产生候选全局频繁项目集；然后，对候选项集进行剪 枝，并将其广播给各站点；扫描一次数据库统计出各项目出现的次数，求得最终的全局 频繁项集。通过对候选项集的剪枝，减少了各站点f b j 的网络传输量，降低了各站点中项 目集的计算量，从而提高了全局频繁项目集的挖掘效率；最后，以恒星光谱数据作为形 式背景，通过实验验证了此算法的正确性和有效性。 第二、网格环境下f p t r e e 的分布式构造算法g r i d d b m a 。该算法首先，统计出全 局项目头表；然后，各站点根据这个项目头表的顺序，独立构造局部频繁模式树b f p t r e e ， 利用合并算法将各局部树合并为一颗全局频繁模式树，并在全局频繁模式树上提取出所 求的频繁项目集，通过对传统频繁模式树的存储结构的改进，减少了树的规模及站点间 的网络通信量，并使树的遍历更加方便有效，提高了合并效率，从而提高了整个频繁项 目集的挖掘效率。最后，采用天体光谱数据作为形式背景，实验验证了该算法的f 确性 和有效性。 关键字：分和式数据挖掘；网格；关联规则；最小支持度；恒星光谱数掘 ab s t r a c t g r i di sad i s t r i b u t e dc o m p u t i n gp l a t f o r mb a s e do ni n t e r n e t ，c a ni n t e g r a t ea v a r i e t yo fc o m p u t i n gr e s o u r c e s ，a n dc o n v e r tt h er e s o u r c e si n t oak i n do fw i d e l y a v a i l a b l e ，r e l i a b l e a n de c o n o m i c a l c o m p u t i n gp o w e r i t h a sd i s t r i b u t e d ， h e t e r o g e n e o u s ，s h a r i n g ，d y n a m i ca n d v i r t u a la n ds oo n d a t am i n i n gi sa n o n t r i v i a lp r o c e s so fd i s c o v e r i n gi m p l i c i t ，p r e v i o u s l yu n k n o w n ，p o t e n t i a lu s e f u l p a t t e r n s o ri n f o r m a t i o nf r o m i n c o m p l e t e ，n o i s y , f u z z y , r a n d o m d a t as e t a s s o c i a t i o nr u l ei so n eo ft h em a i nr e s e a r c hc o n t e n t so fd a t am i n i n g ，r e f l e c t st h e d e p e n d e n c ya n dr e l e v a n c eb e t w e e nt h i n g s a n dh a sb r o a da p p li c a t i o n i nt h i s p a p e r , t h ed i s t r i b u t e dm i n i n ga l g o r i t h m so f a s s o c i a t i o nr u l ea r es t u d i e db yu s i n g t h eg r i da sad i s t r i b u t e dc o m p u t i n gp l a t f o r m t h em a i ns t u d yw o r k sa r ea s f o l l l o w s ： f i r s t ，af 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 ( g r i d d m f ) b a s e do nt h eg r i di s p r e s e n t e d t h el o c a lf r e q u e n ti t e ms e t sa r ei n d e p e n d e n t l ym i n e di ne a c hn o d e ， a n dm e r g e di n t ot h ec a n d i d a t eg l o b a lf r e q u e n ti t e m s e t s t h e n ，t h ec a n d i d a t e i t e m s e t sa r ep r u n e d ，a n db r o a d c a s t e dt oo t h e rn o d e s t h el o c a lc o u n t so ft h e g l o b a lc a n d i d a t ei t e m sa r ec o l l e c t e df o rt h ef i n a lg l o b a lf r e q u e n t i t e m s e t sb y s c a n n i n gt h ed a t a b a s e b yp r u n i n gc a n d i d a t ei t e m s e t s ，t h ec o m m u n i c a t i o nc o s t b e t w e e na l ln o d e s ，a n dt h ec a l c u l a t i o no ft h ei t e m s e t sa r er e d u c e d ，t h e r e b yt h e o v e r a l lm i n i n ge f f i c i e n c yi si m p r o v e d i nt h ee n d ，t h ee x p e r i m e n t ss h o wt h e v a l i d i t ya n de f f e c t i v e n e s so f t h ea l g o r i t h mb yu s i n gs t a rs p e c t r a ld a t as e t s e c o n d ，ad i s t r i b u t e da l g o r i t h mo fc o n s t r u c t i n gf p t r e e ( g r i d d b m a ) b a s e d o nt h eg r i di sp r e s e n t e d a tf i r s t ，t h eg l o b a li t e mh e a dt a b l ei sm a d e ，t h e n ，t h e l o c a lf r e q u e n tp a t t e mt r e e ( b f p t r e e ) i sc o n s t r u c t e di n d e p e n d e n t l ya c c o r d i n gt o t h eo r d e ro ft h ei t e mh e a dt a b l ei ne a c hn o d e t h em e r g e a l g o r i t h mi su s e dt o u n i t et h el o c a lf r e q u e n tp a t t e r nt r e e si n t oag l o b a lt r e e ，w h i c hc o u l de x t r a c tt h e g l o b a lf r e q u e n t i t e m s e t s b e c a u s eo ft h ei m p r o v i n gt h et r a d i t i o n a ls t o r a g e s t r u c t u r e so ff r e q u e n tp a t t e r nt r e e ，t h es i z eo ft h et r e ea n dt h ec o m m u n i c a t i o n b e t w e e nn o d e sa r er e d u c e d ，t h et r a v e r s a lo ft r e ei sm o r ec o n v e n i e n ta n de f f e c t i v e ， i i l a n dt h em i n i n ge f f i c i e n c yo ff r e q u e n ti t e ms e t si s i m p r o v e d i nt h ee n d ，t h e e x p e r i m e n t ss h o wt h ev a li d i t ya n de f f e c t i v e n e s so ft h ea l g o r i t h mb yu s i n gs t a r s p e c t r a ld a t as e t k e y w o r d s ：d i s t r i b u t e dd a t am i n i n g ；g r i d ；a s s o c i a t i o nr u l e s ；m i n i m u ms u p p o r t ； s t a rs p e c t r a ld a t a i v 目录 第一章绪论1 1 1 数据挖掘1 1 1 1 数据挖捌的定义1 1 1 2 数据挖掘流程1 1 1 3 数据挖掘的方法2 1 1 4 数据挖掘的功能4 1 2 关联规则5 1 2 1 关联规则的概念5 1 2 2 关联规则挖掘方法5 1 2 3 国内外研究现状6 1 3 网格计算7 1 3 1 基本概念7 1 3 2 基本特点8 1 3 3 体系结构8 1 4 本文的主要研究内容及论文的组织结构1 0 1 4 1 论文的主要研究内容1 0 1 4 2 论文的组织结构1 0 第二章关联规则的基本概念1 1 2 1 基本概念1 l 2 2 频繁模式挖掘算法1 2 2 2 1a p r i o r i 算法1 2 2 2 2f p g r o w t h 算法1 3 2 3 小结1 5 第三章网格环境下的频繁模式分布式挖掘算法1 7 3 1 引言1 7 3 2 基于剪枝的频繁模式分布式挖掘1 8 3 2 1 基本概念1 8 3 2 2 基本思想1 9 3 2 3 分布式挖掘的网格服务模式2 0 v 3 3 基于剪枝的分前j 式频繁模式挖掘算法2 l 3 3 1 算法描述2 l 3 3 2 算法分析2 3 3 4 实验结果分析2 3 3 5 小结2 4 第四章网格环境下的f p - t r e e 分布式构造方法与算法2 7 4 1 引言2 7 4 2 网格环境下的f p 一树分布式构造方法2 8 4 2 1 基本概念2 8 4 2 2 基本思想3 0 4 2 3 服务模式3 0 4 3 网格环境下的f p 一树分布式构造算法3 l 4 3 1 算法描述3 1 4 3 2 算法分析3 4 4 4 实验结果及分析3 5 4 5 小结3 6 第五章总结与展望3 7 5 1 总结3 7 5 2 展望3 7 参考文献3 9 研究生期间发表的文章及参与项目4 3 致 射4 5 第一章绪论 第一章绪论 1 1 数据挖掘 科技的进步，特别是信息产业的发展，将人类带入了一个崭新的信息时代，经济的 飞速发展使的各行业都产生了大量的数据。随着计算机应用的普及和数掘库技术的不断 发展，数据库管理系统的应用领域越来越广泛，人们已经利用计算机取代了绝大部分手 工操作。最近十几年中，数据库中存储的数据最急剧增大，例如：人类基因组数据库项 目已经搜集了数以g b 级的人类基因编码数据。面对同益扩大的数据库规模，信息量过 大，真伪难辨，人们无法j f 确的运用隐藏的有用信息，传统的数据库技术面临了极大的 挑战。如何4 能从海量数据库和大量繁杂信息中提取有价值的知识，进一步提高信息的 利用率，由此引发了对数据挖掘理论和技术的研究。数据挖掘领域的研究工作是适应市 场竞争的需要的，它可以为决策者提供重要的知识，找出数据之间潜在的相关性，帮助 决策者预测未来的发展趋势进而做出合理的决策。 1 1 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ，简称d m ) 是指从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的，潜在有用的信息或知识的非平 儿过程l 。数据挖掘又称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yf r o md a t a b a s e ，简 称k d d ) 。简单来讲，数据挖掘就是分析大量数据用以发现有意义、有价值的模式和规 则的过程1 3j 。 数据挖掘引起了信息产业界的极大关注，其主要原因是存在大量数据可以广 泛使用，这些数据的规律比较难寻，而且迫切需要将这些数据转换成有用的信息 和知识。获取的信息和知识可以广泛用于各种应用，包括商务管理，生产控制， 市场分析，工程设计和科学探索等领域。数据挖掘主要利用了来自如下一些领域 的思想：( 1 ) 统计学的抽样、估计和假设检验；( 2 ) 人工智能、模式识别和机器学 习的搜索算法、建模技术和学习理论。数据挖掘也迅速地接纳了来自其他领域的 思想，这些领域包括最优化、进化计算、信息论、信号处理、可视化和信息检索。 一些其他领域也起到重要的支撑作用。特别地，需要数据库系统提供有效的存储、 索引和查询处理支持。高性能计算的技术在处理海量数据集方面常常是重要的。 1 1 2 数据挖掘流程 数掘挖掘是一个多步骤的处理过程，大体分三部分：数据准备，数据挖掘和知识发 现，数据挖掘后分析处理。数掘挖掘的一般流程可表示如下图卜1 1 5 j ： 1 网格环境卜的关联规则挖掘算法研究 图1 1 数据挖掘流程 p i g 1 1 t h ef l o wo f d a t am i n i n g ( 1 ) 定义问题：熟悉背景知识，清晰地定义出所求问题，弄清数据挖掘的目的。在 问题定义过程中，数据挖掘人员必须和领域专家以及用户紧密协作，认清数据挖掘目的 是数据挖掘的重要一步。 ( 2 ) 数据选择：数据选择的目的是确定挖掘任务的操作对象，即目标数据。收集所 有内部或外部相关信息，从符合要求的大型数据库和数据仓库1 7 1 标中提取数据挖掘的目 标数据集。 ( 3 ) 数据预处理：对提取的数据进行再加工，一般可能包括检查数据的完整性及数 据的一致性，去除噪声，消除重复记录，填补丢失的域等。 ( 4 ) 数掘挖掘：首先根据对问题的定义，明确挖掘的任务或目的后，再决定使用什 么样的算法：根据数据的特点和用户的要求选择相应的算法，在净化和转换处理过的数 据集上进行数据挖掘，提取出用户所需要的知识。 ( 5 ) 结果分析及评价：对数据挖掘的结果进行解释和评价，转换成为能够最终被用 户理解的知识。整个挖掘过程是一个不断反馈的过程，通过评价，如果存在冗余的模式 可将其剔除；也可能产生了不满足用户要求的模式，这时可能需要将整个发现过程退回 到先前阶段，甚至从头重新丌始，直到用户满意为止。 1 1 3 数据挖掘的方法 数据挖掘相关的理论和技术可以分别按挖掘任务、挖掘对象和挖掘方法来分类，常 用的挖掘方法有【1 2 j ： ( 1 ) 粗糙集( r o u g hs e t ) 粗糙集是一种新的处理含糊性和不确定性问题的数学工具。通过给定的对象集合的 若干个属性描述，将对象按属性的取值情况形成若干等价类，统一等价类中的对象不可 分辨，再根据给定集合的上近似和下近似的定义用于对信息系统中的属性进行约简，最 终取得所需属性规则。 2 数据埘象的集合 法、层次的方法 ( 3 ) 决策树( 决策树是一 枝描述测试结果 次递归处理各子 性进行描述的方法。很多聚类分析方法实现的是对数据对象的“硬划分”，但客观事物 的类属往往并不是十分明确。模糊聚类方法对对象的这种不分明的类属性质进行了很好 的表达和处理，这种方法已经广泛应用到各个领域。 ( 6 ) 神经网络( n e u r a ln e t w o r k ) 神经网络是指由简单计算单元组成的广泛并行互联的网络，能够模拟生物神经系统 的结构和功能。为实现神经网络的计算功能，需分别给出计算单元的计算模型和网络的 连接方式。最早的神经模型是美国心理学家m c c u l l o c h 提出的m p 模型。 ( 7 ) 统计分析方法( s t a t i s t i c a la n a l y s i s ) 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性关系) 和 相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析可采用统计学 方法，即利用统计学原理对数掘库中的信息进行分析。可进行常用统汁( 求大量数据中 的最大值、最小值、总和、平均值等) 、回归分析( 用回归方程来表示变量间的数量关系) 、 相关分析( 用相关系数来度量变量| 、日j 的相关程度) 、差异分析( 从样本统计量的值得出差 异术确定总体参数之问是否存在差异) 等。 另外还有可视化技术、遗传算法、最邻近技术、b a y e s i a n 网络等方法。 3 网格环境卜的关联规则挖掘算法研究 1 1 4 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务般町以分 两类：描述和预测。描述性挖拥；任务刻划数据库中数据的一般特性。预测性挖掘任务在 当自订数据上进行推断，以进行预测进一步做出基于知识的决策。数据挖掘的最终目标是 从数据库中发现隐含的、有用的知识，其主要有以下六类功能1 3 4 l ： ( 1 ) 概念描述( c o n c e p td e s c r i p t i o n ) 对含有大量数据的数据集合进行概述性的总结并进行简明、准确的描述，这种描述 就称为概念描述。具体的描述分为特征性描述和区别性描述。其中，特征性描述用于描 述某类对象的共同特征，区别性描述用于描述不同类对象之间的区别。 ( 2 ) 分类和预测( c l a s s i f i c a t i o na n dp r e d i c t i o n ) 分类是首先找出能够描述数据集合典型特征的模型或函数，以此来分类识别未知数 据的归属或类别，将未知数据映射到某种离散类别之一。分类的关键是确定对数据集合 按照什么标准或什么规则进行分类。分类模型或函数可以通过分类挖掘算法从样本数据 中学习获得。预测是依据历史数据建立模型，用新数据做为输入变元，以获得对未来行 为的预测。 ( 3 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值 之问存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联 分析的目的是找出数据集间的关联关系或者数据与数据间的派生关系，有时并不知道数 据库中数据的关联函魏即使知道也是不确定的，因此关联分析生成的规则带有可信度。 ( 4 ) 聚类分析( c l u s t e r i n ga n a l y s i s ) 聚类用于从数据集中找出相似的数据并组成不同的组。聚类增强了人们对客观现实 的认识，是概念描述和偏差分析的先决条件。与预测模型不同，聚类中没有明显的目标 变量作为数据的属性存在。8 0 年代初，m c h a l s k i 提出了聚类概念技术及其要点是，在划 分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了 传统技术的某些片面性。 ( 5 ) 孤立点分析( o u t l i e r a n a l y s i s ) 孤立点是数据库中的那些与数据的一般行为或模型不一致的数据埘象。孤立点是实 际生活中的反常行为的写照，以往的大部分数据挖掘方法在正式进行数据挖掘之自i 就将 孤立点视为噪声或异常而将其丢失。但是在一些应用场合中，如各种商业欺诈= 行为的检 测，那些罕见的小概率事件或数据比正常的那些更有趣、更有价值。 4 第一章绪沦 ( 6 ) 演化分析( e v o l u t i o na n a l y s i s ) 数据演化分析描述对象的行为随时问变化的规律或趋势，并对其建模和规划。这可 能包括时间相关数据的特征化、区分、关联、分类或聚类，这类分析的不同特点包括时 间序列分析、序列或周期模式匹配和基于类似性的数掘分析。 1 2 关联规则 1 2 1 关联规则的概念 关联规则反映了事物与事物之i 、日j 存在的相互依存性和关联性。关联规则挖掘就是从 大量的数据中挖掘出有价值描述数据项之间相互联系的有关知识【l 】。随着存储在数据库 中的数据规模越来越大，人们对从这些数据中挖掘相应的关联知识越来越有兴趣。例如： 从大量的商业交易记录中发现有价值的关联知识可帮助进行商品分类设计、降价经销分 析、生产安排、货架排放营销或进行其它有关的商业决策。 关联规则是由r a g r a w a l 于1 9 9 3 年提出，它在商业等领域的成功应用，使它成为 数据挖掘中最成熟、最主要、最活跃的研究内容。关联舰则是形如“a b ”的蕴含式， 反映一个事物与其他事物之f n j 的相互依存性和关联性。关联规则挖掘就是要找出隐藏在 数据项之间的有价值的联系，发现大量数据中项目集之间满足一些基本要求( 如最小支 持度和最小置信度) 的所有有趣的关联或相关性。关联规则的支持度和置信度是两个度 量有关规则兴趣性的方法。它们分别描述了一个被挖掘出的关联舰则的有用性和确定 性。如果一个关联规则满足最小支持度阈值和最小置信度阈值，那么就认为该规则是有 意义的，用户或专家可以白行设置最小支持度阂值和最小置信度阈值。 根据不同的标准，关联规则可以分成若干类型：根据规则所处理的值的类型，可分 为稚尔型和多值型。根据规则描述内容所涉及的抽象层次，分为单层、多层及交叉层。 根据对关联挖掘的不同扩充，可扩充为相关分析和最大频繁模式与频繁闭项集挖掘。此 外，还有挖掘空间关联规则，挖掘周期性关联规则，挖掘负关联规则，挖掘交易内部关 联规则等。 1 2 2 关联规则挖掘方法 挖掘关联规则主要包括以下两个步骤1 2 j ： 步骤一：发现所有的频繁项集。步骤二：根据所获得的频繁项集，产生相应的强关 联规则。由于第二步中的操作比较简单，因此挖掘关联规则的整个性能就由第一步中的 操作处理所决定。 单维布尔型的规则是最基础的关联规则挖掘，主要有两种基本算法：a p r i o r i 算法1 6 】 和f p g r o w t h l 7 1 算法。a p r i o r i 算法是一个很有影响的关联规则挖掘算法，为了提高它的 s 网格环境卜的x - 联规! j ! l j 挖捌算法彬究 有效性，专家们已经提出了许多a p r i o r i 算法的变形，如散列项集计数、事物压缩、划 分数据、抽样、动态项集计数等。山事务数据库挖掘多层关联规则一般采用白定向下的 策略，由概念层1 开始向下，到较低的更特定的概念层，对每个概念层的频繁项集累加 计数，直到不能再找到频繁项集；对于每一层，可以使用挖捌频繁项集的任何算法，如 a p r i o r i 或它的变形。另一种是f p g r o w t h 算法，该算法采用分治策略，将所有频繁项集 压缩到一棵频繁模式树( f p 树) ，同时保留项集关联信息；然后将这种压缩后的数据库 分成一组条件数据库，每个关联一个频繁项，并分别挖掘每个数据库。研究表明： f p g r o w t h 方法对于挖掘长的和短的频繁模式都是有效的和可伸缩的，并且大约比 a p r i o r i 算法快一个数量级。 由关系数据库和数据仓库挖掘多维关联规则的技术可以根据量化属性的处理分为 三种基本方法：使用预定义的概念分层对量化属性离散化，离散化后的数值属性具有区 间值可以像分类属性一样处理；根据数据的分布，将量化属性离散化到“箱”，箱可以 在挖掘过程中进一步组合；为紧扣区间数据的语义，将量化属性离散化，此处离散是动 态的，考虑数据点之间的距离，因此这种量化关联规则称作基于距离的关联规则。 关联规则挖掘过程可能发现数以力计的规则，其中许多信息用户并不感兴趣。基于 约束的数据挖掘，可以按照用户给定的条件进行挖掘，使得挖掘过程更有效。这些约束 包括：知识类型约束、数据约束、层约束、兴趣度约束及规则约束。 1 2 3 国内外研究现状 频繁项目集挖掘是关联规则挖掘应用中的关键技术和步骤，以r a g r a w a l 等人提出 的a p r i o r i 算法最为著名，其后的许多挖掘算法大多是对a p r i o r i 算法的改进或衍生变种， 如：a p r i o r i t i d 算法【l o 】、a p r i o r i p r o 算法【1 1 1 、a p r i o r i h y b r i d 算法【1 2 1 等，但它们都不可避 免的要在挖掘过程中生成大量的候选项集，计算候选项集的支持数最耗时。 另一类以f p g r o w t h 算法为代表，通过扫描数据库构成频繁项目的列表，将所有频 繁1 项集按列表顺序构造频繁模式树( f p t r e e ) ，这样就将事物数据库各项间的关联信息 保留在树中，这样，频繁模式的挖掘问题就转换成挖掘f p t r e e 的问题。 在频繁项集中存在着较多的冗余，因此人们采用各种方法，试图减少频繁模式巾的 冗余。目前的方案主要有挖掘频繁闭项集( f r e q u e n tc l o s e di t e ms e t s ，f c i ) 和最大频繁项集 ( m a x i m a lf r e q u e n ti t e ms e t s ，m f i ) 1 2 j ，其中以m f i 的规模最小，而且町以通过m f i 导出f c i 和f i 。因此，最大频繁项集挖掘受到许多研究者的关注，相继出现了一些最大频繁项集 挖掘算法，如：m a x m i n e r l l3 1 ，p i n c e r s e a r c h l l4 1 ，d e p t h p r o j e c t l l ”，m a f i a l l6 1 ，g e n ma x i 7 】 以及d m f i l l 8 i 等。b a y a r d o 提出的m a x m i n e r 算法突破传统自底向上的搜索策略，采用 6 广度优先 从而较低 可能会陷 并采用深 用了与枚 多种剪枝 大频繁项 是利用d i 效率基本 数据库的 m a x m i n e 关信息， 掘最大频 u e n ti t e ms e t st r e e ) q b ，在一定程度上提高了存取速度。颜跃进提出的f p m f i l 2 2 1 算法使用 投影进行超集检验，缩减了超集检测的时间，并通过删除f p 一子树中与最大频繁项集无 关的冗余信息，有效地压缩了树的规模，减少了遍历的丌销。 1 3 网格计算 1 3 1 基本概念 网格技术是一种地理上分布的高性能计算基础平台，它将高速互联网、高性能计算 机、数据库、远程设备等融为一体，以实现各种软件及硬件资源的共享【8 1 。2 0 世纪8 0 年代，人们为了满足大规模应用对计算资源的需求，提出了元计算的概念，将一组通过 互联网链接起来的性质不同的资源集合起来，作为对用户透明的计算环境向用户提供服 务，1 9 9 5 年在元计算的典型代表i - w a y 项目中明确提出了网格的概念。19 9 8 年，网格 的奠基人i a nf o s t e r 和c a r l 在相关文献中首次对网格进行了定义：计算网格是一个包含 硬件和软件的基础设施，它能对高端计算能力提供可靠的、一致的、廉价的接入。2 0 0 1 年，i a nf o s t e r 进一步指出，网格关心的是在动态的、多机构的虚拟组织中协调资源共享 和协同解决问题，其核心思想是在一组参与节点中协商资源共享和管理的能力，利用协 商得到的资源池共同解决一些问题。近年来，网格技术已逐步成熟并得到迅速发展，其 使用范围也不再局限于科学研究项目中，而是被更多的学校、企事业单位所使用。 i a nf o s t e r 提出了网格有三个判断标准：协调非集中控制的资源；使用标准、丌放、 通用的协议及接口；提供非平儿的服务。同时，很多其他学者也提出了不同的网格的概 7 网格环境卜的天联规则挖捌算法研究 念，尽管学者们对网格技术的解释不同，但其核心综合起来就是利用网络将分散在不同 地理位置的电脑组织成一台虚拟的超级计算机，让用户全【面共享网络上的计算资源、信 息资源、数据资源、软件资源、存储资源、通信资源、专家资源等。就比较而言，互联 网实现了计算机硬件的连通，w w w 实现了网页之l 日j 简单的物理连接，网格则是为了实 现网络上所有资源的全面连通。 1 3 2 基本特点 网格作为新兴的计算工具，能够将各种计算资源整合起来，转化为一种随处可得的、 经济的计算能力，具有自身的一些特点【8 】： ( 1 ) 超级计算能力。网格技术能够为科学研究领域和社会经济生活领域提供超级计 算能力。网格的数据挖掘体系结构建立在网格计算技术基础上，数据的传输及计算处理 都具有高效的并行性的特点。 ( 2 ) 分布性和异构性。组成网格的各种资源，在地理位置上是广泛分布的，这些资 源包括计算资源、数据资源、仪器资源等，可以分布在同一地域内或不同地域，甚至不 同的国度。同时，组成嘲格的资源足异构的，对于存储资源来说，有不同的存储系统， 不同的存储方式，不同的访问方式等，同样对于其它资源也存在类似的问题。因此，网 格系统需要解决好资源调度与不同资源之i h j 的接口问题。 ( 3 ) 共享性和集成性。网格的目的是资源共享，用户可以方便的共享整个网络资源， 并且这种共享是深层次的，可以实现多个资源的无缝集成，远远超过现在的因特网所提 供的资源共享程度。 ( 4 ) 抽象性和虚拟性。网格把实际的物理资源抽象为虚拟的逻辑网格资源，网格用 户只需要遵循网格接口的标准，向网格服务器发出资源请求消息，就可以获得符合该请 求的资源，但用户得到的知识物理资源的的逻辑抽象资源，网格向用户屏蔽了物理资源 的细节，用户看不到物理资源，只要关心能够实现什么就行。 ( 5 ) 自治性和动态性。网格上广域分布的各种资源开始都是属于某个组织或个人的， 资源的拥有者对资源具有最高级别的管理权，允许拥有者埘资源进行自主管理，因而具 有自治性。此外，网格上的资源都是动态创建和删除的，能够灵活调整数据搜索的范围。 1 3 3 体系结构 网格体系结构是构建网格环境的基础，为了动态建立虚拟组织，实现跨区域的虚拟 组织管理和资源共享，需要对网格体系结构进行研究。下面介绍两种有代表性的网格体 系结构陋i 。 1 ) 五层沙漏结构 r 第一章绪论 图1 - 2 是五层沙漏模型，它定义了每一层的运行机制、接口和协议等，支持资源提 供者和用户之i 日j 建立资源共享关系。下面简单介绍一下垓模型结构。 |胁用层 l 上 t i ：聚层 1r 资源层 1 i连接层 i 图1 - 2 五层沙漏模型 l o g s i 或w s r f 宿主环境j 协议绑定 1r r l宿主环境协议l i 图1 - 3o g s a 网格体系结构模型 f i g 1 。2f i v eh o u r g l a s sm o d e lf i g 1 。3g r i da r c h i t e c t u r e 最底层是基础结构层，基本功能是管理局部的资源，向上层提供访问这些资源的接 口。基础结构层上面是连接层，连接层的基本功能是实现安全的相互通信，这是资源之 间进行相互操作的前提。它定义了核心的通信和认证协议，通信协议允许在构造层资源 之间交换数据。实际应用中，这些协议大部分是从t c p h p 协议栈中提取的。连接层上 面是资源层，其主要功能是实现对单个资源的共享。包括两方面的协议：信息协议和管 理协议。信息协议可以得到资源的结构和状态信息；管理协议用于通过认证访问资源， 并监控并控制操作的状态及功能。汇聚层是将多个资源集合起来协调多种资源问的的共 享问题。最上层是应用层，包含了在虚拟组织环境下运行的用户应用。之所以称为沙漏 结构，是因为各层的协议数量不同，核心层既要能够实现对上层各协议的映射，又要能 实现对下各层协议的映射，核心协议在所有支持网格计算的地方都应得到支持。因此， 核心协议的数量不能太多，这样核心协议就形成了层次结构中的一个瓶颈。图中，资源 层成为了核心的瓶颈部分。 2 ) 丌放网格服务体系结构( o g s i ) 开放网格服务体系架构( o p e ng r i ds e r v i c ea r c h i t e c t u r e ，简称o g s a ) 是以服务为中 心的结构，如图1 - 3 所示。该模型的每一层都定义了相应的功能，其核心层是o g s i 和 o g s a 服务层，o g s i 后来发展成为w e b 服务资源框架( w s r f ) ，w s r f 可以看作是在结 合性的w e b 服务标准的基础上对o g s i 的重新整合，这种整合使得w s r f 与现有的w e b 服务标准相兼容，利用现有的服务丌发工具构建网格计算设施。网格服务是对w e b 服 0 网格环境卜的关联规则挖掘算法研究 务的一个扩展，它把g l o b u s 标准与面向商业应用的闪特网服务结合起来，把网格计算 从科研应用扩展到更广泛的以分布式系统服务为主的应用领域。 网格的特点使得网格具有比传统分布和并行系统更复杂的内部结构。网格所研究的 分层模型由底向上的四个层次依次是网格纤维层、网格巾问件层、网格工具层和网格应 用层。网格中问件是对特定网格体系结构的实现，为网格计算提供了一系列的基本服务， 包括通信服务、信息和注册服务、安全认证服务、远程进程管理服务、资源分配服务以 及数据访问服务等。网格中间件是网格计算的核心层次。不同的网格体系结构具有不同 的网格工具，近年来，出现了许多网格应用的工具包和软件环境，比如： c o n d o r l 2 5 1 ，l e g i o n t 2 6 】和u n i c o r e 2 7 1 ，其中，应用最为广泛的是g l o b u st o o l k i t l 2 8 j 网格中问件， 它虽然没有被确定为标准，但在实际应用中几乎成为默认的构建网格体系结构的标准， 它为网格用户提供了一个可实施协作的、虚拟的应用环境及应用丌发环境。 1 4 本文的主要研究内容及论文的组织结构 1 4 1 论文的主要研究内容 频繁模式挖掘足一种重要的关联规则挖掘任务，在现实生活中的应用也很广泛。本 文的主要研究内容是从一般的关联规则挖掘算法入手，针对当自订许多分和式算法中存在 的一些问题或不足：分布式节点问数据通信量比较大，i o 时问丌销多，计算资源不能 充分利用等，进行了一些改进，并在网格服务的分布式环境下进行了实施。第一，针对 合并后的候选全局频繁项集的规模过大、网络传输量和项集频数的计算量比较多，提出 相应的剪枝策略；第二，主要针对网格环境下的f p 树的分布式构造方法进行了研究， 使之在分布式环境下可以一次性挖掘出完备的全局频繁项目集。 1 4 2 论文的组织结构 论文内容共分为五个章节，具体组织如下概述： 第一章介绍了数据挖掘、网格技术的基本概念，频繁模式挖掘及国内外研究现状。 第二章介绍关联规则的定义及相关理论，以及关联规则挖掘的两种基本算法。 第三章主要介绍了网格环境下的频繁模式分布式挖掘算法，通过对候选全局频繁 模式集进行剪枝，减少了候选集的规模，提高了频繁项集的挖掘效率。 第四章主要介绍网格环境下的f p 一树分布式构造方法与算法，提出一科，新的频繁 模式树的存储方式，通过对树结构的改进减小了树的舰模，降低了网络通信量，并使树 的遍历简单化，提高了树的合并效率。 第五章对本文所做的研究工作进行总结，并展望今后进一步要做的工作。 1 0 第- 二章关联规则的摹本概念 第二章关联规则的基本概念 2 1 基本概念 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的 取值之间存在某种规律性，就称为关联。如果两个或多个事物之j j 存在一定的关 联关系，则其中一个事物就能通过其他事物推测到。关联可分为简单关联、时序 关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。 a g r a w a l 等于19 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问 题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他们的工作 包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘 规则的效率；对关联规则的应用进行推广。关联规则挖掘在数据挖掘中是一个重 要的课题，最近几年已被业界所广泛研究。参照文献【1 5 】，关联规则的一些基本 概念和定义描述如下： 定义2 1 关联规则挖掘的事务数据集记为d ，d - t l ，t 2 ，t p ，t 。) ，t i = i l ，i 2 ， i k ，i m ) ，t p ( p = l ，2 ，n ) 称为事务( t r a n s a c t i o n s ) ，i k ( k = l ，2 ，m ) 称为项( i t e m ) 。 定义2 2 设i = “，i 2 ，i m 是d 中全体数据项的集合，i 的任意子集x 称为d 中的 项集( i t e m s e t ) ，i x l = k ，则称集合x 为k 项目集。设t p 为d 中的事务，x 为d 中的项目 集，x c _ t p ，则称事物t p 包含项目集x 。每一个事务都有一个唯一的标识符，称为t i d 。 定义2 3 数据集d 中包含项目集x 的事物数称为项目集x 的支持数，记为c o u n t ( x ) 。 项目集x 的支持度记为s u p p o r t ( x ) ： s u p p o r t ( x ) = c o u n t ( x ) l di 10 0 ( 2 1 ) 其中1d1 是事务数据集d 的事务数，若s u p p o r t ( x ) 不小于用户指定的最小支持度阈 值( m i n s u p p o r t ) ，则称x 为频繁项目集( f r e q u e n ti t e m s e t ) ，否则x 为非频繁项目集。 定义2 4 若项目集x 、y ，且x n y = o ，形如x y 的蕴涵式称为关联规则，x 、y 分别称为关联规则x j y 的前提和结论。项目集x u y 的支持度称为关联规则x y 的 支持度，记作：s u p p o r t ( x = y ) ，规则的置信度汜作：c o n