Arbre de décision binaire

a marqué ce sujet comme résolu.

Bonjour,

Pour le besoin que je vais vous expliciter plus bas j’ai conlut qu’un arbre de décision binaire était ce qui était le plus adapté mais j’ai un peu de mal à voir comment démarrer.

En gros voici le concept : Dans une application GUI avec un viewer 3D :

On considère qu’un solide est défini par :

  • plusieurs faces qui sont elle mêmes définies par :
  • plusieurs fils qui sont eux mêmes définis par :
  • plusieurs segments qui sont eux même définis par :
  • 2 sommets

Chaque entité précedemment cité dispose de sa classe (Solid, Face, Wire, Edge, Vertex) Un des moyens que j’ai actuellement pour identifier une de ces entités est l’usage d’un "selecteur"

Un selecteur est un objet qui permet de filtrer des entités selon certains critères. Par exemple : le selecteur monSolide.Selector(edges, "|Z") permet de selectionner tous les segments parallèle à l’axe Z de mon solide.

J’ai à ma disposition tout un tas de selecteurs (perpenticulaire à un axe, entité la plus loin dans une certaine direction, entité disposant de la plus grande surface (pour les faces), ou encore étant inscrit dans une sphere de certaine dimension) De plus les selecteurs peuvent se combiner pour faire des selections encore plus précises.

Tous ces selecteurs permettent de selectionner ce qu’on veut de façon efficace mais il est parfois compliqué de choisir un selecteur adapté lorsqu’on dispose d’un solide complexe.

Mon plan est d’utiliser un arbe de décision pour que l’ordinateur me créer lui même un selecteur adapté lorsque je selectionne une entité (ou plusieurs) donnée.

Cela me semble adapté, car si on considère par exemple le sommet entouré ci-dessous.

image.png
image.png

On peut filter les sommets et déterminer si oui ou non le sommet considéré est dans la selection.

Par exemple :

  • Appartient à la face la plus éloignée dans la direction Y ? -> Non
  • Appartient à la face la plus éloignée dans la direction Z ? -> Oui

Et affiner encore avec plus de selecteurs jusqu’à tomber sur le sommet voulu.

Voilà j’en suis là et je ne sais pas trop comment continuer, je ne sais pas comment créer mon arbre.

J’ai suivi le cours sur le site sur les arbres de décision mais j’ai du mal à faire le parallèle avec mon cas.

Je pense qu’une première étape serait de se simplifier le problème, de ne considérer que les sommets avec quelques selecteurs.

Désolé pour le pavé, si vous avez des recommandations, pistes ou quoique ce soit je suis preneur. Je développe en python donc si vous voyez une lib qui fasse exactement ce dont j’ai besoin je suis preneur également.

Merci !

Hello,

Le plus simple et rapide pour créer un arbre (contrairement à ce que dit toute la littérature de math théorique), c’est de créer un tableau de tests :

choice = [ test1(), test2(), test3(), ..., testN() ]

Tu peux envisager d’étaler ces tests sur plusieurs lignes et de les ajouter à ton tableau.

Et ensuite tu concatènes tout ça : 100111000101 (Note : ton arbre étant binaire, tu peux exclure les séparateurs et tu peux même remplacer ton tableau par une chaîne de caractères, t’évitant ainsi une concaténation de ton tableau en plus).

Pour le comparer avec un fichier contenant la sortie de ton arbre de décision (ou des simples conditions) :

[... avant ...]
100111000100 reponse_A
100111000101 reponse_D
100111000110 reponse_N
[... après ...]

Je ne sais pas combien tu en as et si tu peux générer le résultat de ton arbre automatiquement ?

+0 -1

Je crois que j’ai compris ton idée et ça à l’air en effet de rendre le process assez simple mais j’ai plusieurs problèmes :

  • Je dois réaliser les tests sur des objets en mémoire que je ne peux pas vraiment charger via des fichiers (ni les écrire dans des fichiers)

  • Ces tests ne sont en réalité par strictement définis. Je peux en définir certains mais ils peuvent se composer pour donner un truc du style : >Z and <Y or <X c’est d’ailleurs ce qui me pose problème, je peux les décomposer en tests successifs mais dans ce cas le problème étant que je vais avoir un bazillions de tests.

  • Finalement, j’ai je pense un peu de mal à comprendre comment fonctionne les algos de machine learning sur les arbres de décisions, de ce que j’ai lu j’ai l’impression qu’il faut que les tests soit bien définis mais ce n’est pas trop mon cas d’où la complexité et mon incompréhension.

Je ne suis même pas sur en realité qu’un arbre de décision est adapté, mais ça en avait l’air

+0 -0

Voici ce que je comprends de ton problème:

  • tu as un ensemble de sélecteurs un peu baroques qui ont été conçus petit à petit par des humains
  • on peut sans doute représenter tout ensemble de faces/côtés/points avec (en faisant des unions et intersections de sélecteurs, etc.)
  • mais il n’y a pas d’algorithme clair pour trouver la bonne "formule" (combinaison de sélecteurs) pour un ensemble de points/côtés/faces donnés (ce serait le cas si le langage des sélecteurs était assez simple/régulier)
  • et pourtant tu aimerais faire quand même cette opération, retrouver la "formule" pour sélectionner un ensemble donné
  • c’est pour une application interactive donc les performances ne sont pas super-importantes (il ne faut pas répondre à cent mille requêtes de ce genre en une seconde).

À priori j’essaierais une approche assez bête, par "saturation": tu parcours toutes les formules possibles de taille <=N, pour chaque formule tu calcules l’ensemble des points/côtés/faces que ça représente, et tu t’arrêtes quand ça te donne ton résultat. Pour cela, tu commences par générer toutes les formules (des arbres de sélecteurs) de taille 1, puis de taille 2 (en combinant des formules de taille 1), puis de taille 3, etc., jusqu’à le N que tu as choisi comme "on laisse tomber, c’est trop dur".

Un peu plus précisément:

  • Pour calculer le résultat des formules d’une certaine taille, tu peux t’aider des résultats pour les formules plus petites dont le résultat est déjà calculé. Imaginons par exemple que ton langage de sélecteur contient un combinateur Union(S1, S2) pour prendre l’union de deux sélecteurs), et si tu as déjà calculé le résultat de toutes les formules de taille <=3, tu peux calculer rapidement le résultat de toutes les formulles de la forme Union(S1,S2) de taille 4, en prenant S1, S2 dans ta base (avec taille(S1)+taille(S2) <= 3), et donc en ayant déjà leur résultat sous la main.
  • Si une formule donne un résultat identique à une formule plus petite, on peut l’oublier (ne pas l’inclure dans la base) et ne plus jamais la considérer pour former de nouvelles formules.

Je ne connais pas ton langage de sélecteur, mais il y a peut-être des critères pour accélérer la recherche en "laissant tomber" des formules qui clairement ne vont pas permettre d’arriver au résultat que tu veux:

  • si le résultat d’une formule ne contient aucun des points/côtés/faces que tu cherches, il est possible que cette formule ne puisse jamais se combiner avec d’autres de façon utile pour trouver la solution, et que tu puisses donc la laisser tomber direct. (Mais ça dépend du langage de sélecteurs; si l’opération "complémentaire" existe par exemple cette remarque ne s’applique pas forcément)
  • les propriétés des opérations peuvent aider à éliminer des redondances; par exemple l’union est commutative donc si tu as déjà considéré Union(S1,S2) il est inutile de regarder Union(S2,S1); cela peut s’intégrer facilement en donnant un numéro à chaque formule "intéressante" trouvée, et en forçant les unions (et intersections, etc.) à toujours avoir la formule de gauche avec un numéro plus petit que la formule de droite.
+1 -0

@gasche Tu as parfaitement compris le problème, tellement bien que ca m’étonne !

Le langage de sélection est assez complexe. Qui plus est il est possible de définir des directions arbitraire par exemple donc on a d’un coup une infinité de test/sélection possible et le brute force devient un peu caduque.

Toujours est il que dans un premier temps tout tester comme tu le propose est surement la première solution viable qui peut apporter un résultat satisfaisant. Je devrais peut être commencer par ça et voir après.

Est-il possible d’entrainer un algo de ML sur ce type de cas ? De manière à éviter d’avoir à boucler sur toutes les possibilités à chaque fois (niveau performances ça risque de pêcher un peu :/ )

Pour référence, si ça en intéresse certains les sélecteurs en question sont : Tous les sélecteurs ; String selector

Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte