Κατηγοριοποίηση κειμένων

Abstract

The fast growing of the Internet and the continuous rising of the available material in digital form, make ergent the need for classification algorithms. Older techniques of the Knowledge Engineering back at the '80s, have been replaced by Machine Learning techniques. The last 15 years a large number of methods have been studied and developed, which have succeed in solving this problem. Such techniques include Decision Tress, Naive Bayes, Neural Networks, Linear Classifiers, Logistic Regression, Perceptron, Support Vector Machines etc. An important group of classifiers is Linear Classifiers, which try to classify data by defining separating hyperplanes. Types of Linear Classifiers are Centroid Classifier, Rocchio Classifier and Perceptron Classifier. By combining characteristics of those three simple classifiers, a new, fast and accurate classifier is defined, under the symbolic name Modified Perceptron, due to its resemblence with the classic Perceptron Classifier. This new classifier is proved that it converges and it is shown experimentally that it converges much faster than other Linear Classifiers. By evaluating its performance on classifying international text corpuses and corpuses from conference challenges, it turned that its performance is comparable, if not better, than the state of the art in the field of Text Classification, such as SVMs. Note that it took the first place in the international challenge on spam detection on social bookmarking networks of ECML 2008. Evaluation is performed by the classic model of flat classification, where each category is considered independent from others. This technique, one versus all, has some limitations, such as how it scales when the number of categories is very large or the number of examples is very large. This limitation refers in space requirements, beacause all classifiers have to be stored in memory. As for time requirements, time complexity is O(NM), where N is the number classifiers and M is the dimensionality of each example. To overcome those limitation, a hierarchical model for classification has been developed. Relations among categories where defined and an experimental search was done on the sampling for creating negative sets for each category. The proposed algorithm was succesfully applied on very large classification problems and new issues for further research and improvements where opened.

Η ταχεία εξάπλωση του διαδικτύου και η συνεχώς αυξανόμενη διάθεση υλικού σε ηλεκτρονική μορφή καθιστά επιτακτική την ανάγκη εύρωστων αλγορίθμων ταξινόμησης (κατηγοριοποίησης) του υλικού αυτού. Παλαιότερες τεχνικές της Μηχανικής Γνώσης (Knowledge Engineering) του '80, έχουν δώσει τη θέση τους σε τεχνικές Μηχανικής Μάθησης (Machine Learning). Μία πληθώρα μεθόδων έχουν μελετηθεί και αναπτυχθεί τα τελευταία 15 χρόνια, οι οποίες άλλες λιγότερο και άλλες περισσότερο, σημειώνουν επιτυχία στην επίλυση του προβλήματος. Τέτοιες τεχνικές για παράδειγμα είναι, τα Δένδρα Αποφάσεων, Naive Bayes, Νευρωνικά Δίκτυα, Γραμμικοί Κατηγοριοποιητές, Λογιστική Παλινδρόμηση, Perceptron, Μηχανές Διανυσμάτων Υποστήριξης κ.α. Μία σημαντική ομάδα κατηγοριοποιητών, είναι οι Γραμμικοί Κατηγοριοποιητές, οι οποίοι επιδιώκουν την κατηγοριοποίηση των παραδειγμάτων, ορίζοντας διαχωριστικά υπερεπίπεδα μεταξύ τους. Είδη τέτοιων κατηγοριοποιητών αποτελούν ο κατηγοριοποιητής κεντροειδών (centroid classifier), ο κατηγοριοποιητής Rocchio και ο κατηγοριοποιητής Perceptron. Συνδυάζοντας στοιχεία και χαρακτηριστικά των τριών αυτών απλών κατηγοριοποιητών, ορίζεται ένας νέος γρήγορος και ακριβής γραμμικός κατηγοριοποιητής, παίρνοντας το συμβολικό όνομα Modified Perceptron, εξαιτίας της ομοιότητάς του με τον κλασικό κατηγοριοποιητή Perceptron. Ο νέος αυτός κατηγοριοποιητής αποδεικνύεται ότι συγκλίνει και δείχνεται πειραματικά ότι συγκλίνει αρκετά γρηγορότερα από άλλους γραμμικούς κατηγοριοποιητές. Αξιολογώντας την επίδοσή του στην κατηγοριοποίηση διεθνών συλλογών κειμένων και συλλογών διαγωνισμών, φαίνεται ότι επιτυγχάνει επιδόσεις συγκρίσιμες και τις περισσότερες φορές καλύτερες με τις κορυφαίες τεχνικές κατηγοριοποίησης κειμένων, όπως για παράδειγμα είναι τα SVMs. Σημειωτέον ότι στη συμμετοχή μας στο ECML challenge 2008 απέσπασε την πρώτη θέση σε πρόβλημα ‘link spamming” σε κοινωνικά δίκτυα. Η αξιολόγηση του αλγόριθμου γίνεται με το κλασικό μοντέλο της επίπεδης κατηγοριοποίησης, όπου κάθε κατηγορία θεωρείται ανεξάρτητη από κάθε άλλη. Η τεχνική αυτή του «ενός έναντι όλων» έχει όμως τους περιορισμούς της όπως είναι η κλιμάκωση του αλγόριθμου όταν το πλήθος το κατηγοριών είναι αρκετά μεγάλο ή τα προς ταξινόμηση παραδείγματα είναι πολλά. Οι περιορισμοί αναφέρονται στο χώρο αφού όλοι οι ταξινομητές πρέπει να φυλάσσονται στη μνήμη. Χαρακτηριστικό παράδειγμα του προβλήματος περιλαμβάνει 20,000 ταξινομητές μεγέθους 800,000 χαρακτηριστικών ο καθένας. Ως προς το χρόνο η πολυπλοκότητα του προβλήματος είναι Ο(ΝΜ) όπου Ν είναι το πλήθος των ταξινομητών και Μ το μέγεθος των διανυσμάτων των προς ταξινόμηση κειμένων. Για την υπέρβαση των περιορισμών αυτών υλοποιήθηκε ένα μοντέλο ιεραρχικής κατηγοριοποίησης. Επίσης ορίστηκαν οι σχέσεις εξάρτησης μεταξύ των κατηγοριών και πραγματοποιήθηκε μια πειραματική διερεύνηση όσο αφορά την δειγματοληψία για την δημιουργία των παραδειγμάτων εκπαίδευσης ιδιαίτερα των αρνητικών παραδειγμάτων. Ο αλγόριθμος εφαρμόστηκε σε πολύ μεγάλα προβλήματα κατηγοριοποίησης με επιτυχία και άνοιξε νέα θέματα για περαιτέρω βελτιώσεις.