Scipy разреженные массивы?

Итак, я делаю некоторую классификацию Kmeans, используя множество довольно редких массивов - много-много нулей. Я подумал, что буду использовать пакет scipy 'sparse', чтобы уменьшить накладные расходы на хранилище, но я немного запутался в том, как создавать массивы, а не матрицы.

Я прошел через это руководство по созданию разреженных матриц: http://www.scipy.org/SciPy_Tutorial#head-c60163f2fd2bab79edd94be43682414f18b90df7

Чтобы имитировать массив, я просто создаю матрицу 1xN, но, как вы можете догадаться, Asp.dot (Bsp) не совсем работает, потому что вы не можете умножить две матрицы 1xN. Мне пришлось бы транспонировать каждый массив в Nx1, и это довольно глупо, поскольку я буду делать это для каждого вычисления скалярного произведения.

Затем я попытался создать матрицу NxN, где столбец 1 == строка 1 (так что вы можете перемножить две матрицы и просто взять верхний левый угол в качестве скалярного произведения), но это оказалось действительно неэффективным.

Я бы хотел использовать sparse package scipy в качестве волшебной замены array () numpy, но пока я не совсем уверен, что делать.

Любой совет?


python numpy scipy matrix sparse-matrix
person spitzanator    schedule 29.03.2010    source источник
comment
См. Комментарии ниже, но в итоге я просто свернул свою собственную реализацию разреженного вектора, используя что-то похожее на матрицу dok.   -  person spitzanator    schedule 30.03.2010
comment
Похоже, что исходная ссылка на вопрос умерла. @spitzanator.   -  person Mark    schedule 26.07.2016

Ответы (3)


arrow_upward
35
arrow_downward

Используйте формат scipy.sparse, основанный на строке или столбце: csc_matrix и csr_matrix.

Они используют эффективные реализации C под капотом (включая умножение), а транспонирование не выполняется (особенно, если вы вызываете transpose(copy=False)), как и с массивами numpy.

РЕДАКТИРОВАТЬ: некоторые тайминги через ipython:

import numpy, scipy.sparse
n = 100000
x = (numpy.random.rand(n) * 2).astype(int).astype(float) # 50% sparse vector
x_csr = scipy.sparse.csr_matrix(x)
x_dok = scipy.sparse.dok_matrix(x.reshape(x_csr.shape))

Теперь x_csr и x_dok разрежены на 50%:

print repr(x_csr)
<1x100000 sparse matrix of type '<type 'numpy.float64'>'
        with 49757 stored elements in Compressed Sparse Row format>

И сроки:

timeit numpy.dot(x, x)
10000 loops, best of 3: 123 us per loop

timeit x_dok * x_dok.T
1 loops, best of 3: 1.73 s per loop

timeit x_csr.multiply(x_csr).sum()
1000 loops, best of 3: 1.64 ms per loop

timeit x_csr * x_csr.T
100 loops, best of 3: 3.62 ms per loop

Похоже, я солгал. Перемещение очень дешево, но нет эффективной реализации csr * csc на языке C (в последней версии scipy 0.9.0). При каждом вызове создается новый объект csr :-(

В качестве взлома (хотя scipy в наши дни относительно стабилен) вы можете выполнить скалярное произведение непосредственно на разреженных данных:

timeit numpy.dot(x_csr.data, x_csr.data)
10000 loops, best of 3: 62.9 us per loop

Обратите внимание, что этот последний подход снова выполняет многократное плотное умножение. Редкость составляет 50%, поэтому на самом деле он быстрее, чем dot(x, x), в 2 раза.

person Radim    schedule 19.07.2011
comment
+1 для простого numpy.dot. Для kmeans вам нужен argmax (точка (k x N центров, каждый Nvec x)); центры в любом случае становятся плотными, так что с таким же успехом можно сохранять их плотными. (Однако усреднение множества редких x для новых центров происходит очень медленно.) - person denis; 23.07.2011
comment
Что ж, если мы отложим в сторону скорость умножения, OP может также использовать _1 _... - person Radim; 24.07.2011
comment
Правдоподобно. Я предпочитаю (advt) этот код, который может использовать любую из 20 с лишним метрик в scipy.spatial.distance; метрика более важна для kmeans с высоким разрешением, чем алгоритм. - person denis; 24.07.2011

arrow_upward
1
arrow_downward

Вы можете создать подкласс одного из существующих двумерных разреженных массивов

from scipy.sparse import dok_matrix

class sparse1d(dok_matrix):
    def __init__(self, v):
        dok_matrix.__init__(self, (v,))
    def dot(self, other):
        return dok_matrix.dot(self, other.transpose())[0,0]

a=sparse1d((1,2,3))
b=sparse1d((4,5,6))
print a.dot(b)
person John La Rooy    schedule 29.03.2010
comment
К сожалению, проблема заключается в том, что вам нужно переносить все опасное на лету, что не имеет большого смысла, когда вы проводите миллионы сравнений. Я пробовал кэшировать точечные продукты, но, к сожалению, мы не очень часто делаем одни и те же точечные продукты, так что это не сильно помогло. - person spitzanator; 30.03.2010

arrow_upward
1
arrow_downward

Я не уверен, что это действительно намного лучше или быстрее, но вы можете сделать это, чтобы избежать транспонирования:

Asp.multiply(Bsp).sum()

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

Однако их, наверное, проще переставить:

Asp*Bsp.T

Кажется, это не так уж и много, но вы также можете создать подкласс и изменить метод mul ().

person Justin Peel    schedule 29.03.2010
comment
Я также пробовал для вектора [1, 2, 3] создать матрицу: [1, 2, 3] [2, 0, 0] [3, 0, 0] Взяв два из них и умножив (в любом порядке ) дает желаемое скалярное произведение в верхнем левом углу матрицы результатов. К сожалению, это сильно сказалось на скорости. - person spitzanator; 30.03.2010