Noise in clustering of high dimensional sparse data

Question

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.

Answer 1

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.