On discovery of learned paths from taxi origin-destination trajectories

The increasing pervasiveness of GPS applications has enabled collection of huge amount of taxi trajectories. Discovering the learned paths between origin and destination can convey valuable knowledge to a variety of essential applications. In this paper, we propose scheduling schemes which are based on the section vectors of taxi trajectories, and sample paths are clustered into several classes. Since section vectors which belong to different class have different length usually, spectral clustering method is adopted. One of critical point of the method is to establish similarity matrix of all the different objects, and we further develop a kind of well thought out way to solve the point by combining the length of section with LCS (Longest Common Sequence). What´s more, for testing the validity of cluster number according to the eigenvalues of similarity matrix, WBDR (Within-Between Distance Ratio) algorithm based on k-means is put forward. Simulation results show that both algorithms can get reasonable cluster result.