皮尔逊相似度评分，如何进一步优化？

Question

我实现了一个用来比较两个值字典的皮尔逊相似度评分的方法。在这个方法上花费的时间比其他地方都多（可能会调用很多百万次），所以显然这是一个需要优化的关键方法。

即使是最小的优化也可能对我的代码产生很大的影响，所以我很想探索任何微小的改进。

这是我目前的代码：

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这个库，你可以用它里面的pearson函数：http://www.scipy.org/doc/api_docs/SciPy.stats.stats.html#pearsonr

或者你也可以从这个链接复制粘贴代码（它的许可证很宽松）：http://svn.scipy.org/svn/scipy/trunk/scipy/stats/stats.py（在里面搜索 def pearson()）。在代码中，np 只是numpy的简称（代码里有 import numpy as np）。

Answer 2

真正提高速度的方法是使用numpy或scipy这类库。如果不想用这些库，还有一些小技巧可以优化，比如用x*x会比pow(x,2)快。你可以在获取键的同时提取值，而不是像这样：

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

可以做成类似这样的

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

然后

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

依此类推；每个小技巧是否能节省时间需要通过微基准测试来验证。根据你使用这些系数的方式，返回平方值可以省去一个开平方的步骤（这和几何中使用点之间的距离平方而不是直接使用距离是一个道理，都是为了省去开平方的计算；这也有道理，因为系数本身就有点像距离...;-）。

Answer 3

Scipy是最快的！

我用上面的代码做了一些测试，还用了一份我在电脑上找到的版本，下面是结果和代码：

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)