método optimizado para el cálculo de la distancia del coseno en Python

Question

me escribió un método para calcular la distancia entre dos matrices coseno:

def cosine_distance(a, b): 
    if len(a) != len(b): 
     return False 
    numerator = 0 
    denoma = 0 
    denomb = 0 
    for i in range(len(a)): 
     numerator += a[i]*b[i] 
     denoma += abs(a[i])**2 
     denomb += abs(b[i])**2 
    result = 1 - numerator/(sqrt(denoma)*sqrt(denomb)) 
    return result 

Correr puede ser muy lento en una gran variedad. ¿Hay una versión optimizada de este método que se ejecute más rápido?

Actualización: He intentado todas las sugerencias hasta la fecha, incluso scipy. Aquí está la versión de superar, incorporando las sugerencias de Mike y Steve:

def cosine_distance(a, b): 
    if len(a) != len(b): 
     raise ValueError, "a and b must be same length" #Steve 
    numerator = 0 
    denoma = 0 
    denomb = 0 
    for i in range(len(a)):  #Mike's optimizations: 
     ai = a[i]    #only calculate once 
     bi = b[i] 
     numerator += ai*bi #faster than exponent (barely) 
     denoma += ai*ai  #strip abs() since it's squaring 
     denomb += bi*bi 
    result = 1 - numerator/(sqrt(denoma)*sqrt(denomb)) 
    return result 

Answer 1

Si puede utilizar SciPy, puede utilizar cosine de spatial.distance:

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

Si no puede utilizar SciPy , podrías tratar de obtener una pequeña aceleración reescribiendo tu Python (EDITAR: pero no funcionó como pensé, ver más abajo).

from itertools import izip 
from math import sqrt 

def cosine_distance(a, b): 
    if len(a) != len(b): 
     raise ValueError, "a and b must be same length" 
    numerator = sum(tup[0] * tup[1] for tup in izip(a,b)) 
    denoma = sum(avalue ** 2 for avalue in a) 
    denomb = sum(bvalue ** 2 for bvalue in b) 
    result = 1 - numerator/(sqrt(denoma)*sqrt(denomb)) 
    return result 

Es mejor hacer una excepción cuando las longitudes de a y b no coinciden.

Al usar las expresiones del generador dentro de las llamadas al sum() puede calcular sus valores con la mayor parte del trabajo realizado por el código C dentro de Python. Esto debería ser más rápido que usar un bucle for.

No he cronometrado esto, así que no puedo adivinar cuánto más rápido podría ser. Pero el código de SciPy casi seguramente está escrito en C o C++ y debe ser lo más rápido que puedas obtener.

Si está haciendo bioinformática en Python, de todos modos debería estar usando SciPy.

EDITAR: Darius Bacon programó mi código y lo encontró más lento. Así que sincronicé mi código y ... sí, es más lento. La lección para todos: cuando tratas de acelerar las cosas, no adivines, mide.

Estoy desconcertado de por qué mi intento de poner más trabajo en el C interno de Python es más lento. Lo intenté para listas de longitud 1000 y aún así fue más lento.

No puedo pasar más tiempo tratando de hackear el Python inteligentemente. Si necesitas más velocidad, te sugiero que pruebes SciPy.

EDIT: Acabo de probar a mano, sin timeit. Encuentro que, para abreviar a y b, el código anterior es más rápido; para long a y b, el nuevo código es más rápido; en ambos casos la diferencia no es grande. (Ahora me pregunto si puedo confiar en el tiempo en mi computadora con Windows, quiero probar esta prueba nuevamente en Linux.) No cambiaría el código de trabajo para tratar de hacerlo más rápido. Y una vez más te insto a que pruebes SciPy. :-)

Answer 2

Esto es más rápido para matrices de más de 1000 elementos.

from numpy import array 
def cosine_distance(a, b): 
    a=array(a) 
    b=array(b) 
    numerator=(a*b).sum() 
    denoma=(a*a).sum() 
    denomb=(b*b).sum() 
    result = 1 - numerator/sqrt(denoma*denomb) 
    return result 

Answer 3

(Originalmente pensé) que no vas a acelerarlo mucho sin romper a C (como numpy o scipy) o cambiar lo que permite calcular. Pero así es como me gustaría probar que, de todos modos:

from itertools import imap 
from math import sqrt 
from operator import mul 

def cosine_distance(a, b): 
    assert len(a) == len(b) 
    return 1 - (sum(imap(mul, a, b)) 
       /sqrt(sum(imap(mul, a, a)) 
         * sum(imap(mul, b, b)))) 

Es más o menos el doble de rápido en Python 2.6 con matrices de elementos 500k. (Después de cambiar el mapa a imap, siguiendo a Jarret Hardie.)

Aquí es una versión modificada del código revisado de su creador original:

Es feo, pero viene más rápido. . .

Editar: Y prueba Psyco! Se acelera la versión final por otro factor de 4. ¿Cómo podría olvidarlo?

Answer 4

Al igual que la respuesta de Darius Bacon, he estado jugando con el operador y las herramientas de iteración para producir una respuesta más rápida. El siguiente parece ser un tercio más rápido en una matriz de 500 ítems de acuerdo a timeit:

from math import sqrt 
from itertools import imap 
from operator import mul 

def op_cosine(a, b): 
    dot_prod = sum(imap(mul, a, b)) 
    a_veclen = sqrt(sum(i ** 2 for i in a)) 
    b_veclen = sqrt(sum(i ** 2 for i in b)) 

    return 1 - dot_prod/(a_veclen * b_veclen) 

Answer 5

No hay necesidad de tomar abs() de a[i]b[i] y si está elevarlo al cuadrado.

Tienda a[i] y b[i] en variables temporales, para evitar hacer la indexación más de una vez. Quizás el compilador pueda optimizar esto, pero tal vez no.

Compruebe en el operador **2. ¿Se está simplificando en una multiplicación, o está usando una función de potencia general (log - multiplicar por 2 - antilogaritmo).

No haga sqrt dos veces (aunque el costo de eso es pequeño). Do sqrt(denoma * denomb).

Answer 6

def cd(a,b): 
    if(len(a)!=len(b)): 
     raise ValueError, "a and b must be the same length" 
    rn = range(len(a)) 
    adb = sum([a[k]*b[k] for k in rn]) 
    nma = sqrt(sum([a[k]*a[k] for k in rn])) 
    nmb = sqrt(sum([b[k]*b[k] for k in rn])) 

    result = 1 - adb/(nma*nmb) 
    return result 

Answer 7

El uso del código C dentro de SciPy gana a lo grande en las matrices de entrada largas. El uso de Python simple y directo gana para matrices de entrada cortas; El código basado en izip() de Darius Bacon es el mejor evaluado. Por lo tanto, la última solución es decidir cuál usar en tiempo de ejecución, con base en la longitud de las matrices de entrada:

from scipy.spatial.distance import cosine as scipy_cos_dist 

from itertools import izip 
from math import sqrt 

def cosine_distance(a, b): 
    len_a = len(a) 
    assert len_a == len(b) 
    if len_a > 200: # 200 is a magic value found by benchmark 
     return scipy_cos_dist(a, b) 
    # function below is basically just Darius Bacon's code 
    ab_sum = a_sum = b_sum = 0 
    for ai, bi in izip(a, b): 
     ab_sum += ai * bi 
     a_sum += ai * ai 
     b_sum += bi * bi 
    return 1 - ab_sum/sqrt(a_sum * b_sum) 

hice un instrumento de prueba que puso a prueba las funciones con diferentes entradas de longitud, y se encontró que alrededor de la longitud 200 la función SciPy comenzó a ganar. Mientras más grandes sean las matrices de entrada, más grande gana. Para arreglos de muy corta longitud, digamos longitud 3, gana el código más simple. Esta función agrega una pequeña cantidad de sobrecarga para decidir de qué manera hacerlo, y luego lo hace de la mejor manera.

En caso de estar interesado, aquí es el instrumento de prueba:

from darius2 import cosine_distance as fn_darius2 
fn_darius2.__name__ = "fn_darius2" 

from ult import cosine_distance as fn_ult 
fn_ult.__name__ = "fn_ult" 

from scipy.spatial.distance import cosine as fn_scipy 
fn_scipy.__name__ = "fn_scipy" 

import random 
import time 

lst_fn = [fn_darius2, fn_scipy, fn_ult] 

def run_test(fn, lst0, lst1, test_len): 
    start = time.time() 
    for _ in xrange(test_len): 
     fn(lst0, lst1) 
    end = time.time() 
    return end - start 

for data_len in range(50, 500, 10): 
    a = [random.random() for _ in xrange(data_len)] 
    b = [random.random() for _ in xrange(data_len)] 
    print "len(a) ==", len(a) 
    test_len = 10**3 
    for fn in lst_fn: 
     n = fn.__name__ 
     r = fn(a, b) 
     t = run_test(fn, a, b, test_len) 
     print "%s:\t%f seconds, result %f" % (n, t, r) 

Answer 8

Su solución actualizada todavía tiene dos raíces cuadradas. Puede reducir esto a uno mediante la sustitución de la línea sqrt con:

resultado = 1 - numerador/ (sqrt (denoma * denomb))

A se multiplican es típicamente un poco más rápido que una sqrt. Puede que no parezca mucho, ya que solo se llama una vez en la función, pero parece que estás calculando muchas distancias de coseno, por lo que la mejora se sumará.

Su código parece que debería estar listo para las optimizaciones vectoriales.Entonces, si el soporte de plataformas cruzadas no es un problema y quieres acelerarlo aún más, puedes codificar el código de distancia del coseno en C y asegurarte de que tu compilador vectoriza agresivamente el código resultante (incluso el Pentium II puede vectorizar puntos flotantes))