Get the latest tech news

The CAP theorem of Clustering: Why Every Algorithm Must Sacrifice Something

No clustering algorithm is perfect and you must make a trade-off.

In 2002, Jon Kleinberg(in a paper published at NIPS 2002) proved something that should make every developer pause: it's impossible for any clustering algorithm to have all three properties we'd naturally want it to have. Richness is about possibilities — a clustering algorithm should be capable of producing any grouping that might make sense for your data. While Kleinberg proved this mathematically (check out his paper for the full proof), let's see how this 'pick two out of three' limitation shows up in algorithms you might be using today.

Get the Android app