# Noise in clustering of high dimensional sparse data

Questions:
1) How to detect noise variables in high dimensional data?
2) Does the method that is presented below make sense?
3) What clustering methods are most insensitive to random variables in data?

I'm made an experiment, the data was generated as follows:

• Number of clusters is equal 10
• There are 100 variables
• Each variables is equal to 1 with probability 0.01
• For each cluster I've generated 10000 rows
• For rows from cluster1 I changed var1-var10 so they are equal to 1 with probability 0.1
• For rows from cluster2 I changed var11-var20 so they are equal to 1 with probability 0.1
• I've made the same thing for all 10 clusters.
• At the end I've added 20 noise variables which are equal to 1 with probability p

Here is R code that generates it:

m <- matrix(0, nrow = 100000, ncol = 120)
p <- 0.015
for (i in 1:10){
prob <- c(rep(0.01, 100), rep(p, 20))
prob[(i*10 - 9):(i*10)] <- 0.1
for (j in 1:10000){
row <- (runif(120) < prob) * 1
m[(i - 1) * 10000 + j, ] <- row
}
}


What I want to cluster was columns.
To cluster I'm first doing SVD and then KMEANS on the result.

res <- svd(m, nv = 10)
resKmeans <- kmeans(res$v, 11, iter.max = 100, nstart = 10)  When$p=0.015$the clusters are forming almost perfectly, but if I change$p=0.03\$ then the result is catastrophic - almost all variables from var1-var100 are in one cluster and all the other clusters are formed using noise.

First of all, your data is too extreme, and not at all realistic.

• There are 100 variables
• Each variables is equal to 1 with probability 0.01

This means that most vectors will have a single 1. Many will be 0. Some will have more than one.

Try more complex patterns, and more complex data. Try to estimate the parameters from real data, for example. Or just use real data right away.

In general you should try to use algorithms that were actually designed for sparse data. Don't use plain PCA - it scales badly with dimensionality. Use Sparse PCA. Don't use plain k-means. It really is not meant for binary sparse vectors. The mean does not make sense here. You should be using modes or medoids instead, or a kernel method.

• For each cluster there are 10 variables for which the probability is 0.1. I didn't use the real data only because I wanted to know 'true patterns', and this pattern is rather simple. I found a method that can deal with this even with higher noise. I've randomly permutated values in all columns and then I used random forest to predict whether a row is from orginal matrix or permutated. EVERY single variable from var1-var100 had positive importance and all noise variables had negative importance. After the noise is removed it is fairly easy do cluster this. May 10, 2013 at 22:04
• I didn't use plain k-means, I've used SVD and then k-means on the result of SVD (I'm not sure whether it makes sense). Nevertheless +1 for sparse PCA - I've never heard about it and it may be useful for such problem. Thanks for the answer! May 10, 2013 at 22:06