Евклидово расстояние Python Реализация

Question

Я играю со следующим кодом из программирования коллективного разума, это функция из книги, которая рассчитала расстояние эклидана между двумя кинокритиками.

Эта функция суммирует разницу в ранжировании в словаре, но евклидово расстояние в n измерениях также включает квадратный корень из этой суммы.

AFAIK, поскольку мы используем одну и ту же функцию для ранжирования всех, не имеет значения, квадратный корень мы или нет, но мне было интересно, есть ли для этого особая причина?

from math import sqrt 
# Returns a distance-based similarity score for person1 and person2 
def sim_distance(prefs,person1,person2): 
  # Get the list of shared_items 
  si={} 
  for item in prefs[person1]: 
    if item in prefs[person2]: 
       si[item]=1 
  # if they have no ratings in common, return 0 
  if len(si)==0: return 0 
  # Add up the squares of all the differences 
  sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2) 
                      for item in prefs[person1] if item in prefs[person2]]) 
  return 1/(1+sum_of_squares) 

Answer 1

Причина квадратный корень не используется, потому что это вычислительно дорого; это монотонная (т.е. сохраняет порядок) с квадратичной функции, так что если все вы заинтересованы в том, порядок расстояний, квадратный корень не нужен (и, как уже упоминалось, очень дорогие вычислительно).

Answer 2

Это верно. Хотя квадратный корень необходим для количественно правильного результата, если все, что вам нужно, это расстояние относительно других для сортировки, то брать квадратный корень излишне.

Answer 3

Чтобы вычислить декартово расстояние, сначала вы должны вычислить квадрат расстояния, а затем взять его квадратный корень. Но вычисление квадратного корня вычислительно дорого. Если все, что вас действительно интересует, это сравнение расстояний, то можно сравнить квадрат расстояния - и это намного быстрее.

Для каждых двух действительных чисел A и B, где A и B>> = ноль, всегда верно, что A-квадрат и B-квадрат имеют те же отношения, что и A и B:

• если A если A == B, то A-квадрат == B-квадрат.
• если A> B, то A-квадрат> B-квадрат.

Поскольку расстояния всегда> = 0, это соотношение означает, что сравнение квадрата расстояния дает вам тот же ответ, что и сравнение расстояния.

Answer 4

Просто для взаимных сравнений квадратный корень не нужен, и вы получите квадрат евклидова расстояния ... которое также является расстоянием (математически, см. http://en.wikipedia.org/wiki/Metric_%28mathematics%29).