Document Open Access Logo

Temporal Hierarchical Clustering

Authors Tamal K. Dey, Alfred Rossi, Anastasios Sidiropoulos

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.28.pdf
  • Filesize: 3.08 MB
  • 12 pages

Document Identifiers

Author Details

Tamal K. Dey
Alfred Rossi
Anastasios Sidiropoulos

Cite As Get BibTex

Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos. Temporal Hierarchical Clustering. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.28

Abstract

We study hierarchical clusterings of metric spaces that change over time. This is a natural geo- metric primitive for the analysis of dynamic data sets. Specifically, we introduce and study the problem of finding a temporally coherent sequence of hierarchical clusterings from a sequence of unlabeled point sets. We encode the clustering objective by embedding each point set into an ultrametric space, which naturally induces a hierarchical clustering of the set of points. We enforce temporal coherence among the embeddings by finding correspondences between successive pairs of ultrametric spaces which exhibit small distortion in the Gromov-Hausdorff sense. We present both upper and lower bounds on the approximability of the resulting optimization problems.

Subject Classification

Keywords
  • clustering
  • hierarchical clustering
  • multi-objective optimization
  • dynamic metric spaces
  • moving point sets
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Ali Abam and M. de Berg. Kinetic spanners in ℝ^d. In SOCG, 2009. URL: http://doi.acm.org/10.1145/1542362.1542371.
  2. M. Ackerman and S. Dasgupta. Incremental clustering: The case for extra clusters. In NIPS, 2014. Google Scholar
  3. D. Arthur and S. Vassilvitskii. k-means++: the advantages of careful seeding. In SODA, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283494.
  4. J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data. In SODA, 1997. URL: http://dl.acm.org/citation.cfm?id=314161.314435.
  5. D. Burago, Y. Burago, and S. Ivanov. A Course in Metric Geometry. AMS, 2001. Google Scholar
  6. G. E. Carlsson and F. Mémoli. Characterization, stability and convergence of hierarchical clustering methods. JMLR, 11, 2010. Google Scholar
  7. M. Charikar, C. Chekuri, T. Feder, and R. Motwani. Incremental clustering and dynamic information retrieval. In STOC, 1997. Google Scholar
  8. T. K. Dey, A. Rossi, and A. Sidiropoulos. Spectral concentration, robust k-center, and simple clustering. CoRR, abs/1404.1008, 2014. URL: http://arxiv.org/abs/1404.1008.
  9. T. K. Dey, A. Rossi, and A. Sidiropoulos. Temporal clustering. In ESA, volume 87 of LIPIcs, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.34.
  10. T. K. Dey, A. Rossi, and A. Sidiropoulos. Temporal clustering. CoRR, abs/1704.05964, 2017. URL: http://arxiv.org/abs/1704.05964.
  11. T. K. Dey, A. Rossi, and A. Sidiropoulos. Temporal hierarchical clustering. CoRR, abs/1707.09904, 2017. URL: http://arxiv.org/abs/1707.09904.
  12. J. Eldridge, M. Belkin, and Y. Wang. Beyond hartigan consistency: Merge distortion metric for hierarchical clustering. In COLT, volume 40, 2015. Google Scholar
  13. M. Farach, S. Kannan, and T. J. Warnow. A robust model for finding optimal evolutionary trees. In STOC, 1993. URL: http://doi.acm.org/10.1145/167088.167132.
  14. E. W. Forgy. Cluster analysis of multivariate data: efficiency versus interpretability of classifications. Biometrics, 21, 1965. Google Scholar
  15. S. A. Friedler and D. M. Mount. Approximation algorithm for the kinetic robust k-center problem. Comput. Geom., 43(6-7), 2010. Google Scholar
  16. H. Gabow and R. Tarjan. Faster scaling algorithms for network problems. SIAM J. Comput., 18(5), 1989. URL: https://doi.org/10.1137/0218069.
  17. J. Gao, L. J. Guibas, and A. Thanh Nguyen. Deformable spanners and applications. In SOCG, 2004. URL: http://doi.acm.org/10.1145/997817.997848.
  18. D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Math. Oper. Res., 10(2), 1985. URL: https://doi.org/10.1287/moor.10.2.180.
  19. A. K. Jain and R. C. Dubes. Algorithms for Clustering Data. Prentice-Hall, 1988. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact