The Research For Clustering Methods Based On Hidden Markov Models For Trajectories

With the development of Internet and computer technology, the number of video has a sharp increase. This enriches people’s life, but it results in accumulation of video resources because we can’t process the data in time. Trajectories are widely used to describe the content of vidoes because its characters can describe the video content comprehensively. Clustering trajectories into group is the crucial step in these research. In the article, the main research is how to cluster trajectories using hidden markov models. It mainly includes three aspects:1. Construct distance matrix of trajectories based on the reference hidden markov models. Those existing clustering methods based on hidden makrov models usually need a great deal of computation, especially in the process of constructing distance matrix. In this process, it should train each trajectory in data set into hidden markov model, and then every trajectory learns the parameters of each model. The time complexity of this process is 0(n2), if the number of the data set is n. To solve this issue, it will uses the reference trajectories to implement this process. Select a certain number trajectories as the reference trajectories set from the total trajectories at random, and then train each of them into the hidden markov model as a reference hidden makov models set. Finally, get the matrix based on this models set. The time complexity is 0(n × r), r is the number of this reference trajectories.2. Calculate the similarity of two trajectories using dot product. There are five distance metric methods usually used in clustering methods based on hidden markov models:POR, YY, SYM, BP and KL distance. The first four methods have a simple operation, but the clustering results is not so good. The main problem is that they all contain part of trajectories information. The KL distance includes the whole information of two trajectories, but the complexity of it is too bigger than the other methods. So the KL method can get a better results unsurprisingly, but give up the efficiency of clustering process. In this article, it uses an effective distance method to calculate the similarity of two trajectories. The experiments explain that this method is effective and also it outperforms other distance metric methods. When the reference HMM is 500, the F1 is higher 2% than the KL method with HMMs obtained by the whole trajectory data set.3. Cluster trajectories using spectral clustering method. Comparing with traditional clustering methods (k-means), Spectral clustering method has many fundamental advantages. The process of spectral clustering is simple, this make the whole clustering process is effective. And it always outperform many traditional method in experimental. The experiment results show that when the class of trajectories is 5, the method use spectral clustering is about 1% higher than kmeans, and when the class is 25, the spectral clustering is about 20% higher than kmeans. So the spectral clustering will be more effective than kmeans in this kind of clustering methods.