融合聚类与差分隐私的位置隐私方法研究

张伟媛　汤文兵　陈彦杰

摘 要：移动计算设备的快速发展导致了基于位置的服务（LBS）得到了各领域的应用，但同时给用户隐私安全带来威胁。针对用户位置信息上传共享第三方的问题，提出了融合聚类与差分隐私的位置保护方案。首先，根据位置信息的密集程度将周边位置点进行排序划分，采用k-means聚类对其进行泛化处理；在满足地理不可区分性的前提下通过平面拉普拉斯机制对簇中心进行加噪，得到每个位置点的扰动位置，进而保护位置隐私。实验结果证明，在保障位置隐私安全的前提下，本文算法具有更高的数据利用率。

关键词：差分隐私；k-means聚类；位置隐私；基于位置的服务

中图分类号：TP309.2  文獻标识码：A  文章编号：1673-260X（2023）11-0001-05

1 引言

传感器和移动设备的快速发展在市场上为用户提供了广泛的选择，便利了用户的生活。然而，这些设备的处理和存储能力会导致用户一些隐私信息的泄漏。例如使用基于位置的服务LBS会获取用户的位置信息[1]。用户将准确的位置信息上传到LBS以获得相应的服务，但上传未经处理的位置数据将直接导致用户隐私信息泄露。订外卖、外出交通或与其他用户会面，必须将他们的位置发布到LBS服务器，这些被收集的位置信息将有可能会暴露有关用户的一些基本信息，利用这些信息，广告商可以推送广告，犯罪分子也可能进行犯罪活动[2]。用户一些敏感位置信息的泄露可能对其造成大量损失，保护用户的信息安全，建立安全有效的模型已经成为当前研究的重点。

关于LBS隐私保护方案国内外已经有大量研究成果[3-6]。Song等人提出了一种基于双线性配对理论和k-匿名性的改进隐私保护方案，根据位置信息选择最佳假位置，从而实现隐私保护[7]。随后，Zhang等人提出了一种新的基于地理语义的位置隐私保护方法，同时满足k-匿名性，其中使用最大和最小距离多中心聚类算法构建候选集，并根据其语义相似性生成虚拟位置结果集[8]。然而l-多样性和k-匿名的概念受到数据分布和背景知识攻击的极大限制，因此隐私保护的程度无法得到很好的保证。除上述方法外，LBS隐私保护结构主要包括位置树结构、马尔可夫模型和聚类。位置树的主要思想是根据一定的规则构造树结构，引用前缀树和差分隐私来保护轨迹数据隐私，树的节点用于存储轨迹段[9]。马尔可夫模型主要用于模拟用户实际位置之间的时间相关性，并根据每个位置的转移概率预测下一个可能的位置[10]。聚类可以展现用户在一定时间内的活动规则，去除访问频率较低的位置，因此具有很高的灵活性。Tareqd等人提出了一种基于密度网格的在线数据流聚类方法，采用基于网格的方法来减少距离函数的调用次数，从而提高聚类质量[11]。Sabarish等人提出了一种基于图形的轨迹数据表示模型，使用基于边和顶点的测量方法计算轨迹之间的相似度，并基于路径对相似轨迹进行聚类和识别从而对位置隐私提供了隐私保障[12]。

为了最大化查询结果的准确性，提高算法的效率，在满足差分隐私的条件下本文提出一种融合聚类与差分隐私的位置隐私算法。将差分隐私与k-means聚类算法相结合，选取聚类集合的质心点，使用平面拉普拉斯机制对其进行处理得到扰动位置，并使用扰动位置代替原始位置进行查询。本文的贡献有两个方面。

（1）本文结合k-means聚类和差分隐私提出了可以有效保护用户位置隐私的机制。

（2）使用真实数据集测试所提出方案的效率和有效性，验证本文提出的算法优于其他算法，数据可用性得到了较好的提高。

2 定义及相关概念

2.1 差分隐私

2.1.1 差分隐私定义

2.1.2 隐私保护预算

参数ε称为隐私预算。如公式（1）所示，较小的ε会使算法M生成的查询结果的概率分布在一对相邻的数据集上越相似，攻击者更难判断数据集中是否存在某个元素。隐私保护的程度会更高。因此，ε的值通常要与具体的要求结合，以完成结果的隐私性和利用率之间的平衡。

2.1.3 敏感度

2.2 地理不可区分性

差分隐私通常用于数据聚合问题中的隐私保护，使攻击者无法确定元素是否属于某个数据集。考虑到某一地理空间中特定位置数据点的隐私保护，引用地理不可区分的机制，此机制扩展差分隐私到地理位置数据，并将差分隐私中相邻数据集的概念转换为两个地理上接近的位置。当两个相邻位置彼此靠近时，它们生成相同查询位置的概率相似。因此，攻击者无法根据用户提交的查询位置来确定用户的真实位置。具体定义如下：

其中，参数ε是单位距离的隐私预算，εr代表半径为r的任意圆内的隐私预算。从公式（3）中可以看出，εr越小，同一输出位置的概率分布越相似，攻击者就越难判断用户的真实位置，隐私保护程度越高。同样，通过在真实位置点上添加拉普拉斯噪声来实现地理上的不可辨性，用户的真实位置被保护在一个半径为r的圆内。

2.3 实现机制

2.4 k-means聚类

3 算法设计

针对位置隐私保护机制数据利用率低问题，本文将k-means聚类加入差分隐私位置保护机制中。该机制能够很好地保护单个位置的隐私，并通过k-means算法和差分隐私性使扰动位置与真实位置相似，从而提高位置数据的可用性。其基本思想如下，对于每个位置点，将距离小于r的兴趣点划入该位置所在的聚类簇。该算法使用聚类中心点来代表一定距离内的用户活动区域，区域内的其他位置点被移除，以避免位置冗余。最后，为了进一步保护用户的隐私，原始位置被质心所取代[14]。

3.1 位置点预处理模块

3.2 位置数据聚类模块

3.3 算法安全性分析

4 实例分析

4.1 实验设置

实验所用硬件环境为11th Gen Intel（R） Core（TM） i5 2.40GHz，16GB内存，使用python编程语言实现，操作系统平台为Windows10。使用的数据集为Gowalla，一个收集位置数据的社交网络，允许用户通过签到来分享他们的位置。该数据集使用公共API收集信息，具有196591个站点和950327个域，并在2009年2月至2010年10月时间范围内收集了用户的6442890次签到。

4.2 实验分析

本文采用MSE衡量数据可用性，对比了单纯使用差分隐私算法的数据可用性，分析了隐私预算ε对数据利用率的影响，其中误差越低，代表数据可用性越高，隐私预算ε对算法误差的影响分析如图1所示。

根据拉普拉斯概率密度函数推断，隐私保护程度随ε的增加而降低，该实验结果也反映了这一理论。而且从实验结果中不难看出本文算法的隐私保护程度较好于传统的差分隐私算法，这是由于k-means聚类生成了一个质心，所有位置都被一个唯一的质心替换，因此本文的隐私保护程度更好，数据可用性更高。

图2则分析了待保护位置的数量N对隐私保护程度的影响，从实验结果中可以看出隐私保护程度随着待保护位置数量N的减少而增加。N越大，隐私保护程度越差。同样，对比传统的差分隐私方法，可以看出本文算法的数据可用性更高。

5 总结

本文针对位置数据中的隐私问题提出了一种新的解决方案，设计了一个融合k-means聚类与差分隐私的算法来干扰用户的位置数据。通过理论分析与实验证明，本文算法能够在有效保护用户数据安全性的同时提高数据的利用率。

参考文献：

〔1〕姜海洋，曾剑秋，韩可，等.5G环境下移动用户位置隐私保护方法研究[J].北京理工大学学报，2021， 41（01）：84-92.

〔2〕杨洋，王汝传.增强现实中基于位置安全性的LBS位置隐私保护方法[J].计算机应用，2020，40（05）：1364-1368.

〔3〕XIONG J B， REN J， CHEN L， et al. Enhancing privacy and availability for data clustering in intelligent electrical service of IoT， IEEE Internet of Things Journal， 2019， 6（02）：1530-1540.

〔4〕XIONG J B， MA R， CHEN L， et al. A personalized privacy protection framework for mobile crowdsensing in IIoT， IEEE Transactions on Industrial Informatics， 2020， 16（06）：4231-4241.

〔5〕HE J S， Du J H， ZHU N F. Research on k-anonymity Algorithm for Personalized Quasi-identifier Attributes [J]. Information network security， 2020， 20（10）：19-26.

〔6〕LIU Q， YU J， HAN J， et al. Differentially private and utility-aware publication of trajectory data[J]. Expert Systems with Applications， 2021， 180（07）：115120.

〔7〕SONG C， ZHANG YD， WANG L， et al. Research on k-anonymity privacy protection scheme based on bilinear pairings [J]. The Journal of China Universities of Posts and Telecommunications， 2018， 25（05）：12-19.

〔8〕ZHANG Y B， ZHANG Q Y， LI Z Y， et al. A k-anonymous Location Privacy Protection Method of Dummy Based on Geographical Semantics [J]. International Journal of Network Security， 2019， 21（06）：937-946.

〔9〕ZHAO X， PI D， CHEN J. Novel trajectory privacy-preserving method based on prefix tree using differential privacy [J]. Knowledge-Based Systems， 2020， 198（05）：105940.

〔10〕YUAN T A， MMK A， MAR A， et al. A privacy preserving location service for cloud-of-things system-Science Direct [J]. Journal of Parallel and Distributed Computing， 2019， 123： 215-222.

〔11〕TAREQ M， SUNDARARAJAN E A， MOHD M， et al. Online clustering of evolving data streams using a density grid-based method.IEEE Access 2020， 8， 166472-166490.

〔12〕SABARISH BA， KARTHI R， KUMAR T G. Graph Similarity-based Hierarchical Clustering of Trajectory Data [J]. Procedia Computer Science， 2020， 171：32-41.

〔13〕SINAGA K P， YANG M S. Unsupervised K-means clustering algorithm[J]. IEEE access， 2020， 8： 80716-80727.

〔14〕任曉宇.基于差分隐私的位置隐私保护技术研究[D].山西师范大学，2021.