基于FP-Tree模型的频繁轨迹模式挖掘方法

FP-Tree-Based Approach for Frequent Trajectory Pattern Mining

通过对经典频繁模式数据结构FP-tree的扩展与改进,提出了一种适用于处理轨迹数据的灵活高效的FP-tree轨迹挖掘方法(NFTM)。首先运用二维筛选和GPS格式过滤的方法对轨迹进行预处理,然后将有效数据经一次扫描后,生成按照真实轨迹顺序排列且具备时空属性的改进型FP-tree,使用动态数组存储模式挖掘过程中得到的候选集,根据用户的输入针对性输出相应时间和频率范围的频繁轨迹。最后通过与GSP算法、Prefixspan算法的对比测试表明,该算法具有更短执行时间和更优性能。

Frequent trajectory pattern mining algorithms research focuses on how to make frequent pattern mining algorithms suitable for the mining of temporal and spatial trajectory database and reduce the times of scanning database. This paper proposes a novel trajectory mining algorithms based on novel FP-tree trajectory mining（NFTM）for a more flexible and efficient data processing which is achieved by the improvement and extension of the classic algorithm of frequent pattern structure FP-tree. The first step is the preprocessing of the original locus by using two-dimensional screening and the GPS format sifting. Then the valid data are scanned once only to generate the improved type of FP-tree, which is permutated based on the order of the authentic locus and which is also of the space-time attribute. The candidate collection derived from the process of the pattern mining in dynamic digit group storage is creatively applied. The frequent locus in the corresponding period and frequency range is output in line with users＇ input. Finally, through tests in comparison with two prevalent algorithms -- the GSP algorithm and the Prefixspan algorithm, the conclusion is drawn that the new algorithm has the advantages of shorter executing time and greater ability.