论文部分内容阅读
随着GPS定位、传感器网络和无线通信等应用的日益普及,越来越多的行为轨迹数据被收集和保存在应用服务器,如校园一卡通数据,公交卡数据,大型企业员工刷卡数据等。这些数据中蕴含了丰富有价值的知识。通过这些数据,可以进行大量的分析研究,包括轨迹聚类、轨迹分类、异常检测等。其中,异常检测是行为轨迹数据研究的一个重要方向。行为轨迹数据表达了一个对象在一定的时间、地点进行某项活动。相同群体的对象其行为具有相似性,发现与大多数对象在行为上的不同对象具有重要意义。行为轨迹数据可分为三类,基于时间的、基于位置的和基于事件的,本文研究的是基于事件的行为轨迹数据,此类数据在时间上是离散的。异常对象检测是找出其行为很不同于预期对象的过程。在行为轨迹数据中,独立对象是由若干个相互联系的点组成的。现有的在行为轨迹数据中检测异常对象的问题大多是基于对连续时间序列的轨迹数据进行异常检测,一般采用的方法是提取序列特征,形成序列模式,通过模式匹配来检测异常对象。对于基于事件触发的轨迹数据的异常检测,目前虽然已经有了一定研究成果,但是在实际的应用场景中,由于事件的不确定性等因素,还没有一种完全适合各种应用场景的异常检测算法。本文研究基于事件的行为轨迹数据,且对象间存在着层次分组关系,基于以上两点,本文将行为轨迹相似度的计算引入到异常对象检测算法中,通过行为轨迹相似度进行异常对象检测。在异常对象检测算法中,行为轨迹相似度的计算是至关重要的。为了准确、高效的计算行为轨迹相似度,本文提出了两种行为轨迹相似度的定义,同时提出了四种异常对象检测算法,分别为基于一对一滑动窗口算法,基于一对多滑动窗口算法,基于单重哈希表算法和基于双重哈希表算法。在这四种算法中,基于一对多滑动窗口算法是在基于一对一滑动窗口算法的基础上改进的,是将分组中的所有对象看作一个整体而提高算法效率。基于单重哈希表算法和基于双重哈希表的算法都是基于哈希表的策略设计的,能够在最短的时间找到匹配项。在数据量较大时,基于哈希表算法在整体性能上比基于滑动窗口算法要好。本文采用某高校真实的校园一卡通数据进行实验,综合评估了四个算法的性能。实验结果表明,当数据量较小时,四个算法的效率相差不大,但随着数据量的逐渐增大,基于哈希表的两个算法效率明显比基于滑动窗口的两个算法效率高。同时,本文还分析了影响行为轨迹相似度计算的参数一时间阈值对各算法性能的影响,从结果可以看出,合适的时间阈值能够提高算法效率。本文还对top-k异常对象作了实验分析,验证了本文提出的将行为轨迹相似度的计算引入异常对象检测的有效性。