邓 超 ,罗 泽 ,阎保平

(1.中国科学院计算机网络信息中心,北京 100190；2.中国科学院大学,北京 100049)

1 概述

随着传感器网络、全球定位系统(Global Positioning System,GPS)、手持移动设备和射频识别(Radio Frequency Identification,RFID)等设备的普遍应用,大量的移动对象数据被积累下来[1-2]。在此背景下,针对历史轨迹数据挖掘技术的研究成为当前研究的热点,时空模式发现是主要的研究方向之一,包括时空频繁模式挖掘、时空同现模式挖掘和时空关联模式挖掘[3]。然而,在时空数据挖掘的众多模式中,同现模式的挖掘占有重要地位。

同现模式挖掘就是发现在时间和空间上共同出现的时空对象,比如,两只鸟在飞行过程中在同一时间同一地点出现。重要同现模式挖掘就是发现那些在某区域内同时出现并持续足够长时间的时空对象,重要同现模式不仅包括了同现,还限定了同现必须持续一定长的时间,比如,某几个人可能在一起开会,他们会同时出现在会议室并持续一定时间,或者某些动物群体性的迁徙过程中一起出现在某个区域,并停留了很长时间。

同现模式挖掘的研究已经有了比较长的历史。文献[4]提出空间数据的频繁同现邻居挖掘,使用同现位置的对象数量作为支持量来衡量同现位置的重要程度。文献[5-6]提出一种基于Apriori 算法的同现模式挖掘算法框架,使用参与率来取代支持量,这使得同现评价指标更有统计意义。此外,还有基于聚类方法的同现模式挖掘[7-9]。文献[10]提出基于密度的同现模式挖掘,该算法通过将对象分区,优先处理密集分区的样本,减少了Apriori 算法连接次数,提升了效率,但该算法没有考虑时间信息。……