Αλγόριθμος ID3

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση

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

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

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

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

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

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

O αλγόριθμος[Επεξεργασία | επεξεργασία κώδικα]

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

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

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


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

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

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