采用熵的多维K-匿名划分方法

K-匿名是数据发布应用场景下重要的隐私保护模型。近年来数据集K-匿名化的算法得到广泛的研究，Median  Mondrian算法是目前唯一的多维K-匿名划分方法。文中研究了Median  Mondrian算法，指出其不能有效地平衡数据划分精度与数据隐私安全性之间的矛盾，由此提出基于熵测度机制的多维K-匿名划分方法以及评估K-匿名化结果安全性的测量标准。实验表明该算法是可行的，能有效地提高数据安全性。关  键  词  熵;  K-匿名;  多维划分;  准标识符中图分类号  TP309.2  文献标识码  AMultidimensional  K-anonymity  Partition  Method  Using  EntropyYAN  Hua，LIU  Gui-song(Computational  Intelligence  Laboratory,  University  of  Electronic  Science  and  Technology  of  China  Chengdu  610054)Abstract  K-anonymity  is  an  important  privacy  preserving  model  in  the  data  publishing  scenario.  The  algorithms  on  dataset  K-anonymization  are  researched  extensively  in  recent  years,  Median  Mondrian  algorithm  is  the  only  multidimensional  K-anonymity  partition  method.  However,  our  research  shows  that  Median  Mondrian  algorithm  is  not  well-balanced  on  dealing  with  the  contradiction  between  data  partition  precision  and  data  privacy  preserving.  In  this  paper,  we  propose  an  entropy-based  multidimensional  K-anonymity  partition  method  and  a  new  evaluation  measure  on  K-anonymization  results.  The  experimental  results  show  that  our  new  method  is  feasible  and  preserves  the  privacy  much  more  efficiently  than  Median  Mondrian  algorithm.Key  words  entropy;  K-anonymity;  multidimensional  partition;  quasi-identifier近年来，数据的安全与隐私问题已经成为数据挖掘领域研究的重要课题之一。由于个人数据极容易被商业用途的应用收集与分析，所以越来越多的数据拥有者不愿意提供个人信息，除非个人信息中的敏感信息的隐私能得到保障。保护个人隐私信息最直接的方法是将能唯一标识一个人的属性信息(Identifier)隐藏，如姓名和身份证号码。但这种方法无法解决另一种隐私威胁问题，即链接攻击[1]。链接攻击是指用户通过对发布的数据和其他渠道获得的数据进行链接处理，推演出隐私数据，从而造成隐私泄露。文献[1]提出的K-匿名数据模型正是为了解决链接攻击问题。为了实现数据集的K-匿名化，最有代表性的一类算法[2-4]是通过用户定义的概念层次结构实现K-匿名化，都属于单维的划分方法，其质量取决于使用的概念层次结构。文献[5-6]提出了目前唯一的一个多维K-匿名划分方法，即Median  Mondrian算法。实验结果表明该近似的贪心算法能有效地实现数据集的K-匿名化。K-匿名化后的数据以数值范围替代原始数据的精确值，并且至少有K个数据具有相同的表示，即数据的K-匿名化以损失数据的精确度实现数据的隐私保护。数据的精确度和数据的隐私安全性是相互矛盾的，现有的算法很难在上述两个指标上获得平衡。理想的数据K-匿名化结果应该是在尽可能地减少数据信息损失的情况下，实现数据的隐私安全的最大化。如果两组数据分布具有相同数值范围但数据分布不同，那么数据分布离散程度高的数据安全性高于数据分布相对集中的数据。Median  Mondrian算法的设计是在简单满足K-匿名模型要求的前提下，追求数据划分精度的最大化，而在数据隐私安全性方面考虑不够。熵是最能反映数据点多样性和不确定性的度量机制，因此，基于熵的概念，本文提出一种多维K-匿名划分方法，并针对数据隐私安全性提出新的K-匿名划分结果评价标准。1  K-匿名模型中的基本概念K-匿名模型相关概念的定义如下：已知数据集属于一个更大的数据分布12n，拥有属性集12为数据记录的第i个属性，为数据记录t属性[tA的值。定义  1  标识符(Identifier)。数据集T的标识符I是指能唯一标识数据记录的属性。