Dieser Artikel beschreibt den von Java implementierten Entscheidungsbaumalgorithmus. Teilen Sie es für Ihre Referenz wie folgt weiter:
Der Entscheidungsbaumalgorithmus ist eine Methode, um den Wert einer diskreten Funktion zu approximieren. Es handelt sich um eine typische Klassifizierungsmethode, die die Daten zuerst verarbeitet, den Induktionsalgorithmus verwendet, um lesbare Regeln und Entscheidungsbäume zu generieren und dann Entscheidungen zur Analyse neuer Daten zu verwenden. Im Wesentlichen sind Entscheidungsbäume der Prozess der Klassifizierung von Daten durch eine Reihe von Regeln.
Entscheidungsbaumkonstruktion kann in zwei Schritten durchgeführt werden. Der erste Schritt ist die Erzeugung des Entscheidungsbaums: der Prozess der Generierung des Entscheidungsbaums aus dem Trainingsprobensatz. Im Allgemeinen handelt es sich bei dem Trainings -Beispieldatensatz um einen Datensatz, der eine Geschichte und ein gewisses Maß an Vollständigkeit entsprechend den tatsächlichen Bedürfnissen aufweist und für die Datenanalyse und -verarbeitung verwendet wird. Der zweite Schritt ist das Beschneiden des Entscheidungsbaums: Das Beschneiden des Entscheidungsbaums ist ein Prozess der Überprüfung, Korrektur und Überarbeitung des in der vorherigen Phase erzeugten Entscheidungsbaums. Es wird hauptsächlich die Daten aus dem neuen Beispieldatensatz (als Testdatensatz bezeichnet) verwendet, um die vorläufigen Regeln zu überprüfen, die während des Erzeugungsprozesses des Entscheidungsbaums generiert wurden, und die Beschneidung der Zweige, die die Genauigkeit des Vorausgleichs beeinflussen.
Der Java -Implementierungscode lautet wie folgt:
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;public class DicisionTree { public static void main(String[] args) throws Exception { System.out.print("Wulin.com test Ergebnis:"); String [] attrnames = new String [] {"Alter", "Einkommen", "Student", "Credit_rating"}; // Lesen Sie die Beispiel -Set -Karte <Objekt, Liste <sample >> sample = readAmples (attrnames); // generieren Sie das Entscheidungsbaumobjekt entschiedene Tree = generateCisionTree (Beispiele, Attrnames); // Ausgabe des Entscheidungsbaums OutputDecisionTree (DecisionTree, 0, NULL); } / *** Lesen Sie den Beispielsatz, der klassifiziert wurde, und geben Sie die Karte zurück: Klassifizierung-> Liste der Samples, die zur Kategorie gehören "No", "Fair", "0" }, { "<30", "High", "No", "Excellent", "0" }, { "30-40", "High", "No", "Fair", "1" }, { ">40", "Medium", "No", "Fair", "1" }, { ">40", "Low", "Yes", "Fair ", "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 ". // Lesen Sie die Beispielattribute und deren Klassifizierungen, konstruieren Sie das Beispielobjekt, das das Beispiel darstellt, und teilen Sie die durch Klassifizierungskarte festgelegte Beispiel -Karte <Objekt, Liste <Beispiel >> ret = new HashMap <Objekt, Liste <Beispiel >> (); für (Objekt [] Zeile: rawdata) {sample sample = new sample (); int i = 0; für (int n = row.Length - 1; i <n; i ++) sample.setattribute (attrnames [i], row [i]); sample.setCategory (Zeile [i]); LIST <Sample> sample = ret.get (Zeile [i]); if (sample == null) {sample = new LinkedList <Samprobe> (); ret.put (row [i], proben); } proben.add (Probe); } return ret; } / *** Konstruieren Sie den Entscheidungsbaum* / statisches Objekt generateCisionTree (MAP <Objekt, Liste <sample >> categoryToSsamples, String [] attrnames) {// Wenn es nur eine Probe gibt, verwenden Sie die Klassifizierung, zu der die Probe als Klassifizierung der neuen Probe (kategorienmodell) gehört. // Wenn es kein Attribut für die Entscheidungsfindung gibt, wird die Klassifizierung mit den meisten Stichproben im Beispielsatz als Klassifizierung der neuen Stichprobe verwendet, dh für die Klassifizierung if (attrnames.length == 0) {int max = 0; Objekt maxcategory = null; für (Eintrag <Objekt, Liste <Beispiel >> Eintrag: CategoryToSsamples .EntrySet ()) {int cur = Eintrag.getValue (). Size (); if (cur> max) {max = cur; maxcategory = Eintrag.getKey (); }} return maxcategory; } // Wählen Sie das Testattributobjekt [] rst = wählen // Der Wurzelknoten des Entscheidungsbaums ist das Ast -Attribut der ausgewählte Testattributbaum = neuer Baum (Attrnames [(Ganzzahl) rST [0]]); // verwendete Testattribute sollten nicht als Testattribute ausgewählt werden String [] suba = new String [attrnames.length - 1]; für (int i = 0, j = 0; i <attrnames.length; i ++) if (i! = (integer) rst [0]) suba [j ++] = attrnames [i]; // Branch basierend auf Zweigattributen @SuppressWarnings ("deaktiviert") map <Objekt, Karte <Objekt, Liste <sample >>> Splits =/ * neue Zeile */(Karte <Objekt, Map <Objekt, Liste <Beispiel >>>) rst [2]; für (Eintrag <Objekt, Karte <Objekt, Liste <sample >>> Eintrag: Splits.EntrySet ()) {Object attrValue = Entry.getKey (); Karte <Objekt, Liste <sample >> split = Eintrag.getValue (); Object Child = generateCisionTree (split, suba); Tree.setchild (AttrValue, Kind); } Rückkehrbaum; } /*** Wählen Sie das optimale Testattribut aus. Optimale Mittelwerte, wenn der ausgewählte Testattributzweig auf dem ausgewählten Testattributzweig basiert, wird die Summe der für die Klassifizierung des neuen Stichprobe erforderlichen Informationen aus jedem Zweig ermittelt, der dem maximalen Informationsgewinn entspricht, der durch Ermittlung des Testattributs des neuen Beispiellistens der neuen Beispiele erhalten wird. Wählen SieBestTestAttribute (MAP <Objekt, Liste <sample >> categoryToSsamples, String [] attrnames) {int minIndex = -1; // optimales Attribut -Index double minValue = double.max_value; // Minimum Information Map <Objekt, Karte <Objekt, Liste <Beispiel >>> minsplits = null; // Berechnen Sie für jedes Attribut die Summe der Informationen, die zur Bestimmung der Klassifizierung der neuen Stichprobe in jedem Zweig bei der Verwendung als Testattribut erforderlich sind, und wählen Sie die minimale Optimal für (int attrindex = 0; attrindex <attrNames.Length; Attrindex ++) {int AllCount = 0; // Zähle zum Zählen der Gesamtzahl der Stichproben // Erstellen Sie eine Karte gemäß dem aktuellen Attribut: Attributwert-> (Klassifizierung-> Beispielliste) Karte <Objekt, Karte <Objekt, Liste <Beispiel >>> curSsplits =/ * neue Zeile */new HashMap <Objekt, Karte <Objekt, Liste <Beispiel >>> (); für (Eintrag <Objekt, Liste <Beispiel >> Eintrag: categoryToSsamples .EntrySet ()) {Objektkategorie = Eintrag.getKey (); LIST <Sample> sample = Eintrag.getValue (); für (Beispielprobe: Proben) {Objekt attrValue = sample .getAttribute (attrnames [attrindex]); Karte <Objekt, Liste <sample >> split = curSplits.get (attrValue); if (split == null) {split = new HashMap <Objekt, list <sample >> (); curSplits.put (attrValue, geteilt); } List <Samprobe> SplitSAmples = split.get (Kategorie); if (SplitsAmples == NULL) {SplitsAmples = new LinkedList <Samprobe> (); Split.put (Kategorie, SplitSsamples); } SplitsAmples.Add (Probe); } AllCount += Samples.size (); } // Berechnen Sie die Summe der Informationen, die zur Bestimmung der Klassifizierung der neuen Stichprobe in jedem Zweig erforderlich sind, wenn das aktuelle Attribut als Testattribut doppelte Curvalue = 0,0 verwendet wird; // Zähler: Akkumulieren Sie jeden Zweig für (Karte <Objekt, Liste <Beispiel >> Splits: curSplits.Values ()) {double ProsplitCount = 0; für (Liste <Sample> liste: Splits.Values ()) PRSPLITCOUNT += LIST.SIZE (); // kumulative Stromzweigproben doppelt PerflitValue = 0,0; // Zähler: Aktueller Zweig für (Liste <Sample> Liste: Splits.Values ()) {double p = list.size () / prosplitcount; PRSPLITVALUE -= P * (math.log (p) / math.log (2)); } curValue += (PRSPLITCOUNT / AllCount) * PRSPLITVALUE; } // Wählen Sie das Minimum bis optimal if (minValue> curvalue) {minIndex = attrindex; minValue = Curvalue; minsplits = curSplits; }} return New Object [] {minIndex, minValue, minsplits}; } / *** Ausgabe des Entscheidungsbaums in Standardausgabe* / static void outputDecisionTree (Objekt obj, int Level, Objekt aus) {für (int i = 0; i <stufe; i ++) system.out.print ("| ------"); if (von! = null) system.out.printf ("(%s):", von); if (obj Instance von Baum) {Baumbaum = (Baum) obj; String attrName = tree.getAttribute (); System.out.printf ("[%s =?]/N", attrName); für (Objekt attrValue: tree.getAttributeValues ()) {Object Child = Tree.getCild (attrValue); outputDecisionTree (Kind, Level + 1, attrname + "=" + attrValue); }} else {System.out.printf ("[category = %s]/n", obj); }} / *** Beispiel, das mehrere Attribute und einen Klassifizierungswert enthält, der die Klassifizierung angibt, zu der die Probe gehört* / statische Klasse Sample {private map <String, Objekt> Attribute = new Hashmap <string, Objekt> (); private Objektkategorie; public Object GetAtTribute (String -Name) {return satcrikte.get (name); } public void setAttribute (String -Name, Objektwert) {Attribute.put (Name, Wert); } öffentliches Objekt getCategory () {Rückgabekategorie; } public void setCategory (Objektkategorie) {this.category = category; } public String toString () {return attributes.toString (); }} /*** Entscheidungsbaum (Nicht-Blattknoten), jeder Nicht-Blattknoten im Entscheidungsbaum führt einen Entscheidungsbaum* Jeder Nicht-Blattknoten enthält ein Zweigattribut und mehrere Zweige. Jeder Wert des Ast -Attributs entspricht einem Zweig. Der Zweig führt einen Unterabteilungsbaum*/ statische Klassenbaum {private String-Attribut; private map <Objekt, Objekt> Kinder = new HashMap <Objekt, Objekt> (); öffentlicher Baum (String -Attribut) {this.attribute = Attribut; } public String getAtTribute () {returnattribut; } public Object getChild (Objekt attrValue) {return Children.get (attrValue); } public void setChild (ObjektattrValue, Objektkind) {children.put (attrValue, Kind); } public set <Object> getAtTributeValues () {return children.keyset (); }}}Auslaufergebnisse:
Für weitere Informationen zu Java -Algorithmen können Leser, die an dieser Website interessiert sind, die Themen "Java -Datenstruktur und Algorithmus -Tutorial", "Zusammenfassung der Java -Operation DOM -Knoten -Tipps", "Zusammenfassung der Java -Datei- und Verzeichnisoperationstipps" und "Zusammenfassung der Java -Cache -Operation Tipps" anzeigen
Ich hoffe, dieser Artikel wird für Java -Programme aller hilfreich sein.