# Feature / attribute selection for k-means or other clustering

It seems to me that in literature it is assumed that one knows which features / attributes to choose to characterize an item in clustering.

If I have a database with items which have many attributes, how do I know which attributes to choose for a good clustering? Is there any guideline or literature which deals with this problem?

-

There is a whole research subdomain,

Subspace clustering (Wikipedia)

Subspace clustering is the task of detecting all clusters in all subspaces. This means that a point might be a member of multiple clusters, each existing in a different subspace. Subspaces can either be axis-parallel or affine.

that deals with the problem that for different parts of your data set, different attributes may be useful for clustering.

If you also want to take correlations into account, also have a look at

Correlation clustering (Wikipedia)

Correlation clustering also relates to a different task, where correlations among attributes of feature vectors in a high-dimensional space are assumed to exist guiding the clustering process. These correlations may be different in different clusters, thus a global decorrelation cannot reduce this to traditional (uncorrelated) clustering.

But be careful, there are two different things dubbed with this term. Make sure you look at publications that deal with correlated features.

### Why not k-means

K-means is an optimization problem: minimize variance. However, this is not easily adaptable to subspace clustering. In subspace clustering, you assume that for some points, some attributes are not important. However, if you allow "ignoring" attributes, you can arbitrarily decrease variance by dropping attributes!

Furthermore, in subspace clustering you must assume that some points do not belong to any subspace cluster at all. Ignoring points, again, allows you to "cheat" with variance.

Distances - and variance is the same as squared Euclidean distance; which is why k-means uses a "least (squared Euclidean) distance assignment" - are not comparable across different dimensionality. In the physical world: which is longer, 1 meter, or 1 cubic meter? It does not work. You must not compare distances (and thus, variance) across different subspaces.

In my opinion, for all these reasons, the k-means concept of minimizing variance does not reasonably translate to high-dimensional data, or subspace clustering.

-

Are you looking for something like "best subsets regression" for clustering?

A good place to start would be a subject matter expert. Try and get rid of variables that no one believes have any impact.

Clustering can be modeled in many ways, but if you can view this as a search for modes in a mixture of multivariate normals, then perhaps a place to start would be to check each variable for multi-modality. If the marginal distribution is unimodal, then that variable is not going to become informative about cluster membership when added to others.

A similar approach would be to use part of the data set to find your clusters; then see if you can predict cluster membership from the holdout set on the basis of subsets of variables. If the number is small, you could try all combinations. Otherwise, you might have to try a stepwise approach of some kind.

-
Thank you for the hints. The mentioned "best subsets regression" seems to do what I would like to do. Select the attributes which are in some way more meaningful than other attributes for the clustering. Jain link describe this step as feature selection, but how to do this is a bit vague. So it seems that is more of an iterative process and some kind of art to find the good attributes than a determined process where I have the best attributes in the end. – user2653422 Jun 13 '14 at 14:31