# Advice for clustering a tricky data set

I have a set of data with about 15,000 vectors which fall into three classes all with the same number of vectors. Some of the data is categorical and some numerical so I am using DictVectorizer to convert it to a sparse matrix. This performs a one-hot encoding of the categorical data. Here are the key facts and my problem.

• If I build a Random Forest I get very good accuracy for classification. One-versus-rest gives me over 0.95 for the AUC for example. However Logistic Regression, for example, does not give a good result at all (AUC of around 0.55). On the other hand a large decision tree with 1,000 leaves also gives an AUC of around 0.9. This is mean AUC using cross-validation.
• I can't find an unsupervised way to cluster the data however which gives a good result at all. For example, I tried KMeans but the clusters it finds are not well separated.

The fact that the decision tree works well makes me suspect that the data has a very particular form which makes KMeans (with the default settings at least) unsuitable. I think I need maybe to find a clustering method that effectively builds a decision tree for each cluster.

What can I try that might work for clustering such data?

This is mostly an experiment at the moment so I can learn more about clustering, which is new to me. If there is anything about the data that would be helpful to know, please ask.

• What dimensionality is the data? The first thing you should do is plot it. There are also methods for using random forests for clustering, though I don't think scikit-learn has them built in. – Dougal Sep 26 '15 at 7:22
• @Dougal After conversion to numerical data it is 15,000 by ~300. I did try PCA and then plotting it in 2d but it wasn't hugely informative. I would be very interested in a random forest based clustering method if there is any code for that available. – Lembik Sep 26 '15 at 7:28
• Maybe you should clarify your motivation for wanting to cluster the data. For instance, you seem to have built a pretty good classifier using random forests so what is your motivation for employing those unsupervised learning approaches--are you trying to reduce the size of your data first? – Steve S Sep 26 '15 at 8:43
• Also, remember that plotting your data in two dimensions will only be revealing if a substantial amount of information can be captured by the first two principal components (and cramming 300 dimensions of info into the plane will probably not leave you with anything too fruitful)... – Steve S Sep 26 '15 at 8:51
• @SteveS My motivation is partly just to understand the methods and data better. However I also have a lot of unlabelled data from a similar source and I am hoping to be able to infer new classes within that once I have a method that works on the labelled part. I hope that makes sense. – Lembik Sep 26 '15 at 9:55

## 1 Answer

I think you should focus on dimensionality reduction. The following two facts give me that intution:

1. It is not unusual that KMeans fails in such a high dimensional space, as the "distance between any two points in a given (high dimensional) dataset converges".
2. PCA can also fail if the principal axes of the classes are parallel to each other ("ADIDAS problem"). In this case Linear discriminant analysis (LDA) for dimensionality reduction could help. You could also give Local Linear Embedding/Laplacian Eigenmaps a try - these are dimensionality reduction techniques that want to preserve the structure of the high dimensional dataset in the lower dimensions.

Unfortunately I haven't used scikit yet, so I don't know which techniques are implemented there...

• Thank you. LDA and LLE are both available in scikit learn (see eg scikit-learn.org/stable/modules/generated/…). I will try them out. However I worry the partly categorical nature of the original data may be part of what makes clustering hard and also what makes decision trees work well. – Lembik Sep 26 '15 at 9:58
• I found another thread which supports your worries about clustering with categorical data: datascience.stackexchange.com/questions/22/… – Kanzler Sep 26 '15 at 10:33