（计算机应用技术专业论文）关联规则增量式更新算法的研究.pdf

哈尔滨一 程大学硕士学位论文 摘要 关联规则是数据挖掘研究方向的一个关键技术。自a g r a w a i 引入关联规 则的概念并提出第一个关联规则算法a p r i o r i 算法以来，由于其具有巨大的商 业应用价值和理论研究价值，诸多研究人员对关联规则挖掘算法进行了广泛 的研究并提出了许多新的关联规则挖掘算法。这些关联规则挖掘算法都是在 a g r a w a i 提出的a p r i o r i 算法的基础上不断优化、改进，从而使挖掘的效率不 断提高。 这些经过改进和优化的关联规则挖掘算法虽然各具特点，但同时也存在 着许多不足。除此之外，在关联规则挖掘中还普遍存在两个问题：当挖掘的 数据不断更新时，如何高效即时地获得所需要的结果? 用户在挖掘规则的过 程中需要预先设定一些挖掘参数来获取想要的规则，但这些参数设置往往要 通过多次的调整才能达到预期的目的，那么如何在多次调整中进行高效的计 算呢? 关联规则增量式更新算法正是为了解决以上的问题而提出的。 本文针对第一个问题，通过对一些关联规则增量式更新算法的研究，并 针对f l i p 算法需要多次扫描原数据库、n e w f u p 算法没有考虑后备频繁项 目集的生成代价的缺点，提出了在数据增加情况下，基于后备频繁项目集的 增量式更新算法u m m f u p 算法。并通过实验验证了u m m f u p 算法是有效 的。同时提出了在数据删除情况下基于后备频繁项目集的u m m f u f 2 算法。 并通过试验验证了u m m f u p 2 算法在少量删除数据的情况下，后备频繁项目 集的利用效率会更高，算法会更有效。 关键词：数据挖掘；关联规则；增量式更新；后备频繁项目集 哈尔滨1 二程大学硕十学位论文 a b s t r a c t a s s o c i a t i o nr u l e sh a v eb e e n g a r d e da sav e r y 蛳r t a n t t o p i co f d a t am i n i n g m s e a r e h s i n a g r a w a lp r o p o s e dt h ec o n e , e p to f 鹪s o e i a t i o nn l l 鹤a n dt h ef i r s t 蠲s o e i a t i o nn l l 嚣峨a l g o r i t h m , t h a ti sa p r i 耐，al o to fr e a r c h e r sh a v e b r o a d l yr e s e a r e h e do na p r i o r ia l g o r i t h mb e c a u s ei th a s 嗍m e i a l 、枷u e sa n d 岫r e t i ev a l u e s o nt h i sb a s i s ，m a n yn 唧鹤咖枷r u l e sm i l 血g 蛔f i t h m s 雠 p r o p o s e db yo u t m a i z i n ga n di n l p m v i n ga p f i o f ia l g o f i t h mc c 咀血啪峭l yi no r d e rt o i m p o v e t h ee f f i e i e yo f d a t am i n i n g w h e r e a st h ee e i e so ft h e s ea l g o f i t h m sa e n h a n c e d , 也a er e m a i n s o m ed e f i c i 锄c i 鼯i i lt l l e a l g o f i t h r o _ s i na d d m o mn ma 坞t w op r c v 如t p r o b l e m si na s s o c i 舶nn l l 船m i n i n g ：h o wt oa c q u i r et h e 如s i l t d l s i i l t s e 币c i e n n ya n di m m e d i a t e i yw h e nt h em i n i n gd a mu n a t e sc 0 璐t a | m y ? u s u a l l y ， 甜sn e c e s s a r yt os e t 涨p a r a m e t e r sf o rc l l s l o m c r sb c f 0 豫m i n i n g ，a n dm o s t l y t h e yh a v et 0a d j u s tt 1 1 e s ep a 姗e t e 培m a n yh m 髓t oa e q u i r et h es a t i s f a e t o r yr u l e s ， 也l 膪h o wt 0c a l e u l a l ee 蚯c i e n n yd u r i n gt h er e p e t i t i o mp r o e m s ? mm a i n p u r p o s e f o rp r o p o s i n gm em e r e m 训u l , d a t i 赡a l g o f i t h m si st os o l v et h e p r o b l e m s t os o l v et h ef i r s tp r o b l e m , b a s e do ns o m e 坞9 黜h 船a b o mt h em e r e m 酬 u l x l a t i i l ga l g o f i t h r a s , w i mr e g a r dt ot h ed e t i e i e i e st h a tf u pa l g o r i t h mn e e ds c a n d a t a b a s em a n yt i m e sa n dn e w f u pa l g o r i t h md o e s t 黜i d e rt h ec o s to f p r o d u c i n gt h em o t h b a l lf r e q u e n ti t e ms e t s ，an e wm e r e m e n t a lu p d a t i n ga l g o f i t h m 懈i i l gm o t h b a l lf l q u e n ti t e ms e t s 啊恤c hi 3c a j l e du m m f u pi sp r o p o s e dt ob e u s e di i it h ec 救o f a d d i n gn e wd a t at ot h ed a t a b a s e t h ef e a s i b i l i 锣a n de f f i e i e y o fu m m f u p a l g o r i t h mi sd e m o n s t r a t e dl l s i n g 锄懿p e r i m e n t a tt h es l l n l et i m e ， u m m f u p 2a l g o f i t h mu s i n gm o t h b a l l f r e q u e n ti t e ms e t si sp r o p o s c dt ob e e m p l o y e di nt h ec a s e 池l e t i n gt h ed a t af r o mt h ed a t a b a s e 灿龃c x p c r i m ti s m a d et ov a l i d a t eu m i v l f l r p 2a l g o f i t h m n e 瑚i i l t f l e e t st 1 1 a tt h et i m e so f 坨u s i n gm o t h b a l l 盘c q u e n ti t e ms e t sa 坨m o a n dt h ef e a s i b i l 姆a n de m e i e n e yo f 哈尔滨工程大学硕士学位论文 u m m f u p 2a l g o r i t h mi sb e t t e r 。 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 ；i n c r e m e n t a lu p d a t i n g ；m o t h b a l l f i e q u e n ti t e ms e t s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：至丝丝 日期：纠年二月岁e l 哈尔滨工程大学硕士学位论文 1 1 概述 第1 章绪论 数据挖掘( d a t am i n i n g ) n 一，又称数据库中的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，k d d ) ，数据挖掘通过对大量数据进行分析，获取数 据之间的关系以及其中隐藏的规律、趋势等信息，可以辅助决策者进行决策。 关联规则( a s s o c i a t i o nr u l e s ) n ，挖掘是数据挖掘领域一个重要的研究内容， 其目的就是在事务数据库d 中找出具有用户给定的最小支持度和最小置信度 的关联规则。 关联规则挖掘是a g r a w a l w 等人首先提出的一个重要的k d d 研究课题，其 目的是从交易数据库中挖掘出有潜在价值的关联规则。关联规则自被提出后， 国内外学者对其进行了广泛深入的研究，这些研究主要涉及以下两个方面： 一方面是算法方面，这方面包括新算法的提出和对以往算法缺陷的改进；另 一方面是对关联规则概念的进一步拓宽和延伸。 目前，关联规则的发现问题已经受到许多学者的极大关注，多种快速发 现关联规则的挖掘算法相继被提出，其中尤以a p r i o r i 算法为代表。这些算法 对于静态事务数据库中的关联规则十分有效。然而，在现实世界中，事务数 据库中的数据是随时间的变化而变化的。商业机构中的交易是一个永不问断 的过程，交易行为的模式很可能随着时间的变化呈现出某种新的发展趋势， 使得当前已发现的关联规则可能不再有意义，而可能存在新的、有效的关联 规则还没有被发现。因此，能否有效地挖掘出动态事务数据库中的频繁项目 集和关联规则是衡量一个算法性能好坏的关键。 a g r a w a l 等人在1 9 9 3 年提出的关联规则被数据库界广泛研究，他们提出 的a p r i o r i 算法也在原有算法的基础上得到不断的改进和优化，使关联规则挖 掘的效率有了显著提高。但仍然存在着许多使用这些算法还不能解决的问题： 当挖掘的数据进行不断地更新时，如何高效即时地生成所需要的挖掘结果； 用户需要试探性地预先设定一些固定的挖掘参数，如果参数设置不适当，可 l 哈尔滨工程大学硕士学位论文 能导致响应时问会很长的，并且会产生大量的无用规则等。因此，不仅需要 设计出高效的算法来挖掘出关联规则，同时更需要设计出高效的算法来更新 和维护已经挖掘出的关联规则。 本文正是基于业务数据库不断更新( 数据增加和数据删除的情况) ，对 关联规则增量式更新算法进行研究，并提出了有效的、可行的关联规则增量 式更新算法。 1 2 国内外研究现状 a g r a w a l 等首先提出了关联规则的概念，随后提出了第一个有效的关联 规则挖掘算法a p r i o r i 算法n 。 a p r i o r i 算法以及后来在其基础上进行改进和优化的算法都是基于两个共 同的前提： ( 1 ) 事务数据库中的元组数保持不变； ( 2 ) 最小支持度也固定不变。 然而，在日常的挖掘过程中，数据库中的数据以及挖掘的特定要求更新 频繁的环境下，上述两个前提很难成立。于是研究者们针对以上两个前提不 成立时的情况下，提出了关联规则的增量式更新算法。 在关联规则的实际挖掘过程中，一方面用户往往需要对最小支持度和最 小置信度这两个阈值进行调整来寻找真正感兴趣的和有意义的规则；另一方 面数据库的数据是在不断的被添加、修改和删除，这是一个动态的交互过程。 随着时间的变化，关联规则也需要同步更新。针对上面的两种情况，可以把 关联规则的更新问题归纳为以下4 种情况“一： ( 1 ) 在最小支持度和最小置信度不变的情况下，当数据库d 被添加、 删除或修改时，如何生成更新后的数据库的关联规则； ( 2 ) 在数据库d 不变的情况下，当最小支持度和最小置信度发生变化 时，如何生成d 中的关联规则； ( 3 ) 在最小支持度和最小置信度发生变化的同时，数据库d 也相应地 变化，如何生成更新后的数据库的关联规则； ( 4 ) 在数据库j d 被频繁地进行更新时，如何高效地生成更新后的数据 2 哈尔滨1 = 程大学硕士学位论文 库的关联规则。 所有的关联规则维护问题都可以归结为以上四种情况。对于前两种情况， 许多的国外和国内的研究者已经提出了一些相关的算法，但由于后两种情况 比较复杂，相关的算法还是比较少的。目前也没有形成一种标准的、完善的 维护更新算法。对于第一种情况，d w c h e u n g 等人提出了f u p “，和f u p 2 m 算法。针对第二种情况，冯玉才等人提出了i l j a 和p i u a 算法n 一。由于最小 置信度发生变化时和最小支持度变大时的关联规则的更新问题比较直观， k i a 算法主要考虑的是最小支持度变小时关联规则的高效更新问题。p i u a 算法实际上是将1 u a 算法应用于多处理机并行计算而设计的一种算法。就第 三种情况，高峰等人提出的i u a r 算法n 一提供了一种解决方案，该算法主要考 虑了最小支持度减小时，添加数据集d 时的关联规则的增量式更新问题。对 于第四种情况，d e l l ”算法提供了一种解决方法，它主要运用抽样和统计技 术来判断更新前后的关联规则之间的差异，决定是否应用f u p 2 算法来精确 的计算更新后的关联规则。如果差异足够大，就需要进行更新操作，执行f u p 2 算法来完成关联规则更新；如果差异很小的情况下，并不立即执行f u p 2 算 法，而是把旧的规则作为新规则的近似。d e l l 算法避免了每次都使用f u p 2 算法对不断更新的数据库进行挖掘，这样就有效的解决了算法执行的代价问 题。 在最小支持度和最小置信度不变的情况下，数据库d 被添加、删除时， 如何生成更新后的数据库的关联规则的研究呢? 在这种情况下的增量式更新 问题，首先就应该提到的是f u p 算法。f l i p 算法考虑的是数据库增加数据集 的情况，算法的基本框架和a p r i o r i 算法是一致的，同样是通过多次的迭代产 生频繁项目集。与a p r i o r i 算法不同的是，f l i p 算法利用了已挖掘出的频繁项 目集的信息，避免了重复计算频繁项目集的支持数，从而节省了对频繁项目 集计算时间的开销，因而使算法的运行效率得到了提高。但是f u p 算法在执 行过程中必须多次重复扫描原数据库，对候选项目集进行模式匹配，所以代 价依然很大。为了减少对原数据库的扫描次数，朱玉全等o 一首先提出了后备 频繁项目集的概念，并提出了一种新的关联规则增量式更新算法n e w f u p 算法。n e w f u p 算法通过后备频繁项目集的使用，减少了在算法执行过程中 对原数据库的扫描次数，对算法的执行效率是个提高；但是n e w f u p 算法 3 哈尔滨工程大学硕士学位论文 只是简单的把原数据库的后备频繁项目集作为输入参数，在算法中没有考虑 原数据库的后备频繁项目集的生成代价问题。此外，为了减少对原数据库的扫 描次数，一些改进的算法相继被提出：商志会等m l 提出了改进的f l r p 算法 s f u p 算法，s f u p 算法减少了扫描原数据库的次数；蒙韧等m - 提出了a i u a 算法，a i u a 算法只需扫描原数据库和新增数据库各一次；宋中山等“1 提出了 l i u a 算法，l i u a 算法针对f u p 算法和i u a 算法的缺陷进行了改进。 1 3 本文的组织结构 本文对关联规则增量式更新算法进行了深入的研究。在对f u p 算法和 n e w f u p 算法进行全面研究和细致分析的基础上，提出了基于后备频繁项目 集多次使用、在数据增加的情况下的增量式更新算法u m m f u p 算法和在数 据删除情况下的增量式更新算法u m m f u p 2 算法。 全文共分为4 章： 第l 章对要研究的领域进行了简要介绍，并对国内外的研究现状进行了 阐述，同时提出了本文要研究的方向。 第2 章介绍了数据挖掘的概念、数据挖掘的理论基础、以及数据挖掘技 术的发展方向。重点介绍了关联规则的概念、关联规则的理论基础、关联规 则的发展方向以及对经典的a p r i o r i 算法进行了系统的分析。 第3 章对关联规则增量式更新算法的概念进行了介绍，对关联规则增量 式更新算法的典型算法f u p 算法进行了分析：包括算法的主要思想、具体描 述、以及算法的优缺点，同时本章也对n e w f u p 算法进行了介绍； 第4 章从数据增加和删除的角度提出了基于后备频繁项目集多次使用的 u m m f u p 算法和u m m f u p 2 算法。并分别对算法的基本步骤、算法的描述、 算法的性能等进行了详细地介绍和分析，并通过实验对u m m f u p 算法和 i m 嗍7 l ，2 算法进行了验证。 最后是全文的总结，对本文的研究工作进行了总体的概括，并对本文研 究工作的不足以及未来的研究工作进行了展望。 4 哈尔滨1 = 程大学硕士学位论文 第2 章数据挖掘中的关联规则挖掘 随着数据库技术的迅速发展以及数据库管理系统的应用越来越广泛，商 业数据的积累越来越多。激增的数据背后隐藏着许多有价值的却鲜为人知的 重要信息，经营者们希望能够对数据进行更深层次的分析，以便从中获得更 有价值的信息。数据挖掘技术正是在这样的背景下提出并发展起来的。 2 1 数据挖掘的基本概念 数据挖掘是指从大型数据库或数据仓库中提取出人们感兴趣的知识，这 些知识是隐含着的、事先未知的有用的信息，提取的知识一般可表示为概念 ( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形 式“。在用数据库管理系统存储海量数据时，需要用到机器学习的方法来分 析数据，挖掘包含在大量数据背后的知识，这两者的有机结合就促成了数据 挖掘的产生。数据挖掘是受到各种不同领域研究人员关注的一门交叉性学科， 它涉及到机器学习、模式识别、归纳推理、统计学、数据库、数据可视化、 高性能计算等多个领域。 数据库挖掘这一概念具有两个方面的含义m ：在技术方面上，它是从大量 的、模糊的、随机的实际数据中提取隐含在其中的，人们不可能直观地看到 的重要信息和知识。在商业方面上，人们可以利用数据库挖掘提取辅助商业 决策的关键知识，即从一个数据库中自动发现相关商业模式。数据挖掘是一 类深层次的数据分析，它吸引人的地方就是能够建立预测性模型而不是回顾 性模型。数据挖掘的结果首先必须是事先未知的，并且一定要对决策具有支 持和指导的作用。例如，在对大型超市的日常交易数据进行分析后发现，顾 客购买面包一般也会购买牛奶，如果将这两样商品放在同一货架或相邻货架 上，这样不仅能为客户提供便利，同时也一定会提高面包和牛奶的销售量。 通过数据挖掘技术能够从数据库中挖掘出有价值的、预先未知的知识，并可 以从不同角度展示给用户，从而使大型数据库这种丰富可靠的资源真正达到 为人们所使用。 5 哈尔滨工程大学硕士学位论文 2 2 数据挖掘的理论基础 数据挖掘方法可以是基于数学理论的，也可以是非数学的；可以是演绎 的，也可以是归纳的。从数据挖掘方法研究的历程知，它们是数据库、人工 智能、数理统计、计算机科学以及其它各个相关方面的专家学者以及工程技 术人员，在不断地探讨性研究过程中创立起来的理论体系。1 9 9 7 年，m a n n i l a 对当时流行的数据挖掘的理论框架给出了综述“u 。结合最新的研究成果，有 下面一些重要的理论框架可以帮助大家准确地理解数据挖掘的概念与技术等 特点。 ( 1 ) 模式发现架构 在这种理论框架下，数据挖掘技术被认为是从原数据集中发现知识模式 的过程m 一。通过对机器学习方法的继承和发展，才提出了模式发现架构理论， 同时，该理论也是目前比较流行的数据挖掘研究与系统开发的架构。按照这 种架构，可以针对不同的知识模式的发现过程进行研究工作。目前，数据挖 掘方面的研究人员己经在关联规则、分类模型、聚类模型、序列模式以及决 策树归纳等模式发现的技术与方法上取得了大量的成果。 ( 2 ) 规则发现架构 通过机器学习与数据库技术的综合，a g r a w a l 等将分类、关联及序列这 三类数据挖掘目标作为一个统一的规则发现问题来处理m - 。他们给出了统一 的挖掘模型和规则发现过程中的几个基本运算，这就解决了数据挖掘问题如 何映射到模型和通过基本运算发现规则的问题。这种基于规则发现的数据挖 掘构架也是目前数据挖掘研究领域的常用方法之一。 ( 3 ) 基于概率和统计理论 在这种理论框架下，数据挖掘技术被看作是从大量原数据集中发现随机 变量的概率分布情况的过程n “目前，基于概率和统计理论的方法在数据挖 掘的分类和聚类方面的研究和应用中成果不少。这方面的技术和方法可以看 作是概率和统计理论在机器学习方法中应用的再发展和再提高。统计学作为 一个古老的学科，已经在数据挖掘过程中得到广泛的应用。严格地说，几乎 所有的理论构架都离不开统计方法，统计方法在概念形成、模式匹配以及成 6 哈尔滨工程大学硕士学位论文 份分析等方面都是基础中的基础。 ( 4 ) 微观经济学观点 在这种理论框架下，数据挖掘技术被看作是一个问题的优化过程一。 k l e i n b e r g 等人于1 9 9 8 年建立了在微观经济学框架里判断模式价值的理论体 系。他们认为，如果一个知识模式对一个企业是有效的话，那么它就是有趣 的。有趣的模式发现是一个新的优化问题，可以根据基本的目标函数，对“被 挖掘的数据”的价值提供一个特殊的算法视角，导出优化的企业决策。 ( 5 ) 基于数据压缩理论 在这种理论框架下，数据挖掘技术被看作是对数据的不断压缩过程m 。 按照这种观点，关联规则、决策树、聚类等算法实际上都是对大型数据集的 不断概念化或抽象的压缩过程。 ( 6 ) 基于归纳数据库理论 在这种理论框架下，数据挖掘技术被看作是对数据库的归纳的问题m 一。 一个数据挖掘系统必须具有原始数据库和模式库，数据挖掘的过程就是归纳 数据的查询过程。这种构架也是目前研究者和系统研制者倾向的理论框架之 一o ( 7 ) 可视化数据挖掘 1 9 9 7 年，k e i m 等对可视化数据挖掘的相关技术给出了综述“1 。虽然可视 化数据挖掘必须结合其它技术和方法才有其存在的价值，但是，以可视化数 据处理为中心来实现数据挖掘的交互式过程以及更好地展示挖掘结果等，己 经成为数据挖掘中的一个重要方面。 当然，上面所描述的理论框架并不是孤立的，更不是互斥的。对于特定 的研究和开发领域来说，它们往往是相互交叉各自又有所侧重而已。从上面 的叙述中，也可以看出，数据挖掘的研究是在相关学科充分发展的基础上提 出并不断发展起来的，因此它的概念和理论仍在不断的发展和更新中。 2 3 数据挖掘的发展趋势 数据挖掘语言的设计，高效而有用的数据挖掘方法的设计和系统的开发， 交互和集成的数据挖掘环境的建立，以及应用数据挖掘技术来解决大型的商 ， 哈尔滨工程大学硕士学位论文 业应用问题，都是目i ；i 的研究和开发热点，下面描述的是一些数据挖掘的应 用趋势： ( 1 ) 应用的探索：数据挖掘的应用在早期主要是为了帮助企业提升自身 竞争力，随着数据挖掘的逐渐普及以及数据挖掘技术的日益成熟，数据挖掘 也被应用到其它范围，如生物医学、金融和电信等领域。随着电子商务和电 子市场逐渐成为零售业的主流因素，数据挖掘也在不断扩展其在商业领域的 应用方向* ”。 ( 2 ) 可伸缩的数据挖掘方法：与传统的数据分析方法相比，数据挖掘必 须能够有效地处理大量的数据，并尽可能是交互式的；由于数据量是在不断 的增加过程中，因此针对单独的和集成的数据挖掘系统的可伸缩算法显得十 分重要。一个重要的方向是基于约束的挖掘，它致力于在增加用户交互的同 时如何改进挖掘过程的总体效率。 ( 3 ) 数据挖掘与数据库系统、数据仓库和w c b 数据库系统的集成：数 据挖掘系统的理想体系是与数据库和数据仓库的紧密耦合。事务处理、查询 处理、联机分析处理和联机分析挖掘应集成在一个统一框架中，这将保证数 据的可获得性，数据挖掘的可移植性，可伸缩性，同时具有良好的性能，以 及形成对多维数据分析和探查的集成信息处理环境。 ( 4 ) 数据挖掘语言的标准化：数据挖掘语言的标准化或其它方面的标准 化研究工作将有助于数据挖掘的系统化开发，提高数据挖掘系统和功能间的 相互操作性，有利于数据挖掘系统在企业和社会中的推广和应用。 ( 5 ) 可视化数据挖掘：可视化数据挖掘是从大量数据中发现未知知识的 直观和有效的途径。数据挖掘的系统化研究和可视化挖掘技术将有助于推进 数据挖掘早日成为数据分析的基本工具。 ( 6 ) 复杂数据类型挖掘的新方法：复杂数据类型挖掘是数据挖掘中一项 重要的前沿研究课题，虽然在地理空间挖掘、多媒体挖掘、时序挖掘、序列 挖掘以及文本挖掘方面取得了一些进展，但它们与实际应用的距离依然相差 很远。对此需要进一步的研究，尤其是针对上述数据类型的现存数据分析技 术与数据挖掘方法集成起来的研究。 ( 7 ) w e b 挖掘：由于w e b 上存在大量信息，并且w e b 在当今社会扮演 着重要的角色，有关w 曲内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服 矗 哈尔滨工程大学硕士学位论文 务，将成为数据挖掘中一个最为重要的子领域。 ( 8 ) 数据挖掘中的隐私保护与信息安全：随着数据挖掘工具和电信与计 算机网络的日益普及，数据挖掘面对的一个重要问题是隐私保护和信息安全。 需要进一步开发有关方法，以便在适当的信息访问和挖掘过程中确保隐私保 护与信息安全。 2 4 关联规则的基本概念 关联规则( a s s o c i a t i o nr u l e s ) 是数据挖掘领域研究的一个重要课题。关 联规则挖掘是发现交易( t r a n s a c t i o n ) 数据库中不同项( 集) 之问有趣的关 联或相关关系。关联规则挖掘自1 9 9 3 年a g r a w a l 等人提出后己被数据库界广 泛研究，1 9 9 4 年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 算法有显著提高。 关联规则的挖掘问题可以做如下的形式化描述m ，：设卢 f j ，如，k 是项的集合。任务相关的数据d 是数据库事务的集合，其中每个事务r 是项 的集合，使得r j 。每一个事务有一个标识符，称作t i d 。项的集合称为项 目集( i t e ms e t ) 。设a 是一个项目集，事务r 包含彳当且仅当彳童r 。如果 项目集彳中包含k 个项，则称为卜项目集。关联规则是形如a j b 的蕴涵式， 其中a c i ，b c i ，并且a m b = 磊规则a j b 在事务集d 中成立并且具 有支持度s ，j 是d 中事务包含4 u 口的百分比，它的概率表示为p ( a u 口1 。 如果d 中包含彳的事务同时也包含丑的事务的百分比是c ，则规则a j b 在 事务集d 中具有置信度c ，它是条件概率e ( b i a ) 。也就是 5 u p p o r t ( a j b ) = p t a u b ) c o n f i d e n c e ( 4 研= p ( 曰i 彳) 支持度和置信度两个阈值是描述关联规则的两个重要概念，支持度反映 的是关联规则在数据库中的重要性，表示规则出现的频度；置信度衡量关联 规则的可信程度，表示规则的强度。同时满足最小支持度阚值和最小置信度 阚值的规则称为强关联规则。为了方便，将最小支持度阈值记为r a i n ，sup 9 哈尔滨工程大学硕七学位论文 最小置信度闽值记为m i nc o n f 最小支持度表示项目集在统计意义上的最低 重要性，最小置信度表示规则的最低可靠性。 一个项目集的出现频度是指整个交易数据集d 中包含该项目集的交易记 录数，也称为是该项目集的支持度。如果项目集的出现频度大于或等于最小 支持度阈值m i n _ s u p 与d 中事务总数的乘积，则称项目集满足最小支持度。 如果一个项目集a 满足最小支持度( s u p p o r t ( a ) m n)，则称它为频繁_sup 项目集，频繁卜项目集的集合记为厶。反之，如果一个项目集一不满足最小 支持度，则称为非频繁项目集。 候选项目集是潜在的频繁项目集的集合，是频繁( k - 1 ) 一项目集的超集。 含有k 项的候选项目集记为g ，由它构成频繁卜项目集厶。 挖掘关联规则问题可以分解为以下两个问题：( 1 ) 找出存在于事务数据 库中的所有频繁项目集；( 2 ) 利用频繁项目集生成关联规则。根据定义，这 些规则必须满足最小支持度和最小置信度。对于每个频繁项目集彳，若b c a ， 口勃且 s u p p o r r _ c o u n t ( a ) m i nc o n t s u p p o r t c o u r t ( b ) 一 则生成关联规则b j ( a b ) 。 问题( 1 ) 是近年来关联规则挖掘算法研究的重点。比较流行的方法是基 于a g r a w a l 等人建立的项目集格空间理论。这个理论的核心是；频繁项目集 的子集是频繁项目集；非频繁项目集的超集是非频繁项目集。由于问题( 2 ) 中的相应操作极为简单，因此挖掘关联规则的总体性能由问题( 1 ) 决定。 2 5 关联规则的理论基础 文献【2 9 】给出了关联规则和图论之间的联系，这有利于对关联规则的作 进一步的研究。 文献 3 0 1 也给出关联规则中项目集与数学中的格、不动点以及概念格之 间的联系：( 1 ) 挖掘所有频繁项目集就相当于在项目集格上挖掘具有支持度 约束的所有结点的集合；( 2 ) 闭项目集就是关联关系中一个伽罗瓦闭算子的 不动点，挖掘所有频繁闭项目集就相当于在闭项目集格上挖掘具有支持度约 1 0 哈尔滨下程大学硕士学位论文 束的所有结点的集合：( 3 ) 关联关系中一个概念的内涵就是一个闭项目集。 而且关联关系的概念格上的每一个概念的内涵的支持度都是由其外延所确 定，关联关系的概念格不仅保留了闭项目集的信息，也同时保留了闭项目集 的支持度的信息。这样，挖掘所有的频繁闭项目集就相当于在这个概念格上 挖掘所有外延满足约束的概念。 由这些结果可知，关联规则虽然是来源于实际的应用，但它却有着深厚 的理论基础，这为它今后的继续发展提供了有力的理论依据和保障。另外， 也为今后能把图论、格、不动点或者概念格等数学中的一些理论成果应用到 关联规则中起到了一个指导作用。 2 6 关联规则的主要研究方向及其算法 a g r a w a l 等人提出了关联规则的挖掘问题后，该问题的研究得到了长足 地发展。到目前为止，其主要的研究方向有： ( 1 ) 多循环方式的挖掘算法 此类算法包括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 l 算法m ，p a r k 等人提出的d h p 算法，s a b a s e r e 等人的 p a r t i t i o n 算法m 似及t o i v o n e n 提出的抽样算法s a m p l i n g m ，等等。其中最有 效和最有影响的算法为：a p n o d 算法、d h p 算法和p a r t i t i o n 算法。 ( 2 ) 增量式更新算法 关联规则的增量式更新问题主要归纳为4 种情况，详见第1 章。 ( 3 ) 并行发现算法 目前已经提出的并行挖掘关联规则的算法有：a g r a w a l 等人提出的c d ( c o u n td i s t r i b u t i o n ) 算法、c a d ( c a n d i d a t ed i s t r i b u t i o n ) 算法、i d d ( i n t e l l i g e n t d a t a d i s t r i b u t i o n ) 算法w ，p a r k 等人提出的p d m 算法，c h u e n g 等人提出的 d m a 算法1 和f d m 算法w 虽然是基于分布式数据库的挖掘算法，但也可适 用于并行挖掘。 ( 4 ) 挖掘多层关联规则 在挖掘关联规则的研究过程中，许多研究人员发现在一些现实的应用中， 由于数据量相对比较少，要想在原有的概念层次上发现出强的( s t r o n g ) 和 哈尔滨丁程大学硕十学位论文 有趣的( i n t e r e s t i n g ) 关联规则是比较困难的，因为好多项目集通常没有足够 的支持数。由于概念层次在数据库的挖掘过程中是经常存在的，通常称高层 次的项是低层次项的父亲，通常用一个有向非循环图来表示这种概念层次关 系。于是就可以在较高的概念层次上发现关联规则。基于要挖掘的数据库中 的概念层次和单一概念层次中的关联规则算法，许多学者提出了高效发现多 层次关联规则的算法，主要有：l - i a n 等人的m l2 l 1 1 算法及其变种m lt i l a 算法，m lt m l l 算法、m lt 2 l a 算法和r s r i k a n t 等人的c u m u l a t e 算法， s t r a t i f y 算法及其变种e s t i m a t e 算法、e s t m e r g e 算法m ，等。 ( 5 ) 挖掘多值属性关联规则 关联规则可分为布尔型关联规则和多值属性关联规则。多值属性又可进 一步分为数量属性和类别属性。在文献1 1 4 中，多值属性关联规则挖掘问题 首先被提出。目前，已经提出的用于挖掘多值属性关联规则的算法大多是将 多值数据项关联规则挖掘问题转换为布尔型关联规则挖掘问题，即将多值属 性的值划分为许多个区间，每个区间就算作一个单一属性，将类别属性的每 一个类别也当作一个属性。 ( 6 ) 基于约束的关联规则挖掘 基于约束的关联规则挖掘的主要目的是发现更加有趣的、更加实用的和 相对更特别的关联规则，这种研究主要是允许用户指定他所感兴趣的关联规 则的集合，这种约束不仅可以用来对事务数据库进行预加工处理，而且还可 以把这种约束集成到特定挖掘算法的内部，以此来提高算法的执行效率。基 于约束的关联规则挖掘算法主要有以下几种：m u l t i # e j o i n s 算法、r e c o r d e r 算法，d i r e c t 算法和c a p 算法。文献【3 9 】提出的是多层约束关联规则算法。 陈晓云1 在基于约束的关联规则挖掘也有一定的研究。 ( 7 ) 其它方向 除了以上列出的对关联规则的常见研究方向外，还有其它一些研究方向， 如：发现关联规则的语言n “、挖掘长模式和密集数据集、挖掘相关性和因果 关系发现比例规则、挖掘多维关联规则等等。 哈尔滨工程大学硕士学位论文 2 7 经典的a p ri o r i 算法 1 9 9 4 年，a g r a w a l 等在先前工作的基础上，完善了一个称为a p r i o r i 的关 联规则挖掘算法。这个算法一直作为经典的关联规则挖掘算法被引用。它是 最为典型的一种层次算法，其核心技术被其它各类布尔关联规则挖掘算法所 广泛采用。 2 7 1a p r i o r i 算法 a p r i o r i 算法是通过项目集元素数目不断增长来逐步完成频繁项目集发现 的。首先产生卜频繁项目集l ，然后产生2 - 频繁项目集如，直到不能再扩 展频繁项目集的元素数目而算法停止。在第k 次循环中，先产生卜候选项目 集的集合a ，然后通过扫描数据库生成支持度并测试产生卜频繁项目集厶。 a p r i o r i 算法在第一次迭代时，直接构成候选卜项目集c i 。算法在第k 次迭代时，先根据上一次迭代过程中找到的频繁项目集t ，产生本次迭代的 候选项目集g 。然后依次扫描数据库d 中的事务，确定包含在每条事务中且 属于q 的项目集。当所有事务都扫描完成之后，即可得到q 中各项目集的 支持度。再根据d 和给定的最小支持度确定q 中的频繁项目集。重复上述 过程直到没有新的频繁项目集产生为止。 a p r i o r i 算法中有两个关键步骤：连接步和剪枝步。 ( 1 ) 连接步；为找出l i ( 频繁卜项目集) ，通过k l 与自身连接 ( 厶一d 日丘。) 产生候选卜项目集，该候选项目集记作g ( 其中，上蜘中的 元素是可连接的) 。 ( 2 ) 剪枝步：o 是厶的超集，即它的成员可以是频繁的也可以是不频 繁的，但所有的频繁卜项目集都包含在q 中。扫描数据库，确定q 中每一 个候选的计数，从而确定厶。然而，q 可能很大，这样所涉及的计算量就很 大。为压缩g ，使用a p r i o r i 性质：任何非频繁的( k - 1 ) 一项目集都不可能是 频繁卜项目集的子集。因此，如果一个候选卜项目集的( k - i ) 一项目集的子 集不在三“中，则该候选项目集也不可能是频繁的，从而可以从g 中删除。 一旦从数据库d 中的事务中找出频繁集，就可以由它们产生关联规则。 哈尔滨工程大学硕十学位论文 2 7 2a p r i o r i 算法分析 1 p r i o f i 算法的性能瓶颈 p ri o r ；算法有两个致命的性能瓶颈：第一个就是需要多次扫描事务数 据库，需要很大的f o 负载。对每次k 循环，候选项目集g 中的每个元素都 必须通过扫描数据库一次来验证其是否加入厶。另一个是可能产生庞大的候 选项目集。由如l 产生| | 卜候选项目集q 是指数增长的，如此大的候选项目集 对时间和主存空间都是一种挑战。 2 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 算法产生频繁项目集并生成关联规则这两项工作必须针对增加 新数据后的数据库重新做起，这就意味着以前生成的频繁项目集和关联规则 都没有用了，这样显然不利于快速高效地发现关联规则。再有就是当数据库 的规模超出主存的限定容量时，a p r i o r i 算法就无法使用了，相对于以后的各 种算法，a p r i o r i 算法的效率相对来说是最低的。 2 7 3a p r i o r i 算法的几种优化方法 虽然a p r i o r i 算法自身已经进行了一定的优化，但是在实际的应用中，还 是存在不令人满意的地方，于是人们相继提出了一些优化的方法，文献 4 2 - 4 5 】 是国内的研究人员对a p r i o r i 算法提出的改进算法。 ( 1 ) 基于划分的方法：s a v a s e r e 等m ，设计了一个基于划分( p a n i t i o n ) 的算 法，这个算法在逻辑上首先把数据库分成几个互不相交的数据块，每次单独 考虑每一个分块并对它生成所有的频繁项目集，然后把产生后的频繁项目集 进行合并，用来生成所有可能的频繁项目集，最后再计算这些项目集的具体 支持度。这里分块大小的选择要使得每个分块都可以被调进主存，每个阶段 必须保证只被扫描一次。每一个可能的频繁项目集至少在某一个分块中是频 1 4 哈尔滨 ：程大学硕士学位论文 繁项目集，这就保证了算法的正确性。上面所讨论的算法同时也可以高度并 行，可以把每一分块分别分配给不同的处理器来生成频繁项目集。产生频繁 项目集的每一个循环完成后，处理器之间进行通信来产生全局的候选卜项目 集。通常这里的通信过程是算法性能的主要瓶颈；而另一方面，每个独立的 处理器生成频繁项目集的时间有可能不一致，所以这也是一个性能瓶颈。 ( 2 ) 基于h a s h 的方法：p a r k “等提出来了一个基于杂凑( h a s h ) 的高效 地产生频繁项目集的的算法。通过实验可以发现生成频繁2 一项目集厶是寻找 频繁项目集主要计算所在，p a r k 等就是利用了这个性质并引入了杂凑技术来 改进产生频繁2 一项目集计算量的方法。 ( 3 ) 基于采样的方法；通过利用前一遍扫描得到的结果，并对此仔细地 作组合分析，可以得到一个改进的算法。m a n n i l a t w 等首先考虑了这点，并 认为采样是发现规则的一个有效途径。随后t o i v o n e n t “进一步发展了这个思 想，通过先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成 立的规则，然后对数据库的剩余部分验证这个采样中获得的结果。t o i v o n e n 的算法相对简单并显著地减少了i o 的代