Large scale hierarchical text classification

Abstract

Hierarchies are becoming increasingly popular for the organization of documents, particularly on the Web. Web directories, such as the Υahoo! Directory and the Dmoz Directory, are typical examples. Along with their widespread use, comes the need for automated classification of new documents to the classes of the hierarchy. In this thesis, we call this problem Large Scale Hierarchical Text Classification. It is a large scale classification problem, since the classes are thousands and the documents can be hundreds of thousands or even millions.It is also hierarchical, since the classes are connected by parent-child relations.An important issue in hierarchical classification is the evaluation of different classification algorithms, an issue which is complicated by the hierarchical relations among the classes.Several evaluation measures have been proposed for hierarchical classification using the hierarchy in different ways without however providing a unified view of the problem. In this thesis, we study the problem of evaluation in hierarchical classification by analysing and abstracting the key components of the existing performance measures. We also propose two alternative generic views of hierarchical evaluation and introduce two corresponding novel measures. The proposed measures, along with the state-of-the-art ones, are empirically tested on three large datasets from the domain of text classification. The empirical results illustrate the limitations of existing approaches and how the proposed methods overcome most of them across a range of cases.We then focus on the simplest case of large scale hierarchical text classification, where the hierarchy is a tree and each document belongs in a single leaf class of the hierarchy.A popular method of hierarchical classification is cascade classification, which greedily traverses the hierarchy from the root to the predicted leaf. In order to perform cascade classification, a classifier must be trained for each node of the hierarchy, but in the upper levels the number of features can be prohibitively large. It is therefore desirable to reduce the dimensionality of the feature space at these levels. We examine the computational feasibility of the most common dimensionality reduction method (Principal Component Analysis) for this problem, as well as the computational benefits that it provides for cascade classification and its effect on classification accuracy. Furthermore, we propose a probabilistic cascading approach, which outperforms the traditional greedy cascade, by making better use of the probabilities estimated by the classifiers.Finally, we consider a more complex domain, known as biomedical semantic indexing, where biomedical documents have to be classified to the classes of a large biomedical taxonomy. This domain is more complex in that the taxonomy is a directed acyclic graph, rather than simply a tree, the same document may belong in several classes, and the correct classes are not necessarily leaves of the taxonomy. We examine the use of dense word vectors, also known as word embeddings, as a method of dimensionality reduction. We consider several efficient approaches for the transition from dense word vectors to vectors that represent entire texts, proposing a simple weighted centroid approach that is suitable for this domain. We show that by adopting this approach, hierarchical text classification algorithms become sufficiently scalable for large scale semantic indexing, without being less effective than then usual bag of words representation. We experiment with flat and hierarchically expanded k-nearest neighbor classifiers that employ our centroid representations of article abstracts, examining the effect of various parameters. We also present a high precision system that can be combined with the widely used Medical Text Indexer (MTI) system of the National Library of Medicine to improve its performance.

Οι ιεραρχίες χρησιμοποιούνται όλο και πιο συχνά στην την οργάνωση κειμένων και η χρήση αυτή είναι ακόμη πιο συχνή στο διαδίκτυο. Οι κατάλογοι ιστοσελίδων, όπως το Yahoo Directory και το Dmoz Directory, είναι τέτοια τυπικά παραδείγματα. Μαζί με την συχνή χρήση τους όμως προκύπτει και η ανάγκη για αυτοματοποιημένους τρόπους ταξινόμησης των νέων κειμένων στις κατηγορίες των ιεραρχιών αυτών. Σε αυτή τη διατριβή, ονομάζουμε το πρόβλημα αυτό "μεγάλης κλίμακας Ιεραρχική κατηγοριοποίηση κειμένων". Είναι μεγάλης κλίμακας, γιατί οι κατηγορίες είναι χιλιάδες και τα κείμενα μπορεί να είναι από εκατοντάδες χιλιάδες μέχρι και εκατομμύρια. Είναι επίσης ιεραρχικό επειδή οι κατηγορίες συν΄δεονται μεταξύ τους με σχέσεις γονέα-πατέρα. Ένα σημαντικό θέμα στην ιεραρχική κατηγοριοποίηση είναι η αξιολόγηση διαφορετικών αλγορίθμων κατηγοριοποίησης, που είναι ακόμη πιο έντονο λόγο της ύπαρξης της ιεραρχίας. Διάφορα ιεραρχικά μέτρα έχουν προταθεί στο παρελθόν, αλλά χωρίς να προσφέρουν ένα ενοποιημένο τρόπο εποπτείας του προβλήματος. Σε αυτή τη διατριβή, μελετούμε το πρόβλημα της αξιολόγησης στην ιεραρχική κατηγοριοποίηση, αναλύοντας τα βασικά στοιχεία των υπαρχόντων ιεραρχικών μέτρων. Επίσης διαχωρίζουμε τα υπάρχοντα ιεραρχικά μέτρα σε δυο εναλλακτικά γενικά μοντέλα και προτείνουμε δυο καινοτόμα μέτρα για κάθε μοντέλο. Τα υπάρχοντα και τα προτεινόμενα μέτρα δοκιμάζονται σε τρία μεγάλα σύνολα δεδομένων κατηγοριοποίησης κειμένων. Τα αποτελέσματα των πειραμάτων δείχνουν τους περιορισμούς των υπαρχόντων μέτρων και το πως τα νέα προτεινόμενα μέτρα ξεπερνούν αυτούς τους περιορισμούς. Στη συνέχεια επικεντρωνόμαστε στην απλούστερη μορφή ιεραρχικής κατηγοριοποίησης όπου κάθε κείμενο ανήκει σε μόνο μία κατηγορία και η ιεραρχία έχει μορφή δένδρου. Η πιο συνηθισμένη μορφή ιεραρχικής κατηγοριοποίησης είναι αυτή του Cascade, στην οποία διατρέχεται η ιεραρχία από τη ρίζα του δένδρου ως το προτεινόμενο φύλλο. Για να πραγματοποιηθεί αυτή η διαδικασία, πρέπει να εκπαιδευτεί ένας ταξινομητής σε κάθε κόμβο του δένδρου, αλλά στα πιο ψηλά επίπεδα ο αριθμός των χαρακτηριστικών μπορεί να γίνει απαγορευτικά υψηλός. Για αυτό και είναι επιθυμητή η μείωση της διαστασιμότητας του χώρου των χαρακτηριστικών σε αυτά τα επίπεδα. Δεδομένου ότι η πιο ευρέος διαδεδομένη μέθοδος μείωσης χαρακτηριστικών είναι το Principal Component Analysis (PCA), εξετάζουμε τη χρήση του στο Cascade μελετώντας την επίδραση του στο υπολογιστικό κόστος αλλά και την ακρίβεια των ταξινομικών. Επίσης προτείνουμε έναν εναλλακτικό τρόπο πιθανοτικού Cascade ο οποίος κάνοντας καλύτερη χρήση των πιθανοτήτων των ταξινομητών επιτυγχάνει καλύτερα αποτελέσματα σε σχέση με το παραδοσιακό Cascade. Τέλος, εξετάζουμε ένα πιο πολύπλοκο πρόβλημα, γνωστό ως βιοϊατρική σημασιολογική ταξινόμηση όπου βιοϊατρικά κείμενα πρέπει να ταξινομηθούν σε κατηγορίες που ανήκουν σε μια μεγάλη βιοϊατρική ιεραρχία. Το πρόβλημα αυτό είναι πιο πολύπλοκο διότι η ιεραρχία είναι κατευθυνόμενος γράφος και όχι απλά δένδρο, ενώ κάθε κείμενο μπορεί να ανήκει σε πολλές κατηγορίες η οποίες μάλιστα μπορεί να μην είναι απαραίτητα φύλλα του γράφου. Σε αυτό το πρόβλημα, εξετάζουμε της χρήση πυκνών διανυσμάτων λέξεων (word embeddings) ως ένα τρόπο για μείωση της διαστασημότητας των χαρακτηριστικών. Εξετάζουμε διάφορες προσεγγίσεις για να περάσουμε από τα διανύσματα λέξεων σε διανύσματα κειμένων και προτείνουμε μια απλή διαδικασία με χρήση κεντροειδούς η οποία είναι κατάλληλη για το πρόβλημα. Επίσης δείχνουμε πως η υιοθέτηση αυτής της προσέγγισης κάνει το πρόβλημα της μεγάλης κλίμακας ιεραρχικής κατηγοριοποίησης πολύ πιο κλιμακώσιμο, χωρίς να υστερεί σε ακρίβεια σε σχέση με τη συνηθισμένη προσέγγιση bag-of-words. Στα πειράματά μας εξετάζουμε τη χρήση ιεραρχικών και μη ιεραρχικών ταξινομητών κ-κοντινότερων-γειτόνων και μελετάμε την επίδραση των διαφόρων παραμέτρων τους. Επίσης παρουσιάζουμε ένα υψηλής ακρίβειας σύστημα που συνδυάζεται με το ευρέος χρησιμοποιημένο Medical Text Indexer (MTI) σύστημα της Εθνικής Βιβλιοθήκης της Ιατρικής με στόχο τη βελτίωση των προβλέψεών του.