K-匿名是數(shù)據(jù)發(fā)布應(yīng)用場景下重要的隱私保護(hù)模型。近年來數(shù)據(jù)集K-匿名化的算法得到廣泛的研究，Median Mondrian算法是目前唯一的多維K-匿名劃分方法。文中研究了Median Mondrian算法，指出其不能有效地平衡數(shù)據(jù)劃分精度與數(shù)據(jù)隱私安全性之間的矛盾，由此提出基于熵測度機(jī)制的多維K-匿名劃分方法以及評估K-匿名化結(jié)果安全性的測量標(biāo)準(zhǔn)。實(shí)驗(yàn)表明該算法是可行的，能有效地提高數(shù)據(jù)安全性。
關(guān) 鍵 詞 熵; K-匿名; 多維劃分; 準(zhǔn)標(biāo)識符
中圖分類號 TP309.2 文獻(xiàn)標(biāo)識碼 A
Multidimensional K-anonymity Partition Method Using Entropy
YAN 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

近年來，數(shù)據(jù)的安全與隱私問題已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域研究的重要課題之一。由于個人數(shù)據(jù)極容易被商業(yè)用途的應(yīng)用收集與分析，所以越來越多的數(shù)據(jù)擁有者不愿意提供個人信息，除非個人信息中的敏感信息的隱私能得到保障。保護(hù)個人隱私信息最直接的方法是將能唯一標(biāo)識一個人的屬性信息(Identifier)隱藏，如姓名和身份證號碼。但這種方法無法解決另一種隱私威脅問題，即鏈接攻擊[1]。
鏈接攻擊是指用戶通過對發(fā)布的數(shù)據(jù)和其他渠道獲得的數(shù)據(jù)進(jìn)行鏈接處理，推演出隱私數(shù)據(jù)，從而造成隱私泄露。文獻(xiàn)[1]提出的K-匿名數(shù)據(jù)模型正是為了解決鏈接攻擊問題。為了實(shí)現(xiàn)數(shù)據(jù)集的K-匿名化，最有代表性的一類算法[2-4]是通過用戶定義的概念層次結(jié)構(gòu)實(shí)現(xiàn)K-匿名化，都屬于單維的劃分方法，其質(zhì)量取決于使用的概念層次結(jié)構(gòu)。文獻(xiàn)[5-6]提出了目前唯一的一個多維K-匿名劃分方法，即Median Mondrian算法。實(shí)驗(yàn)結(jié)果表明該近似的貪心算法能有效地實(shí)現(xiàn)數(shù)據(jù)集的K-匿名化。
K-匿名化后的數(shù)據(jù)以數(shù)值范圍替代原始數(shù)據(jù)的精確值，并且至少有K個數(shù)據(jù)具有相同的表示，即數(shù)據(jù)的K-匿名化以損失數(shù)據(jù)的精確度實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù)。數(shù)據(jù)的精確度和數(shù)據(jù)的隱私安全性是相互矛盾的，現(xiàn)有的算法很難在上述兩個指標(biāo)上獲得平衡。理想的數(shù)據(jù)K-匿名化結(jié)果應(yīng)該是在盡可能地減少數(shù)據(jù)信息損失的情況下，實(shí)現(xiàn)數(shù)據(jù)的隱私安全的最大化。如果兩組數(shù)據(jù)分布具有相同數(shù)值范圍但數(shù)據(jù)分布不同，那么數(shù)據(jù)分布離散程度高的數(shù)據(jù)安全性高于數(shù)據(jù)分布相對集中的數(shù)據(jù)。Median Mondrian算法的設(shè)計(jì)是在簡單滿足K-匿名模型要求的前提下，追求數(shù)據(jù)劃分精度的最大化，而在數(shù)據(jù)隱私安全性方面考慮不夠。
熵是最能反映數(shù)據(jù)點(diǎn)多樣性和不確定性的度量機(jī)制，因此，基于熵的概念，本文提出一種多維K-匿名劃分方法，并針對數(shù)據(jù)隱私安全性提出新的K-匿名劃分結(jié)果評價標(biāo)準(zhǔn)。
1 K-匿名模型中的基本概念
K-匿名模型相關(guān)概念的定義如下：已知數(shù)據(jù)集屬于一個更大的數(shù)據(jù)分布12n，擁有屬性集12為數(shù)據(jù)記錄的第i個屬性，為數(shù)據(jù)記錄t屬性[tA的值。
定義 1 標(biāo)識符(Identifier)。數(shù)據(jù)集T的標(biāo)識符I是指能唯一標(biāo)識數(shù)據(jù)記錄的屬性。