分層隱私保留 K 匿名

Abstract

K 匿名是達到資料隱私的一種常見做法，其確保發布的資料集中，任一筆紀錄至少有其他 k - 1 筆與其具有相同屬性值的紀錄。在 K 匿名的保護下，資料發布者會以所有紀錄中最高的隱私要求去設定 k 值，使得每筆紀錄達到相同程度的匿名保護。然而，不同的人或物時常會有不同的隱私要求。有些紀錄需要額外的保護，有些紀錄則僅須較低程度的隱私要求。在這篇論文中，我們提出了基於 K 匿名架構的分層隱私保留 K 匿名。其將資料集中的紀錄分至不同群組，並限制各群組符合自己對應的隱私要求。此作法使得資料發布者不必再以最高的隱私要求去設定 k 值，從而減輕匿名化造成的資訊損失。此外，我們提出了一個叢聚的演算法，來達到分層隱私保留 K 匿名的要求。從真實世界資料集的實驗與評估中，我們證實了提出的方法，對比傳統的 K 匿名，除了在設定參數有更大的彈性，也提供了更高的資料可用性。此外，實驗結果也顯示提出的演算法不僅可以有效率地運行在大型資料集上，也不會因為分層的架構產生額外的執行時間。

k-anonymity is a well-known definition of privacy, which guarantees that any person in the released dataset cannot be distinguished from at least k-1 other individuals. In the protection model, the records are anonymized through generalization or suppression with a fixed value of k. Accordingly, each record has the same level of anonymity in the published dataset. However, different people or items usually have inconsistent privacy requirements. Some records need extra protection while others require a relatively low level of privacy constraint.In this paper, we propose Multi-Level Privacy Preserving K-Anonymity, an advanced protection model based on k-anonymity, which divides records into different groups and requires each group to satisfy its respective privacy requirement. Moreover, we present a practical algorithm using clustering techniques to ensure the property. The evaluation on a real-world dataset confirms that the proposed method has the advantages of offering more flexibility in setting privacy parameters and providing higher data utility than traditional k-anonymity.