Η διαρκώς αυξανόμενη διαθεσιμότητα ηλεκτρονικών πηγών πληροφόρησης έχει δημιουργήσει
νέα δεδομένα και απαιτήσεις στην περιοχή της Ανάκτησης Πληροφορίας. Υπάρχει αδιάκοπη
ανάγκη για βελτίωση των υπαρχόντων και σχεδίαση νέων αλγορίθμων, που να επιτυγχάνουν
υψηλή απόδοση και αξιοπιστία. Ένα επιπλέον ζητούμενο είναι η κατασκευή λογισμικού
περιβάλλοντος που θα διευκολύνει τη χρήση υπαρχόντων αλγορίθμων, την εισαγωγή νέων,
το συνδυασμό τους και τη συγκριτική αξιολόγησή τους.
Στην παρούσα διδακτορική διατριβή, εστιάζουμε σε μεθόδους ανάκτησης πληροφορίας (με
έμφαση στην ανάκτηση κειμένου), που έχουν στον πυρήνα τους τεχνολογίες Γραμμικής
Άλγεβρας και πιο συγκεκριμένα σε τεχνικές που αξιοποιούν τα φασματικά χαρακτηριστικά
των μητρώων όρων-κειμένων. Υπενθυμίζουμε ότι περίοπτη θέση στην περιοχή της Ανάκτησης
Πληροφορίας, όσον αφορά τις τεχνικές της γραμμικής άλγεβρας, κατέχουν οι ιδιάζουσες
τιμές και τα ιδιάζοντα διανύσματα των μητρώων. Περιγράφουμε επίσης το σχεδιασμό και
την κατασκευή ενός ολοκληρωμένου περιβάλλοντος που διευκολύνει τους χρήστες στην
ανάπτυξη, χρήση και αξιολόγηση των αλγορίθμων που στηρίζεται στο εξαιρετικά διαδεδομένο
περιβάλλον της 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.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/2103 |
| Date | 20 October 2009 |
| Creators | Ζεϊμπέκης, Δημήτριος |
| Contributors | Γαλλόπουλος, Ευστράτιος, Zeimpekis, Dimitrios, Βραχάτης, Μιχαήλ, Παπαθεοδώρου, Θεόδωρος, Βαζιργιάννης, Μιχαήλ, Μακρής, Χρήστος, Μεγαλοοικονόμου, Βασίλειος, Στάμου, Σοφία, Γαλλόπουλος, Ευστράτιος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0039 seconds