numpy 有效加权Jaccard距离

vkc1a9a2  于 2023-10-19  发布在  其他
关注(0)|答案(1)|浏览(113)

我试图找到一个~8000*8000 pandas df矩阵中每对行的加权jaccard距离。我尝试了以下方法:

import pandas as pd
import numpy as np

def weighted_j_sim(array1, array2):
    return np.minimum(array1, array2).sum()/np.maximum(array1, array2).sum()

matrix = pd.DataFrame([[1, 2 ,3],
                       [2, 1, 1],
                       [3, 1, 1]])

for index, (name, values) in enumerate(matrix.iterrows()):
    for other_index, (other_name, other_values) in enumerate(matrix.iterrows()):
        if other_index>index: #dont check self or something already compared
            weighted_js = weighted_j_sim(values, 
                                         other_values)

import pandas as pd
import numpy as np
            
def weighted_j_sim(array1, array2):
    #https://stackoverflow.com/a/71276180/11357695
    q = np.concatenate((array1.T, array2.T), axis=1)
    return np.sum(np.amin(q,axis=1))/np.sum(np.amax(q,axis=1))

matrix = pd.DataFrame([[1, 2 ,3],
                       [2, 1, 1],
                       [3, 1, 1]])
    
for index, (name, values) in enumerate(matrix.iterrows()):
    for other_index, (other_name, other_values) in enumerate(matrix.iterrows()):
        if other_index>index: #dont check self or something already compared
            weighted_jd = weighted_j_sim(np.array([values.values]), 
                                         np.array([other_values.values]))

这是非常缓慢的-任何人都可以建议一些 numpy 魔术应用在这里?

ldxq2e6h

ldxq2e6h1#

一个很大的性能问题是代码在Pandas系列对象上执行二次运行时算法,这通常比Numpy数组慢得多。另一个问题是,将同一行多次转换为Numpy数组效率不高。此外,创建多次临时Numpy数组有点昂贵。此外,如果阵列很大,则在同一个阵列中同时运行最小值和最大值可能会效率低下,因为需要将其重新加载到L1缓存。

实现更快

首先要做的是将pandas数组转换为一个连续的Numpy数组。然后,我们可以使用基于编译器的工具,如Numba和Cython,以避免创建许多临时数组并更有效地使用缓存。此外,我们还可以通过在正确的索引处启动第二个循环来轻松删除条件。最重要的是,可以使用多线程(假设weighted_js的计算是线程安全的)。
下面是一个非常快速的Numba实现:

import numba as nb
import numpy as np
import pandas as pd

matrix = pd.DataFrame(np.random.rand(1000, 1000))

# Designed for 64-bit float -- please change the type if you want another kind of matrix
@nb.njit('float64(float64[:,::1],)', fastmath=True, parallel=True)
def compute_fast(matrix):
    checksum = 0

    for i in nb.prange(matrix.shape[0]):
        for j in range(i+1, matrix.shape[0]):
            sum1 = 0.0
            sum2 = 0.0
            arr1 = matrix[i]
            arr2 = matrix[j]

            for k in range(matrix.shape[1]):
                a = arr1[k]
                b = arr2[k]
                sum1 += min(a, b)
                sum2 += max(a, b)

            weighted_js = sum1 / sum2

            # Required for Numba not to optimize out the whole loop 
            # (otherwise weighted_js would be unused and the wholeloop useless).
            checksum += weighted_js

    return checksum

compute_fast(np.ascontiguousarray(matrix.to_numpy()))

性能结果

下面是我的i5- 9600 KF处理器在1000 x1000的架构上的性能:

First code of the question:       166.3 seconds
This optimized implementation:      0.1 second

因此,Numba实现比问题中提供的(第一个)实现快**~1660倍**。它能够在65秒内(而不是几十个小时)计算8000 x8000的矩阵。

注意事项及性能提升

请注意,fastmath只应在输入没有任何特殊值(如NaN、Inf或subnormals)时使用。它也只有在sum2永远不为0时才是安全的(因为被零除)。
请注意,这可以进一步优化。一种方法是使用 * 循环平铺 *,以便更好地使用CPU缓存。如果算法在目标机器上是内存受限的(在我的机器上就是这种情况),这会快得多。另一种方法是在线程之间进行负载平衡。这将使计算速度提高 * 两倍 *。另一个优化包括使用 *SIMD指令 *。这似乎不可能与Numba(至少不容易也不有效)。您需要使用母语(例如:C/C++)来执行这样的优化。这将使计算速度在大多数机器上快4倍。这两种优化可以结合在一起,使计算速度提高8倍。生成的程序应该能够在 * 最佳时间 * 内计算Jaccard距离(假设需要计算所有距离)。
请注意,使用 * 简单精度 *(以及更一般的小类型)可以使计算速度提高两倍(因此,使用之前的优化可以提高16倍)。

相关问题