Affectation d'arbres dans des séries de données

[invitea626a981]

Bonjour,

Pour un projet j'ai une série de points avec une propriété (disons une couleur par exemple). À partir d'un exemple fourni par l'utilisateur sur une petite fraction de ces points, je dois appliquer aléatoirement mes entrées (en respectant les proportions) sur tous les autres points de la série. Jusque là rien de bien compliqué, mais mon problème est le suivant :
Il est possible d'imposer une dépendance entre deux points. C'est à dire que si on a un point rouge et un point vert dans une disposition particulière qui sont mises dans le même groupe, on souhaite que ce groupe soit appliqué en entier dans les autres données. Il peut y avoir plusieurs niveau de dépendance, qui finalement forment un arbre.
Je met un dessin pour plus de clarté : Les points verts représentent les données dans un état inconnu. Les 5 points en bas à gauche représentent les entrées de l'utilisateur. Il faudrait donc pouvoir dire que si on attribue le point jaune à un des points verts, il faudra forcément une configuration similaire pour les deux points bleus "enfants".

Je pense qu'il faut se pencher du coté de la recherche opérationnelle et des problèmes d'affectations pour ce genre de choses, mais je n'ai pas encore vraiment de connaissances dans le domaine. Est-ce que quelqu'un pourrait m'orienter vers des méthodes qui permettent de faire ce genre d'affectations ?

Merci !
-----

[invite0bbe92c0]

Bonjour

Pour moi votre explication est tout sauf clair.
Par exemple : je dois appliquer aléatoirement mes entrées (en respectant les proportions)

Quelles entrées ? Quelles proportions ?

[invitea626a981]

Dans le cas de l'image, les entrées seraient les 5 points en bas à gauche qui vont servir d'exemple de la part de l'utilisateur. Dans cette petite zone de l'image on a 2 bleus (40%) un rose, un orange et un jaune (20% chaque).

Au moment de colorer tous les points non spécifiés (verts, donc) on va essayer d'avoir ~40% de points bleus et ~20% de jaunes, oranges et roses.

Est-ce que c'est plus clair comme ça ?

[inviteb21379d3]

Tout d'abord, nous avons besoin de comprendre exactement ce que vous voulez.
Avez-vous besoin d'un algorithme de classification de l'échantillon dans l'un des deux groupes de couleurs ci-dessus?

[A voir en vidéo sur Futura]

[invitea626a981]

Désolé pour le temps de réponse, je n'ai pas accès en permanence à internet.
Dans le cas où il n'y aurait pas de relation entre mes points, pour généraliser mon exemple j'aurais pour chaque point vert attribué une couleur aléatoire parmi les 5 points d'exemple.
Maintenant si au moment d'attribuer aléatoirement ma couleur je tombe sur le jaune, il faut que le point (vert) sur lequel je met ma couleur ait deux autres points à proximité que je vais rendre bleus, parce qu'une contrainte a été spécifiée de cette manière.
Une solution qui me semble faisable mais extrêmement coûteuse en temps de calcul serait plutôt que d'appliquer aléatoirement mes couleurs je procède comme suit :
- Je trouve ma structure la plus profonde (donc ici le rond jaune avec les deux ronds bleus).
- Je prend chaque point vert, et je regarde dans son voisinage si il y a deux points à une distance similaire.
- Je choisis les solutions en minimisant l'erreur de distance (avec une norme L2 par exemple).

J'ai mis une image du résultat auquel j'aimerais arriver.

[inviteb21379d3]

Comme je ne sais pas exactement quelle est l'ampleur de la masse de données que vous faites allusion, et on ne sait pas encore à quelle distance peut-être ces points, voici ma suggestion pour tenter de minimiser le coût du traitement:

Si vous créez des sous-régions d'intérêt centrée sur chaque point avec une taille statistiquement appropriée, votre recherche sera effectuée uniquement dans les environs de la région, réduisant ainsi la taille de la matrice de points.