（计算机应用技术专业论文）最大频繁项集和频繁基项集挖掘算法研究.pdf

河南大学硕士研究生学位论文 摘要 数据挖掘是计算机科学的一个领域，目的是通过分析快速增长的商业、科学 和工程数据来获取知识和其他利益，这个领域正在迅猛增长和发展。关联规则的 挖掘是数据挖掘课题中的一个重要分支，它被用来描述事务数据库中属性间存在 的潜在关系，近年来已经成为数据挖掘中一个相当活跃的领域。 频繁项集挖掘是关联规则挖掘中的最重要的任务。本文对频繁项集的一种紧 凑表示最大频繁项集挖掘和如何在不丢失规则信息基础上减少关联规则生成 数量问题进行研究。研究的主要内容包括以下几个方面： 1 对有限个有限链直积下集极大元挖掘算法一b o u n d a r y 算法进行了深入研 究，它是一个深度优先算法，可以用在最大频繁项集这类具有位置格下集性质挖 掘问题中。 2 提出了一种用位置向量精确表示项目集的深度优先算法g m p v 来挖掘最大 频繁项集，算法中使用布尔矩阵方法来进行事务数据库映射，在频繁项集生成过 程中通过超集存在检测和基于超集支持度计算等方法提高算法效率，通过实验验 证了g m p v 算法的有效性。 3 在分析频繁基项集的定义和性质的基础上提出了频繁基项集挖掘的剪枝策 略，设计了频繁基项集的挖掘算法，它可以用来进行极大布尔关联规则生成，并 且根据极大布尔关联规则的性质简化了基于频繁闭项集和频繁基项集的极大布尔 关联规则的生成算法。 关键词：关联规则；最大频繁项集；位置向量；布尔矩阵：极大布尔关联规则； 频繁基项集 a b s t r a c t d a t am i n i n gi s a na r e ai nc o m p u t e rs c i e n c et h a t a i m st oa n a l y z et h er a p i d l y i n c r e a s i n g 锄0 u n t so fb u s i n e s s ，s c i e n t i t l e ，a n de n g i n e e r i n gd a t a f o rk n o w l e d g ea n d o t h e rp r o f i t a b l eu s e s a s s o c i a t i o nr u l e sm i n i n gi s a l li m p o r t a n tb r a n c ho f m i n i n g ， w h i c hi su s e dt od e s c r i b et h ei m p l i c i tr e l a t i o n s h i po ft h ea t t r i b u t e si nt h et r a n s a c t i o n a l d a t a b a s e s 锄dh a sb e c o m ea l lq u i t ea c t i v ef i e l di nt h er e s e a r c ho fd a t am i n i n g i nr e c e n t m i n i n gf r e q u e n ti t e m s e t si st h em o s ti m p o r t a n tt a s ko fm i n i n g a s s o c i a t i o nn l l e s l i l t h i sp a p e r ，t h ep r o b l e m so fm i n i n gm a x i m a lf r e q u e n ti t e m s e t s ，w h i c h 1 sac o m p a c t r e p r e s e n t a t i o no ff r e q u e n ti t e m s e t sa n dh o wt or e d u c et h eq u a n t i t yo ft h e a s s o c l a t l o n n l l e sw i t h o u t1 0 s ei n f b r m a t i o no fa s s o c i a t i o nr u l e sa r er e s e a r c h e d t h em a i n r e s e a r c hl s a sf o l l o w s ： 1 t h eb 0 u n d a r ya l g o r i t h mw h o s ef u n c t i o ni st of i n dt h em a x i m a l e l e m e n t so fa d 0 w n s e to fd i r e c tp r o d u c to ff i n i t ef i n i t e c h a i n si st h o r o u g h l ys t u d i e d t h eb o 眦d 叫1 s ad e p t h f i r s ts e a r c ha l g o r i t h m ，a n d i tc a l lb eu s e dt om i n i n gt h em a x i m a l 仃e q u e n t i t e m s e t sp r o b l e m ，w h i c hh a st h ep r o p e r t yo fd o w n s e to fp o s i t i o nl a t t l c e 2 an e wd e p t h f k s ts e a r c ha l g o r i t h m ，c a l l e dg m p v , w h i c h a c c u r a t e l yd i s p l a y st h e i t e m s e tb a s e do np o s i t i o nv e c t o r , h a sp u tf o r w a r d t om i n et h em a x i m a l 仃e q u e n t1 t e m s e t s i ng m p v , t h et r a n s a c t i o nd a t a b a s ew e r em a p p e dt oab o o l e a nm a t r i xa n ds u p e r s e t c h e c k i n ga i l dp r u n i n gm e t h o db a s e d o ns u p p o r ta l s ow e r eu s e dt oi n c r e a s et h ea l g o r i t h m e f f i c i e n c y t h ee x p e r i m e n tr e s u l t sd i s p l a y e dt h a tt h ea l g o r i t h m i sv a l l d i t y 3 b a s e d0 nt h ea n a l y s i so ft h ed e f i n i t i o na n dp r o p e r t yo fo p e n e df r e q u e n ti t e m s e t ， t h e0 p e n e df r e q u e n ti t e m s e tm i n i n ga l g o r i t h mw a sd e s i g n e d ，w h i c hc a i lu s et og e n e r a t e t h em a x i m a lb o o l e a na s s o c i a t i o nr u l e s a c c o r d i n gt o t h ep r o p e r t y0 ft h em a x i m a l b 0 0 1 e a na s s o c i a t i o nr u l e s ，t h i sp a p e rp r e d i g e s t e dt h eg e n e r a t i n ga l g o r i t h mo fm a x i m a l b o o l e a na s s o c i a t i o nr u l e s k e y w o r d s ：a s s 。c i a t i o nr u l e s ；m a x i m a lf r e q u e n ti t e m s e t ；p o s i t i o nv e c t o r ；b 。l e 锄 m a t r i x ：m a x i m a lb o o l e a na s s o c i a t i o nr u l e s ；o p e n e df r e q u e n ti t e m s e t s 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所里交酌学住论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外。论文中不包括其他人已经发表或撰 写过酌研究成果。也不包括其他人为荻得任何教育、科研机构酌学位或证书而 使用过酌材料。与我一同工作的同事对本研究所徽的任何贡献均已在论文中作 了明确酌说明并表示了谢意。 学位串请汰，( 襻位论变样者) 签名： 趵矽卑细，；，日 关于学位论文著作权使甩授权书 本人经河韵大学审核批准授子爰蠡士擘位。作为学位论文的作者，本人完全 了解并同意河南走擘有关保留、。缴罔学往论文3 的要求，即河南大学有权向图家 图书馆、科研信息机构、数据收集机掏和本校图书馆等提供擘位论文( 纸质文 本和电子文本) 以供公众检索、奎阅。本弘授权河南灾学出于宣扬、展览学校 学术发展和进行学术交流等哥竹。可采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用奉授权书) 学位获得者( 学位论文作者) 釜名：驻垒 2 df 学位论文指导教j 研釜名： 2 dr d 年6 月f ，曰 河南大学硕士研究生学位论文第l 页 第1 章绪论 数据挖掘是目前信息科学领域最前沿的研究课题之一，在市场分析、金融投 资、医疗卫生、环境保护、产品制造和科学研究等许多领域均有成功的应用，取 得了十分可观的社会效益和经济效益。同时，数据挖掘的研究和应用为对于计算 机科学前沿学科的发展注入了新的活力，有力地促进了计算机科学朝着纵深方向 顺利发展。 1 1 研究背景与意义 近几十年中，计算机硬件技术稳步的进步导致了功能强大的和价格可以接受 的计算机、数据收集设备和存储介质的大量供应，同时，数据收集和数据存储技 术的快速进步使得各组织结构积累了海量数据。然而，提取有用的信息已经成为 巨大的挑战。如何才能不被大量的数据淹没，并从中发现隐藏的、能对决策提供 支持的知识，提高数据的利用率，就成了人们的焦点。数据挖掘技术应运而生， 并得以蓬勃发展。 关联规则的挖掘是由a g r a w a l 等人【l 】【2 】于1 9 9 3 年首先提出的一个重要的数据 挖掘研究课题，最初用来分析购物篮事务数据中各项之间的有趣联系，以发现商 品销售中的顾客购买模式。关联分析同时在其他方面，如生物信息学、医疗诊断、 网页挖掘、文本分析和科学数据分析等领域也得到了广泛的应用。 1 1 1 数据挖掘概述 数据挖掘( d a t am i n i n g ，d m ) 指的是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的但又是潜在有用的并且最 终可理解的信息和知识的非平凡过程。1 9 9 5 年，在加拿大蒙特利尔召开了第一届 知识发现和数据挖掘国际学术会议，“数据挖掘”概念第一次由u s a m af a y a a d 提出， 从此，数据挖掘一词得以广泛流传。 数据挖掘是数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 不可缺 少的一部分【4 7 】，k d d 是将未n - r 的数据转换为有用信息的整个过程。k d d 过程 包括一系列转换步骤，从数据的预处理到得到数据挖掘结果后的处理。 第2 页河南大学硕士研究生学位论文 数据挖掘涉及多学科技术的集成【2 0 1 ，包括数据库和数据仓库技术、统计学、 机器学习、高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与 信号处理以及空间或时间数据分析。通过数据挖掘，可以从数据库提取有趣的知 识、规律或高层信息，并可以从不同角度观察或浏览它们。发现的知识可以用于 做决策、过程控制、信息管理和查询处理。因此，数据挖掘在信息和数据库系统 方面是最重要的前沿之一，是信息技术最有发展前途的交叉学科之一。 数据挖掘任务用于指定数据挖掘任务要找的模式类型。通常来说，数据挖掘 任务可以分为两大类【2 0 】【4 刀：一类是描述性挖掘任务，描述性挖掘任务描述数据库 中数据的一般性质，任务的目标是导出概括数据中潜在联系的模式，比如相关、 趋势、轨迹、聚类和异常。在本质上，描述性数据挖掘任务通常是探查性的，并 且常常需要后处理技术验证和解释结果；另一类是预测性挖掘任务，预测性挖掘 任务主要是对当前的数据进行推断，以做出预测，其目标是根据其他属性的值， 预测特定属性的值。 数据挖掘任务中的预测建模涉及说明变量函数的方式为目标变量建立模型。 有两类预测建模挖掘任务，分类和回归。分类用于预测离散的目标变量，其找出 描述和区分数据类或概念的模型，以便能够使用模型预测类标号未知的对象类； 回归用于预测连续的目标变量，是一种最长使用的数值预测的统计学方法。这两 项任务的目标都是训练一个模型，是目标变量预测值与实际值之间的预测达到最 小；关联分析用来发现描述数据中的强关联特征的模式，所发现的模式通常蕴含 规则或特征子集的形式来表示。由于搜索空间是指数规模的，关联分析的目标是 以有效的方式提取最有趣的模式；聚类分析中对象根据最大化类内部的相似性、 最小化类之间的相似性的原则进行聚类后分组，其目标是用来发现紧密相关的观 测值群组，使得与属于不同簇的观测值相比，属于同一簇的观测值之间尽可能类 似；异常检测的任务是识别其特征显著不同于其他数据的观测值，这种观测值称 为异常点或离群点，异常检测的算法的目标是发现真正的异常点，而避免错误地 将正常的对象标注为异常点。 尽管与统计学、机器学习和人工智能相比，数据挖掘还很年轻，但是数据挖 掘领域已经发展的很大很丰富了，国际上有许多与数据挖掘相关的会议。数据挖 掘的专门会议主要包括a c ms i g k d d 知识发现与数据挖掘会议( k d d ) 、i e e e 数 河南大学硕士研究生学位论文第3 页 据挖掘国际会议( i c d m ) 、s i a m 数据挖掘国际会议( s d m ) ，其他国际或地区性的数 据挖掘会议有欧洲数据库知识发现的原理与实践会议p k d d 、亚太知识发现与数 据挖掘会议p a k d d 以及数据仓库与知识发现国际会议( d a w a k ) 。数据挖掘的会议 也可以在其他主要会议上找到，如a c ms l g m o d p o d s 会议、超大型数据库国际 会议( v l d b ) 、信息与知识管理会议( c i k m ) 和数据工程国际会议( i c d e ) 、机器学习 国际会议( i c m l ) 、人工智能联合国际会议( i j c a i ) 和美国人工智能学会会议 ( a a a i ) 。 数据挖掘方面的期刊包括i e e e 知识与数据工程汇刊( i e e et r a n s a c t i o no n k n o w l e d g ea n dd a t ae n g i n e e r i n g ，t k d e ) 、数据挖掘与知识发现( d a t am i n i n ga n d k n o w l e d g ed i s c o v e r y ) 、知识与信息系统( k n o w l e d g ea n d i n f o r m a t i o ns y s t e m s ) 、 智能数据分析( i n t e l l i g e n td a t aa n a l y s i s ) 、信息系统( i n f o r m a t i o ns y s t e m s ) 和智 能信息系统国际杂志( j o u r n a lo fi n t e l l i g e n ti n f o r m a t i o ns y s t e m s ) 等。 1 1 2 关联规则概述 关联分析是用于发现隐藏在大型数据集中的令人感兴趣的联系的一种数据挖 掘方法，其发现的联系可用关联规则或频繁项集的形式表示，关联分析是数据挖 掘中最为热门的研究课题之一。 假设在一个商场销售记录中挖掘出有如下一条规则： 尿布 j 啤酒) ( 支持度 = 6 0 ，置信度= 7 5 ) ，此规则的直观意义为：所有购买商品的顾客中有6 0 的顾 客同时购买了尿布和啤酒，而所有购买尿布的顾客中有7 5 的顾客购买了啤酒。 规则的支持度反映了规则的重要性，而规则的置信度反映了规则的准确度。 对关联规则挖掘出的结果进行分析时，需要注意的是由关联规则做出的推断 并不蕴含必然的因果关系，关联规则的挖掘结果只表示规则前件和后件中的项明 显出现，同时，因果关系需要关于数据中的原因和结果属性的知识，并且通常涉 及长期出现的联系。 给定的事物的集合丁，关联规则的发现是指找出支持度大于等于m n _ s u p p o r t 并且置信度大于等于m i n 够d e n c e 的所有规则，其中m i ns u p p o r t 和 m h 7c o n ：d e n c e 是对应的支持度和置信度阈值。挖掘关联规则的一种原始方法是： 计算每个可能规则的支持度和黄信度。但是这种方法代价过高，因为可以从数据 集中提取的规则的数目达到指数级。因此提高关联规则挖掘算法性能的第一步是 第4 页河南大学硕士研究生学位论文 拆分支持度和置信度要求，大多数关联规则挖掘算法通常采用的一种策略是：将 关联规则挖掘任务分解为如下两个主要的予任务，即将关联规则挖掘分成两步来 进行： 第一步称为频繁项集的产生：此步的目标是发现满足给定最小支持度阈值的 所有项集，这些项集称为频繁项集( f r e q u e n ti t e m s e t ，f i ) ，或称之为频繁模式( f r e q u e n t p a t t e r n ) 。 第二步是关联规则的生成：此步的目标是从上一步发现的频繁项集中提取所 有满足最小置信度要求的关联规则。 一般来说，频繁项集的产生所需的计算开销远大于关联规则的产生所需的计 算开销，因此关联规则挖掘的性能主要取决于频繁项集产生的效率。 自关联规则被提出之后，由于其广泛的社会应用意义，之后诸多的研究人员 对对关联规则的挖掘问题进行了大量研究，以解决关联分析任务的概念、实现和 应用问题。关联分析任务的概念问题主要研究集中在建立描述关联分析的理论基 础的框架、扩展形式机制，以处理新的模式类型。例如，已经定义了许多新类型 的模式，如轮廓关联模型【5 1 、模糊关联模型【2 2 】、加权的关联模型【l o 】等其他类型的 模式包括频繁闭项集【4 1 】【5 6 1 、最大频繁项集7 1 等，同时关联分析也成功应用于序列 数据【1 8 】、空间数据2 3 1 和基于图的数据【4 2 】【5 4 1 。关联分析实现问题领域内的研究活动 主要考虑：将挖掘能力集成到现有的数据库技术中，这样可以利用数据库系统 的索引和查询处理机制；产生高效的可伸缩的算法；处理用户指定的或领域 特定的约束；提取模式的后处理。关联规则已经应用于各样的应用领域，如w e b 挖掘【4 6 1 、网络入侵检测【1 1 1 、生物信息掣5 1 1 等等。关联分析也已经应用到其他机器 学习类问题，如分类和回归和聚类分析【5 2 】等。 数据挖掘之所以引起了信息产业界和整个社会的极大关注，其主要原因是由 于现实世界存在广泛使用的大量数据，并且迫切需要将这些数据转换成有用的信 息和知识。从数据挖掘中获取的信息和知识可以广泛用于各种应用，包括市场分 析、欺诈检测、顾客报有、产品控制和科学探索等。最初用于购物篮数据挖掘的 关联分析方法，其所发现的有趣联系可以用关联规则来表示。关联分析可以应用 于其他领域，如生物信息学、医疗诊断、网页挖掘和科学数据分析等。例如，在 地球科学数据分析中，关联模式可以揭示海洋、陆地和大气过程之间的有趣联系。 河南大学硕士研究生学位论文第5 页 这样的信息能够帮助地球科学家更好地理解地球系统中不同的自然力之间的作 用。同时，关联规则可以应用于顾客购物分析、目录设计、商品广告邮寄分析、 追加销售、商品货架设计、仓储规划等商业应用中，关联规则在商业等领域的成 功应用，使它成为数据挖掘领域最成熟、最主要的、最活跃的研究内容。 1 2 国内外研究现状 在关联规则的挖掘中，项的集合称为项集，包含k 个项的项集称为k 项集。项 集的出现频率是包含项集的事务数，可以简称为项集的支持度计数。当某项集的 支持度计数满足预定义的最小支持度阈值时称为频繁项集。由于规则的置信度也 是从支持度计数中推出的，所以关联规则的挖掘问题也可归结为挖掘频繁项集的 问题。如在上节所提到的关联规则挖掘的两个步骤中，频繁项集挖掘的步骤的开 销远大于根据置信度生成关联规则的步骤的开销，所以挖掘关联规则的总体性能 由第一步决定。因此关联规则挖掘算法研究大部分都是集中在如何快速有效地挖 掘频繁项集上。频繁项集的挖掘主要分两类：一类是候选频繁项集产生检测算法 和不产生候选频繁项集的算法，分别以a p r i o r i e l 】和f p g r o w t h 1 9 】算法为代表。 在诸多频繁项集挖掘算法中，计算项集的支持度是产生频繁项集最耗时的工 作，因此，只有减少生产的项集数才可降低算法开销。同时从大型数据集中挖掘 频繁项集的主要挑战就是挖掘过程中产生的大量的满足最小支持度阈值的项集， 当支持度阈值设得很低时尤其如此。这是因为如果一个项集是频繁的，则它的每 个了集也是频繁的。例如，对一个维数为的频繁项集，其每个子集都是频繁项 集，即有2 l 1 个予集，当三很大时，这是一个n p 问题。因此，怎样从频繁项集 中识别出可以推导出其他频繁项集的、较少的、具有代表性的项集引起了人们的 兴趣。因此，最大频繁项集的挖掘研究是很有意义的。 1 2 - 1 最大频繁项集研究现状 b a y a r d o 提出的最大频繁项集【_ 刀( 在有的文中也称为极大频繁项集) 是这样的频 繁项集它的直接超集都不是频繁的，最大频繁项集提供了频繁项集的紧凑表 示，由最大频繁项集可以导出所有的频繁项集的集合。对于可能产生长频繁项集 的数据集，最大频繁项集提供了颇有价值的表示，因为这种数据集中的频繁项集 可能有指数多个。另外，在某些数据挖掘应用中挖掘出最大频繁项集的意义也大 第6 页河南大学硕士研究生学位论文 于挖掘出所有频繁项集的意义，因而国内外关于最大频繁项集挖掘已经进行了大 量的研究。 本文中将最大频繁项集的挖掘算法分为宽度优先算法和深度优先算法两类进 行分析。算法m a x m i n e r l 7 ，p i n c e r - s e a r c h t 3 4 1 ，d m f i 3 6 】和d m f i a 删属于最大频繁 项集挖掘的宽度优先算法。其中，m a x m i n e r 使用集合枚举树作为概念框架，对集 合枚举树进行宽度优先搜索，其突破了传统的自底向上的搜索策略，采用动态排 序的方法来保证高效的前瞻剪枝( 1 0 0 k a h e a dp r u n i n g ) ，减少了遍历的结点数，降低 了搜索时间。由于m a x m i n e r 采用的是传统的横向数据集来计算频繁项集的支持 度，所以它与a p r i o r i 算法一样，扫描数据集的次数等于最长频繁项集的规模。算 法d m f i 和d m f i a 针对m a x m i n e r 没有利用自顶向下信息的缺陷进行改进，d m f i 有效地把自底向上和自顶向下的双向搜索策略进行了结合，并有效地利用了超集 剪枝，提高了最大频繁项集挖掘效率，但该算法仍需多次重复扫描数据库d 来计 算项目集的支持数，这点缺陷还是很大地影响了算法的效率。d m f i a 算法通过两 次扫描建立f p 树来压缩表示事务数据库中与频繁项集相关的信息，从而避免了对 数据库的多遍扫描，是基于f p t r e e 结构的最大频繁项集挖掘算法。p i n c e r - s e a r c h 采用了自底向上和自顶向下的双向搜索策略，但是其候选最大频繁项集的生成中 产生了过多的无用候选项目集，这是p i n c e r - s e a r c h 算法的一个缺陷。 挖掘最大频繁项集的宽度优先算法在计算项集的支持度的时候，大多需要多 次扫描数据库，也需要生成大量的候选最大频繁项集，当数据集一旦上了规模， 就很难保证算法的效率。因此与宽度优先算法对应，在减少扫描数据库次数和避 免生成大量候选最大频繁项集的思想指导下，很多研究者进行了最大频繁项集深 度优先算法的研究。 算法d e p t h p r o j e c t 6 1 ，m a f i a i s ，g e n m a x 1 5 1 ，m i n m a x 4 9 1 ，s m a r t m i n e r 5 引， f p m a x 1 6 1 ，f p m a x 1 7 1 ，f p m f i 5 邹，m m f i 3 1 】都是挖掘最大频繁项集的深度优先算 法。a g a r w a l 等首先提出了按深度优先搜索策略挖掘最大频繁项集的d e p t h p r o j e c t 算法，该算法在内存中保存了所要挖掘的数据集，采用选择性投影。d e p t h p r o j e c t 算法采用了与m a x m i n e r 算法类似的超集频繁性剪枝策略，并且也需要一个最终的 剪裁步骤。算法m a f i a 中沿用了算法d e p t h p r o j e c t 5 】的事务数据库和项集的位图表 示方法，除了传统的前瞻剪枝外，m a f i a 新采用一种称为父等价( p a r e n te q u i v a l e n c e ) 河南大学硕士研究生学位论文第7 页 的方法来做进步的剪枝，采用了深度遍历策略。g o u d a 和z a k i 提出的g e n m a x 算法采用基于集合枚举树的概念模型，将剪枝与挖掘过程集成在一起，并使用两 种优化策略使之正好返回最大频繁项集，但是g e n m a x 算法的超集存在判断需要 分两步进行，影响了最大频繁项集的产生。m i n m a x 使用垂直t i d 1 i s t 数据格式，通 过简单的t i d 1 i s t ( t r a n s a c t i o ni dl i s t ) 交运算计算支持度，使用了传统的几种高效剪枝 策略，还提出了一种新颖的多层回溯剪枝策略，进行了更有效的剪枝。s m a r t m i n e r 也是基于集合枚举树的概念模型和纵向数据表示法。该算法使用一种称为尾信息 的数据结构来指导挖掘过程，能充分利用已挖掘出来的最大频繁项集中的相关信 息。尽管s m a r t m i n e r 不需要超集检测，但是其尾信息的建立和访问代价不小；另 外，它没有对事务数据库投影进行压缩表示。f p m a x 算法是有效的基于f p 树挖 掘最大频繁项集的深度优先算法，它使用f p 树来压缩表示事务数据库中与频繁项 集相关的信息，它不仅保存了基于原始数据集建立的f p t r e e 树，并将最大频繁项 集保存在一棵m f i t r e e 中，在一定程度上提高了最大频繁项集的存取速度。 f p m a x 算法在f p m a x 算法的基础上采用了一种名为f p a r r a y 的基于数组的支持 度预计算技术，大大减少了算法扫描f p t r e e 的时间，但是建立f p a r r a y 的代价 不低。f p m f i 算法也是一个基于f p t r e e 的深度遍历算法，该算法中指出在最大频 繁项集挖掘过程中，当支持度较小时超集检测是算法的主要耗时操作，并采用了 基于投影进行超集检测的机制，另外并通过删除条件模式树的冗余信息，有效地 压缩了条件模式树的规模。m m f i 基于改进的f p t r e e 结构，算法通过修改结点结 构建立有序f p t r e e 以及采用一种n b n ( n o d eb yn o d e ) 的遍历策略，使得算法在挖 掘过程中，既不需要进行超集检测也不需要递归的建立条件频繁模式树，有效的 提高了算法的执行效率。但是m m f i 算法中需要沿结点链搜索本层右侧的结点， 检测是否存在当前处理项集的予集，这一操作的效率有待提高。 本节对现有的最大频繁项集挖掘算法进行了讨论，这些算法的实践证明，关 于频繁项集的挖掘问题已经取得了很大的成绩，但仍有许多问题值得深入研究， 如在最大频繁项集挖掘中如何更为高效的进行超集检测或者以更小的代价避免超 集检测以及如何高效地存储数据集以方便高效进行项集支持度计数等问题仍是值 得深入研究的，本文第三章即是在这些算法的基础上提出一种基于位置向量和布 尔矩阵的最大频繁项集挖掘算法。 第8 页河南大学硕士研究生学位论文 1 2 2 极大布尔关联规则研究现状 在关联规则的分类中，基于规则中处理的变量类别可以将关联规则分为布尔 型关联规则和量化关联规则。布尔关联规则问题处理的属性值一般都是二值逻辑 值；量化关联规则对数值型字段进行处理，将其进行动态的分割，或直接对原始 的数据进行处理，其所处理的数据库属性值可以是数量属性也可以是类别属性。 关联规则在a g r a w a l 等人于文献 2 e p 引入后，a g r a w a l 等在【3 中对关联规则 作了进一步形式化。r s r i k a n t 和r a g r a w a l 在【4 3 】中对关联规则扩展为数量关联 规贝1 j ( q u a n t i t a t i v ea s s o c i a t i o nr u l e s ) 时，将【2 】【3 中的关联规则改称为布尔关联规则 ( b o o l e a n a s s o c i a t i o nr u l e s ) ，由于本文中主要讨论布尔关联规则问题，所以文中在 无特殊说明下，所指的关联规则都是指布尔关联规则。 由【4 3 】中数量关联规则的形式化的描述可知，数量关联规则是基于区间划分 的，即先对属性值域进行区间划分，再给出数学表示。数量关联规则的挖掘是通 过转化为布尔关联规则来进行挖掘的。但是当数量属性取值范围很宽时，如何划 分区间是实现数量关联规则问题到布尔关联规则问题转变的关键，其有可能导致 两个相互牵制的问题“最小支持度问题”和“最小置信度问题”，在文献 1 2 2 4 】 中研究了区间划分的问题。 上文1 1 2 节中提到的模糊关联规则9 】【1 8 】【2 2 】可以认为是对区间划分方法一种改 进，其常利用专家知识人为定义对属性值域进行模糊划分，考虑属性值域上的模 糊集，这种方法的主要问题是在属性值域上有时可能更无法给出有意义的模糊划 分或模糊集。 对事务数据库中属性值均为非负实数的项目之间的关联关系进行研究的比例 规则【1 3 】中，认为事务数据库中属性均为数量属性，属性值均为非负实数，这种比 例规则的研究方法不存在数量关联规则问题的区间划分问题。如果事务数据库中 数据成线性相关的话，那么比例规则能够达到很好的相关性描述。但是无论是在 现实生活中，还是事务数据库里面的数据，有很多数量属性之间并不具有比例关 系，而且有时候人们并不关心一种严格的比例关系，而可能更加关心数量属性的 比例究竟表现在什么样的范围内。文献 2 5 1 1 2 6 1 1 5 0 1 研究了上述的问题，提出了针 对该问题的一种基于数量属性的关联规则弱比例规则。 在与数量关联规则挖掘的对应问题布尔关联规则挖掘中，考虑布尔关联规则 河南大学硕士研究生学位论文第9 页 挖掘的第二步由频繁项集生成对应满足最小置信度的关联规则，在对关联规 则挖掘的效率影响上，由于关联规则的挖掘中频繁项集产生所需的计算开销远大 于规则的产生所需的开销，所以关联规则挖掘的总体性能由第一步决定，但是对 于关联规则的生成结果问题，在实际的应用过程中，在规则的生成步骤中虽然计 算开销不大，在挖掘过程中只要满足最小阈值一般都认为规则成立，这样有可能 会生成大量的关联规则以致产生“规则爆炸 的问题，这个问题将导致用户分析 规则的效率大大降低，同时大量的规则也浪费存储空间。比如在医疗数据挖掘中 可能会产生数以万计的关联规则，用户若要分析某个病因的结果可能会花费大量 的时间在生成的关联规则中查找这个病因是否会产生某种生病的结果。因此，在 这种情况下并不需要将所有的关联规则生成，只需将其中某些规则表达出来，而 且这些关联规则隐含了其它所有关联规则的信息，从这些关联规则完全可以推导 出其它的规则，这样不但简化了规则的数量，节省了规则的存储空间，而且没有 丢失规则的信息，极大地提高用户的使用效率。挖掘极大布尔关联规则【2 7 】【3 9 1 是解 决这个问题的一种方法。 目前对关联规则生成数量的研究和解决办法包括如下几个方面：用聚类的 方法删除冗余的关联规则 5 7 】；研究基于约束的关联规则挖掘，其中包括知识类 型的约束、数据的约束和兴趣度的约束等【2 0 】；生成关联规则最小预测集3 5 】【5 3 】， 它和关联规则集具有同样的预测功能，而且有发现关键属性的能力；生成极大 布尔关联规则集 2 7 】 2 9 1 ，在有的文献中也称为最小规则集【3 8 】 4 8 1 ，利用极大布尔关联 规则，可以使数据库的关联规则的数量可以在不丢失任何规则信息的前提下被压 缩到最小，被压缩后形成的新的集合中的任何一个关联规则都不能由此集合中另 外某个关联规则通过覆盖运算得到。那些在极大布尔关联规则挖掘中没有被生成 的关联规则可以由生成的极大布尔关联规则集合中的某些关联规则通过覆盖运算 得到。 在频繁项集中，频繁闭项集【4 l 】是支持度比它任何超集支持度都大的频繁项集， 而频繁基项集【38 】是支持度比它任何非空真子集支持度都小的频繁项集。频繁闭项 集和频繁基项集与关联规则有很重要的联系【3 0 】 3 9 】：极大布尔关联规则前件与后件 的并为频繁闭项集；极大布尔关联规则的前件一定是频繁基项集等。文献【3 8 】中提 出了一种基于频繁闭项集和频繁基项集的挖掘最小规则集的算法，但是其中的算 第1 0 页河南大学硕士研究生学位论文 法存在者挖掘出来的规则集有冗余问题，文献【3 9 】为解决文献 3 8 】中的不足，在总 结有关频繁闭项集、频繁基项集和极大布尔关联规则的性质的基础上提出了一种 有效的挖掘极大布尔关联规则集的算法，并在理论上给出详细的证明以及实例解 答过程，但是文献 3 9 】中并没有提出频繁基项集的挖掘算法，而且在极大的生成算 法中对频繁闭项集中的每一项均求幂集，生成了数据库的所有的关联规则，这些 问题影响了极大布尔关联规则的生成效率。针对以上问题本文在第二部分对关联 规则挖掘问题。 1 3 主要研究内容和结构安排 本文的主要研究内容分两部分，是两种特殊的频繁项集的挖掘算法，一个是 基于位置向量和布尔矩阵的最大频繁项集生成算法，另一个是频繁基项集的生成 算法，并且在第二部分中基于频繁基项集和频繁闭项集提出了极大布尔关联规则 的生成算法。 1 3 1 本文的研究内容 在弱比例规则模型中，对于给定的最小支持度m s 和最小置信度m c ，弱比例 规则的一个重要子集s 正好是有限个有限链直积的下集，为了找到这个下集s 的 极大元，论文【2 5 】设计了两个有限个有限链直积下集极大元挖掘算法用于弱比例规 则的挖掘。本文在第二章详细介绍了这两个算法中的一个深度优先算法一 b o u n d a r y 算法，并介绍了b o u n d a r y 算法在硬纸板剪切例方面的一个应用。b o u n d a r y 算法是一个高效深度优先遍历的算法，其可以用在所有满足下集性质的有限个有 限链直积的极大元挖掘中，而频繁项集的幂集格正好是满足这种下集性质的结构， 其最大频繁项集即是此下集的极大元，所以可以使用类似b o u n d a r y 算法的思想来 挖掘最大频繁项集，同时为进行数据集的压缩存储，采用了一种布尔矩阵的数据 集存储方法。基于位置向量和布尔矩阵提出了一种深度优先的最大频繁项集生成 算法g m p v 。 在极大布尔关联规则生成方面，文献【3 9 】提出了一种使用频繁闭项集和频繁基 项集来挖掘极大布尔关联规则的方法，但是文献 3 9 】中并没有提出频繁基项集的挖 掘算法，而且在极大的生成算法中对频繁闭项集中的每一项均求幂集，生成了数 据库的所有的关联规则，这些问题影响了极大布尔关联规则的生成效率，基于以 河南大学硕士研究生学位论文第1 1 页 上问题，本文在第4 章首先提出了频繁基项集的挖掘算法，然后根据极大布尔关 联规则的性质简化了极大布尔关联规则的生成算法。 1 3 2 本文的组织结构 本文的组织结构安排如下： 第1 章是全文的绪论，概述了数据挖掘和关联规则，介绍了本文的研究背景、 研究内容和组织结构。 第2 章对本文中涉及到的关联规则概念问题进行了定义，对弱比例规则模型 的有限个有限链直积下集极大元挖掘算法b o u n d a r y 算法进行了详细分析。 第3 章介绍了事务数据库中项目子集的一种表示方法一位置向量表示方法， 并基于位置向量和布尔矩阵提出了一种深度优先的最大频繁项集生成算法。做了 实验对比。 第4 章根据频繁基项集的性质设计了一个频繁基项集的挖掘算法，并且根据 极大布尔关联规则的性质在文献【3 9 】基础上简化了极大布尔关联规则的生成算法。 在总结和展望部分，给出了全文的总结和进一步的研究方向，最后是致谢和 参考文献。 第1 2 页；- - i 南大学硕士研究生学位论文 第2 章关联规则概念及b o u n d a r y 算法概述 关联规则是数据挖掘的研究热点之一，用于发现隐藏在大型数据集中的令人 感兴趣的联系。购物篮分析是最典型的关联规则挖掘问题，对购物篮数据的分析 有助于指导商场货架的组织、布局和配套穿行路线的设计等。在关联规则挖掘中， 频繁项集的挖掘是重要的步骤，根据频繁项集的模式完全性分，频繁项集又可分 为频繁项集的完全集、频繁闭项集和最大频繁项集，其中频繁项集的完全集包含 频繁闭项集，频繁闭项集又包含最大频繁项集。 在一种数量关联规则模型弱比例规则模型中，b o u n d a r y 算法用来深度优 先的进行下集极大元挖掘，b o u n d a r y 算法沿着下集的边界进行深度优先遍历，是 一种高效的下集极大元挖掘算法。 2 1 关联规则基本概念 设集合，是非空有限集，中的元素事务数据库d 中的项目，即有集合，= f l ， 2 ，i m 是项目的集合，集合d = t l ，t 2 ，岛) 为事务数据库，其中每个事务t j ( = l ，2 ，功包含的项集都是，的子集，即t j _ c l ，有一个唯一的标识符t i d ，用来表 示事务的编号，其中t j 中的元素6 0 = 1 ，2 ，p ) 称为项目( i t e m ) 。若彳是一个项集， 事务t 包含彳当且仅当a f 。 当，= f l 2 ，m 是数据库d 中全体项目组成的集合，则，的任何予集x 称 为d 中的项目集( i t e m s e t ) ，冈表示此子集x 中项目个数且当冈= 七称集合x 为缸项 集。设t k 和x 分别为d 中的事务集和项目集，如果x ，则称事务玖包含项目 集儿 定义2 1 事务数据库d 中包含项集x 的事务数目称项集x 的支持度计数，记 为s u p p o r t _ c o u n t ( x ) 。项集x 的支持度，记做：s u p p o r t ( x ) ，项集x 的支持度和支持 度计数的关系为： s u p p o r t ( x ) ：s u p p o t r t _ i c o u n t ( x ) ( 2 1 ) l i 其中ldi 是数据库d 总的事务数目。 若项集x 的支持度s u p p o r t ( x ) 不小于用户指定的最小支持度阈值m i n _ s u p p o r t ， 河南大学硕士研究生学位论文第1 3 页 则称x 为频繁项集，其中后来频繁项集的研究，频繁项集又被分为闭频繁项集、 极大频繁项集、被约束的频繁项集、近似频繁项集等，当项集x 的支持度小于用 户指定的最小支持度阈值时称x 为非频繁项集。 关于频繁项集有一个著名的先验原理，可以在在频繁项集产生是进行候选剪 枝，该定理如下： 定理2 1 1 4 7 i 先验原理如果一个项集是频繁项集，则它的所有子集也一定是频 繁项集。 由频繁项集及其支持度的定义可知，一个项集的支持度决不会超过它子集的 支持度，这是有支持度度量的反单调性性质决定的，先验原理的另一种表述：如 果一个项集是非频繁的，则它的所有超集也一定是非频繁的。根据先验原理可以 有效的进行频繁项集挖掘候选项集指数搜索空间有效地进行剪枝。 在一般关联规则挖掘过程中，最小支持度阈值r a i ns u p p o r t 由用户或领域专家 指定，而最小支持度计数m i nc o u n t = m i ns u p p o r t x id l 。在事务数据库中挖掘频 繁项集的问题可以描述为：给定事务数据库d 和最小支持度阈值m i n 到所有的频繁项集( f i ) 。 关联规则是形如xjy 的蕴含表达式，其中彳和】，是不相交的项集，即 x n y 矽。其中x 称为规则的前件，y 称为规则的后件，关联规则的前件和后件 都是大于最小支持度阈值的频繁项集。规则的支持度( s u p p o r