基于语义空间匿名的轨迹移动模式挖掘算法

doi:10.3969/j.issn.1671-1122.2018.08.005

信息网络安全 ›› 2018, Vol. 18 ›› Issue (8): 34-42.doi: 10.3969/j.issn.1671-1122.2018.08.005

基于语义空间匿名的轨迹移动模式挖掘算法

左开中^1,²(), 陶健^1,², 曾海燕^1,², 孙丽萍^1,²

1. 安徽师范大学计算机与信息学院,安徽芜湖 241002
2. 网络与信息安全安徽省重点实验室,安徽芜湖 241002

收稿日期:2018-03-10 出版日期:2018-08-20 发布日期:2020-05-11
作者简介:
作者简介：左开中（1974—）,男,安徽,教授,博士,主要研究方向为机器学习、隐私保护;陶健（1989—）,男,安徽,硕士研究生,主要研究方向为数据挖掘、隐私保护;曾海燕（1993—）,女,安徽,硕士研究生,主要研究方向为数据挖掘、隐私保护;孙丽萍（1980—）,女,安徽,教授,博士,主要研究方向为空间数据处理、智能计算。
基金资助:
国家自然科学基金[61602009];安徽省自然科学基金[1608085MF145]

Algorithm for Trajectory Movement Pattern Mining Based on Semantic Space Anonymity

Kaizhong ZUO^1,²(), Jian TAO^1,², Haiyan ZENG^1,², Liping SUN^1,²

1. School of Computer and Information, Anhui Normal University, Wuhu Anhui 241002, China
2. Anhui Provincial Key Laboratory of Network and Information Security, Wuhu Anhui 241002, China

Received:2018-03-10 Online:2018-08-20 Published:2020-05-11

摘要/Abstract

摘要：

针对离线场景下利用轨迹数据挖掘用户移动模式时会泄露用户敏感位置隐私问题,文章利用兴趣点的地理空间分布,提出一种基于语义空间匿名的轨迹移动模式挖掘算法来抵御攻击者地图匹配攻击或语义推断攻击,同时实现用户移动模式的挖掘。该算法首先利用网格划分技术对城区进行均匀网格划分产生网格区域;然后利用网格区域中兴趣点的位置分布和语义差异度对轨迹停留点进行空间匿名以满足(k,l)隐私模型;最后借鉴经典模式挖掘PrefixSpan算法思想对匿名轨迹数据集进行频繁移动模式的挖掘。理论分析和仿真实验验证了算法的安全性和有效性,与现有空间匿名的轨迹移动模式挖掘算法MCSPP相比,该算法不仅降低平均信息损失度,同时挖掘的频繁移动模式空间语义解释性更高。

关键词: 轨迹, 停留点, 兴趣点, (k, l)隐私模型, 移动模式挖掘

Abstract:

Aiming at the mining user movement patterns using trajectory data in offline scenario to leaks the privacy problems of the user sensitive location, using the geographic spatial distribution of points of interest, an anonymous trajectory-based moving pattern mining algorithm based on semantic space is proposed to defend against attacker map matching attacks or semantic inference attacks while implementing user mobility patterns mining. The algorithm first uses grid division technology to divide the urban area into uniform grids to generate grid areas. Then use the location distribution and semantic difference degree of the interest points in the grid area to spatially annotate the trajectory stay points to satisfy the (k,l) privacy model. Finally, the idea of mining PrefixSpan algorithm based on classical model mining is used to mine frequent moving patterns of anonymous trajectory datasets. Theoretical analysis and simulation experiments verify the security and effectiveness of the algorithm. Compared with MCSPP, an existing space-based anonymous trajectory moving pattern mining algorithm, this algorithm not only reduces the average information loss degree, but also has a higher spatial interpretation of the frequent movement patterns of mining.

Key words: trajectory, stay point, points of interest, (k, l) privacy model, movement pattern mining

中图分类号:

TP309

左开中, 陶健, 曾海燕, 孙丽萍. 基于语义空间匿名的轨迹移动模式挖掘算法[J]. 信息网络安全, 2018, 18(8): 34-42.

Kaizhong ZUO, Jian TAO, Haiyan ZENG, Liping SUN. Algorithm for Trajectory Movement Pattern Mining Based on Semantic Space Anonymity[J]. Netinfo Security, 2018, 18(8): 34-42.

图/表 14

图1

图2

图3

图4

图5

表1

图6

表2

图7

图8

图9

图10

图11

图12

参考文献 21

[1]	FENG Zhenni, ZHU Yanmin. A Survey on Trajectory Data Mining: Techniques and Applications[EB/OL]. , 2016-4-13.
[2]	GUO Limin, HUANG Guangyan, GAO Xu, et al.DoSTra: Discovering Common Behaviors of Objects Using the Duration of Staying on Each Location of Trajectories[J]. Radiation Research, 2015, 161(2): 137-142.
[3]	HUANG Guangyan, HE Jing, ZHOU Wanlei, et al.Discovery of Stop Regions for Understanding Repeat Travel Behaviors of Moving Objects[J]. Journal of Computer & System Sciences, 2016, 82(4): 582-593.
[4]	SHEN Ying, ZHAO Ligang, FAN Jing.Analysis and Visualization for Hot Spot Based Route Recommendation Using Short-Dated Taxi GPS Traces[J]. Information, 2015, 6(2): 134-151.
[5]	MA Chunguang, ZHANG Lei, YANG Songtao.Review on Location Trajectory Privacy Protection[J]. Netinfo Security, 2015, 15(10): 24-31.
	马春光,张磊,杨松涛. 位置轨迹隐私保护综述[J]. 信息网络安全,2015,15(10):24-31.
[6]	KRUMM J.Inference Attacks on Location Tracks[C]//Springer. 5th International Conference on Pervasive computing, May 13-16, 2007, Toronto, Canada. Heidelberg: Springer, 2007: 127-143.
[7]	CHEN Hongsong, HAN Zhi, DENG Shuning.Analysis and Research on Big Data Security in Smart City[J]. Netinfo Security, 2015, 15(7): 1-6.
	陈红松,韩至,邓淑宁. 智慧城市中大数据安全分析与研究[J]. 信息网络安全,2015,15(7):1-6.
[8]	GIDOFALVI G, HUANG Xuegang, PEDERSEN T B. Probabilistic Grid-based Approaches for Privacy-preserving Data Mining on Moving Object Trajectories[EB/OL]. , 2017-11-10.
[9]	JURECZEK P L, KOZIERKIE A.A Privacy-preserving Framework for Mining Continuous Sequences in Trajectory Systems[C]//IEEE. 2014 European Network Intelligence Conference, September 29-30, 2014, Wroclaw, Poland. New Jersey: IEEE, 2014: 52-58.
[10]	ZHOU Changli, MA Chunguang, YANG Songtao, et al.A Location Privacy Preserving Method Based on Sensitive Diversity for LBS[C]//Springer. 11th IFIP International Conference on Network and Parallel Computing (NPC), September 18, 2014, Taiwan, China. Heidelberg: Springer, 2014: 409-422.
[11]	SHARMA P, BALAKRISHNA G.PrefixSpan: Mining Sequential Patterns by Prefix-projected Pattern[J]. International Journal of Computer Science & Engineering Survey, 2012, 2(4): 111-122.
[12]	GIANNOTTI F, NANNI M, PINELLI D, et al.Trajectory Pattern Mining[C]//ACM. 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 12-15, 2007, San Jose, California. New York: ACM, 2007: 330-339.
[13]	ZHANG Chao, HAN Jiawei, SHOU Llidan, et al.Splitter: Mining Fine-grained Sequential Patterns in Semantic Trajectories[J]. VLDB Endowment, 2014, 7(9):769-780.
[14]	CHEN C C, KUO C H, PENG W C.Mining Spatial-temporal Semantic Trajectory Patterns from Raw Trajectories[C]//IEEE. 2015 IEEE International Conference on Data Mining Workshop, November 14-17, 2015, Atlantic City, NJ, USA. New Jersey: IEEE, 2015: 1019-1024.
[15]	WANG Liang, HU Kunyuan, KU Tao, et al.Mining Urban Moving Trajectory Patterns Based on Multi-scale Space Partition and Road Network Modeling[J]. Acta Automatica Sinica, 2015, 41(1): 47-58.
	王亮,胡琨元,库涛,等. 基于多尺度空间划分与路网建模的城市移动轨迹模式挖掘[J].自动化学报,2015,41(1):47-58.
[16]	HUO Zheng, MENG Xiaofeng, HU Haibo, et al.You Can Walk Alone: Trajectory Privacy-preserving through Significant Stays Protection[C]//Springer.17th International Conference on Database Systems for Advanced Applications, April 15-18, 2012, Busan, South Korea. Heidelberg: Springer, 2012: 351-366.
[17]	CHEN Rui, FUNG B C M, MOHAMMED N, et al. Privacy-preserving Trajectory Data Publishing by Local Suppression[EB/OL]. , 2017-10-11.
[18]	WANG Jiabo, ZHAO Zemao, LI Lin.A Method of Trajectory Privacy Protection in Location-based Service Based on Dummies[J]. Netinfo Security, 2014, 14(3): 62-67.
	王家波,赵泽茂,李林. 位置服务中一种基于假轨迹的轨迹隐私保护方法[J]. 信息网络安全,2014,14(3):62-67.
[19]	LV Mingqi, CHEN Ling, XU Zhenxing, et al. The Discovery of Personally Semantic Places Based on Trajectory Data Mining[EB/OL]. , 2017-10-11.
[20]	YUAN Jing, ZHENG Yu, ZHANG Chengyang, et al.T-drive: Driving Directions Based on Taxi Trajectories[C]//ACM. 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, November 2-5, 2010, San Jose, California. New York: ACM, 2010: 99-108.
[21]	Datatang. Avalible Online[EB/OL]. , 2016-1-13.

基于语义空间匿名的轨迹移动模式挖掘算法

Algorithm for Trajectory Movement Pattern Mining Based on Semantic Space Anonymity

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 21

相关文章 8

编辑推荐

Metrics

本文评价

[1]	戴立, 胡红钢. 免触发信号的侧信道加解密区间定位方法[J]. 信息网络安全, 2019, 19(3): 43-51.
[2]	邹建成, 徐淑情. 一种基于几何变换的数字脚印轨迹隐私保护方法研究[J]. 信息网络安全, 2017, 17(6): 1-5.
[3]	周凯, 彭长根, 何建琼, 王亚伟. 可证明安全的LBS中连续查询的轨迹隐私保护方案[J]. 信息网络安全, 2017, 17(1): 43-47.
[4]	肖剑川, 许力, 叶阿勇, 林丽美. 基于Voronoi图的路网轨迹隐私保护研究[J]. 信息网络安全, 2016, 16(6): 15-21.
[5]	马春光, 张磊, 杨松涛. 位置轨迹隐私保护综述[J]. 信息网络安全, 2015, 15(10): 24-31.
[6]	王家波;赵泽茂;李林. 位置服务中一种基于假轨迹的轨迹隐私保护方法[J]. , 2014, 14(3): 0-0.
[7]	. 位置服务中一种基于假轨迹的轨迹隐私保护方法[J]. , 2014, 14(3): 62-.
[8]	侯晏龙;焦英楠;李志刚;张宝昌. 鲁棒特征提取与行为识别[J]. , 2013, 13(11): 0-0.