python - Scipy sparse... matrices?

sp matrix python

Question

Entonces, estoy haciendo una clasificación de Kmeans usando matrices numpy que son bastante dispersas, montones y montones de ceros. Pensé que usaría el paquete ''disperso'' de scipy para reducir la sobrecarga de almacenamiento, pero estoy un poco confundido acerca de cómo crear matrices, no matrices.

He pasado por este tutorial sobre cómo crear matrices dispersas: http://www.scipy.org/SciPy_Tutorial#head-c60163f2fd2bab79edd94be43682414f18b90df7

Para imitar una matriz, solo creo una matriz 1xN, pero como puedes adivinar, Asp.dot (Bsp) no funciona porque no puedes multiplicar dos matrices 1xN. Tendría que transponer cada arreglo a Nx1, y eso es bastante cojo, ya que lo haría por cada cálculo de producto de punto.

A continuación, traté de crear una matriz NxN donde la columna 1 == fila 1 (de forma que se puedan multiplicar dos matrices y simplemente tomar la esquina superior izquierda como el producto escalar), pero resultó ser muy ineficiente.

Me encantaría usar el escaso paquete de scipy como un reemplazo mágico para numpy''s array (), pero aún no estoy seguro de qué hacer.

¿Algún consejo?

Answer 1

No estoy seguro de que sea mucho mejor o más rápido, pero puedes hacer esto para evitar el uso de la transposición:

Asp.multiply(Bsp).sum()

Esto solo toma el elemento elemento por elemento de las dos matrices y suma los productos. Podría hacer una subclase de cualquier formato de matriz que esté utilizando que tenga la declaración anterior como producto de puntos.

Sin embargo, probablemente solo sea más fácil transponerlos:

Asp*Bsp.T

Eso no parece mucho que hacer, pero también podría hacer una subclase y modificar el método mul ().

Answer 2

Podría crear una subclase de una de las 2d dispersas matrices existentes

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)

Answer 3

Utilice un formato scipy.sparse basado en filas o columnas: csc_matrix y csr_matrix .

Estos usan implementaciones C eficientes bajo el capó (incluida la multiplicación), y la transposición es no operativa (especialmente si se llama transpose(copy=False) ), al igual que con las matrices numpy.

EDITAR: algunos tiempos a través de 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))

Ahora x_csr y x_dok son 50% escasos:

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

Y los tiempos:

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

Entonces parece que dije una mentira. La transposición es muy barata, pero no hay una implementación C eficiente de csr * csc (en el último scipy 0.9.0). Se construye un nuevo objeto csr en cada llamada :-(

Como un hack (aunque scipy es relativamente estable en estos días), puedes hacer el producto de puntos directamente en los escasos datos:

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

Tenga en cuenta que este último enfoque hace una multiplicación nude denso de nuevo. La dispersión es del 50%, por lo que en realidad es más rápido que el dot(x, x) por un factor de 2.