Matrice symétrique et représentation graphique

[invite9a322bed]

Bonjour à tous !

Cela fait bien longtemps que je n'ai pas posté sur ce forum, et que je n'ai pas fait de mathématiques (je suis rouillé ! déjà ! et oui!). Pour un projet personnel, j'ai envie de trouver une ou plusieurs représentations graphiques 2D et 3D pour une matrice symétrique de dimension n avec que des éléments nuls en diagonale, les autres éléments sont entre 0 et 1. Il est évident que ce problème n'est pas solvable en considérant des distances usuelles.
J'ai déjà entendu parler de systèmes à ressort, mais je ne m'y connais pas du tout. Avez vous de la littérature à me conseiller à ce sujet ? Y a t-il des représentations connues ? Sinon, avez vous une idée pour résoudre ce problème ?

Merci !
-----

[Seirios]

Salut mx6,

Ton problème me semble plutôt obscur... Qu'est-ce que tu entends par "représentations graphiques" d'une matrice ?

[invite9a322bed]

Je m'excuse pour ce retard. Alors imaginons on a une matrice pour laquelle l'élément (i,j) représente la distance (ou l'intéraction ou ce que vous voulez ) d'un objet i à un objet j (ça peut être des villes, des produits, pour moi c'est pour une application marketing). Cette matrice est symétrique car distance de i à j est pareil que j à i, et les éléments diagonaux sont nuls. Par un soucis de simplification, les éléments sont normés, c'est à dire tous les éléments sont entre 0 et 1 (les éléments diagonaux sont égaux à 0, les objets très loin entre eux ont une distance proche de 1).

Maintenant, je veux avoir une présentation graphique de tous ces objets en 2D ou 3D. L'intérêt est trouver des relations intéressantes entre les objets via ces représentations.

J'espère que c'est clair maintenant, n'hésitez pas si vous avez toujours des questions

[Resartus]

Il me semble plus pratique de représenter la proximité que la distance (1 si très proche, 0 si pas de relation)
Le plus simple (mais qui ne marche que si les objets ne sont pas trop nombreux) serait des fléches entre chaque objet, d'épaisseur variable (un peu comme des flux economiques entre regions).
Une alternative aux flèches est de créer sur chaque objet des secteurs de couleur (où des formes quelconques) dont la taille variable représente la force de la relation avec l'objet distant de cette couleur.

Peut-on déplacer les objets dans le plan? (ou l'espace?)
Si oui, on peut moduler la taille d'un objet en fonction du total de ses relations et rapprocher les objets qui ont les plus fortes relations. Cela peut permettre d'identifier des clusters. Mais, comme vous le disiez, les distances ne seront pas toujours respectées.

Dans tous les cas, je ne crois pas qu'on puisse dépasser une petite dizaine d'objets sans que cela devienne complètement illisible

[A voir en vidéo sur Futura]

[invite9a322bed]

Bonjour,


Merci pour ta réponse. Le problème est bien plus compliqué puisque c'est pour une application Big Data (donc beaucoup trop de données). Je sais qu'il y a un logiciel qui fait ce genre de présentation : http://gephi.github.io/ . Mais je n'ai pas la moindre idée sur son fonctionnement.

Bien cordialement,

[Resartus]

Si on renonce à l'identification fine des relations, et qu'il faut simplement trouver des clusters, le problème devient plus "mathématique", et en un certain sens plus simple. Google fournit gratuitement* des packs logiciels big data, et il semble (mais je n'ai pas le nom exact en tête) qu'il y a des applis pour traiter ce genre de problèmes.

*Evidemment, "there's no such thing as a free meal". Si vous voulez garder pour vous des infos propriétaires, il vaut peut-être mieux payer un logiciel...

[invite9a322bed]

Merci pour ta réponse. Au fait, je veux bien comprendre les algos derrière tout ça si tu as de la littérature sur ce sujet je suis preneur. Les logiciels fournissent des résultats certes, mais on ne sait pas comment ça fonctionne derrière

[Resartus]

Cela fait partie des problèmes d'optimisation linéaire, ou plutôt quadratique.

https://fr.wikipedia.org/wiki/Optimi..._lin%C3%A9aire
https://fr.wikipedia.org/wiki/Optimisation_quadratique

Pour trouver des solutions comme celles de ton exercice, on doit créer une fonction "d'énergie" variant avec les coordonnées des objets, et que le programme va optimiser

J'imagine que dans ton cas, on peut utiliser une fonction répulsive inversement proportionnelle à la distance geometrique (ou a son carré) entre les objets, et d'autant plus forte que la relation entre objets est faible. Pour éviter que les objets se regroupent sur les bords, il faut refermer l'espace sur lui-même (c'est à dire qu'un objet qui part à droite revient à gauche et idem entre haut et bas, façon pacman).

Après optimisation, les objets les plus éloignés seront ceux qui ont le moins de relations entre eux.

Une difficulté souvent rencontrée avec ce genre de programme est que le temps de calcul pour trouver LA solution optimale augmente très vite avec le nombre de points. Mais on se contente souvent d'une optimisation partielle obtenue en un temps raisonnable par des méthodes statistiques, qui sera en général très proche de l'optimum absolu

[invite9a322bed]

Merci beaucoup pour ces réponses. Je vais lire les articles wikipedia ! Et en effet, quelqu'un m'avait parlé un jour d'une représentation où la liaison peut être considéré comme un système de ressort, et l'idée est de trouver les raideurs de chaque ressorts pour minimiser l’énergie du système.