IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Réduire la taille d'un vecteur de très grande dimension


Sujet :

Algorithmes et structures de données

  1. #1
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut Réduire la taille d'un vecteur de très grande dimension
    J'aimerai réduire des vecteurs de très grande taille. Il sont creux (taux de remplissage inférieur à 1%).
    Après réduction, il faudrait que les propriétés des vecteurs réduits soient conservées, en particulier leur produit scalaire, leur distance.

    Dans une première approche, je me propose de choisir aléatoirement 1% de valeurs en les additionnant pour faire la première coordonnée du vecteur réduit, puis un deuxième pourcent pour la 2ème coordonnée, etc, jusqu'à avoir pris chacune des coordonnées du vecteur d'entrée 1 fois et 1 seule. Le vecteur ainsi réduit aurait une dimension de 100 et serait le résultat d'une projection "additive". Vu que le vecteur d'entrée est creux, les propriétés devrait être conservées avec une probabilité élevée.

    Qu'en pensez-vous?
    Merci.

  2. #2
    Membre régulier
    Profil pro
    Inscrit en
    Janvier 2003
    Messages
    130
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Janvier 2003
    Messages : 130
    Points : 121
    Points
    121
    Par défaut
    Salut

    essaie de voir si tu peux trouver la faon dont les soft comme MatLab font pour stocker des matrices creuses...

    Ca pourrait etre interessant

    @+

  3. #3
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    Merci, mais mon problème n'est pas dans le stockage. Il est assez facile de stocker des matrices creuses.
    Par ailleurs, ces vecteurs seront comparés à des vecteurs construits qui, eux, ne seront pas creux mais qui auront la même (trop) grande dimension.

    C'est donc à la fois un problème d'espace mémoire et de temps de calcul, les deux étant proportionnels à la taille des vecteurs.
    J'ai donc impérativement besoin de les réduire.

    Si je réduis les vecteurs d'un facteur 100, l'espace mémoire et les temps de calcul sont réduits dans la même proportion.

  4. #4
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Points : 554
    Points
    554
    Par défaut
    On peut stocker
    (0,0,0,0,0,5,0,0,0,0,4,0,0,0,3,0,0)
    comme une liste composée des (indices,valeurs) triée selon les indices:
    (6, 5)->(11,4)->(15,3)

    Avec cette structure, il est facile de programmer l'addition, le produit scalaire, la norme.

  5. #5
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Points : 554
    Points
    554
    Par défaut
    On peut stocker
    (0,0,0,0,0,5,0,0,0,0,4,0,0,0,3,0,0)
    comme une liste composée des (indices,valeurs) triée selon les indices:
    (6, 5)->(11,4)->(15,3)

    Avec cette structure, il est facile de programmer l'addition, le produit scalaire, la norme.

  6. #6
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    Oui, je sais, c'est simple. Mais je l'ai dit, ça ne me suffit pas.
    Il y aura des vecteurs calculés à partir des vecteurs creux qui NE seront PAS creux, mais de même dimension (trop grande).

    Soit deux vecteurs:
    (0,0,0,0,0,5,0,0,0,0,4,0,0,0,3,0,0)
    (1,5,4,2,4,5,3,6,1,2,6,5,4,2,1,3,5)

    En gros j'ai 10.000 à 40.000 vecteurs non creux pour 1.000.000 de vecteurs creux. Je dois comparer chaque vecteur creux avec les non-creux (calcul de dictance). C'est trop long/lent et volumineux avec une dimension qui se compte en milliers, voire dizaine de milliers.
    Je dois réduire ma dimension à quelques centaines tout en conservant (ou "presque") les propriétés de distance des vecteurs entre eux.

    Il y a sûrement des mathématiciens dans la salle
    Une petite aide si'ouplé

  7. #7
    Membre du Club
    Profil pro
    Inscrit en
    Février 2005
    Messages
    69
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2005
    Messages : 69
    Points : 61
    Points
    61
    Par défaut
    Comment tu fais pour obtenir tes vecteurs dans quel espace tu travailles et par consequent quelle formule tu utilises pour ton calcul de distance entre les deux vecteurs

  8. #8
    Expert éminent sénior
    Avatar de Guigui_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2002
    Messages
    1 864
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2002
    Messages : 1 864
    Points : 10 067
    Points
    10 067
    Par défaut
    Est-ce que le fait que tes vecteurs soient creux a une importance ?

    sinon tu peux faire de la décomposition en composante principale (ACP)
    Ca te permettra de réduire ton espace à quelques dimensions (nombre que tu choisis). Tu auras forcément une perte "énergétique" sur tes vecteurs mais plus tu conserveras de dimensions moins elle sera grande.
    C'est une des méthodes que j'utilisais pour comparer des images de visages. J'avais des images 100x100 (donc vecteur de dimension 10000). Je les réduisais par ACP à une dimension 100 et je calculais des distances sur l'espace réduit.

    Par contre, passer à la moulinette la projection d'1000000 vecteurs, ce sera forcément long.

  9. #9
    Membre du Club
    Profil pro
    Inscrit en
    Février 2005
    Messages
    69
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2005
    Messages : 69
    Points : 61
    Points
    61
    Par défaut
    Salut guigui
    je sais pas si l'acp est vraiment une bonne solution parce qu'au depart il faut quand meme qu'il construise ça matrice qui serait de taille 1 040 000 * taille vecteur
    avec quel logiciel tu ferai l'acp???

    parce que pour faire les calculs il vaut mieux avoir du materiel de competition

  10. #10
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    Citation Envoyé par loutente
    Comment tu fais pour obtenir tes vecteurs dans quel espace tu travailles et par consequent quelle formule tu utilises pour ton calcul de distance entre les deux vecteurs
    Calcul de distance:
    sqrt( (a1-b1)² + (a2-b2)² + (a3-b3)² +... +(an-bn)²)

    (a1,a2,a3,... ,an) et (b1,b2,b3,... ,bn) étant deux vecteurs.

    La dimension est n (de l'ordre de dizaines de milliers).

  11. #11
    Expert éminent sénior
    Avatar de Guigui_
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Août 2002
    Messages
    1 864
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Enseignement

    Informations forums :
    Inscription : Août 2002
    Messages : 1 864
    Points : 10 067
    Points
    10 067
    Par défaut
    Citation Envoyé par loutente
    Salut guigui
    je sais pas si l'acp est vraiment une bonne solution parce qu'au depart il faut quand meme qu'il construise ça matrice qui serait de taille 1 040 000 * taille vecteur
    avec quel logiciel tu ferai l'acp???

    parce que pour faire les calculs il vaut mieux avoir du materiel de competition
    pour l'ACP, il a besoin d'une base d'apprentissage mais il est pas obligé de mettre tous ses vecteurs dedans. Après c'est sûr que si ses vecteurs n'ont rien du tout en commun (donc que graphiquement, il ne se projète pas dans une même zone), l'ACP sera inutile.

  12. #12
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    Citation Envoyé par Guigui_
    Est-ce que le fait que tes vecteurs soient creux a une importance ?
    C'est un constat.
    Et sans doute un avantage, car il y a de fortes chances que tous les vecteurs soient "quasi orthogonaux" entre eux.

    Citation Envoyé par Guigui_
    sinon tu peux faire de la décomposition en composante principale (ACP)
    Ca te permettra de réduire ton espace à quelques dimensions (nombre que tu choisis). Tu auras forcément une perte "énergétique" sur tes vecteurs mais plus tu conserveras de dimensions moins elle sera grande.
    C'est une des méthodes que j'utilisais pour comparer des images de visages. J'avais des images 100x100 (donc vecteur de dimension 10000). Je les réduisais par ACP à une dimension 100 et je calculais des distances sur l'espace réduit.
    Là, tu m'interresses. Je pense bien que c'est ce qu'il me faut. Tu m'en dis un peu plus?
    Alors, bien sûr, il y aura une perte ("énergétique" comme tu dis ). Mais justement, comme les vecteurs sont creux, la perte pourrait n'avoir qu'un impact réduit, voire négligeable dans le calcul de distance.

    Citation Envoyé par Guigui_
    Par contre, passer à la moulinette la projection d'1000000 vecteurs, ce sera forcément long.
    Ben oui, c'est bien pour ça que j'ai besoin d'une réduction de la taille des vecteurs. Pour l'instant, j'en suis à 3-4 semaines de calcul (estimation). Si je réduis mes vecteurs d'un facteur 100 par exemple, je n'en ai plus que pour quelques heures.

  13. #13
    Membre éprouvé
    Inscrit en
    Avril 2005
    Messages
    1 110
    Détails du profil
    Informations forums :
    Inscription : Avril 2005
    Messages : 1 110
    Points : 937
    Points
    937
    Par défaut
    L'idée initiale fonctionne: la projection aléatoire d'un espace n vers m avec m<<n.

    ACP et LSI (Latent Semantic Index) sont incalculables vu le nombre et la taille des vecteurs à traiter. De plus, j'ai de nouveaux vecteurs qui viennent s'ajouter avec le temps. Il faut donc une solution qui permette de réduire les vecteurs de manière indépendante.

    Par analogie, mon implémentation correspond à réduire des images de 1000x1000 à 100x100 par exemple. Dans ce cas on obtient un facteur de réduction de 100 et pourtant les images résultantes sont parfaitement reconnaissables.

  14. #14
    Nouveau Candidat au Club
    Femme Profil pro
    Étudiant
    Inscrit en
    Juin 2017
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Âge : 29
    Localisation : France, Seine et Marne (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2017
    Messages : 1
    Points : 1
    Points
    1
    Par défaut
    Citation Envoyé par camboui Voir le message
    L'idée initiale fonctionne: la projection aléatoire d'un espace n vers m avec m<<n.

    ACP et LSI (Latent Semantic Index) sont incalculables vu le nombre et la taille des vecteurs à traiter. De plus, j'ai de nouveaux vecteurs qui viennent s'ajouter avec le temps. Il faut donc une solution qui permette de réduire les vecteurs de manière indépendante.

    Par analogie, mon implémentation correspond à réduire des images de 1000x1000 à 100x100 par exemple. Dans ce cas on obtient un facteur de réduction de 100 et pourtant les images résultantes sont parfaitement reconnaissables.
    Bonjour,
    Finalement, comment avez-vous procédez pour réduire la dimension des vecteurs car je rencontre ce même genre de problème. Je comptais faire une analyse par composante principale avant de voir vos messages...

    Merci

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 1
    Dernier message: 15/09/2005, 23h47
  2. [Oracle 8i] réduire la taille d'une base de test
    Par delphim dans le forum Oracle
    Réponses: 2
    Dernier message: 04/07/2005, 12h59
  3. Réduire la taille des fichier .LDF ?
    Par webtheque dans le forum MS SQL Server
    Réponses: 12
    Dernier message: 31/03/2005, 12h48
  4. [GCC] Réduire la taille d'un programme statique
    Par Geronimo dans le forum Autres éditeurs
    Réponses: 3
    Dernier message: 05/03/2004, 17h34
  5. réduire la taille d'un datafile
    Par delphim dans le forum Administration
    Réponses: 30
    Dernier message: 20/02/2004, 17h25

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo