吴 响，臧 昊，俞 啸

（徐州医科大学 医学信息学院，江苏 徐州 221116）

基于抽样路径的K-匿名隐私保护算法*

吴 响，臧 昊，俞 啸

（徐州医科大学 医学信息学院，江苏 徐州 221116）

K-匿名是信息隐私保护的一种常用技术，而使用K-匿名技术不可避免会造成发布数据的信息损失，因此，如何提高K-匿名化后数据集的可用性一直以来都是K-匿名隐私保护的研究重点。对此提出了一种基于抽样路径的局域泛化算法——SPOLG算法。该算法基于泛化格寻找信息损失较小的泛化路径，为减少寻径时间，引入等概率抽样的思想，选用等概率抽样中的系统抽样方法进行取样，利用样本代替数据集在泛化格上寻找目标泛化路径，最后在该路径上对数据集进行泛化。同时，本算法使用局域泛化技术，能够降低信息损失量，提高发布数据集的可用性。实验结果证明，本算法匿名化的数据集信息损失度低，数据可用性高。

隐私保护；路径；信息损失；抽样；K-匿名

0 引言

K-匿名[1]是一种简单而有效的隐私保护模型，实施K-匿名要考虑两个方面：（1）确保数据发布过程中隐私不泄露；（2）发布的匿名数据具有实用性。

基于以上两个要求，众多学者提出了许多匿名算法。但大体上可以分为全域泛化算法[2]和局域泛化算法[3]。相比之下，局域泛化算法不仅可以实现K-匿名，而且一定程度上降低了匿名表的信息损失，使得泛化后的数据集更具有可用性。

然而，在局域泛化中想要寻找最优K-匿名已经被证明是 NP难问题[4]，如何优化 K-匿名算法、尽可能提高数据的可用性成为亟待解决的问题。……