No description available.

Η διαρκώς αυξανόμενη διαθεσιμότητα ηλεκτρονικών πηγών πληροφόρησης έχει δημιουργήσει νέα δεδομένα και απαιτήσεις στην περιοχή της Ανάκτησης Πληροφορίας. Υπάρχει αδιάκοπη ανάγκη για βελτίωση των υπαρχόντων και σχεδίαση νέων αλγορίθμων, που να επιτυγχάνουν υψηλή απόδοση και αξιοπιστία. Ένα επιπλέον ζητούμενο είναι η κατασκευή λογισμικού περιβάλλοντος που θα διευκολύνει τη χρήση υπαρχόντων αλγορίθμων, την εισαγωγή νέων, το συνδυασμό τους και τη συγκριτική αξιολόγησή τους. Στην παρούσα διδακτορική διατριβή, εστιάζουμε σε μεθόδους ανάκτησης πληροφορίας (με έμφαση στην ανάκτηση κειμένου), που έχουν στον πυρήνα τους τεχνολογίες Γραμμικής Άλγεβρας και πιο συγκεκριμένα σε τεχνικές που αξιοποιούν τα φασματικά χαρακτηριστικά των μητρώων όρων-κειμένων. Υπενθυμίζουμε ότι περίοπτη θέση στην περιοχή της Ανάκτησης Πληροφορίας, όσον αφορά τις τεχνικές της γραμμικής άλγεβρας, κατέχουν οι ιδιάζουσες τιμές και τα ιδιάζοντα διανύσματα των μητρώων. Περιγράφουμε επίσης το σχεδιασμό και την κατασκευή ενός ολοκληρωμένου περιβάλλοντος που διευκολύνει τους χρήστες στην ανάπτυξη, χρήση και αξιολόγηση των αλγορίθμων που στηρίζεται στο εξαιρετικά διαδεδομένο περιβάλλον της MATLAB. Αρχικά, εξετάζουμε τα βασικά προβλήματα στην Ανάκτηση Πληροφορίας, που είναι η ομαδοποίηση, η εξαγωγή σχετικών κειμένων και η κατηγοριοποίηση. Στην πρώτη κατηγορία προβλημάτων, στόχος μας είναι η βελτίωση παραδοσιακών αλγορίθμων όπως οι k-means και PDDP. Στο πλαίσιο αυτό προτείνουμε ένα σύνολο υβριδικών τεχνικών που βασίζονται στους δύο αυτούς αλγορίθμους και αντιμετωπίζουν προβλήματα που σχετίζονται με αυτούς. Ειδικότερα, πετυχαίνουν τη βελτίωση της απόδοσής τους ως προς την ποιότητα των παρεχόμενων αποτελεσμάτων ή ως προς την ταχύτητά τους. Σε σύγκριση με τον k-means, επιτυγχάνουν την αφαίρεση του στοιχείου της τυχαιότητας που τον χαρακτηρίζει, λόγω της γνωστής ευαισθησίας του στις αρχικές συνθήκες. Επιπλέον, προτείνουμε ένα ενιαίο σύνολο αποδοτικών "μεθόδων πυρήνα" (kernel methods) που μπορούν να χρησιμοποιηθούν στην περίπτωση που τα δεδομένα του προβλήματος έχουν μη γραμμικά χαρακτηριστικά. Οι παραπάνω υβριδικές μέθοδοι εφαρμόζονται και στο πρόβλημα της μπλοκ διαγωνιοποίησης στοχαστικών μητρώων που μοντελοποιούν για παράδειγμα χημικές διεργασίες, μέσω μαρκοβιανών αλυσίδων. Τα αρχικά αποτελέσματα που έχουμε, υποδεικνύουν ότι η προσέγγιση αυτή μπορεί να βελτιώσει σημαντικά υπάρχουσες μεθόδους, παρέχοντας ταυτόχρονα προσεγγίσεις του πλήθους των μπλοκ που αντιστοιχούν σε σταθερές καταστάσεις της μαρκοβιανής αλυσίδας. Τέλος, προτείνουμε μια διαφορετική προσέγγιση με τον αλγόριθμο ομαδοποίησης Oriented k-windows ο οποίος, όπως και ο PDDP, χρησιμοποιεί ιδιάζοντα διανύσματα (ισοδύναμα, κύριους άξονες - PCA) με σκοπό την εξαγωγή πληροφορίας αναφορικά με τον κυρίαρχο προσανατολισμό των ομάδων στον Ευκλείδειο χώρο. Στη συνέχεια, παρουσιάζουμε αλγορίθμους ανάκτησης σχετικών κειμένων και αλγορίθμους κατηγοριοποίησης που βασίζονται στη "Λανθάνουσα Σημασιολογική Δεικτοδότηση" (LSI). Πιο συγκεκριμένα, παρουσιάζουμε ένα αλγοριθμικό πλαίσιο που στηρίζεται σε μια "μεθοδολογία αντιπροσώπων", με την οποία προσπαθούμε να προσεγγίσουμε σημασιολογικά μια συλλογή, εξάγοντας υποχώρους του χώρου στηλών του μητρώου όρων-κειμένων που προσεγγίζουν τον βέλτιστο υποχώρο της διάσπασης ιδιαζουσών τιμών. Η μεθοδολογία μας χρησιμοποιεί αλγορίθμους ομαδοποίησης, όπως οι υβριδικές μέθοδοι που αναφέραμε, με σκοπό τη διάσπαση του προβλήματος σε ένα σύνολο όσο γίνεται περισσότερο ανεξάρτητων προβλημάτων που μπορούν να λυθούν περισσότερο αποδοτικά. Μέσα από μια εκτεταμένη πειραματική μελέτη, δείχνουμε ότι η συγκεκριμένη μεθοδολογία μπορεί να βελτιώσει άλλες διαδεδομένες προσεγγίσεις (LSI, LLSF κ.λπ.). Επίσης, επεκτείνουμε και εφαρμόζουμε τη "μεθοδολογία αντιπροσώπων" σε μεθόδους πυρήνα, καθώς επίσης και στο πρόβλημα υπολογισμού μη αρνητικών παραγοντοποίησεων μητρώων (NMF). Δείχνουμε ότι η χρήση της μεθοδολογίας επιφέρει σημαντική μείωση του κόστους σε μνήμη και υπολογισμούς των μεθόδων πυρήνα και βελτίωση της ποιότητας των αποτελεσμάτων της NMF. Η διατριβή στάθηκε αφορμή για την ανάπτυξη ενός ολοκληρωμένου λογισμικού περιβάλλοντος. Πιο συγκεκριμένα, οι νέες μέθοδοι που αναφέραμε, καθώς και άλλες διαδεδομένες τεχνικές έχουν υλοποιηθεί και ενταχθεί στο περιβάλλον Text to Matrix Generator (TMG). Το TMG στηρίζεται κατά κύριο λόγο στη MATLAB ενώ μικρότερα τμήματά του έχουν γραφτεί σε Perl. Το TMG αποτελείται από έξι τμήματα, ενώ είναι εύκολα επεκτάσιμο. Τα τμήματα αυτά παρέχουν μια ευρεία συλλογή μεθόδων ανάκτησης πληροφορίας που αποτελείται από μεθόδους (i) κατασκευής και ανανέωσης μητρώων όρων-κειμένων, (ii) υπολογισμού προσεγγίσεων μειωμένης διάστασης και (iii) μη αρνητικών παραγοντοποιήσεων, (iv) ανάκτησης σχετικών κειμένων, (v) ομαδοποίησης και (vi) κατηγοριοποίησης. Για όλα τα παραπάνω, το εργαλείο παρέχει κατάλληλα προσαρμοσμένες γραφικές διεπαφές που διευκολύνουν το χρήστη. Εναλλακτικά, οι λειτουργίες του μπορούν να κληθούν απευθείας από τη γραμμή εντολών. Το TMG διευκολύνει την ταχεία προτοτυποποίηση αλγορίθμων και διατίθεται ελεύθερα μέσω ιστοσελίδας (http://scgroup.hpclab.ceid.upatras.gr/scgroup/Projects/TMG/). Από αναζητήσεις τεκμηριώνεται ότι έχει υποστηρίξει πολλούς επιστήμονες παγκοσμίως τόσο σε ερευνητικό όσο και σε εκπαιδευτικό επίπεδο. Περιγράφουμε επίσης τις πρόσφατες εργασίες μας για την ανάδειξη του TMG ως υπηρεσίας στον Παγκόσμιο Ιστό. Ειδικότερα, αναπτύσσεται λογισμικό για την απομακρυσμένη χρήση του TMG μέσω ειδικού API και τίθενται οι βάσεις για μελλοντική έρευνα που θα αφορά στην βελτιωμένη επίδοση και στην αποδοτική χρήση του συστήματος. / The amount of digital data is rapidly growing and continuously motivates research innovation in Information Retrieval. Much of the data is text, so there is an ever present need to push the field of Text Mining forward by designing and implementing novel, effective algorithms that attain high performance and reliability. It is also desirable to develop software environments that facilitate not only access to existing methods, but also enable the rapid prototyping, performance evaluation and incorporation of new algorithms for Text Mining. In this research we focus on algorithms that use Linear Algebra and Matrix Analysis tools as computational kernels. We use the term spectral to highlight the fact that our methods rely on the spectral characteristics of the underlying term-document matrices that encode the texts under study. We consolidate our new and existing algorithms in a software environment, called TMG, that we built on top of MATLAB and Perl. First, we consider the basic text mining tasks, namely clustering, ad-hoc retrieval and text classication. In clustering, we focus on a well-known spectral method, called PDDP (Principal Direction Divisive Partitioning) and investigate hybrid methods that combine PDDP and standard workhorses such as k-means. In particular, the proposed methods improve the performance of the aforementioned algorithms, regarding the quality of the attained clustering and/or their speed. Compared with k-means, our algorithms eliminate the non-determinism originating from k-means' initialization phase. We also propose a framework for kernel methods, that can be used in case the data exhibit non-linearities. Our spectral clustering algorithms are applied in sparse matrix reordering, specifically in the block diagonalization of row stochastic matrices. In addition to helping in the intepretation of a recent method for identifying metastable states of Markov chains, they also provide the means to improve their performance. Initial results, demonstrate that the proposed methodology can improve significantly over existing techniques, deriving approximations of the number of blocks corresponding to dinstict stable states of the underlying Markov chain. We also show how to use spectral methods to improve the performance of a density-based clustering approach, called Oriented k-windows. In particular, the algorithm uses information derived from the Principal Component Analysis (PCA), in order to guide a windowing technique, namely k-windows, that could give insights about the data orientation. The next part of the thesis deals with ad-hoc retrieval and classification methods, based on Latent Semantic Indexing (LSI). We propose an algorithmic framework based on a "representatives methodology", in order to approximate a collection semantically, by extracting subspaces of the column space of the term-document matrix, that approximate the optimal subspace derived by the SVD. Our methodology uses clustering techniques, like the aforementioned hybrid methods, in a preprocessing stage. Our objective is to split the problem into a set of independent subproblems that could be solved more efficiently. Results from extensive experimentation indicate that our methodology can improve a state-of-the-art method like LSI. We also apply the representatives methodology to kernel methods and Nonnegative Matrix Factorization (NMF). Extensive numerical experiments indicate that this methodology improves the computational cost and memory requirements of kernel methods and also increases the quality of the nonnegative approximations. We have incorporated all the proposed methods in a software environment, called Text to Matrix Generator (TMG). The first release of TMG was before this Ph.D. was even started. but has since undergone several upgrades and rewrites. TMG currently consists of six easily extensible modules. These modules provide methods for (i) constructing and updating term-document matrices, (ii) computing low rank approximations and (iii) non negative factorizations, and (iv) ad-hoc retrieval, (v) clustering and (vi) classification. TMG is accessible in two primary modes, graphical and command line and is freely downloadable from its webpage (http://scgroup.hpclab.ceid.upatras.gr/scgroup/Projects/TMG/). As our usage logs indicate, TMG is being used worldwide for research and educational uses. We also describe a brief overview of open problems and ongoing work. We describe our first version of "remote TMG", that views TMG as a Web resource and provides remote access mode to it by means of a special API.