I am running a clustering algorithm in Spark and I have to choose between K-Means and Bisecting-Kmeans. However the only thing that differes between the two is the runtime because the performance is equally bad. I have a dataset of some 1.3 million entries and they have all been appropriately vectorized. When I run the algorithm for 150-200 clusters, the final output consists of at least only cluster that has over 400k entries. The rest is distributed among the rest. That big cluster with 400k entries is a big issue. Is there any way for me to optimize the clustering (I have little control over the Spark algorithm workflow)? Some way to force that big cluster to divide? Unfortunately I am also capped at how much memspace the calculation can take. Going over 250 clusters is risky because I just may get a Java Heap Space error. Any ideas, sugggestions, how to handle this situation?
-
1$\begingroup$ Is there a logical reason that 50% of the entries are in one cluster? For instance, are their feature values constant and this lack of variability or distinguishing characteristics is dumping them into one undifferentiated mass? $\endgroup$– user78229Commented Nov 2, 2016 at 20:11
-
$\begingroup$ Please add a visualization of your data and clusters (a sample is fine). $\endgroup$– Has QUIT--Anony-MousseCommented Nov 3, 2016 at 6:57
-
$\begingroup$ @Mnemosyne do you solve this problem? some advice after years? $\endgroup$– enneppiCommented May 27, 2022 at 11:41
-
$\begingroup$ sorry, i never solved it. had to use another algorithm to give me more acceptable results. $\endgroup$– MnemosyneCommented Jun 17, 2022 at 15:36
5 Answers
This is very typical behavior of k-means when applies to non-continuous data. It's not what k-means is designed for, you are essentially operating it out of its specifications. Also, k-means is very sensitive to noise. You probably have a lot of one-element clusters, too?
Also Spark is one of the worst tools for clustering. Consider getting the C code from BaylorML / Greg Hamerly. You will be surprised by how much faster it is. People always assume Spark would be the fastest, but the only thing it actually outperforms is Hadoop MapReduce. Depending on your sparsity, 1.3 Mio points should still fit into main memory of a single machine. Then tools such as BaylorML and ELKI will just shine and be a lot faster than Spark.
But that doesn't really help you with your clustering problem, because it most likely is a data problem.
I suggest you do A) visualize your data and the clustering results (PCA is more appropriate than tSNE because it preserves distances better, so you see the outliers!) B) start with a sample rather than all 1.3 million at once! Only scale up once you have a working approach. And you may need to use other clustering algorithms than k-means...
-
$\begingroup$ Can you provide a reference for "This is very typical behavior of k-means when applies to non-continuous data"? $\endgroup$ Commented Jul 4, 2017 at 9:20
-
$\begingroup$ No, I don't have a reference for this, just my experience. It would be worth trying to find a theoretical model to explain this. $\endgroup$ Commented Jul 4, 2017 at 16:08
I am using K means clustering on the "words" matrix from an SVD of a Tf Idf matrix and got similar results. I found the sum of the squares of the features for this large cluster and found they were all low magnitude words. Also similar to your situation, I got a lot of 1 word clusters. To combat this, I only chose data points with magnitudes between .025 and 1. (you could try magnitudes that fit your scale. Mine was based on an orthonormal matrix with 400 columns).
I can't say this is the best approach, but it has helped.
It's very interesting that you are getting a giant cluster with 400k entries using bisecting k-means.
Bisecting k-means iteratively breaks down the cluster with the highest dissimilarity into smaller clusters. Since you are already producing 100+ clusters, it seems to me that maybe the 400k entry cluster has a very high similarity score.
I'd try to visualize the clusters via stratified sampling and then t-SNE. It might be that the 400k entries are more homogenous than we think.
-
$\begingroup$ I came upon this realization a while back too. I am handling a dataset of analysis results and sometimes the results are very generalistic and under those circumstances, those simplistic vectors would be much more similar with each other. Ironically this proves that about half the results is basically "trash" i.e. inconclusive results. $\endgroup$ Commented Nov 3, 2016 at 1:11
When you say "optimise the clustering", I take this to mean that you wish to divide your clusters in an efficient manner.
Before running k-means or bisecting k-means, it is advisable to run a principal component analysis (PCA) on your data. The PCA generates a scree plot of the Number of Clusters and the Within Groups Sum of Squares, and the point at which the Within Groups SSE levels off indicates the ideal number of clusters.
The following link could also be of use to you:
Run this test and see if you still get such a high concentration of observations in one cluster. It could be that an estimate of 150-200 clusters is in fact significantly different from the more realistic estimate.
In several situations like this, I found it helpful to cluster the big cluster into subclusters. It doesn't make sense every time, but if your data has a lot of separate little islands, your K probably will never be enough to cover the biggest "island".
Another approach would be dropping the smallest centroids with their neighbors and putting the same amount of new random centroids into the game.
