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

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

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

• Δείκτης Gini (Gini impurity) — μετρά την πιθανότητα λανθασμένης ταξινόμησης ενός τυχαία επιλεγμένου αντικειμένου, αν ταξινομηθεί τυχαία σύμφωνα με την κατανομή των κλάσεων στο υποσύνολο. Όσο μικρότερος, τόσο καλύτερος.

• Κέρδος πληροφορίας (Information Gain) — διαφορά στην εντροπία πριν και μετά το διαχωρισμό. Όσο μεγαλύτερο το κέρδος πληροφορίας, τόσο καλύτερος ο διαχωρισμός.

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

• Μείωση διακύμανσης (Variance reduction) — χρησιμοποιείται για παλινδρόμηση, ελαχιστοποιεί την διασπορά των τιμών της μεταβλητής στόχου στα υποσύνολα.

Παράδειγμα απλής διαίρεσης με βάση ένα χαρακτηριστικό:

# Ψευδοκώδικας για την επιλογή της καλύτερης διαίρεσης
best_gain = 0
best_feature = None
for feature in features:
    for threshold in possible_thresholds(feature):
        left, right = split(data, feature, threshold)
        gain = information_gain(data, left, right)
        if gain > best_gain:
            best_gain = gain
            best_feature = (feature, threshold)