Hacker News Reader

Isn't a method that gives an approximate or best-fit estimate to a problem still an algorithm, if it terminates?

No. You can't prove that k-means does anything useful.

Is the definition of "algorithm" that you're using here useful?

It's one of the most fundamental concepts in computer science and underpins decades of research. You can decide if it's useful.

This isn't a classroom, and your pedantry isn't adding anything useful to the conversation. We all understand these pedantic quibbles you're arguing about... and what the community is more or less collectively saying is "in this context, we don't care about the distinction between an 'algorithm' in the textbook sense, and a 'heuristic' in the textbook sense".

Nah. Most of them don't understand the difference. If you did you wouldn't can it pedantry.

I personally don't find heuristics beautiful. That's why I commented.

To be fair, you haven't explained at all clearly why you don't think k-means adheres to Knuth's notion of an algorithm.

Your objection seems to be

> You can find pathological cases for k-means such that it will never converge on anything useful

As has been pointed out more than once, a good implementation of k-means is guaranteed to terminate in a finite time. And whatever you mean by "useful" doesn't seem to appear in Knuth's definition of an algorithm.

Reply on news.ycombinator.com