2
$\begingroup$

I'm attempting to use minhash to generate clusters and similarities, and I am primarily using ideas from these resources.

The data that I am working with consists of interactions between users and items. There are 2.2M distinct users and 440M distinct items. Across all of the data, there are only 905M records, so it is very sparse.

In my approach, I am calculating H minimum hash values for each user by reordering the items (of which there are 440M). Users have a wide range of item interactions. The user with the most interactions as 2.5M interactions, the lowest is 1 interaction, the average is 403, and the median is only 26.

In google's doc about Google News, they recommend concatenating 2-4 keys (LSH) and doing this 10-20 times. I imagine this works well when a user has interacted with a smaller amount of items like news articles, but it is woefully low for what I am doing. When I test this number of keys for users that have 1,000+ interactions, many do not have any concatenated min has matches with another user. This is a problem because I can manually calculate cosine or jaccard similarity for some of these users and see an acceptable amount of similarity for my needs. I have found better results by not concatenating hash keys and using as many as 200.

For most of my hash key groups, there are around 2M distinct hash keys for the 2.24M users. As such, there is a fairly low amount of collision.

Do you guys have any tips for increasing the amount of clustering? I am considering using 1,000 hash keys and pairing users if they match on more than one. Thanks in advance.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

MinHash is probably overkill here.

You have about 2 entries per item. The minhash approach is meant for recognizing near-duplicate web pages, and most words occur on millions of web pages - a very different scenario.

On your data, I would simply use inverted lists.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Do you have any links I can read about inverted lists? My main reason for going with minhash was because google is using it to cluster users who read news, and there are several similarities between what they are doing and what I am trying to do. $\endgroup$
    – neelshiv
    Feb 26, 2016 at 15:21
  • $\begingroup$ It's nothing but storing the 1s in every column only. The basic technique that is driving Lucene. $\endgroup$
    – Has QUIT--Anony-Mousse
    Feb 26, 2016 at 16:28
  • $\begingroup$ But I would still need to perform a similarity comparison across all of the items, right? $\endgroup$
    – neelshiv
    Feb 26, 2016 at 18:01
  • $\begingroup$ You would iterate over all the items, yes. Get a list of all matches each, and join them. For further speed up, process the items with most weight first. $\endgroup$
    – Has QUIT--Anony-Mousse
    Feb 26, 2016 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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