Discussion :

[lynaranya]

Bonsoir,
j'ai un fichier csv qui contient une matrice de distance et je voudrais créer un arbre à partir des données de ce fichier

a1 a2 a3 a4
a1 0 1,5 4 ,2 6
a2 1,5 0 2 0,9
a3 1,5 2 0 3,2
a4 1,5 2 3,2 0

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
pour (i=1 à nbr_ligne) faire
      pour (j=1 à nbr_colonnes)  faire
               si (arbre est vide ) alors
                      créer un arbre
               sinon si (sim(ai,aj)>=seuil) alors
                               connecter aj à ai coté gauche de l'arbre 
                          sinon 
                               connecter aj à ai coté droit de l'arbre 
                           finsin
               finsin
     fin pour
fin pour

j'ai besoin d'une aide pour commencer à programmer,

[foetus]

Il faut déjà faire du code assez classique

• lire un fichier, extraire les données du fichier CSV (avec une gestion des erreurs), ... Le résultat, c'est juste une matrice/ tableau à 2 dimensions et un tableau d'identifiants (*) (a1 a2 a3 ...) ... mais la relation identifiant - ligne/ colonne peut correspond à l'indice de (*) (<- il y a très peu de contraintes mais c'est suffisant)
• (******) coder la classique structure nœud. C'est une structure, avec une valeur (******) et 2 fils (ce sont 2 pointeurs vers cette structure). Et évidemment, l'arbre sera un pointeur vers la racine (qui est un nœud)
• Ensuite il reste la distance Peut-être l'associer avec 1 fils qui est plus simple que d'avoir un graphe avec des arêtes (*****) (un arbre est juste un graphe spécial) - quoique le graphe peut éventuellement simplifier la construction "déconnectée" (****) À réfléchir

Ensuite ton algo est faux (du moins je pense je n'y connais rien)

Tu vas partir d'un arbre/ graphe B vide - c'est à dire NULL parce que sa construction va se faire noeud par noeud, mais certains peuvent ne pas être reliés (****). C'est à la toute fin que l'arbre sera complet (du moins je pense je n'y connais rien)
Donc comment coder cette construction en C, Avec un graphe (*****) ? à réfléchir
Préconditions : avoir au moins 2 points, et donc une matrice de distances au moins [2, 2] et évidement la matrice doit être symétrique ( ce qui n'est pas le cas de ta matrice exemple )

1) Il faut choisir la distance la plus courte. Le parcours se fait que sur une moitié (parce que la matrice est symétrique) (haute ou basse par rapport à la diagonale à choisir). Disons entre X et Y, il y a une distance D (D est le minimum de toutes les distances)

2)

• Si ni X ni Y appartient à B, il faut créer 3 nœuds/ 2 arrêtes - un nœud X/Y (nb points : 2) avec deux fils/ feuilles (***) X et Y avec chacun, 1 distance de (D/ 2).
• Si X (respectivement Y) appartient à B mais pas Y (resp. X), il faut créer 2 nœuds/ 2 arrêtes - Un nœud A1/.../AN/Y (resp. A1/.../AN/X) (nb points : (N + 1)) avec deux fils (***) :
  
  • une feuille Y (resp. X) avec une distance de (D/ 2)
  • la partie de l'arbre A1/.../AN (nb points : N) (**) qui contient X (resp. Y) et déduire de (D/ 2) la distance entre la racine de (**) et X (resp. Y)
• Si X et Y appartiennent à B cela semble impossible ... édit : si cela semble possible, il faut créer 1 nœud/ 2 arrêtes - Un nœud A1/.../AN/B1/.../BM (nb points : (N + M)) qui relie les nœuds A1/.../AN (nb points : N) et B1/.../BM (nb points : M) avec chacun, 1 distance de (D/ 2).

3) Apparemment si la matrice de distances n'a plus que 2 lignes/ colonnes, c'est fini (du moins je pense je n'y connais rien)
Sinon :
3-1) Recalculer la matrice de distances en fusionnant :

1. les lignes X et Y en 1 seule ligne X/Y et la distance entre X/Y et un point aX (D X/Y <-> aX) est égale à (D X <-> aX + D Y <-> aX) / 2
2. les colonnes X et Y en 1 seule colonne X/Y de la même façon (<- ta matrice étant symétrique tu n'as qu'à recopier les distances de la ligne (ou vice et versa) , ou éventuellement pour tester que tu trouves les mêmes valeurs)

3-2) Recommencer à l'étape 1

Bonus : peut-être travailler avec un graphe et à la fin le transformer en arbre (******) ... ce qui peut servir également de test si tout s'est bien passé

Voila, c'est assez chaud à coder : ce n'est pas que c'est difficile, mais il y a des détails à réfléchir (par exemple représenter la distance, la construction de ton arbre, la réduction de la matrice, la fusion des identifiants, recherche d'1 nœud dans 1 sous-arbre avec calcul de la distance, ...) mais cela peut être assez intéressant.


Édit : (***) d'ailleurs, je ne vois pas la notion de fils gauche/ fils droit - est-ce important ?

Édit : (******) arf seules les feuilles ont un identifiant (qui peut être la valeur d'un nœud). Sinon les nœuds n'ont pas de valeurs ... ou alors utiliser cette valeur pour le nombre de points gérés, pour retrouver facilement la racine de l'arbre si on travaille avec un graphe (<- voir mon message suivant)

[foetus]

Après réflexion,
*) j'ai l'impression que mon algo n'est pas complet Il me semble qu'à la fin, l'arbre ne sera pas complet, on aura 2 sous-arbres et qu'il manquera la racine. Il faudra la créer ayant comme distance aux fils D / 2 (<- le cas 3 de mon message précédent), D étant la seule distance qui restera dans la matrice de distances (puisque la matrice aura une taille de [2, 2] et qu'elle est symétrique)

*) Il y a 2 types de points

• Les points originaux, ceux ayant des identifiants qui sera dans le tableau d'identifiants qui est le résultat de la lecture de ton fichier CSV (*, message précédent). Tous ces points seront des feuilles dans l'arbre final (<- à vérifier )
• Les points fusionnés avec un identifiant A1/.../AN et seront toujours la racine d'un sous-arbre de l'arbre en construction (<- à vérifier )

Et je pense qu'il est important d'avoir une bonne gestion des identifiants pour avoir le lien entre l'arbre en construction et la matrice de distances. Et ainsi, dégager des simplifications de code comme par exemple, en fonction du type de point, la recherche d'1 point sera soit dans le tableau d'identifiants (*, message précédent) soit dans l'arbre en construction.
Et par conséquent, on n'a plus besoin du nombre de points gérés comme je l'ai proposé, ou plus besoin de rechercher 1 nœud dans 1 sous-arbre avec calcul de la distance ... ou autre

Et l'autre truc , j'ai aussi l'impression, qu'il faut avoir une structure graphe mais organisée comme une forêt d'arbres (puisque pendant la construction de l'arbre, on va avoir des sous-arbres qui vont être reliés 2 par 2) et parce qu'on a besoin que de la racine de ces sous-arbres et il n'y aura aucun parcours en profondeur (<- à vérifier )

[lynaranya]

Bonsoir;

moi j'ai pensé a cela;
après l'importation du fichier csv qui contient une matrice de distance symétrique, il faut creer une fonction qui permet d'ajouter des éléments à l'arbre de la façon suivante:


- création d'une fonction qui permet d'ajouter un arbre, la fonction est de type arbre
- si l'arbre est vide, alors il s'agit de la création d'un arbre,
- sinon on compare la valeur de l'élément à insérer (dis[i,j]) avec la valeur ssim, qui contient la moyenne de tout les éléments de la matrice distance,
- si l'élément est petit,
- on vérifie si on est dans la première ligne de la matrice, c-à-d, i=1,
- dans ce cas la on ajoute l'élément dans le coté gauche de l'arbre (connecter le nœud j au nœud i coté gauche),
- sinon déplacer le nœud j et le connecter au nœud i,
- si l'élément est grand,
- on vérifie si on est dans la première ligne de la matrice, c-à-d, i=1,
- dans ce cas la on ajoute l'élément dans le coté droit de l'arbre (connecter le noeud j au noeud i coté droit),
- sinon déplacer le nœud j et le connecter au nœud i,

- à la fin, on fait un retour de l'arbre

on a plusieurs fonctions et procédure à implémenter:
1) une fonction qui permet de vérifier si l'arbre est vide ou non,
2) une fonction qui permet de créer un nouveau arbre dans le cas où l'arbre est vide
3) une fonction qui permet d’ajouter les éléments
4) une fonction qui permet de supprimer ou bien de déplacer les nœuds