Παλινδρόμηση Δέντρου Αποφάσεων από την Αρχή: Θεωρία και Πράξη

Home » Python » Παλινδρόμηση Δέντρου Αποφάσεων από την Αρχή: Θεωρία και Πράξη

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

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

Τι είναι ένα δέντρο αποφάσεων και γιατί είναι τόσο εύχρηστο;

Ένα δέντρο αποφάσεων είναι ουσιαστικά μια ροή ερωτήσεων ναι/όχι (ή απλών κανόνων) που σας καθοδηγεί από μια ριζική απόφαση μέχρι μια τελική πρόβλεψη σε έναν κόμβο φύλλου. Σε ένα τυπικό περιβάλλον εποπτευόμενης μάθησης, ο στόχος είναι η πρόβλεψη μιας μεταβλητής-στόχου Y χρησιμοποιώντας πολλαπλούς προγνωστικούς παράγοντες (χαρακτηριστικά, συνμεταβλητές) και το δέντρο μαθαίνει μια ακολουθία ερωτήσεων όπως «είναι το βάρος ≤ 103;» ή «είναι η χώρα στις {ΗΠΑ, Ηνωμένο Βασίλειο, Καλιφόρνια};» που σταδιακά διαιρεί τα δεδομένα σε πιο ομοιογενείς ομάδες.

Για να πάρετε μια ιδέα, φανταστείτε ότι θέλετε να προβλέψετε εάν κάποιος είναι παχύσαρκος χρησιμοποιώντας μόνο το ύψος και το βάρος και έχετε ένα σύνολο δεδομένων με ετικέτες που σας λέει ποιος είναι παχύσαρκος και ποιος όχι. Ένα δέντρο μπορεί να ανακαλύψει έναν κανόνα όπως «αν βάρος > 100 κιλά, πρόβλεψη παχυσαρκίας», αλλά αυτός ο κανόνας δεν θα είναι τέλειος: ορισμένα άτομα άνω των 100 κιλών δεν θα είναι παχύσαρκα, ενώ ορισμένα άτομα κάτω από αυτό το όριο θα είναι. Στη συνέχεια, το δέντρο συνεχίζει να προσθέτει περισσότερες ερωτήσεις (υποδιαιρέσεις), για παράδειγμα σχετικά με το ύψος ή ένα εκλεπτυσμένο όριο βάρους, για να «βελτιστοποιήσει» αυτές τις αρχικές πρόχειρες προβλέψεις.

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

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

Δέντρα ταξινόμησης έναντι δέντρων παλινδρόμησης

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

Σε ένα δέντρο παλινδρόμησης, ο συνήθης στόχος είναι η διαίρεση του χώρου χαρακτηριστικών σε περιοχές όπου η απόκριση μπορεί να προσεγγιστεί από μια σταθερά, συχνά τον μέσο όρο των παρατηρήσεων σε αυτήν την περιοχή. Οι τυπικοί κανόνες απόφασης έχουν τη μορφή «είναι x»_k ≤ c;", όπου x_k είναι μία από τις συνμεταβλητές και το c είναι ένα κατώφλι. Αυτοί οι κανόνες διαιρούν επανειλημμένα τον χώρο σε υπερορθογώνια και όλα τα σημεία στο ίδιο υπερορθογώνιο μοιράζονται την ίδια προβλεπόμενη τιμή ŷ.

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

Παρά τις διαφορές αυτές στον τύπο στόχου, από την άποψη της κωδικοποίησης, μπορείτε να εφαρμόσετε μια ενιαία γενική δομή δέντρου και απλώς να προσθέσετε διαφορετικά μέτρα πρόσμειξης ή απώλειας ανάλογα με το αν κάνετε παλινδρόμηση ή ταξινόμηση. Αργότερα, όταν υπολογίζουμε το Information Gain, θα δείτε ότι οι τύποι για την ταξινόμηση (με βάση την εντροπία) και την παλινδρόμηση (με βάση τη διακύμανση) είναι παράλληλοι ως προς το πνεύμα.

Συναρτήσεις προσμίξεων και κόστους σε δέντρα αποφάσεων

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

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

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

Δείκτης Gini: μέτρηση ακαθαρσιών σε δέντρα ταξινόμησης

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

Αν ένας κόμβος περιέχει κλάσεις με πιθανότητες P₁, P₂, … , Π_n, ο δείκτης Gini υπολογίζεται ως Gini = 1 − Σ (P_i)². Όταν ένας κόμβος είναι απόλυτα καθαρός (όλες οι παρατηρήσεις ανήκουν στην ίδια κατηγορία), μία από τις πιθανότητες είναι 1 και οι υπόλοιπες είναι 0, επομένως το άθροισμα των τετραγώνων είναι 1 και ο δείκτης Gini είναι 0, υποδεικνύοντας πλήρη καθαρότητα.

Από την άλλη πλευρά, ο δείκτης Gini φτάνει στο μέγιστο όταν οι κλάσεις αναμειγνύονται ομοιόμορφα μέσα στον κόμβο, για παράδειγμα σε ένα δυαδικό πρόβλημα με P₁ = Ρ₂ = 0.5, που δίνει Gini = 1 − (0.5² + 0.5²) = 0.5. Σε αυτήν την περίπτωση, η πρόβλεψη της κλάσης πλειοψηφίας είναι όσο κακή γίνεται για αυτήν την κατανομή, επειδή ο κόμβος περιέχει το μισό από κάθε κλάση.

Όταν εφαρμόζετε την Gini σε κώδικα, συνήθως λαμβάνετε το διάνυσμα ετικέτας για τον κόμβο, υπολογίζετε τη συχνότητα κάθε κλάσης, μετατρέπετε τις συχνότητες σε πιθανότητες και στη συνέχεια εφαρμόζετε τον τύπο 1 − Σ p². Αν το κάνετε αυτό για πολλαπλές υποψήφιες διαιρέσεις, μπορείτε να συγκρίνετε ποια διάσπαση παράγει παιδιά με χαμηλότερο σταθμισμένο μέσο όρο πρόσμειξης Gini, το οποίο είναι ακριβώς αυτό που χρειάζεται το δέντρο για να αποφασίσει για την καλύτερη διαμέριση.

Εντροπία: μια άλλη άποψη για την ταξινόμηση των προσμίξεων

Η εντροπία είναι ένα εναλλακτικό μέτρο προσμίξεων που χρησιμοποιείται ευρέως στη θεωρία πληροφοριών και σε πρώιμους αλγόριθμους δέντρων όπως οι ID3 και C4.5, και καταγράφει το ποσό της τυχαιότητας ή της αβεβαιότητας στην κατανομή κλάσεων του κόμβου. Ενώ ο Gini εστιάζει στην πιθανότητα λανθασμένης ταξινόμησης, η εντροπία ποσοτικοποιεί την «έκπληξη» που σχετίζεται με την παρατήρηση μιας συγκεκριμένης κλάσης όταν η κατανομή είναι μικτή.

Δεδομένων των πιθανοτήτων κλάσης p₁, …, σελ._c για έναν κόμβο S, η εντροπία του ορίζεται ως E(S) = − Σ p_i log₂(p_i). Αν ο κόμβος είναι καθαρός, μία από τις πιθανότητες είναι 1 και όλες οι άλλες είναι 0, πράγμα που καθιστά το άθροισμα μηδέν (επειδή log₂(1) = 0), επομένως η εντροπία είναι 0, υποδεικνύοντας ότι δεν υπάρχει αβεβαιότητα.

Όταν ο κόμβος περιέχει ομοιόμορφη κατανομή κλάσεων, η εντροπία μεγιστοποιείται· για ένα δυαδικό πρόβλημα με p₁ = σ₂ = 0.5, η εντροπία είναι 1 bit, η οποία είναι η υψηλότερη δυνατή τιμή για δύο κλάσεις. Αυτή η τιμή αντιστοιχεί στη μέγιστη αβεβαιότητα, που σημαίνει ότι ο κόμβος είναι όσο το δυνατόν πιο ακάθαρτος υπό αυτήν την κατανομή.

Παρόλο που η Gini και η εντροπία χρησιμοποιούν διαφορετικούς τύπους και έχουν διαφορετικά αριθμητικά εύρη (Gini μεταξύ 0 και 0.5 για δύο κλάσεις, εντροπία μεταξύ 0 και 1), και οι δύο μετρούν ουσιαστικά την ίδια έννοια, επομένως συνήθως οδηγούν σε πολύ παρόμοια δέντρα στην πράξη. Όταν υπολογίζετε και τα δύο στον ίδιο κόμβο, θα διαπιστώσετε ότι το υψηλό Gini αντιστοιχεί σε υψηλή εντροπία και αντίστροφα, γι' αυτό και πολλές βιβλιοθήκες σάς επιτρέπουν να επιλέξετε οποιοδήποτε από τα δύο χωρίς να αλλάξετε δραστικά την απόδοση.

Απόκτηση πληροφοριών και επιλογή των καλύτερων διαιρέσεων

Για να επιλέξει την καλύτερη διαίρεση μεταξύ πολλών υποψηφίων, ο αλγόριθμος δέντρου χρησιμοποιεί μια μετρική που ονομάζεται Information Gain (Κέρδος Πληροφοριών), η οποία μετρά πόσο μειώνεται η ακαθαρσία όταν διαιρούμε έναν κόμβο στα παιδιά του. Διαισθητικά, ένας διαχωρισμός έχει υψηλό κέρδος πληροφοριών εάν τα παιδιά είναι πολύ πιο καθαρά από τον γονέα, που σημαίνει ότι ο κανόνας διαχώρισε με επιτυχία τα δεδομένα σε πιο ουσιαστικές ομάδες.

Για τα δέντρα ταξινόμησης που χρησιμοποιούν εντροπία, το Information Gain μιας διάσπασης ορίζεται ως IG_{ταξινόμηση} = E(γονέας) − Σ (|S_παιδί| / |Σ_{μητρική εταιρεία}|) · Α(Ν)_παιδί). Αρχικά υπολογίζετε την εντροπία του γονικού κόμβου και, στη συνέχεια, αφαιρείτε τη σταθμισμένη μέση εντροπία των θυγατρικών κόμβων, όπου τα βάρη είναι τα σχετικά μεγέθη τους.

Για τα δέντρα παλινδρόμησης, μια ανάλογη έννοια χρησιμοποιεί τη διακύμανση ή το μέσο τετραγωνικό σφάλμα ως μέτρο πρόσμειξης, δίνοντας IG_{οπισθοδρόμηση} = Var(γονική) − Σ (|S_παιδί| / |Σ_{μητρική εταιρεία}|) · Μεταβλητή(S_παιδί). Σε αυτό το πλαίσιο, ένας καλός διαχωρισμός είναι αυτός που μειώνει σημαντικά τη μεταβλητότητα των τιμών-στόχων μέσα σε κάθε παιδί.

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

Πώς να αναζητήσετε την καλύτερη κατανομή σε κάθε χαρακτηριστικό

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

Για έναν αριθμητικό προγνωστικό παράγοντα, η συνήθης στρατηγική είναι να εξετάσουμε όλες τις μοναδικές τιμές που λαμβάνει ένα χαρακτηριστικό στον τρέχοντα κόμβο, να τις ταξινομήσουμε και στη συνέχεια να εξετάσουμε τα υποψήφια κατώφλια μεταξύ διαδοχικών τιμών. Για κάθε υποψήφιο όριο c, δημιουργείτε δύο ομάδες (x ≤ c και x > c), υπολογίζετε την πρόσμειξη κάθε ομάδας και, στη συνέχεια, υπολογίζετε το Κέρδος Πληροφοριών. Το όριο που αποδίδει το υψηλότερο κέρδος είναι η καλύτερη αριθμητική σας κατανομή σε αυτό το χαρακτηριστικό.

Όταν έχουμε να κάνουμε με κατηγορικούς προγνωστικούς παράγοντες, ο χώρος αναζήτησης είναι πιο περίπλοκος επειδή, κατ' αρχήν, οποιοδήποτε υποσύνολο κατηγοριών θα μπορούσε να σχηματίσει τη μία πλευρά της διαίρεσης, με το συμπλήρωμα στην άλλη πλευρά. Σε ένα χαρακτηριστικό με Κ κατηγορίες, υπάρχουν πολλά πιθανά υποσύνολα (2^Κ−1 − 1 μη τετριμμένες κατατμήσεις), επομένως στην πράξη οι υλοποιήσεις συχνά περιορίζουν αυτήν την αναζήτηση ή χρησιμοποιούν ευρετικές μεθόδους, ειδικά όταν το K είναι μεγάλο.

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

Έλεγχος ανάπτυξης δέντρων με υπερπαραμέτρους

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

Μια συνηθισμένη υπερπαράμετρος είναι η max_depth, η οποία περιορίζει τον μέγιστο αριθμό επιπέδων που μπορεί να αναπτύξει το δέντρο από τη ρίζα έως οποιοδήποτε φύλλο. Εάν η παράμετρος max_depth έχει οριστεί σε None (ή σε πολύ μεγάλο αριθμό), το δέντρο μπορεί να συνεχίσει να αναπτύσσεται εφόσον ικανοποιούνται και άλλοι περιορισμοί. Εάν είναι μικρό, το δέντρο παραμένει ρηχό και πιο ερμηνεύσιμο, αλλά ενδέχεται να μην είναι κατάλληλο για όλες τις περιπτώσεις.

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

Μπορείτε επίσης να επιβάλετε ένα ελάχιστο Information Gain (min_information_gain), έτσι ώστε ο αλγόριθμος να εκτελεί διαχωρισμό μόνο εάν παράγει μια ουσιαστική βελτίωση στη μείωση των προσμίξεων. Αυτό αποφεύγει τη δημιουργία περιττών κλαδιών που δύσκολα αλλάζουν τις προβλέψεις και απλώς περιπλέκουν τη δομή του δέντρου.

Δημιουργία ενός δέντρου αποφάσεων από την αρχή σε κώδικα

Η υλοποίηση ενός δέντρου αποφάσεων από την αρχή συνήθως περιστρέφεται γύρω από ένα μικρό σύνολο βασικών συναρτήσεων που καλούνται αναδρομικά. Ενώ βιβλιοθήκες όπως το scikit-learn ή το rpart κάνουν όλα αυτά κρυφά, η κωδικοποίηση αυτών των βημάτων από μόνοι σας κάνει τη λογική πολύ πιο σαφή (λογική προγραμματισμού) και σας δίνει πλήρη έλεγχο της συμπεριφοράς.

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

Δεύτερον, χρειάζεστε μια συνάρτηση πρόβλεψης για κόμβους φύλλων που μετατρέπει το σύνολο των τιμών-στόχων σε αυτόν τον κόμβο σε μία μόνο πρόβλεψη. Για την παλινδρόμηση, αυτός είναι συνήθως ο μέσος όρος του y σε αυτόν τον κόμβο. Για την ταξινόμηση, συνήθως επιλέγετε την κατάσταση (την πιο συχνή κλάση), ενδεχομένως αποθηκεύοντας και τις πιθανότητες της κλάσης εάν θέλετε πιθανοτικές εξόδους.

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

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

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

Εάν ο κανόνας διαίρεσης είναι αριθμητικός, ελέγχετε εάν η τιμή του χαρακτηριστικού είναι μικρότερη ή ίση με το όριο. Εάν ο κανόνας διαίρεσης είναι κατηγορικός, ελέγχετε εάν η κατηγορία ανήκει σε ένα συγκεκριμένο υποσύνολο. Ανάλογα με το αποτέλεσμα, ακολουθείτε τον κατάλληλο κλάδο (για παράδειγμα, «ναι» αριστερά, «όχι» δεξιά) και επαναλαμβάνετε αυτήν τη διαδικασία στον επόμενο κόμβο.

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

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

Εργασία με δέντρα παλινδρόμησης στην πράξη

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

Στην R, δημοφιλή πακέτα όπως το rpart και το tree διευκολύνουν την κατασκευή δέντρων παλινδρόμησης με μία μόνο κλήση συνάρτησης, καθορίζοντας έναν τύπο όπως y ~ x1 + x2 + … + x11. Αυτά τα πακέτα επηρεάστηκαν από την αρχική μεθοδολογία CART που περιγράφηκε από τον Breiman και τους συναδέλφους του και εφαρμόζουν πολλές από τις ιδέες διαίρεσης και κλαδέματος που είναι τυπικές στη σύγχρονη μοντελοποίηση που βασίζεται σε δέντρα.

Για παράδειγμα, μπορείτε να χρησιμοποιήσετε το πακέτο rpart για να μοντελοποιήσετε μια απόκριση y με βάση έντεκα συνμεταβλητές x1 έως x11, να καθαρίσετε τα δεδομένα από τιμές που λείπουν και, στη συνέχεια, να οπτικοποιήσετε το δέντρο που προκύπτει με βοηθητικές συναρτήσεις όπως η prp από το πακέτο rpart.plot. Οι τερματικοί κόμβοι εμφανίζουν το προβλεπόμενο y για κάθε περιοχή, το οποίο μπορείτε να χρησιμοποιήσετε απευθείας για νέες παρατηρήσεις.

Δεδομένου ενός εκπαιδευμένου δέντρου παλινδρόμησης, μπορείτε να εισάγετε νέες τιμές συνμεταβλητών όπως x9 = 70, x2 = 100 ή x9 = 60, x2 = 150 στη συνάρτηση πρόβλεψης για να λάβετε εκτιμώμενες τιμές ŷ (για παράδειγμα, περίπου 20 ή 28 σε ένα παράδειγμα κατανάλωσης καυσίμου). Συγκρίνοντας αυτές τις προβλέψεις με παρατηρούμενες τιμές, για παράδειγμα μέσω συσχέτισης μεταξύ y και ŷ, σας δίνει μια γρήγορη εικόνα για το πόσο καλά το δέντρο αποτυπώνει το υποκείμενο μοτίβο, ακόμη και όταν το σύνολο δεδομένων είναι αρκετά μικρό.

Από μεμονωμένα δέντρα σε τυχαία δάση

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

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

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

Ο συνδυασμός της μεθόδου bootstrapping και της συνάθροισης προβλέψεων είναι γνωστός ως bagging (συσκευασία) και στα τυχαία δάση λαμβάνετε επίσης μια εσωτερική εκτίμηση του σφάλματος του μοντέλου αξιολογώντας κάθε δέντρο στα σημεία δεδομένων που δεν συμπεριλήφθηκαν στο δείγμα bootstrap του (οι λεγόμενες παρατηρήσεις εκτός συστοιχίας). Αυτό το σφάλμα "έτοιμο προς χρήση" παρέχει έναν βολικό τρόπο μέτρησης της απόδοσης χωρίς να χρειάζεται ξεχωριστό σύνολο επικύρωσης.

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

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