（计算机应用技术专业论文）粒计算在挖掘数据库中关联规则的应用研究.pdf

粒计算在挖掘数据库中关联规则的应用研究 摘要 近年来，随着信息技术的发展，人们所面对和接触的数据量也逐渐增大。为 了不被海量的数据所淹没，从中得到我们所需的知识，数据挖掘就应运而生了。 它是一个新兴的边缘学科，汇集了人工智能、模式识别、数据库、机器学习以及 管理信息系统等多学科的成果，其应用领域非常广泛，并且具有良好的应用前景。 本文对数据挖掘中的关联规则进行了详细的阐述，同时对目前在软计算领域 的研究热点粒计算进行分析研究。粒计算作为一种新的信息和知识处理的方 法近年来已经被许多研究者所重视，并且在许多领域中得到应用。本文将粒计算 方法与技术应用于数据挖掘中关联规则的挖掘领域，着重从另一个角度对关联规 则的挖掘进行了更广泛的研究。本文在对经典的关联规则挖掘算法进行了详细的 分析和研究并通过实例对它的特点以及局限性进行了归纳的基础上，提出了基于 粒计算的关联规则挖掘模型，为基于粒计算的关联规则的提取算法的提出和构造 做了理论上的准备。通过采用二进制串表示所定义的信息粒，提出了基于粒计算 的关联规则挖掘算法。然后本文分别研究了在采用二维表的形式和链式结构来存 储信息粒下，利用二进制粒位运算提取频繁项目集来发现关联规则。从而在经典 的a p f i o f i 算法基础上实现了基于粒的关联规则的提取算法。 最后，文中通过一个实验，将经典a p f i o r i 算法和基于粒计算的关联规则的 提取算法进行了对比，并对实验结果进行了分析。实验结果表明基于粒计算的关 联规则挖掘方法是可行的也是有效的。 关键词：数据挖掘，关联规则，粒计算，二进制粒 粒计算在挖掘数据库中关联规则的应用研究 a b s t r a c t i nt h er e c e n ty e a r s ，w i t ht h ed 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 , t h ed a t aw e f a c eb e c o m eb i g g e ra n db i g g e r i no r d e rn o tt ob ep u z z l e db yl a r g eq u a n t i t yo fd a t a a n dg e tt h ek n o w l e d g ew en e e d ，t h e n ，d a t am i n i n gw a sb o m i t sa n e w l y - e s t a b l i s h e d f r o n t i e rs u b j e c t ，c o n g r e g a t i n gs o m er e s e a r c hr e s u l t so fa r t i f i c i a li n t e l l i g e n c e 、p a r e m r e c o g n i t i o n 、d a t a b a s e 、m a c h i n el e a r n i n ga n dm a n a g e m e n ti n f o r m a t i o ns y s t e m ，e t c i ti sb e i n gu s e de x t e n s i v e l ya n di t sa p p l i c a t i o nf u t u r ei sb r i g h t t h i st h e s i si n t r o d u c e sa s s o c i a t i o nr u l e si nd a t am i n i n gi nd e t a i l sa n da n a l y s et h e h o ts p o ti n s o f tc o m p u t i n g - - g r a n u l a rc o m p u t i n g g r a n u l a rc o m p u t i n ga san e w i n f o r m a t i o na n dam e t h o do fd e a l i n go fk n o w l e d g ew a sv a l u e db ym a n yr e s e a r c h e r a n da p p l i e di nm a n yf i e l d s t h i st h e s i sa p p l i e sg r a n u l a rc o m p u t i n gt e c h n o l o g yt ot h e a r e ao fm i n i n ga s s o c i a t i o nr u l e si nd a t am i n i n g ，s t u d i e st h em i n i n go fa s s o c i a t i o nr u l e s e x t e n s i v e l yf r o mo t h e rw a y s i nt h et h e s i s ，b a s e do nt h ea n a l y z i n ga n ds t u d y i n gc l a s s i c m i n i n ga l g o r i t h m so fa s s o c i a t i o nr u l e si nd e t a i l sa n ds u m m a r i z i n gi t sc h a r a c t e r i s t i c a n dl i m i tt h r o u g ha ni n s t a n c e ，w ei n t r o d u c eam o d e lo fm i n i n ga s s o c i a t i o nr u l e sb a s e d o ng r a n u l a rc o m p u t i n g a l lo ft h ea b o v er a t i o n a l l yp r e p a r ef o rt h ep r o p o s i t i o na n d c o n s t r u c t i o no fm i n i n ga s s o c i a t i o nr u l e sa l g o r i t h mb a s e do nt h eg r a n u l a rc o m p u t i n g t h r o u g hd e f i n i n gi n f o r m a t i o ng r a n u l ew i t hb i n a r ys t r i n g ，w ei n t r o d u c ea na l g o r i t h m o fm i n i n ga s s o c i a t i o nr u l e sb a s e do ng r a n u l a rc o m p u t i n g t h e nw er e s e a r c h e dt h e m e t h o d so fm i n i n gf r e q u e n ti t e m st og e ta s s o c i a t i o nr u l e su s i n gb i n a r yg r a n u l e sw i t h t w o - d i m e n s i o nt a b l ea n dl i n ks t r u c t u r e b a s e do nt h ec l a s s i ca p r i o r ia l g o r i t h m ，w e i m p r o v ei ta n dr e a l i z et h ea l g o r i t h mo fm i n i n ga s s o c i a t i o nr u l e sb a s e do nt h eg r a n u l a r c o m p u t i n g i nt h ee n d ，t h et h e s i sc o m p a r et h ec l a s s i ca p r i o r ia l g o r i t h mw i t ht h ea l g o r i t h mo f m i n i n ga s s o c i a t i o nr u l e sb a s e do nt h eg r a n u l a rc o m p u t i n gt h r o u g ha ne x p e r i m e n ta n d a n a l y z et h er e s u l to fi t t h er e s u l tp r o v e st h ea l g o r i t h mo fm i n i n ga s s o c i a t i o nr u l e s b a s e do nt h eg r a n u l a rc o m p u t i n gi sf e a s i b l ea n de f f e c t i v e k e y w o r d s ：d a t am i n i n g ，a s s o c i a t i o nr u l e s ，g r a n u l a rc o m p u t i n g ，b i n a r yg r a n u l e 独创性声明 y9 2 8 7 8 0 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得直基太堂或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：涨和讳 签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解直昌盘堂有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权壶昌太堂可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：专承丽荡 签字日期：年月 日 学位论文作者毕业后去向： 工作单位 通讯地址 导师签名：聊仳砰 签字日期：年g 月肛日 电话 邮编 粒计算在挖掘数据库中关联规则的应用研究 第一章绪论 1 1 论文研究的背景及意义 近半个世纪以来，计算机和信息技术的高速发展给人类社会带来了巨大的变 化与影响，人们利用信息技术生产和搜集数据的能力也在不断提高。当前有千千 万万个数据库被用于商业管理、政府办公、科学研究和工程开发等，这一势头仍 将持续发展下去。而且近年来，随着i n t e m e t 的迅猛发展，网络经济等概念的出 现，一个新的挑战被提了出来：在这被称之为信息爆炸的时代，信息过量几乎成 为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从中及时发现有 用的知识，提高信息利用率呢? 要想使数据真正为我所用，只有充分利用它为我 们的决策和发展服务才行，否则大量的数据反而会成为我们的包袱，甚至垃圾。 因此，面对“丰富的数据，贫乏的知识”的现象，数据挖掘技术应运而生，并得 以蓬勃发展，越来越显示出其强大的生命力。 尽管现在数据挖掘技术已经取得了一些丰硕的成果，但并不意味着它的技术 已完全成熟。由于数据库系统的复杂性和多样性，尤其是随着应用的发展和信息 技术的进步，新的数据库系统还在不断涌现，这就使任何单一的工具、模型或方 法都难以彻底地解决该问题。该技术的成功应用不但要求人们针对不同应用的特 点来研究和实现相应的功能，而且还要求在这些系统中尽可能地应用一些新的技 术和工具。粗集理论就是这样一种迅速成熟起来的新型数学工具。粒计算是r o u g h 集理论的扩充，它能将复杂问题划分为一系列更容易管理和更小的子问题，从而 降低全局计算代价并且能更好地领悟问题，同时提供一种对其本质更好的洞察 力，避免陷入不必要的细节中去，对于一些包含不完备、不确定性和模糊信息的 复杂问题能比较好的得到解决【1 , 2 , 3 】。因此，根据粒计算的特点，本文对其在挖掘 数据库中关联规则的应用进行较深入的研究。 关联规则最初起源于对超级市场的“购物篮”问题的研究【4 】，侧重于确定数 据中不同属性之间的联系，找出满足给定支持度和可信度阈值的多个属性之间依 赖关系，发现交易数据库中不同商品( 项) 之间的联系，分析顾客的购买习惯， 粒计算在挖掘数据库中关联规则的应用研究 发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进 行分类及制定相应的营销策略。我们还可将这种分析数据的方法应用于其他的不 同领域，例如银行、保险，学校等。这样对我们的各企事业单位做出最优的决策 或采取较好的措施提供了很好的参考，具有非常大的实际指导意义。 基于粒计算的关联规则的提取是从另一个角度来解决海量数据中提取有用 信息的问题。其基本思想是将待分析的数据库根据某种关系构建有关信息粒，即 进行信息粒化。信息被粒化后用一个二进制数字串形式把它表示出来，然后通过 二进制的逻辑与运算得到频集，最终得到我们需要的规则。这种基于粒计算进行 关联规则挖掘的方法在语义表示上能形象地反映所研究事务的特征，给出了解决 问题的另一种方式，并且在速度上也会得到一定的改善，这对于在海量数据中进 行规则的提取是具有实际应用价值的。 1 2 国内外研究现状 2 0 世纪8 0 年代初r s 理论由数学家z p a w l a k 首次提出后，多年来无论在 理论上还是在相关领域的应用上都取得了令人瞩目的研究成果。r s 理论作为一 种处理含糊和不精确问题的新型数学工具【5 j ，在人工智能、认知科学以及软计算领 域中近年来得到大量应用。尤其是在机器学习与决策分析等方面。r o u g h m e r e o l o g y 是r o u g h 集理论的扩充，它是一种包含关系提供了智能a g e n t 在分布 式环境下对个体进行综合和分析的一种方法学【6 】。近来，它已经被用作研究信息 粒计算的基础。 l a z a d e h 经过长期研究提出了信息粒和信息粒化的概念【7 1 。他认为粒计算 是一个含义广泛的术语，覆盖了所有有关粒的理论、方法学、技术和工具的研究， 并认为粒计算是模糊信息粒化、r o u g h 集理论和区间计算的超集，是粒数学的子 集。他把信息粒描述为一个命题：x 的值是以程度入隶属于模糊子集gc u ，其 中x 是u 上的变量，x 的值是u 上的一个实体，写成：g = xi sgi s 入，形式上被 记成：g = u u ：x 的值( v ( x ) = u ，v 是u 上的赋值符号) 是以程度入隶属于模糊 子集gc u ) 。很显然o 入1 ，入是模糊隶属函数ug 。 t y l i n 采用了领域的观点描述信息粒【8 j ：设s = ( u ，a ，v ，f ) 是信息系统， b ：v u 为二元关系，其中u 是所讨论对象的全集，a 是属性集，v 是属性值集， 粒计算在挖掘数据库中关联规则的应用研究 f 是信息函数。用b 定义信息粒形式为：g p = u u ：ubp , p v ) 。显然g p 是清晰 还是模糊的完全取决于二元关系b 的特性。所以，对于两个二元关系b 和d ， 如果b e d ，则按b 将全域划分的粒比按d 将全域划分的粒更细。在这种情况下， 也可将不同大小的粒度分成不同粒度层，并在不同层上进行各自分别处理。 当前存在许多信息粒化的方法：集合论和区间分析、f u z z y 集、r o u g h 集、 v a g u e 集、集对分析及其相互关联、可拓集、灰度集、证据理论、神经网络、结 块、决策树、语义网络、a d 转换、约束规划、聚类分析等1 2 j 。粒计算的主要形 式框架有集合理论和区间分析、模糊集、粗糙集、概率论、商空间理论。虽然这 些模型大多是独立发展起来的，彼此之间并没有多少相互影响，但他们最终都统 一于粒计算这个框架下，这也说明了粒计算本身就是一种更为基础的问题求解方 法【9 1 。 目前，基于上述模型，学术界进行了一系列研究，粒计算被广泛应用于多个 领域，在国外，将它应用于数据挖掘、知识发现方面已有了一定的成果，但在国 内将它应用于数据库中的关联规则的提取还是比较少。 数据挖掘( d a t am i n i n g ) ，又称数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) ，在最近几年里已被数据库界所广泛研究，其中关联规则( a s s o c i a t i o n r u l e s ) 的挖掘是一个重要的问题【4 】。a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客 交易数据库中项集间的关联规则问题，他提出的a p r i o r i 算法是经典的频集算法， 但它有自身的局限性，主要体现在两个方面：第一，在产生频繁模式时需要产生 大量的候选项，这需要占用较多内存空间和c p u 的处理时间；第二，由候选项 产生频繁模式时，每一个频繁模式的产生都需要扫描事务数据库一遍，将消耗大 量的c p u 时间遍历数据库以及内存与外存间的大量数据交换，对于一个包含数 量很多和上百万级的事务记录的数据库的多次遍历，将会带来巨大的开销。 以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。为了提高算 法挖掘规则的效率，他们对经典的a p r i o r i 算法进行优化，引入随机采样、基于 散列技术、基于划分技术、事务压缩以及并行的思想等，进一步推广了关联规则 的应用，但这些方法还是有自己的瓶颈。最近也有独立于频集方法的工作，以避 免频集方法的一些缺陷，探索挖掘关联规则的新方法。 但就目前情况来看，虽然关联规则的挖掘算法已有了很大的改进，但在实际 粒计算在挖掘数据库中关联规则的应用研究 应用中还需要我们对它进行深一步的研究，因为现实生活中的数据量是非常的大 的，在处理海量数据时，速度仍然是一限制，因此在本文中，我将用粒的方法来 提取关联规则，希望在某些方面能有所突破进一步完善解决问题的途径。 1 3 论文的结构安排 本文的结构安排如下： 第一章：绪论 主要介绍论文研究的背景和意义以及论文的结构安排。 第二章：数据挖掘综述 主要介绍数据挖掘中的基本知识，对挖掘的过程和分类进行了介 绍，并对数据挖掘中的关联规则的挖掘进行了具体的说明，同时 详细介绍了几种经典的关联规则挖掘算法。 第三章：粒计算理论 主要介绍粒计算理论所涉及的基本概念及当前的一些研究现状， 并对r o u g h 集的基本知识进行了介绍，为更好地理解粒计算提 供了帮助。在本章还介绍了其他几种常用的粒计算框架和它的发 展方向及主要应用。 第四章：基于粒计算的关联规则提取算法 首先介绍了基于粒计算的关联规则挖掘的基本思想，然后对它的 数据模型及定义进行了介绍，提出了信息粒的两种存储方式以及 在该种存储方式下的算法的实现。用实例将经典算法与基于粒计 算的关联规则提取算法进行了对比分析，并提出了基于粒计算的 多维关联规则挖掘，最后对该算法的特点进行了分析。 第五章：基于粒计算关联规则提取算法实验对比及结果分析 该章将经典的挖掘算法a p r i o r i 算法与基于粒计算的关联规则链式 提取算法用实验进行了对比，并对结果进行了分析。 4 粒计算在挖掘数据库中关联规则的应用研究 第二章数据挖掘综述 2 1 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 称为数据库中知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ) ，是指从数据中识别有效的，新颖的，潜在有用的，以及最终可理解 的模式的非平凡过程【4 j 。 其中“数据是一组事实的集合( 如关系数据库中的记录) ；“模式”是以 某种语言来表示的一个表达式，它可以用来描述数据子集；“过程”在数据挖掘 中通常指多阶段的一个过程，包括数据准备，模式搜索，知识估价，以及反复的 修改求精。“非平凡过程”是指要有一定程度的智能性和自动性，而不是象求平 局值那样的简单计算。“新颖的”要求发现的模式因该是新的；“潜在有用的”是 指发现的知识将来有实际的效用，如用于决策支持系统可提高经济效益；“最终 可理解的 要求发现的模式能被用户理解。 2 2 数据挖掘的过程 数据挖掘又被视为数据库中知识发现过程的基本步骤。知识发现过程由以 下步骤组成 4 1 ： ( 1 ) 数据清理( 消除噪声或不一致数据) ( 2 ) 数据集成( 多种数据源可以组合在一起) ( 3 ) 数据选择( 从数据库中检索与分析人物相关的数据) ( 4 ) 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作) ( 5 ) 数据挖掘( 基本步骤，使用智能方法提取数据模式) ( 6 ) 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) ( 7 ) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 尽管大多数人都同意数据挖掘是知识发现过程的一个步骤。然而，在产业 界、媒体和数据库研究界，术语“数据挖掘”比术语“数据库中知识发现” 更流行。因此，数据挖掘有一个更为广泛的概念：数据挖掘是从存放在数 粒计算在挖掘数据库中关联规则的应用研究 据库、数据仓库或其他信息库中的大量数据中的挖掘有兴趣知识的过程。 基于这种观点，典型的数据挖掘系统具有如图2 1 所示的主要组成部分。 集成 图2 1 数据挖掘系统结构 2 3 数据挖掘的分类 数据挖掘是一个交叉学科领域，受多个学科影响。我们可从不同的角度对 它进行分类，如根据所采用的技术分类，根据任务分类，根据挖掘的数据类型分 类等等。 2 3 1 根据数据挖掘技术分类 目前常用的数据挖掘技术包括如下【1 0 】： ( 1 ) 决策树方法 利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立 粒计算在挖掘数据库中关联规则的应用研究 决策树的一个结点，再根据字段的不同取值建立树的分枝，在每个 分枝子集中重复建立树的下层结点和分枝的过程，即可建立决策树。 国际上最有影响和最早的决策树算法是q u i u l a n 研制的i d 3 方法， 数据库越大它的效果越好，但这种方法仅限于分类任务。 ( 2 ) 神经网络方法 神经元网络技术是属于软计算( s o f tc o m p u t i n g ) 领域内一种重要方 法，它是多年来科研人员进行人脑神经学习机能模拟的成果，已成 功地应用于各工业部门。在数据挖掘的应用方面，当需要从复杂或 不精确数据中导出概念和确定走向比较困难时，利用神经网络技术 就会特别有效。经过训练后的神经网络可以像具有某种专门知识的 “专家”，因此可以像人一样从经验中学习。神经网络有多种结构， 但最常用的是多层b p ( b a c kp r o p a g a t i o n ) 模型。 ( 3 ) 覆盖正例排斥反例方法 它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在 正例集合中选一个种子，到反例集合中逐个比较，与字段取值构成 的选择相容则舍去，相反则保留。按此思想循环所有正例种子，将 得到正例的规则。 ( 4 ) 粗集( r o u g h s e t ) 方法 在数据库中，将行元素看成对象，列元素看成属性( 分为条件属性 和决策属性) 。根据等价类的概念对数据进行划分，它可用于数据约 简( 例如，删除与任务无关的记录或字段) ，数据意义评估，对象相 似或差异性分析，因果关系及范式采掘等。在后面章节还会详细介 绍。 ( 5 ) 遗传算法 基于进化理论，并采用遗传结合、遗传变异、以及自然选择等设计 方法的优化技术。这种算法可以起到产生优良后代的作用。遗传算 法已在优化计算和分类机器学习方面显示了明显的优势。 ( 6 ) 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示 粒计算在挖掘数据库中关联规则的应用研究 的确定性关系) 和相关关系( 不能用函数公式表示，但仍是相关确 定关系) 。对它们的分析采用如下方法：回归分析、相关分析、主成 分分析。 ( 7 ) 模糊集方法 利用模糊集理论对实际问题进行模糊评判、模糊决策、模糊模式识 别和模糊聚类分析。模糊性是客观存在的。系统的复杂性越高，精 确化能力就越低，即模糊性就越强。这是z a d e h 总结出的互克性原 理。 ( 8 ) 基于事例的推理方法 这种方法的思路非常简单，当预测未来情况或进行正确决策时，系 统寻找与现有情况相类似的事例，并选择最佳的解决方案，这种方 法能用于很多问题的求解，。并能获得好的效果，其缺点是系统不能 生成汇总过去经验的模块或规则。 ( 9 ) 可视化技术 用直观图形将信息模式、数据的关联或趋势呈现给决策者，使用户 能交互式地分析数据关系，可视化技术将人的观察力和智能融合入 数据挖掘系统，极大地改善了系统挖掘的速度和深度。 2 3 2 根据挖掘的对象分类 由于挖掘的数据模型和数据类型的不同，挖掘的对象可以包括文本数据源、 i m e m e t ( w 曲) 、关系数据库、事务数据库、面向对象数据库、多媒体数据库、 空间数据库、时间序列数据库等。 2 3 3 根据挖掘的任务分类 根据发现知识的不同，任务的不同可以分为以下几类： ( 1 ) 关联规则分析 关联分析的目的是发现隐藏在数据间的相互关系。后面将具体介 绍。 粒计算在挖掘数据库中关联规则的应用研究 ( 2 ) 特征规则分析 从与学习任务相关的一组数据中提取出关于这些数据的特征式，用 以表达该数据集的总体特征。 ( 3 ) 区分规则分析 发现或提取要学习的数据的某些特征或属性，使之与对比数据能够 区分开来。 ( 4 ) 分类分析 首先为每个记录赋予一个标记，即按标记分类记录，然后检测这些标 记的记录，描述出这些记录的特征。 ( 5 ) 聚类分析 从数据中得出一组聚类规则，将数据分成若干类。这些类可能相互排 斥而且是穷举的，从而描述数据。 ( 6 ) 预测 通过对数据的分析处理，估计一组数据中的某些丢失数据的可能值 或一个数据集合中某种属性值的分布情况。 ( 7 ) 变化和偏差分析 探测现有数据与历史记录或标准之间的显著变化和偏离，从而获得 有用的知识。 2 4 数据挖掘中关联规则的挖掘 在数据挖掘所发现的知识模式中，关联规则模式是非常重要的一种，也是最 活跃的一个分支。关联规则表示数据库中一组对象之间某种关联关系的规则。它 可用于发现交易数据库中不同商品( 项) 之间的联系，从而找出顾客购买行为模 式。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用 户进行分类。 2 4 1 基本概念 设i = i l ，i 2 ，i m ) 是二进制文字的集合，其中的元素称为项( i t e m ) 。记d 为交 粒计算在挖掘数据库中关联规则的应用研究 易( t r a n s a c t i o n ) t 的集合，这里交易丁是项的集合，并且t _ c 。对应每一个交易 有唯一的标识，如交易号，记作t i d 。设x 是一个j 中项的集合，如果x _ c t ，那 么称交易丁包含兄 一个关联规则是形如x j y 的蕴涵式，这里x c , y d , 并且x n y = o 。规则 x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交易数 与所有交易数之比，记为s u p p o r t ( x = ：, y ) ，即 s u p p o r t ( x = ，y ) = t ：x u y c t ，t d i i d l 规则x y 在交易集中的可信度( c o n 矿d e 挖c e ) 是指包含x 和y 的交易数与 包含x 的交易数之比，记为c o n f i d e n c e ( x j y ) ，即 c o n f i d e n c e ( x = ：, y ) = l t ：x u y _ c t ，t d i i t ：x c t ，t e d i 给定一个交易集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用 户给定的最小支持度( m i n _ s u p ) 和最小可信度( m i n _ c o n f ) 的关联规则。若同时满足 最小支持度阂值和最小置信度的规则称为强规则。项目的集合称为项目集 ( i t e ms e t ) 。包括k 个项目的项目集称为k - 项目集。项目集的出现频率是包含 项目集的事务数目，简称为项集的频率、支持计数或计数。如果项目集的出现频 率大于或等于m i ns u p 与d 中事务总数的乘积，则项目集满足最小支持度 m i ns u p 。如果项目集满足最小支持度，则称它为频繁项集( f r e q u e n ti t e m s e t ) 。 频繁k 项目集的集合通常记作l k 。 2 4 2 项目集的性质 频繁项目集具有以下三个性质，这三个性质是所有关联规则算法的基础。 性质1 ：子集支持 设a 和b 是两个不同的项目集，如果a c _ b ，则s u p p ( a ) s u p p ( b ) 。因为d 中所有支持b 的交易也一定支持a 。 性质2 ：非频繁项目集的超集也一定是非频繁的。 如果a 在d 中不满足最小支持度条件，即s u p p ( a ) _ r a i n _ s u p ，则b 的每个子集a 粒计算在挖掘数据库中关联规则的应用研究 也是频繁的。 2 4 3 关联规则的性质 关联规则项目集有以下四个性质【l l 】。 性质l ：规则的非结合性 如果规则x j z 及y j z 在d 中成立，规则x u y ：z 不一定在d 中成立。 如果x 厂、y = o ，并且d 中支持z 的所有交易都只支持x 或y ，则集合x w y w z 的支持度为0 ，因此x u y j z 的可信度为0 。 类似的，如果规则x j y ，x z 成立，规则x ：y u z 不一定成立。 性质2 ：规则不可分解性 如果x u y j z 在d 中成立，规则x j z 及y j z 不一定在d 中成立。例如， 当z 只出现在一个交易中时，如果x 及y 也出现在其中，即s u p p ( x w y ) = s u p p ( z ) ， 规则就是不可分解的。另外，如果x 与y 的支持度与x y 的支持度相比足够大， 就会使得分解后的两个规则不具有所要求的可信度，因而规则也不可分解。 性质3 ：规则的不可传递性 由规则x j y 及y j z 成立不能推出规则x j z 。 性质4 ：规则的可扩展性 设有项目集l ，a ，b ，并且b g a c l ，如果规则a j ( l a ) 不满足最小可信 度条件，则b j ( l b ) 也不满足最小可信度条件。 同理，对项目集l ，d ，c ，并且d g c c l ，d = 0 ，如果规则( l c ) j c 成立， 那么规贝j j ( l d ) j d 也成立。 这个性质在当所有频繁项目集及其支持度已经确定出来后的时候，可以加速 规则产生的过程。 2 4 4 关联规则的分类 传统的关联规则挖掘形式是购物篮分析。事实上，关联规则不是仅此一种。 根据不同的标准，关联规则有许多分类方法【4 】： ( 1 ) 根据规则中处理的值的类型，关联规则可以分为布尔关联规则和量化关 粒计算在挖掘数据库中关联规则的应用研究 联规则。 布尔型关联规则处理的值都是离散的、种类化的数据，它考虑的关联是项的 在与不在的关系；而量化型关联规则是对数值型字段进行处理，将其进行动态的 分割，或者直接对原始的数据进行处理，它描述的是量化的项或属性之间的关联。 当然，数值型关联规则中也可以包含种类变量。例如： 性别= “女 = 职业= “秘书”，是布尔型关联规则； 性别= “女”= 收入= “2 0 0 0 - - - 2 5 0 0 ”，涉及的量化属性收入已离散化， 它是一个量化型关联规则。 ( 2 ) 根据规则中所涉及的数据的抽象层，可以分为单层关联规则和多层关联 规则。 在单层的关联规则中，它不考虑现实的数据是具有多个不同的层次的，不涉 及不同抽象层的项或属性；而在多层的关联规则中，对数据的多层性已经进行了 充分的考虑，规则涉及不同抽象层的项或属性。例如： i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则； 台式机= s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 根据规则中涉及到的数据的维数，关联规则可以分为单维关联规则和多 维关联规则。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而 在多维的关联规则中，要处理的数据将会涉及多个维。换句话说，单维关联规则 是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。 例如： 啤酒_ 尿布，这条规则只涉及到用户购买的物品； 性别= “女”= 职业= “秘书”，这条规则就涉及到两个字段的信息，是 两个维上的一条关联规则。 ( 4 ) 根据关联挖掘的各种扩充分类 根据对关联规则的不同扩充分类，有许多新的方法被提出扩充了关联规则的 数据挖掘，包括：序列模式挖掘、空间关联规则挖掘、否定关联规则挖掘、最大 模式的挖掘、频繁闭合项集的挖掘、文本数据库中的关联规则挖掘以及并行和分 布关联规则的挖掘等。 粒计算在挖掘数据库中关联规则的应用研究 2 4 5 关联规则挖掘的步骤 一般关联规则的挖掘分为以下两过程： ( 1 ) 找出所有频繁项目集：根据定义，这些项目集出现的频繁性至少和预定 义的最小支持计数一样。 ( 2 ) 由频繁项目集产生强关联规则：根据定义，这些规则必须满足最小支持 度和最小置信度。 在这两步过程中，第二步较容易实现，挖掘关联规则的总体性能由第一步决 定。目前有许多挖掘算法及优化算法，在后面我们将做具体介绍。 2 5 经典的关联规则挖掘算法 目前，经典的挖掘算法主要分为两类，一类是产生候选项目集的算法，另一 类是无候选项集的挖掘算法。下面就这两类算法进行具体的介绍。 2 5 1 有候选项集产生的算法 a p r i o d 算法是有候选项集产生的挖掘频繁项集的典型算法，该算法以一种 迭代的方式按从小到大的顺序找出所有的频繁项目集，并根据已知的频繁项目集 去产生更大的侯选集，为提高频繁项集逐层产生的效率，它还将频繁项集的所有 非空子集都必须也是频繁的性质应用于压缩搜索空间。 2 5 1 1a p r i o r i 算法描述 输入：事务数据库d ；最小支持度阀值m i ns u p 。 输出：d 中频繁项集l 。 方法： ( 1 ) l 1 = f i n d _ f r e q u e n t _ l - i t e m s e t s ( d ) ； ( 2 )f o r ( k - - 2 ；l k 1 ；k + + ) ( 3 ) c k = a p r i o r i g e n ( l k 1 ，m i n _ s u p ) ； 得到候选集 ( 4 ) f o re a c ht r a n s a c t i o n sted 粒计算在挖掘数据库中关联规则的应用研究 ( 5 ) c t = s u b s e t ( c k ，t ) ； ( 6 ) f o re a c hc a n d i d a t e sc ec t ( 7 ) c c o u n t + + ； ( 8 ) ( 9 ) l k = c e c rl c c o u n t _ a r n i n _ s u p ) ( 1 0 ) ( 1 1 ) r e t u r nl 2 u k l k ； p r o c e d u r ea p r i o r i _ g e n ( l k 1 ：f r e q u e n t ( k - 1 ) i t e m s e t s ；m i n _ s u p ：m i n i m u ms u p p o r t ) 生成新的侯选集的过程 ( 1 ) f o re a c hi t e m s e t1 1e l k i ( 2 ) f o re a c hi t e m s e t1 2 l k 1 ( 3 )i f ( 1 l 【l 】_ 1 2 1 ) 八( 1 l 2 】= 1 2 2 】) 八八( 1 l 陬- 2 】_ 1 2 k 一2 ) a ( 1 l k - 1 1 2 k - 1 】) t h e n ( 4 ) c = l l0 0 1 2 ；连接产生后选集 ( 5 ) i f h a s _ i n f r e q u e n t _ s u b s e t ( c ，l k - i ) t h e n (6)delete c ； ( 7 ) e l s ea d d c t oc k ； ( 8 ) ( 9 ) r e t u r nc k ； p r o c e d u r eh a s _ i n f r e q u e n t _ s u b s e t ( c ：c a n d i d a t ek - i t e m s e t ；l k 1 ：f r e q u e n t ( k - 1 ) 一i t e m s e t ) 判断子集是否频繁 ( 1 ) f o re a c h ( k 一1 ) 一s u b s e t sso f c ( 2 )i f ( s 壁l k 1 ) t h e n ( 3 ) r e t u r nt r u e ； ( 4 ) r e t u r nf a l s e ； 在上述算法中，它的主要思想是产生候选集后，通过遍历数据库得到频繁项 集。在这里产生候选集是关键的一步，此算法中它将候选集的产生分两个过程完 成：连接和剪枝。 连接：为找l k ，通过l k 1 与自己连接产生候选k - 项集的集合( 这步算法如 过程a p r i o r i _ g e n 中的1 4 步描述) 。在此过程中它通过条件( 1 l 【1 】_ 1 2 1 ) 入 粒计算在挖掘数据库中关联规则的应用研究 ( 1 l 2 1 = 1 2 1 2 1 ) a k ( 1 l k - 2 = 1 2 k - 2 ) a ( i i k - 1 1 2 k - l 】) 保证了所得候选项集即不会 遗漏也不会重复。 剪枝：c k 是l k 的超集，它的成员可以是频繁的也可以是不频繁的，但所有 的频繁k 项集都包含在c k 中。为确定是否频繁只有扫描数据库对c k 进行计数， 但由于c k 可能很大因此要对c k 进行压缩，在这使用a p r i o r i 性质：任何非频繁 的( 1 ( - 1 ) 一项集都不可能是频繁k 项集的子集。因此，如果一个候选k 项集的皿1 ) 一 项子集不在l k - l 中，则该候选集也不可能是频繁的，从而可以从c k 中删除( 具体 算法如过程a p d o r i _ g e n 中的5 - 7 步描述) 。非频繁子集的测试在过程 h a sh f f r e q u e n ts u b s e t 中。 2 5 1 2a p r i o r i 算法局限性 a p d o r i 算法虽然通过自身的一些优化方法大大地减少了候选项集的尺寸获 得了比较满意地结果，但是它还是有其本身的局限性，主要表现在以下两方面： 1 ) 可能产生大量的候选集。当长度为1 的频集有1 0 0 0 0 个的时候，长度为2 的候选集个数将会超过1 0 m 。还有就是如果要生成一个很长的规则的时候，要 产生的中间元素也是巨大量的。 2 ) a p r i o r i 算法采用的是模式匹配的方法检查候选项集，当候选项集较大时， 它可能需要重复地扫描数据库，从而将大量的时间消耗在内存与数据库的数据交 换上。 2 5 1 3a p r i o r i 算法的优化技术 基于以上的局限性，人们提出了许多a p r i o r i 算法的变形，其中采取了多种 优化技术用来提高原算法的效率。具体有以下几种【4 】： ( 1 ) 基于划分( p a r t i t i o n i n g ) 的方法。 这个算法先把数据库从逻辑上分成n 个互不相交的部分，每个部分的最小支 持度等于整个事务数据库的最小支持度与该部分的事务数之积。对于每一个部 分，找出它的所有频繁项集也称为局部频繁项集，然后把每个部分的频繁项集合 起来作为整个数据库的候选项集，通过扫描数据库得出最后全局的频繁项集。整 粒计算在挖掘数据库中关联规则的应用研究 个过程只需扫描两次数据库。这里每部分的大小选择要由每个部分可以被放入内 存的大小决定。但在这种方法中，当把所有部分的频繁项集集合形成全局的候选 项集时时间也是一大瓶颈。 ( 2 ) 基于散列( h a s h b a s e d ) 的方法。 这种方法可以压缩候选k 项集，它的基本思想是当扫描数据库中事务，由候 选k - 项集产生频繁k 项集时，同时产生每个事务的( k 十1 ) 项集，并通过散列函 数将它们散列到散列表的不同桶中增加相应桶的计数，对于散列表中对应桶计数 小于最小支持度的将它们从候选( k + 1 ) 一项集中删除，这样就大大压缩了候选项 集。对于这种方法构造一个有效的散列函数非常关键。 ( 3 ) 基于采样( s a m p l i n g ) 的方法。 这种方法的基本思想是：选取给定数据库的随机样本，然后在样本而不是在 原有数据库中搜索频繁项集。这种方法是用牺牲精度的代价来换取有效性，样本 的大小由是否能够把它放入内存来确定。由于我们搜索的是样本中的频繁项集， 所以我们可能丢失一些全局的频繁项集，为此我们使用比事务数据库最下支持度 低的支持度值来搜索样本中的频繁项集，然后通过数据库的其余部分计算它的实 际频繁度。这种方法比较适合在效率优先的情况下使用。 ( 4 ) 事物压缩( t r a n s a c t i o n ) 的方法。 这种