title: Determining the best k for a k nearest neighbour
body: <p>I have need to do some cluster analysis on a set of 2 dimensional data (I may add extra dimensions along the way). </p>
  
  <p>The analysis itself will form part of the data being fed into a visualisation, rather than the inputs into another process (e.g. <a href="http://en.wikipedia.org/wiki/Radial_basis_network" rel="nofollow noreferrer">Radial Basis Function Networks</a>). </p>
  
  <p>To this end, I'd like to find a set of clusters which primarily "looks right", rather than elucidating some hidden patterns. </p>
  
  <p>My intuition is that <a href="http://en.wikipedia.org/wiki/K-means_clustering" rel="nofollow noreferrer">k-means</a> would be a good starting place for this, but that finding the right number of clusters to run the algorithm with would be problematic.</p>
  
  <p>The problem I'm coming to is this: </p>
  
  <p><strong>How to determine the 'best' value for</strong> <em>k</em> <strong>such that the clusters formed are stable and visually verifiable</strong>?</p>
  
  <p>Questions:</p>
  
  <ul>
  <li>Assuming that this isn't NP-complete, what is the time complexity for finding a good <em>k</em>. (probably reported in number of times to run the k-means algorithm).</li>
  <li>is k-means a good starting point for this type of problem? If so, what other approaches would you recommend. A specific example, backed by an anecdote/experience would be maxi-bon.</li>
  <li>what short cuts/approximations would you recommend to increase the performance.</li>
  </ul>