Knowledge discovery from GPS trajectory data is an important topic in several scientific areas, including data mining, human behavior analysis, and user modeling. This paper proposes a task that assigns personalized visited-POIs. Its goal is to estimate fine-grained and pre-defined locations (i.e., points of interest (POI)) that are actually visited by users and assign visited-location information to the corresponding span of their (personal) GPS trajectories. We also introduce a novel algorithm to solve this assignment task. First, we exhaustively extract stay-points as candidates for significant locations using a variant of a conventional stay-point extraction method. Then we select significant locations and simultaneously assign visited-POIs to them by considering various aspects, which we formulate in integer linear programming. Experimental results conducted on an actual user dataset show that our method achieves higher accuracy in the visited-POI assignment task than the various cascaded procedures of conventional methods.
Various stay-point extraction methods have already been proposed. For example, Ashbrook and Starner @cite_13 @cite_19 use a modified @math -means method, @cite_20 use DBSCAN @cite_9 , and @cite_39 employ Mean-Shift @cite_24 , all of which are based on clustering. @cite_25 and @cite_26 assume that stay-points are positions within a constant radius from a center where the stay time exceeds a constant time. More recently, @cite_23 developed a more robust stay-point extraction algorithm that considers outliers and missing points in GPS trajectories.
@cite_26 @cite_9 @cite_39 @cite_24 @cite_19 @cite_23 @cite_13 @cite_25 @cite_20
2779280457 1993221692 2076943964 2199495299
We tackle the problem of extracting stay regions from a geospatial trajectory where a user has stayed longer than a certain time threshold. There are four major difficulties with this problem: (1) stay regions are not only point-type ones such as at a bus-stop but large and arbitrary-shaped ones such as at a shopping mall; (2) trajectories contain spatial outliers; (3) there are missing points in trajectories; and (4) trajectories should be analyzed in an online mode. Previous algorithms cannot overcome these difficulties simultaneously. Density-based batch algorithms have advantages over the previous algorithms in discovering of arbitrary-shaped clusters from spatial data containing outliers; however, they do not consider temporal durations and thus have not been used for extracting stay regions. We extended a density-based algorithm so that it would work in a duration-based manner online and have robustness to missing points in stay regions while keeping its advantages. Experiments on real trajectories of 13 users conducting their daily activities for three weeks demonstrated that our algorithm statistically significantly outperformed five state-of-the-art algorithms in terms of F1 score and works well without trajectory preprocessing consisting of filtering, interpolating, and smoothing. We propose a novel keypoint-based method for long-term model-free object tracking in a combined matching-and-tracking framework. In order to localise the object in every frame, each keypoint casts votes for the object center. As erroneous keypoints are hard to avoid, we employ a novel consensus-based scheme for outlier detection in the voting behaviour. To make this approach computationally feasible, we propose not to employ an accumulator space for votes, but rather to cluster votes directly in the image space. By transforming votes based on the current keypoint constellation, we account for changes of the object in scale and rotation. In contrast to competing approaches, we refrain from updating the appearance information, thus avoiding the danger of making errors. The use of fast keypoint detectors and binary descriptors allows for our implementation to run in real-time. We demonstrate experimentally on a diverse dataset that is as large as 60 sequences that our method outperforms the state-of-the-art when high accuracy is required and visualise these results by employing a variant of success plots. Spatio-temporal and geo-referenced datasets are growing rapidly, with the rapid development of some technology, such as GPS, satellite systems. At present, many scholars are very interested in the clustering of the trajectory. Existing trajectory clustering algorithms group similar trajectories as a whole and can't distinguish the direction of trajectory. Our key finding is that clustering trajectories as a whole could miss common sub-trajectories and trajectory has direction information. In many applications, discovering common sub-trajectories is very useful. In this paper, we present a trajectory clustering algorithm CTHD (clustering of trajectory based on hausdorff distance). In the CTHD, the trajectory is firstly described by a sequence of flow vectors and partitioned into a set of sub-trajectory. Next the similarity between trajectories is measured by their respective Hausdorff distances. Finally, the trajectories are clustered by the DBSCAN clustering algorithm. The proposed algorithm is different from other schemes using Hausdorff distance that the flow vectors include the position and direction. So it can distinguish the trajectories in different directions. The experimental result shows the phenomenon. In k-means clustering we are given a set of n data points in d-dimensional space Rd and an integer k, and the problem is to determine a set of k points in &#211C;d, called centers, to minimize the mean squared distance from each data point to its nearest center. No exact polynomial-time algorithms are known for this problem. Although asymptotically efficient approximation algorithms exist, these algorithms are not practical due to the extremely high constant factors involved. There are many heuristics that are used in practice, but we know of no bounds on their performance.We consider the question of whether there exists a simple and practical approximation algorithm for k-means clustering. We present a local improvement heuristic based on swapping centers in and out. We prove that this yields a (9+e)-approximation algorithm. We show that the approximation factor is almost tight, by giving an example for which the algorithm achieves an approximation factor of (9-e). To establish the practical value of the heuristic, we present an empirical study that shows that, when combined with Lloyd's algorithm, this heuristic performs quite well in practice.