Clustering Observations by String Sequences (Python/Pandas df) I have a dataset consisting of approximately 2 million unique observations. It was initially a set of ID's and URLs. The goal is to cluster the ID's based on the URLs looked at. I transformed both columns to index form to simplify the data. As such, the set has 2 columns; 1. A unique ID and 2. A bag of key strings (they are identifying numbers but in string format, separated by spaces). Example format:


ID |  KeyWords
0 |   1 2 
1 |   2
2 |   3
3 |   2 3


I initially vectorised KeyWords by TD-IDF and used a simple and dirty KMeans (via sklearn) to cluster them into 13 clusters (selected by the elbow method), which seemed to work and output intuitive and interesting results.

However, the issue I have come across is that there is always one dominant cluster that holds ~80% of the observations. I assume that KMeans was the limiting factor with assumed constant variance, and looked into Latent Dirichlet Allocation (LDA), as well as Gaussian Mixture Modelling (GMM) and BayesianGMM as alternatives. Using the same data format as above, LDA seemed to produce unintuitive results, for which all the topics were very similar and did not make much sense (vastly different to KMeans clusters, expected to see some key similar topics?). 

I'm quite new and out of my depth with clustering and have been reading quite a lot about it, but if anyone could provide any insights into immediate logic flaws or a push in the right direction I would very much appreciate it.

Edit: 
There's about 3300 unique URLs (or KeyWords in this case). The number of tokens/URLs per document is quite skewed actually. The median is 1, mean is ~1.5 (there is a small number of ID's that have a very large number of tokens, some I can deem as outliers but most I cannot). Another key fact is that in the dominant cluster, almost all of these "big players" who have looked at a large number of KeyWords are all within the dominant cluster. I removed them to see how it played out, and the dominant cluster remains.
As URLs are usually unique strings, I am not sure if NLP methods are proper things here. That is interesting that TFIDF+Kmeans gave you an intuitive results however as the problem is unsupervised, it´s pretty difficult to say what is intuitive that way. 

In my opinion your problem is a typical Community Detection in Bipartite Graphs e.g. this paper. This approach is certainly worth to try. Of course the result can be combined with other algorithms e.g. in a voting schema.

The last but not the least is to take a clustering method which does not limit to resolution e.g. in Community Detection, any Modularity-based method is only able to capture clusters larger than a resolution limit. One approach to this is a hierarchical approach to partitioning the data in which you again apply clustering on the significantly large cluster you find.

Hope it helps!