<p>There are many possible ways of making clustering repeatable:</p>

<ul>
<li>The most basic method of dealing with k-means randomness is simply running it multiple times and selecting the best one (the one that minimizes the inner cluster distances/maximizes the between clusters distance).</li>
<li>One can use some <a href="http://arxiv.org/abs/1304.7465" rel="noreferrer">fixed initialization</a> for your data instead of randomization. There are many heuristics for starting the k-means. Or at least minimize the variance by using algorithms like <a href="http://en.wikipedia.org/wiki/K-means++" rel="noreferrer">k-means++.</a></li>
<li>Use modification of k-means which guarantees global minimum of regularized function, ie. <a href="http://www.control.isy.liu.se/research/reports/2011/2992.pdf" rel="noreferrer">convex k-means</a></li>
<li>Use different clustering method, which is deterministic, ie. <a href="https://www.google.pl/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;ved=0CCwQFjAA&amp;url=http://eccc.hpi-web.de/report/2004/050/download/&amp;ei=Z1srUqWSNqSt4ASAwICoDA&amp;usg=AFQjCNGT67wor9Z322tZBJsJGICq0JHnSA&amp;sig2=uS4_K146acIJgawM70El5g" rel="noreferrer">Data Nets</a></li>
</ul>
How To Fight Randomness Caused By KMeans Clustering
<p>I'm developing an algorithm to classify different types of dogs based off of image data. The steps of the algorithm are:</p>

<ol>
<li><p>Go through all training images, detect image features (ie SURF), and extract descriptors. Collect all descriptors for all images.</p></li>
<li><p>Cluster within the collected image descriptors and find k "words"  or centroids within the collection.</p></li>
<li><p>Reiterate through all images, extract SURF descriptors, and match the extracted descriptor with the closest "word" found via clustering.</p></li>
<li><p>Represent each image as a histogram of the words found in clustering.</p></li>
<li><p>Feed these image representations (feature vectors) to a classifier and train...</p></li>
</ol>

<p>Now, I have run into a bit of a problem. Finding the "words" within the collection of image descriptors is a very important step. Due to the random nature of clustering, different clusters are found each time I run my program. The unfortunate result is that sometimes the accuracy of my classifier will be very good, and other times, very bad. I have chalked this up to the clustering algorithm finding "good" words sometimes, and "bad" words other times.</p>

<p>Does anyone know how I can hedge against the clustering algorithm from finding "bad" words? Currently I just cluster several times and take the mean accuracy of my classifier, but there must be a better way.</p>

<p>Thanks for taking time to read through this, and thank you for your help!</p>

<p>EDIT:</p>

<p>I am not using KMeans for classification; I am using a Support Vector Machine for classification. I am using KMeans for finding image descriptor "words", and then using these words to create histograms which describe each image. These histograms serve as feature vectors that are fed to the Support Vector Machine for classification.</p>