K-匿名是數據發布應用場景下重要的隱私保護模型。近年來數據集K-匿名化的算法得到廣泛的研究，Median Mondrian算法是目前唯一的多維K-匿名劃分方法。文中研究了Median Mondrian算法，指出其不能有效地平衡數據劃分精度與數據隱私安全性之間的矛盾，由此提出基于熵測度機制的多維K-匿名劃分方法以及評估K-匿名化結果安全性的測量標準。實驗表明該算法是可行的，能有效地提高數據安全性。
關 鍵 詞 熵; K-匿名; 多維劃分; 準標識符
中圖分類號 TP309.2 文獻標識碼 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

近年來，數據的安全與隱私問題已經成為數據挖掘領域研究的重要課題之一。由于個人數據極容易被商業用途的應用收集與分析，所以越來越多的數據擁有者不愿意提供個人信息，除非個人信息中的敏感信息的隱私能得到保障。保護個人隱私信息最直接的方法是將能唯一標識一個人的屬性信息(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是指能唯一標識數據記錄的屬性。