Эффективно вычислить попарно подобие Жакара из разреженного массива

Question

У меня есть массив, подобный следующему, с каждой строкой, являющейся наблюдением, и каждым столбцом, являющимся объектом:

import scipy
my_sparse_array = scipy.sparse.random(2000, 10000000, density=0.01, format='csr')

Для каждой пары наблюдений (строк) я хочу вычислить сходство по Джакарту междуих - учитывая, что ненулевое значение в массиве означает, что функция присутствует, а нулевые значения указывают на отсутствие функции.Следовательно, пересечение будет в том случае, когда оба наблюдения имеют ненулевое значение для объекта, а объединение - в том случае, если только одно из наблюдений имеет ненулевое значение.Функции, в которых оба значения равны нулю, следует игнорировать.

Какой наиболее эффективный способ выполнения этого парного вычисления.Мой план состоял в том, чтобы сделать комбинации всех пар 0 - 1999, поднастроить две строки, удалить все столбцы с ненулевыми столбцами, а затем вычислить, но это кажется ужасно неэффективным, так как для этого требуется тонна соединений.

Желаемый результат - матрица 2000 x 2000 с индексом Жакара.Бонусом будет сделать промежуточный массив из 4 столбцов с индексом наблюдения 1, индексом наблюдения 2, пересечением и объединением.

Спасибо!Jack

Answer 1

Если быть точным, он должен учитываться в объединении, если хотя бы одна из записей отлична от нуля.

Независимо от того, что вам придется делать O (n ^ 2) сравнений.В частности, существует n (n-1) / 2 возможных пар.Так что любые ускорения будут исходить из самих сравнений.

Кажется, что значение записей не имеет значения для вашего определения, поэтому все будет быстрее, если вы приведете к логическим значениям.Предположим, X=my_sparse_array.astype('bool)' - это ваш разреженный логический массив размера (2000, 10000000).Вы можете вычислить пересечение и объединение между строками i и j следующим образом:

intersection = scipy.sum(X[i].multiply(X[j]))
union = scipy.sum(X[i]+X[j])

Функция умножения действует поточечно, поэтому k -ая запись X[i].multiply(X[j]) равна 1, если обаk -й элементы X[i] и X[j] равны единице, в противном случае - нулюПоэтому он действует как логика и операция.Аналогично, + действует как логическая операция или операция.Сумма просто дает число ненулевых записей в строке.