# K-means clustering in Matlab for feature selection

I am doing feature selection on a cancer data- set which is multidimensional (27803 * 84). I want to try with k-means clustering algorithm in Matlab but how do I decide how many clusters do I want? Is it equal to the number of classes I have? (in my case- it is 2- cancer or no cancer). Please suggest. Thank you.

This is a rather well-known problem with k-means clustering - there's not a great way to choose k a priori. See http://en.wikipedia.org/wiki/Determining_the_number_of_clusters_in_a_data_set

Generally, you end up running k-means for a lot of values of k, and then choosing the best k based on some metric of goodness, several are suggested in the linked article.

You could try running a principle components analysis, to reduce the dimensionality of your space to something smaller. If you find that only a few principle components provide the dominant discrimination ability between cancer and no-cancer, you may be able to whip up some plots in the reduced dimensionality space to visually decide how many clusters.

If you have access to Science, there's an interesting algorithm discussed here http://www.sciencemag.org/content/344/6191/1492.full, which doesn't rely on sphericality like k-means does and also provides some metrics for choosing the number of clusters in a principled fashion.

• I don't think that science article is very interesting. It seems highly redundant to other algorithms for finding density peaks, such as meanshift, DENCLUE, etc. - why was it published outside the clustering community?!? Sep 25, 2014 at 10:48

Note that k-means doesn't work tool well on high-dimensional data. There are multiple reasons for this:

1. k-means is really sensitive to outliers (and you will have a lot of outliers in high-dimensional data). Because it uses squared deviations, any extreme value (i.e. outliers) has a large effect on the measured quality (least squares!)

2. k-means is very sensitive to data normalization, and it's probably hard to normalize your data appropriately. Try different normalizations, and your results will be drastically different. Also, many normalizations are sensitive to outliers, too.

3. k-means uses all dimensions. You may need to perform feature selection and weighting; and these choices may need to be different in different parts of your data. This is particularly often observed in biological data (read up on biclustering).

As for choosing k, there is plenty of literature on heuristics for that. But they are heuristics and fail more often than they work on real data.

Note that Classes are not the same thing as clusters.

In your case, there may be different kinds of cancer, that could show up as different clusters. But most likely you will also have various clusters of normal data.

It may even be reasonable to cluster on the positive/negative examples only. Because there is no use in fitting your clusters to your labels, because you already have exact labels; no need to approximate them with k-means.