Re: [jira] Commented: (MAHOUT-103) Co-occurence based nearest neighbourhood

[Ankur Goel <an...@corp.aol.com>]

Hi Ted,
      Since we are doing simple co-occurrence based counting, the counts will be of the form - 
A -> B:[double value] , C:[double value] ...
B -> A:[double value], D:[double value] ...

Initially it was a long value but later changed to double as I had to apply a linear decay to the score to get better results.
Note that scores might not be symmetric because of this, A->B score would be higher if B occurred after A but the same fact would make B->A score lower.

As you can see from each entry we can get the values for AB and AB'. 
A'B and A'B' are not available directly in a single result and need to be computed.

It would be nice to hear how you are planning to implement this in map-red.

Thanks
-Ankur

----- Original Message -----
From: "Ted Dunning" <te...@gmail.com>
To: mahout-dev@lucene.apache.org
Sent: Thursday, March 19, 2009 12:05:30 PM GMT +05:30 Chennai, Kolkata, Mumbai, New Delhi
Subject: Re: [jira] Commented: (MAHOUT-103) Co-occurence based nearest  neighbourhood

Ankur,

What form will the counts be in when you need this function?

Four integers separately available?

Values in a view of a matrix?

I will be happy to adapt some code to compute the measure you need.

On Wed, Mar 18, 2009 at 9:45 PM, Ankur (JIRA) <ji...@apache.org> wrote:

> map-red implementation of the log-likelihood ratio test as described in
> Ted's paper.




-- 
Ted Dunning, CTO
DeepDyve

Re: [jira] Commented: (MAHOUT-103) Co-occurence based nearest neighbourhood

[Ted Dunning <te...@gmail.com>]

The classic technique is to get total counts for B and for all events and
assume that these are effectively *B and *B' (that is, the number of times
that B exists is the number of times that either A or A' occurred with B).
This is usually just fine.  Then k(A'B) = k(B) - k(AB) and k(A'B') = k(*) -
k(B) - k(AB').  It is commonly necessary to compute the total and the
individual item counts like k(B) in a separate pass through the data, but
some storage schemes may make that unnecessary.

To get this right requires a careful touch.  I try to keep in mind that if
we start with a binary occurrence matrix U = users x items, then the item
cooccurrence matrix should be exactly U' U = items x items.  If U is
represented as a set of (user, item) pairs, then we can compute U' U by a
join to self followed by counting.  This usually results in a list of (item,
item, count) triples.

The item counts are then the rowsums of U' U and the overall sum of U' U is
the total count.  These can easily be computed from U' U and take much less
time than computing U' U.  Note that U' U is symmetrical so you should only
need to compute the rowsums.  Checking that the column sums are the same is
a nice exercise, but not necessary in production.  The rowsums are
represented (item, count) pairs and the overall total is just a count.

The final scoring of the cooccurrence counts requires that you join the
triples that form U' U once with the rowsums against the first member of the
triple and then again with the against the second member of the triple.  You
can carry around the overall total separately, but there is an implied join
against this single number as well.

This gives you tuples of the form (a, b, count_ab, count_a, count_b,
total).  The counts you need for the contingency table are

    count_ab,                  count_a - count_ab
    count_b - count_ab,        total - count_a - count_b + count_ab

Does this answer your question?

I can make the log-likelihood code have a method that takes count_ab,
count_a, count_b and total as arguments.

On Sun, Mar 22, 2009 at 10:32 PM, Ankur Goel <an...@corp.aol.com>wrote:

> As you can see from each entry we can get the values for AB and AB'.
> A'B and A'B' are not available directly in a single result and need to be
> computed.
>
> It would be nice to hear how you are planning to implement this in map-red.
>



-- 
Ted Dunning, CTO
DeepDyve

111 West Evelyn Ave. Ste. 202
Sunnyvale, CA 94086
www.deepdyve.com
408-773-0110 ext. 738
858-414-0013 (m)
408-773-0220 (fax)