K-Means Cluster has over 50% of the points in one cluster. How to optimize it? 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?
 A: 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...
A: 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.
A: 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:
https://spark.apache.org/docs/1.2.1/mllib-dimensionality-reduction.html#principal-component-analysis-pca
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.
A: 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.
A: 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.
