基于GPS轨迹的规律路径挖掘算法.docx

基于ＧＰＳ轨迹的规律路径挖掘算法何雯１，２，李德毅１，２，安利峰１，张天雷１，郭沐１，陈桂生２（１．清华大学计算机科学与技术系，北京１０００８４；２．中国电子系统工程研究所，北京１００８４０）摘要：基于用户的历史轨迹数据，对用户的规律路径进行挖掘和提取。在轨迹预处理和聚类的基础上，定义了支撑路径的概念，提出了一种基于支撑得分的规律轨迹挖掘算法。并通过规律停止率特征，提高了对轨迹交通模式识别的准确率。基于１７８名用户４年的ＧＰＳ轨迹记录，以及３７名用户的实际轨迹数据，开展了用户试验。结果表明，本文算法能够有效地提取用户的规律路径，并对路径中的干扰具有一定的鲁棒性。关键词：人工智能；轨迹挖掘；规律路径；交通模式；位置服务中图分类号：ＴＰ１８；ＴＰ３９１文献标志码：Ａ文章编号：１６７１－５４９７（２０１４）０６－１７６４－０７ＤＯＩ：１０．１３２２９／ｊ．ｃｎｋｉ．ｊｄｘｂｇｘｂ２０１４０６０３５ＲｅｇｕｌａｒｒｏｕｔｅｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎＧＰＳｔｒａｊｅｃｔｏｒｉｅｓＨＥＷｅｎ１，２，ＬＩＤｅ－ｙｉ１，２，ＡＮＬｉ－ｆｅｎｇ１，ＺＨＡＮＧＴｉａｎ－ｌｅｉ１，ＧＵＯＭｕ１，ＣＨＥＮＧｕｉ－ｓｈｅｎｇ２（１．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ１０００８４，Ｃｈｉｎａ；２．ＩｎｓｔｉｔｕｔｅｏｆＥｌｅｃｔｒｏｎｉｃＳｙｓｔｅｍＥｎｇｉｎｅｅｒｉｎｇｏｆＣｈｉｎａ，Ｂｅｉｊｉｎｇ１００８４０，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｂａｓｅｄｏｎｕｓｅｒｓ＇ｈｉｓｔｏｒｉｃａｌｔｒａｊｅｃｔｏｒｙｄａｔａ，ｕｓｅｒｓ＇ｒｅｇｕｌａｒｒｏｕｔｅｓｗｅｒｅｍｉｎｅｄａｎｄｅｘｔｒａｃｔｅｄ．Ａｃｏｎｃｅｐｔｏｆｓｕｐｐｏｒｔｒｏｕｔｅｗａｓｄｅｆｉｎｅｄａｆｔｅｒｒｏｕｔｅｐｒｅ－ｐｒｏｃｅｓｓｉｎｇａｎｄｇｒｏｕｐｉｎｇ．Ａｒｅｇｕｌａｒｒｏｕｔｅｍｉｎｉｎｇａｌｇｏｒｉｔｈｍｗａｓｐｒｏｐｏｓｅｄｂａｓｅｄｏｎｔｈｅｓｕｐｐｏｒｔｓｃｏｒｅ．ＡｆｅａｔｕｒｅｏｆＲｅｇｕｌａｒＳｔｏｐＲａｔｅ（ＲＳＲ）ｗａｓｕｓｅｄｔｏｉｍｐｒｏｖｅｔｈｅａｃｃｕｒａｃｙｏｆｔｈｅｔｒａｎｓｐｏｒｔａｔｉｏｎｍｏｄｅｒｅｃｏｇｎｉｔｉｏｎ．ＴｈｅｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅａｐｐｒｏａｃｈｗａｓｖａｌｉｄａｔｅｄｂａｓｅｄｏｎｔｈｅＧＰＳｄａｔａｏｆ１７８ｕｓｅｒｓｏｖｅｒｆｏｕｒｙｅａｒｓ．Ａｒｅａｌｕｓｅｒｓｔｕｄｙｗａｓａｌｓｏｐｅｒｆｏｒｍｅｄａｍｏｎｇ３７ｕｓｅｒｓ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｒｅｓｕｌｔｓｄｅｍｏｎｓｔｒａｔｅｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｃａｎｅｆｆｅｃｔｉｖｅｌｙｅｘｔｒａｃｔｔｈｅｒｅｇｕｌａｒｒｏｕｔｅｓａｎｄｉｓｒｏｂｕｓｔｔｏｓｌｉｇｈｔｄｉｓｔｕｒｂａｎｃｅｉｎｔｒａｊｅｃｔｏｒｙｄａｔａ．Ｋｅｙｗｏｒｄｓ：ａｒｔｉｆｉｃｉａｌｉｎｔｅｌｌｉｇｅｎｔ；ｔｒａｊｅｃｔｏｒｙｍｉｎｉｎｇ；ｒｅｇｕｌａｒｒｏｕｔｅｓ；ｔｒａｎｓｐｏｒｔａｔｉｏｎｍｏｄｅ；ｌｏｃａｔｉｏｎｂａｓｅｄｓｅｒｖｉｃｅ惯、生活经验等。近年来，随着ＧＰＳ智能终端的普及，越来越多的人开始习惯于记录并分享轨迹日志。基于这些日志，可以分析并挖掘出用户的一些行为特征，从而为用户提供个性化的基于位置的智能服务，有效地提升和改善用户的应用体引言０用户行为是开展用户推荐和个性化用户服务的基础。用户轨迹是用户行为的重要组成部分，不仅包含用户的出行信息，还包含用户的出行习收稿日期：２０１３－０４－２７．基金项目：国家自然科学基金重点项目９０９２０３０５）．作者简介：何雯（１９８２－），女，博士研究生．研究方向：智能交通，空时数据挖掘．Ｅ－ｍａｉｌ：ｈｅ－ｗ０９＠ｍａｉｌｓ．ｔｓｉｎｇｈｕａ．ｅｄｕ．ｃｎ通信作者：李德毅（１９４４－），男，研究员．研究方向：不确定人工智能，智能交通，网络数据挖掘，云计算．Ｅ－ｍａｉｌ：ｌｉｄｙ＠ｃａｅ．ｃｎ·１７６５·第６期何雯，等：基于ＧＰＳ轨迹的规律路径挖掘算法验。从ＧＰＳ轨迹中删除停留区域的数据点。本文采用文献［８］的方法对停留区域进行检测。一个停留区域Ｓ｛ｐｍ，ｐｍ＋１，…，ｐｎ｝Ｔ满足：ｄ（ｐｍ，ｐｎ）＜δ且ｄ（ｐｍ，ｐｎ＋１）＞δ规律路径是用户行为中频繁且最具预测性的行为，对理解和预测用户行为具有重要意义。规律轨迹在气象、生态等领域也有着广泛的应用［１－３］。近年来，很多学者对用户的ＧＰＳ轨迹进行了分析和挖掘。例如，对用户个人路径的挖掘和预测［４－５］，以及对用户行为目的的推测［６－７］。Ｇｉｄｏｆａｌｖｉ等［８］基于车辆的ＧＰＳ数据，挖掘了可共享的最长路径。郭黎敏等［９］针对