一种基于字符串模型的轨迹相似度计算

Measure Similarity between Trajectories Based on Alphabetic String Model

建立字符串轨迹模型,利用双层结构进行建模,有效减少了表征轨迹时需要使用的字符总数。对LCS进行改进,使之适用于该模型,从而提高了计算轨迹间距离的精度。通过比较,改进的距离计算方法与多维向量组轨迹模型下距离计算方法的计算时间,作为衡量计算速率的标准。利用多维标度技术(MDS)将得到的距离矩阵映射到二维空间中,通过人工标识MIT停车场行人路径数据,计算类间、类内距离的均值和方差,衡量距离计算方法的精度。最后通过路径数据中的四类典型问题,验证本文设计的方法在解决实际问题中的能力。实验表明,改进LCS应用于双层字符串轨迹模型,在时间消耗上最优,精度最高,能很好的解决四类典型问题。

The trajectories by alphabetic string with a two double-layer structure is established, in order to mea- suse s ：milarity between trajectories rapidly and accurately. This model decreases the number of characters which are used to express trajectories. The LCS is improved according to the double-layer alphabetic string model in order to improve the accuracy of calculation. The time cost in two different models is also compared which reflects the speed of calculation . In order to compare the accuracy of each method, The MIT parkinglot dataset and import MDS are labeled to map the matrix of distances into 2-D coordinates in order to calculate the means and variance in- ter-clusters and intra-clusters. At last, the new method is used to solve four kinds of representative problems. Through experiments, the conclusion is made that our method based on double-layer alphabetic string model per- forms best in time cost and accuracy. It can also solve the representative problems very well.