PS I got a copy of "Collective Intelligence" and it is indeed a great overview.
I think my experience agrees with everything he says in Chapter 3 on Collaborative Filtering. He mentions a few different similarity metrics -- Euclidean distance and Tanimoto coefficient -- that were interesting enough that I implemented them today. So I think I've covered chapter 3! Coming back to your message Ankur, yes I think the code already supports what you suggest, in part. His "item similarity table" is the "ItemCorrelation" you feed into GenericItemBasedRecommender. He rightly suggests this should be precomputed, which is where GenericItemCorrelation comes in -- it can just compute item-item correlations based on any algorithm you want like PearsonCorrelation and save them off. You could modify this to save only "strong" correlations as you say. I can surely dig in here with you and write code to do this if it's not clear. Yes it is parallelizable in the way you suggest. After you get past maybe 10,000 items it is going to get quite painful to calculate this on one machine, indeed. Another approach is to use some external a priori knowledge to define item similarity rather than using user preferences. For example maybe I just say that two movies in the same genre are pretty similar, and ones that aren't, aren't. That takes no precomputation of any kind. And finally back to your question about binary yes/no user preferences -- the TanimotoCoefficientCorrelation I just added should be pretty suitable for situations where you only care about whether a preference exists or not. I need to continue along this line and build optimized versions of User that can more efficiently store this sort of thing rather than a bunch of dummy Item and Preference objects that are superfluous in this context. This could also greatly speed up item-item similarity computations. On Wed, May 21, 2008 at 7:36 AM, Goel, Ankur <[EMAIL PROTECTED]> wrote: > Hey Sean, > Thanks for the suggestions. In my case the data-set os only > going to tell me if the useer clicked on a particualar item. So lets say > there are 10,000 items a user might only have clicked 20 - 30 items. I > was thinking more on the lines of building an item similarity table by > comparing each item with every other item and retaining only 100 top > items decayed by time. > > So a recommender for a user would use his recent browsing history to > figure out top 10 or 20 most similar items. > > The approach is documented in Toby Segaran's "Collective Intelligence" > book and looks simple to implement even though it is costly since every > item needs to be compared with every other item. This can be > parallelized in way that for M items in a cluster of N machines, each > node has to compare M/N items to M items. Since the data-set is going to > sparse (no. of items having common users), I believe this would'nt be > overwhelming for the cluster. > > The other approach that I am thinking to reduce the computation cost is > to use a clustering algorithm like K-Means that's available in Mahout to > cluster similar user/items together and then use clustering information > to make recommendations. > > Any suggestions? > > Thanks > -Ankur > > > -----Original Message----- > From: Sean Owen [mailto:[EMAIL PROTECTED] > Sent: Tuesday, May 20, 2008 9:37 PM > To: [email protected]; Goel, Ankur > Subject: Re: Taste on Mahout > > + Ankur directly, since I am not sure you are on the dev list. > > On Tue, May 20, 2008 at 12:06 PM, Sean Owen <[EMAIL PROTECTED]> wrote: >> All of the algorithms assume a world where you have a continuous range > >> of ratings from users for items. Obviously a binary yes/no rating can >> be mapped into that trivially -- 1 and -1 for example. This causes >> some issues, most notably for corrletion-based recommenders where the >> correlation can be undefined between two items/users in special cases >> that arise from this kind of input -- for example if we overlap in >> rating 3 items and I voted "yes" for all 3, then no correlation can be > >> defined. >> >> Slope one doesn't run into this particular mathematical wrinkle. >> >> Also, methods like estimatePreference() are not going to give you >> estimates that are always 1 or -1. Again, you could map this back onto >> 1 / -1 by rounding or something, just something to note. >> >> So, in general it will be better if you can map whatever input you >> have onto a larger range of input. You will feed more information in, >> in this way, as well. For example, maybe you call a recent "yes" >> rating a +2, and a recent "no" a -2, and others +1 and -1. >> >> >> The part of slope one that parallelizes very well is the computing of >> the item-item diffs. No I have not written this yet. >> >> >> I have committed a first cut at a framework for computing >> recommendations in parallel for any recommender. Dig in to >> org.apache.mahout.cf.taste.impl.hadoop. In general, none of the >> existing recommenders can be parallelized, because they generally need > >> access to all the data to produce any recommendation. >> >> But, we can take partial advantage of Hadoop by simply parallelizing >> the computation of recommendations for many users across multiple >> identical recommender instances. Better than nothing. In this >> situation, one of the map or reduce phase is trivial. >> >> That is what I have committed so far and it works, locally. I am in >> the middle of figuring out how to write it for real use on a remote >> Hadoop cluster, and how I would go about testing that! >> >> Do we have any test bed available? >> >> >> >> On Tue, May 20, 2008 at 7:47 AM, Goel, Ankur <[EMAIL PROTECTED]> > wrote: >>> I just realized after going through the wikipedia that slope one is >>> applicable when you have ratings for the items. >>> In my case, I would be simply working with binary data (Item was >>> clicked or not-clicked by user) using Tanimoto coefficient to >>> calculate item similarity. >>> The idea is to capture the simple intuition "What items have been >>> visited most along with this item". >>> >>> >>> -----Original Message----- >>> From: Goel, Ankur [mailto:[EMAIL PROTECTED] >>> Sent: Tuesday, May 20, 2008 2:51 PM >>> To: [email protected] >>> Subject: RE: Taste on Mahout >>> >>> >>> Hey Sean, >>> I actually plan to use slope-one to start with since >>> - Its simple and known to work well. >>> - Can be parallelized nicely into the Map-Reduce style. >>> I also plan to use Tanimoto coefficient for item-item diffs. >>> >>> Do we have something on slope-one already in Taste as a part of > Mahout ? >>> >>> At the moment I am going through the available documentation on Taste > >>> and code that's present in Mahout. >>> >>> Your suggestions would be greatly appreciated. >>> >>> Thanks >>> -Ankur >>> >>> -----Original Message----- >>> From: Sean Owen [mailto:[EMAIL PROTECTED] >>> Sent: Tuesday, April 29, 2008 11:09 PM >>> To: [email protected]; Goel, Ankur >>> Subject: Re: Taste on Mahout >>> >>> I have some Hadoop code mostly ready to go for Taste. >>> >>> The first thing to do is let you generate recommendations for all >>> your users via Hadoop. Unfortunately none of the recommenders truly >>> parallelize in the way that MapReduce needs it to -- you need all >>> data to compute any recommendation really -- but you can at least get > >>> paralellization out of this. You can use the framework to run n >>> recommenders, each computing 1/nth of all recommendations. >>> >>> The next application is specific to slope-one. Computing the >>> item-item diffs is exactly the kind of thing that MapReduce is good >>> for, so, writing a Hadoop job to do this seems like a no-brainer. >>> >>> On Tue, Apr 29, 2008 at 11:14 AM, Goel, Ankur >>> <[EMAIL PROTECTED]> >>> wrote: >>>> Hi Folks, >>>> What's the status of hadoopifying Taste on Mahout ? >>>> What's been done and what is in progress/pending ? >>>> >>>> I am looking using a scalable version of Taste for my project. >>>> So basically trying to figure out what's already done and where I >>>> can pitch in. >>>> >>>> Thanks >>>> -Ankur >>>> >>> >> >
