5
$\begingroup$

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:

  1. ID | KeyWords
  2. 0 | 1 2
  3. 1 | 2
  4. 2 | 3
  5. 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.

$\endgroup$
  • 1
    $\begingroup$ How big is your vocabulary and what is the median number of tokens per document? Not looking for exact figures here, approximations are fine. Just trying to understand the scale of your data. LDA generally performs best with a sizeable vocabulary and a large corpus. $\endgroup$ – David Marx Feb 15 '18 at 12:42
  • $\begingroup$ I put the info in the original post. I'm starting to think; may it be best to remove all the observations with only 1 KeyWord (as they don't add much in terms of pattern recognition), and just cluster them by prediction after the modelling? (Might be breaking data-science rules here) $\endgroup$ – Glorfendal Feb 15 '18 at 23:24
  • 1
    $\begingroup$ Not sure if that's your case, but URLs naturally tend to form hierarchical relations (domain-subdomain, or site-area-page). Did you think using some form if hierarchical clustering? $\endgroup$ – mikalai Feb 22 '18 at 17:12
  • $\begingroup$ Thanks for the reply Mikalai. I had a look into it but from memory I decided that K-Means seemed more appropriate initially (can't remember exactly why, maybe along the lines of getting direct hard clusters). However, I only realised yesterday that I had treated all the URLs as having equal interest, completely ignoring the URL structure. A serious oversight on my behalf (it is my first time working with webdata, but nonetheless it should have been quite obvious). I will definitely reconsider Hierarchical Clustering when I review the project next week $\endgroup$ – Glorfendal Feb 24 '18 at 0:32
1
$\begingroup$

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!

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the recommendations! I'll look into the methods right away. It's quite interesting I think as it seems quite simple in theory and what may be a common application, but so far many of the similar posts on word clustering just haven't hit the mark $\endgroup$ – Glorfendal Feb 15 '18 at 23:35
  • 1
    $\begingroup$ Glad you liked it! Two points:1) as i mentioned at the beginning URLs are not words. Words happen in documents together so TFIDF tells you how many times they happen in the same document and in all documents. But here each document is one unique word (url). That's why you better see them as just categories/objects. Plus the fact that linguistic prperty of word is missing in your case. 2) google "TextGraphs Workshop 2018" to see an example showing that this is an active research/work area. Good Luck! $\endgroup$ – Kasra Manshaei Feb 16 '18 at 8:38
1
$\begingroup$

TF IDF as well as LDA are meant to work with much longer documents. All documents should have more than 100 tokens.

With a median of 1, no clustering will be able to do much. Either they visited the same url, or they didn't. That is too little information for a statistical approach.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Firstly thanks for your response! I removed all observations with only 1 token from the initial dataset, leaving about 450,000 observations with a median of 4 (still quite low). Why does it matter how many tokens are in each document? Is it to do with the vectorisation and calculating similarity? $\endgroup$ – Glorfendal Feb 19 '18 at 5:32
  • $\begingroup$ I already gave the answer to that, too. Too little data to get robust statistical results, and to differentiate. I do not think dropping data is the appropriate answer. Instead, you need to rethink the objective. I.e. how do you evaluate the quality of a cluster on your data and problem? What function are you trying to solve? $\endgroup$ – Has QUIT--Anony-Mousse Feb 19 '18 at 6:48
  • $\begingroup$ Yeah I think I'm finding it harder as I've really only done supervised learning before. Supervised learning is so much easier in comparison as there's a direct method of evaluation, but unsupervised learning I'm finding a lot harder (especially when I can't visualise the results as easy). Gotta wrap this project up pretty soon, but I think I'll spend quite some time exploring the methods more deeply. Thanks again for the insights $\endgroup$ – Glorfendal Feb 19 '18 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.