This is one of those interesting mathematical attempts to formalize a very human “I know it when I see it” quality. So maybe k-means is a poorly defined task if you don’t know k. Then you end up with the meta task of defining k, which has its problems, as seen in the paper. K-means alone, on some unknown data, without knowing the distance metric, and with no other heuristics or analysis, is going to go wrong. But if you are performing a dataset specific task, in a known vector space, with a good understanding of the outcome, then it’s really useful. The problem is probably that people learn that k-means is an unsupervised learning algorithm, and apply it incorrectly.
