Τι είναι το Δέντρο Απόφασης;

Τι είναι το Δέντρο Απόφασης;

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

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

Μορφή δέντρου αποφάσεων

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

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

Αλγόριθμοι για Δέντρα Αποφάσεων

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

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

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

Όσον αφορά τη συνάρτηση κόστους παλινδρόμησης για αναδρομικό δυαδικό διαχωρισμό, ο αλγόριθμος που χρησιμοποιείται για τον υπολογισμό του κόστους είναι ο ακόλουθος:

άθροισμα(y – πρόβλεψη)^2

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

Όσον αφορά τη συνάρτηση κόστους για ταξινόμηση, η συνάρτηση είναι η εξής:

G = άθροισμα (pk * (1 – pk))

Αυτή είναι η βαθμολογία Gini και είναι μια μέτρηση της αποτελεσματικότητας ενός διαχωρισμού, με βάση πόσες περιπτώσεις διαφορετικών τάξεων υπάρχουν στις ομάδες που προκύπτουν από τη διάσπαση. Με άλλα λόγια, ποσοτικοποιεί πόσο μικτές είναι οι ομάδες μετά τη διάσπαση. Ένας βέλτιστος διαχωρισμός είναι όταν όλες οι ομάδες που προκύπτουν από τη διαίρεση αποτελούνται μόνο από εισόδους από μια κλάση. Εάν έχει δημιουργηθεί μια βέλτιστη διαίρεση, η τιμή "pk" θα είναι είτε 0 είτε 1 και το G θα είναι ίση με μηδέν. Ίσως μπορείτε να μαντέψετε ότι ο διαχωρισμός στη χειρότερη περίπτωση είναι αυτός όπου υπάρχει μια αναπαράσταση 50-50 των κλάσεων στη διαίρεση, στην περίπτωση της δυαδικής ταξινόμησης. Σε αυτήν την περίπτωση, η τιμή "pk" θα ήταν 0.5 και το G θα ήταν επίσης 0.5.

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

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

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

Θεωρήσεις για τη χρήση των δέντρων αποφάσεων

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

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