K-means is probabilistically poor

• Autorzy: Kłopotek Mieczysław

Identyfikatory

DOI

10.34739/si.2022.27.01

• Języki publikacji: EN

Abstrakty

EN

Kleinberg introduced the concept of k-richness as a requirement for an algorithm to be a clustering algorithm. The most popular algorithm k means dos not fit this definition because of its probabilistic nature. Hence Ackerman et al. proposed the notion of probabilistic k-richness claiming without proof that k-means has this property. It is proven in this paper, by example, that the version of k-means with random initialization does not have the property probabilistic k-richness, just rebuking Ackeman's claim.

Słowa kluczowe

EN

k-means; clustering; probabilistic k-richness

• Wydawca: Wydawnictwo Uniwersytetu Przyrodniczo-Humanistycznego w Siedlcach
• Czasopismo: Studia Informatica : systems and information technology
• Rocznik: 2022
• Tom: Vol. 2(27)
• Strony: 5--26
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Kłopotek Mieczysław

• Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland

• https://orcid.org/0000-0003-4685-7045

Bibliografia

• 1. Ackerman M., Ben-David S., and Loker D. Towards property-based classification of clustering paradigms. In J.D. Lafferty, C.K.I. Williams, J. ShaweTaylor, R.S. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems 23, pages 10-18. Curran Associates, Inc., 2010.
• 2. Ackerman M., Ben-David S., Loker D., and Sabato S. Clustering oligarchies. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2013, Scottsdale, AZ, USA, April 29 - May 1, 2013, pages 66-74, 2013.
• 3. Bandyopadhyay S. and Murty M. N. Axioms to characterize efficient incremental clustering. In Proceedings of the 23rd International Conference on Pattern Recognition, pages 450-455. IEEE, 2016.
• 4. Ben-David S. Attempts to axiomatize clustering, 2005. NIPS Workshop, December 2005.
• 5. Ben-David S. and Ackerman M. Measures of clustering quality: A working set of axioms for clustering. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Advances in Neural Information Processing Systems 21, pages 121-128. Curran Associates, Inc., 2009.
• 6. Correa-Morris J. An indication of unification for different clustering approaches. Pattern Recognition, 46(9):2548-2561, 2013.
• 7. Hopcroft J. and Kannan R. Computer science theory for the information age, 2012. chapter 8.13.2. A Satisfiable Set of Axioms. page 272ff.
• 8. Kleinberg J. An impossibility theorem for clustering. In Proc. NIPS 2002, pages 446-453, 2002. http://books.nips.cc/papers/files/nips15/LT17.pdf.
• 9. Kłopotek R. A. and Kłopotek M. A. On probabilistic krichness of the k-means algorithms. In Giuseppe Nicosia, Panos M. Pardalos, Renato Umeton, Giovanni Giuffrida, and Vincenzo Sciacca, editors, Machine Learning, Optimization, and Data Science - 5th International Conference, LOD 2019, Siena, Italy, September 10-13, 2019, Proceedings, volume 11943 of Lecture Notes in Computer Science, pages 259-271. Springer, 2019.
• 10. Meilă M. Comparing clusterings: An axiomatic view. In Proceedings of the 22Nd International Conference on Machine Learning, ICML '05, pages 577-584, New York, NY, USA, 2005. ACM.
• 11. Strazzeri F. and Sánchez-García R. J. Possibility results for graph clustering: A novel consistency axiom. https://arxiv.org/abs/https://arxiv.org/abs/1806.06142, 2021.
• 12. Laarhoven T. and Marchiori E. Axioms for graph clustering quality functions. Journal of Machine Learning Research, 15:193-215, 2014.
• 13. Wierzchoń S.T. and Kłopotek M. A. Modern Clustering Algorithms. Springer Verlag Series: Studies in Big Data 34. Springer, 2018.
• 14. Zadeh R. B. and Ben-David S. A uniqueness theorem for clustering. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI '09, pages 639-646, Arlington, Virginia, United States, 2009. AUAI Press.
• 15. Mohammad Z. A. A PAC-Theory of Clustering with Advice. PhD thesis, University of Waterloo, 2018.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).