(k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping

• URL: http://arxiv.org/abs/2012.00464v1
• Date: Tue, 1 Dec 2020 13:17:27 GMT
• Title: (k, l)-Medians Clustering of Trajectories Using Continuous Dynamic Time Warping
• Authors: Milutin Brankovic, Kevin Buchin, Koen Klaren, Andr\'e Nusser, Aleksandr Popov, Sampson Wong
• Abstract summary: In this work we consider the problem of center-based clustering of trajectories. We propose the usage of a continuous version of DTW as distance measure, which we call continuous dynamic time warping (CDTW) We show a practical way to compute a center from a set of trajectories and subsequently iteratively improve it.
• Score: 57.316437798033974
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Due to the massively increasing amount of available geospatial data and the need to present it in an understandable way, clustering this data is more important than ever. As clusters might contain a large number of objects, having a representative for each cluster significantly facilitates understanding a clustering. Clustering methods relying on such representatives are called center-based. In this work we consider the problem of center-based clustering of trajectories. In this setting, the representative of a cluster is again a trajectory. To obtain a compact representation of the clusters and to avoid overfitting, we restrict the complexity of the representative trajectories by a parameter l. This restriction, however, makes discrete distance measures like dynamic time warping (DTW) less suited. There is recent work on center-based clustering of trajectories with a continuous distance measure, namely, the Fr\'echet distance. While the Fr\'echet distance allows for restriction of the center complexity, it can also be sensitive to outliers, whereas averaging-type distance measures, like DTW, are less so. To obtain a trajectory clustering algorithm that allows restricting center complexity and is more robust to outliers, we propose the usage of a continuous version of DTW as distance measure, which we call continuous dynamic time warping (CDTW). Our contribution is twofold: 1. To combat the lack of practical algorithms for CDTW, we develop an approximation algorithm that computes it. 2. We develop the first clustering algorithm under this distance measure and show a practical way to compute a center from a set of trajectories and subsequently iteratively improve it. To obtain insights into the results of clustering under CDTW on practical data, we conduct extensive experiments.

Related papers

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Fuzzy K-Means Clustering without Cluster Centroids [21.256564324236333]
  Fuzzy K-Means clustering is a critical technique in unsupervised data analysis. This paper proposes a novel Fuzzy textitK-Means clustering algorithm that entirely eliminates the reliance on cluster centroids.
  arXiv  Detail & Related papers  (2024-04-07T12:25:03Z)
• Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering [1.3927943269211591]
  Efficiently solving a vehicle routing problem in a practical runtime is a critical challenge for delivery management companies. This paper explores both a theoretical and experimental connection between the Capacitated Vehicle Problem (CVRP) and the Constrainedid-Based Clustering (CCBC) The proposed framework consists of three stages. At the first step, a constrained centroid-based clustering algorithm generates feasible clusters of customers.
  arXiv  Detail & Related papers  (2024-03-20T22:24:36Z)
• Distribution-Based Trajectory Clustering [14.781854651899705]
  Trajectory clustering enables the discovery of common patterns in trajectory data. The distance measures employed have two challenges: high computational cost and low fidelity. We propose to use a recent Isolation Distributional Kernel (IDK) as the main tool to meet all three challenges.
  arXiv  Detail & Related papers  (2023-10-08T11:28:34Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Fast conformational clustering of extensive molecular dynamics simulation data [19.444636864515726]
  We present an unsupervised data processing workflow that is specifically designed to obtain a fast conformational clustering of long trajectories. We combine two dimensionality reduction algorithms (cc_analysis and encodermap) with a density-based spatial clustering algorithm (HDBSCAN) With the help of four test systems we illustrate the capability and performance of this clustering workflow.
  arXiv  Detail & Related papers  (2023-01-11T14:36:43Z)
• Adaptively-weighted Integral Space for Fast Multiview Clustering [54.177846260063966]
  We propose an Adaptively-weighted Integral Space for Fast Multiview Clustering (AIMC) with nearly linear complexity. Specifically, view generation models are designed to reconstruct the view observations from the latent integral space. Experiments conducted on several realworld datasets confirm the superiority of the proposed AIMC method.
  arXiv  Detail & Related papers  (2022-08-25T05:47:39Z)
• ThetA -- fast and robust clustering via a distance parameter [3.0020405188885815]
  Clustering is a fundamental problem in machine learning where distance-based approaches have dominated the field for many decades. We propose a new set of distance threshold methods called Theta-based Algorithms (ThetA)
  arXiv  Detail & Related papers  (2021-02-13T23:16:33Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• Ball k-means [53.89505717006118]
  The Ball k-means algorithm uses a ball to describe a cluster, focusing on reducing the point-centroid distance computation. The fast speed, no extra parameters and simple design of the Ball k-means make it an all-around replacement of the naive k-means algorithm.
  arXiv  Detail & Related papers  (2020-05-02T10:39:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.