À l'aide d'une matrice creuse rapport à un tableau numpy

Je suis la création de certains des tableaux numpy avec le nombre de mots en Python: les lignes sont les documents, les colonnes sont les chiffres pour le mot X. Si j'ai beaucoup de zéro, les gens suggèrent à l'aide de matrices creuses lors du traitement de ces plus loin, par exemple dans un classificateur. Lors de l'alimentation d'un tableau numpy par rapport à une matrice creuse dans le Scikit régression logistique classificateur, il ne semble pas faire beaucoup de différence, cependant. Donc, je me demandais à propos de trois choses:

  • Wikipédia dit

    d'une matrice creuse est une matrice dans laquelle la plupart des éléments sont nuls

    Est qu'un moyen approprié de déterminer quand utiliser une matrice creuse
    format - dès que > 50 % de la valeur est égale à zéro? Ou faut-il faire
    sens de l'utiliser, juste au cas où?

  • Combien une matrice creuse aider à la performance dans une tâche comme la mienne,
    surtout par rapport à un tableau numpy ou une liste standard?
  • Jusqu'à présent, je collecte mes données dans un tableau numpy, puis de les convertir dans le
    csr_matrix dans Scipy. Est-ce le bon moyen de le faire? Je ne pouvais pas
    comprendre comment construire une matrice creuse de la terre, et que
    peut-être impossible.

Toute aide est très appréciée!

OriginalL'auteur patrick | 2016-05-01

  1. 15

    La scipy sparse matrix paquet, et d'autres semblables dans MATLAB, était basé sur les idées développées à partir de l'algèbre linéaire en problèmes, tels que la résolution de très grands éparses équations linéaires (par exemple, des différences finies et des éléments finis implémentations). Des choses comme la matrice du produit (le dot produit pour les tableaux numpy) et de l'équation de solveurs sont bien développés.

    Mon bruts de l'expérience, c'est que éparse csr de la matrice produit doit avoir un 1% densité à être plus rapide que l'équivalent dense dot opération - en d'autres termes, une valeur différente de zéro pour tous les 99 zéros. (mais voir les tests ci-dessous)

    Mais les gens aussi essayer d'utiliser des matrices creuses pour économiser de la mémoire. Mais gardez à l'esprit qu'une telle matrice a pour stocker les 3 tableaux de valeurs (au moins dans le coo format). Donc, la densité doit être inférieure à 1/3 de commencer à économiser de la mémoire. Évidemment, vous n'allez pas pour économiser de la mémoire, vous devez d'abord construire le tableau dense, et de créer des rares un.

    La scipy paquet met en œuvre de nombreuses éparses formats. Le coo format est plus facile à comprendre et à construire. Construire une fonction documentation et de regarder son .data, .row, et .col attributs (3 tableaux 1d).

    csr et csc sont généralement construits à partir de la coo format, et de compresser les données un peu, ce qui les rend un peu plus difficile à comprendre. Mais ils ont la plupart des mathématiques fonctionnalité.

    Il est également possible de l'indice de csr format, si, en général, c'est plus lent que l'équivalent dense matrix/matrice de cas. D'autres opérations comme l'évolution des valeurs (en particulier de 0 à différente de zéro), la concaténation, les différentiels de croissance, sont aussi plus lents.

    lil (listes de listes) est également facile à comprendre, et le meilleur pour la construction incrémentale. dok est en fait un dictionnaire de la sous-classe.

    Un point-clé est que d'une matrice creuse est limitée à la 2d, et à bien des égards se comporte comme le np.matrix classe (si ce n'est pas une sous-classe).

    Une recherche pour d'autres questions à l'aide de scikit-learn et sparse pourrait être la meilleure façon de trouver les avantages/inconvénients de l'utilisation de ces matrices. J'ai répondu à un certain nombre de questions, mais je sais que les "maigres" côté mieux que le "savoir". Je pense qu'ils sont utiles, mais j'ai l'impression, c'est que l'ajustement n'est pas toujours la meilleure. Toute personnalisation est sur le learn côté. Jusqu'à présent, le sparse colis n'a pas été optimisé pour cette application.

    J'ai juste essayé de la matrice des essais de produits, à l'aide de la sparse.random méthode pour créer une matrice creuse avec une faible densité. Sparse matrix multiplication effectuée mieux que ce que j'attendais. 

    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

    C'est un problème de taille; pour les plus petits de la matrice dense dot est plus rapide

    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

    Mais comparer l'indexation

    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
    Ne sont pas ceux des tests de synchronisation de la conversion???

    OriginalL'auteur hpaulj

  2. 4

    d'une matrice creuse est une matrice dans laquelle la plupart des éléments sont nuls
    Est-ce un moyen approprié de déterminer quand utiliser une matrice creuse format - dès que > 50 % de la valeur est égale à zéro? Ou est-il judicieux d'utiliser juste au cas où?

    Il n'y a pas de règle générale. Il dépend uniquement de votre utilisation précises plus tard. Vous devez calculer la complexité du modèle basé sur des matrices creuses et sans, et puis vous pouvez trouver le "sweet spot". Cela dépendra à la fois du nombre d'échantillons et de la dimension. En général, c'est souvent se résume à de la matrice de multiplication de la forme

    X' W

    où X est la matrice de données x N d, et W est le poids de la matrice d x K. par conséquent, "dense" la multiplication prend NdK temps, bien que rares, en supposant que votre moyenne par ligne faible densité de p est NpdK. Ainsi, si votre densité est de 50%, vous pouvez vous attendre presque 2x plus rapide de l'opération. La partie la plus difficile est d'estimer la surcharge des rares accès par opposition à optimisés dense base.

    Combien une matrice creuse aider à la performance dans une tâche comme la mienne, surtout par rapport à un tableau numpy ou une liste standard?

    Pour un cas particulier de LR, cela peut être même quelques fois plus rapide que dense format, mais dans le but d'observer la différence vous avez besoin de beaucoup de données (>1000) de grande dimension (>100).

    Jusqu'à présent, je collecte mes données dans un tableau numpy, puis de les convertir dans le csr_matrix dans Scipy. Est-ce le bon moyen de le faire? Je ne pouvais pas comprendre comment construire une matrice creuse de la terre, et c'est peut-être impossible.

    Non, il n'est pas une bonne approche. Vous pouvez construire "à partir de zéro", par exemple, d'abord la construction d'un dictionnaire et de le convertir ensuite etc. il ya beaucoup de façons de construire des matrices creuses sans denses, l'un en premier lieu.

    Comme une note ajoutée, la scipy documentation patrick liens de fait a quelques exemples en bas de la façon de construire une matrice creuse à partir de zéro.
    je sais que vous n'êtes pas censé poster "merci" des commentaires, mais c'est une réponse impressionnante & très utile commentaire. merci les gars.

    OriginalL'auteur lejlot

  3. 0

    @hpaulj Votre timeit est faux, u commence à ralentir les résultats de la cause de la cartographie rares.aléatoire d'un tableau numpy (son slowish) avec cela à l'esprit:

    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)

    À se rapprocher de numpy nous avons besoin de nous 

    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)

    OriginalL'auteur komuher