（计算机软件与理论专业论文）基于无或言规则集的关联规则挖掘算法研究.pdf

华中科技大学硕士学位论文 摘要 数据挖掘是信息技术自然演化的结果。使用数据挖掘工具进行数据分析可以方 便的获得重要的数据模式并应用于决策。数据挖掘本身是面向应用的，关联规则挖 掘作为数据挖掘的重要技术广泛应用于各大领域，特别是商业领域。随着数据集的 大小和复杂度的增长，研究高效的关联规则挖掘算法，并增强其对不同数据集的适 应性显得十分重要。 关联规则挖掘算法分两步实现。先挖掘得到频繁项目集集合，然后根据频繁项 目集集合得到强关联规则。目前的研究侧重于频繁项目集集合生成。经典的生成频 繁项目集集合的算法包括a p r i o r i 算法和f p g r o w t h 算法。基于这些算法产生了很多 变体，不同的变体侧重于不同的改进方向。基于a p r i o r i 的改进算法i h p d 利用多种 改进思想的互补性，进一步提高了关联规则挖掘算法的时间性能，并且使算法的适 应性更广。 i h p d 算法采用了精简集挖掘思想。精简集挖掘基于以下思想：先挖掘出精简频 繁项目集集合，即频繁项目集集合的子集，然后构造出其它频繁项目集，并且计算 得到支持度，而不需要额外的扫描数据库。1 h p d 算法将i h p 算法在候选项目集集合 剪枝方面的特点以及d h p 算法在数据库数据剪枝方面的经验应用于精简集挖掘，使 得该算法不仅改善了针对长类型频繁项目集挖掘的程序性能，而且对精简集不太擅 长的非长类型频繁项目集挖掘，它也能有效的实现。 关键词：数据挖掘，关联规则，频繁项目集，精简集 华中科技大学硕士学位论文 a b s t r a c t d a t am i n i n gc a r tb ev i e w e da sar e s u l to ft h en a t u r a le v o l u t i o no fi n f o r m a t i o n t e c h n o l o g y d a t am i n i n g t o o l sp e r f o r md a t a a n a l y s i s a n dm a yu n c o v e ri m p o r t a n td a t a p a t t e r n s ，c o n t r i b u t i n gg r e a t l yt os t r a t e g i e s d a t am i n i n ge s s e n t i a l l ya i m sa ta p p l i c a t i o n s a s a ni m p o r t a n tt e c h n o l o g yo fd a t am i n i n g ，a s s o c i a t i o nr u l em i n i n gh a sb e e na p p l i e dg r e a t l y t ov a r i o u s f i e l d s ，e s p e c i a l l y b u s i n e s sf i e l d a st h e g r o w t h o ft h ed a t as e t s s i z ea n d c o m p l e x i t y , i ti s c r u c i a lf o ru st o s t u d yt h ea 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 mt o e n s u r e s y s t e m sh i g h - p e r f o r m a n c ea n ds t r o n ga p p l i c a b i l i t y t od a t as e t s a s s o c i a t i o nr u l em i n i n gi sa t w o - s t e pp r o c e s s f i n da l lf r e q u e n ti t e m s e t sa tf i r s t t h e n g e n e r a t es t r o n g a s s o c i a t i o nr u l e sf r o mt h e f r e q u e n t i t e m s e t s r e s e a r c h e m p h a s i z e s p a r t i c u l a r l y o nt h ef i r s t s t e pc u r r e n t l y t h e f a m o u s a l g o r i t h m s t of i n dt h e f r e q u e n t i t e m s e t si n c l u d ea p r i o r ia n df p g r o w t h m a n yv a r i a t i o n so ft h e s ea l g o r i t h m sh a v eb e e n p r o p s e dt h a t f o c u so n i m p r o v i n gv a r i o u sq u e s t i o n s a na p r i o r i - l i k ea l g o r i t h mi h p d c o m b i n e st h ea d v a n t a g e so f m a n ya l g o r i t h m st h e ni m p r o v e st h ea l g o r i t h mp e r f o r m a n c e g r e a t l ya n d c a nb e a p p l i e dt om o r e c a s e s i h p di sa l l a l g o r i t h mb a s e do nc o n d e n s e dr e p r e s e n t a t i o ni ne s s e n c e a l g o r i t h m s b a s e do nc o n d e n s e dr e p r e s e n t a t i o na r eb a s e do nt h e f o l i o w i n gi d e a i t i ss u f f i c i e n tt o e x t r a c tap a r t i c u l a rs u b s e to ft h ef r e q u e n tp a t t e r nc o l l e c t i o n ，s u c ht h a tw ec a n r e g e n e r a t e f r o mt h es u b s e tt h ew h o l ec o l l e c t i o nw i t h o u tc o s t l ys c a no ft h e o r i g i n a ld a t aa n dn e w s u p p o r tc o u n t i n g i h p dc o m b i n e sa l lt h ea d v a n t a g e so fi h pa n dd h pt h e n a p p l i e st h e m t o c o n d e n s e dr e p r e s e n t a t i o nm i n i n g ，w h i c hb r e a k st h er e s t r i c t i o nt h a tt h ea l g o r i t h mc a nb e e f f i c i e n to n l yi nd i f f i c u l tc a s e s 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 ，f r e q u e n ti t e m s e t ，c o n d e n s e d r e p r e s e n t a t i o n i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：刁茅h 蹴妒弋叫肌踟 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密劝。 ( 请在以上方框内打“”) 学位论文作者签名：赫 吼渺午年中月蜘 指导 日期 华中科技大学硕士学位论文 1 1 研究背景 1绪论 随着计算机硬件技术稳定的进步，高性能的计算机，数据采集设备和存储介质 变得越来越容易获得。在此基础上，数据库、数据仓库技术迅速发展，并广泛应用 于各领域，大批量数据的存储成为可能。数掘的丰富带来了对强有力的数据分析工 具的需求，人们已不满足于使用这些数据完成简单的日常事务处理，决策层希望能 从这些数据获得更有价值的信息。因此，研究数据内部特征成为一门新的课题，数 据挖掘就是在这样的背景下成为一门新兴的学科。 数据挖掘( d a t a m i n i n g ) 指的是从大量的数据中发现知识”l 。数据可以是以结构 化数掘为主的关系数据库和数据仓库中的数据，也可以是其它复杂类型的数据，如 对象数据、空间数据、多媒体数据、时序数据、文本数据以及w e b 数据等等。可以 根据知识的特征，将应用于其上的数据挖掘技术分为如下几类：概念描述( c o n c e p t d e s c r i p t i o n ) 、关联分析( a s s o c i a t i o na n a l y s i s ) 、分类和预测( c l a s s i f i c a t i o n a n d p r e d i c t i o n ) 、聚类分析( c l u s t e ra n a l y s i s ) 、孤立点分析( o u t l i e r a n a l y s i s ) 和演变分 析( e v o l u t i o na n a l y s i s ) 。概念描述分为两类：1 数据特征化( d a t ac h a r a c t e r i z a t i o n ) ， 将目标类数据的特征进行汇总；2 数据区分( d a t ad i s c r i m i n a t i o n ) ，将目标类对象 的特性和一个或多个对比类对象的特性进行比较。关联分析是发现关联规则的过程， 这些规则展示属性一值频繁在给定数据集中起出现的条件。分类用于预测数据对 象的类标记。它先分析训练数据集，找出区分数据类的模型，然后使用模型预测类 标记未知的对象类。预测主要用于值预测。聚类分析根据最大化类内的相似性，最 小化类间的相似性的原则对数据对象进行聚类或分组。孤立点分析主要用于挖掘数 据库中与数据的一般行为或模型不一致的数据对象。演变分析描述行为随时问变化 的对象的规律或趋势，并对其建模。本文主要研究基于关系数据库的关联规则挖掘 技术。 典型的数据挖掘系统的体系结构如图1 - l 所示。下面介绍数据挖掘系统的执行步 骤f 1 1 ： 1 整理待挖掘数据。如果数据源为数据库，先要进行数据清理工作，即消除噪 华中科技大学硕士学位论文 声或不一致数据，然后将多种数据源组合在一起。如果数据源为数据仓库，则不需 要进行前面的数据清理和集成工作。由此得到的数据有时可以直接用于数据挖掘。 大多数情况下，需要针对特定任务，选择与分析任务相关的数据，并通过汇总等操 作将数据统一成可挖掘数据。 2 用户通过图形用户界面录入数据挖掘查询语句或者指定特定任务。 3 用户指定兴趣度限制( 如关联分析的支持度、置信度) ，并存入知识库。 4 根据用户录入选择相应的数据挖掘功能模块，使用知识库信息( 如关联分析 的支持度) 指导挖掘过程，在挖掘过程中，用户可以针对挖掘得到的中间结果，由 图形用户界面录入改进的兴趣度限制，重新存入知识库，使用知识库中的新信息重 新指导挖掘过程。数据挖掘功能模块使用数据库服务器或者数据仓库服务器提取整 理后的待挖掘数据。 5 挖掘过程结束后，模式评估模块根据从知识库读取的用户指定的兴趣度限制 ( 如关联规则的置信度) 确定有趣模式。 6 将得到的有趣模式以各种可视化方式返回给用户。 图1 - 1 典型的数据挖掘系统的体系结构 华中科技大学硕士学位论文 需要强调的是，数据挖掘技术从一开始就是面向应用的。目前，数据挖掘在众 多领域都有着广泛的应用，尤其是在如银行、电信、保险、零售等商业领域。数据 挖掘所能解决的典型商业问题包括：市场营销( m a r k e t i n g ) 、客户群体划分( c u s t o m e r s e g m e n t a t i o n c l a s s i f i c a t i o n ) 、背景分析( p r o f i l ea n a l y s i s ) 、交叉销售 ( c r o s s s e l1i n g ) 等市场分析行为，以及客户流失性分析( c h u r na n a l y s i s ) 、客户 信用记分( c r e d jts c o r i n g ) 、欺诈发现( f r a u dd e t e c t i o n ) 、错误信息检测( e r r o r d e t e c t i o n ) 等等 2 1 。 另外，在证券行业可以利用预测模型分析股票行情，在制造业中可以对产品生 产和测试中产生的大量数据进行分析，找出存在的问题，提高质量。针对集体项目 的体育比赛，分析以前比赛的统计数据可以帮助教练更合理的排兵布阵。使用w e b 挖掘和文本挖掘还可以对网页和文档进行分类。数据挖掘还可以应用于科学研究， 如生物医学、天文学等方面。 根据著名数据挖掘网站k d n u g g e t s 统计，目前已有5 0 多种数据挖掘工具问世。 这些工具一般可分为三类：1 通用工具。通用工具是非面向特定应用的，其市场较 为成熟。主要包括：s a se n t e r p r i s em i n e r 、i b m i n t e l l i g e mm i n e r 、u n i c a p r w 、s p s s c l e m e n t i n e 、s g im i n e s e t 、o r a c l ed a r w i n 和a n g o s s k n o w l e d g e s e e k e r ；2 综合工具。 该类工具将d s s ( d e c i s i o ns u p p o r ts y s t e m s ) 、o l a p 和d a t am i n i n g 的功能整合在一 起。著名的有c o g n o ss c e n a r i o 和b u s i n e s so b j e c t s ：3 面向特定应用工具。该领域 厂商针对特定行业提供特定方案。重要的工具有：k d l ( 针对零售业) 、o p t i o n s & c h o i c e s ( 针对保险业) 、h n c ( 针对信用卡欺诈或呆帐侦测) 和u n i c am o d e ll ( 针 对行销业) 。 1 2 关联规则挖掘 关联规则挖掘寻找给定数据集中项之间的有趣联系。下面以购物篮分析为例分 析关联规则挖掘的特点。每个购物篮代表顾客的单次购买对应购物清单，不考虑商 品的购买数量，如果用布尔量0 ，1 分别表示某件商品未被购买和已被购买，那么每 个篮子都可以用在尔向量表示。分析布尔向量，就可以得到反映商品同时购买的购 买模式。例如，关联规则啤酒等尿布说明购买清单中存在啤酒就一定存在尿布。 关联规则挖掘的形式化定义将在2 1 节中给出。下面介绍关联规则的分类情况。 华中科技大学硕士学位论文 ：= = ：= = = 2 = ；= = = = = = = = = = = = = = = = = = = = = = = = ；= ； 根据规则所处理的值的类型，关联规则可分为布尔的( b o o l e a n ) 和量化的 ( o u a n t i t a t i v e ) 。布尔关联规则涉及的项目只有存在和不存在两种情况，上面介绍的 规则啤酒j 尿布就是布尔类型的。量化关联规则描述可量化属性之间的关系，如规 则l n c o m e ( x ，“2 0 0 0 3 0 0 0 ) j b u y s ( x ，“彩电”) ，其中i n c o m e 和b u y s 为量化的 属性，“2 0 0 0 - - 3 0 0 0 ”和“t v ”均为量化值。 根据规则中数据涉及的维可以将关联规则分为单维的( s i n g l e d i m e n s i o n a l ) 和多 维的( m u l t i d i m e n s i o n a l ) 。单维关联规则只涉及单个谓词，如规则b u y s ( x ，“计算 机”) j b u y s ( x ，“软件”) ，而多维关联规则涉及多个谓词，如上面量化关联规则 的例子也是一个多维关联规则。 根据规则涉及的抽象层，关联规则可以分为单层的( s i n g l e l e v e l ) 和多层的 ( m u l t i l e v e l ) 。在单层关联规则中，谓词的挖掘不考虑不同的抽象层，即规则b u y s ( x ，“计算机”) j b u y s ( x ，“软件”) 和规则b u y s ( x ，“计算机”) j b u y s ( x ， “应用软件”) 在单层关联规则挖掘中不可能同时出现，而多层关联规则考虑多个抽 象层。 本文研究的算法是挖掘单维单层布尔类型关联规则。 1 3 关联规则挖掘研究进展 1 3 1关联规则挖掘问题的提出 关联规则挖掘问题首先由a g r a w a l 等人于1 9 9 3 年在【3 中提出。研究该问题主要 是为了帮助零售机构分析销售数据对如下问题做出决策：需要销售哪些商品，怎样 制订促销策略，怎样布置货架使利润最大化等等。该篇论文指出，关联规则挖掘问 题可以分两步解决：先挖掘得到大项集集合( 1 a r g ei t e m s e t s ) ，然后从大项集集合中 产生关联规则。同时它提出了语法约束( s y n t a c t i cc o n s t r a i n t s ) 和支持度约束( s u p p o r t c o n s t r a i n t s ) 的概念，并且指出解决该问题的第二步实现起来相当直接，因此只针对 大项集集合生成提出了相应的算法a i s 。该算法使用层次迭代策略，在每次迭代时， 先扫描数据库，由边界集( f r o n t i e rs e t ) 使用特定构造策略生成候选项目集集合，同 时计数得到该层大项集，接着重新生成新的边界集，方便下层迭代使用。候选项目 集集合生成使用如下思想：将边界集( 边界集中的项目集的超集是潜在的候选项目 华中科技大学硕士学位论文 集) 中的特定k 一项目集x 作为f j 缀，将事务项中比该项目集中所有项目都大的项目 链接到x 尾部得到( k + 1 ) 一项目集，预测该项目集是否是大项集，如果不是，则将该 项目集加入到候选项目集集合，不考虑其超集是否是候选项目集，否则，将该项目 集作为新的前缀递归生成其它的候选项目集。由于生成候选项目集集合需要扫描数 据集，因此可以同时对候选项目集进行计数。边界集中存放的是当前层候选项目集 集合生成时预测是小项集，实际是大项集的项目集，初始阶段边界集存放单个项目 集a 。当项目集预测为小项集时，其超集不会在该层候选项目集集合中出现，因此计 数后一旦发现预测错误，需要在下层迭代时判断其超集是否是大项集。该算法生成 的候选项目集集合很大，严重影响了算法的时间性能。 1 9 9 3 年h o u t s m a 等人提出了使用s q l 表示的大项集集合生成算法一s e t m 【4 l 。 该算法也采用层次迭代策略，并使用和a i s 算法相似的候选项目集集合生成方法。 它将频繁k 一项目集和数据集中事务项拥有的项目相结合得到候选( k + 1 ) 项目集。该算 法简单描述如下：数据集s a l e 使用 形式存放数据，其中t i d 表示事务 项i d 号，i t e m 表示特定项目。使用数据结构月：存放候选k 一项目集集合。r ：中的每 个元素具有如下形式 ，其中x t 是t i d 代表的事务项中潜在的频繁k 一项 目集，即该事务项的特定k 项目子集。可以直接使用r ：对候选k - 项目集计数。r 。和 r ：结构相同，用频繁k 项目集集合e k 对尺：剪枝得到民，将心和s a l e 做连接操作 得到候选( k + 1 ) 一项目集集合r ：+ l 当r ：+ l = g 时算法终止。该算法本质上仍然是对数 据集中的每个事务项得到其可能子集，然后对特定子集计数，判断是否是大项集。 不过它对事务项求得相应的子集使用分层结构实现，可以使用已得到的频繁k 一项目 集对数据集剪枝，去掉无用k 子集，然后由余下的k 子集构造得到事务项的f k + 1 1 一 子集。该算法的缺点是，r ：相当庞大，对特定候选项目集而言，所有包含该项目集 的事务项在j r ：中都有一条记录，而且为了计数方便，还要对r ：排序，另外为了使用 s q l 的优化策略，还要对r 排序，排序需要的时间开销相当大。该算法的最大特点 是，使用标准的s q l 连接操作得到大项集集合，因此可以使用排序和建立索引等方 法对算法进行优化。另外和a i s 算法不同的是，其候选项目集集合生成操作和计数 华中科技大学硕士学位论文 数操作是分离的。 比较上面两个算法可以知道，a i s 算法侧重于候选项目集集合剪枝，而s e t m 算法侧重于数据集剪杖。这两种思想在以后产生的算法中很容易看到。尽管这两个 算法在性能上不是很理想，但是它们的提出为以后的关联规则挖掘研究打下了坚实 的基础。 1 9 9 4 年a g r a w a l 等人在 5 中提出了目前普遍采用的关联规则挖掘问题的形式化 描述并提出了经典的频繁项目集挖掘算法a p r i o r i 。a p f i o f i 算法使用宽度优先搜索 策略，它使用a p r i o r i 性质一频繁项目集的所有非空子集一定是频繁项目集，在第k 次迭代时( k 1 ) 由频繁( k 1 ) 项目集生成候选k 项目集集合，并使用a p r i o r i 性质对 候选k 一项目集集合剪枝，然后扫描数据库对候选k 一项目集进行计数，得到频繁k 一项 目集集合，如此持续迭代，直到频繁k 一项目集集合为空。由此可见，a p r i o r i 算法和 a i s 算法一样，侧重于候选项目集集合剪枝。由于它生成候选项目集集合时不用扫描 数据集，因此无法和a i s 算法一样同时对候选项目集计数，因此其候选项目集集合 生成操作和计数操作是分离的。由于a p r i o r i 算法使用层次迭代策略，如果数据库规 模较大，可以设置缓冲区，将候选项目集集台和频繁项目集集合分成多个块，很方 便的进行内外存交换，因此a p r i o r i 算法针对数据库的可扩展性较好。 在使用a p r i o r i 性质极大的减小了候选项目集集合之后，a g r a w a l 等人将目光又 投入到了数据集剪枝方面，提出了基于a p r i o r i 的改进算法a p r i o r i t i d 。该算法将 a p r i o r i 性质应用到数据集中，用它来减少数据库的大小和事务项的大小。它采用如 下数据集剪枝策略：在k 层迭代中，使用数据集中的事务项的( k 一1 ) 一子集构造得到事 务项的k - 子集，然后使用已得到的候选k 一项目集对数据集剪枝，去掉无用k - 子集。 算法详细描述如下：扫描数据库，用数据集c ：存放该数据库数据，该数据集中的每 个元素具有如下形式 ，其中以是t i d 代表的事务项中潜在的频繁k - 项 目集，即该事务项的特定k - 项目子集。当k 等于1 时，c f 对应于数据库中数据，在 之后的k 次迭代中，使用由l 生成c 女的方法，对c ：一1 中每个事务项对应的记录生 成所有的k - 项目集c ：，过滤c ：中没有出现在c 女中的k - 项目集，即完成对数据库数 华中科技大学硕士学位论文 据中的事务项的剪枝。一旦c ：中某一事务项对应的记录对应的k 一项目集都未出现在 c 。中，那么该事务项数据都可以从数据库中删除，也就减小了数据库的大小。这种 对数据库数据进行剪枝的方法相当直接，也就是在k 次迭代中，将数据库中事务项 信息以k 一项目集的形式表示出来，然后依照候选k 项目集集合中信息，删除不是候 选k 项目集的k 项目集，以此达到对数据库数据进行剪枝的目的。当事务项较大， 需要大量的空间保存数据库数据信息，而且其存储结构随迭代层次动态的变化，维 护它需要相当的时间开销，因此程序性能不算很好。 1 3 2 基于a p r i o r i 的改进算法研究 a p r i o r i 算法提出以后，出现了大量基于a p r i o r i 算法的变体。这些变体有的侧重 于提高关联规则挖掘算法的时间性能，有的侧重于算法的可扩展性，还有的着重解 决针对特定类型数据集挖掘的瓶颈问题。下面根据采用的改进思想分别介绍一些具 有代表性的基于a p r i o r i 的改进算法。 1 9 9 5 年提出了三种基于a p r i o r i 的改进思想：采用哈希技术对候选项目集集合剪 枝，对数据集剪枝和划分技术。 i h p q 算法和d h p 7 1 算法是采用哈希技术对候选项目集集合剪枝的代表性算法。 1 h p 算法和d h p 算法本质上来说都是使用数据集信息对候选项目集集合剪枝，不同 的是，i h p 算法使用数据集的静态信息，而d h p 算法在每次迭代时都对数据集进行 剪枝，因此每次都构造动态的数据集信息。 i h p 算法使用哈希技术将数据集中数据散列到各桶，然后使用数据集中数据对候 选项目集集合进行剪枝。具体说明如下：在初次扫描数据库时，对每个项目采用特 定的哈希函数将包含它的所有的事务项对应的唯一标识t i d 散列到各桶中。对特定 的项目而言，各桶中存放散列到该桶的所有包含该项目的事务项的个数，该哈希结 构被称为该项目的t h t ( t i d h a s ht a b l e ) 。在得到所有k 频繁项目集后，可以将所 有未出现在k - 频繁项目集集合中的项目对应的t h t 删除。剩下的项目对应的t h t 可以用来高效的对候选( k + 1 ) 一项目集集合进行剪枝。这一剪枝是通过函数 g e t m a x p o s s i b l e c o u n t ( x ) 实现的。该函数参数为待剪枝的项目集，返回值为包含该项 7 华中科技大学硕士学位论文 目集的事务项的最大个数。其过程为：先对每个桶查找出该项目集中各商品项的t h t 对应j 二该桶存放的数据的最小值( 即在该桶对应的事务项集中，包含该项目集的事 务项的最大个数) ，然后统计各桶最小值之和即为包含该项目集的所有事务项的最大 个数。如果统计值小于最小支持度，则将该项目集剪枝。 由于它只要维护一个单一的哈希结构，而且除了删除操作外，不必对该结构进 行动态的调整，也不需要改变其中的数据，因此使用它剥候选项目集集合剪枝成本 较低，不过随着迭代层次增大，数据集中存在的大量无用信息会影响候选项目集集 合剪枝的有效性。 m i n g s y a nc h e n 等人提出的d h p 算法采用另外一种方法。在扫描数据库对候选 k 项目集进行计数的同时生成每一个事务项中所有的( k + 1 ) ，项目子集，如果特定 ( k + 1 ) 项目集的k 一项目子集都是候选k 一项目集，则说明该项目集是潜在的频繁( k + 1 ) 一 项目集。使用特定的哈希函数将该( k + 1 ) 项目集存放到哈希结构各桶中，并对各桶计 数，用于下次迭代对候选( k + 1 ) 一项目集集合的剪枝。对候选项目集集合剪枝采用如下 策略：在生成候选k - 项目集的同时，判断该候选k 项目集在k 一项目集集合对应哈希 结构的计数值，将该值和指定支持度进行比较，完成对候选项目集集合的第一次剪 枝。其基本思想是利用上一次迭代( 假设迭代层次为k ) 中扫描数据库的机会，将数 据集中所有可能的( k + 1 ) 一项目集找出，散y l j 至l j ( k + 1 ) 项目集对应哈希结构各桶中并计 数，然后利用该哈希结构对候选( k + 1 ) 项目集集合剪枝。 d h p 算法每一次迭代使用的哈希结构都是基于动态的数据库信息，因此剪枝的 有效性较高，不过由于每一次迭代都需要构造相应的哈希结构，因此开销相当大， 其程序性能改进的有效性也受到影响。 d h p 算法还采用对数据集剪枝的策略使其对候选项目集集合剪枝的效果更好。 由于频繁( k + 1 ) - 项目集具有( k + 1 ) 个k 一项目子集，并且这些项目子集都是频繁的。 于是，对特定事务项来说，如果特定项目能在( k + 1 ) 迭代层次计数中发挥作用，那 么至少在该事务项相应k - 项目子集中存在k 个候选k - 项目集包含该项目，因此在对 候选k - 项目集进行计数时，可以同时判断特定事务项中有哪些项目出现在该事务项 对应的候选k - 项目集中的次数小于k ，那么这些项目就可以从该事务项中删除。这样 华中科技大学硕士学位论文 就实现了对事务项的一次剪枝。 然后对剪枝后的数据库数据进行二次剪枝。这一次也是针对特定事务项的项目。 前面提到，在扫描数据库对候选k 一项目集进行计数的同时会生成每一个事务项中所 有的( k + 1 ) 一项目集，一旦其所有的k - 项目子集都是候选k 一项目集，那么就说n w ( k + i ) - 项目集是潜在的候选( k + 1 ) 项目集，因此使用特定的哈希函数将他们存放到哈希结构 各桶中，并对各桶计数，方便对下次迭代产生的候选( n 1 ) - 项目集集合剪枝。将事务 项中从未在这些潜在的频繁( k + 1 ) 项目集中出现的所有项目从该事务项中删除，由此 实现了对数据库数据的第二次剪枝。 对特定迭代层次k 而言，对数据集的剪枝需要对每个事务项求得所有的( k 十1 ) - 子集，由于求事务项的子集的操作时间复杂度较高，因此只有在总迭代层次较低而 且事务项的长度较小的情况下，对数据集的剪枝需要的时间成本较低。 利用a p r i o r i 性质对数据集剪枝的算法a p r i o r i t i d 已经在前面介绍。 s a v a s e r e 等人在 8 】中提出的p a r t i t i o n 算法采用划分技术改进算法性能。其基本 思想是将数据集d 分区( 分区的大小以可以读入内存为宜) ，用最小支持度和分区中 事务项的个数的乘积作为分区最小支持度，对每个分区挖掘频繁项目集集合，那么 数据集d 中任何频繁项目集必定至少是一个分区的频繁项目集。将所有的分区频繁 项目集集合合并得到全局候选项目集集合，然后扫描数据库，对候选项目集进行支 持度计数，得到全局频繁项目集。这种方法的出发点是为了减少磁盘i o 而将数据集 数据进行分批处理，使每次处理的数据都能在内存中完成。另外，由于分区之间相 互独立，因此可以并行处理，提高了算法的时间性能。但是当数据集数据分布不均 匀时，即大量项目集只在某个分区是频繁项目集，对全局数据集而言不是频繁的， 此时全局候选项目集集合中存在大量的无用项目集，极大的影响了算法的时间性能。 抽样技术于1 9 9 6 年由t o i v o n e n l 9 1 等人提出。其基本思想是从指定的数据集d 中 随机抽取样本s ( 该样本的大4 , n n 掘n 繁项目集的操作可以在内存中完成) ，适当 降低最小支持度，然后挖掘s 中的频繁项目集集合l 8 ，最后扫描数据集剩余部分， 得到r 中的频繁项目集的实际支持度。抽样的方法在效率方面的优势特别n , n ，其 缺点是，由于最小支持度被降低，对于密集型数据集挖掘任务而言，很可能会产生 华中科技大学硕士学位论文 较多的无用频繁项目集。另外，获取的频繁项目集集合可能不完整。如果需要完整 的频繁项目集集合，可以扫描数据集，判断已获得的频繁项目集集合对应的负边界 ( 最小小项集组成的集合) 中是否存在频繁项目集，如果不存在，那么说明f 实际 包含了d 中的所有频繁项目集。否则，说明原数据集中还可能存在未被挖掘的频繁 项目集，对已有频繁项目集集合生成相应的负边界，重新扫描数据集，判断负边界 中是否存在频繁项目集。如此迭代，直到负边界中不存在频繁项目集。通常只需要 扫描一次d ，最多需要扫描两次。 1 9 9 7 年b r i n 等人提出了基于动态项集计数的算法d i d m j 。该算法将数据集划分 为标记开始点的块，不像a p r i o r i 算法那样由( k 1 ) 层候选项目集集合生成k 层候选 项目集集合，它可以在任何开始点添加新的候选项目集。该算法动态的评估已被计 数的所有项目集的支持度，如果一个项目集的所有子集被确定为频繁的，则添加它 作为新的候选项目集。其优势主要有三点：1 算法的迭代层次减少，提高了算法的时 间性能；2 算法具有并行性：3 可以采用增量更新技术扩展该算法。 1 3 3 挖掘密集类型数据的算法研究 前面介绍的基于a p r i o r i 的改进算法对稀疏类型数据集( 如购物篮数据) 挖掘任 务而言具有较好的时间性能但是对于密集类型数据，如电信数据和人口普查数据， 由于算法执行的遍数等于最长频繁项目集的长度，因此遍数会很多，各迭代层次候 选项目集集合也相应增大。如果要得到长度为m 的频繁项目集，需要产生( 2 m 一1 ) 个真子集，因为它们也是频繁项目集，因此具有指数复杂度。算法性能会大大降低。 针对这类数据，产生了下面两种改进思想：最大频繁项目集( m a x i m a l f r e q u e n t i t e m s e t ) 挖掘思想和精简集( c o n d e n s e dr e p r e s e n t a t i o n ) 挖掘思想。这两种思想不仅 可以应用于基于a p r i o r i 框架的算法，还可以用于基于f p g r o w t h 框架的算法以及 基于垂直数据格式1 1 2 i ( 如t i d s e t s 和d i f f s e t s ) 的算法。 最大频繁项目集挖掘的基本思想是：由于最大频繁项目集的任何真超集都不是 频繁的，最大频繁项目集的任何真子集都是频繁的，可以先得到最大频繁项目集集 合，然后对每个最大频繁项目集生成子集，这些子集的并集即为最终的频繁项目集 1 0 华中科技大学硕士学位论文 全集。使用该思想可以得到频繁项目集全集，但是构造得到的频繁项目集的支持度 需要重新扫描数据集计数得到。 1 9 9 7 年，g u n o p u l o s 等人提出了a 1 1 一m f s 算法，该算法是一种针对内存数据 库的挖掘最大频繁项目集的随机算法。它迭代的扩展工作项目集直到无法扩展。该 算法不能保证发现所有的最大频繁项目集，而且不适用于磁盘数据库。不过对于内 存数据库挖掘任务其时间性能较好。z a k i 等人在 1 q 中提出了多个挖掘最大频繁项目 集的算法。这些算法只对预处理过的数据库扫描一次，极大的减小了y o 成本。这些 算法采用了三个主要技术：1 使用等价类( e q u i v a l e n c ec l a s s e s ) 或者最大超图集合 ( m a x i m a lh y p e r g r a p h c l i q u e s ) 将项目集进行聚类得到潜在的最大频繁项目集集合； 2 使用自底向上、自顶向下或者混合型的格遍历( 1 a t t i c e t r a v e r s a l ) 方法从每个聚类 子格中得到最大频繁项目集集合；3 c l u s t e r a p r 算法采用了水平格式的数据库布局， 而其它算法采用了垂直格式的数据库布局。 1 9 9 8 年l i n 和k e d e m 提出了p i n c e r s e a r c h 算法【1 5 】，和f 1 4 q j 的算法不一样的是， 该算法是在搜索过程中企图发现最大频繁项目集，而 1 4 r p 的算法是在搜索之前的初 始化阶段预测可能的最大频繁项目集。该算法像a p r i o r i 一样使用自底向上的策略构 造候选项目集，并且同时进行自顶向下的搜索。在构造候选项目集时采用n p 难度方 法约简( n p h a r dr e d u c t i o n ) ，确保候选项目集集合中不存在非频繁项目集。 b a y a r d o 提出了另外一种挖掘最大频繁项目集的算法m a x m i n e r t l 6 】。该算法使用 r y m o n 的集合枚举树( s e t - e n u m e r a t i o nt r e e ) 搜索框架，采用宽度优先搜索策略， 启发式生成候选项目集集合。它使用两种剪枝方案缩小搜索空间：1 子集不频繁性 ( s u b s e t i n f r e q u e n c y ) ，即如果特定项目集不频繁，那么其超集也不是频繁项目集： 2 超集频繁性( s u p e r s e t - f r e q u e n c y ) ，即如果特定项目集是频繁的，那么其子集必定 都是频繁项目集。方案2 采用“向前看”( 1 0 0 k a h e a d ) 剪技策略，如果提前判断得知 超集是频繁的，就不用构造得到其所有子集，而且也不用对其子集计数，因而减少 了数据库扫描次数。在最坏情况下，其数据库扫描次数和a p r i o r i 算法相等。另外， 它还采用启发式重排序( r e o r d e r i n gh e u r i s t i c ) 策略增强方案2 的剪枝效果。其时间性 能和最大频繁项目集的数目几乎成线性关系，与最长频繁项目集的长度无关，而 l l 华中科技大学硕士学位论文 a p r i o r i 算法的时间性能和最长频繁项目集的长度成指数关系。当挖掘密集类型数据 时，该算法要比a p r i o r i 算法快l 到多个数量级。 精简集1 1 8 1 ( c o n d e n s e dr e p r e s e n t a t i o n ) 的概念由m a n n i l a 等人于1 9 9 6 年提出。精 简集是一种有趣的占一a d e q u a t e 集( 万一a d e q u a t er e p r e s e n t a t i o n ) ，即查询得到的结果 比原始结果要小1 9 1 。频繁项目集集合是占一a d e q u a t e 集，而精简频繁项目集集合是频 繁项目集集合的一个特殊子集，即不存在特定规则的频繁项目集集合。精简集挖掘 基于以下思想：先挖掘出精简频繁项目集集合，然后构造出其它频繁项目集，并且 计算得到支持度，而不需要额外的扫描数据库。 精简频繁集挖掘算法的剪枝分三步：1 k 无规则频繁项目集的( k - 1 ) 予集必定是 ( k - 1 ) 一无规则频繁项目集；2 k - 无规则频繁项目集的支持度一定大于等于预先定义好 的支持度闽值：3 k - 无规则频繁项目集一定是无规则的。 使用精简集的算法很多，如基于j f r e e 集的m i n e x 算法1 1 9 1 、基于c 1 0 s e d 集的 a c l o s e 算法 2 0 1 、基于d i s j u n c t i o n f r e e 集的h l i n e x 算法 2 2 1 、基于r u l e f r e e 集的 h o p e - i i 算法、将分区思想和f r e e 集相结合的s e g f r e e 算法以及将使用哈希技术对 候选项目集集合进行剪枝、减少事务项的大小和减少数据库的大小的改进思想和 d i s j u n c t i o n f r e e 集结合起来的i h p d 算法。这些算法都是基于a p r i o r i 框架的精简集 挖掘算法，我们将在第三章对上面提到的算法进行详细介绍。还有些基于其他框架 的精简集挖掘算法。如基于f p _ g r o w t h 框架的c l o s e d 集挖掘算法c l o s e t l 2 3 1 和基于 垂直数据库格式的c l o s e d 集挖掘算法c h a r m f 2 4 1 。 针对密集类型数据挖掘，2 0 0 0 年a g a r w a l 等人提出了使用宽度优先搜索策略的 t r e e p r o j e c t i o n 算法口5 】和使用深度优先搜索策略的d e p t h p r o j e c t 算法1 2 6 1 。它们都采用 字典树结构口”( l e x i c o g r a p h i ct r e e ) 。其中t r e e p r o j e c t i o n 算法使用类似a d r i o r i 算法 的层次迭代策略，使用字典树结构存放候选项目集集合，在k 层迭代时将事务项投 影到字典树结构中( k - 2 ) 层的所有结点，构建每个节点对应的矩阵结构。然后使用 该矩阵结构直接得到频繁k 一项目集集合，最后调整字典树结构中各节点信息方便下 层迭代使用。由于在各层迭代中都要将事务项投影到字典树结构中特定层的所有节 点，因此c p u 时间花费较大，而且由于每个节点都要生成相应的矩阵结构，因此内 华中科技大学硕士学位论文 存占用较大。不过，由于它使用事务项投