Αλγόριθμος ID3

Ο ID3 (Iterative Dichotomiser 3) είναι ένας αλγόριθμος, ο οποίος χρησιμοποιείται για να παραγάγει ένα δέντρο απόφασης.

Ο αλγόριθμος είναι βασισμένος στο Ξυράφι του Όκαμ: προτιμά τα μικρότερα δέντρα απόφασης (απλούστερες θεωρίες) από μεγαλύτερες. Εντούτοις, δεν παράγει πάντα το μικρότερο δέντρο, και για αυτό τον λόγο είναι ευρετικός. Το Ξυράφι του Όκαμ τυποποιείται χρησιμοποιώντας την έννοια της εντροπίας πληροφοριών:

$I_{E}(i)=-\sum _{j=1}^{m}f(i,j)\log f(i,j)$

Ο αλγόριθμος ID3 μπορεί να συνοψιστεί ως εξής:

1. Πάρτε όλες τις αχρησιμοποίητες ιδιότητες και υπολογίστε την εντροπία τους λαμβάνοντας υπόψη δείγματα δοκιμής
2. Επιλέξτε την ιδιότητα για την οποία η εντροπία είναι ελάχιστη
3. Δημιουργήστε έναν κόμβο που να περιέχει αυτή την ιδιότητα

Μια εξήγηση της υλοποίησης του ID3 μπορεί να βρεθεί στον αλγόριθμο C4.5, ο οποίος είναι μια επέκταση του ID3.

Ο αλγόριθμος

Ο πραγματικός αλγόριθμος είναι ο ακόλουθος:

ID3 (Παραδείγματα, Ιδιότητα_Στόχος, Ιδιότητες)

• Δημιούργησε ένα αρχικό κόμβο για το δέντρο
• Εάν όλα τα παραδείγματα είναι θετικά, Επέστρεψε την Ρίζα ως δέντρο με ένα κόμβο, με ετικέτα= +.
• Εάν όλα τα παραδείγματα είναι αρνητικά, Επέστρεψε την Ρίζα ως δέντρο με ένα κόμβο, με ετικέτα= -.
• Εάν ο αριθμός των προβλεπόμενων ιδιοτήτων είναι κενός, τότε Επέστρεψε την Ρίζα ως δέντρο με ένα κόμβο, με ετικέτα = την πιο κοινή τιμή της ιδιότητας-στόχου των παραδειγμάτων.
• Αλλιώς Ξεκίνα
  • A = Η ιδιότητα που κατηγοριοποιεί καλύτερα τα παραδείγματα.
  • Ιδιότητα Δέντρου απόφασης για τη ρίζα = A.
  • Για κάθε πιθανή τιμή, $v_{i}$, του A,
    • Πρόσθεσε ένα νέο κλάδο κάτω από τη Ρίζα, που να αντιστοιχεί στη δοκιμή A = $v_{i}$.
    • Θέσε Παραδείγματα($v_{i}$), ως το υποσύνολο των παραδειγμάτων που έχουν την τιμή $v_{i}$ για το A
    • Αν Παραδείγματα($v_{i}$) είναι κενό
      • Τότε κάτω από αυτό τον νέο κλάδο πρόσθεσε έναν κόμβο-φύλλο με ετικέτα = την πιο κοινή τιμή στόχο στα παραδείγματα
    • Αλλιώς κάτω από αυτό τον νέο κλάδο πρόσθεσε το υποδέντρο ID3 (Παραδείγματα($v_{i}$), Ιδιότητα_Στόχος, Ιδιότητες – {A})
• Τέλος
• Επέστρεψε Ρίζα

Το αρχικό κείμενο του άρθρου αυτού είναι μετάφραση του αντίστοιχου αρχικού κειμένου της Αγγλικής Wikipedia.

Εξωτερικοί σύνδεσμοι

• Σεμινάρια - http://www2.cs.uregina.ca/
• Περιγραφή και παραδείγματα - http://www.cise.ufl.edu/
• Περιγραφή και παραδείγματα - http://www.cis.temple.edu/
• Υλοποίηση του ID3 σε Python Αρχειοθετήθηκε 2008-12-12 στο Wayback Machine.
• Υλοποίηση του ID3 σε Ruby
• Υλοποίηση του ID3 σε C# - https://web.archive.org/web/20061109050158/http://www.codeproject.com/cs/algorithms/id3.asp
• Δέντρα απόφασης Perl Module - Υλοποίηση του ID3 σε Perl

Αναφορές

• Mitchell, Tom M. Machine Learning. McGraw-Hill, 1997.