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

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

Ένα δέντρο απόφασης είναι μια δομή που μοιάζει με γραφική παράσταση, όπου κάθε εσωτερικός κόμβος αντιπροσωπεύει μια δοκιμή σε ένα χαρακτηριστικό (π.χ., “Είναι ηλικία > 30;”), κάθε κλάδος αντιπροσωπεύει το αποτέλεσμα της δοκιμής αυτής, και κάθε κόμβος φύλλων κατέχει μια ετικέτα κλάσης ή συνεχή αξία. Ο στόχος είναι να δημιουργηθεί ένα μοντέλο που προβλέπει μια μεταβλητή-στόχος με την εκμάθηση απλών κανόνων απόφασης που προκύπτουν από τα χαρακτηριστικά των δεδομένων. Τα δέντρα αποφάσεων είναι δημοφιλή επειδή είναι εύκολο να ερμηνεύσει και απαιτούν μικρή προεπεξεργασία δεδομένων (δεν κλιμάκωση ή ομαλοποίηση).

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

Βασικές Έννοιες που Πρέπει να Κατανοήσετε

Κόμβοι, Κλάδοι και Φύλλα

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

Κριτήρια διαχωρισμού

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

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

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

Λόγος αύξησης και αύξησης πληροφοριών

Το κέρδος πληροφοριών είναι η διαφορά μεταξύ της πρόσμειξης του γονικού κόμβου και του σταθμισμένου ποσού των προσμείξεων παιδιών. Ενώ απλό, τείνει να ευνοεί χαρακτηριστικά με πολλές τιμές. Ο λόγος κέρδους (που χρησιμοποιείται στο C4.5) ομαλοποιεί αυτό. Για αυτό το φροντιστήριο θα κολλήσει με το τυπικό κέρδος πληροφοριών χρησιμοποιώντας Gini πρόσμειξη, η οποία είναι η προεπιλογή σε CART (Classification and Regression Trees).

Οικοδόμηση μιας απόφασης δέντρο βήμα προς βήμα

1. Ετοιμάστε τα δεδομένα σας

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

  • Χαρακτηριστικά: Ηλικία, Εισόδημα
  • Φορτηγός: Εγκεκριμένος (1) ή μη εγκεκριμένος (0)

Καθαρίστε τα δεδομένα: χειριστεί τις τιμές που λείπουν, αφαιρέστε τα αντίγραφα, και να εξασφαλίσει αριθμητικούς τύπους.

2. Καθορίστε μια λειτουργία κριτηρίου διαχωρισμού

Θα εφαρμόσουμε την πρόσμειξη Gini. Ο δείκτης Gini για ένα σύνολο αντικειμένων είναι:

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

3. Εφαρμογή της αξιολόγησης του διαχωρισμού

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

4. Κατασκευάστε το δέντρο αναδρομικά

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

5. Κάντε Προβλέψεις

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

Πλήρης εφαρμογή σε Python

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

import numpy as np
from collections import Counter

class DecisionTree:
 def __init__(self, max_depth=None, min_samples_split=2):
 self.max_depth = max_depth
 self.min_samples_split = min_samples_split
 self.tree = None

 def fit(self, X, y):
 dataset = np.column_stack((X, y))
 self.tree = self._grow_tree(dataset)

 def _grow_tree(self, dataset, depth=0):
 X, y = dataset[:, :-1], dataset[:, -1]
 n_samples, n_features = X.shape
 n_labels = len(np.unique(y))

 # Stopping conditions
 if (n_labels == 1 or depth == self.max_depth or n_samples < self.min_samples_split):
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 best_feature, best_threshold = self._best_split(dataset, n_features)
 if best_feature is None:
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 left_idx, right_idx = self._split(dataset[:, best_feature], best_threshold)
 left_subtree = self._grow_tree(dataset[left_idx], depth+1)
 right_subtree = self._grow_tree(dataset[right_idx], depth+1)
 return {'leaf': False,
 'feature': best_feature,
 'threshold': best_threshold,
 'left': left_subtree,
 'right': right_subtree}

 def _best_split(self, dataset, n_features):
 best_gini = float('inf')
 best_feature, best_threshold = None, None
 for feature in range(n_features):
 thresholds = np.unique(dataset[:, feature])
 for i in range(len(thresholds)-1):
 thresh = (thresholds[i] + thresholds[i+1]) / 2
 left_idx, right_idx = self._split(dataset[:, feature], thresh)
 if len(left_idx) == 0 or len(right_idx) == 0:
 continue
 gini = self._gini_gain(dataset, left_idx, right_idx)
 if gini < best_gini:
 best_gini = gini
 best_feature = feature
 best_threshold = thresh
 return best_feature, best_threshold

 def _split(self, values, threshold):
 left_idx = np.where(values <= threshold)[0]
 right_idx = np.where(values > threshold)[0]
 return left_idx, right_idx

 def _gini_gain(self, dataset, left_idx, right_idx):
 total = len(left_idx) + len(right_idx)
 gini_left = self._gini(dataset[left_idx, -1])
 gini_right = self._gini(dataset[right_idx, -1])
 return (len(left_idx)/total) * gini_left + (len(right_idx)/total) * gini_right

 def _gini(self, labels):
 _, counts = np.unique(labels, return_counts=True)
 p = counts / np.sum(counts)
 return 1 - np.sum(p**2)

 def predict(self, X):
 return np.array([self._predict_row(x, self.tree) for x in X])

 def _predict_row(self, x, node):
 if node['leaf']:
 return node['value']
 if x[node['feature']] <= node['threshold']:
 return self._predict_row(x, node['left'])
 else:
 return self._predict_row(x, node['right'])

Δοκιμές του Δέντρου

Χρησιμοποιήστε ένα απλό σύνολο δεδομένων όπως το κλασικό σύνολο δεδομένων ίριδας (δύο χαρακτηριστικά για δυαδική ταξινόμηση). Το scikit ⁇ learn Iris dataset λειτουργεί καλά. Συγκρίνετε την ακρίβεια του δέντρου σας με το scikit-learn’s για να επαληθεύσετε την ορθότητα.

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

data = load_iris()
X = data.data[:100] # take only first two classes (binary)
y = data.target[:100]

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

tree = DecisionTree(max_depth=3)
tree.fit(X_train, y_train)
preds = tree.predict(X_test)
accuracy = np.mean(preds == y_test)
print(f'Accuracy: {accuracy:.2f}')

Προχωρημένες Τεχνικές για να Βελτιώσετε το Δέντρό Σας

Το Κούρνισμα για να Αποφεύγετε την Υπερταξία

Ένα πλήρως καλλιεργημένο δέντρο μπορεί να απομνημονεύσει το θόρυβο στα δεδομένα της εκπαίδευσης. Το κλάδεμα αφαιρεί τα κλαδιά που έχουν μικρή προγνωστική ισχύ. Κοινές μέθοδοι προ-αποσυναρμολογούνται (σταμάτημα της ανάπτυξης νωρίς μέσω [[[LFT:4]]] ή [[LFT:5]]) και μετά-πλέξιμο (μεγάλωμα του πλήρους δέντρου στη συνέχεια αφαίρεση των κλαδιών με τη χρήση ενός συνόλου επικύρωσης ή κόστους-περίπλοκων κλαδέματος).

Χειρισμός Συνεχών και κατηγοριοποιημένων χαρακτηριστικών

Για τα συνεχόμενα χαρακτηριστικά, χρησιμοποιήσαμε τα μεσαία σημεία μεταξύ ταξινομημένων τιμών ως κατώτατα όρια. Για κατηγορηματικά χαρακτηριστικά (π.χ., “Χρώμα = κόκκινο/πράσινο/μπλε”), κάθε κατηγορία μπορεί να γίνει ένας ξεχωριστός κλάδος (πολλαπλές ⁇ τρεις χωριστές) ή μπορείτε να τα δυαδικά ⁇ κωδικοποιήσετε. Οι περισσότερες σύγχρονες υλοποιήσεις (όπως το σκικίτ ⁇ λέαρν) χρησιμοποιούν δυαδικούς διαχωρισμούς ακόμα και για κατηγοριακά χαρακτηριστικά αξιολογώντας όλα τα υποσύνολα.

Αντιμετώπιση των Αγνοούμενων Αξιών

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

Συγκρίνοντας με τις Βιβλιοθήκες και Περαιτέρω Ανάγνωση

Ενώ η κατασκευή από το μηδέν είναι εκπαιδευτική, τα συστήματα παραγωγής χρησιμοποιούν βιβλιοθήκες όπως το scikit ⁇ learn που παρέχουν βελτιστοποιημένες εφαρμογές C. Μπορείτε να μάθετε περισσότερα από την επίσημη [[LFT:0]]scikit ⁇ learn τεκμηρίωση δέντρων αποφάσεων[[[LFT:1]]]. Για βαθύτερη θεωρία, το βιβλίο «Τα Στοιχεία της Στατιστικής Μάθησης» των Hastie, Tibshirani, και Friedman είναι μια έγκυρη πηγή. Μια άλλη εξαιρετική αναφορά είναι το πρωτότυπο βιβλίο CART από τους Breiman et al.

Συμπέρασμα

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