Pearson Ähnlichkeit Score, wie kann ich optimieren diese weiter?

Question

Ich habe eine von Pearson Ähnlichkeitsbewertung implementiert für den Vergleich von zwei Wörterbücher von Werten. Es wird mehr Zeit in diesem Verfahren aufgewendet als anderswo (potenziell viele Millionen Anrufe), so ist dies eindeutig die kritische Methode zu optimieren.

Selbst die geringste Optimierung einen großen Einfluss auf meinen Code haben, so bin ich daran interessiert, auch die kleinsten Verbesserungen zu erforschen.

Hier ist, was ich bisher:

def simple_pearson(v1,v2):

    si = [val for val in v1 if val in v2]

    n = len(si)

    if n==0: return 0.0

    sum1 = 0.0
    sum2 = 0.0
    sum1_sq = 0.0
    sum2_sq = 0.0
    p_sum = 0.0

    for v in si:
        val_1 = v1[v]
        val_2 = v2[v]
        sum1+=val_1
        sum2+=val_2
        sum1_sq+=pow(val_1,2)
        sum2_sq+=pow(val_2,2)
        p_sum+=val_1*val_2

    # Calculate Pearson score
    num = p_sum-(sum1*sum2/n)
    temp = (sum1_sq-pow(sum1,2)/n) * (sum2_sq-pow(sum2,2)/n)
    if temp < 0.0:
        temp = -temp
    den = sqrt(temp)
    if den==0: return 1.0

    r = num/den

    return r

Answer 1

Scipy ist die schnellste!

I don einige Tests mit dem Code oben und auch mit einer Version habe ich auf meinem comp gefunden, siehe unten für die Ergebnisse und der Code:

pearson 14.7597990757
sim_pearson 15.6806837987
scipy:pearsonr 0.451986019188

try:
    import psyco
    psyco.full()
except ImportError:
    pass

from math import sqrt

def sim_pearson(set1, set2):
    si={}
    for item in set1:
        if item in set2:
            si[item] = 1

    #number of elements
    n = len(si)

    #if none common, return 0 similarity
    if n == 0: return 0

    #add up all the preferences
    sum1 = sum([set1[item] for item in si])
    sum2 = sum([set2[item] for item in si])

    #sum up the squares
    sum_sq1 = sum([pow(set1[item], 2) for item in si])
    sum_sq2 = sum([pow(set2[item], 2) for item in si])

    #sum up the products
    sum_p = sum([set1[item] * set2[item] for item in si])

    nom = sum_p - ((sum1 * sum2) / n )
    den = sqrt( (sum_sq1 - (sum1)**2 / n) * (sum_sq2 - (sum2)**2 / n) )

    if den==0: return 0
    return nom/den



# from http://stackoverflow.com/questions/1307016/pearson-similarity-score-how-can-i-optimise-this-further
def pearson(v1, v2):
    vs = [(v1[val],v2[val]) for val in v1 if val in v2]

    n = len(vs)

    if n==0: return 0.0

    sum1,sum2,sum1_sq,sum2_sq,p_sum = 0.0, 0.0, 0.0, 0.0, 0.0

    for v1,v2 in vs:
        sum1+=v1
        sum2+=v2
        sum1_sq+=v1*v1
        sum2_sq+=v2*v2
        p_sum+=v1*v2

    # Calculate Pearson score
    num = p_sum-(sum1*sum2/n)
    temp = max((sum1_sq-pow(sum1,2)/n) * (sum2_sq-pow(sum2,2)/n),0)
    if temp:
        return num / sqrt(temp)
    return 1.0






if __name__ == "__main__":
    import timeit

    tsetup = """
from random import randrange
from __main__ import pearson, sim_pearson
from scipy.stats import pearsonr
v1 = [randrange(0,1000) for x in range(1000)]
v2 = [randrange(0,1000) for x in range(1000)]
#gc.enable()
"""
    t1 = timeit.Timer(stmt="pearson(v1,v2)", setup=tsetup)
    t2 = timeit.Timer(stmt="sim_pearson(v1,v2)", setup=tsetup)
    t3 = timeit.Timer(stmt="pearsonr(v1,v2)", setup=tsetup)

    tt = 1000

    print 'pearson', t1.timeit(tt)
    print 'sim_pearson', t2.timeit(tt)
    print 'scipy:pearsonr', t3.timeit(tt)

Answer 2

Die echte Geschwindigkeit zu erhöhen würde, indem gewonnen werden, um numpy oder scipy. Kurz davon gibt es microoptimizations: z.B. x*x ist schneller als pow(x,2); Sie können die Werte in der gleichen Zeit wie die Tasten, indem Sie statt extrahieren:

si = [val for val in v1 if val in v2]

so etwas wie

vs = [ (v1[val],v2[val]) for val in v1 if val in v2]

und dann

sum1 = sum(x for x, y in vs)

und so weiter; ob jeder von ihnen bringt Zeitvorteil microbenchmarking braucht. Je nachdem, wie Sie diese Koeffizienten verwenden den Platz zurückkehren würde sparen Sie sqrt (das ist eine ähnliche Idee zur Verwendung von Quadraten der Abstände zwischen den Punkten, in der Geometrie, eher als die Abstände selbst, und aus dem gleichen Grund - spart Ihnen eine sqrt ; das macht Sinn, weil der Koeffizient ein Abstand ist, ein bisschen ...; -).

Answer 3

Wenn Sie scipy verwenden können, können Sie die pearson-Funktion: http://svn.scipy.org/svn/scipy/trunk/scipy/stats/stats.py (für def pearson() suchen). In dem Code np nur numpy ist (der Code tut import numpy as np).

Answer 4

Ich würde vorschlagen, zu ändern:

[val for val in v1 if val in v2]

set(v1) & set(v2)

do

if not n: return 0.0    # and similar for den

statt

if n == 0: return 0.0

und es lohnt sich zu ersetzen letzten 6 Zeilen mit:

try:
    return num / sqrt(abs(temp))
except ZeroDivisionError:
    return 1.0

Answer 5

Da es sieht aus wie Sie ziemlich viel numerischen Berechnung zu tun, sollten Sie Psyco ein Schuss. Es ist ein JIT-Compiler, die laufenden Code analysiert und optimiert bestimmte Operationen. Installieren Sie es, dann am Anfang der Datei Put:

try:
    import psyco
    psyco.full()
except ImportError:
    pass

Dies wird Psyco der JIT aktivieren und sollten Sie Ihren Code ein wenig beschleunigen, kostenlos :) (eigentlich nicht, es braucht mehr Speicherplatz)

Answer 6

Wenn die Eingänge auf alle Ihre mathematischen Funktionen ziemlich eingeschränkt sind, können Sie eine Lookup-Tabelle verwenden anstelle der mathematische Funktion. Dies kann man einige Performance (Geschwindigkeit) auf Kosten der zusätzlichen Speicher verdienen, um die Tabelle zu speichern.

Answer 7

Ich bin mir nicht sicher, ob dies in Python hält. Aber die sqrt Berechnung ist eine prozessorintensive Berechnung.

Sie könnten für eine schnelle Annäherung newton

Answer 8

Ich werde schreiben, was ich habe, so weit wie eine Antwort mich von der Frage zu unterscheiden. Dies ist eine Kombination von einigen oben beschriebenen Techniken scheint die beste Verbesserung gegeben zu haben ist weit.

def pearson(v1,v2):
    vs = [(v1[val],v2[val]) for val in v1 if val in v2]

    n = len(vs)

    if n==0: return 0.0

    sum1,sum2,sum1_sq,sum2_sq,p_sum = 0.0, 0.0, 0.0, 0.0, 0.0

    for v1,v2 in vs:
        sum1+=v1
        sum2+=v2
        sum1_sq+=v1*v1
        sum2_sq+=v2*v2
        p_sum+=v1*v2

    # Calculate Pearson score
    num = p_sum-(sum1*sum2/n)
    temp = max((sum1_sq-pow(sum1,2)/n) * (sum2_sq-pow(sum2,2)/n),0)
    if temp:
        return num / sqrt(temp)
    return 1.0

Edit:. Es sieht aus wie psyco 15% improvment für diese Version gibt, die nicht massiv ist, aber genug, um seine Verwendung zu rechtfertigen