关联规则隐藏算法综述

包耕张玲乐

摘 要：近年来，数据挖掘备受青睐，它可以从大量数据集合中提取隐藏的知识。如何实现既找到数据中隐藏的知识，又不透露其中的敏感信息尤为关键。隐私保护数据挖掘（PPDM）能够实现对敏感信息的保护，关联规则隐藏是PPDM技术中的一种，用来保护敏感性的关联规则。总结了关于隐私保护的数据挖掘方法并指出了其优缺点，同时重点对关联规则隐藏算法进行了分析。

关键词关键词：数据挖掘；隐私保护；关联规则隐藏

DOIDOI：10.11907/rjdk.162016

中图分类号：TP312

文献标识码：A 文章编号文章编号：16727800（2016）011004602

0 引言

隐私保护数据挖掘在数据挖掘领域是一个富有成效的研究课题。PPDM的目的是通过各种方法转换现有的数据集，甚至在挖掘的过程中，一些数据在某种程度上的机密性依然保持不变。在数据挖掘中，用户给出数据并免费使用他们自己的工具。因此，数据挖掘之前的隐私保护要应用在用户自己的数据上。鉴于此，需要开发新的隐私保护控制系统，也即将这些数据集转换成一个新的数据集来保护原始数据。提出关联规则隐藏算法的目标是为了保护一些特别的数据，使其在关联规则隐藏算法的过程中不被发现。例如：政府想推出一些关于农村地区发展的新计划，农村部门有关于农民和劳动的数据库，他们想通过第三方分析这些数据，但是不能揭示农村劳动者的个人信息；又如：商店想要了解消费者的购物行为，该例中消费者的数据不是很重要，但是从数据所分析出的结果需要得到保护。

数据挖掘是一种从海量信息中挖掘出有用信息的技术。在当前社会，共享和发布信息已经成为常见现象。然而，数据的搜集和分析会暴露个人隐私。目前，隐私保护数据挖掘已经引起了广泛关注，许多关于隐私保护的技术因此被提出。本文将讨论不同的隐私保护技术及它们的优缺点，并重点讨论关联规则挖掘算法。

数据挖掘可以在很短时间内分析大量的信息，智能算法将一些敏感性和机密性的数据存储在大量分支数据中。各种各样的挖掘技术中也许包含很多关于个人和组织的敏感性信息。关联规则挖掘就是从给出的数据中发现一些能够满足预先定义好的最低值和机密度的关联规则。该问题通常被分解为两个子问题：一是找出该项目中谁的发生超出了预先定义的临界值，这些被称为频繁大项集；二是从这些大项集中产生关联规则。关联规则隐藏是指修改原始数据的过程，在该过程中，一些确定的敏感性关联规则消失，但是并不影响数据和一些不敏感规则。

通过转换将一些敏感性的数据隐藏起来的过程叫做数据清洗过程。为了进行转换，一个小数量的交易需要通过删除一个或多个项目而发生改变，或者一些交易是通过将错的改为对的来添加噪声数据集，发布的数据库称为清洁数据库。同时，该方法也稍微修改了一些数据，但是在实际应用中非常容易被接受。

1 关联规则隐藏算法相关技术

关联规则隐藏算法阻止敏感性规则被公开。其主要问题归纳如下：给定一个事务数据库X用最小机密度、最小支持度，以及一系列从数据库X中挖掘出来的规则。一个R的子集RH为敏感性关联规则，该子集不能被公开。关联关系隐藏的目的是将X转换为X′，通过这些方法任何人将不会挖掘出属于RH的规则，而且属于R的不敏感规则也不会受到影响。

1.1 启发式技术

启发式技术解决如何确定合适的数据集对数据进行转换。启发式技术的转变方法既包括扰动项，通过改变其属性值完成（例如改变属性值由1到0），还包括阻塞项，用“？”改变现存的属性值。

1.1.1 基于扰动的方法

基于数据扰动提出对数据的启发式修改，它将一个被选择的属性值由1改为0，因此敏感规则的支持度将会减少，发布数据的效应将会达到最大。其关键的一步是借助于启发式的思想如何将X变为X，。

Agrawal and Srikant使用数据扰动技术来改变数据，这样可以根据原始数据的相似值获得改变过的数据版本，同样挖掘规则也相应地改变为相似的挖掘规则。这个重建的分布用来构造一个新的模型。

本文提出了5种算法，所有这些算法都是基于扰动技术，其中3种是隐藏一些关联规则，剩下的两种是隐藏大项集。这5种算法都用到了参数，具有有效性。由于首先要根据它们的种类隐藏关联规则，因而副作用也很明显。

文献[1]力求在隐私数据和公开数据中达到平衡，即尽量减少关于消除事项的相互影响，并且尽量减少偶然和替代事项。其效应是测量隐藏在修改过程中产生副作用的无敏感规则的数量。

1.1.2 基于阻塞的方法

通过用一个问号或者一个真值替代一个确定的数据来减少敏感规则的支持度和置信度，该方法已经在实施。最小的支持度和最小的置信度相应地改变成一个最小的支持区间和最小的置信区间。如果一个敏感规则的支持度和/或者置信度在该区间，则并不违反数据的机密性。

Yucel Saygin使用一些分块来扰动关联规则。当一些原始数据的值被一些不知道的值替换之后，就难以界定敏感关联规则的支持度和置信度。Yucel Saygin在其论文中通过一些例子，在关联规则挖掘中使用不确定的符号，也即用支持区间和置信区间来代替支持度和置信度。

Xiao X[2]提出了一个新的个人匿名概念的概括性框架，该框架是为了确保普遍性来满足每个人的要求。它提供了关于隐私保护不同大小的数据表的记录。Liu Mingetal基于（I，k）匿名化模型提出了个人匿名模型。

1.2 基于重建的关键规则

最近提出的许多关于隐私保护的问题是通过在一个总体水平上来扰动数据和重建分支，也即该算法先用在扰动数据上，然后用在重建分支上。重建方法和数据类型不同，相应的算法也不同。

Agrawal用贝叶斯定义的算法进行分支重建。Agrawal对于重建关联规则提出了一个统一的随机选择的算法。本文在贝叶斯的基础上作了改进，在（期望最大化）EM算法的帮助下进行重建。

1.2.1 数据重建方法

另一个数据重组方法是将原始数据搁置一边，开始于消除所谓的“知识数据”。新的被公开的数据由经过消除的知识数据而重建。Chen首次提出了基于约束基础的转换项目，即Lattice Mining procedure （CIILM），用于隐藏经常性的敏感项目，它们的数据重建是基于子项目集。另一个隐私保护方法是与逆频繁项目集挖掘相关联，也即从给出的频繁数据中推出原始数据，这是由Mielikainen提出的。

1.2.2 FP树方法

FP方法在文献[3]中被提出，是基于重组技术的逆频繁项目集挖掘。有3个步骤：①用频繁项目挖掘算法产生从数据D形成的支持项；②将消除算法超过频繁项目从FS中得到FS，；③从FS中获得公开数据D。

1.3 基于密码基础的技术

不同的组织希望交换它们的数据，但是不能暴露其敏感信息。因此，在交换信息时使用一些保密规则。

1.3.1 垂直分区的分布式数据

该算法是根据“安全和”的概念而提出，安全和是指节点之间的安全计算，每个分项目的支持度之和将要被计算。

文献[4]讨论了各种各样的隐私保护的分解方法，包括安全和、安全联合、交集的安全大小以及数积等。文献[5]讨论了如何使用分级点来计算频繁项目，它使用线形的算法技术来计算两个向量的分节点。

1.3.2 水平分区的分布式数据

衡量全局频繁项集，确保不揭露网站信息，只找到在网站上支持度的安全值。支持度高过阈值就是全局频繁项集。

Shaofei Wu提出了一种算法来保持隐私保护和知识挖掘之间的平衡。该解决方法在挖掘阶段后使用了一个过滤器来隐藏一些被发现的规则。在使用该算法之前，要建立数据结构和敏感规则的有效模型。

Chirag N. Modi提出相应算法以阻止一些通过不安全的媒介来获得隐私的方法。

1.4 精确方法

这些方法跟随着隐藏进程，作为一个约束满意度问题已经被二进制整数程序设计（BIP）解决。它们给出了很好的解决方法，但遭受了从高时间复杂度到CSP。

Gkoulalas and Verykios针对找到一个隐藏规则问题的最佳解决方法提出了相应建议。该隐藏问题在尽量减少原始数据甚至是消除数据之间的距离。

文献[6]基于边界值的方法，提出了解决隐藏敏感频率项集问题的最佳方法。隐藏敏感频率项是通过综合扩展原始数据集生成数据集。扩展原始数据来隐藏数据敏感项被证明是对于解决扩展隐藏问题的最佳解决方法。

2 关联规则隐藏目的

2.1 隐藏目的

（1）如果预先定好了原始数据的支持度和置信度的阈值，则敏感性规则不能被挖掘出来，如果这些数据在同样或更高的阈值内被挖掘，那么它可以公布其转换过的数据。这要求转换过的数据不包含敏感性规则。

（2）在给定的支持度和置信度内如果能挖掘到原始数据不敏感的规则，那么对于转换过的数据在同样支持度和置信度或者更高的值内，也应该被挖掘出。另一个要求是在转换数据时不能丢失规则。

（3）不能有错误的规则，错误的规则指原始数据中不存在的规则。

2.2 挖据算法目标

隐私保护挖掘算法应该做到：①个人敏感信息需要被维护；②对于不敏感数据的使用不妥协；③没有一个指数计算的复杂性。

2.3 关联规则隐藏发展方向

关联规则隐藏有两个主要方向：①在原始数据中隐藏一些特别的关联规则；②从原始数据挖掘出一些频繁项，即隐藏这些特别的频繁项，即确保从敏感规则在公开的数据里变得无关紧要。

3 结语

在共享环境下，关联规则隐藏用处极大。本文提出了一种分类的隐私保护关联规则挖掘方法，并进行了详细分析。现有方法仅提供了隐藏敏感知识的近似解，如何找到数据库信息披露的精确解还有待进一步研究。

参考文献：

[1] S R M OLIVEIRA，O R ZAIANE，Y SAYGIN.Secure association rule sharing， advances in knowledge discovery and data mining[C].Sydney：Proceedings of the 8th PacificAsia Conference（PAKDD2004），2004：7485.

[2] S OLIVEIRA，O ZAIANE.Algorithms for balancing privacy and knowledge discovery in association rule mining[C].Hong Kong：Proceedings of 7th international database engineering and applications symposium （IDEAS03），2003.

[3] YONGCHENG LUO，YAN ZHAO，JIAJIN LE.A Survey on the privacy preserving algorithm of association rule mining[C].International Society for EighteenthCentury Studies，2009：241245.

[4] CHRIS CLIFTON，MURAT KANTARCIOGLOU，XIADONGLIN，et al.Tools for privacy preserving distributed data mining[J].SIGKDD Explorations，2002，4（2）：17.

[5] IOANNIDIS I，GRAMA A，ATALLAH M.A secure protocol for computing dotproducts in clustered and distributed environments[C].Proceedings of International Conference on Parallel Processing，2002：379384.

[6] GKOULALAS DIVANIS，V S VERYKIOS.Exact knowledge hiding through database extension[J].IEEE Transactions on Knowledge and Data Engineering，2009，21（5）：699713.

（责任编辑：孙 娟）