Arbre de décision pour réels

Soyez le premier à donner votre avis sur cette source.

Vue 8 345 fois - Téléchargée 774 fois

Description

Il s'agit d'un programme que j'ai fait pour m'aider à trouver quelless combinaisons de paramètres provoquaient un bug sur un autre programme. Le programme en question à un fichier d'entrer contenant plusieurs paramètres réels qui servent à faire des calculs poussés et une certaine combinaison provoquait une erreur.
Il lit un fichier csv (la première ligne étant le nom des colonnes, chaque valeur étant séparé par des virgules, la dernière colonne étant un booléen indiquant si il y a beuge ou pas). Ce fichier représente tous les exemples (par exemple, 130 exemples où le prog à tourné et 25 où il a raté).
Le programme affiche ensuite l'arbre selon la forme suivante :
- A chaque noeud , dans le text affiché : Le premier chiffre correspond à l'indice de la colonne dans le fichier csv, la deuxième partie est la condition à respecté (elle porte sur la valeur dans la colonne à l'indice précédant), la ligne du dessous correspond à la répartition des résulats sans beug (100% = pas de beug, 0% = bug à coup sur)
- A partir d'un noeud : celui de gauche, respecte la condition du noeud et pas celui de droite

Il n'y a pas d'élagage, ce programme affiche toutes les répartitions possibles. Une amélioration possible serait de l'inclure !

J'espère n'avoir rien oublié dans la description !!

Il n'y a aucune compétence particulière à avoir, il faut juste être à l'aise en c# et en algortihme.

Source / Exemple :


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

/* deadhand - SeyoS (c) */

namespace ArbreDeDécision
{
    public class AlgoArbreDeDécision
    {
        private double[][] exemples;

        public AlgoArbreDeDécision(double[][] exemples)
        {
            this.exemples = exemples;
        }

        public struct Segmentation
        {
            public double valeur;
            public bool inferieur;
            public double pourcentageRepartionVrai;
            public double pourcentageRepartionFaux;
            public int indice;
        }

        public struct Repartition
        {
            public int nbVrai;
            public int nbVraiTotal;
            public int nbFaux;
            public int nbFauxTotal;
        }

        public Segmentation segmentation(int j)  //Répartition des ok et des beugs en fonction du paramètre j
        {
            double vrai=0;
            int nbVrai=0;
            double faux=0;
            int nbFaux=0;
            for(int i = 0; i< exemples.Length; i++) {
                if(exemples[i][exemples[j].Length-1] == 1) {
                    vrai+=exemples[i][j];
                    nbVrai++;
                }
                else {
                    faux+=exemples[i][j];
                    nbFaux++;
                }
            }
            vrai = vrai/nbVrai;
            faux = faux/nbFaux;
            Segmentation seg;
            seg.pourcentageRepartionFaux = 0;
            seg.pourcentageRepartionVrai = 0;
            seg.valeur = Math.Abs(Math.Abs(vrai) - Math.Abs(faux))/2 + Math.Min(vrai,faux);
            if(vrai>faux)
                seg.inferieur = false;
            else
                seg.inferieur = true;
            seg.indice = j;
            Repartition rep = repartition(seg);
            seg.pourcentageRepartionVrai = (double)rep.nbVrai / (double)rep.nbVraiTotal * 100;
            seg.pourcentageRepartionFaux = (double)rep.nbFaux / (double)rep.nbFauxTotal * 100;
            return seg;
        }

        public Repartition repartition(Segmentation seg) { //Nombre de faux et de vrai correspondant à cet segmentation par rapport à la totalit des vrais et des faux
            Repartition rep;
            rep.nbFaux = 0;
            rep.nbFauxTotal = 0;
            rep.nbVrai = 0;
            rep.nbVraiTotal = 0;
            for (int i = 0; i < exemples.Length; i++)
            {
                if (exemples[i][exemples[0].Length - 1] == 1)
                    rep.nbVraiTotal++;
                else
                    rep.nbFauxTotal++;
                if ((exemples[i][seg.indice] >= seg.valeur && !seg.inferieur) || (exemples[i][seg.indice] <= seg.valeur && seg.inferieur))
                    if(exemples[i][exemples[0].Length-1] == 1)
                        rep.nbVrai++;
                    else
                        rep.nbFaux++;
                    
            }
            return rep;
        }

        public int rechercheRacine() //Recherche le paramètre le plus représentatifs des résultats
        {
            int bestIndice = 0;
            Segmentation bestSegmentation;
            bestSegmentation.pourcentageRepartionFaux = 100;
            for (int j = 0; j < exemples[0].Length-1; j++)
            {
                Segmentation seg = segmentation(j);
                if (seg.pourcentageRepartionFaux >= bestSegmentation.pourcentageRepartionFaux)
                {
                    bestSegmentation = seg;
                    bestIndice = j;
                }
            }
            return bestIndice;
        }

        public int rechercheRacine(List<Segmentation> listSegmCheck, double[][] exemplesCorrespondant) //Idem que plus haut pour les exemples correspondant et en dehors des indices déjà utilisés
        {
            int bestIndice = 0;
            Segmentation bestSegmentation;
            bestSegmentation.pourcentageRepartionVrai = 0;
            for (int j = 0; j < exemplesCorrespondant[0].Length - 1; j++)
            {
                if (!wasChecked(j, listSegmCheck))
                {
                    Segmentation seg = segmentation(j, exemplesCorrespondant);
                    if (seg.pourcentageRepartionVrai >= bestSegmentation.pourcentageRepartionVrai)
                    {
                        bestSegmentation = seg;
                        bestIndice = j;
                    }
                }
            }
            return bestIndice;
        }

        public bool wasChecked(int j, List<Segmentation> listSegmCheck)
        {
            foreach(Segmentation seg in listSegmCheck)
            {
                if (seg.indice == j)
                    return true;
            }
            return false;
        }

        public Segmentation segmentation(int j, double[][] exemplesCorrespodant) //Segmentation parmis les exemples correspondant
        {
            double vrai = 0;
            int nbVrai = 0;
            double faux = 0;
            int nbFaux = 0;
            for (int i = 0; i < exemplesCorrespodant.Length; i++)
            {
                if (exemplesCorrespodant[i][exemplesCorrespodant[i].Length - 1] == 1)
                {
                    vrai += exemplesCorrespodant[i][j];
                    nbVrai++;
                }
                else
                {
                    faux += exemplesCorrespodant[i][j];
                    nbFaux++;
                }
            }
            vrai = nbVrai==0?0:vrai / nbVrai;
            faux = nbFaux==0?0:faux / nbFaux;
            Segmentation seg;
            seg.pourcentageRepartionFaux = 0;
            seg.pourcentageRepartionVrai = 0;
            seg.valeur = Math.Abs(Math.Abs(vrai) - Math.Abs(faux)) / 2 + Math.Min(vrai, faux);
            if (vrai > faux)
                seg.inferieur = false;
            else
                seg.inferieur = true;
            seg.indice = j;
            Repartition rep = repartition(seg);
            seg.pourcentageRepartionVrai = rep.nbVraiTotal==0?0:(double)rep.nbVrai / (double)rep.nbVraiTotal * 100;
            seg.pourcentageRepartionFaux = rep.nbVraiTotal==0?0:(double)rep.nbFaux / (double)rep.nbFauxTotal * 100;
            return seg;
        }

        public List<Node> rechercheBranches(Node pere) //Recherche les noeuds qui suivent immédiatement celui-ci.
        {
            List<Node> branches = new List<Node>();
            List<Segmentation> listSegmCheck = new List<Segmentation>();
            Node temp = pere;
            do
            {
                listSegmCheck.Add(temp.Segmentation);
                temp = temp.Pere;
            } while (temp != null);
            int nbElementCorrespondant = nombreElementCorrespondant(listSegmCheck,true);
            double[][] exemplesCorrespondant = new double[nbElementCorrespondant][];
            int indice = 0;
            for (int i = 0; i < exemples.Length; i++)
            {
                if (exempleCorrespond(i, listSegmCheck,true)) {
                    exemplesCorrespondant[indice++] = exemples[i];
                }
            }
            if (nbElementCorrespondant > 0)
            {
                int j = rechercheRacine(listSegmCheck, exemplesCorrespondant);
                Node node1 = new Node();
                node1.Pere = pere;
                node1.Segmentation = segmentation(j, exemplesCorrespondant);
                node1.VraiPourLePere = true;

                nbElementCorrespondant = nombreElementCorrespondant(listSegmCheck, false);
                if (nbElementCorrespondant > 0)
                {
                    exemplesCorrespondant = new double[nbElementCorrespondant][];
                    indice = 0;
                    for (int i = 0; i < exemples.Length; i++)
                    {
                        if (exempleCorrespond(i, listSegmCheck, false))
                        {
                            exemplesCorrespondant[indice++] = exemples[i];
                        }
                    }
                    j = rechercheRacine(listSegmCheck, exemplesCorrespondant);
                    Node node2 = new Node();
                    node2.Pere = pere;
                    node2.Segmentation = segmentation(j, exemplesCorrespondant);
                    node2.VraiPourLePere = false;
                    branches.Add(node1);
                    branches.Add(node2);
                }
            }
            return branches;
        }

        public int nombreElementCorrespondant(List<Segmentation> segmentations,bool sens)
        {
            int nb = 0;
            for (int i = 0; i < exemples.Length; i++)
            {
                if (exempleCorrespond(i, segmentations,sens))
                    nb++;
            }
            return nb;
        }

        public bool exempleCorrespond(int i, List<Segmentation> segmentations,bool vrai) //Correspond si respecte toutes les segmentations
        {
            foreach (Segmentation segmentation in segmentations)
            {
                if (vrai)
                {
                    if ((exemples[i][segmentation.indice] > segmentation.valeur && !segmentation.inferieur) || ((exemples[i][segmentation.indice] < segmentation.valeur && segmentation.inferieur)))
                       return false;
                }
                else
                    if ((exemples[i][segmentation.indice] > segmentation.valeur && segmentation.inferieur) || ((exemples[i][segmentation.indice] < segmentation.valeur && !segmentation.inferieur)))
                        return false;
            }
            return true;
        }

        public Node fillTree(Node racine) //Rempli tout les noeuds à partir de la racine
        {
            if (!racine.estUneFeuille())
            {
                List<Node> branches = racine.Branches;
                List<Node> branchesTemp = new List<Node>();
                foreach (Node node in branches)
                {
                    List<Node> branchesRes = rechercheBranches(node);
                    node.Branches = branchesRes;
                    branchesTemp.Add(fillTree(node));
                }
                racine.Branches = branchesTemp;
            }
            return racine;
        }
    }
}

Conclusion :


Have fun !!!

Codes Sources

A voir également

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.