En scipy, podemos construir una matriz dispersa utilizando scipy.dispersas.lil_matrix (), etc. Pero la matriz es en 2d.

Me pregunto si hay una estructura de datos existente para las 3d de la matriz /array (tensor) en Python?

p.s. Tengo un montón de datos dispersos en 3d y la necesidad de un tensor a la tienda /realizar la multiplicación. Cualquier sugerencias para implementar un tensor si no hay ninguna estructura de datos existentes?

  • este post puede ayudar a stackoverflow.com/questions/4490961/…
  • …pero no disperso, por desgracia.
  • ¿Qué significa una «matriz en 2D»? Si te refieres a una matriz que representa un 2D transformación lineal, entonces estamos hablando de una matriz 2×2 de valores Reales (aproximados por los valores de punto flotante) con determinante 1 para una rotación rígida. Si usted desea representar traducción y, a continuación, se incorpora la matriz de 2×2 en el interior de una matriz de 3×3, y si desea permitir el corte o la expansión/contracción, a continuación, usted puede relajar el requisito determinante -pero aun así eso es un total de 9 valores de punto flotante. ¿Por qué quiere/necesita una escasa representación?
  • matriz en 2D» significa una matriz de dimensión 2. Una unidad en una matriz 2d puede ser representado como (x,y, r), donde x & y son las coordenadas y r es el valor almacenado en (x, y). Necesito una escasa representación, porque cuando x & y son muy muy grandes, digamos x<10^5, y < 10^4, Y sólo muy pocos datos se almacenan en la matriz, digamos 10^4. numpy proporciona la matriz dispersa de la matriz 2d. Pero muy a menudo, necesitamos 3d o incluso n-d. Supongo que n-d caso es demasiado general. De manera que cualquier solución a 3d son lo suficientemente bueno para mí.
  • Gracias – estaba confundido por el P. S. en su pregunta (me sonó como que usted quería multiplicar un montón de Euclídea tuplas por una matriz álgebra lineal estilo). Pero si vamos a hablar de m x n x o matrices suena como su «escasa» la aplicación va a necesitar para proporcionar algún tipo de iterador de la interfaz para poder implementar (elemento por elemento) de la multiplicación.
InformationsquelleAutor zhongqi | 2011-10-07

4 Comentarios

  1. 14

    Feliz sugerir un (posiblemente obvio) implementación de este, que podría ser hecho en Python puro o C/Cython si tienes el tiempo y el espacio para las nuevas dependencias, y necesita que sea más rápido.

    Una matriz dispersa en N dimensiones puede asumir que la mayoría de los elementos están vacías, por lo que utilizar un diccionario clave en tuplas:

    class NDSparseMatrix:
      def __init__(self):
        self.elements = {}
    
      def addValue(self, tuple, value):
        self.elements[tuple] = value
    
      def readValue(self, tuple):
        try:
          value = self.elements[tuple]
        except KeyError:
          # could also be 0.0 if using floats...
          value = 0
        return value

    y se usaría así:

    sparse = NDSparseMatrix()
    sparse.addValue((1,2,3), 15.7)
    should_be_zero = sparse.readValue((1,5,13))

    Usted puede hacer la aplicación más robusta al comprobar que la entrada es de hecho una tupla, y que contiene sólo números enteros, pero que se acaba de retrasar las cosas, así que no te preocupes a menos que usted está liberando su código para el mundo más tarde.

    EDITAR – un Cython aplicación de la multiplicación de la matriz del problema, suponiendo que otras tensor es un N Dimensional NumPy array (numpy.ndarray) podría tener este aspecto:

    #cython: boundscheck=False
    #cython: wraparound=False
    
    cimport numpy as np
    
    def sparse_mult(object sparse, np.ndarray[double, ndim=3] u):
      cdef unsigned int i, j, k
    
      out = np.ndarray(shape=(u.shape[0],u.shape[1],u.shape[2]), dtype=double)
    
      for i in xrange(1,u.shape[0]-1):
        for j in xrange(1, u.shape[1]-1):
          for k in xrange(1, u.shape[2]-1):
            # note, here you must define your own rank-3 multiplication rule, which
            # is, in general, nontrivial, especially if LxMxN tensor...
    
            # loop over a dummy variable (or two) and perform some summation:
            out[i,j,k] = u[i,j,k] * sparse((i,j,k))
    
      return out

    Aunque usted necesitará siempre a mano el rollo este de que el problema a la mano, porque (como se menciona en el comentario del código) tendrá que definir qué índices se están sumando más, y tenga cuidado con la matriz de longitudes o las cosas no funcionan!

    EDITAR 2 – si la otra matriz es también escasa, entonces usted no necesita hacer las tres forma de bucle:

    def sparse_mult(sparse, other_sparse):
    
      out = NDSparseMatrix()
    
      for key, value in sparse.elements.items():
        i, j, k = key
        # note, here you must define your own rank-3 multiplication rule, which
        # is, in general, nontrivial, especially if LxMxN tensor...
    
        # loop over a dummy variable (or two) and perform some summation 
        # (example indices shown):
        out.addValue(key) = out.readValue(key) + 
          other_sparse.readValue((i,j,k+1)) * sparse((i-3,j,k))
    
      return out

    Mi sugerencia para una implementación en C sería el uso de una simple estructura para mantener los índices y los valores:

    typedef struct {
      int index[3];
      float value;
    } entry_t;

    necesitarás algunas funciones para asignar y mantener una matriz dinámica de tales estructuras, y la búsqueda de ellos tan rápido como usted necesita; pero debe probar la implementación de Python en lugar de rendimiento antes de preocuparse de esas cosas.

    • El problema es el de las operaciones matemáticas, no el contenedor de datos… nunca he oído hablar de algoritmos para el uso eficiente de los escasos N-d tensor de productos. Echa un vistazo scipy.sparse.dok_matrix. Es lo que usted está describiendo aquí, sólo se limita a 2D. Es bastante fácil de extender a celebrar N-D datos, pero ¿cómo se puede operar en los datos?? (Dicho esto, su respuesta es totalmente razonable…)
    • ah, yo lo he entendido mal? así que esta pregunta está pidiendo más información sobre la aplicación de un scipy compatible con la multiplicación de la matriz de la operación? Esto debería ser relativamente fácil de implementar, sin duda, ya que todo lo que realmente necesita para que es un bucle de consulta para el valor en un índice, que me ha proporcionado. Voy a echar un vistazo a la scipy especificaciones sin embargo.
    • Así, podría decirse que, yo lo he entendido mal como bien. De cualquier manera, mi punto era que usted no está tomando ventaja de la dispersión de la estructura de al realizar operaciones. Lo que he descrito en su edición trata como un conjunto denso. (Que ciertamente funciona! Su respuesta resuelve el problema a la mano.) La matriz dispersa bibliotecas de tomar ventaja de la escasa-dad de la matriz, y evitar cosas como un bucle por cada elemento de la matriz, independientemente de la «dispersión». Ese es el punto principal de la utilización de una matriz dispersa. Las operaciones de aproximadamente escala con el número de «densa» de los elementos, no las dimensiones de la matriz.
    • Gracias por la respuesta. Pero me temo que la multiplicación con su sugirió estructura de datos puede no ser muy eficiente…
    • Usted tendría un bucle en cada elemento de la no-matriz dispersa (u en este caso) de todos modos, seguramente? A menos que ambas son escasos, en cuyo caso yo lo he entendido mal, incluso más. En ese caso, usted puede simplemente recorrer las llaves en el diccionario, y extraer los índices de la tupla. De todos modos, no estoy a la velocidad de escasa álgebra, dejar solo al equipo de la ciencia detrás de la optimización de los algoritmos sobre el tema. Lo siento, @zhongqi !
    • «A menos que ambas son escasos» <– Esa es la idea! 🙂 Lo siento, no era más claro. Me refería a las operaciones entre dos matrices dispersas. (Que es generalmente el caso, cuando usted está tratando con una situación donde el uso de matrices es una buena solución). Multiplicaciones entre dos matrices dispersas más común es el de caso de uso para una matriz dispersa de la biblioteca, así que hay una gran cantidad de esfuerzo puesto en la optimización de esa situación en particular. La implementación de un eficiente escasa tensordot (es decir, la multiplicación por N-D) es trivial. Sin embargo, nuevamente, la solución es bien. (+1) no Es práctico para grandes, matrices dispersas, aunque
    • edición 2 de mayo de ayuda, pero no estoy seguro. En algún momento, tendrá que lidiar con los datos que hay, aunque, lo que significa un bucle por su ficticia de los índices de…

  2. 4

    Una respuesta alternativa como la de este año es el dispersas paquete. Según el propio paquete implementa escasa matrices multidimensionales en la parte superior de NumPy y scipy.sparse por la generalización de la scipy.sparse.coo_matrix diseño.

    He aquí un ejemplo tomado de la documentación:

    import numpy as np
    n = 1000
    ndims = 4
    nnz = 1000000
    coords = np.random.randint(0, n - 1, size=(ndims, nnz))
    data = np.random.random(nnz)
    
    import sparse
    x = sparse.COO(coords, data, shape=((n,) * ndims))
    x
    # <COO: shape=(1000, 1000, 1000, 1000), dtype=float64, nnz=1000000>
    
    x.nbytes
    # 16000000
    
    y = sparse.tensordot(x, x, axes=((3, 0), (1, 2)))
    
    y
    # <COO: shape=(1000, 1000, 1000, 1000), dtype=float64, nnz=1001588>
    • Esto es compatible con sklearn.some_model.ajuste()?
    • Tal vez, pero para ser honesto, creo que tendrías que probarlo.
    • Recomiendo escribir «a partir de 2017» en lugar de «a partir de este año»
  3. 3

    Mejor que escribir todo de nuevo desde cero puede ser la utilización de scipy escasa módulo medida de lo posible. Esto puede conducir a la (el) mejor rendimiento. Tuve un poco de problema similar, pero yo sólo tenía que tener acceso a los datos de manera eficiente, no realizar operaciones en ellos. Además, mis datos sólo estaban dispersas en dos de las tres dimensiones.

    He escrito una clase que soluciona mi problema y podría (como yo creo) ser fácilmente extendido a satisfiy el OP necesidades. Es posible que todavía se mantienen algunas potencial de mejora.

    import scipy.sparse as sp
    import numpy as np
    class Sparse3D():
    """
    Class to store and access 3 dimensional sparse matrices efficiently
    """
    def __init__(self, *sparseMatrices):
    """
    Constructor
    Takes a stack of sparse 2D matrices with the same dimensions
    """
    self.data = sp.vstack(sparseMatrices, "dok")
    self.shape = (len(sparseMatrices), *sparseMatrices[0].shape)
    self._dim1_jump = np.arange(0, self.shape[1]*self.shape[0], self.shape[1])
    self._dim1 = np.arange(self.shape[0])
    self._dim2 = np.arange(self.shape[1])
    def __getitem__(self, pos):
    if not type(pos) == tuple:
    if not hasattr(pos, "__iter__") and not type(pos) == slice: 
    return self.data[self._dim1_jump[pos] + self._dim2]
    else:
    return Sparse3D(*(self[self._dim1[i]] for i in self._dim1[pos]))
    elif len(pos) > 3:
    raise IndexError("too many indices for array")
    else:
    if (not hasattr(pos[0], "__iter__") and not type(pos[0]) == slice or
    not hasattr(pos[1], "__iter__") and not type(pos[1]) == slice):
    if len(pos) == 2:
    result = self.data[self._dim1_jump[pos[0]] + self._dim2[pos[1]]]
    else:
    result = self.data[self._dim1_jump[pos[0]] + self._dim2[pos[1]], pos[2]].T
    if hasattr(pos[2], "__iter__") or type(pos[2]) == slice:
    result = result.T
    return result
    else:
    if len(pos) == 2:
    return Sparse3D(*(self[i, self._dim2[pos[1]]] for i in self._dim1[pos[0]]))
    else:
    if not hasattr(pos[2], "__iter__") and not type(pos[2]) == slice:
    return sp.vstack([self[self._dim1[pos[0]], i, pos[2]]
    for i in self._dim2[pos[1]]]).T
    else:
    return Sparse3D(*(self[i, self._dim2[pos[1]], pos[2]] 
    for i in self._dim1[pos[0]]))
    def toarray(self):
    return np.array([self[i].toarray() for i in range(self.shape[0])])
    • Yo estoy en la misma situación y esto es muy útil. Yo creo que con un poco de trabajo extra que esto podría ser implementado en scipy‘s de la matriz dispersa módulo. Has considerado?
    • Gracias! No he considerado la implementación de este en scipy escasa módulo. Creo que una implementación en scipy debe apoyar a todos los estándar de numpy características de la matriz. Que sería factible, pero requiere un pedazo decente de trabajo. También, creo que la adición de C implementaciones para las operaciones en estas matrices sería mucho más eficiente y más adecuado para la scipy.

Dejar respuesta

Please enter your comment!
Please enter your name here