电子学报 ›› 2015, Vol. 43 ›› Issue (11): 2338-2344.DOI: 10.3969/j.issn.0372-2112.2015.11.029

• 科研通信 • 上一篇    

基于稀疏化最小生成树聚类的个性化轨迹隐私保护算法

王超, 杨静, 张健沛   

  1. 哈尔滨工程大学计算机科学与技术学院, 黑龙江 哈尔滨 150001
  • 收稿日期:2014-02-19 修回日期:2014-04-11 出版日期:2015-11-25 发布日期:2015-11-25
  • 作者简介:王超 男,1988年生于河北省沧州市.哈尔滨工程大学计算机科学与技术学院博士研究生.主要研究方向为数据库与知识工程、数据挖掘、隐私保护.E-mail:wangchao0605@hrbeu.edu.cn;杨静 女,1962年生于黑龙江哈尔滨.哈尔滨工程大学计算机科学与技术学院教授、博士生导师.主要研究方向为数据库与知识工程、数据挖掘、隐私保护、软件理论等.E-mail:yangjing@hrbeu.edu.cn
  • 基金资助:

    国家自然科学基金(No.61370083,No.61073041,No.61073043);高等学校博士学科点专项科研基金(No.20112304110011,No.20122304110012);哈尔滨市科技创新人才研究专项资金(优秀学科带头人No.2011RFXXG015)

The Sparse Minimum Spanning Tree Clustering Based Personalized Trajectory Privacy Protection Algorithm

WANG Chao, YANG Jing, ZHANG Jian-pei   

  1. College of Computer Science and Technology, Harbin Engineering University, Harbin, Heilongjiang 150001, China
  • Received:2014-02-19 Revised:2014-04-11 Online:2015-11-25 Published:2015-11-25

摘要:

现有的轨迹匿名算法没有充分考虑轨迹内外在特征信息以及移动对象个性化的隐私需求.为此,本文提出个性化轨迹k-匿名的概念,并提出轨迹结构相似性度量模型,综合考虑轨迹方向、速度、转角和位置等内外在特征信息;然后,提出基于稀疏化最小生成树聚类的个性化隐私保护算法,通过稀疏化的方法降低最小生成树聚类的执行时间,通过贪婪策略生成近似最优的轨迹k-匿名集合.实验结果表明,本文的轨迹结构相似性度量模型能更加准确地度量轨迹间的相似性,所提算法花费了更少的时间代价,具有更高的数据可用性.

关键词: 轨迹相似性, 个性化轨迹k-匿名, 稀疏化, 最小生成树聚类, k-节点划分

Abstract:

The existing trajectory anonymity methods can not reflect the trajectory internal and external characteristics information well,and ignore personalized privacy requirements of moving objects.To solve these problems,we propose a new similarity measure model of trajectory structure,which considers the trajectory internal and external characteristics information of direction、speed、angle and location.On this basis,we propose the sparse minimum spanning tree clustering based personalized trajectory privacy protection algorithm.It reduces runtime by sparse methods,and generates an approximate optimal trajectory k-anonymity set by greedy strategy.Finally,the results showed our new similarity measure model of trajectory structure can calculate distance of trajectories more accurately,and our method offers better utility and costs less time than previous proposals in the literature.

Key words: trajectory similarity, personalized trajectory k-anonymity, sparse methods, minimum spanning tree clustering, k-node partition

中图分类号: