# Do I need to drop variables that are correlated/collinear before running kmeans?

I am running kmeans to identify clusters of customers. I have approximately 100 variables to identify clusters. Each of these variables represent the % of spend by a customer on a category. So, if I have 100 categories, I have these 100 variables such that sum of these variables is 100% for each customer. Now, these variables are strongly correlated with each other. Do I need to drop some of these to remove collinearity before I run kmeans?

Here is the sample data. In reality I have 100 variables and 10 million customers.

Customer CatA CatB CatC
1         10%  70%  20%
2         15%  60%  25%

• Have you tried PCA analysis in order to decorrelate your data? – Miroslav Sabo Jun 21 '13 at 10:17
• "Collinear" isn't quite the same as "correleted". So your question remains unclear – ttnphns Jun 21 '13 at 12:02
• Closely related: on removing correlated variables before doing PCA. – whuber Nov 19 '13 at 15:23

Don't drop any variables, but do consider using PCA. Here's why.

Firstly, as pointed out by Anony-mousse, k-means is not badly affected by collinearity/correlations. You don't need to throw away information because of that.

Secondly, if you drop your variables in the wrong way, you'll artificially bring some samples closer together. An example:

Customer CatA CatB CatC
1        1    0    0
2        0    1    0
3        0    0    1


(I've removed the % notation and just put values between 0 and 1, constrained so they all sum to 1.)

The euclidean distance between each of those customers in their natural 3d space is $\sqrt{(1-0)^2+(0-1)^2+(0-0)^2} = \sqrt{2}$

Now let's say you drop CatC.

Customer CatA CatB
1        1    0
2        0    1
3        0    0


Now the distance between customers 1 and 2 is still $\sqrt{2}$, but between customers 1 and 3, and 2 and 3, it's only $\sqrt{(1-0)^2+(0-0)^2}=1$. You've artificially made customer 3 more similar to 1 and 2, in a way the raw data doesn't support.

Thirdly, collinerarity/correlations are not the problem. Your dimensionality is. 100 variables is large enough that even with 10 million datapoints, I worry that k-means may find spurious patterns in the data and fit to that. Instead, think about using PCA to compress it down to a more manageable number of dimensions - say 10 or 12 to start with (maybe much higher, maybe much lower - you'll have to look at the variance along each component, and play around a bit, to find the correct number). You'll artificially bring some samples closer together doing this, yes, but you'll do so in a way that should preserve most of the variance in the data, and which will preferentially remove correlations.

~~~~~

EDIT:

Re, comments below about PCA. Yes, it absolutely does have pathologies. But it's pretty quick and easy to try, so still seems not a bad bet to me if you want to reduce the dimensionality of the problem.

On that note though, I tried quickly throwing a few sets of 100 dimensional synthetic data into a k-means algorithm to see what they came up with. While the cluster centre position estimates weren't that accurate, the cluster membership (i.e. whether two samples were assigned to the same cluster or not, which seems to be what the OP is interested in) was much better than I thought it would be. So my gut feeling earlier was quite possibly wrong - k-means migth work just fine on the raw data.

• I think a lot of care must be taken when eliminating variables by PCA. First of all the variances must be normalized before such elimination as you can incorrectly eliminate variables just because they have different scale due to their units. Secondly after that I would eliminate only those dimensions that have miniscule variation, because since PCA assumes an orthogonal basis if you have variation in a non-orthogonal direction this will be captured by k-means but eliminated by PCA. – Cowboy Trader Nov 19 '13 at 12:20
• A more fundamental concern is that PCA on the independent variables gives no information at all about the dependent variable. It is easy to construct examples where this PCA approach will eliminate every variable that matters and keep only those that don't! To see what's going on, let $(X_1,X_2)$ have a bivariate Normal distribution with variances of $1$ and correlation $\rho\gt 0$ and set $Y=X_1-X_2$. A PCA on data from $(X_1,X_2)$ will identify $X_1+X_2$ as the principal component and eliminate $X_1-X_2$. Regressing $Y$ on $X_1+X_2$ will be nonsignificant. – whuber Nov 19 '13 at 15:21
• It is irrelevant discussion in the unsupervised setting. For supervised setting yes PCA doesn't care about the relationship to the target variable. If the direction of dependency falls in the direction of low variance bad luck. – Cowboy Trader Nov 19 '13 at 17:49

On a toy example in 2d or 3d, it shouldn't make much of a difference, it just adds some redundancy to your data: all your points are on an odd, (d-1) dimensional hyperplane. So are the cluster means. And distance in this (d-1) dimensional hyperplane is a linear multiple of the same distance, so it doesn't change anything.

If you artificially construct such data, e.g. by doing $(x,y)\mapsto(x,y,x+y)$ then you do distort space, and emphasize the influence of $x$ and $y$. If you do this to all variables it does not matter; but you can easily change weights this way. This empasizes the known fact that normalizing and weighting variables is essential. If you have correlations in your data, this is more important than ever.

Let's look at the simplest example: duplicate variables.

If you run PCA on your data set, and duplicate a variable, this effectively means putting duplicate weight on this variable. PCA is based on the assumption that variance in every direction is equally important - so you should, indeed, carefully weight variables (taking correlations into account, also do any other preprocessing necessary) before doing PCA.

• In light of my analysis at stats.stackexchange.com/a/50583, this reasoning appears to be incorrect. – whuber Nov 19 '13 at 15:24
• I have much improved my answer, it was too much based on the toy example data. – Anony-Mousse Apr 21 '15 at 4:47

It's advisable to remove variables if they are highly correlated.

Irrespective of the clustering algorithm or linkage method, one thing that you generally follow is to find the distance between points. Keeping variables which are highly correlated is all but giving them more, double the weight in computing the distance between two points(As all the variables are normalised the effect will usually be double).

In short the variables strength to influence the cluster formation increases if it has a high correlation with any other variable.