pedromnasc's blog

1 Dimensional Clustering
By pedromnasc, 11 years ago, In English

Hello,

I was thinking on problem of 1D clustering. I have n points and i want to partition them in k sets minimizing the within-cluster sum of squares, like here: http://en.wikipedia.org/wiki/K-means_clustering#Description. I can solve this problem using dynamic programming in O(n^2 * k). Can i improve this time? Can i use divide and conquer optimization? If yes, how to proof it?

Thanks!

EDIT: Here's a paper that explains the standard dynamic programming O(n^2 * k): http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Think abouth convex hull trick optimization. Makes complexity to O(KNlogN)

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Based on this: http://codeforces.me/blog/entry/8219 , isn't clear to me how to put the recorrence in the form of Convex Hull Optimization2. For me it fits better in Divide and Conquer Optimization, but i can't proof that it's correct and i don't know a fast way to calculate the cost function using Divide and Conquer Optimization.

    → Reply