16th AIAI 2020, 5 -7 June 2020, Greece

k-means Cluster Shape Implications

Mieczysław Kłopotek, Sławomir Wierzchoń, Robert Kłopotek


  We present a novel justification why k-means clusters should be (hyper)ball-shaped ones. We show that the clusters must be ballshaped to attain motion-consistency. If clusters are ball-shaped, one can derive conditions under which two clusters attain the global optimum of k-means. We show further that if the gap is sufficient for perfect separation, then an incremental k-means is able to discover perfectly separated clusters. This is in conflict with the impression left by an earlier publication by Ackerman and Dasgupta. The proposed motion-transformations can be used to the new labeled data for clustering from existent ones.  

*** Title, author list and abstract as seen in the Camera-Ready version of the paper that was provided to Conference Committee. Small changes that may have occurred during processing by Springer may not appear in this window.