ART

 

.

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

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

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

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

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

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

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

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


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

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

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

Αναφορές

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

Εγκυκλοπαίδεια Πληροφορικής

Κόσμος

Αλφαβητικός κατάλογος

Hellenica World - Scientific Library

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License