关键字 |
泛化,桶化,属性公开保护,成员船公开保护,切片 |
介绍 |
保密性微数据发布是现代社会研究的热点。微数据包含记录,每个记录包含关于个人实体(如个人、医院或公司)的数据。介绍了各种微数据匿名化技术。最常见的是对匿名的泛化和对Ã①Â△Â△-diversity的桶化。在两种技术中,属性分为三类:(1)某些属性是可以明显识别个人的标识符,如姓名或公共安全号码;(2)某些属性是准标识符(QI),对手可能已经知道(可能来自其他公开信息),当这些属性结合在一起时,可以潜在地识别一个人,例如出生日期、性别、姓名和邮政编码;(3)一些属性是敏感属性(sa),它们是对手无法识别的,是敏感测量的,如帐户类型、疾病和工资。 |
在泛化和桶化这两种技术中,首先从数据中删除标识符,然后将元组划分到桶中。这两种技术在下一步中有所不同。泛化将每个桶中的QI-值转换为“不太详细但有意义的上下文”值,这样同一桶中的元组就不能通过QI值来区分。在桶化中,通过随机排列每个桶中的SA值,将SA从QIs中分离出来。匿名化的数据由一组敏感属性值排列的桶组成。 |
概括: |
泛化过程取决于所涉及的属性或应用程序,用户可以选择一些属性保持在相当低的抽象级别,而其他属性则泛化到更高的级别。控制一个属性的广义程度通常是非常主观的。调用此过程的控件“属性泛化控制”。 |
有许多可能的方法来控制泛化过程,其中我们使用了两种常见的方法。 |
第一种技巧叫做属性泛化阈值控制”,要么为所有属性设置一个泛化阈值,要么为每个属性设置一个阈值。如果属性中唯一值的数量大于属性阈值,则应该执行进一步的属性移除或属性泛化。数据挖掘系统通常允许默认属性阈值在2到8之间,并且应该允许专家和用户修改阈值。如果用户认为某一特定属性的泛化程度很高,则可以增加阈值。这对应于沿着属性向下钻取。此外,为了进一步泛化关系,用户可以降低特定属性的阈值,这对应于沿属性向上滚动。 |
第二种技术叫做广义关系阈值控制,设置泛化关系的阈值。如果不是。当广义关系中不同元组大于阈值时,应进行进一步的概化。否则,不应执行进一步的泛化。这样的阈值应该出现在数据挖掘系统中,通常在10到30之间,或者由专家或用户设置,并且应该是可调的。例如,如果用户觉得广义关系非常小,他可以增加阈值,这意味着向下钻取。否则,为了进一步推广关系,他可以降低阈值,这意味着卷起。 |
这两种技术可以依次应用;首先应用属性阈值控制技术对每个属性进行泛化,然后应用关系阈值进一步缩小泛化关系的大小。无论采用哪种泛化控制技术,都应该允许用户调整泛化阈值,以获得有趣的概念描述。 |
相关工作 |
切片是一种具有成员船泄露保护的数据安全发布的新方法。通过对数据进行水平和垂直的划分,可以降低大数据库中数据的维数。水平分区是通过将元组分组为桶来实现的,垂直分区是通过根据属性之间的相关性将属性分组为列来实现的。与概化和桶化相比,它能提供更好的数据效用。 |
表1显示了一个示例微数据表及其使用各种匿名技术的匿名版本。原始表格如1(a)所示。QI值为{c-age, c-sex, zip code},敏感属性SA为帐户类型。表1(b)为4-匿名的概化表,表1(c)为2-多样性的水桶化表,表1(d)为替换基于多集概化的概化表,表1(e)和表1(f)为两个切片表。 |
切片首先将属性划分为列,每列包含属性的子集。水平分区是通过将元组分组到桶中来完成的。竖着的隔板把桌子隔开。例如,表1(f)中的切片表包含2列,即{c-age, c-sex}和{邮政编码和帐户类型},而在表1(e)中包含4列,每个属性恰好位于一列。 |
切片还将元组划分为桶。每个桶包含元组的一个子集。这个水平分区表1(e)包含2个桶,每个桶包含4个元组。 |
切片的主要标准是它可以通过随机排列来打破不同列之间的链接,将元组划分为bucket。 |
例如表1(f)。值{(24,M),(24,F),(33,F),(44,F)是随机排列的,有值{(1234903,SAVING),(12345904,CURRENT),(12345904,LOAN),(12345903,SAVING)}是随机排列的,以便隐藏一个bucket内两列之间的链接。 |
切片表如表1(f)所示,满足2-多样性,考虑一个QI值为{24,M, 12345903的元组t1来确定t1的敏感值,考虑表1(f)中匹配的桶,观察第一个桶B1 t1必须在B1,因为在桶B2中没有(24,M)匹配,因此得出t1必须在B1。 |
下一个属性是ZIPCODE属性,它位于bucket B1中的第二列(邮政编码,帐户类型),我们知道t1的列值是(12345903,CURRENT)和(12345903,SAVING),这是t1敏感值的两个可能值,没有其他列将12345903作为邮政编码。CURRENT ACCOUNT和SAVING ACCOUNT是元组t1的可能值。 |
A.系统架构:本文所使用的基本数据为 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-108-g002.gif) |
防止身份泄露 |
防止身份泄露可以保证攻击者无法将特定记录与已知个人关联起来。最流行的担保是k- anonymous [Samarati 2001, Sweeney 2002]。k-匿名性保证每个记录与其他k-1记录在准标识符方面没有区别。准标识符的每个组合在匿名数据集中出现0次或k次以上。 |
在[He et. al. 2009]中,提出了一种将集值数据转换为匿名形式的方法,即分区算法。分区使用泛化将数据转换为k-匿名形式。泛化是将一组原始值替换为一个新的更抽象的值。例如,如果以城市的形式报告个人的居住区域,则可以将匿名数据中的城市名称替换为国家名称,如图2所示。分区采用本地编码;并非原始值的所有表象都被广义的表象所取代。分区是一种自顶向下的算法;它首先考虑将所有值泛化到泛化层次结构中更一般的值,然后向下钻取层次结构,直到k-匿名属性不再成立。 |
属性披露保护 |
数据集中的数据值通常不如个人信息重要。在与隐私相关的文本中,一个常见的区别是准标识符和敏感值。准标识符通常通过几个来源了解,它们不会威胁到个人的隐私。另一方面,敏感值被认为是无法通过其他来源获得的,它们暴露了重要的个人信息。如果存在这样的区别,并且数据发布者知道它,那么还必须保护数据,防止敏感属性的泄露。防止敏感值的一个常见保证是l-多样性。l -多样性保证了任何对手都不能将她的背景知识与低于我们所代表的敏感值联系起来。良好表示通常定义为概率阈值:对手不能将其背景知识与任何概率超过1/l的敏感值关联起来。 |
第一个在集值属性中提供防止属性泄露的匿名化方法。的建议依赖于将敏感值从准标识符中分离出来,如表4和表5所示。分离的思想最早在[Xiao et. al. 2006]的关系语境中提出,但在[Ghinita et. al. 2008, Ghinita et. al. 2011]中针对集值语境进行了调整和扩展。提出的匿名化方法的基本思想是创建相似记录的集群(关于准标识符),然后在每个集群中分别发布准标识符和敏感值。这种转换对于泛化和抑制的一个好处是,它不需要创建具有相同准标识符的组。这样,即使对于非常高基数和维数的数据,信息损失也保持在较低的水平。 |
切片算法 |
A.属性划分 |
属性划分是通过在同一列中使用高度相关的属性来完成的。这在使用和隐私方面都是非常有用的技术。将高度相关的属性分组到同一列中可以降低数据的维数,增加使用率是非常容易的。不相关属性的关联比高度相关属性的关联具有识别风险,因为不相关属性之间的关联比高度相关属性之间的关联发生的频率要低。因此,最好打破不相关属性之间的关联,以保护隐私。 |
B.列概化 |
对列进行广义化,以满足出现频率。泛化就是把数据从低层次推到高层次。bucket化在属性公开方面也提供了与泛化相同的安全级别的保护。 |
概化不是一个强制性的过程,尽管它对标识/成员船披露保护有用。如果一个列值是唯一的,它很容易被对手识别,具有唯一列值的元组只能有匹配的桶,这种方法不是一个很好的隐私保护,因为元组可以属于一个等价类/桶。这是唯一的列值可以被识别的主要问题。因此,应用列概化来确保列值至少以某种频率出现是有用的。 |
当列泛化应用于隐私保护时,我们必须保持较小的桶大小,因为泛化会丢失大量的信息。因此,维护较小的存储桶对实用性更好。 |
C.元组划分: |
表1显示了一个示例微数据表及其使用各种匿名技术的匿名版本。的 |
算法元组划分(T, â Â]) |
1.Q = {t};Sb = à ¤。 |
2.而Q不为空 |
3.从Q中移除第一个桶B;Q = Q−{b}。 |
4.把B分成两部分B1和B2,就像蒙德里安那样。 |
5.如果多样性检查(T, Q U {B1, B2} U SB, â Â]) |
6.Q = Q u {b1, b2}。 |
7.Else SB = SB U {B}。 |
8.回报某人。 |
元组划分算法 |
上面的元组划分算法维护了两种数据结构:(1)一个桶队列作为Q(2)一组切片桶作为SB最初SB是空的,Q只包含一个桶,包括所有元组。在每次迭代中,算法从Q中删除一个桶,并在SB中分割为两个桶作为切片桶,该桶满足ldiversity,然后将这两个桶放在最后进行进一步迭代,如果Q为空,则计算出切片表。切片桶的集合存储在SB中。 |
元组划分的准则是l-多样性检查,采用l-多样性检查算法进行划分。 |
算法多样性检验(T,T_, â Â]) |
1.对于每个元组t ε t, L[t] = à ¤. t。 |
2.对于T_中的每个桶B |
3.记录桶B中每列值v的f (v)。 |
4.对于每个元组t ε t |
5.计算p (t,B)并求出D(t,B) |
6.L[t] = L[t] U {hp (t,B),D(t,B)i}。 |
7.对于每个元组t ε t |
8.根据L[t]计算每个s的p (t, s)。 |
9.如果p(t, s)≥1/â  ',返回false。 |
10.返回true。 |
成员船披露保障 |
切片是一种对会员船信息进行隐私保护的方法。在匿名数据中,原始数据中的元组应该与原始数据中不存在的元组具有相同的频率,这是至关重要的。否则,对手可以通过检查他们在匿名数据中的频率来确定他们可以确定原始数据元组与非原始数据元组之间的差异。 |
让我们研究一下对手如何从桶化中确定成员信息。桶化可以释放原始形式的QI值。对手可以比较桶数据与QI值的一个人通过观察选民名单信息。如果匹配的频率为零,则对手可以确认该个人不在数据中。如果匹配的频率大于零,则对手可以确认该个人在数据中,因为这个匹配元组属于该个人,因为几乎没有其他个人具有相同的QI值。 |
切片保护成员船披露信息的一般方法是让I是原始数据中的元组集,I '是原始数据中不存在的元组集,也称为假元组,如果一个元组在I '中,它至少匹配切片数据中的一个元组桶,对于成员船披露保护切片考虑两个措施。第一个度量是假元组的数量。如果假元组个数为0,则确定每个元组的成员船信息。第二个度量是原始元组和假元组的匹配桶数。如果匹配相似,则会保护成员信息,因为对手无法区分原始元组和假元组。 |
结论及未来工作 |
这项工作为今后的研究提供了各种指导。 |
本文提出了一种新的切片方法,它是一种很有前途的隐私保护和微数据发布技术。切片可以克服一些匿名技术的缺点,如泛化和桶化。它可以提供比桶化更好的数据效用。切片是通过计算原始数据和重复数据中QI值的频率来保护成员船披露信息。它可以通过将高度相关的属性组合到一列中来降低数据的维数。对于涉及敏感属性的信息保护,切片比桶化更有效。 |
我们在切片中使用的一般方法是:在对数据进行匿名化处理之前,先对特征进行分析,然后通过降低数据的维数,将数据中高度相关的属性合并为一列,将这些特征用于数据的匿名化处理。 |
这项工作激发了未来研究的几个方向。切片是一种每个属性都在一列中的技术。扩展是切片的重叠,它在多个列中复制一个属性。 |
其次,我们计划通过随机排列敏感属性值来进行成员船舶披露保护,但效果并不好。我们计划设计更有效的元组分组算法。 |
表格一览 |
|
数字一览 |
![Click Here 数字](//www.cheescube.com/articles-images/IJAREEIE-108-g001.gif) |
图1 |
|
参考文献 |
- p . Samarati。微数据发布中被调查者隐私的保护。大地物理学报,13(6):1010-1027,2001。
- l·斯威尼。k -匿名:一种保护隐私的模式。Int。j .不确定。模糊。,10(5):557–570, 2002.
- 肖x,陶y。剖析:简单有效的隐私保护。在VLDB, 139-150页,2006。
- 肖x,陶y。带有查询松弛的输出扰动。在VLDB,页857-869,2008。徐勇,王凯,王永昌。傅,余p.s.。匿名化事务数据库以供发布。在KDD,第767-775页,2008。
- 李俊杰,陶勇,肖曦。在发布数字敏感数据时保护邻近隐私。在SIGMOD,第473-486页,2008。
- D.基弗和J.格尔克。向匿名数据集注入实用程序。在SIGMOD, 217-228页,2006。
|