（计算机软件与理论专业论文）基于隐私保护的关联规则挖掘算法研究.pdf

中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 基于隐私保护的关联规则 挖掘算法研究 专业：计算机软件与理论 硕士生：方靖 指导教师：印鉴教授 摘要 隐私保护是当前数据挖掘领域中一个十分重要的研究问题，其目标是要在 不精确访问真实原始数据的条件下，得到准确的模型和分析结果。目前，隐私 保护数据挖掘方法主要分为数据干扰和查询限制这两种策略。然而，它们本身 却都存在着一些固有的缺陷，对隐私数据的保护程度不高。关联规则挖掘作为 数据挖掘中的重要方法之一，在现有的隐私保护研究方面同样存在这样的问题。 为了提高隐私数据的保护程度和挖掘结果的准确性，本文将数据干扰和查询 限制策略有机地结合起来，提出了一种新的数据随机处理方法部分隐藏的转 移概率矩阵( p h t p m ) 数据变换方法。本文首先利用p h t p m 对原始事务集进行 变换和隐藏；然后以此为基石：i ：，针对经过p h t p m 方法处理后的数据，给出了一种频 繁项集生成算法o p a m ；最后运用有效的优化策略对o p a m 进行改进，进而提出 了一种简单而又高效的算法a o p a m 。理论分析和实验结果均表明，基于p h t p m 的隐私保护关联规则挖掘方法比原有的方法在数据的保护程度上具有更好的隐 私性，在挖掘的结果上具有高的准确性；而且p h t p m 方法也有着很好的高效性 和适用性。 关键字：数据挖掘，关联规则，隐私保护，随机化回答，转移概率矩阵 中山大学硕士学位论文 基于隐私保护的关联规则挖掘算法研究 t h er e s e a r c ho f 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 nr u l e m i n i n g m a j o r ：c o m p u t e rs o r w a r ea n dt h e o r y n a m e ：f a n gj i n g s u p e r v i s o r ：p r o f y i nj i a n a b s t r a c t p r i v a c yp r e s e r v a t i o ni so n eo ft h em o s ti m p o r t a n tt o p i c si nd a t am i n i n g t h e p u r p o s ei st od i s c o v e ra c c u r a t ep a r e r n sw i t h o u tp r e c i s ea c c e s st ot h eo r i g i n a ld a t a i n p r e s e n t , t h e r ea r ct w om a i ns t r a t e g i e si np r i v a c yp r e s e r v a t i o nd a t am i n i n g d a t a p e r t u r b a t i o na n dq u e r yr e s t r i c t i o n h o w e v e r , b o t ho ft h e mh a v es o m ei n h e r e n td e f e c t w h i c hw i l ld e g r a d et h ep r i v a c y a so n eo f t h em o s ti m p o r t a n tm e t h o d si nd 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 st h es a m ep r o b l e mi np r i v a c yp r e s e r v a t i o nr e s e a r c ha r e a i no r d e rt oi m p r o v et h ep r i v a c yp r e s e r v a t i o na n dm i n i n ga c c u r a c y ，an e wm e t h o d i sp r e s e n t e di nt h i sp a p e r f i r s t , an e wd a t ap r e p r o c e s s i n ga p p r o a c h , p a r t i a lh i d i n g 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 ( p h t p m ) i sp r o p o s e d i nt h i sa p p r o a c h ，t h et w op r i v a c y p r e s e r v i n gs t r a t e g i e sa r ec o m b i n e dt ot r a n s f o r ma n dh i d et h eo r i g i n a ld a t a t h e n , a p r i v a c yp r e s e r v i n ga 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 mo p a ma n da l li m p r o v e d a l g o r i t h ma o p a m b a s e do np h t p ma r cp r e s e n t e d a ss h o w ni nt h et h e o r e t i c a l a n a l y s i sa n dt h ee x p e r i m e n t a lr e s u l t s ，p r i v a c yp r e s e r v i n ga s s o c i a t i o nr u l em i n i n g b a s e do np h t p mc a na c h i e v es i g n i f i c a n ti m p r o v e m e n t si nt e r m so fp r i v a c y , m i n i n g a c c u r a c y ，e f f i c i e n c y , a n da p p l i c a b i l i t y 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 ，p r i v a c yp r e s e r v i n g ，r a n d o m i z e r e s p o n s e ，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 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 1 1 引言 第1 章概述 随着信息技术，特别是网络技术、数据存储技术和高性能处理器技术的飞速 发展，海量数据的收集、管理和分析变得越来越方便，知识发现和数据挖掘更是 在一些深层次的应用中发挥了积极的作用。数据挖掘技术( d a t am i n i n g 简称d m ) 是针对“r i c h d a t a p o o r i n f o r m a t i o n ”问题而提出的一种分析型工具，它能从大量 的、模糊的、随机的数据中提取出数据间重要的但容易被人工分析忽略的知识和 信息，自动地发现隐藏在数据间的模式，并作出预测性分析。这些数据的分析结 果对于政府、商业组织决策以及提供社会福利等方面都有着十分重要的作用。 但与此同时，数据挖掘的广泛应用也带来了隐私保护方面的诸多问题。例如， 通过对医院病人的病历数据进行挖掘，可以发现各种疾病之间的关联。但在使用 一般方法进行挖掘的过程中，不可避免地会使病例数据暴露，从而造成病人隐私 的泄露。还有治安系统中的违法记录、保险公司的理赔情况，银行卡客户的交易 行为等信息中的关联关系，都对政府和企业决策具有相当重要的意义，但同时又 都是公民非常注重的个人隐私。 因此尽管数据挖掘应用对社会目标有着很大的利用价值，但人们对它的使用 却持有一定的保留意见。人们最容易想到的是那些不被授权的金融交易和医疗记 录被利用的潜在伤害。美国最近的民意调查显示了人们对个人信息被利用的忧 虑：有7 0 以上的被访者反对将医疗记录不受制约地应用于研究目的；有7 8 的 被访者认为计算机技术代表了对个人隐私的威胁，因此如果要保护隐私，将来要 严格控制计算机的使用；将近有7 6 的人觉得自己对个人信息已经失去了控制， 隐私受到威胁。时代周刊、英国广播电视以及最近的一些研究表明：至少有9 3 的被访者认为公司在出售个人数据之前必须获得个人的允许。另一项调查显示， 有9 6 的被访者认为私人信息不应该在没有被允许的情况下使用，超过2 0 的被 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 访者亲身体验过隐私的侵犯。 隐私被普遍地认为是个人用来控制自己信息的权力。1 9 9 0 年莲花发展公司发 布了一个储存有l o 千万个美国家庭记录的数据光盘，其数据的详细引起了公众的 强烈不满，因此莲花公司不得不决定停止该数据光盘的发布。不幸的是，由于一 些大公司已经访问并使用了这个莲花数据库，因此每年依然至少有4 0 千万个信用 记录，7 0 千万个药品记录，l o 千万个医疗记录和6 0 千万个私人记录被2 0 0 多个部 门出售，这些出售的记录包括银行资产负债表、租赁历史、犯罪记录以及那些没 有被公开过的电话号码。这些信息被结合起来发展成为了个人的数据形象，出售 给了私人个体、研究机构以及政府组织。而这些数据形象正是现在的知识发现和 数据挖掘工具的分析主体【1 1 。 可见，如何在数据挖掘过程中解决好隐私保护的问题，研究保护隐私的方法， 防止数据被误用，找出更多保护数据隐私和安全的解决方案己成为数据挖掘研究 中一个重要的研究领域1 2 3 1 。首先需要明确的是，可能泄露隐私的并不是数据挖 掘技术本身，而是数据挖掘方法的特定应用和具体过程。数据挖掘有一个重要特 征，就是从大量数据中挖掘出来的模式或者规则，通常是针对综合数据而非细节 数据。那么，我们是否可以基于非精确的原始数据而抽取出准确的模式与规则 呢? 实现隐私数据的合理保护和基于统计数据的模式抽取两者兼得，正是隐私保 护数据挖掘方法研究的出发点和最终目科4 1 。 1 2 国内外相关工作 目前，隐私保护的数据挖掘方法按照基本策略主要可以分成数据干扰1 4 】和 查询限i n t 9 “3 1 两大类。 数据干扰方法是一种解决数据挖掘中个人隐私保护难题的常用方法。数据干 扰技术的主要思想是在保持数据在挖掘和统计中的效用的同时，通过转换改变数 据使得真实的个人数据值不被披露。因为转换后的数据不是反映真实的个人数据 值，所以即使数据项跟某个个体相关联，这个个体的隐私也不会被侵犯。数据 干扰技术的一个主要方法是数据交换。通过数据记录之间交换数据从而保护了可 2 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 靠的统计结果，同时又能隐藏了真实的数据值。数据干扰技术的另一个主要方法 是随机化；为数据增加“噪声”以保护真实数据不被发现。通过对数据的随机化 处理，数据不再反映真实的世界，从而使得数据无法被滥用而侵犯个人的隐私。 当然数据干扰技术的关键在于如何从变换后的数据中获得有效的数据挖掘结果。 查询限制策略则是通过数据隐藏、数据抽样和数据划分等方式，避免数据挖 掘者拥有完整的原始数据，而后再利用概率统计的方法或者分布式计算的方法得 到所需的挖掘结果。 但是，这两种策略本身都存在着一些固有的缺陷。在采用数据干扰策略的方 法中，所有经过干扰的数据均与真实的原始数据直接相关；而在采用查询限制策 略的方法中，所有提供的数据又都是真实的原始数据。这些都会降低方法对隐私 数据的保护程度。 关联规则的挖掘作为数据挖掘中最重要的方法之一，也在隐私保护方面取得 了一定的研究成果。数据干扰方法应用于隐私的保护关联规则挖掘是首先由 a g r a w a la n ds r i k a n t 提出的【4 】。他们拿把n 个原始值而，屯，看作是n 个具有相同 分布的独立随机变x l ，x ：，x 。的值，其中随机变量x 。，x ：，x 。同随机变量x 具 有相同的分布，密度函数是f x 。为了隐藏原始数据，因此提供给挖掘算法的数 据是+ 乃，屯+ 肋，+ 只，乃是加入的噪声数据，对应随机变量x 的值，y 的 密度函数是f y ( 均值为o 的正态分布或者均匀分布) 。对于挖掘算法，已知毛+ 咒 和f y ，需要在此基础上重构x 的近似分布，即f x 的近似估算。其主要思路是利 用贝叶斯规则迭代进行近似估算f x 。 另外一个具有代表性的数据干扰应用是文献【5 ，6 】提出了一种基于随机变换 的m a s k ( m i n i n g a s s o c i a t i o n sw i t hs e c r e c yk o n s t r a i n t s ) 川方法。研究的主要方法是 首先将原始数据集构造为二维布尔稀疏矩阵数据模型，利用简单概率方法改变数 据的原始值，使得项目值以概率p 保持不变，i ：! g l - p 的概率取反。若为项目从l 变 成o 则相当于删除项目，反之则为添加噪声项目，实质是对数据集中的项目以一 定概率进行增删或保持不变，从而对原数据集的信息进行了保护。由于发现关联 规则必须先获得频繁项集，因此须对项集的支持度进行重构，估算项集受干扰前 3 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 的支持度，从而发现频繁项目集。 虽然这些方法都实现了隐私保护的关联规则挖掘。但这些方法都是利用了统 计学中的沃纳模型，不仅由于变换后的所有数据均与真实的原始数据直接相关， 使得对隐私数据的保护程度并不理想，而且随机化参数的选择也都受到限制，必 须偏离0 5 。 在查询限制策略方面的关联规则挖掘研究工作中，文献【9 】提出了通过使用 “未知”值来替代部分敏感的原始数据，使得敏感规则不被发现的方法。文献 z 0 1 也提出了针对特定的敏感规则对原始数据进行隐藏，降低敏感规则支持度，使其 不被发现的方法。在这些数据隐藏方法中，虽然一部分敏感信息得到了很好的保 护，但由于所提供的所有数据都是真实的原始数据，所以对整个数据集的隐私保 护程度并不高。而且，这类方法必须预先知道需要隐藏或者处理的敏感规则，但 在通常情况下，具体的规则在挖掘结果出来以前都是未知的。 分布式数据隐私保护是采用查询限制策略的另一类方法，分布式数据隐私保 护基于一个这样的前提假设：参与者拥有自身的数据，各方通过合作进行挖掘， 但是在这个过程中不允许任何一方获得别人的数据。在这个假设下，分布式数据 模型的主要思想是通过加密和解密技术来保持隐私的，特别的，利用安全多方计 算方法可以获得准确的挖掘结果。隐私保护的衡量标准是各站点之间的数据是否 保密，即每个站点不能泄露站内事务属性值。 文献【1 l ，1 2 】分别提出了基于水平划分和垂直划分的隐私保护关联规则挖掘 方法。水平型分布数据的关联规则挖掘目的是找出全局关联规则，即满足全局最 小支持度和全局最小置信度。在水平型分布的数据库中，一个项集的全局支持度 是局部的支持度之和，所以可以由局部k 频繁项集产生全局k 频繁项集。隐私保护 的思路是保证各个站点只知道本站点的频繁项集，而无法获得其他站点的频繁项 集。而对于垂直型分布数据，挖掘隐私关联规则的关键步骤是项集支持度的计算， 如果可以通过异地的双方的中间数据安全计算全局项集支持度，然后将该全局项 集支持度同阀值进行比较，即可判定该项集是否频繁集。文献 1 3 1 还提供了一个 支持隐私保护数据挖掘的分布式计算工具集。但这类方法只能用于分布式数据 库，所有的数据提供者都必须参与到计算中来，单点故障就会产生错误的结果， 甚至造成挖掘无法进行。而且，当数据提供者的数量很多时，这类方法的性能会 4 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 由于巨大的通信开销而显著下降。 最近文献 1 4 】提出了一种新的隐私保护数据挖掘策略，它将数据干扰和查询 限制策略的思想结合了起来。文中提出了一个应用于隐私保护关联规则挖掘的方 法部分隐藏的随机化回答( f d k p h ) 方法。虽然灿心h 能在一定程度上克服 数据干扰和查询限制的一些固有缺陷，但由于在r r p h 方法中当选择“对数据 进行回答时，回答的结果都是真实的数据，即实际上并没有将这部分数据进行干 扰，使到数据的隐私程度不能得到很好的保护。而且由于算法在对伪造数据库进 行频繁项集挖掘时是完全基于a p r i o r i 算法思想的，因此造成了由k 1 频繁项集 生成k 频繁项集时的挖掘误差传递。而本文提出的方法就是要在运用这种新的策 略的基础上，弥补这些方面的缺陷，把数据干扰和查询限制真正地有机结合起来。 而且在以下章节的描述中可以看到，其实r r p h 中的数据变换方法是本文提出 的数据变换方法中的一个特例情况。 1 3 本文的主要工作与贡献 可以看出，在应用需求的推动下，隐私保护的数据挖掘方法已受到广泛的关 注，并取得了相当大的进展，但仍然存在着很多的不足之处以及尚未解决的问题。 在国内，隐私保护的数据挖掘还是一个崭新的领域。 ， 为了提高对隐私数据的保护程度和挖掘结果的准确性，本文根据文献 1 4 】 提出的将数据干扰和查询限制相结合的策略，提出了一种基于部分隐藏的转移 概率矩阵( p a r t i a lh i d i n gt r a n s i t i o np r o b a b i l i t ym a t r i x ) 数据变换的隐私保护关联 规则挖掘方法。该方法对随机化参数的选择没有任何限制，也不需要其他额外 的信息，而且可以同时适用集中式数据库和分布式数据库。更重要的是，理论 分析和实验结果均表明：基于p h t p m 的隐私保护关联规则挖掘方法克服了单 一策略中固有的缺陷，把两种有机地结合了起来。在相同时间和空间开销的条 件下可以得到比原有方法更高的数据保护隐私性和挖掘结果准确性，同时还具 有很好的适用性。 本文的主要贡献在于； 5 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 ( 1 ) 将数据干扰和查询限制策略相结合，提出了一种新的数据随机处理与分布 重构的方法p h t p m ； ( 2 ) 以p h t p m 方法为基础，实现了数据的变换和隐藏； ( 3 ) 提出了一种面向经过p h t p m 方法处理后的数据生成频繁项集的算法 o p a m 。并针对o p a m 算法在空间开销、时间开销、挖掘准确性上的不足， 运用一些优化策略对其进行改进，给出了一个改进后的算法a o p a m ； ( 4 ) 在数据保护的隐私性、挖掘结果的准确性、挖掘过程的高效性以及应用的 适用性方面，对基于p h t p m 的隐私保护关联规则挖掘方法进行了详细的 分析和实验，并与原有的一些方法进行了比较。 1 4 论文结构 本文的余下部分组织如下：第2 章首先给出隐私保护关联规则挖掘的问题描 述，然后介绍在此问题研究上具有代表性的两个算法，最后给出一些相关概念和 定理；第3 章首先给出p h t p m 的主要思想和总体框架，接着介绍如何利用 p h t p m 方法对数据进行变换和隐藏，然后说明如何对经过p h t p m 方法处理的 数据进行关联规则挖掘；第4 章介绍了三点优化策略来对第3 章提出的频繁项集 挖掘算法进行改进，并给出了一个改进后的挖掘算法；第五章给出了对p h t p m 方法的详细分析和评价，并给出了本文的实验方法与实验对比结果；第6 章是本 文的结论部分。 6 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 第2 章隐私保护的关联规则挖掘问题 2 1 关联规则挖掘 关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。随着大量数 据不停地收集和储存，许多业界人士对于从他们的数据库中挖掘关联规则越来越 感兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助去做商务决策的 制定，如分类设计、交叉购物和贱卖分析【3 1 。 关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购 物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被 顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如：在同一次 去超级市场，如果顾客购买牛奶，他也购买面包( 和什么类型的面包) 的可能性 有多大? 通过帮助零售商有选择地经销和安排货架，这种信息可以引导销售。例 如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商 品。 关联规则挖掘的基本概念如下：设i - - i 。，i ：，i 。j 是项的集合。设任务相关 的数据d 是数据事务的集合。其中每个事务t 是项的集合，使得每一个事务有唯 一标识t i d 。设a 是一个项集，则a 支持事务t 当且仅当a 暑t 。关联规则是形如 a j b 的蕴涵式，其中a c i ，b c i ，并且a n b = a 。规则a j b 在事务中 成立，具有支持度s ( s u p p o r t ) 。其中s 是数据库d 中事务包含a u b 的百分比，即 s u p p o r t ( a j b ) = 气昌里“0 0 。规则a j b 具有置信度c ( c o n f i d e n c e ) ，其中c 是指包含a 的事务中同时也包含b 的百分比，即c c n f i & n c e ( a j b ) = p ( b i a ) 支持度是统计意义上的衡量，而置信度是对规则强度的衡量。同时满足最小支持 度和最小置信度的规则被认为是有趣规则。 7 中山大学硕士学位论文 基于隐私保护的关联规则挖掘算法研究 项的集合称为项集( i t e m s e t ) 。包含k 个项的集合称为k - 项集。项集的出现 频率是包含项集的数据数，简称为项集的频率、支持计数或计数。项集满足最小 支持度m i n s u p ，如果项集的出现频率大于或等于m i n s u p 与d 中事务总数的乘积。 如果项集满足最小支持度，则称它为频繁项集( f r e q u e n ti t e m s e t ) 。 通常，关联规则挖掘的过程分为以下两步： ( 1 ) 发现频繁项集。所谓频繁项集是指支持度不低于预先设定阈值的项集。 ( 2 ) 根据第l 步发现的频繁项集，产生置信度不低于预先设定阈值的关联规则。 2 2a p r i o r i 算法 a p f i o f i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。算法的 名字基于这样的事实：算法使用频繁项集性质的先验知识。正如我们将看到的， a p f i o d 使用一种称作逐层搜索的迭代方法，k 项集用于探索( k + 1 ) 项集。首先 找出频繁1 - 项集合。该集合记作l i 。l t 用于找频繁2 - 项集l ：。而l ：用于找l ， 如此下去，直到不能找到频繁k - 项集。找每个l 。需要一次数据库扫描口1 。 为提高频繁项集逐层产生的效率，一种称作a p r i o r i 性质的重要性质用于压 缩搜索空间。下面先介绍一下这个性质。 a p d o d 性质：频繁项集的所有非空子集都必须也是频繁的。a p r i o r i 性质基 于如下观察：根据定义，如果项集i 不满足最小支持度阈值m i n s u p ，则i 不是频 繁的，即p ( 1 1 m i n s u p 。如果项a 添加到i ，则结果项集i u a 不可能比i 更频 繁出现。因此，i u a 也是不频繁的，即p ( i u a 、 m i n _ s u p 。 接着来看看算法如何利用a p d o d 性质。从l k 。找l k 。算法分两个步骤来完 成： ( 1 ) 连接步：为找l 。，通过l k 。与自己连接产生候选k - 项集的集合。该候选项 集的集合记作c 。设l 。和l ：是l 。中的项集。记号l i 【刀表示l ，的第j 项( 例 如，1 【k l 】表示的倒数第3 项) 。为方便计，假定事务或项集中的项按字 中山大学硕士学位论文 基于隐私保护的关联规则挖掘算法研究 典次序捧序。执行连接o m & - ，其中的l k i 元素是可连接的，如果它们前 ( k - 2 ) 个项相同。即是，l b 。的元素h 和1 2 是可连接的，如果 ( 【l 】= 易【l 】) ( 【2 】= 1 2 1 2 1 ) ( 【| | 一2 】= ，2 七一2 】) ( 【_ | 一1 】 乞【_ j 一l 】) 。条 件t 。 k - 1 】 u _ i 一1 】是简单地保证不产生重复。连接l 。和1 ：产生的结果项集 是“l 】，“2 卜l # - q , u k - i 】。 ( 2 ) 剪枝步：c 。是k 的超级；即是，他的成员可以是也可以不是频繁的，但 所有的频繁k - 项集都包含在c 。中。扫描数据库，确定c k 中每个候选的计 数，从而确定l k ( 即根据定义，计数值不小于最小支持度计数的所有候选 是频繁的，从而属于l k ) 然而，c k 可能很大，这样所涉及的计算量就很 大。为压缩c k ，可以用以下办法使用a p r i o r i 性质：任何非频繁的( k - 1 ) 项集都不可能是频繁k 项集的子集。因此，如果是一个候选k 项集的( k 1 ) 子集不在l - 。中，则该候选也不可能是频繁的，从而可以由c 。中删除。这 种子集测试可以使用所有频繁项集的散列树快速完成。 最后，给出a p r i o f i 算法的伪代码。 算法：a p r i o r i 使用根据候选生成的逐层迭找出频繁项集。 输入：事务数据库d ；最小支持度阈值m i n s u p 。 输出：d 中的频繁项集l 。 方法： ( 1 ) 厶= 倒一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 i a ；七+ + ) ( 3 ) g = a p r o i r i g e n ( l t - l ，r a i n _ s u p ) ； ( 4 )f o re a c ht r a n s a c t i o nte d 扫描事务集d 来对k 项集进行计数 ( 5 ) g = s u b s e t ( c , ，0得到候选集中为事务t 的子集的项集 9 中山大学硕士学位论文 基于隐私保护的关联规则挖掘算法研究 ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 1 0 ) ( 1 1 ) f o re a c hc a n d i d a t ec c i c c o u n t + + ： 厶- - c q 1 c c o u t 2r n i n _ s u p r e t u r nl = u t 厶； p r o c e d u r ea p r i o r i _ g e n ( l 一i ；频繁k - 1 项集；m i n s u p ：最小支持度阈值) ( 1 ) f o r e a c h i t e m s e t 厶- l ( 2 ) f o r e a c h i t e m s e t 如丘- l ( 3 )i f ( 4 ) ( ( 1 1 1 】= 如【1 】) ( 【2 】= 如 2 】) ( 【t - 2 】= f 2 【七一2 】) ( - 1 】 之 一l 】) ) t h e n c = t e a 2 ( 5 ) i f h a s _ i n f r e q u e n t _ s u b s e t ( c ，丘- 1 ) t h e n ，连接步：产生候选集 (6)deletec ：剪枝步：删除具有非频繁子集的候选 ( 7 )e l s ea d dc t o g ； ( 8 ) ( 9 )r e t u r i l g ； 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 ：候选k - 项集；厶一l ：频繁k - 1 项集) ( 1 ) f o re a c h ( k - 1 ) - s u b s e tso f c ( 2 )i fj 甚丘- lt h e n ( 3 ) l c t u m t r u e ； ( 4 ) r e t u r nf a l s e ； 1 0 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 a p i i o r i 算法的第一步找出频繁l - 项集的集合l 1 在第2 一1 0 步，l k 。用于产 生候选c k ，以找出l k 。a p r i o r i _ g e n 过程产生候选，然后使用a p r i o r i 性质删除 那些具有非频繁子集的候选( 第3 步) 。该过程在下面描述。一旦产生了所有的 候选，就扫描数据库( 第4 步) 对于每个事务，使用s u b s e t 函数找出事务中是 候选的所有子集( 第5 步) ，并对每个这样的候选累加计数( 第6 和第7 步) 最 后，所有满足最小支持度的候选形成频繁项集l 。然后，调用一个过程，由频繁 项集产生关联规则。 2 3 隐私保护数据挖掘 通常情况下我们讨论的各种数据挖掘技术都是在能够获得正确的输入数据 时才能挖掘出正确的结果。但是在现实生活中，要获得正确的输入数据却并非是 一件容易的事情。特别是在网络飞速发展的今天，很多互联网用户在被要求提交 他们的个人信息时，他们往往会是提交一份不正确的个人信息，以免他们的个人 资料被互联网服务商用于不正当的地方。设想一下以下情景：假设某公司要去建 立一个它的所有客户的个人资料的统计模型。例如一家零售商店希望知道最有可 能买d v d 机或爬山用品的客户的年龄和收入；一个影视公司希望了解用户们对 各类型电影的偏好，以便他们做的广告能更有针对性；又或者是一家网上购物公 司希望根据网上消费者的一些统计资料来调整他们的网页布局与设计。所有的这 些情景中，都是会有一个中心的服务机构( 例如上述的几家公司) ，以及很多很 多的客户( 例如上述的各种用户) ，他们每人都拥有这自己的一份信息。中心服 务机构会采集所有客户所拥有的信息来建立一个统计模型( 例如关联规则挖掘) 。 通常这种统计模型都不会在包含个别用户的信息，仅仅包含了大量用户的一些平 均信息。 正如我们所说的，中心机构总是希望得到每个用户真实的信息以便能获得精 确的统计模型，但实际上用户们却变得越来越关心他们自己的个人信息。他们很 可能会避免给出一些信息或给出一些错误的信息，令自己的隐私受到保护。所以 现在要解决的问题就是中心机构如何在获得受到隐私包含的信息后仍然能统计 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 出尽可能正确的结果。这就是隐私保护数据挖掘要研究的内容。 基于隐私保护关联规则挖掘就是要在不精确访问原始事务集的条件下，尽量 准确地发现其中的频繁项集，用于产生支持度与置信度分辨不低于用户给定阈值 的关联规则。可以看出，隐私性与准确性在此是一个矛盾，如何能在保持较高的 隐私性条件下挖掘出准确性较高的频繁阂值是基于隐私保护关联规则挖掘的一 大挑战。接下来本文将介绍两个已有的基于隐私保护关联规则挖掘方法 m a s k 和p p r h 方法。 2 4m a s k 方法 该方法由s j r i z v i 和j r h a r i t s a 于2 0 0 2 年提出 f l ，主要应用于 “m a r k e t b a s k e t 事务数据库。该数据库的列由商品名组成，行由每位顾客的购物 行为提供，是固定长度的0 和1 字符串。其中，1 表示购买，0 表示没购买，即 一个顾客元组是一个随即向量x = x 。 ，其中x ，= l 或0 ，从该元组中产生变换 向量x = x j ，其中i = d i s t o r t i o n ( x 。) ，这里定义的变换函数为r = 五肋r i ，i 是r 的补集，满足二项式分布，即以p 的概率取值l ，以1 p 的概率取值0 ，i 表示第i 个商品。一个商品的上述变换过程如表2 - 1 所示。 表2 - 1 单个布尔属性变换过程 一 鬈x i 概率 l10 p o l l 1 - p oo0p 1ol 1 - p 从表2 l 中可以得到第i 个商品以概率p 保持初始值不变，以概率l - - p 转 变成与之相反的布尔值。 1 2 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 假设置为某顾客c 购买第i 件商品的支持度，也可以理解为某顾客c 购买第 i 件商品的概率，现在从变换后的值来重构初始值确实为l 的情况，即某顾客确 实购买第i 件商品的概率。 墨c p ，墨) = e 写= l i 五= 1 0 五= 1 i 耳= l + 0 i = o i 五= 1 ) p 五= l i 耳= o ( 2 1 ) 公式( 2 1 ) 其实就是一个全概然表达式，分别以巧= l 和l ：= o 为情况进行概率 计算，该式简化为： 焉( p ，墨) = p p 瓦= i i 誓= l + ( 1 一p ) 只 五= l i 鬈= o ( 2 - 2 ) 其中 懈- - i i t , - l = 觜= e “= l 只 = t l x , - - 1 - - - - - - - - - - - - - - - - - - - - - - ；- - - - - - - - - - - - - - - - - - 一= ： e l = l j!：!一 e 五= l p r = l l x , = l + e 五= o e z = 1 1 - - 0 同样地 最终，可以得到 墨兰旦 s jx p + ( 1 一墨) ( 1 一p ) e 似= l i t , 2 。 2 而丽s , x 而( 1 - p ) 置( p ，焉) = 瓦两s i t x p 丙2 而+ 再而s x 再( 1 - i i p ) 2 而 2 3 ) 从式( 2 3 ) 可以得到，当数据库中所有项的支持度相同时，值最小现在 取一个所有商品支持度的平均值来计算，重构概率公式变化为： 墨( p ) = 石鬲而$ o x p 丽2 + i 瓦$ 0 x 再( i - 丽p ) 2 ( 2 - 4 ) 以不同的p 值和值做出墨( p ) 的变化图形，如下图所示。 中山大学硕士学位论文 基于隐私保护的关联规则挖掘算法研究 ， 图2 - i 重构概率 从图2 - i 可以看到： ( 1 ) 重构概率值在两端比较高，在中间最低，p = o 5 时取得最小值； ( 2 ) 曲线以p = o 5 为轴对称； ( 3 ) 越小，重构概率越低，而且范围跨度越大。 丑= 0 的情况也可以按照这种方法得出。通常情况下人们都希望对0 和l 赋 予不同的权值，因为l 代表着实际行动，而0 没有意义。 最终得到隐私的度量计算： 以p ) = ( 1 一r ( p ) ) 1 0 0 ( 2 - 5 ) 其中，r ( p ) = 被l ( p ) + ( 1 一口) 民( p ) ，a 为值l 超过值0 的权值。 这样得到不同权值的隐私保持，如图2 2 所示。 | 柏 毒 柚 柚 o i 一 d 厂i矿_ 0r l 厂 弋 f 尸一 1 “嘲_ l - f o0 40 8l ， 图2 - 2 - - - 0 0 1 时的隐私度 1 4 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 从图2 - 2 可以看到在p = o 1 和p = o 9 时隐私保持值很高。通过大量实验数据， 最终证明在p = o 9 时既能保证相当高的隐私保持程度，又能达到满意程度的正确 性。其中的关联规则挖掘采用的是著名的a p f i o r i 算法，先产生候选k 项集，再 产生l 【频繁项集，最后生成强关联规则。 2 5 部分隐藏的随机化回答方法( r r p h ) 该方法由张鹏等在2 0 0 6 年提出的【1 4 1 ，它首先提出将数据干扰和查询限制两 种策略相结合，使之相互弥补，从而提高对隐私保护的程度。 r r p h 在实施挖掘之前。同时对原始数据进行变换和隐藏，而且对随机化参 数的选择也没有任何限制具体方法如下： 给定随机化参数o sp i p 2 p ，l ，且p l + p 2 + n = 1 对于项x 0 , 1 ，设5 = x ， r 2 = l ，r 3 = o ，则随机化函数r ( x ) 以岛的概率选择取值为，j = l ，2 ，3 。设项的 总数为k ，则对于用。一l 序列表示的事务x _ “，屯，黾) ，干扰后的事务 y 三锄，段，欺) 可以通过y = r ( x ) 计算得到，其中m 呵“) 也就是说tm 以p l 的概率取值为毛，以p ：的概率取值为l ，以n 的概率取值为o 。可以看出，当咒以 p ：或n 的概率选择b 或5 来进行随机化回答的时候，相应的事务被完全隐藏起 来。这样，对事务集d 中的每一个事务x ，经过随机化函数r 的处理得到y ，而且 由于y 在形式上仍然是一个与x 长度相同的0 1 序列，所以就可以作为一个伪造的 事务加入到伪造的事务集d ，中。从表2 2 可以看到p p r h 方法的数据映射概率。 中山大学硕士学位论文 基于隐私保护的关联规则挖掘算法研究 31o 见 4 1l n + p 2 由数据映射概率，可以得到从伪造事务集的项集支持度中估算出真实支持度 的公式。 ( 1 ) 对于频繁1 项集： a = 石x ( p i + p 2 ) + ( 1 一丌) p 2 = 万p l + 见 于是， 万：尘尘( 2 - 6 20 ) 万= 二三j a 其中，f 是一个项，冗表示d 中f 的支持度，九表示d ，中i 的支持度。 ( 2 ) 对于频繁k - 项集，由于各项集是独立地进行随机转换的，因此k 项集的转 换概率由各项集转换概率相乘获得。因此可以得到k 项集真实支持度的估算公 式： c = m 一1 c ( 2 7 ) 其中c 与c 分别表示由k - 项集的各0 1 序列组合在真实与伪造事务集中的支持数 所构成的列矩阵。m 为数据在各o 1 序列组合间转换的概率所组成的 ( 2 一1 ) x ( 2 一1 ) 矩阵。 利用以上两条估算公式，可以得出在伪造事务集中进行频繁项集的挖掘算 法。 算法：面向经过r r p h 方法处理的数据生成频繁项集。 输入：r r p h 方法处理后的事务集d ，最小支持度阈值s 。 输出：d 中的频繁项集l 。 ( 1 ) s c a nd ，f o re a c hi t e mi ic o u n ti n o u n t ； 对每个项i 计数 ( 2 ) 厶= f l f ，( ( i w o u n t i v ) 一p 2 ) i p l j ； ( 3 ) f o r ( k = 2 ；一l o ；七+ + ) ) ( 4 ) g = a p r o i r i g e n ( l , 一1 ) ； 生成候选k 项集c k 1 6 中山大学硕士学位论文 基于隐私保护的关联规则挖掘算法研究 ( 5 ) ( 6 ) ( 7 ) f o re a c ht r a n s a c t i o nfed f o r0 = l ；j g 【；j + d c j = p a r t i a l s u b s e t ( c k ，t ，力) ； ，摩务t 中恰好包匈 项的候选k 项集 f o re a c hc a n d i d a t e c c , j c 肋峭+ + ； f o r e a c h c a n d i d a t ec e g c z o u n t = 一c l ，+ q j c l 们 + + q f 堋； 厶= 斜i c g ，聊删j ； ( 1 5 ) ( 1 6 ) ( 1 7 ) 坞t i l m 工= k t 丘 通过合理的随机化参数选择，p p r h 方法能在相同时间和空间开销的条件下， 得到m a s k 方法更好的隐私性和准确性。但由于在r r p h 方法中当选择p 。对数据 回答时，回答的结果都是真实的数据，即实际上并没有将这部分数据进行干扰， 使到数据的隐私程度不能很好地得到保护。而且由于算法在对伪造数据库进行频 繁项集挖掘时是完全基于a p f i o f i 算法思想的，因此造成了由k 1 频繁项集生成k 频 繁项集时的挖掘误差传递。所以本文将在运用这种新的结合策略的基础上，弥补 p p r h 方法的这些不足之处，提出一个更为有效的隐私保护关联规则挖掘方法一 部分隐藏的转移概率矩阵( p h t p m ) 方法。 2 6 相关概念定义 1 7 ， ， d ” ” d n n n n n 中山大学硕士学位论文基于隐私保护的关联规则挖掘算法研究 本节将定义一些在用部分隐藏的转移概率矩阵进行数据变换时需要用到的 相关定义和属性。 定义l 单属性转移概率矩阵1 5 j 用a 来表示记录的某个属性，属性a 共有n 个不同的取值a 。( 1 ，s 行) ；定 义属性a 的转移概率矩阵只为 2 l l 五l 五。1 五。 厶( 1 s 七s 以，1 s ，n ) 表示为属性之从q 变为q