You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by "Sean Owen (Created) (JIRA)" <ji...@apache.org> on 2011/10/20 15:22:11 UTC
[jira] [Created] (MAHOUT-847) Improve Euclidean distance similarity
calculation
Improve Euclidean distance similarity calculation
-------------------------------------------------
Key: MAHOUT-847
URL: https://issues.apache.org/jira/browse/MAHOUT-847
Project: Mahout
Issue Type: Improvement
Components: Collaborative Filtering
Affects Versions: 0.5
Reporter: Sean Owen
Assignee: Sean Owen
Priority: Minor
Fix For: 0.6
In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
I propose fixing the calculation accordingly.
In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-847) Improve Euclidean distance
similarity calculation
Posted by "Lance Norskog (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-847?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13132191#comment-13132191 ]
Lance Norskog commented on MAHOUT-847:
--------------------------------------
As a perpetual beginner, it is daunting to learn Mahout. It helps if well-defined math terms are only used when the code matches the (200-year-old) concept.
WarpedEuclideanSimilarity perhaps would be more clear.
> Improve Euclidean distance similarity calculation
> -------------------------------------------------
>
> Key: MAHOUT-847
> URL: https://issues.apache.org/jira/browse/MAHOUT-847
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Sean Owen
> Assignee: Sean Owen
> Priority: Minor
> Labels: distance, euclidean, similarity, vector
> Fix For: 0.6
>
> Attachments: MAHOUT-847.patch
>
>
> In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
> I propose fixing the calculation accordingly.
> In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-847) Improve Euclidean distance
similarity calculation
Posted by "Lance Norskog (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-847?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13132186#comment-13132186 ]
Lance Norskog commented on MAHOUT-847:
--------------------------------------
A instance of this class will probably be called with the same 'n' over and over, so it could cache sqrt(n).
> Improve Euclidean distance similarity calculation
> -------------------------------------------------
>
> Key: MAHOUT-847
> URL: https://issues.apache.org/jira/browse/MAHOUT-847
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Sean Owen
> Assignee: Sean Owen
> Priority: Minor
> Labels: distance, euclidean, similarity, vector
> Fix For: 0.6
>
> Attachments: MAHOUT-847.patch
>
>
> In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
> I propose fixing the calculation accordingly.
> In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-847) Improve Euclidean distance similarity
calculation
Posted by "Sean Owen (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-847?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen updated MAHOUT-847:
-----------------------------
Attachment: MAHOUT-847.patch
> Improve Euclidean distance similarity calculation
> -------------------------------------------------
>
> Key: MAHOUT-847
> URL: https://issues.apache.org/jira/browse/MAHOUT-847
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Sean Owen
> Assignee: Sean Owen
> Priority: Minor
> Labels: distance, euclidean, similarity, vector
> Fix For: 0.6
>
> Attachments: MAHOUT-847.patch
>
>
> In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
> I propose fixing the calculation accordingly.
> In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-847) Improve Euclidean distance similarity
calculation
Posted by "Sean Owen (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-847?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen updated MAHOUT-847:
-----------------------------
Status: Patch Available (was: Open)
> Improve Euclidean distance similarity calculation
> -------------------------------------------------
>
> Key: MAHOUT-847
> URL: https://issues.apache.org/jira/browse/MAHOUT-847
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Sean Owen
> Assignee: Sean Owen
> Priority: Minor
> Labels: distance, euclidean, similarity, vector
> Fix For: 0.6
>
> Attachments: MAHOUT-847.patch
>
>
> In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
> I propose fixing the calculation accordingly.
> In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-847) Improve Euclidean distance
similarity calculation
Posted by "Sean Owen (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-847?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13132507#comment-13132507 ]
Sean Owen commented on MAHOUT-847:
----------------------------------
The problem with caching sqrt(n) is that every pair of users / vectors may overlap in a different number of dimensions. It's not fixed (or if it were, I wouldn't be correcting for it as it wouldn't change ordering).
Well, the real Euclidean distance is in there alright. It is not a similarity metric by itself (it gets bigger with less similarity). So there's a transformation to a similarity value, and that's the made-up bit I'm changing here. I think "EuclideanDistance"+"Similarity" is therefore accurate.
> Improve Euclidean distance similarity calculation
> -------------------------------------------------
>
> Key: MAHOUT-847
> URL: https://issues.apache.org/jira/browse/MAHOUT-847
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Sean Owen
> Assignee: Sean Owen
> Priority: Minor
> Labels: distance, euclidean, similarity, vector
> Fix For: 0.6
>
> Attachments: MAHOUT-847.patch
>
>
> In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
> I propose fixing the calculation accordingly.
> In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-847) Improve Euclidean distance
similarity calculation
Posted by "Sean Owen (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-847?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13133279#comment-13133279 ]
Sean Owen commented on MAHOUT-847:
----------------------------------
No, EuclideanDistanceMeasure is a distance measure rather than similarity measure. That is, it can be bigger than 1 and (obviously) gets bigger as the Euclidean distance grows. It is not changed, and continues to return the usual Euclidean distance. This is not used in recommenders.
> Improve Euclidean distance similarity calculation
> -------------------------------------------------
>
> Key: MAHOUT-847
> URL: https://issues.apache.org/jira/browse/MAHOUT-847
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Sean Owen
> Assignee: Sean Owen
> Priority: Minor
> Labels: distance, euclidean, similarity, vector
> Fix For: 0.6
>
> Attachments: MAHOUT-847.patch
>
>
> In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
> I propose fixing the calculation accordingly.
> In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (MAHOUT-847) Improve Euclidean
distance similarity calculation
Posted by "Lance Norskog (Issue Comment Edited) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-847?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13132191#comment-13132191 ]
Lance Norskog edited comment on MAHOUT-847 at 10/20/11 11:24 PM:
-----------------------------------------------------------------
As a perpetual beginner, it is daunting to learn Mahout. It helps if well-defined math terms are only used when the code matches the (200-year-old) concept.
Perhaps _WarpedEuclideanSimilarity_ would be more clear?
was (Author: lancenorskog):
As a perpetual beginner, it is daunting to learn Mahout. It helps if well-defined math terms are only used when the code matches the (200-year-old) concept.
WarpedEuclideanSimilarity perhaps would be more clear.
> Improve Euclidean distance similarity calculation
> -------------------------------------------------
>
> Key: MAHOUT-847
> URL: https://issues.apache.org/jira/browse/MAHOUT-847
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Sean Owen
> Assignee: Sean Owen
> Priority: Minor
> Labels: distance, euclidean, similarity, vector
> Fix For: 0.6
>
> Attachments: MAHOUT-847.patch
>
>
> In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
> I propose fixing the calculation accordingly.
> In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (MAHOUT-847) Improve Euclidean distance similarity
calculation
Posted by "Sean Owen (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-847?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sean Owen updated MAHOUT-847:
-----------------------------
Resolution: Fixed
Status: Resolved (was: Patch Available)
> Improve Euclidean distance similarity calculation
> -------------------------------------------------
>
> Key: MAHOUT-847
> URL: https://issues.apache.org/jira/browse/MAHOUT-847
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Sean Owen
> Assignee: Sean Owen
> Priority: Minor
> Labels: distance, euclidean, similarity, vector
> Fix For: 0.6
>
> Attachments: MAHOUT-847.patch
>
>
> In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
> I propose fixing the calculation accordingly.
> In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (MAHOUT-847) Improve Euclidean distance
similarity calculation
Posted by "Lance Norskog (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/MAHOUT-847?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13133234#comment-13133234 ]
Lance Norskog commented on MAHOUT-847:
--------------------------------------
How does this compare with EuclideanDistanceMeasure? Does EDM have the same semantics as the old or new EDSimilarity? If I use one or the other in parallel-structured recommender stacks should I expect roughly the same results? Or, should EDM be rewritten to match?
> Improve Euclidean distance similarity calculation
> -------------------------------------------------
>
> Key: MAHOUT-847
> URL: https://issues.apache.org/jira/browse/MAHOUT-847
> Project: Mahout
> Issue Type: Improvement
> Components: Collaborative Filtering
> Affects Versions: 0.5
> Reporter: Sean Owen
> Assignee: Sean Owen
> Priority: Minor
> Labels: distance, euclidean, similarity, vector
> Fix For: 0.6
>
> Attachments: MAHOUT-847.patch
>
>
> In the non-distributed recommender world, the Euclidean distance similarity is calculated as n/(1+d), where d is distance and n is dimension. 1/(1+d) is a valid mapping from distance [0,infinity) to similarity (0,1]. n is there to "correct" for the fact that things are farther apart in higher dimensions. It would be right-er, after some discussion, to use a factor of sqrt(n), and apply directly to the distance; 1/(1+d/sqrt(n)).
> I propose fixing the calculation accordingly.
> In the distributed similarity, the formula is 1-1/(1+d), which is the wrong way around. That will be fixed. I'd apply the same heuristic, except that at the moment we don't have access to the value of n at that point. I don't like the inconsistency but it's minor; would rather get this change in now, which definitely improves things.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira