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:
- There are 100 millions of tags most of them used only once.
- Some tags are used very often, say one tag may be used on 1% of whole dataset.
- 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.