Δέντρα Απόφασης — Εντροπία, Gini & Random Forest

Ένα δέντρο απόφασης προβλέπει κάνοντας μια ακολουθία ερωτήσεων όπως «ολοκλήρωσε το practice quiz;» ή «εισόδημα πάνω από $50{,}000$;». Σε ένα δέντρο ταξινόμησης, η καλύτερη ερώτηση είναι συνήθως εκείνη που κάνει τους θυγατρικούς κόμβους λιγότερο ανακατεμένους από τον γονικό κόμβο. Εδώ μπαίνουν η εντροπία και η ακαθαρσία Gini.

Τα random forests χρησιμοποιούν την ίδια βασική ιδέα, αλλά παίρνουν τον μέσο όρο πολλών δέντρων αντί να βασίζονται σε ένα μόνο δέντρο. Αν χρειάζεσαι μόνο τη βασική ιδέα, κράτα αυτό: η εντροπία και το Gini βοηθούν ένα δέντρο να επιλέγει διαχωρισμούς, και ένα random forest βοηθά να μειωθεί η αστάθεια ενός μεμονωμένου δέντρου.

Δέντρα Απόφασης, Εντροπία και Gini: Τι Μετρούν

Η εντροπία και η ακαθαρσία Gini είναι και οι δύο τρόποι να βαθμολογήσεις το πόσο ανακατεμένος είναι ένας κόμβος ταξινόμησης.

Αν ένας κόμβος περιέχει πιθανότητες κλάσεων $p_1, p_2, \dots, p_k$, τότε ένας συνηθισμένος τύπος για την εντροπία είναι

$$H = -\sum_{i=1}^k p_i \log_2 p_i$$

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

Η ακαθαρσία Gini είναι

$$G = 1 - \sum_{i=1}^k p_i^2$$

Και οι δύο δείκτες είναι $0$ όταν ένας κόμβος είναι απολύτως καθαρός. Και οι δύο μεγαλώνουν όταν οι κλάσεις είναι πιο ανακατεμένες.

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

Πώς Ένα Δέντρο Απόφασης Επιλέγει Διαχωρισμό

Για την εντροπία, ένας συνηθισμένος κανόνας είναι το information gain:

$$\text{Information Gain} = H(\text{parent}) - \sum_j \frac{n_j}{n} H(\text{child}_j)$$

Εδώ, το $n$ είναι ο αριθμός των δειγμάτων στον γονικό κόμβο και το $n_j$ είναι ο αριθμός στον θυγατρικό κόμβο $j$.

Για το Gini, η ιδέα είναι παράλληλη: υπολόγισε τη σταθμισμένη ακαθαρσία των θυγατρικών κόμβων και προτίμησε τον διαχωρισμό που τη μειώνει περισσότερο.

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

Λυμένο Παράδειγμα: Εντροπία και Gini για Έναν Διαχωρισμό

Έστω ότι ένας κόμβος περιέχει $6$ παραδείγματα εκπαίδευσης για μια πρόβλεψη επιτυχίας/αποτυχίας:

• $3$ είναι Επιτυχία
• $3$ είναι Αποτυχία

Άρα ο γονικός κόμβος είναι ισομερώς ανακατεμένος.

Η εντροπία του είναι

$$H_{\text{parent}} = -\frac{3}{6}\log_2\left(\frac{3}{6}\right) - \frac{3}{6}\log_2\left(\frac{3}{6}\right) = 1$$

Η ακαθαρσία Gini του είναι

$$G_{\text{parent}} = 1 - \left(\frac{3}{6}\right)^2 - \left(\frac{3}{6}\right)^2 = 0.5$$

Τώρα δοκίμασε τον διαχωρισμό «ολοκλήρωσε το practice quiz;»

• Κλάδος Ναι: $4$ παραδείγματα, με $3$ Επιτυχία και $1$ Αποτυχία
• Κλάδος Όχι: $2$ παραδείγματα, με $0$ Επιτυχία και $2$ Αποτυχία

Για τον κλάδο Ναι,

$$H_{\text{yes}} = -\frac{3}{4}\log_2\left(\frac{3}{4}\right) - \frac{1}{4}\log_2\left(\frac{1}{4}\right) \approx 0.811$$

και

$$G_{\text{yes}} = 1 - \left(\frac{3}{4}\right)^2 - \left(\frac{1}{4}\right)^2 = 0.375$$

Για τον κλάδο Όχι, ο κόμβος είναι καθαρός, άρα

$$H_{\text{no}} = 0, \qquad G_{\text{no}} = 0$$

Η σταθμισμένη εντροπία μετά τον διαχωρισμό είναι

$$\frac{4}{6}(0.811) + \frac{2}{6}(0) \approx 0.541$$

Άρα το information gain είναι

$$1 - 0.541 \approx 0.459$$

Η σταθμισμένη τιμή Gini μετά τον διαχωρισμό είναι

$$\frac{4}{6}(0.375) + \frac{2}{6}(0) = 0.25$$

Άρα η μείωση Gini είναι

$$0.5 - 0.25 = 0.25$$

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

Γιατί τα Δέντρα Απόφασης Βγάζουν Διαισθητικά Νόημα

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

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

Γιατί τα Random Forests Συχνά Λειτουργούν Καλύτερα

Ένα μεμονωμένο δέντρο είναι εύκολο στην ερμηνεία, αλλά μπορεί να είναι ασταθές. Μια μικρή αλλαγή στα δεδομένα μπορεί να παράγει αισθητά διαφορετικό δέντρο.

Ένα random forest μειώνει αυτή την αστάθεια χτίζοντας πολλά δέντρα αντί για ένα. Η συνηθισμένη συνταγή είναι:

• δειγματοληψία των δεδομένων εκπαίδευσης με επανάθεση για κάθε δέντρο
• εξέταση μόνο ενός τυχαίου υποσυνόλου χαρακτηριστικών σε κάθε διαχωρισμό
• συνδυασμός των προβλέψεων από όλα τα δέντρα

Για ταξινόμηση, το forest συνήθως προβλέπει με πλειοψηφική ψήφο. Για παλινδρόμηση, συνήθως παίρνει τον μέσο όρο των εξόδων των δέντρων.

Το συμβιβαστικό σημείο είναι απλό. Ένα random forest είναι συχνά πιο ακριβές και πιο σταθερό από ένα μεμονωμένο δέντρο, αλλά είναι πιο δύσκολο να εξηγηθεί ως ένα καθαρό σύνολο κανόνων.

Συνηθισμένα Λάθη με τα Δέντρα Απόφασης

Αντιμετώπιση της Εντροπίας και του Gini ως Διαφορετικά Είδη Πρόβλεψης

Είναι κριτήρια διαχωρισμού, όχι ξεχωριστές οικογένειες μοντέλων. Το μοντέλο παραμένει δέντρο απόφασης και στις δύο περιπτώσεις.

Παράβλεψη της Συνθήκης της Ταξινόμησης

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

Υπερβολική Αναζήτηση Τέλειας Καθαρότητας

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

Υπόθεση ότι το Random Forest Εξηγεί Από Μόνο του τον Εαυτό του

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

Πότε να Χρησιμοποιήσεις Δέντρο Απόφασης ή Random Forest

Τα δέντρα απόφασης εμφανίζονται σε εργασίες ταξινόμησης και παλινδρόμησης στα οικονομικά, την ιατρική, τις λειτουργίες, το marketing και πολλές άλλες εφαρμοσμένες περιοχές. Είναι χρήσιμα όταν η σχέση ανάμεσα στις εισόδους και τις εξόδους δεν περιγράφεται καλά από ένα γραμμικό μοντέλο και όταν έχουν σημασία οι εξηγήσεις σε μορφή κανόνων.

Χρησιμοποίησε ένα μεμονωμένο δέντρο όταν η ερμηνευσιμότητα έχει τη μεγαλύτερη σημασία και χρειάζεται να εξετάσεις τη διαδρομή της απόφασης. Χρησιμοποίησε ένα random forest όταν η ποιότητα πρόβλεψης και η σταθερότητα έχουν μεγαλύτερη σημασία από το να έχεις ένα συμπαγές δέντρο που μπορείς να διαβάσεις γραμμή προς γραμμή.

Δοκίμασε Ένα Παρόμοιο Πρόβλημα

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