基于LBS(位置服务)的隐私保护算法研究 .pdf

基于LBS(位置服务)的隐私保护算法研究--第1页

基于LBS(位置服务)的隐私保护算法研究

黄小英

【摘要】随着数据挖掘和数据发布等数据库应用的出现与发展,如何保护隐私数据

和防止敏感信息泄露成为当前面临的重大挑战.隐私保护技术需要在保护数据隐私

的同时不影响数据应用.根据采用技术的不同,出现了数据失真、数据加密、限制发

布等隐私保护技术.

【期刊名称】《制造业自动化》

【年(卷),期】2011(033)009

【总页数】3页(P96-98)

【关键词】隐私保护;随机化;安全计算

【作者】黄小英

【作者单位】广西工商职业技术学院,南宁,530003

【正文语种】中文

【中图分类】TP312

数据挖掘和数据发布是当前数据库应用的两个重要方面。一方面，数据挖掘与知识

发现在各个领域都扮演着非常重要的角色。数据挖掘的目的在于从大量的数据中抽

取出潜在的、有价值的知识（模型或规则）。传统的数据挖掘技术在发现知识的同

时，也给数据的隐私带来了威胁。另一方面，数据发布是将数据库中的数据直接地

展现给用户。而在各种数据发布应用中，如果数据发布者不采取适当的数据保护措

施，将可能造成敏感数据的泄漏，从而给数据所有者带来危害。所以，如何在各种

基于LBS(位置服务)的隐私保护算法研究--第1页

基于LBS(位置服务)的隐私保护算法研究--第2页

数据库应用中保护数据的隐私，成为近年来学术界的研究热点。

没有任何一种隐私保护技术适用于所有应用。隐私保护技术分为三类：

1）基于数据失真（Distorting）的技术：使敏感数据失真但同时保持某些数据或

数据属性不变的方法。例如，采用添加噪声（AddingNoise）、交换

（Swapping）等技术对原始数据进行扰动处理，但要求保证处理后的数据仍然可

以保持某些统计方面的性质，以便进行数据挖掘等操作。

2）基于数据加密的技术：采用加密技术在数据挖掘过程中隐藏敏感数据的方法。

多用于分布式应用环境中，如安全多方计算（SecureMultipartyComputation，

以下简称SMC）。

3）基于限制发布的技术：根据具体情况有条件地发布数据。如：不发布数据的某

些域值，数据泛化（Generalization）等。

隐私保护技术需要在保护隐私的同时，兼顾对应用的价值以及计算开销。通常从以

下三方面对隐私保护技术进行度量：

1）隐私保护度：通常通过发布数据的披露风险来反映，披露风险越小，隐私保护

度越高。

2）数据缺损：是对发布数据质量的度量，它反映通过隐私保护技术处理后数据的

信息丢失：数据缺损越高，信息丢失越多，数据利用率（Utility）越低。具体的度

量有：信息缺损（InformationLoss）、重构数据与原始数据的相似度等。

3）算法性能：一般利用时间复杂度对算法性能进行度量。例如，采用抑制

（Suppression）实现最小化的k-匿名问题已经证明是NP-hard问题；时间复杂

度为O(k)的近似k-匿名算法，显然优于复杂度为O(klogk)的近似算法。均摊代价

（AmortizedCost）是一种类似于时间复杂度的度量，它表示算法在一段时间内

平均每次操作所花费的时间代价。除此之外，在分布式环境中，通讯开销

（CommunicationCost）也常常关系到算法性能，常作为衡量分布式算法性能

基于LBS(位置服务)的隐私保护算法研究--第2页

基于LBS(位置服务)的隐私保护算法研究--第3页

的一个重要指标。

数据失真技术通过扰动（Perturbation）原始数据来实现隐私保护。它要使扰动

后的数据同时满足：