2

我已经实现了 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
4

8 回答 8

4

真正的速度提升将通过转向 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)

等等; 这些中的每一个是否带来时间优势都需要进行微基准测试。根据您使用这些系数的方式，返回平方将为您节省一个 sqrt（这与在几何中使用点之间的距离平方而不是距离本身类似的想法，并且出于同样的原因 - 为您节省一个 sqrt ; 这是有道理的，因为系数是一个距离，有点......;-)。

于 2009-08-20T15:57:29.517 回答
2

如果你可以使用 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）。

于 2009-08-21T19:19:26.543 回答
2

Scipy 是最快的！

我对上面的代码以及在我的 comp 中找到的版本进行了一些测试，结果和代码见下文：

皮尔逊 14.7597990757
sim_pearson 15.6806837987
scipy:pearsonr 0.451986019188


尝试：
    导入 psyco
    psyco.full()
导入错误除外：
    经过

从数学导入 sqrt

def sim_pearson(set1, set2):
    si={}
    对于 set1 中的项目：
        如果 set2 中的项目：
            si[项目] = 1

    #元素个数
    n = 长度 (si)

    #如果没有共同点，返回0相似度
    如果 n == 0：返回 0

    #把所有的偏好加起来
    sum1 = sum([set1[item] for item in si])
    sum2 = sum([set2[item] for item in si])

    #对正方形求和
    sum_sq1 = sum([pow(set1[item], 2) for item in si])
    sum_sq2 = sum([pow(set2[item], 2) for item in si])

    #总结产品
    sum_p = sum([set1[item] * set2[item] for item in si])

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

    如果 den==0：返回 0
    返回名义/登



# 来自 http://stackoverflow.com/questions/1307016/pearson-similarity-score-how-can-i-optimise-this-further
定义皮尔逊（v1，v2）：
    vs = [(v1[val],v2[val]) for val in v1 if val in v2]

    n = 长度 (vs)

    如果 n==0：返回 0.0

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

    对于 v1,v2 在 vs 中：
        和1+=v1
        sum2+=v2
        sum1_sq+=v1*v1
        sum2_sq+=v2*v2
        p_sum+=v1*v2

    # 计算皮尔逊分数
    num = p_sum-(sum1*sum2/n)
    temp = max((sum1_sq-pow(sum1,2)/n) * (sum2_sq-pow(sum2,2)/n),0)
    如果温度：
        返回 num / sqrt(temp)
    返回 1.0






如果 __name__ == "__main__":
    导入时间

    tsetup = """
从随机导入 randrange
从 __main__ 进口皮尔逊，sim_pearson
从 scipy.stats 导入 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

    打印“皮尔逊”，t1.timeit(tt)
    打印“sim_pearson”，t2.timeit(tt)
    打印 'scipy:pearsonr', t3.timeit(tt)
于 2010-02-17T12:22:13.120 回答
1

我建议改变：

[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
于 2009-08-20T16:08:11.977 回答
1

由于看起来您正在进行大量的数值计算，因此您应该给Psyco一个机会。它是一个 JIT 编译器，可以分析正在运行的代码并优化某些操作。安装它，然后在文件顶部放置：

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

这将启用 Psyco 的 JIT，并且应该会在一定程度上加速您的代码，免费 :)（实际上不是，它会占用更多内存）

于 2009-08-21T03:24:43.250 回答
0

如果您的任何数学函数的输入受到相当大的限制，您可以使用查找表而不是数学函数。这可以以额外的内存来存储表为您赢得一些性能（速度）。

于 2009-08-20T15:47:28.897 回答
0

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

您可能会寻求快速近似牛顿

于 2009-08-20T15:49:11.733 回答
0

我将发布到目前为止的答案，以将其与问题区分开来。这是上面描述的一些技术的组合，这些技术似乎已经给出了迄今为止最好的改进。

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% 的改进，虽然不是很大，但足以证明它的使用是合理的。

于 2009-08-21T14:23:36.117 回答