（计算机应用技术专业论文）保护隐私的关联规则挖掘研究.pdf

保护隐私的关联规则挖掘研究 摘要 随着信息技术，特别是网络技术、数据存储技术和高性能处理器技术的飞速发展， 海量数据的收集、管理和分析变得越来越方便，知识发现和数据挖掘更是在一些深层次 的应用中发挥了积极的作用。任何事情都有其两面性，数据挖掘领域也不例外，随之产 生的是信息安全和保护隐私的问题。所以，如何在保证信息隐私的情况下挖掘出有用信 息已经成为目前数据挖掘界的一个研究热点。 本文首先从数据分布方式、数据修改方式等角度，对当前流行的保护隐私数据挖掘 算法进行了深入浅出的介绍和分析。重点介绍了m a s k 、i 沁h 、p a r d 三种保护隐私 的关联规则挖掘方法。通过分析它们的缺点和不足，提出一种新颖的保护隐私关联规则 挖掘方法一基于转移概率矩阵的部分随机化回答( p a r t i a lr a n d o m i z e dr e s p o n s eb a s e d o n p r o b a b i l i t ym a t r i x ，简称p r r p m ) 方法。 为了在保护隐私的同时能够准确、高效地进行关联规则挖掘，p r r p m 方法在进行 频繁1 项集和频繁k 项集( k 1 ) 挖掘时分别采用不同的数据转换策略。在挖掘频繁1 项 集时，先使用“属性转移概率矩阵”对每个属性进行部分转换，然后提出一种方法恢复 1 项集在原数据集中的支持度，以便找出数据集中的所有频繁1 项集；而在挖掘频繁k 项集( k 1 ) 时，要先使用“多项集转移概率矩阵 对所有的候选频繁k 项集进行部分转 换，然后提出一种方法恢复候选频繁k - 项集在原数据集中的支持度，以便找出所有的频 繁k 项集。 理论分析和实验验证表明，本文提出的p r r p m 方法比r r p h 和m a s k 方法在隐 私性、准确性、复杂度方面更具有优势。 关键词：属性转移概率矩阵；多项集转移概率矩阵；部分随机化；保护隐私；关联规则； 大连交通大学t 学硕十学位论文 a b s t r a c t w i t ht h er a p i d l yd e v e l o p i n go fi n f o r m a t i o n t e c h n o l o g i e s ，e s p e c i a l l yo fn e t w o r k t e c h n o l o g y ，d a t as t o r a g et e c h n o l o g ya n dh i g hc a p a b i l i t yp r o c e s s o rt e c h n o l o g y ，i ti sm o r ea n d m o r ec o n v e n i e n tt oc o l l e c t ，m a n a g ea n da n a l y s em a s s i v ed a t a k n o w l e d g ed i s c o v e r ya n d d a t am i n i n gh a v em o r ep o s i t i v ee f f e c ti nd e e pa p p l i c a t i o n ，b u te v e r yc o i nh a st w os i d e sa n d d a t am i n i n gi sn o te x c e p t i o n a l i n f o r m a t i o ns e c u r i t ya n dp r i v a c yp r e s e r v i n gb r i n g u p 、析t 1 1t h e d e v e l o p m e n to fd a t am i n i n g s o ，h o wt om i n eu s e f u la n de x a c ti n f o r m a t i o no nt h ep r i v a c y p r e s e r v i n gi sb e c o m i n gh o t s p o ti nd a t am i n i n gf i e l da tp r e s e n t f i r s t l y ，t h ec u r r e n tp r i v a c yp r e s e r v i n gd a t am i n i n ga l g o r i t h m sa r ei n t r o d u c e da n d a n a l y s e d ，a s d a t a d i s t r i b u t i n gm e t h o d ，d a t am o d i f y i n gm e t h o de t c s e c o n d l y ，t h r e e p r i v a c y p r e s e r v i n ga s s o c i a t i o nr u l e sm i n i n gm e t h o d sm a s k ，r r p ha n dp a r da r ei m p o r t a n t t oi n t r o d u c e f i n a l l l y ，an e wp r i v a c y p r e s e r v i n ga s s o c i a t i o nr u l e sm i n i n gm e t h o d ( p r r p m ) i s p r o p o s e di nt h i sp a p e r , w h i c hi san o v e lp a r t i a lr a n d o m i z e dr e s p o n s em e t h o db a s e do n p r o b a b i l i t ym a t r i x p r r p mm e t h o dc h o o s e sd i f f e r e n td a t at r a n s i t i o ns t r a t e g i e st of i n df r e q u e n t1 - i t e m s e t s a n df r e q u e n tk - i t e m s e t s ( k 1 ) i no r d e rt om i n ea s s o c i a t i o nr u l e sa c c u r a t e l ya n de f f i c i e n t l y w h i l ep r e s e r v i n gp r i v a c y w h e nm i n i n gf r e q u e n t1 - i t e m s e t s ，an e wm e t h o di sp r e s e n t e dt o r e c o v et h es u p p o r to ff r e q u e n t1 - i t e m s e t si no r i g i n a ld a t as e tt of i n da l l f r e q u e n t1 - i t e m s e t s a f t e rt r a n s f o r m i n ge v e r ya t t r i b u t ep a r t i a l l yw i m1 - i t e m s e t st r a n s i t i o np r o b a b i l i t ym a t r i x ；w h e n m i n i n gf r e q u e n tk - i t e m s e t s ( k 1 ) ，as a m em e t h o di sp r e s e n t e dt or e c o v e rt h es u p p o r to f c a n d i d a t ef r e q u e n tk - i t e m s e t s ( k 1 ) i no r i g i n a ld a t as e tt of i n da l lf r e q u e n tk - i t e m s e t s ( k 1 ) a f t e rt r a n s f o r m i n ge v e r yc a n d i d a t ef r e q u e n tk - i t e m s e t s ( k 1 ) p a r t i a l l y 谢t l lm u l t i i t e m s e t t r a n s i t i o np r o b a b i l i t ym a t r i x t h e o r ya n a l y s i sa n de x p e r i m e n t ss h o wt h a tt h ep r r p mm e t h o di se f f e c t i v e l ya n db e t t e r t h a nt h o s eo fm a s ka n dr r p hi nt h ep r i v a c y ，a c c u r a c ya n dc o m p l e x i t y k e yw o r d s ：a t t r i b u t et r a n s i t i o np r o b i l i t ym a t r i x ：m u l t i - i t e m s e tt r a n s i t i o np r o b i l i t y m a t r i x ；p a r t i a lr a n d o m i z e dr e s p o n s e ；p r i v a c yp r e s e r v i n g ；a s s o c i a t i o n r u l e s i l 第一章绪论 第一章绪论弟一早瑁了匕 1 1 研究背景 随着信息技术，特别是网络技术、数据存储技术和高性能处理器技术的飞速发展， 海量数据的收集、管理和分析变得越来越方便，知识发现和数据挖掘更是在一些深层次 的应用中发挥了积极的作用。但与此同时，也带来了隐私方面的诸多问题。例如，通过 对医院病人的病历数据进行挖掘，可以发现各种疾病之间的关联。在使用一般方法进行 挖掘的过程中，不可避免地会使病例数据暴露，从而造成病人隐私的泄露。还有治安系 统中的违法记录、保险公司的理赔情况、银行卡客户的交易行为等信息中的关联关系， 都对政府和企业决策具有相当重要的意义，但同时又都是公民非常重视的个人隐私。所 以，如何在数据挖掘过程中解决好隐私问题( 如何在保护隐私的情况下挖掘出有用信息) 目前已经成为数据挖掘界研究的一个热点。 数据挖掘( d a t am i n n i n g 简称d m ) 是知识发现( 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 s ， 简称k d d ) 的一个阶段，是从大型数据库中提取人们感兴趣的知识，这些知识是隐含的、 事先未知的、潜在的有用信息，提取的知识表示为概念、规则、规律、模式等形式。数 据挖掘要处理的问题，就是在庞大的数据库中寻找有价值的隐藏事件，加以分析，并将 这些有意义的信息归纳成结构模式，供给有关部门决策时参考。常用的方法有关联规则、 决策树、聚类、神经网络等方法。挖掘出正确有用的信息可以为企业带来可观的经济利 益，可是只有在正确真实的数据中才能挖掘出真正有用的信息，真正为企业带来利润， 但是在现实生活中是不现实的。为了保护数据的隐私，人们不愿提供正确的信息给服务 商；企业也不愿把自己的真实数据给挖掘人员以免泄露企业机密。因此，要想挖掘出正 确有用的信息必须考虑隐私保护的问题。 隐私保护是数据挖掘领域研究的一个新热点。隐私在不同的应用环境下有不同的解 释。数据挖掘过程中所涉及的隐私一般指的是用户的基本信息( 如姓名、年龄、家庭住 址等) 或用户某些行为产生的信息( 如购物信息、医疗信息、网页浏览信息等，这些信息 有意或无意的泄露可能会给用户带来麻烦) 。例如，医疗公司希望客户泄露所患疾病目 的是了解疾病之间相关性，而客户担心是自己隐私( 姓名、病史等) 的泄露是否会影响就 业。在分布式数据挖掘中，参与的各方有各自的数据，通过合作进行挖掘的过程中，各 方都不想让其他方访问或者得到自己的数据。因此，保护隐私的数据挖掘是一项非常有 意义的工作。 大连交通大学t 学硕十学位论文 1 2 国内外研究现状 在1 9 9 5 年召开的第一届k d d 上，隐私保护的数据挖掘就成为了一个专门的研究主 题。1 9 9 9 年r a k e s ha g r a w a l 在k d d 9 9 上作了一个非常精彩的主题演讲，将隐私保护的 数据挖掘作为未来的研究重点之一。自此之后，隐私保护的数据挖掘就越来越受到人们 的重视，迅速成为近年来数据挖掘领域研究的热点之一。各种新技术和新方法层出不穷， 各种方法都有其特点下面首先介绍各种隐私保护技术。 1 2 1 隐私保护技术的分类 下面分别从数据的分布方式、数据的修改方式、数据挖掘算法、保护对象以及隐私 保持五个角度对保护隐私的数据挖掘算法进行归纳【h j 。 ( 1 ) 数据分布方式 根据数据分布方式，隐私保护技术可以分为针对集中式数据的隐私保护技术和针对 分布式数据的隐私保护技术。分布式的隐私保护技术又分为数据水平分割的隐私保护技 术和数据垂直分割的隐私保护技术。数据的水平分割主要原因是多个机构或组织对于不 同的个体收集了相似的信息；数据的垂直分割主要原因是多个机构或组织收集了同样的 个体的不同信息。 ( 2 ) 数据修改方式 主要将数据库中的某些敏感信息作一定的修改以确保原来数据库中的隐私信息不 被泄露。常用的方案主要有如下几种：值替代方法，就是用一个新的值替代原有的值； 分组方法，就是用一个问号替代一个己存在的属性值；交换方法，就是单个记录间值的 交换；取样方法，主要指的是用于挖掘的数据只是总样本中的一个样本。 ( 3 ) 数据挖掘算法 在现阶段，数据隐藏技术都是在每一个数据挖掘算法中单独考虑。例如：决策树算 法、关联规则算法、粗糙集以及贝叶斯网络等数据挖掘算法中已经有了许多保护隐私的 重要思想。v s v e r y k i o s 等提出了研究组合数据挖掘算法中的数据隐藏技术，即将两个 或更多的数据挖掘算法合并，在这些组合的数据挖掘算法中研究数据隐藏技术。 ( 4 ) 保护对象 数据挖掘过程中的隐私保护可分为对初始的用户数据隐私保护( 输入保护) 和对挖掘 结果的隐私保护( 输出保护或称规则保护) 。数据隐私保护主要是指基本的原始数据集成 的数据是否被隐藏。想要隐藏以规则形式存在的集成数据，复杂度较高，正因为如此， 学者们提出了各种启发式( h e u r i s t i c s ) 方法。公共信息暴露的越少，数据挖推断精度会越 低，但同时数据的安全性得到了一定程度的保障。 2 第一章绪论 ( 5 ) 隐私保持 隐私保持是一种最重要的隐私保护技术，它的主要特点是有选择性地修改原始数 据。这种修改能使隐私在不受危害的情况下获得较高的技术实用性。实用性大小主要体 现在使用隐私保护技术以后有用信息的丢失量大小。隐私保持技术主要有三种：基于探 索式的隐私保持技术、基于密码学的隐私保持技术和基于重构的隐私保持技术。 1 2 2 隐私保护技术的评估标准 对隐私保护技术的评估，最重要的工作就是要建立合适的评估标准。笔者在阅读有 关文献后得出：在实际的应用中，不可能用一个统一标准来衡量所使用的隐私保护技术， 而只能说一种隐私保护技术可能在某一个特定应用中在某个标准上比其它隐私保护技 术好。因而，应该向用户提供一套度量准则，让用户能根据自己的需要选择最合适的隐 私保护技术。通常，隐私保护技术的评价指标有： ( 1 ) 隐私性 这是保护隐私的基本原则，保护隐私方法必须能够保证在进行数据挖掘时不泄露隐 私数据和敏感规则。 ( 2 ) 准确性 为达到保护隐私的目的，在进行数据挖掘时首先要对隐私数据和敏感规则进行隐藏 和变换，这样势必会造成规则的丢失和误生成，即准确性下降。一个有效的解决方案应 该能够在隐私性和准确性之间找到平衡。 ( 3 ) 适用性 隐私保护技术的适用性主要包括两个方面：对属性类型的适用性和对数据挖掘方法 的适用性。一个好的隐私保护技术应该能够处理各种不同的属性类型，如布尔型属性、 分类属性等。一个理想的、保护隐私的数据挖掘方法也应该是独立于各种各样的数据挖 掘方法。 ( 4 ) 多功能性 一个多功能的隐私保护技术应该能够应用在不同的数据源分布，它不但可以用在集 中式数据库上，也可以用在分布式数据库上。 ( 5 ) 通信代价 当数据是分布在不同的站点时，隐私保护技术应该考虑各个站点之间的通信代价。 1 3 本文所做工作及创新点 在上述背景下，本文主要对保护隐私的关联规则方法进行了研究，本文的内容主要 有： 大连交通大学t 学硕十学位论文 ( 1 ) 提出p r r p m 方法 首先，通过对当前主流隐私保护的关联规则挖掘方法进行分析提出p r r p m 方法； 然后，通过分析挖掘频繁1 项集和频繁k 项集时所采用的数据转换策略，给出相应支持 度的恢复方法，并在此基础上给出了p r r p m 的总体架构、完整的数据转换和挖掘步骤 及算法伪代码。 ( 2 ) 证明p r r p m 的有效性 为了说明p r r p m 的有效性，本文首先给出了其隐私性评价指标和准确性衡量公式， 并在此基础上证明在参数选择合理时p r r p m 的隐私性和准确性要比m a s k 和r r p h 的高；通过实验说明p r r p m 不仅适用于布尔属性也适用于分类属性和离散化数据类型， 并且其准确性和隐私性没有因此而受到影响。 1 4 论文组织结构 本文按以下方式进行组织： 第一章绪论 首先介绍本课题的研究背景，然后分别从数据的分布方式、数据的修改方式、数据 挖掘算法、保护隐私的对象以及隐私保持五个角度对国内外研究的保护隐私的数据挖掘 算法进行归纳，并列出了隐私保护技术各种评估标准。最后，介绍本文所做的工作和论 文组织结构。 第二章关联规则概念与常用方法 首先介绍关联规则基本的概念与性质，然后对关联规则进行分类，接着重点介绍 a p r i o r i 算法、f p g r o w t h 算法和基于图的关联规则挖掘算法并分析它们的优缺点。最后， 介绍了目前关联规则主要研究的问题。 第三章保护隐私方法研究综述 首先，根据数据分布方式、数据修改方式、数据挖掘算法、保护隐私对象和隐私保 护技术对典型的保护隐私算法进行归类；然后，重点介绍m a s k 、r r p h 和p a r d 等保 护隐私的关联规则挖掘方法并分析它们的优缺点。 第四章保护隐私的关联规则挖掘 首先，通过对当前主流保护隐私的关联规则挖掘方法的缺点和不足，提出基于转移 概率矩阵的部分随机化回答方法( p r r p m ) ；然后简单介绍了相关概念和性质并在此基础 上分别给出了恢复支持度的方法、p r r p m 的总体架构、完整挖掘步骤及算法伪代码； 最后通过分析和比较，说明p r r p m 方法在隐私性、准确性、适用性方面都要比m a s k 方法和r r p h 方法要好。 4 第一章绪论 第五章实验 通过实验分析说明p r r p m 方法比r r p h 方法和m a s k 方法不仅实用性较好，而 且准确性也比后两者高。 总结 对本文工作的总结和对未来工作的展望。 大连交通大学工学硕士学位论文 第二章关联规则概念与常用算法 关联规则概念首先由a g r a w a l 等在1 9 9 3 年提出，是数据挖掘领域中一个最基本、 最重要的问题，近几年被广泛研究。关联规则最初定义在一组布尔型记录组成的事务数 据库之上，每个记录包含了事务项出现与否的信息，描述了不同商品购买行为之间的关 系。关联规则在客户购物篮分析、文本文档词频分析、股票事务分析、网页访问日志推 断模式和网络入侵检测等方面得到了广泛的应用。关联规则挖掘的基本问题就是研究事 务数据库中事务项出现之间的关系，找出具有用户给定的最小支持度和最小置信度的关 联规则，其中频繁项集的挖掘又是最基本的问题。 本章将介绍关联规则的基本概念、性质及常用算法。 2 1 关联规则基本概念与性质 a g r a w a l 等在文献【9 】中对关联规则挖掘的基本模型及问题进行了描述。在本节将详 细地介绍这一基本概念。 设，= i ii 2 ，f 3 。m ) 是m 个不同的项组成的集合，设d = f l ，：。j 。 是数据库事务的集 合，其中的每一个事务f ，( 1 j 刀) 是，中一组项的集合，即r ，每个事务有一个唯 一的标志符t i d 。 定义2 1 一个集合a 门尔为一个项集( i t e m s e t ) ；如果项集包含k 个项，则称该项集 称为一个k 项集。 定义2 2d 是事务数据库，f 是一个事务，a 是一个项集。如果彳f ，则事务f 支 持项集a 。事务数据库d 中支持项集a 的事务所占总事务的百分比称为该项集的支持 度，记作s u p p o r t d ( 彳) ，定义如( 2 1 ) 所示。 s u p p 。州) = 皆 ( 2 1 ) 定义2 3d 是事务数据库，a 是一个项集。如果项集爿在事务数据库d 中支持度不 小于用户给定的最小支持度，则称项集a 是一个大项集或者频繁项集；否则称项集a 为 小项集或者非频繁项集。 定义2 4 关联规则是形如ajb 的蕴涵式，其中ac i ，bc ，an b = 矽。a 称 为规则的前项，b 称为规则的后项。规则ajb 在事务数据库d 中的支持度是d 中事务 支持项集aub 的事务所占d 中总事务的的百分比，记作s u p p o r t d ( 彳jb ) ，定义如公 式( 2 2 ) 所示。 6 第二章关联规则概念与常用方法 s u p p o r t o ( 4j 曰) ；竖葛掣( 2 2 ) 规则ajb 在事务数据库d 中的置信度是d 中事务支持项集aub 的事务所占支 持项集a 的总事务的的百分比，记作c o n f i d e n c e n ( 彳jb ) ，即： c o n f i d e 舭删删= 觜觜 ( 2 3 ) 规则的支持度和置信度是两个不同的概念。支持度是规则的统计显著性度量，而置 信度则对应于规则的强度度量。同时满足最小支持度( m i n s u p ) 和最小置信度( m i n c o n f ) 的 规则称为强规则。 关联规则挖掘的基本问题就是研究事务数据库中事务项出现之间的关系，找出所有 具有用户给定的最小支持度( m i n s u p ) 和最小置信度( m i n c o n j ) 的关联规则，即产生强规则 aj b ，其中s u p p o r t d ( 彳jb ) m i n s u p 上1 c o n f i d e n c e d ( 彳jb ) m i n c o n f 。 挖掘关联规则一般分为以下两个过程： ( 1 ) 求出d 中满足最小支持度m i n s u p 的所有频繁集； ( 2 ) 利用频繁集生成满足最小可信度m i n c o n f 的所有关联规则。 由于第二步比较简单，性能主要取决于第一步。 性质2 1 若项集彳是频繁项集，则其所有非空子集都是频繁的。 性质2 2 若项集a 是非频繁项集，则其所有超集都是非频繁的。 定义2 5 如果频繁项集f 的所有超集都是非频繁项集，那么，称为最大频繁项集。 2 2 关联规则的分类 关联规则按照不同的标准有不同的分类1 1 0 。4 l ： ( 1 ) 按照规则中处理的变量类别 基于规则中处理的变量类别，可以分为布尔型关联规则和数值型关联规则。布尔型 关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值型的关 联规则则可以和多维或者多层关联规则结合起来，对数值型字段进行处理，将其进行动 态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变 量。 ( 2 ) 按照规则中数据的抽象层次 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单层关联 规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的。而在多层关联 规则中，对数据的多层性已经进行了充分的考虑。 7 大连交通大学工学硕士学位论文 ( 3 ) 按照规则中涉及到的数据维 基于规则中涉及到的数据维，可以分为单维关联规则和多维关联规则。在单维关联 规则中，涉及到数据的一个维，如用户购买的物品等。在多维的关联规则中，要处理的 数据将涉及到多个维。 2 3 典型关联规则算法 自从1 9 9 3 年以来，数据挖掘领域的研究学者在挖掘关联规则问题上上做了大量的 研究并取得了令人瞩目的成果，目前大多数研究集中在频繁项集的挖掘方法上，关于关 联规则的挖掘算法归纳起来主要有：循环式扫描算法、增量式更新算法、挖掘泛化或多 层关联规则、挖掘多值属性关联规则、基于约束的关联规则挖掘、并行挖掘算法、普遍 化关联规则的挖掘。下面主要介绍三种典型的关联规则挖掘算法：a p r i o r i 算法【l 0 1 、 f p g r o w t h 算法【1 4 1 引、基于图的关联规则挖掘算法【1 9 。2 1 1 。 2 - 3 1a p r i o r i 算法 典型的关联规则算法是由r a g r a w a l 等于1 9 9 3 年首先提出的a p r i o r i 算法，是描述 数据库中数据项之间存在的一些潜在关系的规则，它属于数据库遍历类算法。该关联规 则在分类上属于单维、单层、布尔关联规则。 ( 1 ) 算法的基本思想 关联规则提取问题可以分为两个子问题： 找出事务数据库中所有大于或等于用户指定最小支持度的项集，具有最小支持 度的项集称为频繁项集或者大项集。 利用最大频繁项集生成所需要的关联规则，根据用户指定的最小置信度确定规 则的取舍，最后得到强关联规则。 事实上，关联规则提取执行过程的第一个子问题是核心问题，它决定挖掘关联规则 的总体性能，第二个子问题相对容易实现。 ( 2 ) a p r i o r i 定理及其推论 a p r i o r i 定理：频繁项集的所有非空子集都必须也是频繁的。由a p r i o r i 定理可以得 到以下两个推论： 推论1 ：非频繁项集的超集一定是非频繁项集。 推论2 ：强规则的子规则也是强规则。 ( 3 ) a p r i o r i 核心算法分析i 1 0 】 为了生成所有频集，使用了递推的方法。其核心思想简要描述如下： 厶：f r e q u e n ti t e m s e to fs i z ek 8 第二章关联规则概念与常用方法 q ：c a n d i d a t ei t e m s e to f s i z ek l ：a l li t e ms e t si nd a t a b a s ed m e t h o d ： 1 ) 厶= l a r g e1 - i t e ms e t s ； 2 ) f o r ( k = l ；厶! = 矽；l 【抖) d ob e g i n 3 ) g + l = a p r i o r i g e n ( l k ) ；通过对l k 自连产生新的候选集 4 ) f o re a c ht r a n s a c t i o nf dd ob e g i n 5 )c = s u b s e t ( g 小t ) ； 事务t 中包含的候选集 6 ) f o r e a c hc a n d i d a t ec c d o 7 )c c o u n t + + ：对候选项集进行计数 8 )e n d ； 9 ) l k + l = p c ic c o u n l m i n s u p 1 0 ) e n d 1 1 ) l = u 厶+ l 首先产生频繁1 - 项集厶，然后是频繁2 - 项集厶，直到有某个广值使得为空时算 法停止。这里在第k 次循环中，先产生候选( k + 1 ) 一项集的集合g + 。，g + 。中的每一个项 集是对两个只有一个项不同的属于厶的频繁项集做一个连接来产生的。c k + l 中的项集是 用来产生频繁项集的候选集，最后的频繁项集厶+ 。必须是g + 。的一个子集。g + 。中的每 个元素需在事务数据库中进行验证来决定其是否是频繁项集，是则加入l k + l 否则不加 入。 为了提高算法的效率，a g r a w a l 等引入了修剪技术来减小候选集g 的大小。一个项 集是频繁项集当且仅当它的所有子集都是频繁项集。那么，如果c 。中某个候选项集有 一个( k - 1 ) 一子集不属于厶- 1 ，则这个项集可以被修剪掉，不再被考虑，这个修剪过程可以 降低计算所有的候选集的支持度的代价。 ( 4 ) a p r i o r i 算法缺点 a p r i o r i 算法采用了逐层搜索的迭代的方法，算法简单明了，没有复杂的理论推导， 也易于实现。但其有一些难以克服的不足： 需要多次扫描数据库，每次验证g ( 七= 1 , 2 ，刀) 中的候选项集是否频繁时都需 要扫描数据库一次来获得候选项集的支持度，当频繁项集的最大长度为n 时，则需要扫 面n + 1 次数据库。如果遇到海量数据库，或者n 太大时，耗时太长，难以满足实际应用。 9 大连交通大学t 学硕士学位论文 a p r i o r i 算法会产生大量的候选频繁项集。m 个频繁k 项集就会产生m ( m 一2 ) 2 个候选频繁( k + 1 ) 项集。 基于支持置信度框架理论发现的大量规则中，有一些规则即使满足用户指定的 最小支持度和置信度，但仍没有实际意义；如果最小支持度定得较高，覆盖的数据较少， 有意义的规则可能不被发现。这都将误导决策的制定。 算法的适应范围小，该算法仅仅考虑了布尔型、单维的关联规则的挖掘，但在 实际应用中，可能出现数值的、多维的、多层的关联规则。这时，该算法就不再适用， 需要改进，甚至需要重新设计算法。 ( 5 ) a p r i o r i 的改进算法 针对a p r i o r i 算法存在以上一些主要的不足，要提高a p n o r i 的效率，可以从以下两 个方面去做工作：一是减少对数据库的扫描次数；二是生成较小的候选频繁项集。目前 许多专家学者通过大量的研究工作，提出了一些改进的算法以提高a p r i o r i 的效率。 散列技术 该算法由p a r k 等在1 9 9 5 年提出。通过实验发现寻找频繁项集的主要计算是在生成 频繁2 项集厶上，p a r k 就是利用这个性质引入散列技术来改进产生频繁2 项集的方法。 事务压缩技术 a g r a w a l 等提出压缩进一步迭代扫描的事务数据的方法。因为不包含任何k 项集的 事务，不可能包含任何( k + 1 ) 项集，可对这些事务加上删除标志，扫描数据库时不再考 虑。 划分技术 s a v a s e r e 等设计了一个基于划分的算法，这个算法先把数据库从逻辑上分成几个互 不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并， 用来生成所有可能的频集，最后计算这些项集的支持度。 抽样技术 基于前一遍扫描得到的信息，对此仔细地组合分析，可以得到一个改进的算法， m a n n i l a 等先考虑了用采样来解决这一点。随后又由t o i v o n e n 进一步发展了这个思想， 先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数 据库的剩余部分验证这个结果。t o i v o n e n 的算法较简单并显著地减少了i o 代价，但是 产生的结果存在数据扭曲。 动态项集计数 b r i n 等给出该算法。动态项集计数技术将数据库划分为标记开始点的块。不像 a p r i o r i 仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始 1 0 第二章芙联规则概念与常用方法 点添加新的候选项集。该技术动态地评估被计数的所有项集的支持度，如果一个项集的 所有子集己被确定为频繁的，则添加它作为新的候选。该算法需要的数据库扫描比 a p r i o r i 少。 2 3 2f p g r o w t h 算法 针对a p f i o r i 算法的固有缺陷，j h a n 等在文献 1 4 】中提出了不产生候选挖掘频繁项 集的方粕p g r o w t h 算法。 ( 1 ) f p g r o w t h 的基本思想 该算法采用分而治之的策略，在经过第一遍扫描之后，把数据库中的频繁项集压缩 到一棵频繁模式树( f p t r e e ) ，同时依然保留其中的关联信息，随后再将f p t r e e 分化成 一组条件数据库，每组条件库和一个长度为1 的频繁项集相关，然后再对这些条件库分 别进行挖掘。 ( 2 ) 算法核心 f p g r o w t h 算法一般分为以下几步进行： 挖掘频繁1 项集 首先扫描一遍数据库，得到频繁1 项集的集合。然后，对频繁1 项集按支持度计数 的递减顺序排序，结果记为厶。 构造f p t r e e 首先，创建树的根节点，用“n u l l ”标记。 然后，扫描数据库，对事务中的每个项按照厶中的次序进行处理( 根据支持度递减 顺序排序并对每个事务创建一个分枝) 。 对f p t r e e 进行挖掘 通过前两步，数据库中的频繁项集都已经被压缩到f p t r e e 中，现在只要对f p t r e e 进行挖掘就可以得到频繁项集。对f p - t r e e 的挖掘可以通过调用f p _ g r o w t h ( t r e e ，n u l l ) 实 现，该过程实现如下： p r o c e d u r ef p _ g r o w t h ( t r e e ，0 【) 1 ) i f t r e e 含单个路径pt h e n 2 )f o r 路径p 中结点的每个组合( 记作) 3 ) 产生模式u 口，其支持度等于中结点的最小支持度； 4 ) e l s e 5 ) f o re a c h 口，在t r e e 的头部 6 )产生一个模式= a ，u 口，其支持度等于口j 的支持度； 大连交通大学工学硕十学位论文 7 )构造的条件模式基，然后构造的条件f p t r e r m p ； 8 ) i ft r e e f l t h e n 调用f p _ g r o w t h ( t r e e f l ，) ； 9 ) ( 3 ) 算法分析 f p g r o w t h 方法将发现频繁模式的问题转换成递归地发现一些短模式，然后与后缀 连接。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降低了搜索开销。 当原始数据量很大的时候，构造基于内存f p t r e e 是不现实的，但此时可以结合划 分的方法，使得一个f p t r e e 可以放入主存中。实验表明，f p g r o w t h 对不同长度的规 则都有很好的适应性，同时在效率上较之a p r i o r i 算法有巨大的提高【1 5 。1 3 】。 2 3 3 基于图的关联规则挖掘算法 除了a p r i o r i 和f p g r o w t h 两类算法，s h o w j a n ey e n 和a r b e el p c h e n 也提出了一 种有效的算法基于图的关联规则挖掘算法【1 9 圳】，该算法仅扫描一次数据库，然后构 建关联图并根据该图来生成候选频繁项集，最后通过验证得到所有的频繁项集。 ( 1 ) 算法的基本思想 采用垂直数据库布局，将数据库的信息映像到位向量矩阵，因此只需扫描一遍数据 库；构建关联图，可以通过该图直接生成候选频繁项集；对候选频繁项集中各项的位向 量做相交操作( 即逻辑“与 操作) 来验证该候选项集是否是频繁项集。 ( 2 ) 算法核心 基于图的关联规则算法一般分为以下几步进行： 第1 步扫描一遍事务数据库d ，为每个项赋予一个唯一的整数编号，并且为每个 项建立一个位向量。项的位向量的长度等于事务数，若某项在第n 个事务中出现，则该 项的位向量的第n 位置1 ，否则置o 。项的位向量中l 的数量表示该项在数 据库中出现的次数，即表示支持数的大小。项i 的位向量用b v i 表示。 第2 步确定图的节点。满足最小支持度的所有项( 频繁1 项集厶中的项) 构成图的 节点集，用v 表示。 第3 步构建关联图并生成频繁2 项集。关联图是一种有向图，图中每个节点表示 一个频繁1 项集( 节点称为项节点) 。关联图表示了频繁1 项集之间的一种关联关系，其 构建方法为：对厶中任意两个频繁1 项集i 和j ( 不妨设髑) 的位向量做相交操作b v i a b v i ，如果位向量中l 的个数不小于最小支持度，那么在关联图中就创建一条从i 到 j 的有向边( 注意有向边都是编号小的项指向编号大的项) ；同时将 i ，j a n 入频繁2 项集 的集合厶。 1 2 第二章关联规则概念与常用方法 第4 步得到所有的频繁k 项集( k 2 ) 。第3 步后得到了关联图和所有的频繁2 项集， 频繁( k + 1 ) 一项集( 七2 ) 的生成方法是这样的( 令k 初值为2 ) ：令频繁( k + 1 ) 项集的集合厶+ 。 为空。对每一个频繁k 项集，其最后一个项被用来扩展得到候选频繁( k + 1 ) 项集。扩展 方法为：设 i l ，i 2 ，e e pi k 表示一个频繁k - 项集，i k 是最后一项。设关联图中从i k 发出 的有向边指向的所有项节点为 u i ，u 2 ，u n ) ，贝j j i l ，i 2 ，i k ，u 1 ) ， i l ，i 2 ， i k ，u 2 ，a e i 1 ，i 2 ，i k ，u f l 就是扩展得到的候选频繁( k + 1 ) 项集。然后将每个候选 频繁( k + 1 ) 项集中的k + 1 个项的位向量进行相交操作，如果位向量中l 的个数不小于 最小支持度，则该候选项集是频繁的，将其加入厶+ ，。令k = k + l ，若频繁k 项集厶不为 空，循环执行上述操作；否则，算法终止。最终所有的频繁项集为厶u 厶u 厶。 ( 3 ) 算法分析 该算法仅需扫描一次数据库，相比a p f i o r i 和f p g r o w t h 算法减少了访问数据库的 操作时间；通过构造关联图，提供了候选频繁k 项集( k 2 ) 的生成方法。考察a p r i o r i 算 法，其候选频繁( k + 1 ) 项集的生成，是通过频繁k 项集两两自连接，然后再进行剪枝得 到。d l g 算法相比a p r i o d 算法，候选项集的生成方法更加简单，并且仅扫描一次数据 库，算法效率较高。 但是使用该算法仍需要产生大量的候选项集。 ( 4 ) 改进算法 为了减少候选项集的数量，还出现了很多基于图的关联规则改进算法d l g 2 ，该算 法对d l g 坶j 进行了以下两方面的改进： 按支持度降序对频繁1 项集重新编号再构建关联图 频繁1 项集得到之后，按照支持度大小降序对频繁1 项集集的各项从1 开始递增重 新编号，即支持度最大的频繁项集重编号l ，次之重编号为2 ，依次类推。然后再构建 关联图。根据d l g 算法，关联图的边都是由编号小的项节点指向编号大的项节点。这 样在关联图中，重新编号后的项1 发出的有向边指向的节点最多；项2 次之，依次类推。 而频繁k 项集中的各项是按编号由d , n 大排列的。因此，按照改进方法生成的关联图由 频繁k 一项集扩展得到候选频繁( k + 1 ) 项集时，扩展的节点与频繁k 项集的前k 1 个节点 在关联图中相邻的几率增大了，这样就去掉了原来算法可能产生的一部分冗余候选频繁 ( 1 + 1 ) 项集，相当于做了一次剪枝。 利用a p r i o f i 定理及其推论删减用来生成候选项集的冗余扩展项节点 通过改进大大减少了候选项集的数量。 大连交通大学t 学硕士学位论文 2 4 关联规则主要研究问题 关联规则目前主要研究的问题有【l o l ： ( 1 ) 提出更为合理有效的规则评价标准 在许多实际应用中，如果仅凭借支持度和置信度这两个评价关联规则的标准，可能 会发现大量冗余、虚假或非有趣的规则，因而提出一些新的评价标准很有必要，但这可 能要视具体应用而定。 ( 2 ) 设计更高效的可扩展的挖掘算法 为了从海量数据库中有效地抽取信息，挖掘算法的效率显得尤为重要。单纯从计算 机的角度对算法的研究已趋于饱和，有必要加强结合领域知识的理解，以提取与挖掘任 务有关的数据，有效地减少问题的复杂度，提高算法的效率。在这方面，基于约束的关 联规则挖掘有广阔的发展前景。 ( 3 ) 对更多类型的数据源的挖掘 目前大多挖掘算法都是对关系型数据库的挖掘。由于应用领域的不同，所挖掘的数 据的类型也不同，如结构化数据、超文本数据、多媒体数据、空间数据、面向对象数据、 多维数据、数据仓库、数据流等，研究对这些类型数据库的关联规则挖掘也将是很迫切 的工作。 ( 4 ) 并行关联规则 数据量的不断增长、维数的越来越高、数据的不对称性动态负载的平衡、并行的数 据库管理系统与文件系统等，所有这些都是目前在并行数据挖掘中尚需要解决的问题。 随着大规模并行计算在数据挖掘中的应用，由于挖掘系统本身的原因，并行数据挖掘无 法实现任意程度的并行。 ( 5 ) 与数据仓库和o l a p ( o n - l i n ea n a l y t i c a lp r o c e s s i n g ) 的结合 数据挖掘需要的数据是一些经过净化、集成处理的数据，通常这种预处理过程也是 昂贵的，而数据仓库作为o l a p 的数据源，存储的就是这样的数据。它能为o l a p 提供 数据，当然也可以为数据挖掘提供数据。o l a m ( o n l i n ea n a l y t i c a lm i n i n g ) 将两者结合 起来，发展一种建立在o l a p 和数据仓库基