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

Question

我有两个矩阵A和B，每个矩阵的大小都是NxM，其中{}是样本数，M是柱状图单元的大小。因此，每一行代表一个特定样本的直方图。在

我想做的是计算不同样本对的两个矩阵之间的chi-square距离。因此，矩阵A中的每一行都将与另一个矩阵B中的所有行进行比较，最终得到一个大小为NxN且C[i,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的行广播到2D数组中：

^{pr2}$

对于这个（70，M）的数组比它的形状大得多。在

如果没有可用内存，也可以使用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