一种隐私保护的在线相似轨迹挖掘方法-哈尔滨工业大学学报.PDF

第４５卷　 第 １１期 哈　 尔　 滨　 工　 业　 大　 学　 学　 报 Ｖｏｌ４５ Ｎｏ１１ 　 　 ２０ １３年１１月 ＪＯＵＲＮＡＬ ＯＦ ＨＡＲＢＩＮ ＩＮＳＴＩＴＵＴＥ ＯＦ ＴＥＣＨＮＯＬＯＧＹ Ｎｏｖ． ２０１３ 　 　 　 　 　 　 一种隐私保护的在线相似轨迹挖掘方法 赵家石，杨　 静，张健沛 （哈尔滨工程大学 计算机科学与技术学院，１５０００１哈尔滨） 摘　 要：为了解决相似轨迹挖掘中的隐私保护、轨迹数据简化和在线处理问题，提出了一种能够保护用户原始轨迹数据 隐私的在线挖掘相似轨迹的方法．该方法首先利用随机投影技术压缩和扰动原始轨迹数据，然后通过基于密度的聚类方 法判定各个时间段内相似的移动对象，采用局部敏感哈希技术寻找在足够多的时间段内都相似的移动对象，避免了传统 方法中的交集运算，实现快速估计轨迹间相似度．实验结果表明：该方法能够有效的发现相似轨迹，并且时间开销较小． 关键词：数据挖掘；隐私保护；相似模式；轨迹数据 － － － 中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：０３６７ ６２３４（２０１３）１１ ０１０１ ０５ Ｐｒｉｖａｃｙ ａｗａｒｅ ｏｎｌｉｎｅ ｍｉｎｉｎｇ ｏｆ ｓｉｍｉｌａｒ ｔｒａｊｅｃｔｏｒｉｅｓ ＺＨＡＯＪｉａｓｈｉ，ＹＡＮＧＪｉｎｇ，ＺＨＡＮＧＪｉａｎｐｅｉ （Ｃｏｌｌａｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，１５０００１Ｈａｒｂｉｎ，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｆ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ， ｔｒａｊｅｃｔｏｒｙ ｄａｔａ ｓｉｍｐｌｉｆｉｃａｔｉｏｎ ａｎｄ ｏｎｌｉｎｅ ｐｒｏｃｅｓｓｉｎｇ ａｔｔｒａｃｔ ｃｏｎｓｉｄｅｒａｂｌｅ ｅｆｆｏｒｔｓ ｆｒｏｍ ｒｅｓｅａｒｃｈｅｒｓ ｉｎ ｔｈｅ ａｒｅａ ｏｆ ｔｒａｊｅｃｔｏｒｙ ｄａｔａ ｍｉｎｉｎｇ，ｕｎｆｏｒｔｕｎａｔｅｌｙ， ｉｔ ｉｓ ｄｉｆｆｉｃｕｌｔ ｆｏｒ ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄ ｔｏｓｏｌｖｅａｌｌｔｈｅｓｅｐｒｏｂｌｅｍｓ．Ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｓａｎｏｎｌｉｎｅｓｉｍｉｌａｒｔｒａｊｅｃｔｏｒｉｅｓｍｉｎｉｎｇｍｅｔｈｏｄ ｗｈｉｃｈ ｃａｎ ｐｒｅｓｅｒｖｅ ｔｈｅ ｐｒｉｖａｃｙ ｏｆ ｏｒｉｇｉｎａｌ ｔｒａｊｅｃｔｏｒｙ ｄａｔａ． Ｔｈｅ ｍｅｔｈｏｄ ｆｉｒｓｔ ｃｏｍｐｒｅｓｓｅｄ ａｎｄ ｐｅｒｔｕｒｂｅｄ ｔｈｅ ｏｒｉｇｉｎａｌ ｄａｔａ ｂａｓｅｄ ｏｎ ｒａｎｄｏｍ ｐｒｏｊｅｃｔｉｏｎ ｔｅｃｈｎｉｑｕｅ， ｔｈｅｎ ｆｏｕｎｄ ｔｈｅ ｓｉｍｉｌａｒ ｍｏｖｉｎｇ ｏｂｊｅｃｔｓ ｉｎ ｅａｃｈ ｔｉｍｅ ｓｅｇｍｅｎｔ ｂｙ ｃｌｕｓｔｅｒｉｎｇ ｔｈｅ ｔｒａｎｓｆｏｒｍｅｄ ｄａｔａ ｂａｓｅｄ ｏｎ ｄｅｎｓｉｔｙ， ａｎｄ ｆｉｎａｌｌｙ ｉｔ ｆｏｕｎｄ ｓｉｍｉｌａｒ ｔｒａｊｅｃｔｏｒｉｅｓ ｂｙ ｅｓｔｉｍａｔｉｎｇ ｔｈａｔ ｉｆ ｔｈｅ ｔｒａｊｅｃｔｏｒｉｅｓ ｗｅｒｅ ｓｉｍｉｌａｒ ｆｏｒ ａ ｌｏｎｇ ｅｎｏｕｇｈ ｄｕｒａｔｉｏｎ ａｎｄ ｅｓｔｉｍａｔｅｄ ｔｈｅ ｓｉｍｉｌａｒｉｔｙ ｏｆ ｔｒａｊｅｃｔｏｒｉｅｓ ｕｓｉｎｇ ｌｏｃａｌ ｓｅｎｓｉｔｉｖｉｔｙ ｈａｓｈｉｎｇ． Ｔｈｉｓ ａｖｏｉｄｅｄ ｔｈｅ ｉｎｔｅｒｓｅｃｔｉｏｎ ｏｐｅｒａｔｉｏｎ ｉｎ ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄ ａｎｄ ｒｅｄｕｃｅｄ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ｔｉｍｅ． Ｔｈｅ ｅｘ