Euklidische Entfernung Python-Implementierung

Question

ich mit dem folgenden Code aus der Programmierung kollektive Intelligenz spielte, ist dies eine Funktion aus dem Buch, die eclidian Abstand zwischen zwei Filmkritikern berechnet.

Diese Funktion summiert die Differenz der Klassifizierungen in dem Wörterbuch, aber euklidischer Abstand in n Dimensionen enthält auch die Quadratwurzel aus dieser Summe.

AFAIK, da wir die gleiche Funktion zu ordnen jeder benutzen es nicht wir Quadratwurzel Materie oder nicht, aber ich frage mich, ist es einen bestimmten Grund dafür?

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

Der Grund für die Quadratwurzel nicht verwendet wird, ist, weil es rechnerisch teuer ist; es ist monotone (das heißt, es bewahrt Reihenfolge) mit der Quadrat-Funktion, so dass, wenn alles, was Sie interessiert sind, in der Reihenfolge der Abstände, die Quadratwurzel nicht erforderlich ist (und, wie erwähnt, sehr teuer rechnerisch).

Answer 2

Das ist richtig. Während die Quadratwurzel für ein quantitativ korrektes Ergebnis notwendig ist, wenn alle um dich kümmern ist Abstand zu anderen für die Sortierung, dann die Quadratwurzel ist überflüssig.

Answer 3

ein cartesianischen Abstand zu berechnen, müssen Sie zuerst die Distanz-squared berechnen, dann nehmen Sie seine Quadratwurzel. Aber eine Quadratwurzel Berechnung ist rechnerisch teuer. Wenn alle sind Sie wirklich daran interessiert ist, den Vergleich Entfernungen, es funktioniert genauso gut den Abstand-squared zu vergleichen -. Und es ist viel schneller

Für jeden zwei reelle Zahlen A und B, wobei A und B> = Null, ist es immer wahr sind, dass A-squared und B-Quadrat hat die gleiche Beziehung wie A und B:

• , wenn A
• , wenn A == B, dann A-squared == B-squared.
• , wenn A> B, dann A-squared> B-squared.

Da Entfernungen sind immer> = 0 diese Beziehung bedeutet Vergleich Abstand-squared gibt Ihnen die gleiche Antwort wie Abstand zu vergleichen.

Answer 4

Nur für Ringversuche die Quadratwurzel nicht notwendig ist, und Sie würden den quadratischen euklidischen Abstand bekommen ... die auch ein Abstand (mathematisch gesprochen, finden Sie unter http://en.wikipedia.org/wiki/Metric_%28mathematics%29 ).