Trajectory Outlier Detection Based On Kernel Function

With the rapid development of GPS, RFID, sensor Wi-Fi and widely using of smart mobile devices, the trajectory data of moving objects has an explosive growth. How to find valuable information in the trajectory data set is an important issue Moving objects trajectory outlier detection as an important branch of trajectory data mining can find potential valuable abnormality information. This thesis focuses on the research of the technologies of trajectory outlier detection. The major work is as follows.Most existing trajectory outlier detection algorithms just focused on the geospatial location of trajectory, and ignore other important features of moving objects such as speed, direction and so on. Moreover, feature extraction in original input space is ineffective. This thesis proposed a trajectory outlier detection method based on KPCA(TOD-KPCA). Firstly, we perform preprocess to normalize the length of trajectories. Then, mapping the trajectories from original input space to higher-dimensional space and do feature extraction. Finally, we use one-class SVM to do unsupervised learning and outlier detection on trajectory features. This method can serve as a framework for combing other trajectory features. The experiments show that TOD-KPCA performs effectively.Most existing kernel based trajectory outlier detection algorithms use resampling methods to convert variable-length trajectories to fixed-length trajectories, which have an adverse effect on the original features of trajectories. This thesis proposed a variable-length trajectory outlier detection method based on KPCA and Fast Global Alignment Kernel(VTOD-FGAK) to deal with variable-length trajectories. The method use fast global alignment kernel as the mapping kernel function of KPCA. Fast global alignment kernel can deal variable-length trajectories effectively and maintain the original features, avoid the human disturbance, improve the accuracy of outlier detection, some shorter abnormal trajectories can be found out. The experiments show that VTOD-FGAK performs effectively.For KPCA, the eigen decomposition of kernel matrix is O(N3), this will severely handicap the computation of KPCA on large high-dimensional dataset. Aimed to the problem, this thesis proposed a incremental trajectory outlier detection method based on incremental KPCA. The method uses KES split and merge algorithm to update the kernel eigenspace model. Maintain a fixed-size sliding window, when M newly trajectory data arrived, remove old M trajectory data from the feature space and then add the M newly trajectory data to the eigenspace. The method only need calculate the eigenspace of the M newly trajectory and update the kernel eigenspace model based on the original kernel eigenspace model of sliding window. This can reduce the computational complexity. The experiments shows to be efficient.Based on the research of theory in this thesis, we design and realize the trajectory outlier detection system. The system offers functions on TOD-KPCA, VTOD-FGAK and incremental trajectory outlier detection. At each step, a simple parameter setting interface and visualization display for outlier detection results are presents.