Fréchet Kernel for Trajectory Data Analysis

Trajectory analysis has been a central problem in applications of location tracking systems. Recently, the (discrete) Frechet distance becomes a popular approach for measuring the similarity of two trajectories because of its high feature extraction capability. Despite its importance, the Frechet distance has several limitations: (i) sensitive to noise as a trade-off for its high feature extraction capability; and (ii) it cannot be incorporated into machine learning frameworks due to its non-smooth functions. To address these problems, we propose the Frechet kernel (FRK), which is associated with a smoothed Frechet distance using a combination of two approximation techniques. FRK can adaptively acquire appropriate extraction capability from trajectories while retaining robustness to noise. Theoretically, we find that FRK has a positive definite property, hence FRK can be incorporated into the kernel method. We also provide an efficient algorithm to calculate FRK. Experimentally, FRK outperforms other methods, including other kernel methods and neural networks, in various noisy real-data classification tasks.