论文部分内容阅读
人们在日常活动中产生了各式各样的移动轨迹数据,如GPS移动轨迹数据,手机移动轨迹数据等等。这些移动轨迹包含着大量信息,在安全监控领域,数据挖掘领域等等都存在着广泛的研究和应用前景,对移动轨迹数据进行不同尺度的数据挖掘是个研究热点。我们以移动轨迹数据作为研究对象,从微观到宏观的两个角度出发对移动轨迹数据进行了挖掘研究,首先在微观的具体移动轨迹检索问题上设计了一系列算法,之后再宏观的基于移动轨迹的聚团发现问题上进行了扩展研究并提出了新方法,同时还实现了一个演示系统。在微观的涉及具体的移动轨迹检索问题上,我们提出了一系列新的索引结构和算法用于检索移动轨迹。创新点在于:1.首度设计了一种新的线索树结构为移动轨迹建立索引。3.首度提出了一种新的启发式算法用于在检索轨迹时,减少检索的数据规模。新算法能够有效减少检索的时间开销,提高检索移动轨迹数据的效率。这个新的算法目前被我们应用于手机的安全监控领域,我们提出了一种新的辅助视频监控的手机识别方案。只需输入一条关于目标人物的视频监控轨迹,我们就能在手机轨迹库中检索到与之相匹配的手机轨迹,提取出手机轨迹中的手机ID,从中辨识出目标人物的手机。我们在广州市的手机轨迹数据集上(40GB,1亿多条记录)进行了算法的测试工作,实验表明使用超过4个不同的监控点即可几乎唯一确定某个手机用户,算法查询时间消耗不到1秒。在宏观的基于移动轨迹的聚团发现问题上,我们提出了一种新的基于熵的层次聚类算法。其创新点在于:1.新算法首度使用了新的信息熵指导函数用于聚团的合并。2.新算法首度同时结合了轨迹数据点间的空间信息和拓扑连接关系指导聚类,是一种新的层次聚类算法。我们将新算法应用于GPS采集的移动轨迹数据中的社团或区域聚团的发现。新算法能找出移动轨迹数据中的那些在空间上相接近,内部个体彼此的联系上紧密,在对外联系上又相似的团体或区域聚团,这在诸如疾病扩散控制,电网耗电规律发现,定向广告推送等应用领域中可以起到指导作用。本文使用了纽约市计程车GPS轨迹数据集(11GB,近2亿条记录)对新算法进行了实验,实验表明新算法能够准确的划分出具有意义的区域聚团。