Item based similarity with GraphChi

Item based collaborative filtering is one of the most popular collaborative filtering methods used in more than 70% of the companies I am talking to.  Following my mega collaborator Justin Yan's advice, I have started to implement some item based similarity methods in GraphChi.

Item based methods compare all pairs of items together, for computing similarity metric between each pair of items. This task becomes very quickly computation intensive. For example, Netflix data has around 17K movies. If we want to compute all pairs of movies to find the most similar ones, we need to compare around 290M pairs!

If we use a symmetric similarity measure, the distance between movie A and B, is similar to the distance between movie B and A. Thus for the Netflix example we have around 145M pairs to compute. To reduce the work furthermore, we only compare movies which where watched together by at least X users, for example X=5. Otherwise, those movies are not considered similar.

When the dataset is big, it is not possible to load it fully into memory at a single machine. That is where GraphChi comes in. My preliminary implementation of the item similarity computes similarity between all pairs without fully reading the dataset into memory. The idea is to load a chunk of the items (called pivots) into memory, and then stream over the rest of the items by comparing the pivots to the rest of the items.

The simplest distance metric I have implemented is Jaccard distance. The distance of items i and j is computed as follows:
         wi = number of users who watched movie i
         wj = number of users who watched movie j
         wij = number of users who watched both movie i and movie j
         Dij =  wij / ( wi + wj - wij )

It is clear that Dij is a number between zero and one.
Additional distance functions are found here.

As always, I am looking for brave beta testers who want to try it out!
For full Netflix data, it takes around 1200 seconds to compute distances of around 130M item pairs. (Around 1000 item pairs in a second, using a 24 core machine, with only 800MB memory used).

Ping me if you are interested in other distance metric so I could add them as well.

How to try it out:

1) Follow GraphChi installation instructions steps 1-4.
2) Download smallnetflix_mm
3) Run itemcf on smallnetflix data using:

bickson@thrust:~/graphchi$ > ./toolkits/collaborative_filtering/itemcf --training=smallnetflix_mm --nshards=1 --clean_cache=1 --K=10 --quiet=1
WARNING:  common.hpp(print_copyright:183): GraphChi Collaborative filtering library is written by Danny Bickson (c). Send any  comments or bug reports to danny.bickson@gmail.com
[training] => [smallnetflix_mm]
[nshards] => [1]
[clean_cache] => [1]
[K] => [10]
[quiet] => [1]

 === REPORT FOR sharder() ===
[Timings]
edata_flush: 0.005163s (count: 13, min: 0.000335s, max: 0.000534, avg: 0.000397154s)
execute_sharding: 0.273818 s
finish_shard.sort: 0.065508 s
preprocessing: 1.05835 s
shard_final: 0.15078 s
[Other]
app: sharder
Total item pairs compared: 6325948 total written to file: 35551 pairs with zero distance: 124609
/Users/bickson/code/graphchi-cpp
Sorting output file smallnetflix_mm.out0
Sorting output file smallnetflix_mm.out1
Sorting output file smallnetflix_mm.out2
Sorting output file smallnetflix_mm.out3
Sorting output file smallnetflix_mm.out4
Sorting output file smallnetflix_mm.out5
Sorting output file smallnetflix_mm.out6
Sorting output file smallnetflix_mm.out7
Merging sorted files:
File written: smallnetflix_mm-topk
Total lines: 35551

Now let's examine the output file

bickson@thrust:~/graphchi$ 3561 3076 0.23296110332
3561 1990 0.270156830549
3561 1794 0.218252897263
3561 1788 0.227363973856
3561 1598 0.211793571711
3561 1536 0.233875498176
3561 1507 0.224534928799
3561 557 0.237991556525
3561 411 0.22253626585
3561 338 0.237756416202

For each item we get exactly K=10 similar items. (The item are sorted in reverse order).
The format is rather simple. In each row we have:
<item A> <item B> <similarity>

Command line arguments
--training - input file name in sparse matrix market format
--min_allowed_intersection=XX - filter out item pairs with less than XX users who rated them  jointly.
--quiet=1 run with less verbose traces
--nshards=1 ## mandatory argument
FOR itemcf:  --distance=XX, 0 = Jaccard index, 1=AA, 2=RA, 3=Aiolli
FOR itemcf2: --distance=XX, 3 = PEARSON, 4=COSINE, 5=CHEBYCHEV, 6=MANHATTEN, 7=TANIMOTO, 8=LOG_LIKELIHOOD, 9 = SLOPE_ONE


Useful GraphChi command line arguments:
execthreads XX - set the number of execution threads
membudget_mb XX - fix the size of used memory to XX mb

Additional metrics:

Adamic/Adar (AA) (itemcf):

Just got an email from Timmy Wilson, our man in Ohio: 
"There are a lot of similarity functions out there -- Adamic / Adar is another good one "

I looked it up an indeed it is a very simple cost function: 

Distance_item_i_j = sum over users which rated both items i j (1 / log (user_rating) )

see equation (2) in the paper: http://arxiv.org/abs/0907.1728 "Role of Weak Ties in Link Prediction of Complex Networks". The equation gives larger weight to users which rated both items but have relatively small number of rated items.

I have also added the RA cost function, which is same like AA but without the log.

Pearson Correlation (itemcf)

I got a request from additional reader "silly snail" to implement Pearson Correlation as well. Let m be a vector of size M (users) which hold the user rating mean.

Let a be a sparse vector holding user rating for item a, and the same for item b.

Pearson_correlation_i_j = ((a - mean)' * (b-mean)) / (stddev(a) * stddev(b))

And stddev(a) = sum((a-mean).^2) / (n - 1) 
where n = length(a).

To run pearson correlation, use the program ./toolkits/collaborative_filtering/preason

A toy example:

Prepare the file "stam" with the content:
%%MatrixMarket matrix coordinate real general
3 4 9
1 1 3
1 2 4
2 3 1
2 4 1
2 1 2
3 1 1
3 2 2
3 3 3
3 4 4

Namely there are 3 users, 4 items, and 9 ratings. 
Now run pearson correlation:
./toolkits/collaborative_filtering/pearson --training=stam execthreads 1 

Lets examine the output file:
head stam.out0
2 1 0.337405
...


Namely, the pearson correlation between items 1 and 2 is 0.337405.
Now let's do the same computation in matlab:
matlab

>> a=full(mmread('stam')); % load the matrix into memory

a =

     3     4     0     0

     2     0     1     1

     1     2     3     4

>> means=mean(a') % compute the item vectors mean

means =

    1.7500    1.0000    2.5000

>> A=a(:,1)-means'  % compute item 1 vector minus mean

A =

    1.2500

    1.0000

   -1.5000

>> B=a(:,2)-means'  % compute item 2 vector minus mean

B =

    2.2500

   -1.0000

   -0.5000

>> dist = A'*B  % multiply the result

ans =

    2.5625

>> stddeva=sum(A.^2)/2 % compute stddev item 1

stddeva =

    2.4062

>> stddevb=sum(B.^2/2)% compute stddev item 2

stddevb =

    3.1562

>> dist/(stddeva*stddevb) % compute pearson correlation

ans =

    0.3374

Luckily we got the same result! namely pearson correlation between the two first items is 0.3374.

Cosine Distance (itemcf)

See: http://reference.wolfram.com/mathematica/ref/CosineDistance.html

Manhattan Distance (itemcf2)

See http://en.wikipedia.org/wiki/Taxicab_geometry

Log Similarity Distance (itemcf2)

See http://tdunning.blogspot.co.il/2008/03/surprise-and-coincidence.html

Chebychev Distance (itemcf2)

http://en.wikipedia.org/wiki/Chebyshev_distance

Tanimoto Distance (itemcf2)

See http://en.wikipedia.org/wiki/Jaccard_index

Aiolli's method (itemcf)

See the paper: F. Aiolli, A Preliminary Study on a Recommender System for the Million Songs Dataset Challenge Preference Learning: Problems and Applications in AI (PL-12), ECAI-12 Workshop, Montpellier. pdf

Slope One Recommender (itemcf2)

Is described in A Programmer's Guide to Data Mining , page 18.

How to compute recommendations out of similarities?

For computing top K recommendations for each user, you can use the itemsim2ratings utility

as explained here. The input file for itemsim2rating is the similarity matrix computed by itemcf.

Additional reading:

Matrix factorization based collaborative filtering with GraphChi.
Case study: million songs dataset

Acknowledgements

• Tao Ye, Pandora Internet Radio, for beta testing itemcf.
• Timmy Wilson, Smarttypes.org, for proposing additional metrics
• Denis Parra, Univ. of Pittsburgh, for proposing additional metrics
• Clive Cox, Rummble Labs, for implementing and contributing asym. cosine metric.
• Mohammad Burhan, Fraunhofer IAIS, for suggesting Slope One recommender implementation.