优化 Python 中两个矩阵的直方图距离度量

Question

我有两个矩阵A和B，每个矩阵的大小都是NxM，其中N是样本数，M是直方图箱的大小。因此，每一行代表该特定样本的直方图。

我想做的是计算一对不同样本的两个矩阵之间的 chi-square 距离。因此，矩阵 A 中的每一行都将与另一个矩阵 B 中的所有行进行比较，从而得到大小为 NxN 和 [=22] 的最终矩阵 C =] 对应于 A[i] 和 B[j] 直方图之间的 chi-square 距离。

这是我的 python 代码：

def chi_square(histA,histB):
   esp = 1.e-10
   d = sum((histA-histB)**2/(histA+histB+eps))
   return 0.5*d
def matrix_cost(A,B):
   a,_ = A.shape
   b,_ = B.shape
   C = zeros((a,b))
   for i in xrange(a):
      for j in xrange(b):
         C[i,j] = chi_square(A[i],B[j])
  return C

目前，对于 100x70 矩阵，整个过程需要 0.1 秒。

有什么方法可以提高这种性能吗？

如果有任何想法或建议，我将不胜感激。

谢谢。

Answer 1

好的！我假设您使用的是 numpy?

如果您有可用的 RAM，您可以使用 broadcast 数组并使用 numpy 对这些数组的操作的高效矢量化。

方法如下：

Abroad = A[:,np.newaxis,:]  # prepared for broadcasting
C = np.sum((Abroad - B)**2/(Abroad + B), axis=-1)/2.

与您的算法相比，我的平台上的时间考虑因素显示速度增益为 10 倍。

比前一个选项使用更少 RAM 的较慢选项（但仍然比您的原始算法更快）只是将 A 的行广播到二维数组中：

def new_way(A,B):
    C = np.empty((A.shape[0],B.shape[0]))
    for rowind, row in enumerate(A):
        C[rowind,:] = np.sum((row - B)**2/(row + B), axis=-1)/2.
    return C

这样做的好处是，对于形状 (N,M) 远大于 (100,70) 的数组，它可以是运行。

如果您没有可用内存，您还可以参考 Theano 将昂贵的 for 循环推到 C 级。对于 (100,70) 数组和 (1000,70):

，与第一个选项（不考虑初始编译时间）相比，我获得了 2 倍的速度增益

import theano
import theano.tensor as T
X = T.matrix("X")
Y = T.matrix("Y")
results, updates = theano.scan(lambda x_i: ((x_i - Y)**2/(x_i+Y)).sum(axis=1)/2., sequences=X)
chi_square_norm = theano.function(inputs=[X, Y], outputs=[results])
chi_square_norm(A,B)  # same result

优化 Python 中两个矩阵的直方图距离度量

Optimizing histogram distance metric for two matrices in Python

python

algorithm

optimization

numpy

matrix