1d optimal clustering I have the following problem - i have a range of numbers (ie. [1, 5, 7, 8, 15, 29, 100]). I need to cluster them OPTIMALLY (not local optimum as in lloyd algorithm) and better than NP time, minimizing as in k-means problem (to find points such that squared distances from clustroids to points of clusters are minimized). 
So far I found only some paper on the dynamic solution for k-means but it seems too difficult. Can someone suggest some possible way to do this.
 A: The R package Ckmeans.1d.dp provides a dynamic programming approach to find the optimal solution to the k-means objective in one dimension. It's discussed in:

Wang and Song (2011). Ckmeans.1d.dp: Optimal $k$-means Clustering in One Dimension by Dynamic Programming. The R Journal Vol. 3/2. pdf

This may be what you meant by "I found only some paper on the dynamic solution for k-means but it seems too difficult," but you may not have realized that there's just an R package you can call to avoid having to implement the algorithm yourself. It's really not that bad to implement, anyway, and I doubt there's going to be a simpler optimal algorithm in polynomial time.
A: 1-dimensional data is a lot easier, and the problem is not NP-hard in 1 dimension.
Try the following approach:


*

*Sort the data!

*Rather than assigning points to clusters, you partition the data into k non-empty intervals. So for $k=2$, you would put one point into the first interval, all others into the second. Then put two points into the first, all others into the second. And so on. There are several shortcuts you can implement for this, I'm not going to detail this.
The cost of this is $O(n \ log(n))$ for sorting (with tiny constants) and $O(n^{k-1})$ (without improvements) for enumerating all possible partitions. Thus, for small $k$, it is not exponential. (For large $k$, the bound may actually be $O((n-k)^{k-1})$ by disallowing empty partitions.)
There are some fairly easy strategies to avoid having to check all such partitions; but exploiting order is the easiest to avoid $O(k^n)$ cost.
