ID3 Algorithmus

[LuckyLan]

Hallo liebes Java-Forum,

Ich hätte eine Frage wegen einer Implementierung von einem ID3 Algorithmusses.



Wir sollen diese Funktion rekursiv verwenden, um den ID3 Algorithmus zu implementieren.

Die Klasse CSVAttribute enthält:

11 Attribute, wobei eines das Klassenlabel darstellt
(ist glaube ich für meine Frage allerdings nicht wichtig)

Die Klasse DecisionTreeNode enthält:

DecisionTreeNode parent,
int attributindex (die position des attributes, das durch die node dargestellt wird)
HashMap<String, DecisionTreeNode> splits (enthält alle Kinder der Node)


Mein Problem ist folgendes:

Wie setze ich im ersten Aufruf das Parent, so dass bei der Rekursion keine Probleme auftreten?

Ich hatte bis jetzt n.setParent(n.getParent()), was aber keinen Sinn macht

MfG
LuckyLan

 

[mihe7]

createTree erzeugt ja einen Baum. Der Wurzelknoten des Baums hat keinen Vaterknoten. D. h. createTree liefert einen Knoten, der keinen Vaterknoten hat. Um diesen Knoten t als Wurzel eines Teilbaums an einen Knoten v zu hängen, setzt Du eben den Vaterknoten von t auf v (und fügst natürlich t als Kind von v ein).

 

[LuckyLan]

Könntest du vielleicht genauer erklären, wen du mit t und v meinst?


Bin ich mit meinen Überlegungen auf dem richtigen Weg?
Ich soll in dem ersten Aufruf (vor der Rekursion) den Knoten v erstellen und dem Knoten t (was ein Kind von v ist) v als Parent hinzufügen?

Würde ich dann nicht in dem ersten rekursiven Aufruf schwierigkeiten bekommen, falls ich auf v oder t zugreifen wollen würde?
Derzeit sollte mein Code keine Möglichkeit darbieten, dass ich darauf zugreifen kann, weil ich keine Node übergebe.

 

[mihe7]

Nein, nicht vor dem ersten Aufruf.

Skizze für einen willkürlich gewählten Baum:

// createTree erzeugt einen Baum und liefert dessen Wurzel zurück.
// Die Wurzel hat keinen Parent.
Node createTree(String text) {
    // wenn der Text aus höchstens einem Zeichen besteht,
    // besteht der Baum nur aus der Wurzel, die den Text enthält
    if (text.length() < 2) {
        return new Node(text);
    }

    // Ansonsten besteht die Wurzel des Baums aus dem "mittleren Zeichen"
    int center = text.length() / 2;
    Node root = new Node(text.substring(center, center+1));
   
    // Für die Elemente, die links vom "mittleren Element" stehen, erzeugen wir einen Baum,
    // dessen Wurzel wir in leftTree speichern
    Node leftTree = createTree(text.substring(0, center));
   
    // Für die Elemente, die rechts vom "mittleren Element" stehen, erzeugen wir einen Baum,
    // dessen Wurzel wir in rightTree speichern
    Node rightTree = createTree(text.substring(center+1, text.length()));

    // Wir hängen nun leftTree und rightTree an root an.
    root.left = leftTree;
    leftTree.parent = root;
    root.right = rightTree;
    rightTree.parent = root;

    return root; // wir geben die Wurzel des neu erzeugten Baums zurück
}

 

[LuckyLan]

Nein, nicht vor dem ersten Aufruf.

Skizze für einen willkürlich gewählten Baum:

// createTree erzeugt einen Baum und liefert dessen Wurzel zurück.
// Die Wurzel hat keinen Parent.
Node createTree(String text) {
    // wenn der Text aus höchstens einem Zeichen besteht,
    // besteht der Baum nur aus der Wurzel, die den Text enthält
    if (text.length() < 2) {
        return new Node(text);
    }

    // Ansonsten besteht die Wurzel des Baums aus dem "mittleren Zeichen"
    int center = text.length() / 2;
    Node root = new Node(text.substring(center, center+1));
  
    // Für die Elemente, die links vom "mittleren Element" stehen, erzeugen wir einen Baum,
    // dessen Wurzel wir in leftTree speichern
    Node leftTree = createTree(text.substring(0, center));
  
    // Für die Elemente, die rechts vom "mittleren Element" stehen, erzeugen wir einen Baum,
    // dessen Wurzel wir in rightTree speichern
    Node rightTree = createTree(text.substring(center+1, text.length()));

    // Wir hängen nun leftTree und rightTree an root an.
    root.left = leftTree;
    leftTree.parent = root;
    root.right = rightTree;
    rightTree.parent = root;

    return root; // wir geben die Wurzel des neu erzeugten Baums zurück
}

Ich habe mein Problem nicht vollständig beschrieben.
Auf das Beispiel des willkürlichen Baumes würde das wie folgt aussehen:

Falls der Text 0 Zeichen enthält, gib die Parentnode aus

Und um das zu lösen, braucht man doch einen Zugriff auf die Parentnode. Nur weiß ich nicht, wie man einen Zugriff bekommen kann, ohne eine weitere Funktion zu erstellen, die die Parentnode übergibt.

 

[mihe7]

Falls der Text 0 Zeichen enthält, gib die Parentnode aus

In dem Fall würde im Parent geprüft, ob ein erneuter Aufruf von createTree 0 Zeichen zur Folge hätte und dann würde der Aufruf einfach unterlassen

Zum Beispiel vor Zeile 16

if (center != 0)[/icode] einfügen.

 

[LuckyLan]

Ich glaube du verstehst mich da leider etwas falsch.

Falls der Text 0 Zeichen enthält, gibt die Parentnode aus, müsste in Code ungefähr so aussehen:

If(text==0)return this.parent

Bloß sollte dieser Aufruf nicht funktionieren, weil wir das Parent noch nicht gesetzt haben oder liege ich falsch?

 

[mihe7]

Sorry, dass ich erst jetzt antworte, das ist heute irgendwie untergangen.

Ich glaube du verstehst mich da leider etwas falsch.

Das ist durchaus möglich. Allerdings wüsste ich nicht, warum man in einer Methode createTree den Parent einer Wurzel zurückgeben sollte, zumal klar ist, dass es diesen nicht gibt.