CODEWITHSUNDEEP
machine-learningcomputer-visioncluster-analysisk-means
caring-goat-913
caring-goat-913

Reputation: 4049

How To Fight Randomness Caused By KMeans Clustering

I'm developing an algorithm to classify different types of dogs based off of image data. The steps of the algorithm are:

  1. Go through all training images, detect image features (ie SURF), and extract descriptors. Collect all descriptors for all images.

  2. Cluster within the collected image descriptors and find k "words" or centroids within the collection.

  3. Reiterate through all images, extract SURF descriptors, and match the extracted descriptor with the closest "word" found via clustering.

  4. Represent each image as a histogram of the words found in clustering.

  5. Feed these image representations (feature vectors) to a classifier and train...

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.

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.

Thanks for taking time to read through this, and thank you for your help!

EDIT:

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.

Upvotes: 5

Views: 3570

Answers (3)

Ben Allison
Ben Allison

Reputation: 7394

I would offer two possible suggestions, in addition to those provided.

K-means optimises an objective related to the distance between cluster points and their centroids. You care about classification accuracy. Depending on the computational cost, a simple brute-force approach is to induce multiple clusterings on a subset of your training data, and evaluate the performance of each on some held-out development set for the task you care about. Then use the highest performing variant as the final model. I don't like the use of non-random initialisation because this is only a solution to avoid the randomness, not find the true global minimum of the objective, and your chosen initialisation may be useless and just produce consistently bad classifiers.

The other approach, which is much harder, is to view the k-means step as a dimensionality reduction to enable classification, and incorporate this into the classifier directly. If you use a deep neural net, the layer(s) closest to the input are essentially dimensionality reducers in the same way as the k-means clustering you induce: the difference is their weights are set wrt the error of the net on the classification problem, rather than some unrelated intermediate step. The downside is that this is much closer to a current research problem: training deep nets is hard. You could start with a standard one-hidden-layer architecture (with binary activations on the hidden layer, and using cross-entropy loss on the output layer with outputs coded as one-of-n categories), and attempt to add layers incrementally, but as far as I'm aware standard training algorithms start to behave poorly beyond the single hidden layer, so you'd need to investigate layer-wise training to initialise, or some of the Hessian-Free stuff coming out of Geoff Hinton's group in Toronto.

Upvotes: 2

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

That is actually an important problem with the BofW approach, and you should share this prominently. SIFT data may actually not have k-means clusters at all. However, due to the nature of the algorithm, k-means will always produce k clusters. One of the things to test with k-means is to validate that the results are stable. If you get a completely different result each time, they are not much better than random.

Nevertheless, if you just want to get some working results, you can just fix the dictionary once and choose one that is working well.

Or you might look into more advanced clustering (in particular one that is more robust wrt. noise!)

Upvotes: 1

lejlot
lejlot

Reputation: 66795

There are many possible ways of making clustering repeatable:

  • 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).
  • One can use some fixed initialization 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 k-means++.
  • Use modification of k-means which guarantees global minimum of regularized function, ie. convex k-means
  • Use different clustering method, which is deterministic, ie. Data Nets

Upvotes: 6

Related Questions