# Clustering by same random projection

I have $N$, $1024$-dimensional vectors. I want to cluster them by some similarity. Given the high dimensionality, standard metrics won't work. I tried a few Approximate Nearest Neighbor implementations which use randomized kd-trees or priority search k-means to find nearest neighbors. I don't trust their results either, because they depend a lot on parameter configuration.

Now, I know the number of clusters in this dataset because I know the number of classes , which is 55. As I was thinking, I had this idea, that I could just take a random weight matrix $W$ of size $1024$ x $55$, that will take as input my vectors and output a $55$ dimensional vector, and I'll apply $argmax$ on this $55$ dimensional vector and just use that value as the cluster $id$ . The $W$ , once randomly selected, remains the same for every input vector. Because I only care about clustering similar vectors and not about their exact class, I think this should work well. I guess this is very similar to cosine similarity, but instead of distance, I get a cluster id, because I use this random $W$ as a "judge" of similarity...Similarity w.r.t $W$, in other words.

Now, I'm an engineer and while this looks at first glance to be okay, I know things can't be that easy..I mean people have been researching high-dimensionality clustering and search for a very long time, and it is a hard problem. So I know I either made some stupid logical flaw above, or that there is some good theoretical reason not to do it this way. I want to know what I'm thinking wrong here, and why.

Thanks.

• Sounds like a great idea! High-D clustering is still a wide open field. There are way more ideas than researchers. Give your idea a shot and let us know the results. Try 2 or 3 instead of 55 first. Consider the possibilities of inverting the op.
– Ray
Commented Sep 21, 2018 at 14:39

While I can't guarantee this is well-suited to your data, the following approach is pretty standard for when you want to cluster high-dimensional data.

You basically want to dimensionally reduce your data and then apply a clustering algorithm which would perform poorly in high dimensions but works well in low-dimensions.

PCA, TSNE, UMAP and AutoEncoders are all dimensionality reduction algorithms which you might consider using. All of these algorithms have hyperparameters whose performance greatly affects the output. There is, in all cases, a hyper parameter related to the dimension you want to project into, so one thing you could try is to project into 2- or 3-d and plot what your data looks like. For PCA, you can see what fraction of the variance is retained as a function of dimension and for AutoEncoders, you could plot your divergence as a function of dimension (although this will be computationally costly).

Once your data is dimensionally reduced, you can try the usual suspects (e.g. KMeans), although most likely you'll want to use DBscan or HDBScan.

I'm intrigued as to how you know you have 55 clusters. If, as you say, there are 55 classes, does this mean your data is labelled? If so, why do you want to cluster? Regardless of this, if you know you have 55 clusters, this is something you can harness very nicely in this approach.

I'm not an expert on (H)Dbscan, but I don't believe you set the cluster number, you set a density parameter and it will find the clusters and tell you the cluster number. Consequently, if for some reasonable combination of dimensionality reduction hyperparameters and (H)Dbscan hyperparameters, you are getting 55 clusters (or close to), you're probably on the right track.

Documentation for your dimensionality reduction implementation and your clustering algorithm should give you an idea for what constitutes reasonable ranges of parameter values.