Cet article décrit l'algorithme d'arbre de décision mis en œuvre par Java. Partagez-le pour votre référence, comme suit:
L'algorithme d'arbre de décision est une méthode pour approximer la valeur d'une fonction discrète. Il s'agit d'une méthode de classification typique, traitant d'abord les données, en utilisant l'algorithme d'induction pour générer des règles et des arbres de décision lisibles, puis en utilisant des décisions pour analyser de nouvelles données. Essentiellement, les arbres de décision sont le processus de classification des données grâce à une série de règles.
La construction de l'arbre de décision peut être effectuée en deux étapes. La première étape est la génération de l'arbre de décision: le processus de génération de l'arbre de décision à partir de l'ensemble d'échantillons de formation. D'une manière générale, l'ensemble de données d'échantillons de formation est un ensemble de données qui a un historique et un certain degré de compréhensivité en fonction des besoins réels et est utilisé pour l'analyse et le traitement des données. La deuxième étape est l'élagage de l'arbre de décision: l'élagage de l'arbre de décision est un processus de vérification, de correction et de révision de l'arbre de décision généré à l'étape précédente. Il utilise principalement les données du nouvel ensemble de données d'échantillon (appelé ensemble de données de test) pour vérifier les règles préliminaires générées pendant le processus de génération de l'arbre de décision et élatir les branches qui affectent la précision de la prédance.
Le code d'implémentation Java est le suivant:
Package Demo; import java.util.hashmap; import java.util.linkedlist; import java.util.list; import java.util.map; import java.util.map.entry; import java.util.set résultat:"); String [] attNames = new String [] {"Age", "Revenu", "Student", "Credit_Rating"}; // Lire la carte de définition des exemples <objet, list <nample>> échantillons = lecture échantillons (attamins); // Générez l'objet d'arbre de décision DecisionTree = GenerateDecisionTree (échantillons, attamins); // Sortie de l'arborescence de décision OutputDecisionTree (DecisionTree, 0, null); } / ** * Lisez l'ensemble d'échantillons qui a été classé et renvoie la carte: Classification-> Liste des échantillons appartenant à la catégorie * / MAP STATIQUE <Objet, List <nample>> ReadSamples (String [] AttrNames) {// Sample Attributs et leur classification (le dernier élément dans le tableau [] [] {"<30,", [] rawdata = nouvel objet [] [] {"<30,", [] RawData = New Object [] [] {"<30,", [] RawData = New Object "Non", "Fair", "0"}, {"<30", "high", "non", "excellent", "0"}, {"30-40", "high", "non", "Fair", "1"}, {"> 40", "Medium", "non", "Fair", "1", {">", "Low", "oui", "1", "{"> "," Low "," oui "," 1 "," {">", "" ">40 ", "Low ", "Yes", "Excellent", "0" }, { "30-40", "Low ", "Yes", "Excellent", "1" }, { "<30 ", "Medium", "No", "Fair ", "0" }, { "<30 ", "Low ", "Yes", "Fair ", "1" }, { ">40 ", "Medium", "Yes", "Fair "," 1 "}, {" <30 "," Medium "," Oui "," Excellent "," 1 "}, {" 30-40 "," Medium "," Non "," Excellent "," 1 "}, {" 30-40 "," High "," Oui "," Fair "," 1 "}, {"> 40 "," Medium "", "Non", "Excellent", ". // Lisez les exemples d'attributs et leurs classifications, construisez l'échantillon d'objet représentant l'échantillon et divisez l'ensemble d'échantillons par carte de classification <objet, liste <nample>> ret = new hashmap <objet, list <nample>> (); pour (objet [] ligne: rawdata) {échantillon échantillon = nouveau échantillon (); int i = 0; pour (int n = row.length - 1; i <n; i ++) sample.setAttribute (attnames [i], row [i]); Exemple.setCategory (row [i]); List <nample> échantillons = ret.get (row [i]); if (échantillons == null) {échantillons = new LinkedList <Sample> (); ret.put (ligne [i], échantillons); } sample.Add (échantillon); } return ret; } / ** * Construisez l'arborescence de décision * / objet statique généréécisionTree (map <objet, list <nample>> catégoriestosamples, string [] attnemes) {// s'il n'y a qu'un seul échantillon, utilisez la classification à laquelle l'échantillon appartient à la classification du nouvel échantillon if (catégoriestosamples.size () == 1) de retour categorytos.KeySet (). Itorator ().). // S'il n'y a pas d'attribut pour la prise de décision, la classification avec le plus d'échantillons de l'ensemble d'échantillons est utilisée comme classification du nouvel échantillon, c'est-à-dire votez pour la classification if (attnames.length == 0) {int max = 0; Objet maxcategory = null; pour (entrée <objet, list <nample>> Entrée: catégorieTOS. if (cur> max) {max = cur; maxcategory = entry.getKey (); }} return maxcategory; } // Sélectionnez l'objet d'attribut de test [] rst = ChoOsBestTestAtTribute (catégorieTOSamples, attNames); // Le nœud racine de l'arborescence de décision, l'attribut de branche est l'arborescence d'attribut de test sélectionné = new arbre (attnames [(entier) RST [0]]); // Les attributs de test utilisés ne doivent pas être sélectionnés comme attributs de test à nouveau String [] suba = new String [attNames.length - 1]; pour (int i = 0, j = 0; i <attnames.length; i ++) if (i! = (entier) rst [0]) suba [j ++] = attNames [i]; // Générer une branche basée sur les attributs de branche @SuppressWarnings ("Unchecked") Map <Object, Map <Object, List <nample>> Splits = / * New Line * / (Map <Object, Map <Object, List <nample>>>) RST [2]; pour (entrée <objet, map <objet, liste <nample>> Entrée: splits.entrySet ()) {objet attRvalue = entry.getKey (); Map <object, list <nample>> split = entry.getValue (); Object Child = GenerateDecisionTree (Split, SubA); Tree.Setchild (attrvalue, enfant); } return arbre; } / ** * Sélectionnez l'attribut de test optimal. Moyens optimaux que si la branche d'attribut de test sélectionnée est basée sur la branche d'attribut de test sélectionnée, la somme des informations requises pour la classification du nouvel échantillon * est déterminée à partir de chaque branche, ce qui est équivalent au gain d'informations maximum obtenu en déterminant l'attribut de test du nouvel échantillon * Retour à la table: Attribut Sélectionné Attribut, Somme d'informations, MAP (Valeur d'attribut -> (catégorie-> Échantillon) * / STATIC Objet STATIC [] Map <object, list <nample>> catégorieTOSamples, string [] attNames) {int minindex = -1; // Indice d'attribut optimal double minvalue = double.max_value; // Map d'informations minimales <Objet, carte <objet, liste <sample>> MINSPLITS = NULL; // Schéma de branche optimal // Pour chaque attribut, calculez la somme des informations requises pour déterminer la classification du nouvel échantillon dans chaque branche lorsqu'elle est utilisée comme attribut de test, et sélectionnez le minimum optimal pour (int attindex = 0; attindex <attnames.length; attindex ++) {int allCount = 0; // compteur pour compter le nombre total d'échantillons // Créer une carte en fonction de l'attribut actuel: Valeur d'attribut -> (Classification-> Exemple de liste) MAP <Objet, Map <Object, List <nample>> CursPlits = / * Nouvelle Line * / New Hashmap <Object, Map <Object, list <nample>>> (); pour (entrée <objet, list <nample>> Entrée: catégorieTOS. List <nample> sampes = entry.getValue (); pour (échantillon d'échantillon: échantillons) {objet attRvalue = échantillon .getAttribute (attnames [attRindex]); Map <object, list <nample>> split = cursplits.get (attvalue); if (split == null) {Split = new HashMap <objet, liste <nample>> (); cursplits.put (attrvalue, fraction); } List <nample> Splitsample = Split.get (catégorie); if (Splitsample == NULL) {Splitsample = new LinkedList <Sample> (); Split.put (catégorie, Splits échantillons); } Splits échantillons.add (échantillon); } allCount + = échantillons.size (); } // Calculez la somme des informations requises pour déterminer la classification du nouvel échantillon dans chaque branche lors de l'utilisation de l'attribut actuel comme attribut de test double courbure = 0,0; // COMPTER: accumuler chaque branche pour (map <objet, liste <nample>> Splits: cursplits.values ()) {double persplitCount = 0; for (list <nample> list: splits.values ()) PitplitCount + = list.size (); // Échantillons de branche de courant cumulatif double PitplitValue = 0,0; // COMPTEND: Branche actuelle pour (liste <nample> Liste: Splits.Values ()) {double p = list.size () / persplitCount; persplitValue - = p * (math.log (p) / math.log (2)); } CurValue + = (PROSPLITCOUNT / ALLCOUNT) * PARTPLITVALUE; } // Sélectionnez le minimum à optimal if (minValue> CurValue) {minindex = attIndex; minvalue = courbure; minSplits = cursplits; }} return nouvel objet [] {minindex, minValue, minSplits}; } / ** * Sortie l'arborescence de décision vers la sortie standard * / static void OutputDecisionTree (Object Obj, int Level, Object From) {for (int i = 0; i <level; i ++) System.out.print ("| ------"); if (from! = null) System.out.printf ("(% s):", de); if (obj instanceof arbre) {arbre arbre = (arbre) obj; String attName = Tree.getAttribute (); System.out.printf ("[% s =?] / N", attrname); for (object attRvalue: Tree.getAttributeValues ()) {object child = tree.getchild (attvalue); outputDecisionTree (enfant, niveau + 1, attraNa + "=" + attRvalue); }} else {System.out.printf ("[catégorie =% s] / n", obj); }} / ** * Exemple, contenant plusieurs attributs et une valeur de classification qui spécifie la classification à laquelle l'échantillon appartient * / STATIQUE Sample de classe {Private Map <String, Object> Attributs = new HashMap <String, Object> (); catégorie d'objets privés; objet public getAttribute (name de chaîne) {return attributes.get (name); } public void setAttribute (nom de chaîne, valeur objet) {attributs.put (name, valeur); } Objet public getCategory () {Retour catégorie; } public void setCategory (catégorie d'objet) {this.category = catégorie; } public String toString () {return attributes.toString (); }} / ** * Arbre de décision (nœud non-feuille), chaque nœud non-feuille de l'arborescence de décision conduit un arbre de décision * Chaque nœud non-feuille contient un attribut de branche et plusieurs branches. Chaque valeur de l'attribut de branche correspond à une branche. La branche guide une arborescence de sous-décision * / arbre de classe statique {attribut de chaîne privée; map privé <objet, objet> enfants = new hashmap <objet, objet> (); public arbre (String attribut) {this.attribute = attribut; } public String getAttribute () {return attribut; } public objet getChild (objet attRvalue) {return children.get (attrvalue); } public void setChild (objet attRvalue, objet enfant) {enfants.put (attrvalue, enfant); } public set <Bject> getAtTributeValues () {return children.KeySet (); }}}Résultats en cours:
Pour plus d'informations sur les algorithmes Java, les lecteurs qui sont intéressés par ce site peuvent afficher les sujets: "Structure de données Java et tutoriel d'algorithme", "Résumé des conseils de nœud de Dom Operation Java", "Résumé du fichier Java et des conseils d'opération de répertoire" et "Résumé des conseils d'opération Java Cache"
J'espère que cet article sera utile à la programmation Java de tous.