The comparison matrix is actually sparse because you can eliminate all cases with zero cooccurrence. That means that (except for super users), the comparison process scales roughly with the log file size. For super active users, Sean's suggestion for sampling is a good one.
On Wed, Jun 4, 2008 at 4:41 AM, Goel, Ankur <[EMAIL PROTECTED]> wrote: > After making some sense of what Ted is suggesting and looking at the > sample code from Sean, I finally understood what we are trying to with > this. > The concern here is that this technique could hit scalability issues > with a large number of users and items even if the computation is > distributed over reasonably large cluster (50 nodes) since every item > need to be compared against every other item. Say for e.g. in my case > there are would be 50 - 100 million items (may be more) and an > equivalent number of users. > > Thoughts ? > > > -----Original Message----- > From: Sean Owen [mailto:[EMAIL PROTECTED] > Sent: Monday, June 02, 2008 4:50 AM > To: [email protected] > Subject: Re: Taste on Mahout > > OK Ted I implemented this and it works, in the sense that I get the same > numbers as in your paper. But I have run into some interesting corner > cases. Here's my code, which will help illustrate: > > public final double itemCorrelation(Item item1, Item item2) throws > TasteException { > if (item1 == null || item2 == null) { > throw new IllegalArgumentException("item1 or item2 is null"); > } > int preferring1and2 = > dataModel.getNumUsersWithPreferenceFor(item1.getID(), item2.getID()); > if (preferring1and2 == 0) { > // I suppose we can say the similarity is 0 if nobody prefers both > at the same time? > return 0.0; > } > int preferring1 = > dataModel.getNumUsersWithPreferenceFor(item1.getID()); > if (preferring1 == preferring1and2) { > // everyone who prefers 1 also prefers 2 -- perfect similarity > then? > return 1.0; > } > int preferring2 = > dataModel.getNumUsersWithPreferenceFor(item2.getID()); > int numUsers = dataModel.getNumUsers(); > double logLikelihood = > twoLogLambda(preferring1and2, preferring1 - preferring1and2, > preferring2, numUsers - preferring2); > return 1.0 - 1.0 / (1.0 + logLikelihood); > } > > private static double twoLogLambda(double k1, double k2, double n1, > double n2) { > double p1 = k1 / n1; > double p2 = k2 / n2; > double p = (k1 + k2) / (n1 + n2); > return 2.0 * (logL(p1, k1, n1) + logL(p2, k2, n2) - logL(p, k1, > n1) - logL(p, k2, n2)); > } > > private static double logL(double p, double k, double n) { > return k * Math.log(p) + (n - k) * Math.log(1.0 - p); > } > > > So we're going to get "NaN" whenever a "p" value is 0.0 or 1.0 in > logL(). This comes up in some cases with clear interpretations: > > "preferring1and2 == 0" > If nobody likes both items at the same time, I'd say their similarity is > very low, or 0.0. > > "prefererring1and2 == preferring1" or > "preferring1and2 == preferring2" > This means everyone who prefers one items also prefers the other. In > this case I'd say the two item similarities is quite high, or 1.0. > > "preferring2 == 0" > I guess we can't say anything about the similarity of items 1 and 2 if > we know of nobody expressing a pref for #2. Or we could say it is 0? > that or NaN. I am not clear on which is the more natural interpretation. > > "numUsers == preferring2" > Everyone likes item 2. Again not clear what to do here except say we > can't figure out a similarity? NaN? > > "preferring1 - preferring1and2 == numUsers - preferring2" > Honestly I cannot figure out an interpretation for this case! NaN? > > Thoughts would be much appreciated. > > On Sat, May 31, 2008 at 2:32 PM, Ted Dunning <[EMAIL PROTECTED]> > wrote: > > Yes. That is a good basic recommendation system. Another approach is > > > to use the co-occurrence matrix to find items that have anomalous > > co-occurrence and then build a weighted model based on overall > > frequency. This allows you to weight the recommendations differently > > than you would with the raw co-occurrence score. If you have the > > right audience and interface then you will still do quite well even > > with some moderately poor ordering of the recommendations because your > > > viewers will dig pretty far down into the list. Some other interfaces > are not so forgiving (think radio). > -- ted
