（计算机软件与理论专业论文）面向关联规则挖掘的隐私保护.pdf

摘要 摘要 由于数据挖掘是从大量真实数据中提取有价值的知识，在数据挖掘的过程中 很可能会引发敏感信息的泄露，这就带来了隐私保护方面的诸多问题。因此，如 何在保护隐私的同时得到满意的挖掘结果成为数据挖掘领域的一个焦点，其中倍 受关注的分支之一是关联规则挖掘的隐私保护。在关联规则挖掘过程中，某些属 性的具体取值或是挖掘获得的关联规则关系到数据提供者的个人隐私，这样的信 息是应该受到保护的。 本文分别研究了针对静态数据库和数据流上关联规则挖掘的隐私保护。 在静态数据库关联规则挖掘的隐私保护领域，针对那些侵犯隐私的规则已经 提出了一些敏感规则的隐藏方法，但是这些方法并没有把隐藏规则带来的影响以 及对规则的恶意重构作为重点考虑。然而这两方面对于最终的挖掘结果和隐私保 护策略的有效性都有十分重要的影响。 在数据流上进行数据挖掘隐私保护的工作还很少。由于流数据的特殊性质使 得处理流数据成为一项很复杂的工作，因此既要保证满意的挖掘结果，还要考虑 隐私保护就给研究工作提出了更大的挑战。 本文的主要贡献和创新总结如下： 采用减小项集支持度和减小规则置信度两种方法结合使用的策略，对敏感规 则进行隐藏。详细分析了数据转换给原始数据集合带来的影响并定义了一个 修复参数，用来减小数据转换对数据质量的影响。 基于对静态数据库数据挖掘隐私保护技术的研究，提出了数据流上关联规则 挖掘隐私保护的解决方案。利用一个随机函数对原始数据进行转换，在转换 后的数据集上利用支持度恢复算法将项集的近似原始支持度恢复出来，从而 达到数据流上隐私保护的关联规则挖掘。 初步的实验证明了本文提出的两种方法的可行性，有效性和正确性。提出的 敏感规则隐藏策略达到了：既不暴露敏感规则，又有效地抑制了挖掘者的恶 意重构。针对数据流上关流规则挖掘的隐私保护算法在不显著增加时间空间 耗费的前提下，达到了数据流上挖掘关联规则的隐私保护目的，并具有较高 的正确性和效率。 关键词数据挖掘，关联规则挖掘，隐私保护，敏感规则，数据流 a b s t r a c t a b s t r a c t d a t am i n i n gi su s e dt om i n ev a l u a b l ek n o w l e d g eb a s e do ng r e a ta m o u n to f t r u e d a t a ，b u tl a r g er e p o s i t o r i e so fd a t ac o n t a i ns e n s i t i v ei n f o r m a t i o n ，i ti sas e r i o u st h r e a t t od a t ap r o v i d e r s ot h i sk i n do fi n f o r m a t i o nm u s tb ep r o t e c t e da g a i n s tu n a u t h o r i z e d a c c e s s t h ep r o t e c t i o no f p r i v a t ei n f o r m a t i o nh a sb e e nal o n g t e r mg o a li nd a t am i n i n g o n eo ft h er e s e a r c hi s s u e si sp 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 i nt h e p r o c e s so fa s s o c i a t i o nr u l em i n i n g ，s o m ev a l u e so fa na t t r i b u t eo rs o m eo fm i n i n g r e s u l t sa r er e l a t i v et op r i v a c y ，s ot h e ys h o u l db ep r o t e c t e d i nt h i st h e s i s ，w es t u d yp 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 i d em i n i n go f b o t hs t a t i c d a t a b a s e sa n dd a t as t r e a m s i nt h ef i e l do f 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 gi nd a t a b a s e s ，t h e r ea r e s o m em e t h o d st oh i d ep r i v a c yr e l a t e dr u l e s b u tm o s to f t h et e c h n i q u e sd on o ta t t a c h i m p o r t a n c et op r o b l e m so f i n f l u e n c eo no r i g i n a ld a t as e ta f t e rr a n d o m i z a t i o na n dt h e a d v e r s a r y sr e c o n s t r u c t i o no f t h eh i d d e nr u l e s f u r t h e r m o r e ，t h e r ea r el i t t l es t u d i e sc o n s i d e ra b o u tp r i v a c yp r e s e r v i n gm i n i n g a s s o c i a t i o nr u l e sf r o md a t as t r e a m s i ti sk j n do f b e c a u s et h ep a r t i c u l a rc h a r a c t e r i s t i c s o fs t r e a m i n gd a t a t h es p e c i f i cc o n t r i b u t i o n sa n di n n o v a t i o n sa r ea sf o l l o w s ： a s t r a t e g yw h i c hc o m b i n e sm e t h o d so fd e c r e a s i n gs u p p o r ta n dd e c r e a s i n g c o n f i d e n c ei su s e dt oh i d es e n s i t i v er u l e s w em a k ead e t a i la n a l y s i sa b o u tt h e i n f l u e n c eo fd a t ad i s t o r t i o n ，b a s e do nw h i c har e n o v a t i n gp a r a m e t e ri sp r o v i d e dt o r e d u c es i d ee f f e c td e r i v e df r o mt h ed a t ad i s t o r t i o n b a s e do nt h es t u d i e so fs t a t i cd a t a b a s ep r i v a c yp r e s e r v i n gt e c h n i q u e s am o d e lo f p r i v a c yp r e s e r v i n gm i n i n ga s s o c i a t i o nr u l e sf r o md a t as t r e a m si sp r e s e n t e d a f t e r d i s t o r t i o nb yar a n d o m i z e df u n c t i o n ，an o v e ls u p p o r tr e c o v e r i n ga l g o r i t h mi su s e d t oc a l c u l a t et h eo r i g i n a ls u p p o r t so f f r e q u e n ti t e ms e t s i nt h i sw a y ，t h ep 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 em i n i n go v e rd a t as t r e a m si sa c h i e v e d p r e l i m i n a r ye x p e r i m e n t ss h o wt h a to u rm e t h o d sa r ef e a s i b l e e f f i c i e n ta n d e f f e c t i v e u s i n gt h es e n s i t i v er u l eh i d i n gm e t h o d ，w ec a ng u a r a n t e et h a tt h e p r i v a c yi sp r e s e r v e d a l s ot h ea d v e r s a r y sr e c o n s t r u c t i o ni se f f e c t i v e l yr e s t r a i n e d t h ep r i v a c yp r e s e r v i n ga l g o r i t h mo v e rd a t as t r e a m sp r o t e c tt h ep r i v a t e i n f o r m a t i o n ，b u td o e sn o ti n c r e a s em u c hc o s to ft i m ea n ds p a c e a l s o ，g o o d 2 垒! 壁! ! 壁 _ - - _ _ - _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - - h _ _ _ _ - _ _ _ _ _ _ _ _ _ m i n i n gr e s u l t sa r eg u a r a n t e e d k e y w o r d sd a t am i n i n g ，p r i v a c yp r e s e r v a t i o n ，s e n s i t i v er u l e ，d a t as t r e a m 第一章绪论 1 1 数据挖掘简介 第一章绪论 数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识 别有效的、新颖的、潜在有用的，以及最终可理解的模式的过程。它是- j q 涉 及面广泛的交叉学科，包括机器学习、数理统计、神经网络、数据库、模式识 别、粗糙集、模糊数学等相关技术。 数据挖掘可以在任何类型的信息存储上进行。这包括关系数据库、数据仓 库、事务数据库、高级数据库系统、展开文件和w w w 。高级数据库系统包括 面向对象和对象一关系数据库；面向特殊应用的数据库，如空间数据库、时间序 列数据库、文本数据库和多媒体数据库。 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务 一般可以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特 性。预测性挖掘任务是在当前数据上进行推断，以进行预测。 在某些情况下，用户不知道他们的数据中什么类型的模式是有趣的，因此 可能想并行搜索多种不同的模式。这样，数据挖掘系统要能够挖掘多种类型的 模式，以适应不同的用户需求或不同的应用。此外，数据挖掘系统应当能够发 现各种粒度的模式。数据挖掘系统应当允许用户给出参数，指导或聚焦有趣模 式的搜索。由于有些模式并非对数据库中的所有数据都成立，通常每个被发现 的模式带上一个确定性或可信性度量参数。 数据挖掘所发现的模式类型最常见的有以下五类：广义知识、关联知识、分 类知识、预测型知识和偏差型知识。 ( 1 ) 广义知识是指类别特征的概括性描述知识。根据数据的微观特性发现其表 征的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事 物共同性质，是对数据的概括、精炼和抽象。 ( 2 ) 关联知识反映的是一个事件与其他事件之间的依赖或关联关系的知识。如 果两项或多项属性之间存在关联，那么其中一项的属性值就可以依据其他 属性值进行预测。最为著名的关联规则发现方法是r a g r a w a l 提出的 a p r i o r i 算法。 ( 3 ) 分类知识反映的是同类事物共同性质的特征型知识和不同事物之间的差 异型特征知识。最为典型的分类方法是基于决策树( d e c i s i o n t r e e ) 的分 类方法。 第一章绪论 ( 4 ) 预测型知识根据时间序列型数据，由历史的和当前的数据去推测未来的数 据，也可以认为是以时间为关键属性的关联知识。 ( 5 ) 偏差型知识是对差异和极端特例的描述，揭示事物偏离常规的异常现象， 如标准类外的特例，数据聚类外的离群点( o u t l i e r ) 等。 数据挖掘的过程是个非常复杂的过程，涉及到确定挖掘目标、数据准备、建 立模型、数据挖掘、结果分析等多个环节，需要严格地按照规范的操作方式有步 骤地进行才能达到数据挖掘的最终目的，利用数据结果提供决策支持。下图是一 个标准的数据挖掘过程示意图： 1 2 关联规则挖掘简介 图1 1 数据挖掘过程 大量数据之间的关联关系的发现在选择购物、决策分析和商务管理方面是很 有用的。关联规则挖掘是发现大量数据中项集之间有价值关联的过程。一个典型 的例子是购物篮分析。通过发现顾客放入购物篮中不同商品之间的联系，来分析 顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，可以帮助零售商制 定营销策略。例如，将顾客经常打包购买的商品放在一起可以进步刺激这些商 品的同时购买。 关联规则的形式化描述如下： 设i = i i ，i 2 ，i m ) 是项的集合，数据d 是数据库事务的集合，其中每个事务 t 是项的集合，满足t 1 。每个事务有一个标识符，称作t i d 。设a 是一个项 集，事务t 支持a 当且仅当a t 。关联规则是形如a = b 的蕴涵式，其中a 匕i ， b ，并且4 n b = 西。 第一章绪论 定义1 ，1 项集a 的支持度s u p p o r t ( a ) 是包含a 的事务t 在事务数据库d 中出 现的次数同d 中事务总数的比值，即： s u p p o r t c 舻皆 定义1 2 规则a = b 的置信度定义为在条件a 成立的前提下b 也成立的条 件概率，即： c 。够如n r ( 爿= b ) = ! ! ：黜 支持度和置信度是关联规则挖掘中两个很重要的参数。支持度表示规则的频 繁性；置信度表示项集之间的关联，它们分别反映规则的有用性和确定性。关联 规则挖掘的目的就是发现同时满足最小支持度阈值和最小置信度阈值的规则，这 两个阂值可以由用户或领域专家设定。 如果规则a = b 在事务集d 中成立，需要满足置信度大于最小置信度阂值c 即c o f i d e n t ( a = b ) c ( 其中指的是数据集合d 中包含项集a 的事务个数) 。 当s u p p o ( a u b l s 时，a = b 的支持度需要满足最小支持度阈值s 。 关联规则的挖掘是一个两步的过程： 第步：找出所有频繁项集：根据定义，这些项集出现的频繁行至少和预定 的最小支持度计数一样。 第二步：由频繁项集产生强关联规则：根据定义，这些规则必须满足最小置 信度闽值。 比较经典的关联规则挖掘算法有f p g r o w t h 和a p f i o f i 算法。 1 3 数据挖掘的研究现状 随着数据处理、先进数据库技术以及机网络技术等的迅速发展，涌现出了许 多与数据挖掘相关新的研究方向。其中数据挖掘的隐私保护和数据流挖掘方向已 经为许多人所重视。 1 3 1 数据挖掘的隐私保护 数据挖掘确实在深层次的趋势指导应用中发挥了积极的作用，但与此同时也 带来了隐私保护方面的诸多问题。比如对于金融交易、医疗记泉和网络通信等数 据，在挖掘的过程中很可能会引发敏感信息的泄露。早在1 9 9 8 年，a n nc a v o u k i a n 第一章绪论 发表了一篇题为数据挖掘：以破坏隐私为代价的报告，引起了很大的轰动。 该报告剖析了数据挖掘和隐私的关系，指出数据挖掘可能是个人隐私提倡者未来 十年所要面对的“最根本的挑战”，从那时起隐私问题就成为让数据挖掘者窘迫 的雷区。 基于网络技术，个人数据信息的传播范围大、速度快、影响广。这些个人数 据信息可以被利用者出于各种目的进行收集、整理、利用或者转让，更可能被恶 意者获取，作为非正当用途的工具。所以在国际上一系列关于数据隐私权保护的 规范中阐述了若干己被普遍遵守的核心原则。包括：1 ) 目的的说明和使用限制， 收集数据的时候必须指定数据的使用目的，不能超出此目的范围使用数据。2 ) 公开性，数据提供者有权利知道关于他们的何种信息被收集，由谁访问以及数据 如何被使用。依据这些原则，在挖掘收集到的信息时必须考虑如何进行隐私保护。 这就产生了数据挖掘中隐私保护的问题，即如何在保证个人隐私的前提下进行数 据挖掘。 r a g r a w a l 等人于2 0 0 0 年首次提出了数据挖掘中的隐私保护 ( p r i v a c y p r e s e r v i n g ) 问题 a s 0 0 1 。这篇文章是针对决策树分类算法提出的隐私 保护策略。逐渐地，各种隐私保护技术应用到了数据挖掘的各个分支，包括分类 a s 0 0 ，c m 9 8 ，d z 0 2 】、聚类 c k l + 0 2 ，k g k + 0 3 】、关联规则挖掘 r h 0 2 ，s v e 0 2 ， e s a 十0 2 ，v e e + 0 0 ，s v c 0 1 ，o z 0 2 等。 已经有很多保护敏感信息的方法被提出，包括对数据进行转换、数据抽样等。 但是不论采用哪种方式进行隐私保护，都会对数据质量产生不同程度的破坏，因 此在隐私保护的同时必须考虑对挖掘结果的影响。挖掘结果的正确性、有效性是 挖掘者的最终目的，而隐私保护是数据提供者的需求，这两点都要考虑。 c l i f t o n 在 c c 9 9 1 中采用的是抽样方法，研究了提供给挖掘者的抽样数据量与 挖掘模式价值之间的关联。他还说明了如何决定抽样数据的大小才能得到比较好 的挖掘结果。 a g r a w a l 和s r i k a n t 采用数据混淆的方法对敏感数据的取值进行变换，这样在 保护隐私的同时获得了接近准确的挖掘结果 a s 0 0 】。数据挖掘算法的分析是隐私 保护应该考虑的第一步。他们的方法是对原始数据加上服从某种分布( 均匀分布 或正态分布) 的噪声数据，从而得到了可以认为是不会泄露原始数据信息的扭曲 数据。然后利用扭曲数据的值以及噪声数据的分布”通过b a y e s 法则构建原始数 据的近似分布。 n a g r a w a l 和a g g a r w a l 在他们的文章中提出了利用最大化期望值来重构原始 数据的分布用以得到更正确的分类模型 a a 0 1 1 。它更有效的实现了分布重构，最 大可能的使重构分布接近于原始数据的分布，降低了信息丢失的程度。同时，提 第一章绪论 出了一个很好的隐私定义和衡量隐私的方法。 c l i f t o n 和m a r k s 在 c m 9 6 伸指出挖掘算法与保护策略间的联系是十分值得 研究的。如果挖掘结果的正确性闽值已知，就比较容易确定如何进行隐私保护。 在 c c 9 9 1 中提出的方法与挖掘技术是无关的，而在其他一些文章 a b e + 9 9 ，j r 9 9 中提出了针对于某类挖掘( 分类挖掘、关联规则挖掘等) 的保护算法。 此外，在很多情况下用户不愿意提供个人信息，除非确保隐私不被泄露，这 样就需要保证有效的数据收集，因此数据收集和挖掘方法的研究成为一个焦点： p b 9 9 ， l c l 8 5 ， l e w 9 9 】。 1 3 2 数据流挖掘 随着信息处理在更多领域的广泛应用，数据已经不仅仅拘泥于文件、数据库 等静态形式。连续、无限、快速的数据流型数据已经出现越来越多的应用领域。 例如：电子商务，无线电通信、工业生产等领域，数据增长的速度远远超出了人 们的想象。尽管在这些大量、异质的数据信息资源中蕴涵着具有巨大潜在价值的 知识，但是它们的体积过于庞大，还在无限、高速地增长，数据更新速度很快， 所以在这类数据中挖掘有价值的模式就变得尤为重要。传统的数据挖掘方法认为 数据是从静态的、有限的数据空间中挖掘出来的。随着数据以流的形式出现，数 据挖掘需要面临内存和运行时间的挑战。 数据流和静态数据集合是不同的数据模型。在数据流模型下，输入数据不能 从磁盘或内存随机访问，它们是以连续的“流”的形式出现的，存储也不同于传 统的存储方式。“流”数据的主要特点有： ( 1 ) 时效性：数据流中的数据携带事件的时间特性。 ( 2 ) 实时性：数据流中的数据要求实时处理。这就对数据处理速度提出了挑战。 数据流挖掘算法的处理速度一定要能够跟上数据项到达的速度。 ( 3 ) 无限性：数据流随时间而源源不断，意味着数据流量的无限性。 ( 4 ) 瞬间性：数据流中的数据除非进行特殊存储，否则流过后不可能再次访问， 也就是说对数据只能进行单次扫描。此外，无限性决定了数据流是不可能 完全存储的。通常，内存中放置的是数据集的概要信息。 最早的数据流挖掘方法采用：把不能存放到内存中的数据先存至磁盘中，然 后连续多次访问磁盘来进行数据挖掘。但是这样的处理办法速度太慢，远远低于 数据的增长速度。大量的未处理数据堆积在磁盘上，即使当它们被处理的时候， 也可能变的没有任何应用意义了。所以对无限的数据流的挖掘算法成为许多研究 的焦点。 一个可行的数据流挖掘算法要满足一定的条件： 第一章绪论 ( 1 ) 用尽量短并且连续的时间段来处理每一条记录，否则就会造成大量数据 的堆积。 ( 2 ) 用有限的内存处理所有的数据。 ( 3 ) 简历模型的时候对数据最多只扫描一次。因为数据以流的形式到达，算 法没有时间重复访问旧的数据。 ( 4 ) 算法对数据流中的每一条记录的都要适用，没有任何偏好。 ( 5 )要能够产生一个高质量的模型。这个模型至少要和静态数据挖掘达到相 同的目的。 ( 6 ) 当数据源变化的时候，己经建立好的数据模型要随之更新以适应新的数 据。 现有的研究中已经提出了很多数据流挖掘的算法：关联规则挖掘 c c f 0 2 ， d g i + 0 2 ，m m 0 2 ，j c l + 0 4 、决策树【j a 0 3 ，w f y + 0 3 】、数据流聚类 a h w + 0 3 ， a h w + 0 4 。 然而，目前还没有对于数据流上关联规则挖掘的隐私保护研究。随着基于数 据流的应用越来越广泛，数据流上数据挖掘的隐私保护也会逐渐成为研究焦点。 要达到数据流上隐私保护的挖掘目的必须满足：在不明显增加时间和空间开销的 基础上从大量的“流”数据中发现频繁项集i 同时满足数据提供者对隐私的要求。 1 4 本文的目标和研究内容 根据上面的描述，本文的研究目的是：i ) 基于对数据质量和重构可能性的 分析研究更有效的敏感规则隐藏技术，既满足敏感规则的有效隐藏，又降低了重 构敏感规则的可能性。2 ) 研究数据流上关联规则挖掘隐私保护技术。在不显著 增加时空耗费的前提下，既保证挖掘结果的正确性，又满足隐私保护需求。本文 的工作如下： 提出了一种新的敏感规则隐藏的算法。将减小项集支持度和减小规则置信度 两种方法结合使用，提出了一种新的策略对敏感规则进行隐藏。最终达到既 不暴露敏感规则，又有效地抑止了挖掘者的恶意重构。 详细地分析了数据转换给原始数据集合带来的影响，给出了公式画的分析结 果。基于该分析提出了一个修复参数，用来减小数据转换给原始数据集合带 来的影响。在挖掘转换后的数据库时，利用这个修复参数对规则的支持度和 置信度做调整，以达到最好的挖掘结果。 基于对静态数据库的数据挖掘隐私保护技术的研究，提出了实现数据流上关 联规则挖掘隐私保护的解决方案。利用一个随机函数对原始数据进行转换， 在转换后的数据集上利用提出的支持度恢复算法近似恢复出项集的原始支 第一章绪论 持度，从而达到数据流上隐私保护的关联规则挖掘。 1 5 本文结构 第二章描述了数据挖掘隐私保护的发展以及研究过程。第三章提出静态数据 库中敏感规则的保护方法，并对该方法给数据质量带来的影响做了详细地分析。 第四章提出了数据流上隐私保护地挖掘关联规则的算法，并通过实验从时间耗 费、空间耗费以及算法挖掘正确性等方面证明了算法的有效性。第五章对全文进 行总结。 第二章背景及相关工作 第二章背景及相关工作 2 1 涉及隐私的应用 随着数据挖掘技术的发展，大量的私人信息如购物习惯、犯罪记录、病史、 信用卡使用记录等，通过应用数据挖掘技术被广泛的收集和分析。一方面。这些 数据对于政府、商业组织决策和提供社会福利如医疗研究、减少犯罪、国家安全 等是很重要的。另一方面，因为数据挖掘揭示了不容易发现的模式或各种知识， 如果不能正确使用的话，它可能对隐私和信息安全构成威胁。公开分析大量的私 人数据还可能是对个人隐私的一种侵犯。在数据挖掘工具和电信与计算机网络曰 益普及的今天，数据挖掘要面对的一个重要问题是隐私保护和信息安全，开发有 关的方法以便在适当的信息访问和挖掘过程中确保隐私保护和信息安全变得十 分迫切。 信息技术的突飞猛进使得有关隐私的话题也发生了飞速的变化。一般认为， 隐私是指有关生活领域中比较个人的事情。而网络环境中，最容易受到侵犯的是 资料隐私权。对其侵害的特征是对个人数据信息的非法收集、利用或篡改、窃取 1 9 9 5 年7 月，欧洲联盟数据保护规章给个人数据下的定义是：有关一个人被 识别或可识别的自然人的任何信息，包括身体的、生理的、经济的、文化的、社 会的。因此，个人数据信息的范围非常广泛，并与“个人”有关。他人可以借助 这些数据来对数据主体加以识别。 在数据挖掘中，涉及隐私的应用主要有： ( 1 ) 个公司为了更好地管理客户，需要对收集到的数据进行挖掘。这时， 数据源中可含有能够识别客户身份的一些标识，例如姓名、地址、电话号码等。 泄露这些信息可能侵犯了客户的隐私。当然，为了符合隐私管理的要求，安全管 理员可能会从客户记录中删除这些标识。但是，释放的数据也不一定被完全保护。 客户的记录可能包含一些可以连接到其他数据库，可以识别出客户身份的信息。 当这些数据被合并使用时，就容易侵犯客户的隐私。 ( 2 ) 两个或更多的公司有一个记录了顾客购买活动的数据库，为了他们的共 同利益，这些公司决定合作在他们的数据库中进行关联规则挖掘。然而，其中一 些公司不想公开他们数据库中的一些战略性模式给其他公司。他们想通过转换数 据来使得战略性模式隐藏，而其他的模式与其他公司分享。此时，如果无法隐藏 战略性模式也是对隐私的侵犯。 ， 第二章背景及相关工作 2 2 隐私保护方法的分类 目前存在很多种数据挖掘隐私保护的方法，我们可以按照以下几种标准对其 进行划分： ( 1 ) 数据分布：每个数据挖掘的参与者都只拥有一部分原始数据，挖掘者通过 协同的分布式计算得到所需的挖掘结果。v c 0 2 ，k c 0 2 两篇文章分别提出 了基于水平划分和垂直划分的隐私保护关联规则挖掘方法。水平划分就是 每个站点只保留部分数据记录；垂直划分就是将记录的不同属性分布在不 同的站点。 ( 2 ) 数据扰乱：通过预定义的转换来改变原始数据，将变换后的数据提供给挖 掘者进行分析。对转换方法的要求是：从变换后的数据中不能推算出原始 数据，即保证隐私度；同时，转换方法只改变单个属性值，不改变整体的 变化趋势，从而确保挖掘结果的正确性。数据扰乱具体方法主要包括：a ) 随机化方法：为数据增加噪声以保护真实数据不被发现，如文献 r h 0 2 ， k d w + 0 3 中的方法。b ) 交换法：将数据记录间的属性取值进行交换 【e c b 9 9 1 。c ) 抽样法：从原始数据中的抽样一部分提供给挖掘者。 ( 3 ) 隐藏目的：在隐私保护的过程中选择隐藏个人数据还是概括信息。在些 应用中，需要对某些属性的特殊取值进行隐藏，这属于数据的隐藏 a s 0 0 ， r h 0 2 ，e c b 9 9 】。通常，可以利用随机函数对原始数据进行转换，然后提 供给挖掘者，在转换后的数据库中，挖掘者仍然能够得到满意的结果。而 另外一些应用下需要对聚合数据( 中间结果或挖掘结果等) 进行保护和隐 藏，这属于对概括信息的隐藏 8 s 9 8 ，v e e + 0 0 ，s v c 0 1 ，s v e 0 2 ，b a 0 5 1 。对 于关联规则挖掘，按照隐藏目的隐私保护方法可以分为两类：一类是保护 单项的隐私信息，比如用户的年龄或住址是不希望被公开的。另一类是保 护挖掘结果。在挖掘结果中存在一些规则是关系到隐私的，我们称这类规 则是敏感规则。比如通过一个病人购买药物的记录可以推断出他的病症 等。如果这样的规则被挖掘出来将会泄漏数据提供者的隐私信息，针对这 类问题的就是敏感规则的保护，这是本文研究的目标之一。 2 3 关联规则挖掘中隐私保护的相关工作 2 3 1 静态数据库中敏感规则的保护 根据关联规则的定义，有两种方法可以隐藏敏感规则：减小频繁项集的支持 2 第二章背景及相关工作 度至最小支持度阂值( m s t ) 以下或减小规则置信度至最小置信度( m c t ) 以下a 下面简单介绍这两种方法。 首先考虑减小规则支持度的方法。对于规则a = b 求解其支持度的公式为 攀。由于i d l 是数据集合中含有事务的总个数，是一个常数，所以要减小支 l 川l 持度只能通过减小分子l 爿u 曰 来实现。可以减小同时支持项集a 和项集b 的事 务的个数达到。 其次考虑采用减小规则置信度的方法来隐藏规则a = b 。求解置信度的公式 为掣，可见能够通过减小l 爿u b i 或增大l a l 来减小规则的置信度。但是， a 1 需要注意的是公式中的分子和分母是有关联的。( a ) 减小分子的同时保持分母不 变，减小事务中b 部分的项集个数。( b ) 增大分母取值，即增加支持项集a 的 事务个数。 最初的一些方法，只是通过减小频繁项集的支持度( 1 变为o ) 隐藏敏感 规则。这样会导致对挖掘结果带来的影响：不敏感的规则被错误地隐藏。而在 v e e + 0 0 中，提出：既可以减小敏感规则的支持度，也可以通过减小置信度( 1 变为0 或者0 变为l ) 使其隐藏。这样对挖掘结果正确性的影响表现为：隐藏 了不敏感的规则或是引入错误的规则。 文献 s w 0 2 提出，把“敏感水平”( s e n s i t i v el e v e l ) 作为关联规则的又一 个衡量尺度。用它来说明一个规则是否敏感，当一个规则的支持度和置信度均小 于最小支持度阈值和最小置信度阈值时，它不是敏感的，也就是说规则的敏感性 与支持度和置信度相关。因此可以通过减小支持度或置信度来隐藏敏感规则。 【s v e 0 2 中引入了一种新的项取值：? ，这样数据库中就出现了三种取值： 0 ， 1 ，? 。当一个事务数据的某项标记为? 时，表示不能确定事务中是否包含该项 即表示取值的不确定性。用? 代替真实的取值( o 和1 ) 来产生转换后的数据 集，既实现了敏感规则的隐藏，又使数据的改变对其他规则挖掘的影响较小。 s v e 0 2 】中提出了两类( 仅让n 0 变化为? 或仅让1 1 变化为? ) 三个方法来隐 藏敏感规则。 由于引入了取值? ，规则的支持度和置信度由一个确切的数值变为一个取 值区间。于是有了两个新的定义：支持度区间和置信度区间。 支持度区间定义为 m i n s u p ，m a x s u p 。对于一个项集a ，它的最小支持度 m i n s u p ( a ) 等同于原来支持度的定义即a 中所有项为1 1 的事务的比例；而最大支 持度m a x s u p ( a ) 指 a 中所有项为1 或? 的事务的比例。 第二章背景及相关工作 置信度区间定义为 m i n c o n f , m a x c o n f 。对一个规则a j b ，它的最小置信度 m i n c o n f ( a j b ) 定义为m i n s u p ( a b ) m a x s u p ( a ) ；最大置信度m a x c o n f ( a j b ) 定义 为m a x s u p ( a b ) m i n s u p ( a ) 。最初数据集合中不含? 时，m i n s u p = m a x s u p 且 m i n c o n f = m a x c o n f ，在隐藏规则的过程钟，区间的范围逐渐扩大，随之规则的不 确定性逐渐增大。 对于一个项集a ，它的支持度取值有如下几种情况( m s t 表示最小支持度阕 值；m c t 表示最小置信度闽值) ： ( 1 ) 当m i n s u p ( a ) - m s t 时，a 是敏感的； ( 2 ) 当m a x s u p ( a ) m s t 时，a 是不敏感的； ( 3 ) 当m i n s u p ( a ) m s t m a x s u p ( a ) 时，a 在某种程度上是敏感的。 对于置信度区间有同样的特征。 当个敏感规则r 满足m i n s u p ( r ) m s t m a x s u p ( o 或m i n c o n f ( r ) m c t 兰 m a x c o n f ( r ) 时，就说这个规则被隐藏了。因此有两类方法隐藏一个规贝i i s v e 0 2 】： 一是使它的最小支持度小于m s t ；一是使它的最小置信度小于m c t 。 通过减小最小支持度隐藏一个规则r ( 形如i r jr ，1 ，是r 的前件，r ，是r 的 后件) 的方法就是减少支持它的频繁项集的个数，即把支持这个规则的事务中相 应某项的l 变为? ，直至m i n s u p ( r ) m s t 。而对减小m i n c o n f ( r ) 的方法，由于 m i n c o n f ( r ) = m i n s u l ：l ( r ) m a x s u p ( 1 0 ，又有两种算法：一是减小m i n s u p ( r ) ，一是增大 m a x s u p ( 1 0 。第一种算法：首先产生事务集合t r ，包含完全支持r 的事务。然后， 对t r 中的事务，将r 中的某项1 变为? ，直至m i n c o n f ( r ) m c t 。第二种算法： 首先产生事务集合t 包含部分支持1 ，的事务。然后，对于t i 。中的事务，将其 目前不支持的l ，所对应的若干项n 0 变为? ，直至m i n c o n f ( r ) m c t 。 例如：要隐藏的规则是a b j c ，事务数据集如表3 1 ，表中的每一行代表一 个事务，每一列代表一项。( 设m s t = 3 0 ，m c t - - 4 5 ) 。 表3 1 事务数据示例1 t i d ab c t l 11 1 t 21l1 t 31l1 t 4 11 o t 5 o0 o 若减小m i n s u p ( a b c ) ，可以将t 1 的a ，b ，c 取值变为( 1 ，1 ，? ) ，则 m i n s u p ( a b c ) = 2 0 m s t , a b j c 被隐藏。若增大m a x s u p ( a b ) ，可以将t 5 的 第二章背景及相关工作 a ，b ，c 取值变为( ? ，? ，0 ) ，则m i n c o n f ( a b j c ) = 4 0 m c na b j c 被隐藏。 然而，只在数据集上使用一种隐藏算法会让挖掘者比较容易地重构出被隐藏 的敏感规则 s v c 0 1 。而且，由于数据挖掘的目的是发现正确的知识，所以还需 要考虑数据变换对挖掘结果的影响。针对这些问题本文提出一种改良算法，使变 换后数据库中的? 既有一0 转换来的又有1 转换来的，既保证敏感规则的有效隐 藏，又降低了重构敏感规则的可能性。在详细分析负面影响的前提下，提供给挖 掘者一个修复参数p ( 表示一个? 取值为l 的概率) ，以减小这种变换对原始数 据库的影响。当按照这个参数进行挖掘时负面影响是最小的，即在不暴露敏感规 则的基础上挖掘出大部分有价值的规则，且引进最少的错误规则。 2 3 2 数据流上关联规则挖掘的隐私保护 随着数据流应用的不断增多，对数据流挖掘方面的研究也愈演愈烈。区别于 传统的静态数据，“流”数据具有连续、无界及实时的特点，因此这类数据的挖 掘对处理时间和内存要求比较高。目前已经出现了很多数据流挖掘的算法，比如： 数据流上的频项集挖掘 m m 0 2 ，j c l + 0 4 干n 聚类 a h w + 0 3 ，a h w + 0 4 等。然而，还 没有对于数据流挖掘隐私保护的研究。 现有的工作都是针对静态数据( 数据库、文本等) 的挖掘操作进行隐私保护， 然而这些方法不适用于“流”数据，这是由“流”数据的特殊性质决定的。在静 态数据库挖掘的隐私保护研究工作中，文献 r h 0 2 1 的隐私保护策略对本文数据流 上关联规则挖掘的保护方法提供了很大启发。【r h 0 2 中提出用一个转换函数对原 始数据x = x i ) 进行变化，最终变为y i = x ix o rr t ( 是r 的补) 。x 和y 分 别表示进行数据转换前后的某一条记录。r i 表示概率密度函数，该函数满足伯努 力分布f = b e r n o u l l i ( p ) ，也就是说r i 以p 的概率取1 ，以1 - p 的概率取0 。这样， 对于一条记录x ，某个项x i 的值以概率p 保持不变，以1 p 的概率变化为相反的 值。数据库中所有的记录都利用这种方式进行变化之后，最终提供给挖掘者的是 经过转换的数据。 这篇文章使用了经典的事务型数据库，一个用户的购买记录构成一条记录。 令s i 代表项i 的真实支持度，也就是说任意一位顾客购买产品i 的概率是s 。 假定某个顾客确实购买了产品i ，也就是说原始数据库中对应的项i 的取值为t 1 ，。 原数据库中的1 是可以由转换后的数据恢复出来的。经过一系列的概率计算得 到，对某个取值为1 的项，能够正确重构出它的支持度的概率为： 苎三垩萱墨丝塑叁三堡 r ，( 力= i i 歹i 褊+ i i 万s _ ix万(1了-ip雨)2 。这个式子表示项i 的 一个1 ，的重构概率。那么，转换数据库中所有1 的重构概率为： 。 ，r 】( p ，s ，) “1 一矿。 当数据库所有项的支持度都相同的时候，上面公式的取值达到最小a 并且因 此得到尺。( 内= i i 歹j 等+ i i 石兰苦。同理，可以得 到转换数据库 中所有一0 的重构概率 为 ： 胄。( = 百二= 若等菩+ i i ( 歹1 - _ s 丁o ) j x ( i 1 - 而p ) 2 。那么，总的重构概率 就是r ( p ) = a r ( p ) + ( 1 一日) 民( p ) 。其中口表示的是数据库中1 1 的权重。需要注 意的是：在整个数据库中取值n 0 的个数要远远超过取值1 1 的个数，因此，取值1 1 的意义远远高于一0 。 根据上个公式可以得到隐私保护的概率：尸( p ) = 1 一r ( p ) 。图4 1 是隐私度p 关于概率p 的函数曲线。图中支持度s o 取0 0 1 ，a 取不同值。可以看到，对于一 个给定的s o , 隐私度曲线的形状是确定的。而且，曲线的顶点是在p = o 1 和 p = o 9 ，a = o 9 时，隐私度高达8 5 。 图2 1 隐私度与a 和p 的关系 原始数据集合经过转换之后得到一个新的数据集合。实际上，在转换数据集 中挖掘频繁项集的问题可以转化为重构项集原始支持度的问题。也就是说，项集 第二章背景及相关工作 在转换数据集中的支持度，经过恢复得到近似的原始支持度，最终判断该项集是 否频繁。 由转换方法可以知道，原始数据库中的l 最后变为部分：一是原取值就为1 的部分；另一是原来为0 后被转换为1 的部分。由此可得到据转换后数据库中 项的取值计算原始项取值的公式c 7 = m 。c 。c 7 ，c 。分别表示原数据库和转 换后数据库中项的取值向量，m 是由转换参数p 组成的概率矩阵。通过这样的 计算恢复出原始数据库中项的支持度，从而挖掘出规则实现了隐私保护的关联规 则挖掘。 本文提出了一种针对数据流进行关联规则挖掘隐私保护的架构和具体算法。 我们以事务型数据流为例，最终达到：挖掘者在不明显增加时空耗费的前提下， 从数据流中发现频繁项集，同时满足数据提供者对隐私的要求。 2 4 隐私保护的发展方向 随着越来越多的研究工作对隐私保护的重视，隐私保护技术也越来越引起关 注，并且涌现出越来越多的隐私保护技术。例如：对多维数据的数据挖掘隐私保 护等。对于未来隐私保护技术的发展一些关键的要求可以成为发展的指南： ( 1 ) 独立性。一个理想的数据挖掘隐私保护技术方案应该是独立于各种各样的 数据挖掘算法。 ( 2 ) 隐私度和准确性的权衡。隐私度是隐私保护的基本原则