手机信令的时空密度轨迹点识别算法

手机信令具有时空序列性以及数据量大、采样频率不均、定位精度低与基站振荡等特点,导致传统手机信令聚类方法数据密度分布不均、时空开销大且聚类效果差。提出一种用于手机信令的时空密度轨迹点识别算法。将手机信令数据网格化以统一评估尺度,根据振荡噪声特征对网格簇进行时空联结减少空间不确定性和计算量,结合网络轨迹的曲折性以及移动与停留时间重新定义网格簇内轨迹点时空移动能力,计算网格簇的时空密度以判断用户停留区域,并采集具有移动停留标签的轨迹数据以验证算法有效性和识别效率。实验结果表明,该算法识别精度较改进DBSCAN算法更高,适用于识别手机信令数据停留区域,对复杂轨迹停留区域的识别效果更好。     

基于停留点聚类的多粒度热点区域分析方法

挖掘热点区域是为了满足越来越多的基于位置服务的需求,同时为了解决用户对不同地理位置的热点区域的需要在文中引入多粒度,即挖掘多个粒度的地理位置上的热点区域。本文将基于大量用户的GPS轨迹来挖掘多粒度热点区域,首先从每个用户的GPS轨迹中提取出所有的停留点并构成一个所有用户停留点的数据集,然后在该数据集上使用改进的基于密度的聚类算法ClusteringⅡ来挖掘出不同粒度上所有的热点区域,最后使用真实的GPS轨迹数据进行试验,通过实验表明我们的方法不仅在数据量上更少,而且聚类结果中的噪音数据更少。     

基于速度的轨迹停留点识别算法

轨迹中的停留点识别是将空间轨迹转换为语义轨迹的关键步骤.当前轨迹停留点识别方法缺少对轨迹记录点时间连续性的考虑,导致识别出的停留点缺乏时间信息.同时,在轨迹点缺失的情况下,停留点信息也无法被准确识别.针对上述问题,本文提出一种基于速度的时空聚类方法,首先通过缺失轨迹的时空特性确定真实缺失子轨迹,并根据缺失轨迹的平均速度对其进行插值填充,再结合轨迹速度特征和时空特性识别轨迹中的停留点.实验采用GeoLife轨迹数据集对所提出的方法进行验证,结果表明,该算法能够有效地识别用户的停留点,并对轨迹中的干扰具有一定的鲁棒性.     

基于时空模式的轨迹数据聚类算法

针对轨迹聚类算法在相似性度量中多以空间特征为度量标准,缺少对时间特征的度量,提出了一种基于时空模式的轨迹数据聚类算法。该算法以划分再聚类框架为基础,首先利用曲线边缘检测方法提取轨迹特征点;然后根据轨迹特征点对轨迹进行子轨迹段划分;最后根据子轨迹段间时空相似性,采用基于密度的聚类算法进行聚类。实验结果表明,使用所提算法提取的轨迹特征点在保证特征点具有较好简约性的前提下较为准确地描述了轨迹结构,同时基于时空特征的相似性度量因同时兼顾了轨迹的空间与时间特征,得到了更好的聚类结果。     

基于轨迹信息熵分布的异常轨迹检测方法

针对异常轨迹检测多特征检测和检测单元造成的检测效率低等问题。提出一种基于轨迹信息熵分布的异常轨迹检测方法。该算法根据轨迹偏转角与速度将轨迹分割成若干轨迹段,计算轨迹段间加权多特征距离判断轨迹间相似度,进而完成轨迹聚类并计算出每类代表性轨迹,然后对待检测轨迹进行分割,利用代表性轨迹计算每个轨迹段的信息熵,通过比较轨迹信息熵大小及其分布特点实现异常轨迹检测。大西洋飓风数据仿真实验结果表明该方法提高了聚类效果,克服以整条轨迹检测效率低的缺点,提升了异常轨迹检测算法的有效性。     

基于改进密度峰值聚类算法的轨迹行为分析

为了深入挖掘校园无线网络轨迹行为数据信息,采用基于密度的聚类方法对校园内用户的轨迹行为进行特征聚类。由于基于密度的聚类算法通常采用距离作为相似性度量方式,为了有效衔接此类聚类算法,先将用户相似度矩阵通过转换函数转变为距离矩阵。引入离群点检测算法,将离群点检测算法与聚类算法相结合,减少参数的输入个数,增加聚类的聚合程度。改进后的聚类算法可以有效检测出数据轨迹的异常,帮助高校通过对学生上网记录的处理找到浏览信息与大部分同学不一致的人,缩小目标范围,进行有针对性的处理。通过定性分析和实验对比验证,确定两种基于离群点检测的共享最近邻的快速搜索密度峰值聚类适用于校园无线网络行为轨迹相似度矩阵的处理,邓恩指数等聚类内部指标及整体性能优于同类算法。     

基于海量牧区羊群轨迹的区域属性挖掘研究*

现代畜牧业在实际放牧过程中由定位设备产生海量轨迹数据。为了从牧区日常移动轨迹中挖掘出潜在有用价值,提出一种新的基于速度扰动划分与聚类方法。该方法首先将连续定位轨迹段以速度扰动方式进行划分,设置速度扰动阈值,区分牲畜兴趣点及运动状态,并借助于聚类方法将地理位置上相似轨迹点进行聚类进而检测牲畜运动兴趣点。结合核密度分析法对聚类轨迹点进行强度可视化展示。同时,为满足处理海量轨迹数据算法需求,搭建云计算平台进行数据挖掘。理论与实验表明,本文提出的方法可以有效从海量草原牲畜运动轨迹中发现其不同兴趣区域及强度关系,并对后续相关研究具有指导意义。     

融合隐私保护的车辆轨迹数据停留点挖掘方法

随着车载GPS定位设备的普及, 产生了大量的车辆轨迹数据和位置信息, 各种轨迹挖掘技术也应运而生. 然而, 现有的轨迹挖掘技术较少考虑用户的隐私泄露问题, 因此, 本文提出了一种融合隐私保护的车辆轨迹数据停留点挖掘方法. 在该算法中, 首先通过密度聚类筛选出轨迹停留点, 其次结合差分隐私技术对停留点进行隐私保护. 通过实验验证, 该方法不仅能有效识别出停留点的位置, 还能保护其隐私不被泄露.     

iBTC:一种基于独立森林的移动对象轨迹聚类算法

移动对象轨迹聚类在城市规划、公共空间设计、移动对象行为预测等领域具有重要的理论指导意义和实际应用价值。针对传统聚类算法(如k-means,DBSCAN)在移动对象轨迹方面聚类效果不佳的问题,提出一种新的轨迹聚类算法iBTC。该算法首先对轨迹进行分段,根据最小描述长度原理,将轨迹分段问题转换为求无向图的最短路径问题,使用Dijkstra算法求得轨迹的最佳分段;然后将轨迹聚类问题转换为一种特殊的异常检测问题,并基于独立森林的思想,使用细分-合并过程对轨迹数据进行聚类;最后在模拟数据集和监控视频记录的行人轨迹公开数据集上进行实验,结果表明该算法能够取得较好的聚类效果。     

基于轨迹分析的行人异常行为识别

提出一种基于轨迹分段主题模型的异常行为检测方法。为了解决跟踪偏差引起的轨迹不连续问题,首先使用模糊聚类算法对所有的轨迹进行全局聚类,然后对每一类轨迹采用分段采样的方式对段内轨迹点使用主题模型LDA进行局部聚类;以最大概率的轨迹点作为视觉单词,每类轨迹表示成一系列视觉单词的集合,在此基础上建立局部隐马尔科夫模型HMM;最后通过轨迹匹配的方法进行异常轨迹识别。在CAVIAR数据库上的实验结果表明,该算法能识别多种异常行为,提高了异常行为检测的准确率。     

手机轨迹中活动停驻点识别

针对现有停驻点的问题,将手机用户轨迹与背景地理信息相结合,并引入功能区概念,通过考虑用户在某一功能区域内的整体活动来判断用户是否在此停驻。通过对带有标签的模拟的手机轨迹数据进行实验,证明了新的停驻点识别方法有效地避免了由于正常切换、错误切换带来的误判。停驻点的判断更为宽泛,不仅限于一个小的范围（单个基站的覆盖范围）,而是由多个相邻且功能相似小区组成的功能区中的小区集合。     

基于时空约束密度聚类的停留点识别方法

轨迹停留点的识别是轨迹分析、出行活动语义挖掘的关键。针对基于密度聚类的停留点识别方法对时空信息的表达缺陷,提出新的时空约束停留点识别方法,在密度聚类中引入轨迹的间接时空特征表示,将具有时空相似性的轨迹点进行聚合;采用与聚类过程相统一的时空特征约束对轨迹簇进行细粒度识别。算法在进行约束的时候再次利用到聚类时候所用的输入数据特征,特征的充分利用提高了识别的准确率。实验结果验证了本文方法的有效性。     

面向港口停留区域识别的船舶停留轨迹提取方法

针对港口停留区域识别时船舶轨迹大数据的精度低、稀疏、漂移等问题，提出了一种多约束条件下的船舶停留轨迹提取（MPTSSE）方法。首先，结合船舶轨迹数据特点，给出了用于停留区域识别与提取的停留段概念的定义；其次，建立了基于速度、时间差、停留时长、距离等多约束的轨迹停留段提取模型和并行化轨迹停留段提取算法；最后，基于Hadoop框架给出了船舶轨迹大数据集上的轨迹停留段提取算法实现。基于真实船舶轨迹数据的实验结果表明，与基于Stop/Move模型的轨迹停留提取方法相比，MPTSSE方法在三个港口泊位的提取中准确率提高了22%。MPTSSE方法能有效避免轨迹停留段误分割情况，同时在大规模船舶轨迹数据下具有较高的执行效率。     

一种基于最优轨迹的假查询隐私保护机制

随着移动通信技术和无线传感器的发展, 基于位置服务的应用给我们的生活带来极大的便利。在实际使用中, 用户需要向不可信的LBS服务提供商发送自己的实时位置和相关的查询信息, 这可能会导致用户的个人隐私信息遭到泄露, 特别是在使用连续位置查询服务时, 服务提供商可以利用位置的时空相关性来构建用户的轨迹信息, 进而推断出用户的居住地址、公司位置等敏感信息。传统的位置隐私保护方法通常只考虑到当前位置, 在解决连续位置查询时存在挑战, 因此, 为了解决连续位置查询中难以权衡轨迹可用性与隐私性的问题, 提出一种基于最优位置轨迹的假查询隐私保护机制。首先, 通过真实轨迹和假轨迹间的互信息来度量轨迹的隐私, 解决轨迹隐私难以量化的问题。在此基础上, 提出一种基于马尔科夫链的轨迹互信息计算方法, 简化了轨迹互信息的计算过程,并使用两条轨迹上对应位置点间的欧几里距离来量化位置轨迹的可用性。其次, 考虑到生成的假轨迹可能并不符合用户的通行习惯, 容易被识别出来, 我们选择历史轨迹作为假轨迹。为了减少轨迹上位置点的数量, 使用四叉树法对路网区域进行划分, 将轨迹划分为不同的片段, 在相关约束条件下寻找最优的历史轨迹作为假轨迹, 从而保证使用的假轨迹更加真实、合理。最后, 实验结果表明,本文的方案可以最大程度的实现位置数据隐私性和可用性平衡, 与其他方案相比, 安全性更高、系统计算开销更少。     

基于密度聚类的出租车异常轨迹检测

出租车GPS装备的普及使用产生了大量轨迹数据。出租车异常轨迹的检测和分析，可为惩罚具有欺诈行为的出租车司机提供有益支撑。针对出租车稀疏轨迹，基于轨迹相对相似度检测异常轨迹，由于其具有不对称性，类似于DBSCAN的传统密度聚类方法无法适应此种情况，本文提出基于密度RDBSCAN算法用于出租车异常轨迹聚类检测。对于聚类得出的候选异常轨迹，结合轨迹密度异常值和轨迹长度异常值的概念，利用证据理论综合前述2个因素来判别轨迹的异常程度，进而得到异常程度最高的TOP-N异常轨迹。使用旧金山真实的出租车数据，通过提取相同起点和终点（Origin-Destination, OD）的轨迹集进行实验，实验结果表明本文提出的方法能够有效地检测到异常轨迹，并成功给出异常程度最高的TOP-N异常轨迹。     

一种利用不完整数据检测交通异常的方法

城市化进程的加快带来了严重的交通问题,检测交通异常成为数据挖掘领域的热点之一。传统道路管理主要是应用视频监控,使得处理交通问题的效率受限。鉴于上述原因,提出了一种利用不完整数据检测交通异常的方法(Traffic Anomaly Detection,TAD)。首先,利用相关性聚类从手机数据中获取车辆密度信息,降低处理不完整数据的计算开销;然后,设计一个自适应无参数检测算法,根据手机呼叫量变化率捕捉车辆的分散式动态异常,以解决道路状况不确定性难题;最后,提出异常轨迹算法来追踪异常分布路线并预测影响范围,提高异常检测效率。实验结果表明,TAD方法在不同的实验环境下能够有效地检测交通异常,与现有算法相比,所提算法在有效性和伸缩性上效果更好。     

Discovering places of interest in everyday life from smartphone data

In this paper, a new framework to discover places-of-interest from multimodal mobile phone data is presented. Mobile phones have been used as sensors to obtain location information from users’ real lives. A place-of-interest is defined as a location where the user usually goes and stays for a while. Two levels of clustering are used to obtain places of interest. First, user location points are grouped using a time-based clustering technique which discovers stay points while dealing with missing location data. The second level performs clustering on the stay points to obtain stay regions. A grid-based clustering algorithm has been used for this purpose. To obtain more user location points, a client-server system has been installed on the mobile phones, which is able to obtain location information by integrating GPS, Wifi, GSM and accelerometer sensors, among others. An extensive set of experiments has been performed to show the benefits of using the proposed framework, using data from the real life of a significant number of users over almost a year of natural phone usage.     

基于连续查询的用户轨迹k-匿名隐私保护算法

随着移动服务和移动网络的持续发展,基于LBS的连续查询服务被广泛应用。基于单点的K-匿名位置隐私保护算法已经不能满足连续查询下用户位置隐私需求。针对用户轨迹隐私保护提出新的保护方法,该方法采用不可信第三方中心匿名器,用户获取自己的真实位置后首先在客户端进行模糊处理,然后提交给第三方匿名器,第三方匿名器根据用户的隐私需求结合用户某时刻的真实位置信息生成虚假用户,然后根据历史数据生成虚假轨迹。为了进一步提高虚假轨迹与用户真实轨迹的相似性,该算法提出了虚假轨迹生成的两个约束条件：虚假轨迹距用户真实轨迹的距离约束和相似性约束。经大量实验证明,该算法与传统的不同时刻K-匿名算法相比,不仅可以满足连续查询的用户轨迹隐私保护而且可以满足基于快照的LBS用户位置隐私保护。