Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3469096.3474937acmconferencesArticle/Chapter ViewAbstractPublication PagesdocengConference Proceedingsconference-collections
short-paper

Efficient sparse spherical k-means for document clustering

Published: 16 August 2021 Publication History

Abstract

Spherical k-Means is frequently used to cluster document collections because it performs reasonably well in many settings and is computationally efficient. However, the time complexity increases linearly with the number of clusters k, which limits the suitability of the algorithm for larger values of k depending on the size of the collection. Optimizations targeted at the Euclidean k-Means algorithm largely do not apply because the cosine distance is not a metric. We therefore propose an efficient indexing structure to improve the scalability of Spherical k-Means with respect to k. Our approach exploits the sparsity of the input vectors and the convergence behavior of k-Means to reduce the number of comparisons on each iteration significantly.

References

[1]
Marcel R. Ackermann, Christiane Lammersen, Marcus Märtens, Christoph Raupach, Christian Sohler, and Kamil Swierkot. 2010. StreamKM++: A clustering algorithm for data streams. In 2010 Proceedings of the 12th Workshop on Algorithm Engineering and Experiments, ALENEX 2010.
[2]
Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni. 2009. Streaming k-means approximation. In Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference.
[3]
Jon Louis Bentley. 1975. Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM (1975).
[4]
Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and Brian Tagiku. 2011. Streaming k-means on well-clusterable data. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
[5]
Deepayan Chakrabarti, Ravi Kumar, and Andrew Tomkins. 2006. Evolutionary clustering. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
[6]
Inderjit S. Dhillon and Dharmendra S. Modha. 2001. Concept decompositions for large sparse text data using clustering. Machine Learning (2001).
[7]
Charles Elkan. 2003. Using the Triangle Inequality to Accelerate k-Means. In Proceedings, Twentieth International Conference on Machine Learning.
[8]
Jeff Johnson, Matthijs Douze, and Herve Jegou. 2019. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data (2019). arXiv:1702.08734
[9]
Alain Lelu and Martine Cadot. 2020. Evaluation of Text Clustering Methods and their Dataspace Embeddings: an Exploration. In Data Analysis and Rationality in a Complex World. https://hal.archives-ouvertes.fr/hal-03053176
[10]
Stuart P. Lloyd. 1982. Least Squares Quantization in PCM. IEEE Transactions on Information Theory (1982).
[11]
Gerard Salton and Christopher Buckley. 1988. Term-weighting approaches in automatic text retrieval. Information Processing and Management 24, 5 (1988), 513--523. arXiv:115
[12]
Christina Teflioudi and Rainer Gemulla. 2016. Exact and approximate maximum inner product search with LEMP. ACM Transactions on Database Systems (2016).

Cited By

View all
  • (2023)Toward Visually Analyzing Dynamic Social Messages and News Articles Containing Geo-Referenced InformationVolunteered Geographic Information10.1007/978-3-031-35374-1_6(133-146)Online publication date: 9-Dec-2023
  • (2022)Document clusteringWIREs Computational Statistics10.1002/wics.158814:6Online publication date: 8-Jun-2022

Index Terms

  1. Efficient sparse spherical k-means for document clustering

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      DocEng '21: Proceedings of the 21st ACM Symposium on Document Engineering
      August 2021
      178 pages
      ISBN:9781450385961
      DOI:10.1145/3469096
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 16 August 2021

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. document clustering
      2. k-means
      3. large-scale analysis

      Qualifiers

      • Short-paper

      Funding Sources

      Conference

      DocEng '21
      Sponsor:
      DocEng '21: ACM Symposium on Document Engineering 2021
      August 24 - 27, 2021
      Limerick, Ireland

      Acceptance Rates

      Overall Acceptance Rate 194 of 564 submissions, 34%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)7
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 16 Nov 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2023)Toward Visually Analyzing Dynamic Social Messages and News Articles Containing Geo-Referenced InformationVolunteered Geographic Information10.1007/978-3-031-35374-1_6(133-146)Online publication date: 9-Dec-2023
      • (2022)Document clusteringWIREs Computational Statistics10.1002/wics.158814:6Online publication date: 8-Jun-2022

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media