Ταξινόμηση δέντρου απόφασης

Εισαγωγή

Τα Δέντρα Αποφάσεων (DT) είναι μια μη παραμετρική εποπτευόμενη μέθοδος μάθησης που χρησιμοποιείται για ταξινόμηση και παλινδρόμηση. Ο στόχος είναι να δημιουργηθεί ένα μοντέλο που προβλέπει την τιμή μιας μεταβλητής στόχου μαθαίνοντας απλούς κανόνες απόφασης που συνάγονται από τα χαρακτηριστικά δεδομένων.

Εντροπία

Ο στόχος της εκπαίδευσης είναι να βρεθούν οι καλύτερες διασπάσεις στους κόμβους προκειμένου να βρεθεί το βέλτιστο δέντρο. Οι διαχωρισμοί γίνονται χρησιμοποιώντας ορισμένα κριτήρια όπως: Εντροπία.

Υπάρχουν πολλοί ορισμοί της εντροπίας όπως:

Η εντροπία αντιστοιχεί στην ποσότητα των πληροφοριών που περιέχονται σε μια πηγή πληροφοριών.
Η εντροπία μπορεί επίσης να θεωρηθεί ως η τυχαιότητα ή η μέτρηση της έκπληξης σε ένα σύνολο.
Η εντροπία είναι μια μέτρηση που μετρά το απρόβλεπτο ή την ακαθαρσία στο σύστημα.

Στα δέντρα απόφασης, θα θεωρήσουμε την εντροπία ως το μέτρο της καθαρότητας μέσα σε έναν κόμβο. Ο στόχος του μοντέλου δέντρου απόφασης είναι να μειώσει την εντροπία των κόμβων σε κάθε διάσπαση:

Έτσι, θέλουμε να μεγιστοποιήσουμε τη διαφορά μεταξύ της εντροπίας του γονικού κόμβου και της εντροπίας των θυγατρικών κόμβων. Αυτή η διαφορά ονομάζεται Κέρδος πληροφοριών.

Η Εντροπία $H$ ενός συνόλου $X$ διατυπώνεται μαθηματικά ως εξής:

H(X) = - \sum\limits\_{x \in X} p(x) \log p(x)

Κέρδος πληροφοριών

Το κέρδος πληροφοριών είναι η διαφορά μεταξύ της εντροπίας του γονικού κόμβου και του σταθμισμένου αθροίσματος των εντροπιών των κόμβων chlid, και επομένως μπορεί να διατυπωθεί ως εξής:

$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$

$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$

που:

Το $H(.)$ είναι η εντροπία.
Το $Y$ είναι ο πληθυσμός πριν από τη διαίρεση, αντιπροσωπεύει τον γονικό κόμβο.
Η $X$ είναι η μεταβλητή που θέλουμε να χρησιμοποιήσουμε για τον διαχωρισμό.
Το $x$ είναι μια μοναδική τιμή του X.
Το $Y[X==x]$ είναι μια διαχωρισμένη λίστα με μόνο τιμές $x$ .

ας πάρουμε ένα σωστό παράδειγμα:

Θα υπολογίσουμε το κέρδος πληροφοριών όταν διαιρούμε τον γονικό κόμβο χρησιμοποιώντας τις τιμές του X:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

Αρχικά, υπολογίζουμε την εντροπία του γονικού κόμβου:

$H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow)$

$= - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3$

Στη συνέχεια, θα υπολογίσουμε την εσωτερική πιθανότητα κάθε θυγατρικού κόμβου μετά τη διαίρεση χρησιμοποιώντας τις μοναδικές τιμές του X:

$unique(X) = [Circle, Square]$

$\sum\_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square)$

$+ P(Circle|X) \times H(Y | X = Circle)$

$= \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle)$

Οπως:

$H(Y | X = Τετράγωνο)$ : αντιπροσωπεύει την εντροπία του πρώτου θυγατρικού κόμβου.
$H(Y | X = Circle)$ : αντιπροσωπεύει την εντροπία του δεύτερου θυγατρικού κόμβου.

Ξεκινάμε με τον πρώτο θυγατρικό κόμβο:

$H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square)$

$- P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square)$

$= - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23$

Και μετά ο δεύτερος θυγατρικός κόμβος:

$H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle)$

$- P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle)$

$= - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28$

Τέλος, αντικαθιστούμε τις εντροπίες στον τύπο κέρδους πληροφοριών:

$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$

$= 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041$

Όπως αναφέρθηκε προηγουμένως, ο στόχος ενός διαχωρισμού κόμβου είναι να μεγιστοποιήσει το Κέρδος Πληροφοριών και έτσι να ελαχιστοποιήσει την Εντροπία στον προκύπτον θυγατρικό κόμβο. Για να γίνει αυτό, πρέπει να προσπαθήσουμε να χωρίσουμε τον κόμβο με διαφορετικά σύνολα εισόδων $X_1, X_2, \ldots, Xn$ και διατηρούμε μόνο τη διαίρεση που μεγιστοποιεί το κέρδος πληροφοριών:

$X^{\*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i)$

Πότε να σταματήσετε να χωρίζετε

Ο κόμβος που χωρίζει σε δέντρα απόφασης είναι αναδρομικός, επομένως πρέπει να υπάρχει ένα κριτήριο που μπορούμε να χρησιμοποιήσουμε για να σταματήσουμε τη διαίρεση. Αυτά είναι μερικά από τα πιο εφαρμοσμένα κριτήρια:

Όταν ο κόμβος είναι καθαρός: Η(κόμβος) = 0. Είναι άσκοπο να χωρίσουμε περαιτέρω τον κόμβο.
Μέγιστος αριθμός βάθους: Μπορούμε να ορίσουμε ένα μέγιστο βάθος που μπορεί να φτάσει το μοντέλο, αυτό σημαίνει ότι ακόμα κι αν ο κόμβος δεν είναι καθαρός, η διαίρεση διακόπτεται.
Ελάχιστος αριθμός δειγμάτων ανά κόμβο: Μπορούμε επίσης να ορίσουμε έναν ελάχιστο αριθμό $N$ δειγμάτων ανά κόμβο. Εάν ο αριθμός των δειγμάτων ανά κόμβο είναι ίσος με $N$ , τότε σταματάμε να χωρίζουμε ακόμα κι αν ο κόμβος δεν είναι καθαρός.

Στο τέλος της εκπαίδευσης (το διαχωρισμό), κάθε κόμβος που βασίζεται στο τέλος του δέντρου αποφάσεων ονομάζεται "Φύλλο", επειδή δεν είναι ρίζα σε κανένα υποδέντρο. Κάθε φύλλο θα αντιπροσωπεύει την απόδοση της κατηγορίας με τα περισσότερα δείγματα.

Συμπέρασμα

Το δέντρο αποφάσεων είναι ένας από τους πιο διάσημους αλγόριθμους μηχανικής μάθησης λόγω της αποτελεσματικότητάς του, του διαισθητικού υποβάθρου και της απλής εφαρμογής του. Αυτός ο αλγόριθμος μπορεί περαιτέρω να χρησιμοποιηθεί με αριθμητικές ανεξάρτητες μεταβλητές (Gaussian Decision Tree) και μπορεί να επεκταθεί για την επίλυση εργασιών παλινδρόμησης επίσης.