title: Partition into classes: jenks vs kmeans
body: <p>I want to partition a vector (length around 10^5) into five classes. With the function <code>classIntervals</code> from package <code>classInt</code> I wanted to use <code>style = "jenks"</code> natural breaks but this takes an inordinate amount of time even for a much smaller vector of only 500. Setting <code>style = "kmeans"</code> executes almost instantaneously. </p>
  
  <pre><code>library(classInt)
  
  my_n &lt;- 100
  set.seed(1)
  x &lt;- mapply(rnorm, n = my_n, mean = (1:5) * 5)
  
  system.time(classIntervals(x, n = 5, style = "jenks"))
  R&gt; system.time(classIntervals(x, n = 5, style = "jenks"))
     user  system elapsed 
    13.46    0.00   13.45 
  
  system.time(classIntervals(x, n = 5, style = "kmeans"))
  R&gt; system.time(classIntervals(x, n = 5, style = "kmeans"))
     user  system elapsed 
     0.02    0.00    0.02
  </code></pre>
  
  <p>What makes the Jenks algorithm so slow, and is there a faster way to run it? </p>
  
  <p>If need be I will move the last two parts of the question to stats.stackexchange.com: </p>
  
  <ul>
  <li>Under what circumstances is kmeans a reasonable substitute for Jenks? </li>
  <li>Is it reasonable to define classes by running classInt on a random 1% subset of the data points?</li>
  </ul>