3
$\begingroup$

I have five millions of objects each of them having one or more tags. How do I compute statistically sound similarity score between each pair of the objects taking into account that:

  1. There are 100 millions of tags most of them used only once.
  2. Some tags are used very often, say one tag may be used on 1% of whole dataset.
  3. Some objects are heavily tagged with hundreds of thousands tags on them while others may be tagged only a couple of times.

Second question: how do I cluster objects taking into account 1-3? My guess is that k-means and other popular clustering techniques won't do much here. I've tried k-means already with simple distance defined as number of similar tags on the objects and clusters are so vague to the point being almost meaningless.

Improve this question
$\endgroup$
1
$\begingroup$

k-means clearly does not make sense, because the mean does not make sense on this kind of data.

However, don't skip the preprocessing. Preprocessing is 90% of your work. E.g. you can probably just drop any unique tag. You can use stemming to merge variations of the same word etc. But in general classic text mining techniques such as TF-IDF should be worth a try.

Now that you can't use k-means doesn't mean that all other clustering algorithms suffer from the same issue. First of all, you can try e.g. DBSCAN and OPTICS.

But maybe you aren't actually looking for clustering algorithms. Have you considered looking at groups defined implicitely e.g. by frequent itemsets? Have you looked at classic document clustering techniques? And how about using the various clustering algorithms for categorical data? There is no reason to use a vector space oriented method such as k-means on a data which naturally is not vectorized. Search on Scholar for "clustering categorical data".

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks you! I did some very preliminary testing and frequent itemsets shows some promise. One more question though: for using graph clustering algorithms I will need to build a graph from my data i.e. decide which objects should be connected. I seems like n^2 operation if I will compare all pairs of objects which is too much work. Is there linear or n*log(n) approach to graph building? $\endgroup$ – Moonwalker Jun 4 '13 at 14:41
  • $\begingroup$ Good DBSCAN and OPTICS implementations should use index structures to run in O(n log n). In ELKI, I recommend using STR bulk loaded R*-trees, these work best for me. $\endgroup$ – Has QUIT--Anony-Mousse Jun 4 '13 at 14:54
  • $\begingroup$ Oh, silly me! I though DBSCAN and OPTICS would work only on graphs (which I hand to build beforehand, hence n^2 cost). $\endgroup$ – Moonwalker Jun 4 '13 at 15:00
1
$\begingroup$

You can use set-based similarities, sometimes known as fingerprint similarities, and subsequently use graph-based algorithms. DBSCAN is one option, but other commonly used algorithms are Louvain clustering, RNSC (Restricted Neighbourhood Search Clustering), APC (Affinity Propagation Clustering) and MCL (Markov CLuster) algorithm. As Anony-Mousse says, pre-processing will be important. Try to drop very infrequent tags and perhaps also tags that occur with very high frequency.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer! I think I still do not understand one thing: how do I assign weights for graph edges which I will need for graph clustering algorithms? I simply cannot run n^2 operations to compare each pair of vertexes. $\endgroup$ – Moonwalker Jun 4 '13 at 14:38
  • $\begingroup$ It is a lot of data, that's true. Part of the mcl software (disclaimer - I wrote it) is a program called 'mcxarray'. It can parallelise using both threads (CPUs) and jobs (machines) and integrate partial solutions later. I find that brute force is still the easiest solution, if one has access to good compute resources. Three more comments: - objects with many tags could well be problematic. - I would test on smaller (carefully chosen) subsets before going large-scale. - Wayfair has done something similar I think: engineering.wayfair.com/recommendations-with-markov-clustering . $\endgroup$ – micans Jun 6 '13 at 10:35

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.