# How to limit my input data for Jaccard item-item similarity calculation?

I'm trying to compute item-item similarity using Jaccard (specifically Tanimoto) on a large list of data in the format

(userid, itemid)


An item is considered as rated if i have a userid-itemid pair. I have about 800k users and 7900 items, and 3.57 million 'ratings'. I've restricted my data to users who have rated at least n items(usually 10). However, I'm wondering if I should place an upper limit on number of items rated. When users rate 1000 or more items, each user generates 999000 pairwise-combinations of items to use in my calc, assuming the calculation

n! / (n-r)!


Adding this much input data slows the calculating process down tremendously, even when the workload is distributed(using hadoop). I'm thinking that the users who rate many, many items are not my core users and might be diluting my similarity calculations.

My gut tells me to limt the data to customers who have rated between 10 and 150-200 items but I'm not sure if there is a better way to statistically determine these boundaries.

Here are some more details about my source data's distribution. Please feel free to enlighten me on any statistical terms that I might have butchered!

The distribution of my users' itemCounts:

> summary(raw)
itemsRated
Min.   :   1.000
1st Qu.:   1.000
Median :   1.000
Mean   :   4.466
3rd Qu.:   3.000
Max.   :2069.000

> sd(raw)
itemsRated
16.46169


If I limit my data to users who have rated at least 10 items:

> above10<-raw[raw\$itemsRated>=10,]
> summary(above10)
Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
10.00   13.00   19.00   34.04   35.00 2069.00
> sd(above10)
[1] 48.64679
> length(above10)
[1] 64764


If I further limit my data to users who have rated between 10 and 150 items:

> above10less150<-above10[above10<=150]
> summary(above10less150)
Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
10.00   13.00   19.00   28.17   33.00  150.00
> sd(above10less150)
[1] 24.32098
> length(above10less150)
[1] 63080


Edit: I dont think this is an issue of outliers as much as the data is positively skewed.

-
try to use a graph database. the bit vector solution seems to bee reasonable but not for a large amount of data in a relational database, a simple query execution time could jump up to seconds... –  user12011 Jun 15 '12 at 11:09

I'm confused: shouldn't you only need the 7900^2 item similarities, for which you use ratings from all users, which is still quite sparse?

UPDATE

I still think there's a more efficient way to do this, but maybe I'm just being dense. Specifically, consider item A and item B. For item A, generate a U-dimensional vector of 0's and 1's, where U is the number of users in your data set, and there's a 1 in dimension i if and only if user i rated item A. Do the same thing for item B. Then you can easily generate the AB, A and B terms for your equation from these vectors. Importantly, these vectors are very sparse, so they can produce a very small data set if encoded properly.

1. Iterate over the item ID's to generate their cross product: (ItemAID, ItemBID)
2. Map this pair to this n-tuple: (ItemAID, ItemBID, ItemAVector, ItemBVector)
3. Reduce this n-tuple to your similarity measure: (ItemAID,ItemBID,SimilarityMetric)

If you set up a cache of the ItemXVector's at the start, this computation should be very fast.

-
To compute similarity, I need to count the number of times two items were rated together by the same person. That count becomes my numerator. The formula I'm using to calculate similarity between items A & B is AB / A + B - AB Where AB is the number of times items A and B were rated by the same person, and A and B are the number of times each item was rated overall. In order to perform that count, I need to generate all of the itemA,itemB pairs in my mapper, and then sum the counts in my reducer. The items are rated in a binary fashion-if a (userid,itemid) exists, then 1. –  Neil Kodner Aug 4 '10 at 17:43
what do you mean with "set up a cache"? which platform do you use? –  ulkas Jan 8 '13 at 14:42

I've solved similar problem with MinHash which is specifically designed to approximate Jaccard distance. Idea is simple using MinHash probabilistic features you group your data into smaller groups (with same hash(s)) and then evalaute pairwise distance inside group (kind of block structure of matrix). The final answer is not exact but you can control how close it to exact by changing depth and amount of hashes.

-
in case i have a case where my users rated less than 10 items, is it ok to use minhash for this? since picking up a subgroup from a group will almost always result into an empty set (in this case, when a user has less than 10 ratings out of 7900 items, the minHash could be contra-productive imho). –  ulkas Jan 8 '13 at 14:40