Использование разреженной матрицы против массива numpy

Ответ 1

Редкий матричный пакет scipy и подобные в MATLAB были основаны на идеях, разработанных из задач линейной алгебры, таких как решение больших разреженных линейных уравнений (например, конечных разностных и конечных элементов). Так что вещи, подобные матричному продукту (продукт dot для массивов numpy) и решатели уравнений хорошо разработаны.

Мой грубый опыт заключается в том, что разреженный матричный продукт csr должен иметь 1% -ную разреженность быстрее, чем эквивалентная плотная операция dot - другими словами, одно ненулевое значение для каждых 99 нулей. (но см. тесты ниже)

Но люди также пытаются использовать разреженные матрицы для экономии памяти. Но имейте в виду, что такая матрица должна хранить 3 массива значений (по крайней мере, в формате coo). Таким образом, разреженность должна быть меньше 1/3, чтобы начать экономить память. Очевидно, что вы не собираетесь сохранять память, если сначала создаете плотный массив и создаете разреженный из них.

Пакет scipy реализует множество разреженных форматов. Формат coo проще всего понять и построить. Постройте по документации и посмотрите на ее атрибуты .data, .row и .col (3 1d массивы).

csr и csc обычно строятся из формата coo и немного сжимают данные, что делает их более трудными для понимания. Но у них большая часть математической функциональности.

Также возможно индексировать формат csr, хотя в целом это медленнее, чем эквивалентный плотный матричный/массивный случай. Другие операции, такие как изменение значений (особенно от 0 до отличных от нуля), конкатенация, прирост роста, также медленнее.

lil (списки списков) также легко понять и лучше всего подходит для инкрементного построения. dok - фактически словарь-подкласс.

Ключевым моментом является то, что разреженная матрица ограничена 2d и во многом ведет себя как класс np.matrix (хотя это не подкласс).

Поиск других вопросов с использованием scikit-learn и sparse может быть лучшим способом найти плюсы и минусы использования этих матриц. Я ответил на несколько вопросов, но я знаю "редкую" сторону лучше, чем "учиться". Я думаю, что они полезны, но я понимаю, что подгонка не всегда лучшая. Любая настройка находится на стороне learn. Пока пакет sparse не оптимизирован для этого приложения.

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

In [251]: M=sparse.random(1000,1000,.5)

In [252]: timeit M1=M*M
1 loops, best of 3: 2.78 s per loop

In [253]: timeit Ma=M.toarray(); M2=Ma.dot(Ma)
1 loops, best of 3: 4.28 s per loop

Это проблема размера; для меньшей матрицы плотная dot быстрее

In [255]: M=sparse.random(100,100,.5)

In [256]: timeit M1=M*M
100 loops, best of 3: 3.24 ms per loop

In [257]: timeit Ma=M.toarray(); M2=Ma.dot(Ma)
1000 loops, best of 3: 1.44 ms per loop

Но сравните индексирование

In [268]: timeit M.tocsr()[500,500]
10 loops, best of 3: 86.4 ms per loop

In [269]: timeit Ma[500,500]
1000000 loops, best of 3: 318 ns per loop

In [270]: timeit Ma=M.toarray();Ma[500,500]
10 loops, best of 3: 23.6 ms per loop

Ответ 2

разреженная матрица - это матрица, в которой большая часть элементов равна нулю Это подходящий способ определить, когда использовать разреженный формат матрицы - как только > 50% значений равны нулю? Или имеет смысл использовать на всякий случай?

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

X' W

где X - матрица данных N x d, а W - некоторая весовая матрица d x K. Следовательно, "плотное" умножение принимает время NdK, хотя и разреженное, считая, что ваша средняя разрешающая строка равна p NpdK. Таким образом, если ваша разреженность составляет 50%, вы можете ожидать почти в 2 раза быстрее работы. Более сложная задача - оценить накладные расходы на разреженный доступ, а не на сильно оптимизированную плотность.

Сколько разреженной матрицы помогает производительность в задаче вроде моей, особенно по сравнению с массивом numpy или стандартным списком?

Для конкретного случая LR это может быть в несколько раз быстрее плотного формата, но для того, чтобы наблюдать разницу, вам нужно много данных ( > 1000) с высоким размером ( > 100).

Пока я собираю свои данные в массив numpy, а затем конвертирую в csr_matrix в Scipy. Это правильный способ сделать это? Я не мог понять, как построить разреженную матрицу с нуля, и это может быть невозможно.

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

Ответ 3

@hpaulj Ваше время неверно, вы получаете медленные результаты, приводящие к отображению sparse.random в массив numpy (он медленный), помня об этом:

M=sparse.random(1000,1000,.5)
Ma=M.toarray()

%timeit -n 25 M1=M*M
352 ms ± 1.18 ms per loop (mean ± std. dev. of 7 runs, 25 loops each)

%timeit -n 25 M2=Ma.dot(Ma)
13.5 ms ± 2.17 ms per loop (mean ± std. dev. of 7 runs, 25 loops each)

Чтобы приблизиться к numpy, нам нужно иметь

M=sparse.random(1000,1000,.03)

%timeit -n 25 M1=M*M
10.7 ms ± 119 µs per loop (mean ± std. dev. of 7 runs, 25 loops each)

%timeit -n 25 M2=Ma.dot(Ma)
11.4 ms ± 564 µs per loop (mean ± std. dev. of 7 runs, 25 loops each)