Optimaler Entscheidungsbaum: Datenschnittstelle
Warning: preg_match(): Compilation failed: group name must start with a non-digit at offset 8 in /www/htdocs/w0102873/mediawiki/includes/MagicWord.php on line 739
Aus It2010-g1
Segr (Diskussion | Beiträge) (→gewichtete Entropie) |
Chge (Diskussion | Beiträge) (→Entscheidungsbaum) |
||
| Zeile 3: | Zeile 3: | ||
Die Daten die in unserem Projekt verarbeitet werden sollen, liegen zunächst in Form einer Tabelle vor. | Die Daten die in unserem Projekt verarbeitet werden sollen, liegen zunächst in Form einer Tabelle vor. | ||
Diese Tabelle muss irgendwie in Java abgebildet werden. | Diese Tabelle muss irgendwie in Java abgebildet werden. | ||
| − | Diese Datenorganisation bildet dann auch die Schnittstelle zu unseren Export | + | Diese Datenorganisation bildet dann auch die Schnittstelle zu unseren Export- und Import-Klassen. |
| − | + | ||
| − | + | ||
| + | In einem weiteren Schritt müssen die Daten noch in eine Baumstruktur gewandelt werden. | ||
== Repräsentation der Tabellendaten == | == Repräsentation der Tabellendaten == | ||
| Zeile 12: | Zeile 11: | ||
In Java könnte eine Tabelle folgendermaßen abgebildet werden: | In Java könnte eine Tabelle folgendermaßen abgebildet werden: | ||
| − | Jeder Zeile ist ein Listenelement, | + | Jeder Zeile ist ein Listenelement, welches wiederum eine Liste ist, das allen zu dieser Zeile gehören Spaltenattribute enthält. |
| − | Es gibt | + | Es gibt also eine Liste in einer Liste und kann daher ähnlich angesprochen werden wie ein Koordinatensystem. |
== Aufbau eines Baums == | == Aufbau eines Baums == | ||
| − | Bäume | + | Bäume werden in diesem Projekt wie folgt dargestellt:<br> |
| − | Es gibt eine Klasse die einen Knoten | + | Es gibt eine Klasse die einen Knoten repräsentiert. Ein solcher Knoten hat als Attribute einen Namen, ein Daten-Objekt und eine Liste von weiteren Knoten, die dann seine Kind-Knoten darstellen. Um einfacher mit einem Baum arbeiten zu können, ist in jedem Knoten zusätzlich auch der Eltern-Knoten hinterlegt.<br> |
Um den Baum anzusprechen oder zu kopieren, wird der Root-Knoten angesprochen. | Um den Baum anzusprechen oder zu kopieren, wird der Root-Knoten angesprochen. | ||
== Entscheidungsbaum == | == Entscheidungsbaum == | ||
| − | Um Entscheidungsbäume darzustellen wurde eine Klasse für dessen Knoten implementiert, | + | Um Entscheidungsbäume darzustellen wurde eine Klasse für dessen Knoten implementiert, welche von der Klasse der Baumknoten erbt. Diese speichert zusätzlich noch die zugehörige Tabelle, den Attributnamen des Knoten und das Ziel-Attribut.<br> |
| − | Weiter bietet es Methoden zur Berechnung der Entropie, zur Berechnung der gewichteten Entropie und zur | + | Weiter bietet es Methoden zur Berechnung der Entropie, zur Berechnung der gewichteten Entropie und zur Erstellung eines optimalen Entscheidungsbaumes, ausgehend von sich selbst.<br> |
=== Entropie === | === Entropie === | ||
| − | Die Entopie eines Knotens | + | Die Entopie eines Knotens wird von der Methode calculateEntropy() wiefolgt berechnet: [[Datei:Formel_Entropie.png]]<br> |
Dabei ist '''n''' die Anzahl der verschiedenen Werte des Zielattributes in dem Knoten,<br> | Dabei ist '''n''' die Anzahl der verschiedenen Werte des Zielattributes in dem Knoten,<br> | ||
'''x_n''' die Anzahl der Elemente des Knotens, die den n-ten Zielattributwert besitzen und<br> | '''x_n''' die Anzahl der Elemente des Knotens, die den n-ten Zielattributwert besitzen und<br> | ||
'''y''' die Anzahl aller Elemente des Knotens. | '''y''' die Anzahl aller Elemente des Knotens. | ||
| + | |||
=== gewichtete Entropie === | === gewichtete Entropie === | ||
| − | Die gewichtete Entropie eines Knotens wird mit folgender Formel berechnet: [[Datei:Formel_gewichtete_Entropie.png]]<br> | + | Die gewichtete Entropie eines Knotens wird mit folgender Formel von der Methode calculateWeightedEntropy() berechnet: [[Datei:Formel_gewichtete_Entropie.png]]<br> |
Dabei ist '''n''' die Anzahl der Kinder des Knotens,<br> | Dabei ist '''n''' die Anzahl der Kinder des Knotens,<br> | ||
'''x_n''' die Anzahl der Elemente des n-ten Kindes,<br> | '''x_n''' die Anzahl der Elemente des n-ten Kindes,<br> | ||
'''y''' die Anzahl der Elemente des Knotens und<br> | '''y''' die Anzahl der Elemente des Knotens und<br> | ||
'''z_n''' die Entropie des n-ten Knotens. | '''z_n''' die Entropie des n-ten Knotens. | ||
| + | |||
=== Generierung eines Optimalen Entscheidungsbaumes === | === Generierung eines Optimalen Entscheidungsbaumes === | ||
Ein optimaler Entscheidunsbaum wird von der Methode generateOptimizedTree(), wie im nachfolgendem Diagramm dargestellt, erzeugt.<br> | Ein optimaler Entscheidunsbaum wird von der Methode generateOptimizedTree(), wie im nachfolgendem Diagramm dargestellt, erzeugt.<br> | ||
[[Datei:Flussdiagramm_generateOptimizedTree.png]] | [[Datei:Flussdiagramm_generateOptimizedTree.png]] | ||
