Δέντρα αποφάσεων βασισμένα σε ταξινομητές SVM: αλγόριθμοι εκπαίδευσης και ταξινόμησης
Creators: name: Τσοτσόλη, Ελισάβετ Νικολάου
name: Τζαλακώστα, Ελένη Λάμπρου
Publisher: name: Aristotle University of Thessaloniki
Year: 2009
Subjects: Αλγόριθμοι ταξινόμησης δεδομένων
Δυαδικά δέντρα
Support Vector machines
Binary trees

description: Τα δέντρα αποφάσεων SVM ή απλά Binary Trees (BTS) δεν είναι απλά ένα θεωρητικό αντικείμενο για έρευνα και μελέτη, αλλά μπορούν να παίξουν σημαντικό ρόλο και να αλλάξουν τα δεδομένα στον τομέα της κατηγοριοποίησης στοιχείων (classification) στην τεχνητή νοημοσύνη. Αυτό που τα κάνει ξεχωριστά, είναι η δυνατότητα να κατηγοριοποιούν δεδομένα σε περισσότερες των δύο κλάσεων, σε αντίθεση με τους δυαδικούς ταξινομητές. Ωστόσο, τα δυαδικά δέντρα στηρίζονται και χρησιμοποιούν τους δυαδικούς ταξινομητές για να «στηθούν». Όπως μαρτυρά και το όνομά τους, τα δέντρα αποφάσεων ξεκινούν έχοντας όλα τα δεδομένα τοποθετημένα στη ρίζα ενός δέντρου, τα οποία στη συνέχεια χωρίζουν σε δύο πάντα κατηγορίες. Σχηματίζουν κατόπιν δύο νέους υποκόμβους και επαναλαμβάνουν τη δυαδική διάσπαση των κλάσεων έως ότου δημιουργηθεί ένα δυαδικό δέντρο με δεδομένα μίας μόνο κλάσης σε κάθε του φύλλο. Ένας αλγόριθμος που ακολουθεί την παραπάνω διαδικασία είναι ο «αλγόριθμος ΒΤS». Επιλέγει τυχαία δύο από τις κλάσεις προς ταξινόμηση, υπολογίζει το δυαδικό διαχωριστή τους και με βάση αυτόν, ταξινομεί όλες τις εναπομένουσες. Ταυτόχρονα υπολογίζει την πιθανότητα κάθε δείγματος να έχει ταξινομηθεί λάθος και τη λαμβάνει υπόψη. Η διαδικασία αυτή επαναλαμβάνεται για κάθε νέο κόμβο που δημιουργείται μέχρι να απομείνει μόνο μία κλάση σε κάθε κόμβο. Η τυχαία επιλογή των αρχικών κλάσεων εξαλείφεται με εφαρμογή του αλγορίθμου “Centered BTS - CBTS”. Ένας δεύτερος αλγόριθμος για την αντιμετώπιση πολλαπλών κατηγοριοποιήσεων είναι ο «αλγόριθμος αποστάσεων». Με βάση την ευκλείδεια απόσταση τοποθετεί τις δύο πιο απομακρυσμένες κλάσεις στα δύο πρώτα παιδιά του. Τις υπόλοιπες τις τοποθετεί σε μία από τις δύο αρχικές, συγκεκριμένα ταξινομεί κάθε κλάση στην αρχική που βρίσκεται πιο κοντά της. Η διαδικασία επαναλαμβάνεται έως ότου σε κάθε κόμβο βρίσκεται μία μόνο κλάση οπότε και έχει σχηματιστεί το δυαδικό δέντρο. Τέλος κάθε κόμβος εκπαιδεύεται και υπολογίζεται ο ταξινομητής που θα ταξινομεί τα δεδομένα του. Εφαρμόζοντας τους παραπάνω αλγορίθμους σε πειραματικά δεδομένα, διαπιστώ-νουμε υψηλά ποσοστά επιτυχίας στην κατηγοριοποίηση και τη δημιουργία σταθερών και σχετικά απλών δυαδικών δέντρων. Σε σύγκριση μάλιστα με τον απλό SVM “one against one” αλγόριθμο είναι ταχύτεροι, ιδίως όταν πρόκειται για προβλήματα πλήθους δεδομένων και πολλών κλάσεων. Οι αλγόριθμοι “SVM” και «αποστάσεων» είναι δύο νέες μέθοδοι που επιδέχονται έρευνα και βελτιώσεις. Ίσως καταφέρουν να γίνουν ακόμη πιο αξιόπιστοι και γρήγοροι και αποτελέσουν βάση για κατηγοριοποιήσεις σημαντικών δεδομένων στην τεχνητή στην τεχνητή νοημοσύνη.
description: The SVM binary trees or just Binary Trees (BTS) are not only a theoretical subject for study and research but they can also play an important role in data classification and computational intelligence in general. The important thing about SVM trees is the possibility to classify data that belong to more than two classes as opposed to binary classifiers. Nevertheless, Binary trees of SVM use the binary classifiers (SVM) to succeed their goal. Binary trees begin the classification process having all data in the root of the tree and classifying them in two nodes every time. Thus, each time two subnodes are being created and the process goes on until there are data of one and only one category in each node. Then the binary tree has been formed. An algorithm that follows the above procedure is the BTS algorithm. To be more specific, BTS algorithm, chooses two data classes by chance and computes their binary classifier. Based on that classifier, it classifies the rest data classes to one of the two subnodes that have been created. At the same time it computes the probability of misclassification of a sample and takes it into account. The process stops when each node contains data of one class only. Another algorithm that deals with multiclass classification problem using binary trees is the ‘distance’ algorithm. Based on the Euclidean distance the algorithm classifies the two more distanced classes in the two subnodes. Then, it classifies each one of the rest classes to the subnode that contains the class with which the Euclidean distance is smaller. The process repeats until there is only one class in each node and the binary tree is then created. Finally, the data of each node are being trained in order to compute their binary classifier. The above two mulitclass algorithms have been tested to various classification problems and succeeded very high percentages of accuracy. Comparing them to the one-against-one algorithm, it turned out that they are faster and less complex especially when we deal with problems with lots of data and classes. The ‘BTS’ and ‘distance’ algorithms are two new methods in mulitclass classification problems that of course need more study and improvement. In that case, it is more than certain that they will be even more efficient and reliable.