代码之家  ›  专栏  ›  技术社区  ›  Andrew Ingram

皮尔逊相似度评分,我如何进一步优化?

  •  2
  • Andrew Ingram  · 技术社区  · 15 年前

    我已经实现了Pearson的相似性评分,用于比较两个价值词典。这种方法花费的时间比其他任何地方都多(可能有数百万次调用),因此这显然是优化的关键方法。

    即使是最轻微的优化也会对我的代码产生很大的影响,所以我很想探索哪怕是最小的改进。

    以下是我目前为止的情况:

    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
    
    8 回复  |  直到 15 年前
        1
  •  2
  •   roman    15 年前

    弯腰是最快的!

    我在上面的代码和我在comp上找到的版本上做了一些测试,有关结果和代码,请参见下面的内容:

    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)
    
    
        2
  •  4
  •   Alex Martelli    15 年前

    真正的速度增加将通过移动到麻木或坐骨神经痛。除此之外,还有一些微优化:例如 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)
    

    等等,这些是否都能带来时间优势,都需要微基准。根据你是如何使用这些返回平方的系数,可以节省一个sqrt(这类似于在几何中使用点之间距离的平方,而不是距离本身,并且出于同样的原因——可以节省一个sqrt;这很有意义,因为系数是一个距离,有点…;-)。

        3
  •  2
  •   tonfa    15 年前

    如果可以使用scipy,可以使用皮尔逊函数: 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 只是麻木(代码确实如此 import numpy as np )

        4
  •  1
  •   SilentGhost    15 年前

    我建议改变一下:

    [val for val in v1 if val in v2]
    

    set(v1) & set(v2)
    

    if not n: return 0.0    # and similar for den
    

    而不是

    if n == 0: return 0.0
    

    最后6行替换为:

    try:
        return num / sqrt(abs(temp))
    except ZeroDivisionError:
        return 1.0
    
        5
  •  1
  •   Steven Kryskalla    15 年前

    因为看起来你在做大量的数值计算,你应该 Psyco 一枪它是一个JIT编译器,用于分析运行的代码并优化某些操作。安装它,然后在文件顶部放置:

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

    这将启用psyco的jit,并且应该免费加快代码的速度:(实际上不是,它占用了更多的内存)

        6
  •  0
  •   Chris Judge    15 年前

    如果对任何数学函数的输入都受到相当大的限制,则可以使用查找表而不是数学函数。这可以以存储表所需的额外内存为代价为您赢得一些性能(速度)。

        7
  •  0
  •   Toad    15 年前

    我不确定这是否适用于python。但是计算sqrt是一个处理器密集型计算。

    你可以快速逼近 newton

        8
  •  0
  •   Andrew Ingram    15 年前

    我会把我的答案贴出来,把它和问题区分开来。这是上面描述的一些技术的组合,这些技术似乎提供了迄今为止最好的改进。

    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
    

    编辑:看起来psyco为这个版本提供了15%的改进,虽然不是很大,但足以证明它的使用是合理的。

    推荐文章