13 ms·
K-means is not an algorithm, it's a heuristic for an Np-hard problem.
by another-cuppa 8y ago
K-means is not an algorithm, it's a heuristic for an Np-hard problem.
- wnkrshm 8y agoIsn't a method that gives an approximate or best-fit estimate to a problem still an algorithm, if it terminates?
- another-cuppa 8y agoNo. You can't prove that k-means does anything useful.
- alanbernstein 8y agoIs the definition of "algorithm" that you're using here useful?
- another-cuppa 8y agoIt's one of the most fundamental concepts in computer science and underpins decades of research. You can decide if it's useful.
- mindcrime 8y agoThis 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".
- another-cuppa 8y agoNah. 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.
- n4r9 8y agoTo 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.
- n4r9 8y agoIt is absolutely an algorithm in the sense of "a set of rules to be followed". I think you mean that it doesn't guarantee an optimal solution. That just means it's a heuristic algorithm, same as simulated annealing is a heuristic algorithm for solving optimisation problems.
- another-cuppa 8y agoNope. An algorithm has to be effective. You can find pathological cases for k-means such that it will never converge on anything useful. So if you set your termination case to be convergence it will never terminate and if you don't then it will never be effective.
- zaphar 8y agoI think you might be in the minority in this opinion. Many algorithms have pathological cases but are still considered algorithms
- another-cuppa 8y agoMinority? This is directly from Knuth.
- bstamour 8y agoKnuth defines effectiveness as: "... all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil." K-means and other heuristic algorithms fit that description.
- billfruit 8y agoIn that sense kmeans may be better referred to as a 'computational method' rather than an algorithm.
- another-cuppa 8y ago