7
$\begingroup$

We're build an item-item recommender based on the text descriptions of the items. Our initial approach was to calculate the TF-IDF vectors for each item. We used a hashing tf with 5000 possible hashes for the words. Then approximate all-pairs using a sampling technique (DIMSUM).

We have an mxn matrix where m is the number of words, n is the number of items. The naive approach of calculating all column cosine similarities won't work here since we have n=10^7 m=10^4.

Our first attempt was using DIMSUM http://stanford.edu/~rezab/papers/dimsum.pdf which is an all-pairs sampling technique. The problem with DIMSUM is it works for data where m >> n. Our matrix is short and wide n>m.

My Question: What is a good approach for estimating all-pairs similarity of items based on words. Where number of items is 10^7, number of words is 10^4. We only want items pairs above a certain threshold of similarity.

We don't have to do it this way, our task is to recommend a small set of items given one item, we have ways of doing this using collaborative filtering, but we want to also handle new items that we have no user data for so we're trying to find a way to use tf-idf vectors for that case.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Are you planning on using distributed computation? If so, have you considered Apache Spark...it's much faster in many cases than map reduce. $\endgroup$
    – user9424
    Commented Jul 31, 2015 at 2:07
  • $\begingroup$ I'm using spark. columnSimilarity is implemented in scala for spark, I'm using python so I implemented it myself in the python bindings. Either way, doing all pairs similarity brute force is infeasible even on huge spark clusters. DIMSUM offers a smart trick for sampling only column similarities that have a high probability of being over a certain threshold, the issue is that DIMSUM works only when you have more rows than columns. I have many more columns than rows. see the linked paper for details $\endgroup$
    – Brandon Hamric
    Commented Jul 31, 2015 at 20:44
  • $\begingroup$ Have you considered dimension reduction ? PCA is a good candidate for this kind of problem, specially involving the TFIDF vector model. Once you perform the dimension reduction, you can then apply a simple KMeans to cluster your items. $\endgroup$
    – eliasah
    Commented Oct 17, 2015 at 9:42

1 Answer 1

Reset to default
2
$\begingroup$

There are methods that approximate Jaccard similarity using hash functions, one of them MinHash. They scale well with the number of dimensions and evaluate similarity of two items. If you want to do nearest neighbor queries (finding similar items given one item) you should look at locality sensitive hashing (LSH), which essentially maps similar items to the same hash value. There is a nice implementation in scikit-learn called LSHForest. It approximates cosine distance and scales well to large number of items and dimensions.

Improve this answer
$\endgroup$

Your Answer

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

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