（计算机应用技术专业论文）关联规则并行采掘算法的研究.pdf

硕士学位论丈 m a s l e r s1 1 i e s i s 摘要 随着信息技术的迅猛发展，各个部门积累了海量数据，迫切要求从这些数 据中自动地采掘有价值的信息和知识以支持决策。于是数据采掘技术应运而 生。关联规则采掘是数据采掘中的一个重要分支，也是目前应用最广泛的一种 数据采掘类型。 目前传统的关联规则采掘技术大多采用串行算法，例如l e v e l w i s e 算法、 n o n 1 e v e l w i s e 算法以及不产生候选项目集的算法，其中r a g r a w a l 等人提出的 a p r i o r i 算法是处理事务数据库中大项目集较为有效的算法。这些算法总的来 说，都需要对数据库作多遍重复扫描，降低了采掘效率，不能满足大数据库的 要求。随着分布式数据库的发展，提出了采掘关联规则更有效的并行算法，如 l e v e l w i s e 并行模式，d m a 并行模式等，明显地提高了采掘效率。其中p s p a d e 算法是一种广泛应用于大型数据库上快速采掘频繁序列的有效并行算法，它将 搜索空间分成了更小的基于后缀的类，可在每个处理器上独立地处理，实现了 数据的本地性最大化和同步的最小化。 本文通过对p s p a d e 算法的研究，发现算法执行中，处理器将所有的类和它 的中问i d 列表存于主存，导致了大量的内存开销。当处理更大的数据集时， 容易产生内存不足而溢出。本文根据搜索算法内存管理的思想，提出了一种内 存扩展方案来解决这一问题。在内存不足和获得足够内存两种情况下，把部分 类写入磁盘，释放了内存空间，缓解了内存的压力。在程序需要时，再将写入 磁盘的类加入共享队列作为多余的类处理。本文通过对这种方案的分析，指出 了它的优缺点和适用范围。 关键词：k d d 数据采掘关联规则分布式数据库并行算法 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 fi n f o r m a t i o nt e c h n o l o g y , l a r g ea m o u n t so fd a t a h a v ea c c u m u l a t e di na l lk i n d so f d e p a r t m e n t s i tb e c o m e sm o r e a n dm o r e u r g e n tt o m i n eu s e f u li n f o r m a t i o na n dk n o w l e d g ea u t o m a t i c a l l yt os u p p o r tt h es t r a t e g i e s t h e t e c h n o l o g yo f d a t am i n i n ge m e r g e s ，a st h et i m e sr e q u i r e a s s o c i a t i o nr u l em i n i n g i sa n i m p o r t a n tb r a n c ho f d a t am i n i n g a n db e c o m e so n eo ft h ew i d e s ta p p l i e dd a t a m i n i n gs t y l e s h o w e v e r , t h et r a d i t o n a la s s o c i a t i o nr u l em i n i n g m o s ta d o p t e ds e r i a l a l g o r i t h m s ，s u c ha sl e v e l w i s ea l g o r i t h m s ，n o n l e v e l - w i s ea l g o r i t h m sa n da l g o r i t h m s t h a td on o tg e n e r a t ec a n d i d a t e s a p r i o r ia l g o r i t h mi sm o r ee f f i c i e n to n et od e a lw i t h l a r g ei t e m s e t si nt r a n s a c t i o nd a t a b a s ea m o n gt h e s ea l g o r i t h m s b u ta l l t h es e r i a l a l g o r i t h m sc a nn o ta v o i ds c a n n i n gd a t a b a s er e p e a t l y , w h i c hr e d u c e st h ee f f i c i e n c y o fm i n i n ga n d h a sn o a b i l i t y t om e e tt h en e e do f l a r g e d a t a b a s e w i t ht h e d e v e l o p m e n t o fd i s t r i b u t e dd a t a b a s e ，s o m ep a r a l l e lf o r m u l a t i o n sa p p e a rt op r u n n i n g r u l e ss u c ha sl e v e l w i s e ，d m a ，a n df m a ，w h i c h i m p r o v e t h ee f f i c i e n c yd r a m a t i e l y p s p a d e ，o n eo fp a r a l l e la l g o r i t h m sf o r f a s td i s c o v e r yo ff r e q u e n ts e q u e n c e si n l a r g ed a t a b a s e s ，d e c o m p o s e st h eo r i g i n a l s e a r c hs p a c ei n t os m a l l e rs u f f i x b a s e d c l a s s e sw h i c hc a nb es o l v e di n d e p e n d e n t l yo ne a c hp r o c e s s o nt h e nt h ep s p a d e a l g o r i t h ms u c c e e d si nm a x i m i z i n g d a t al o c a l i t ya n dm i n i m i z i n gs y n c h r o n i z a t i o n h o w e v e r , p s p a d e ，w o r k i n go n t h e a s s u m p t i o n t h a te a c hc l a s sa n di t s i n t e r m e d i a t ei d l i s t sf i ti nm a i nm e m o r y , w h i c h o c c u p i e s c o n s i d e r a b l em e m o r y s p a c e o n c eh a n d l i n g l a r g e rd a t a b a s e s ，i t w o u l dr u no u to fm e m o r y i nt h i s p a p e r , a m e m o r ye x t e n d i n gs c h e m ew a sp r o p o s e dt o s o l v et h i sp r o b l e m hw o u l dr e l e a s e i i 硕士学位论文 、i ”je r s 1 f i n i s l a r g es p a c eo fm e m e r yb yw r i t i n gs o m e c l a s s e st od i s kr e s p e c t i v e l yw h e nt h e r ei sn o e n o u g hm e m e r yo rw h e ne n o u g hm e m o r yi so b t m n e d i fn e c e s s a r y , t h e s ec l a s s e s w o u l dj o i nt h es h a r eq u e u e a tt h ee n do ft h i sp a p e r , p r o sa n dc o n s ，a sw e l la s a p p l i c a b i l i t yo f t h i ss c h e m e ，a r e p r o v i d e d k e y w o r d s ：k d d ，d a t am i n i n g ，a s s o c i a t i o nr u l e ，d i s t r i b u t e dd a t a b a s e ，p a r a l l e l a l g o r i t h m 硕士学位论文 m a s f e r s 7 1 1 e s i s 第一章引言 随着社会信息量的不断增大，数据库的数量和规模也在飞速增长，迫切需 要新的技术与工具来帮助人们从快速积累的大量数据中搜寻有用的信息。本文 根据当前的实际需要并结合国内外在数据采掘方面的研究进展，在清华大学智 能与系统国家重点实验室开放课题的资助下，对数据采掘中的关联规则进行了 详细地介绍，着重对关联规则的并行采掘算法进行了仔细地研究，并提出了对 现有p s p a d e 并行采掘算法改进的方案。 1 1 数据采掘的产生 随着数据库技术的迅猛发展，使得人们收集数据的能力大大提高，特别是 随着网络系统的流行更使得数据和信息爆炸性地增长。商业企业、科研机构和 政府等部门在过去若干年里都积累了海量的、以不同形式存储的数据，这些数 据异常庞大和繁杂，而且仍在不断增长，要从这些数据中发现有价值的信息和 知识并达到为决策服务的目的已成为非常艰巨的任务。传统的统计分析( 如计 算均值、标准方差等) 在一定程度上是有用的，但还不能揭示隐藏于大量数据 中的知识，依赖人工对这些g b 甚至t b ( 1 0 ”) 数量级的数据进行有效的分析 也是不可能的。数据的极大丰富而数据分析工具的匮乏使得研究并设计一种可 以从大规模数据中自动、高效地提取有价值的信息或知识的数据处理分析新技 术追在眉睫，数据采掘正是为了解决这个问题而在八十年代末产生并在九十年 代发展起来的新兴的研究领域 l 】。 数据采掘作为一种可从海量数据中自动地提取有价值的信息和知识以有 效地支持决策的新技术1 6 1 ，它既是信息科学的前沿课题，也是一个融合了多个 研究领域的理论和实践问题。目前，数据采掘已经成为了数据库、人工智能、 统计分析等领域的重要研究课题，数据采掘技术已经被成功地应用到商业、金 融业等各个行业中 ”。随着社会生活的数字化、信息化程度的进一步提高，以 硕士学位论文 、1 、州f r sj i f f s f 、 及数据采掘技术的进一步发展和成熟，其必将具有更为广阔的应用前景【2 】【“。 1 2 数据采掘的定义 数据采掘( d a t am i n i n g ) ，又称为数据挖掘、数据开采等。一般认为数据 采掘是数据库中知识发现( k n o w l e d g ed is c o v e r yi nd a t a b a s e ，简称k d d ) 的 一个环节。，是采用具体的数据采掘算法从数据中自动高效地提取有用模式的 过程，而k d d 是包含数据采掘、数据准备等环节的循环往复过程。k d d 的定义 随蓄人们研究的不断深入也在不断完善，在k d d 研究领域一致认可的描述性定 义是f a y y a d 等人给出的1 ： k d d 是从数据集中识别出有效的、新颖的、潜在有用的、以及最终可理解 的模式的高级处理过程。 在k d d 中模式的有效性、新颖性、潜在有用性和最终可理解性综合在一 起称为兴趣度( i m e r e s t i n g n e s s ) 1 4 1 1 。 从定义中可以看出，k d d 是一个高级的处理过程，它从数据集中识别出 以模式来表示的知识。高级的处理过程是指一个多步骤的处理过程，多步骤之 问相互影响、反复调整，形成一种螺旋式上升过程f ”1 。k d d 包括以下步骤： 1 数据准备 k d d 的处理对象是大量的数据，这些数据一般存储在数据库系统中，是 长期积累的结果。但往往不适合直接在这些数据上面进行知识采掘，需要做数 据准备工作，一般包括数的选择( 选择相关的数据) 、净化( 消除嗓音、冗余 数据) 、推测( 推算缺失数据) 、转换( 离散值数据与连续值数据之间的相互转 换数据值的分组分类，数据项之间的计算组合等) 、数据缩减( 减少数据量) 。 如果k d d 的对象是数据仓库，那么这些工作往往在生成数据仓库时已经准备 妥当。数据准备是k d d 的第一个步骤，也是比较重要的一个步骤。数据准备 是否做好将影响到数据采掘的效率和准确度以及最终模式的有效性。 2 数据采掘 数据采掘是确定数据采掘的任务或目的( 如数据总结、分类、聚类、关联 规则采掘等) 和所采用的数据采掘算法并从数据中采掘出有关信息和知识。数 据采掘是k d d 最关键的步骤，也是技术难点所在。研究k d d 的人员中大部 分都在研究数据采掘技术，采用较多的技术有决策树、分类、聚类、粗糙集、 关联规则、神经网络、遗传算法等。数据采掘根据k d d 的目标，选取相应算 法的参数，分析数据，得到可能形成知识的模式模型l i 。 3 评估、解释模式模型 解释评估是对数据采掘所发现的模式进行修剪，去除冗余的、用户不感兴 趣的模式，并将最终的采掘结果转换成用户容易理解的形式或用各种可视化方 法加以显示( 如各种图表方式、图文方式、图形方式、自然语言方式等) 5 6 1 。 上面得到的模式模型，有可能是没有实际意义或没有实用价值的，也有可能是 其不能准确反映数据的真实意义，甚至在某些情况下是与事实相反的，因此需 要评估，确定哪些是有效的、有用的模式。评估可以根据用户多年的经验，有 些模式也可以直接用数据来检验其准确性。这个步骤还包括把模式以易于理解 的方式呈现给用户。 4 巩固知识 用户理解的、并被认为是符合实际和有价值的模式模型形成了知识。同时 还要注意对知识做一致性检查，解决与以前得到的知识互相冲突、矛盾的地方， 使知识得到巩固。 5 运用知识 发现知识是为了运用，如何使知识能被运用也是k d d 的步骤之一。运用 知识有两种方法：一种是只需看知识本身所描述的关系或结果，就可以对决策 提供支持；另一种是要求新的数据运用知识，由此可能产生新的问题，而需要 对知识做进一步的优化。k d d 过程可能需要多次的循环反复。每一个步骤一 j l 与预期目标不符，都要回到前面的步骤，重新调整，重新执行。 数据采掘是k d d 最核心的部分，是采用机器学习、统计等方法进行知识 学习的阶段。数据采掘算法的好坏将直接影响到所发现知识的好坏。目前大多 数的研究都集中在数据采掘算法和应用上。 1 3 数据采掘技术 数据采掘的研究融合了来自不同学科领域的技术和成果，使得目前的数据 采掘技术和系统表现出多种多样的形式。对数据采掘技术进行明确的分类，可 l 帮助潜在的用户区分不同的系统，从而选择适合自己需求的种类。 1 3 1 数据采掘技术分类 数据采掘中的关键技术是进行模式识别和关系识别的算法。许多算法来源 二j 二人： 智能和机器学习等研究领域。此项技术可分成四种常见的任务： 1 关联发现( a s s o c i a t i o nd i s c o v e r y ) 关联分析算法在数据库的记录或对象间抽取关联性。它展示了数据间未知 的依赖关系，根据这种关联性就可从某一数据对象的信息来推断另一数据对象 的信息。关联性是一种统计意义上的关系，并以置信度因子衡量关联的程度。 通常须设定最小置信度作为阀值。对于数据类型皆为布尔属性其关联分析算法 见 5 3 1 。在一般情况下，对于数量属性的数据可通过区间划分的方法将其转化 为布尔属性【8 j 。 2 聚类分析( c l u s t e r i n ga n a l y s i s ) 聚类分析问题可描述为：给定n 维空间r 中的m 个向量，把每个向量归属 到c 个聚类中的某一个，使得每个向量与其聚类中心的距离最小1 9 】。聚类分析 问题的实质是一个全局最优问题。k 均值算法是应用较广的算法，但它不一定 能得到全局最优。遗传算法具有计算简单、全局优化效果好的特点，以及它在 纰合优化问题方面所具有的优势。其它一些优化效果较好的算法大多需要大量 的时间和空间开销。 3 分类与回归( c l a s s i f i c a t i o n a n d r e g r e s s i o n ) 目前有四种技术用于分类与回归： 1 ) 决策树。 它是一种将一个训练文件( t r a i n i n gf i i e ) 划分成一组规则的技术。它由节点 分枝组成，起始节点称为根节点。训练文件被分成两个或更多的子集，这取决 于试验的结果。最终结果是一组包括所有可能的规则【5 4 】。由于它是以树状结构 的图形来表示模型的。因此容易理解，它已成为常用的工具。算法通常有 c h i s q u a r e d a u t o m a t i ci n t e r a c t i o n d e t e c l i o n ( c h a i d ) ，c l a s s i f i c a t i o n a n d r e g r e s s i o n t r e e sf c a r t ) ，i d 3 ，c 45 ，a c 2 ，c n 2 等。这些算法都适合于分类 问题，其中一些算法采掘相当快速，适用于回归问题。但当决策树在信息缺乏 完整的情况下使用时，这就意味着在训练文件中未把大量主要潜在的规则考虑 在内，因而这种方法可能漏掉未发现的有价值的规则。 2 、简单贝叶斯( s i m p l eb a y e s ) 。 它是一种对无条件数据限制其输入的技术，仅适用于分类问题( 之所以称 为“简单”是由于这种算法假定变量是独立的) 。该技术是基于这样一个简单 的概念：把在训练数据中观测到的频率作为条件概率。 3 1k - n n ( k n e a r e s tn e i g h b o r ) 。 与其它技术不同，它没有明确的训练阶段。因为训练数据实际上是模型。 新事例的预测是由寻找一组最相似的事例作出的( “k ”是这组内项的个数) 。 并使用它们的主要结果作为预测值。 4 ) 神经网络( n e u r a ln e t w o r k s ) 。 神经网络通过学习在分析数据中的模式来构造模型。它由“神经元”的互 联，或按层组织的节点构成。通常，神经模型由三个层次组成：输入、中间层和 输出。每一神经元求得输入值，再计算总输入值，由过滤机制( 例如阀值) l l 较 总输入，然后确定它自己的输出值。可通过连接一组神经元来模型化复杂行为。 当修改连接层“连接度”或参数时，神经网络就进行了学习或“训练”。 4 偏差检验( d e v i a t i o nd e t e c t i o n ) 偏差检验技术用于抽取数据中的偏差和异常。那些令人关注的偏差包括： 不适合于标准类的异常；与父类或兄弟类有很大差别：相邻两时间段内信息的 变动( o n 某一地区两个季度销售收入的变动) ；处于模式边缘的冗余。偏差分析 有助于滤掉知识发现引擎所抽取的无关信息，以及那些不适合的数据。 132 数据采掘技术应用 以上描述的不同数据采掘算法和技术的分类，可以按分析员如何用它们解 决现实世界的数据采掘问题来进行。数据采掘算法和技术可概括地分为下面几 种使用类型“： 1 关联规则的发现 关联规则的一个典型例子是市场菜篮子分析，此分析弓一组产品相关联。 通过采掘事物数据可派生关联规则，利用此规则可以了解客户的行为。例如， 观察客户对办公用品的订货，在那些订购笔的客户中，有7 0 订购也订购了写 字台，“笔”是规则的前提，“写字台”是舰则的结果，关联规则中可有任意多 个前提和结果。“7 0 ”表示了置信度因子，采掘系统试图在给定的数据集c ， 找到尽可能多的关联规则或模式【8 4 1 。 分析员通常感兴趣的是一组关联，如：查找所有以“写字台”作为结果的 关联，以便制定战略来增加“写、字台”的销售，因为“写字台”是一种高利 润的商品。如果“铅笔”是一种微利商品，那么要检查所有以“铅笔”作为前 提的关联，以便确定不再销售铅笔时带来的影响。如果“写字台”具有很高的 刊润，那么需要查找所有以“铅笔”作为前提，并以“写字台”作为结果的关 联，以便了解为增加“写字台”订货所需的“铅笔”。事务分析不一定要同时 处理所有订货，只要在给定时间框架内包含所有订货就可以了。 序列模式可看成一种特定的关联规则。在许多情况下，客户事物要经历很 长时间，这也是顾客全局关系的一部分。分析员对订货之前发生的事情感兴趣， 例如，邮寄宣传材料、订购本身、客户服务清求、定单传送( 及时或非及时) ， 售后服务、后继订货以及其他与顾客交互。数据库可以包含所有这些临时数据， 月可跨跃多个时间段。序列模式功能可以分析数据库中一组此类型的数据，并 发现某一段时间内顾客购买定单中常见的模式。例如，顾客现在订购了一台打 印机，在以后还可能定购“打印纸”。定货应具有种基于打印机生命周期的 模式：初始购买、售后服务和维修服务。可能在初始购买时有大量订货，在服务 请求时是限量的，而在每一服务请求完后又有大量定货。在售后管理和收入计 6 划中，关于这些模式的知识是有价值的。此外，分析员可发动促销活动，以便 将这种模式改变或更符合效益要求的模式，并增加客户的满意度。此关联模式 用于查找一组客户，这些客户符合特定频率的购买模式p j 。 2 聚类分析 当要分析的数据缺乏描述信息，或者是无法组织成任何分类模式时，利用 聚类算法可以自动地找到类。聚类功能可用于一组顾客的现金流分析，这些顾 客在一月的特定时间内付帐f 例如，当收到社会保险支票时，或者月工资存入 帐户时) 。聚类还可用于市场细分，寻找相关的组。 3 分类使用 分类问题涉及规则的查找，此规则将数据记录划分成不连贯的组，划分基 于数据记录的属性。例子：信息认可和商店定位。在商店定位中，首先按成功的 商店、一般商店和失败商店进行排列，然后得出这三类商店各自具有特殊性， 然后选择包含位置属性的地理数据库，并对每一项预期的商店位置属性进行分 析，以便确定预期的商店定位属于哪一类。只有那些符合成功一类要求的商店 才选作所希望的商店定位。 4 神经网络的使用 神经网络已应用于许多商业领域，例如：市场营销领域需要检查客户的彳于为 以便构造微观市场细分和邮寄表，并且还要寻找理想的客户群。财经分析领域 包括现金流分析和欺诈检查。商业运作领域包括传送计划和后勤分析。 5 决策树的使用 用树型结构来表示决策集合，这些决策集合通过对数据集的分类产生规 则。典型的决策树方法有分类树和回归树，目前比较流行的决策树有c a r t 树、 c h a r t 树、i d 树等1 3 j 。 1 4 关联规则采掘技术 关联规则采掘作为一种重要的数据采掘技术，目前已经成为了数据采掘的 重要研究内容。对关联规则采掘问题的研究是由a g r a w a l 等人在1 9 9 3 年提出 来，并给出了关联规则采掘的a i s 算法，最初的动机是希望从存储商品销售数 7 据的事务数据库中采掘出反应有关顾客购买行为的知识，以指导商业决策“o 。 事务数据库中的每条事务记录了顾客在商场或超市中一次购物的交易内容( 商 品的种类、数量等信息) 。关联规则采掘考察每位顾客购物的交易内容，从而 发现类似于“一些商品j 另一些商品”形式的规则，称之为关联规则。 关联规则采掘问题的提出引起了众多研究人员的重视，并对该问题展开了 深入的研究。许多研究者( 包括a g r a w a 等人) 对最初的关联规则采掘问题进 j 门深入的研究，包括对原有的算法进行优化，如引入随机采样、并行的思想 等【7 引，以提高算法采掘规则的效率，对关联规则的应用进行推广；同时关联规 则采掘问题被进一步扩展和改进，被应用到更广泛的领域。目前，关联规则采 掘技术已经被应用到除商业领域外的其它领域，如电讯业、金融业等，均取得 了良好的效果。 根据关联规则采掘方式的不同，可以将关联规则技术分为两大类：关联舰 l 则的串行采掘技术和关联规则的并行采掘技术。传统的关联规则的采掘采用串 仃算法，随着分布式数据库的发展，串行算法逐渐被更高效的并行算法所代替。 41 关联规则的串行采掘技术 数据采掘的一个主要问题是关联规则的采掘，而采掘关联规则问题的核心 扫于发现最大项目集。现今已有多种发现最大项目集的串行算法，通常的串行 算法都是首先生成候选项目集，然后计算它们的支持度从而生成最大项目集7 j 。 串行算法包括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 i h y b r i d ； p a r k 等人提出的d h p ；s a v a d e r e 等人提出的p a r t i t i o n 等等。其中最有效和最有 影响的算法是：a p r i o r i ，d h p 和p a r t i t i o n 。这些算法在对事务数据库进行第k ( k 1 ) 次扫描时，没有充分利用第k 1 次对事务数据库扫摇的结果，使得候选频繁项 i j 集c k 中的元素个数在整个第k 次扫描中始终保持为一个常数，不会随着对 事务数据库的扫描而减少，这样大量的候选项目集以及重复扫描数据库，严重 影响了算法效率【2 0 】【7 7 】。 数据采掘是直接面向海量数据库系统的，这类数据库通常有上百个属性和 数百万个记录，并且数据表之间包含复杂的关系。这就必然导致数据采掘过程 中搜索维数和搜索空间的激增，数据库的巨大规模、异地分布及数据采掘方法 的计算复杂性要求进行并行数据采掘【2 0 j 【2 1 i 。 14 2 关联规则的并行采掘技术 传统的关联规则串行采掘算法，虽然进行了许多的改进和扩充工作，仍然 无法改变对数据库多遍扫描的事实。而数据采掘是应用于大数据库中的技术， 要处理的数据量极大，多遍扫描会增加i o 时间，降低采掘效率”“。这样就 需要寻找用于数据采掘的更高效可行的技术。并行算法就在这种情况下应运而 生【7 6 j 。 在数据采掘领域，开发并行算法有两种途径：其一是对已有的串行算法进 行改进，采掘其中的并行性质并加以利用，使得串行程序并行化：其二是对问 题的本质重新审视，设计全新的并行算法。第一种途径相对容易一些，但是并 行粒度较小，通信量较大。第二种途径需要全新设计，但如果成功，就会得到 粗粒度并行算法，适合于在分布式并行机上应用”。1 。 目前已经提出的并行采掘关联规则的算法有a g r a w a l 等人提出的 c d ( c o u n t d is t r i b u t i o n ) 、c a d ( c a n d i d a t ed is t r i b u t i o n ) 、d d ( d a t a d is t r i b u t i o n ) ，p a r k 等人提出的p d m 。算法d m a 虽然是基于分布式数据库的 采掘算法”，但也可适用于并行采掘算法c d 具有速度较快、容易实现、要求 各计算机间同步次数较少等优点，但它有通信量大和候选项目集大等缺点。算 法c a d ，d d 及p d m 的执行效果都不如c d 算法1 。算法d m a 虽克服了算法c d 的 一些弱点，但它要求各计算机闯同步次数较多。 1 5 p s p a d e 并行采掘算法 由于网络计算和网络通信技术的进步，分稚式计算平台已经越来越盛行。 一种新的具有更高性能价格比的体系逐渐成为应用主流一分布式集群计算体 系。当用户需要完成任何任务时，分布式集群计算提供了尽可能多的计算机处 理能力和数据的透明访问能力，同时实现高性能与高可靠性的目标“。 硕士晕位论文 、i 沁r sj j i 巧f 、 本文介绍的p s p a d e 算法是一种广泛应用在分布式共享存储系统平台上，在 大型数据库中发现频繁序列的有效并行算法。p s p a d e 将原始搜索空间分成更小 的基j 二后缀的类，每个类可以在不同步的处理器上被独立处理”。 但是，p s p a d e 算法必须使用动态的类内和类间负载平衡以确保每个处理器 获得相同的工作量，由于每个类和它的中间i d 列表存于主存，导致了大量的 内存牙销。当处理更大的数据集时，容易产生内存溢出。本文在该算法的基础 l 对该问题进行分析，采用内存扩展方案对算法进行控制，使得p s p a d e 算 法在处理大数据集时也能顺利执行，同时给出了它的优缺点和适用范围。 i 6 本文的主要工作 本文的主要工作包括以下几个方面： 对各种传统的串行算法进行对比分析，总结它们的优缺点，说明进行并行 采掘关联规则的必要性； 对并行采掘关联规则进行阐述，并对几类典型的并行算法进行了研究，对 它们的性能进行比较； 在对以往并行算法研究的基础上，介绍了一种广泛应用在大型数据库中快 速采掘序列模型的p s p a d e 并行算法，解决了存在于大多并行算法中大量 同步歼销的问题，但仍存在很大的内存开销。针对这一问题，本文通过对 该算法的具体分析，提出了内存扩展方案对算法进行控制，解决了算法处 理大数据集时出现内存溢出的问题。 1 7 论文的组织 本文的安排分为六章，第一章介绍了数据采掘的基本知识，讨论了关联规 则采掘技术的研究现状以及本文的目的和意义。 第二章具体讨论了关联规则采掘技术的基本概念、基本算法以及关联规则 采掘技术的发展趋势。 第三章对关联规则的并行采掘的技术进行了介绍，讨论了并行采掘技术的 1 0 基本概念、基本内容，并对几种典型的算法进行了比较。 第四章详细介绍了p s p a d e 算法，一种广泛应用于大型数据库上快速采掘频 繁序列的并行算法。 第五章在p s p a d e 算法研究的基础上，提出了内存扩展方案，解决了该算法 在处理大数据集时遇到的内存溢出问题。 第六章是本文的总结和展望。 第二章关联规则采掘问题 数据采掘是根据决策需要，确定数据采掘的任务和目的，并采用具体的数 据采掘算法从数据集中采掘出有用知识的过程，是k d d 的核心环节。目前，数 据采掘的研究主要集中在分类、聚类、依赖模式采掘、路径发现、异常和趋势 发现等方面。其中关联规则采掘在商业等领域的成功应用，使它成为了数据采 掘中最成熟、最重要、最活跃的研究内容“。 21 问题的产生 条码技术的发展使得零售机构能够收集和存储大量的销售记录，这些销售 、l 己录称为篮子数据( b a s k e td a t a ) 。记录顾客在一次购物中购买的商品信息的 篮子数据称为事务( t r a n s a c t i o n ) 。在现代化的超级市场中，售货员可以用条 码扫描器方便而准确地记录下所有的事务。许多组织已经收集并存储了大量的 篮子数据，并表明这些数据是他们从事营销活动和商业决策的重要基础和依 据。但是，现有的数据库管理系统并没有提供足够的工具来从这些数据中发现 有价值的信息和知识。 在这样的应用背景下，关联规则采掘问题1 9 9 3 年被a g r a w a l 等人提了出 来，其最初的研究目标是从事务数据库中发现有关顾客购买行为方面的知识， 并用关联规则的形式来表达所发现的知识。 2 2 问题的定义 为了准确地描述关联规则采掘问题，便于问题的讨论，需要给出关联规则 采掘问题的正式定义。下面用事务数据库来定义关联规则采掘问题 定义2 1 关联规则采掘的数据集记为d ( d 为事务数据库) ， d 一 t 。，t ：，t ”，t 。 ，tk = i ，i ：，i 一，i 。 ( k = l ，2 ，n ) 为一条事务； t - 中的元素i 。( 3 = 1 ，2 ，p ) 称为项目( i t e m ) 。 在事务数据库中项目就是商品的名称，事务数据库中的事务在数据库中就 是一条记录，包括一些其它信息，如日期、客户编号等，在关联规则采掘中这 些信息一般就被忽略掉，使得一条事务中仅包含项目的标识符，即顾客在该事 务中购买了哪些商品。若顾客购买了某商品，则此商品对应的项目标识符就包 含在该事务中。由此可知，事务就是项目的集合。 为了找出关联规则，必须处理各种不同的项目组合，每一个项目组合都称 为一个项目集。由于空集在这里没有意义，因此若项目总数为ii i ，所有需要考 察的项目集数量为寥”一l 。 定义2 2 设i = i ，i2 ，一，i 是d 中全体项目组成的集合，i 的任何子集 x 称为d 中的项目集( i t e r a s e t ) ，i ) ( i = k 称集合x 为k 项目集。设t 。和x 分别为 d 中的事务和项目集，如果x a t 。，称事务t 。包含项目集x 。 事务和项目集虽然都是项目的集合，但两者有不同的含义。事务是数据库 d 的组成元素( 类似于关系数据库中的记录或元组) ，而项目仅仅是为采掘关联 规则而规定的项目组合。事务与项目集的包含关系表明对该事务来说，此项目 集中的各个项目是相互关联的。 定义2 3 数据集d 中包含项目集x 的事务数称为项目集x 的支持数，记 为d 。项目集x 的支持率，记作：s u p p o r t ( x ) ， s u p p 。( 。) 2 酱圳o 2 1 其刊d i 是数据集d 的事务数。若s u p p o r t ( x ) 不小于用户指定的最小支持率( 记 作：m i n s u p p o r t ) ，则称x 为频繁项目集( 或大项目集) ，否则称x 为非频繁项 目集( 或小项目集) 。 定理2 1 设x 、y 是数据集d 中的项目集 ( i )若x y ，则 s u p p o r t ( x ) _ s u p p o r t ( y ) ( 2 2 ) ( i i ) 若x c y ，如果x 是非频繁项目集，则y 也是非频繁项目集 ( i i i ) 若x y ，如果y 是频繁项目集，则x 也是频繁项目集 证明】 ( i ) 对任意的事务t 。因为x c y 就有y c t 等x c t 。因此，g x o ”得到 s u p p o r t ( 耻茜_ s u p 刚耻裔 得证。 ( i i ) 由x 是非频繁项目有： s u p p o r t t 耻强“弧u p p 州 因为x 互y ，由( 2 2 ) 式知 s u p p o r t ( x ) _ s u p p o f t ( y ) 由此可知 s u p p o r t ( y ) _ s u p p o r t ( y ) 由可知 s u p p o r t ( x ) h m i n s u p p o r t 即x 是频繁项目集 得证。 定义2 4 若x 、y 为项目集，且x n y = o ，蕴涵式x y 称为关联规则，x 、 y 分别称为关联规则x j y 的前提和结论。项目集( x u y ) 的支持率称为关联规 则x j y 的支持率，记作：s u p p o r t ( x 等y ) ， s u p p o r t ( x j y ) = s u p p o r t ( x u y ) ( 2 3 ) 关联规则x y 的置信度记作：c o n f i d e n c e ( x j y ) ， c o n l i d e n c e ( x j y ) ：s u _ _ p p o a ( x u y ) x 1 0 0 ( 2 4 ) s u pp o r t ( x ) 硕士学位论文 l 、s ie r s l i i e s i s 通常用户根据采掘需要指定的最小置信度记为m i n c o n f i d e n c e 。 支持率和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则 在整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。一般来说， 只有支持率和置信度均较高的关联规则才可能是用户感兴趣的、有用的关联规 则。 定义2 5 如果s u p p o r t ( x j y ) - m i n s u p p o 九且c o n f i d e n c e ( x j y ) m i n c o n f i d e n c e ，称关联规则x ；y 为强规则，否则称关联规则x j y 为弱规则。 2 3 关联规则采掘问题的分解 关联规则采掘的任务就是要采掘出d 中所有的强规则。强规则x j y 对应 的项目集( x u y ) 必定是频繁项目集( 由定义5 和( 1 3 ) 式可知) ，由定理l ( i i ) 和( 1 4 ) 式可知：频繁项目集( x u y ) 导出的关联规则x j y 的置信度可由频 繁项目集x 和( x u y ) 的支持率计算。因此，可以把关联规则采掘划分为两个 子问题： ( 1 ) 根据最小支持率找出数据集d 中的所有频繁项目集； ( 2 ) 根据频繁项目集和最小置信度产生关联规则。 第一个子问题的任务是迅速高效地找出d 中全部频繁项目集，是关联规则 采掘的中心问题，是衡量关联规则采掘算法的标准，目前大多数有关关联规则 采掘问题的研究都是针对第一个子问题而展开的：第二个子问题可直接( 1 1 ) 式和( 1 4 ) 式求解。 2 31 根据频繁项目集产生强规则 由( 2 。4 ) 式知，强规则的产生过程如下： 对于每个频繁项目集f ，产生f 的所有非空真子集； 对于 f的每个非空子集m，如果 s u p p o _ r t ( f ) 1 0 0 历，门c o n f y d e 仃c p ，则输出强规则r t m j ( f m ) s u pp o r t i ，押) 推论对项目集f 和其子集m 和一，若m 2m ，则关联舰则m j f m 的置信 度不可能大于关联规则m j f m 的置信度。 证明 由f m 、f _ d m 且m 三m ，根据定理2 1 ( i ) 知 s u p p o r t ( 1 1 1 ) s u p p o r t ( m ) s u p p o r t ( f - m ) 2 s u p p o rt ( f - m ) 而 s u p p o r t ( m ，j f 一吖) ：s u pp o r t ( _ f - _ m ) s u p p o r t ( m ) s l 【p p 。r t ( m = ，f m ) ：s u pp o r t ( f - m ) s u pp o r t ( m ) 因此 s u p p o r t ( m f i l l ) s u p p o r t ( m j f m ) 得证 在根据频繁项目集产生强规则时，利用推论2 2 可以减少计算量，进一步提高 强规则的产生效率。 2 3 2 关联规则采掘的基本模型 图2 1 关联规则采掘的基本模型 综上所述，关联规则采掘的基本模型可用图2 1 表示，其中d 为数据集， l g o r i t h m l 为频繁项目集的搜索算法，a l g o r i t h m 一2 为关联规则的产生算法， r 为采掘出的关联规则集合。 用户通过指定m i n s u p p o r t 、m i n c o n f i d e n c e 分别与算法a i g o r i t h m l 和 6 a 1g o r i t h m 一2 交互，并通过与r 的交互对采掘结果进行解释和评价。 24 关联规则采掘算法 传统的关联规则采掘算法都是串行的，通常都是首先，生成候选项目集然 后计算它们的支持度从而生成最大项目集。根据扫描数据库方式的不同，将串 行算法分为l e v e l 一w i s e 算法、n o n l e v e 卜w is e 算法以及不产生候选项目集的 算法几类。 2 4 1l e v l - w is e 算法 这是一类从频繁( k 1 ) 一项目集中产生候选k 一项目集的算法，称之为 l o v e l w i s e 算法。和r i o r i 算法是一种最早的le v e 卜w is e 算法，按项目集从 小到大的顺序寻找频繁项目集，也是产生频繁项目集最早最流行的算法之一。 下面首先对4 卢_ ，i o r i 算法进行主要的介绍，不仅因为它历史的重要性，而且本 文以后所讨论的主要并行算法都是基于a p r i o r i 算法的。 大部分已有的串行算法用于发现频繁项目集。这些算法有两个共同的特 征。第一，它们都采用了项目集支持率的反单调性的原则。这个性质说明当项 目集的长度增加时，它的支持率不是降低就是保持不变；换句话说，当且仅当 k 项目集的所有k - 1 子项目集都是频繁的，它才是频繁项目集。a p r i o r i 算法 是最早采这种特性的算法之一。a p r i o r i 用这种方法系统地控制了可能的项目 集在数量上呈指数增长，减少了搜索空间。第二种共性就是他们都需要搜索一 个共同的项目集的格。简要来说，已知项目集j r ，格足所有，子集的系统列表， 开始，在底部置为空，所有的单项目集在第一层，所有的2 项目集在第二层， 以此类推。带有k 个项目的k 项目集位于格的第k 层，与出现在第k 一1 层上的 所有k 一1 子集相连。算法用这种方式遍历格，采用支持率的反单调特性，构成 了决