Трансляция Numpy/Scipy, вычисляющая скалярное произведение для определенных элементов

Начните с небольшой «разреженной» матрицы (csr лучше всего подходит для математики):

In [167]: A=sparse.csr_matrix([[1, 2, 3],  # Vadim's example
               [2, 1, 4],
               [0, 2, 2],
               [3, 0, 3]])

In [168]: AA=A.A    # dense equivalent  

In [169]: idx=np.array([[1,1,0,3],[3,0,0,2]]).T  # indexes

Я буду придерживаться версии numpy (Pandas построен поверх numpy)

Мы могли бы взять все точечные произведения строк и выбрать подмножество, определяемое idx:

In [170]: (AA.dot(AA.T))[idx[:,0], idx[:,1]]
Out[170]: array([18, 16, 14,  6], dtype=int32)

Произведение разреженной матрицы (A.dot(A.T) также работает:

In [171]: (A*A.T)[idx[:,0], idx[:,1]]
Out[171]: matrix([[18, 16, 14,  6]], dtype=int32)

Или мы можем сначала выбрать строки, а затем взять сумму произведений. Мы не хотим использовать здесь dot, так как мы не берем все комбинации.

In [172]: (AA[idx[:,0]]*AA[idx[:,1]]).sum(axis=1)
Out[172]: array([18, 16, 14,  6], dtype=int32)

Версия einsum этого калькулятора:

In [180]: np.einsum('ij,ij->i',AA[idx[:,0]],AA[idx[:,1]])
Out[180]: array([18, 16, 14,  6], dtype=int32)

sparse может сделать то же самое (* — матричное произведение, .multiply — поэлементное).

In [173]: (A[idx[:,0]].multiply(A[idx[:,1]])).sum(axis=1)
Out[173]: 
matrix([[18],
        [16],
        [14],
        [ 6]], dtype=int32)

С этим маленьким корпусом плотные версии работают быстрее. Индексация разреженных строк выполняется медленно.

In [181]: timeit np.einsum('ij,ij->i', AA[idx[:,0]], AA[idx[:,1]])
100000 loops, best of 3: 18.1 µs per loop

In [182]: timeit (A[idx[:,0]].multiply(A[idx[:,1]])).sum(axis=1)
1000 loops, best of 3: 1.32 ms per loop

In [184]: timeit (AA.dot(AA.T))[idx[:,0], idx[:,1]]
100000 loops, best of 3: 9.62 µs per loop

In [185]: timeit (A*A.T)[idx[:,0], idx[:,1]]
1000 loops, best of 3: 689 µs per loop

Чуть не забыл - итеративные версии:

In [191]: timeit [AA[i].dot(AA[j]) for i,j in idx]
10000 loops, best of 3: 38.4 µs per loop

In [192]: timeit [A[i].multiply(A[j]).sum() for i,j in idx]
100 loops, best of 3: 2.58 ms per loop

Индексация строк матрицы формата lil выполняется быстрее

In [207]: Al=A.tolil()

In [208]: timeit A[idx[:,0]]
1000 loops, best of 3: 476 µs per loop

In [209]: timeit Al[idx[:,0]]
1000 loops, best of 3: 234 µs per loop

Но к тому времени, когда он преобразуется обратно в csr для умножения, это может уже не сэкономить время.

===============

В других недавних вопросах SO я обсуждал более быстрые способы индексации разреженных строк или столбцов. Но в них конечной целью было суммирование по выбранному набору строк или столбцов. Для этого было на самом деле быстрее всего использовать матричное произведение - с матрицей из 1 и 0. Применение этой идеи здесь немного сложнее.

Глядя на функцию индексации csr.__getitem__, я обнаружил, что она на самом деле выполняет индексацию A[idx,:] с матричным произведением. Он создает матрицу extractor с такой функцией:

def extractor(indices,N):
    """Return a sparse matrix P so that P*self implements
    slicing of the form self[[1,2,3],:]
    """
    indptr = np.arange(len(indices)+1, dtype=int)
    data = np.ones(len(indices), dtype=int)
    shape = (len(indices),N)
    return sparse.csr_matrix((data,indices,indptr), shape=shape)

In [328]: %%timeit
   .....: A1=extractor(idx[:,0],4)*A
   .....: A2=extractor(idx[:,1],4)*A
   .....: (A1.multiply(A2)).sum(axis=1)
   .....: 
1000 loops, best of 3: 1.14 ms per loop

На этот раз время немного лучше, чем с A[idx[:,0],:] (In[182] выше) — предположительно потому, что оно немного упрощает действие. Он должен масштабироваться таким же образом.

Это работает, потому что idx0 — это логическая матрица, полученная из [1,1,0,3].

In [330]: extractor(idx[:,0],4).A
Out[330]: 
array([[0, 1, 0, 0],
       [0, 1, 0, 0],
       [1, 0, 0, 0],
       [0, 0, 0, 1]])

In [296]: A[idx[:,0],:].A
Out[296]: 
array([[2, 1, 4],
       [2, 1, 4],
       [1, 2, 3],
       [3, 0, 3]], dtype=int32)

In [331]: (extractor(idx[:,0],4)*A).A
Out[331]: 
array([[2, 1, 4],
       [2, 1, 4],
       [1, 2, 3],
       [3, 0, 3]], dtype=int32)

================

В общем, если проблема слишком велика, чтобы напрямую использовать плотный массив, то лучше всего масштабировать до большого разреженного случая.

(A[idx[:,0]].multiply(A[idx[:,1]])).sum(axis=1)

Если это по-прежнему вызывает ошибки памяти, выполните итерацию, возможно, по группам массива idx (или кадра данных).

Если я правильно понимаю ваш вопрос, вы можете использовать функцию dot в Pandas для вычисления скалярного произведения между двумя сериями:

A['Row1'].dot(A['Row2'])

Документация: http://pandas.pydata.org/pandas-docs/stable/generated/pandas.DataFrame.dot.html

Я думаю, .assign() и .apply() (для панд> 0.16.0) подходят:

import numpy as np
from pandas import DataFrame
from scipy.sparse import bsr_matrix

df = DataFrame(np.random.randint(4, size=(4, 2)), columns=['Row1', 'Row2'])
A = bsr_matrix([[1, 2, 3],
               [2, 1, 4],
               [0, 2, 2],
               [3, 0, 3]])

A = A.tocsr() # Skip this if your matrix is csc_, csr_, dok_ or lil_matrix
df.assign(Value=df.apply(lambda row: A[row[0]].dot(A[row[1]].transpose())[0, 0], axis=1))

Out[15]: 
   Row1  Row2  Value
0     1     3     18
1     1     0     16
2     0     0     14
3     3     2      6