EuclideanDistanceSimilarity

[Tamas Jambor <ja...@googlemail.com>]

hi Sean,

I have just tried out the EuclideanDistanceSimilarity method to 
calculate user similarity, but there is something strange it don't 
understand. I use 200 as the neighbourhood size, and within this 
neighbourhood I get a prediction for around 75% of my test items using 
Pearson correlation, but with this new one, I get almost 95% covered for 
the same dataset. Just wondering why, because I would expect the same 
proportion, since the way that the algorithm calculates prediction did 
not change.

thanks,
Tamas

Re: EuclideanDistanceSimilarity

[Sean Owen <sr...@gmail.com>]

Ah OK. That's weird that you get such large RMSE then. I'll see what
my results are later.

On Wed, Mar 3, 2010 at 2:55 PM, Tamas Jambor <ja...@googlemail.com> wrote:
> actually I cap the estimates. the issue is not there.

Re: EuclideanDistanceSimilarity

[Tamas Jambor <ja...@googlemail.com>]

actually I cap the estimates. the issue is not there.

On 03/03/2010 13:50, Sean Owen wrote:
> On Wed, Mar 3, 2010 at 1:45 PM, Tamas Jambor<ja...@googlemail.com>  wrote:
>    
>> my problem is that using Person correlation with adjusted weighed average
>> prediction (i.e. not shifting the weights) results in a very bad RMSE,
>> especially for item-based (but I get a surprisingly good results for other
>> measures), so that surely something wrong with negative weights.
>>      
> Yes, that alone is not sufficient -- you'd need to cap the estimated
> preference value at the minimum / maximum possible values. Otherwise
> the RMSE could be infinite, since the estimate can be arbitrarily
> large or small.
>
> My patch for issue 321 will address this, such that you can safely use
> Pearson. Or you can hack it into your own customized version.
>
>    
>> however, just tried cosine similarity and EuclideanDistanceSimilarity for
>> item-based, they are OK in terms of RMSE (around 1.03 for both), although
>> EuclideanDistanceSimilarity performs a slightly better with other measures (
>> e.g. NDCG, MAP, precision, etc).
>>      
> Euclidean distance similarity works because its weights aren't
> negative. Even if you aren't capping the estimates, you won't get such
> out-of-bounds estimates.
>
> (Uncentered) Cosine measure similarity works for the same reason,
> assuming your preference value range is nonnegative -- the cosine is
> never negative then.
>
> The real solution isn't really to use uncentered data, but to fully
> implement support for negative weights, which means capping.
>    

Re: EuclideanDistanceSimilarity

[Sean Owen <sr...@gmail.com>]

On Wed, Mar 3, 2010 at 1:45 PM, Tamas Jambor <ja...@googlemail.com> wrote:
> my problem is that using Person correlation with adjusted weighed average
> prediction (i.e. not shifting the weights) results in a very bad RMSE,
> especially for item-based (but I get a surprisingly good results for other
> measures), so that surely something wrong with negative weights.

Yes, that alone is not sufficient -- you'd need to cap the estimated
preference value at the minimum / maximum possible values. Otherwise
the RMSE could be infinite, since the estimate can be arbitrarily
large or small.

My patch for issue 321 will address this, such that you can safely use
Pearson. Or you can hack it into your own customized version.

> however, just tried cosine similarity and EuclideanDistanceSimilarity for
> item-based, they are OK in terms of RMSE (around 1.03 for both), although
> EuclideanDistanceSimilarity performs a slightly better with other measures (
> e.g. NDCG, MAP, precision, etc).

Euclidean distance similarity works because its weights aren't
negative. Even if you aren't capping the estimates, you won't get such
out-of-bounds estimates.

(Uncentered) Cosine measure similarity works for the same reason,
assuming your preference value range is nonnegative -- the cosine is
never negative then.

The real solution isn't really to use uncentered data, but to fully
implement support for negative weights, which means capping.

Re: EuclideanDistanceSimilarity

[Tamas Jambor <ja...@googlemail.com>]

> You can easily implement an uncentered cosine similarity metric. If
> you have reasons to do this I'd be curious to hear -- are there
> practical reasons for it?
>    
my problem is that using Person correlation with adjusted weighed 
average prediction (i.e. not shifting the weights) results in a very bad 
RMSE, especially for item-based (but I get a surprisingly good results 
for other measures), so that surely something wrong with negative weights.
however, just tried cosine similarity and EuclideanDistanceSimilarity 
for item-based, they are OK in terms of RMSE (around 1.03 for both), 
although EuclideanDistanceSimilarity performs a slightly better with 
other measures ( e.g. NDCG, MAP, precision, etc).

T

Re: EuclideanDistanceSimilarity

[Sean Owen <sr...@gmail.com>]

On Wed, Mar 3, 2010 at 11:21 AM, Tamas Jambor <ja...@googlemail.com> wrote:
> for me one good practical indication would be, as you mentioned, that we
> don't have to deal with negative similarity, which is still a problem for
> me.

(I opened https://issues.apache.org/jira/browse/MAHOUT-321 to track
this -- I have most of a patch done which removes the "+1" and
replaces it with capping.)


> my understanding of the question is that when you center the data, you can
> interpret person correlation as cosine similarity, but in fact that has
> nothing to do with
> cosine similarity in the sense of the original definition, since we
> transformed the vectors so their direction is different.

If you mean the cosine of the angle between the original and
transformed vectors is different -- of course, yes. I'm suggesting the
measure is more meaningful on the transformed vectors for the reasons
I gave. I understand this to be standard practice, but am not an
expert on this particular issue.

You can easily implement an uncentered cosine similarity metric. If
you have reasons to do this I'd be curious to hear -- are there
practical reasons for it?

Re: EuclideanDistanceSimilarity

[Tamas Jambor <ja...@googlemail.com>]

for me one good practical indication would be, as you mentioned, that we 
don't have to deal with negative similarity, which is still a problem 
for me.

my understanding of the question is that when you center the data, you 
can interpret person correlation as cosine similarity, but in fact that 
has nothing to do with
cosine similarity in the sense of the original definition, since we 
transformed the vectors so their direction is different.

T

On 03/03/2010 08:37, Sean Owen wrote:
> That's right. I used to have separate implementations.
>
> This might be a good question to ask the experts: while based on my
> understanding of the issues, it seems a bit better to compute the
> cosine measure based on centered (mean = 0) data, I wonder if there
> are good arguments for not doing this?
>
> Instead of computing the cosine of the angle between user vectors A
> and B, it would be computing the cosine of the angle between A+m_A and
> B+m_B, where m_A and m_B are vectors whose entries are just the
> average of elements in A and B respectively. It pushes the A and B
> endpoints out in the direction of (1,1,...1) or (-1,-1,...,-1).
>
> This narrows the angle, and makes similarities tends towards 1. In
> fact for the case where ratings are in, say, [0,10], the angle never
> gets past 90 degrees, so the similarity is in [0,1] and not even
> [-1,1]. It feels like it's losing a bit of dynamic range, but that's
> got to be a minor issue.
>
> That is the greater the average preference, the less difference in
> preference will matter to the similarity measure. The only aspect of
> this I don't like is that differences in preferences at the small end
> of the range matter much more, which doesn't seem intuitively right.
> The similarity between users who rated two movies (0,1) and (1,0) is
> as low as possible -- 0 -- while the similarity between users who
> rated two movies (9,10) and (10,9) is nearly 1. But in both cases they
> rated two movies quite similarly on a scale of 0 to 10. With
> centering, the result would have been identical.
>
>
>
> On Wed, Mar 3, 2010 at 12:19 AM, Tamas Jambor<ja...@googlemail.com>  wrote:
>    
>> sure, if you center the data then they are identical. but the uncentered
>> cosine similarity is quite different, as far as I know.
>>
>> T
>>
>> On 02/03/2010 22:55, Sean Owen wrote:
>>      
>>> Yes, that's also the Pearson-correlation-based one, since it forces
>>> the data to be 'centered' (mean of 0) during the computation. In that
>>> case they are actually identical.
>>>
>>> On Tue, Mar 2, 2010 at 10:47 PM, Tamas Jambor<ja...@googlemail.com>
>>>   wrote:
>>>
>>>        
>>>> Thanks. that makes sense. Which one would be cosine similarity? do you
>>>> have
>>>> that implemented?
>>>>
>>>>          
>>
>>      

Re: EuclideanDistanceSimilarity

[Sean Owen <sr...@gmail.com>]

That's right. I used to have separate implementations.

This might be a good question to ask the experts: while based on my
understanding of the issues, it seems a bit better to compute the
cosine measure based on centered (mean = 0) data, I wonder if there
are good arguments for not doing this?

Instead of computing the cosine of the angle between user vectors A
and B, it would be computing the cosine of the angle between A+m_A and
B+m_B, where m_A and m_B are vectors whose entries are just the
average of elements in A and B respectively. It pushes the A and B
endpoints out in the direction of (1,1,...1) or (-1,-1,...,-1).

This narrows the angle, and makes similarities tends towards 1. In
fact for the case where ratings are in, say, [0,10], the angle never
gets past 90 degrees, so the similarity is in [0,1] and not even
[-1,1]. It feels like it's losing a bit of dynamic range, but that's
got to be a minor issue.

That is the greater the average preference, the less difference in
preference will matter to the similarity measure. The only aspect of
this I don't like is that differences in preferences at the small end
of the range matter much more, which doesn't seem intuitively right.
The similarity between users who rated two movies (0,1) and (1,0) is
as low as possible -- 0 -- while the similarity between users who
rated two movies (9,10) and (10,9) is nearly 1. But in both cases they
rated two movies quite similarly on a scale of 0 to 10. With
centering, the result would have been identical.



On Wed, Mar 3, 2010 at 12:19 AM, Tamas Jambor <ja...@googlemail.com> wrote:
> sure, if you center the data then they are identical. but the uncentered
> cosine similarity is quite different, as far as I know.
>
> T
>
> On 02/03/2010 22:55, Sean Owen wrote:
>>
>> Yes, that's also the Pearson-correlation-based one, since it forces
>> the data to be 'centered' (mean of 0) during the computation. In that
>> case they are actually identical.
>>
>> On Tue, Mar 2, 2010 at 10:47 PM, Tamas Jambor<ja...@googlemail.com>
>>  wrote:
>>
>>>
>>> Thanks. that makes sense. Which one would be cosine similarity? do you
>>> have
>>> that implemented?
>>>
>
>

Re: EuclideanDistanceSimilarity

[Tamas Jambor <ja...@googlemail.com>]

sure, if you center the data then they are identical. but the uncentered 
cosine similarity is quite different, as far as I know.

T

On 02/03/2010 22:55, Sean Owen wrote:
> Yes, that's also the Pearson-correlation-based one, since it forces
> the data to be 'centered' (mean of 0) during the computation. In that
> case they are actually identical.
>
> On Tue, Mar 2, 2010 at 10:47 PM, Tamas Jambor<ja...@googlemail.com>  wrote:
>    
>> Thanks. that makes sense. Which one would be cosine similarity? do you have
>> that implemented?
>>      

Re: EuclideanDistanceSimilarity

[Sean Owen <sr...@gmail.com>]

Yes, that's also the Pearson-correlation-based one, since it forces
the data to be 'centered' (mean of 0) during the computation. In that
case they are actually identical.

On Tue, Mar 2, 2010 at 10:47 PM, Tamas Jambor <ja...@googlemail.com> wrote:
> Thanks. that makes sense. Which one would be cosine similarity? do you have
> that implemented?

Re: EuclideanDistanceSimilarity

[Tamas Jambor <ja...@googlemail.com>]

Thanks. that makes sense. Which one would be cosine similarity? do you 
have that implemented?

Tamas

On 02/03/2010 21:31, Sean Owen wrote:
> My guess is that it is due to the fact that the Pearson correlation is
> undefined for two series of just one data point -- that is, two items
> or users that overlap in only one preference will have no similarity.
> Very 'isolated' items have no similarity to anything else and no
> estimate can be produced.
>
> The Euclidean distance-based metric doesn't have this property.
>
>
>
> On Tue, Mar 2, 2010 at 9:25 PM, Tamas Jambor<ja...@googlemail.com>  wrote:
>    
>> hi Sean,
>>
>> I have just tried out the EuclideanDistanceSimilarity method to calculate
>> user similarity, but there is something strange it don't understand. I use
>> 200 as the neighbourhood size, and within this neighbourhood I get a
>> prediction for around 75% of my test items using Pearson correlation, but
>> with this new one, I get almost 95% covered for the same dataset. Just
>> wondering why, because I would expect the same proportion, since the way
>> that the algorithm calculates prediction did not change.
>>
>> thanks,
>> Tamas
>>
>>      

Re: EuclideanDistanceSimilarity

[Sean Owen <sr...@gmail.com>]

My guess is that it is due to the fact that the Pearson correlation is
undefined for two series of just one data point -- that is, two items
or users that overlap in only one preference will have no similarity.
Very 'isolated' items have no similarity to anything else and no
estimate can be produced.

The Euclidean distance-based metric doesn't have this property.



On Tue, Mar 2, 2010 at 9:25 PM, Tamas Jambor <ja...@googlemail.com> wrote:
> hi Sean,
>
> I have just tried out the EuclideanDistanceSimilarity method to calculate
> user similarity, but there is something strange it don't understand. I use
> 200 as the neighbourhood size, and within this neighbourhood I get a
> prediction for around 75% of my test items using Pearson correlation, but
> with this new one, I get almost 95% covered for the same dataset. Just
> wondering why, because I would expect the same proportion, since the way
> that the algorithm calculates prediction did not change.
>
> thanks,
> Tamas
>