Schéma pour association d'éléments avec mots-clefs ?
Résolu/Fermémamiemando Messages postés 33077 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 18 avril 2024 - 6 déc. 2022 à 18:58
- Schéma pour association d'éléments avec mots-clefs ?
- Schéma téléphone oublié - Guide
- Dcb association - Forum Téléphones & tablettes Android
- Germain veut gérer les activités de son association avec une base de données. il a commencé à créer des tables dans un fichier, mais il n’est pas sûr du résultat. le fichier à télécharger contient uniquement le schéma de cette base de données. en l’état actuel, que peut-on en déduire ? - Forum Outlook
- Schéma branchement autoradio couleur fils - Forum Autoradio
- Photoshop elements gratuit - Télécharger - Retouche d'image
7 réponses
5 déc. 2022 à 16:51
Bonjour,
Si j'ai bien compris ton problème tu recherches un algorithme de "force-based directed graph drawing". Quelques algorithmes sont donnés dans cet article scientifique. Si tu travailles sur une interface web, une bonne solution technique serait sans doute d'utiliser d3js car cette librairie javascript implémente déjà des des rendus de graphes basés sur des forces.
Pour ma part j'ai aussi entendu parler de celle qui est basée sur les valeurs propres de la matrice graphe.
Parmi toutes ces méthodes, je ne peux pas te dire laquelle est la plus rapide, celle qui a le meilleur rendu, ou la plus facile à coder, mais j'ai l'impression que ça n'est de toute façon pas l'objet de la question.
Une fois l'algorithme choisi, il faut définir ton modèle de graphe. Chaque sommet correspond à l'un ensemble Ei non vide. Chaque arc connecte deux sommets dont les ensembles partagent une intersection non vide. Chaque arc est pondéré par exemple par la distance de Jaccard : |Ei n Ej| / |Ei u Ej| (qui est toujours bien défini puisque deux sommets adjacents ont une intersection non vide et donc une union qui comporte au moins un élément).
Bonne chance
4 déc. 2022 à 12:35
BONJOUR,
ça dépend:
De comment tu veux afficher les résultats.
Du format des données.
De leur emplacement.
L'algo n'a rien de compliqué:
- Lire les élément et leurs mots.
- Si mots récurrents stocker élément et mots.
Un exemple facilite la compréhension.
J'ai donné un exemple.
Peu importe le format des données, je demande un algorithme.
Le but est d'afficher les éléments sur l'écran, +/- proches suivant leur nombre de mots-clés communs, comme sur le schéma donné en exemple. E1 est entre ses 2 mots-clés et donc proche de E1 avec qui il a un mot-clef commun.
J'envisage une 1ere étape où je calculerais un facteur de proximité entre chaque paire d'éléments.
Mais après ?
4 déc. 2022 à 17:04
Le format: Si les données sont structurées ou si elles sont en vrac, ce n'est pas tout à fait pareil.
4 déc. 2022 à 18:05
Les données sont comme indiquées.
Un tableau associatif:
[
E1 => [ M1 , M2 ] ,
E2 => [ M2 ] ,
E3 => [ M3 ]
]
.
Modifié le 4 déc. 2022 à 18:24
E1 => M1 M2 M3
E2 => M2 M3
E2=> _ M2 M3
Tu vois la différence ?
Modifié le 4 déc. 2022 à 18:33
Tu te focalises sur des détails.
J'ai les données, bien structurées, propres.
.
As-tu une piste pour ma recherche d'algorithme ?
5 déc. 2022 à 01:02
L'algo pour trouver les associations, c'est une chose.
L'affichage ça en est une autre.
Et les deux n'ont absolument rien à voir l'une avec l'autre.
L'affichage c'est un problème totalement différent de l'algo.(et plus complexe)..
Modifié le 5 déc. 2022 à 01:25
Afficher de l'aléatoire, c'est très facile.
Afficher sous contrainte c'est plus difficile.
Et ce n'est pas un algo qui fera l'affichage, mais de la réflexion/cogitation.
Quand on a réalisé l'affichage, on peut décrire (commenter) la procédure qui l'a généré.
Rarement l'inverse.
5 déc. 2022 à 01:52
Suite du: #11
Pour un affichage cohérent:
Les E en étoile autour du M commun.
Ou M commun en "titre" et les E en liste. (plus facile)
5 déc. 2022 à 11:46
Un E peut avoir des M communs avec plusieurs E.
C'est + compliqué que les étoiles.
Mais effectivement je pense à une démarche circuli: ceux qui ont le plus de points communs doivent être au centre. Mais du bon côté du centre pour être proches des "cousins" qui partagent des M.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Modifié le 5 déc. 2022 à 11:37
Suite de: #11 et #12:
Après ça dépend aussi du nombre de: "E", du nombre de: "M", et du nombre moyen de: "M" par "E".
Un test avec: 10 E, 4 M, et: 2M par E
Donne déjà 22 associations
On n'ose pas penser à ce que ça donnerait avec 20 E, 5 M et 3 M par E.
Modifié le 5 déc. 2022 à 13:08
J'en trouve 64 par groupes de 15 à 24
Bon courage pour l'affichage
C'est faisable en colonnes ou en lignes
Mais pour l'étoile ça risque d'être "coton".
6 déc. 2022 à 11:25
De l'infaisabilité de la chose:
Résultats pour 10 E 3 M et 2 M par E:
E1 est liée à 15 autres E par M1 M2 M3
E2 liée à 5 autres par M2
E3 liée à 6 autres par M1
E4 liée à 10 autres M1 et M3
E5 liée à 9 autres par M2 et M3
E6 liée à 5 autres par M2
E7 liée à 10 autres par M1 M3
E8 liée à 11 autres par M1 M2
E9 liée à 5 autres par M2
E10 liée à 6 autres par M1
C'est déjà ingérable à afficher dans le style demandé par nico.
6 déc. 2022 à 11:52
Je n'ai pas trop compris où tu voulais en venir avec ton exemple, mais dans le cas général (peu importe que tu travailles dans un espace à 2 ou 3 dimensions) une représentation qui respecte parfaitement la distance que tu as choisie. Cependant, tu peux concevoir des algorithmes qui essayent de regrouper dans cet espace les éléments qui ont une distance proche et c'est précisément le rôle de ceux que j'ai évoqué dans le message #17.
Là où je te rejoins, c'est que ce genre d'affichage ne sera lisible que si le degré des sommets globalement est très faible (ce qui n'est pas le cas dans ton exemple, mais peut-être dans le cas d'usage de Nico).
Modifié le 6 déc. 2022 à 15:16
En effet.
Les références que tu m'as données sont très pertinentes.
Je ne maîtrise pas toutes les subtilités mathématiques, je souhaite qqch de personnalisé et mon but est aussi de progresser sur les possibilités de cette famille d'algorithmes.
Je vais donc partir d'un algorithme de base et l'affiner au fur et à mesure.
Les algorithmes sont basés sur des itérations en appliquant les forces à partir de positions initiales aléatoires. Or, dans mon cas d'usage, je peux trouver des positions de départ meilleures que l'aléatoire (les éléments qui ont + de liens sont vers le centre).
Pour l'indice de Jaccard, j'ai 4 cas (puisque j'ai 2 types d'éléments). J'ai une formule pour un cas. Pour les autres, je dois réfléchir. Sachant qu'il y aura plusieurs itérations pour voir les résultats et affiner.
Par rapport aux remarques sur la taille du problème qui rendrait le schéma forcément illisible, il y a plusieurs parades:
- couleurs ou formes # aux # éléments
- calques
- zooms avec différents niveaux de détails suivant le niveau de zoom
- ( sûrement d'autres idées )
Pour la taille qui rendrait le temps de calcul énorme: limiter les itérations...
...
Sur l'algorithme, j'ai un souci de compréhension sur un point: après calcul des forces entre 2 éléments, vers où bouger un élément (gauche, droite, haut, bas?) et lequel des 2 bouger.
...
Atchao :)))
6 déc. 2022 à 16:32
Sur l'algorithme, j'ai un souci de compréhension sur un point: après calcul des forces entre 2 éléments, vers où bouger un élément (gauche, droite, haut, bas?) et lequel des 2 bouger.
Cela dépend de l'algorithme je suppose. Pour certains, tu donnes une force de répulsion (~ressort), pour d'autre une force d'attraction (~aimant). Je pense qu'en fouillant sur github tu dois pouvoir trouver des exemples. Mais la direction (l'axe si tu préfères) sur lequel opère la force est celui qui traverse les deux sommets.
Voici à quoi pourrait ressembler un algorithme naïf.
Pour chaque sommet u du graphe :
- Soit s un vecteur initialisé à (0, 0) (si tu es dans le plan)
- Pour chaque voisin v de u
- Calcule la force que u exerce sur v (intensité) : k
- Determine un vecteur unitaire colinéaire à (u, v). Tant qu'à faire choisi le orienté dans le même sens que (v, u) si c'est une répulsion et (u, v) si c'est une attraction : e
- Multiplie ce vecteur unitaire par l'intensité et ajoute le à s : s += k.e
- Le vecteur s indique dans quelle direction déplacer u
Répète la procédure un grand nombre de fois.
Mais bon, le jour où tu veux implémenter un tel algorithme, je pense qu'en fouillant un peu sur github il y a plein d'algorithmes sur étagères à partir desquels tu pourrais broder ton propre algorithme. Pour que je te suggères des pointeurs il faudrait me dire dans quel langage tu envisages d'implémenter ton algorithme.
Par rapport aux remarques sur la taille du problème qui rendrait le schéma forcément illisible, il y a plusieurs parades:
- couleurs ou formes # aux # éléments
- calques
- zooms avec différents niveaux de détails suivant le niveau de zoom
- ( sûrement d'autres idées )
Ça peut aider effectivement, mais si le cœur de ton graphe est très dense, les sommets risquent d'être placés dans un ordre assez arbitraire. On peut espérer que les sommets placés au bord du graphe parviennent à irradier autour de ce cœur. Mais comme je le disais dans un autre message, la qualité du résultat dépend beaucoup de la densité de ton graphe. Si tu as beaucoup de sommets avec un degré élevé, il y aura tellement d'interaction qu'il ne se passera pas grand chose. Si au contraire, chaque sommet à un petit nombre de voisin (disons de l'ordre de 4), tu peux espérer que les sommets arrivent à se placer les uns par rapport aux autres...
6 déc. 2022 à 18:15
Oui la visibilité dépend des données.
Mais
L'algorithme a des paramètres sur les forces, Les faire varier peut changer le rendu, non?
Pour l'indice de Jaccard, je peux faire varier la formule.
Je suis curieux de voir ce que ça donnera.
...
Pour le vecteur d'attraction-répulsion, ok sur le principe. Mais le plan n'est pas infini, on est sur un écran. Donc il faut une stratégie de bord: rebond?
Il y a aussi la question d'équilibrer l'occupation de l'espace, même en cas de faible densité..
...
J'avance tranquillement.
...
Merci pour tes contributions.
6 déc. 2022 à 18:58
J'imagine que là aussi ça dépend de l'algorithme. Dans un modèle à ressort, je suppose les voisins directs sont attractifs, les autres sommets sont répulsifs pour éviter qu'ils ne s'éloignent indéfiniment. Dans un modèle attractif il faut de la même manière éviter le phénomène inverse pour éviter que tous les sommets ne finissent confondus en un même point. Je pense que là il faut choisir un algorithme qui te plaît bien (à défaut d'en trouver un tout prêt qui te convienne) et poser des questions spécifiquement sur cet algorithme.
Mais bon, pour être honnête avec toi, je crains que tu ne réinventes la roue. Quelque soit le langage choisi, faire un rendu javascript est plutôt une bonne idée car cela te permettra de voir ce que ça donne dans un notebook ou d'exposer les résultat sur une page web. Et en ce sens, d3js et son layout de graphe a largement été testé (car il est largement utilisé) fait probablement déjà plus ou moins ce que tu veux. Voir ce lien.
6 déc. 2022 à 12:29
On ne connaît ni le but du sujet ni son étendue.
La représentation demandée par nico, si elle est possible en théorie, se heurte vite aux limites de la lisibilité.
Cas de E8 liée à 11 autre en 2 groupes.
Avec ou sans traits de liaisons c'est illisible (et pour seulement 10 E).
Modifié le 5 déc. 2022 à 16:56
Le nom du problème et des solutions :)
Super réponse détaillée :)
Merciiii!
Je vais étudier ça.
5 déc. 2022 à 17:00
Dany = Nico ? Juste pour m'y retrouver :-)
Est-ce que ton problème est résolu ?
5 déc. 2022 à 17:14
Pour l'algo d'associations ça a l'air bon.
Mais ça ne va pas être évident d'afficher des 15 ou 25 E associées parmi 60 autres.
Dans le style demandé par nico (qui à mon sens n'est qu'un "gadget", et pas forcément plus lisible que des simples listes titrées)