Python: косинусное сходство между двумя большими массивами - PullRequest
Новая
       37

Python: косинусное сходство между двумя большими массивами

0 голосов
/ 27 августа 2018

У меня есть два массива:

Массив 1 : 500 000 строк x 100 столбцов

Массив 2 : 160 000 строк x 100 столбцов

Я хотел бы найти наибольшее косинусное сходство между каждой строкой в ​​массиве 1 и массивом 2 .Другими словами, я вычисляю сходства косинусов между первой строкой в ​​массиве 1 и всеми строками в массиве 2 и нахожу максимальное сходство косинусов, а затем вычисляю сходства косинусов между второй строкой в ​​массиве 1 и всеми строками вМассив 2 и найдите максимальное косинусное сходство;и сделать это для остальной части массива 1.

В настоящее время я использую функцию sklearn cosine_similarity() и делаю следующее, но это очень медленно.Интересно, есть ли более быстрый способ, который не включает многопроцессорность / многопоточность, чтобы выполнить то, что я хочу сделать.Кроме того, массивы, которые я имею, не редки. 

from sklearn.metrics.pairwise import cosine_similarity as cosine

results = []
for i in range(Array1.shape[0]):
     results.append(numpy.max(cosine(Array1[None,i,:], Array2)))

1 Ответ

0 голосов
/ 27 августа 2018

Итерация в Python медленно.Всегда лучше «векторизовать» и максимально использовать numpy-операции над массивами, которые передают работу низкоуровневой реализации numpy, которая является быстрой.

cosine_similarity уже векторизовано.Поэтому идеальное решение будет просто включать cosine_similarity(A, B), где A и B - ваш первый и второй массивы.К сожалению, эта матрица имеет размер 500 000 на 160 000, что слишком много для памяти (она выдает ошибку).

Следующее лучшее решение - это разделить А (по строкам) на большие блоки (вместо отдельных строк).так что результат все еще помещается в память и перебирает их.Я нахожу для ваших данных, что использование 100 строк в каждом блоке помещается в памяти;намного больше, и это не работает.Затем мы просто используем .max и получаем 100 максимумов для каждой итерации, которые мы можем собрать вместе в конце.Формула для косинусного сходства двух векторов равна uv / | u || v | , и это косинус угла между ними.Поскольку мы выполняем итерации, мы продолжаем каждый раз пересчитывать длины строк в B и отбрасывать результат.Хороший способ обойти это - использовать тот факт, что сходство косинусов не меняется, если вы масштабируете векторы (угол одинаков).Таким образом, мы можем вычислить все длины строк только один раз и разделить их, чтобы сделать строки единичными векторами.И затем мы вычисляем косинусное сходство просто как uv , что можно сделать для массивов с помощью умножения матриц.Я быстро проверил это, и это было примерно в 3 раза быстрее.

Собрав все это вместе: 

import numpy as np

# Example data
A = np.random.random([500000, 100])
B = np.random.random([160000, 100])

# There may be a proper numpy method for this function, but it won't be much faster.
def normalise(A):
    lengths = (A**2).sum(axis=1, keepdims=True)**.5
    return A/lengths

A = normalise(A)
B = normalise(B)

results = []

rows_in_slice = 100

slice_start = 0
slice_end = slice_start + rows_in_slice

while slice_end <= A.shape[0]:

    results.append(A[slice_start:slice_end].dot(B.T).max(axis=1))

    slice_start += rows_in_slice
    slice_end = slice_start + rows_in_slice

result = np.concatenate(results)

Это займет у меня около 2 секунд на 1000 строк А для запуска.Таким образом, для ваших данных должно быть около 1000 секунд.

...