Αλγόριθμοι Ομαδοποίησης Και Μείωσης Διάστασης Για Δεδομένα Του Παγκοσμίου Ιστού

Abstract

Ο κύριος στόχος της παρούσας διπλωματικής εργασίας είναι η υλοποίηση και πειραματική αξιολόγηση δυο συγκεκριμένων αλγορίθμων μείωσης διάστασης, που προορίζονται να χρησιμοποιηθούν πάνω σε δεδομένα του Παγκοσμίου Ιστού. Ο πρώτος αλγόριθμος που εξετάζουμε στηρίζεται στη διαδικασία της ομαδοποίησης, ενώ ο δεύτερος στηρίζεται σε μια τεχνική που ανήκει στην οικογένεια της Πιθανοτικής Ανάλυσης Κρυμμένης Σημασιολογίας. Συνεπώς, η πορεία προς την εκπλήρωση του τελικού στόχου περιλαμβάνει τέσσερα διακριτά στάδια: την υλοποίηση ορισμένων αλγορίθμων ομαδοποίησης, την υλοποίηση του αλγορίθμου Πιθανοτικής Ανάλυσης Κρυμμένης Σημασιολογίας, την αξιοποίηση των παραπάνω στα πλαίσια των δυο αλγορίθμων μείωσης διάστασης και, τέλος, την πειραματική αξιολόγηση των τελευταίων πάνω σε πραγματικά δεδομένα του Ιστού.Στο πρώτο στάδιο αναπτύσσεται σε Java ένα πλαίσιο εργασίας λογισμικού, που βασίζεται στις κατάλληλες δομές δεδομένων και στον απαραίτητο αντικειμενοστραφή σχεδιασμό, προκειμένου να χρησιμοποιηθεί για την υλοποίηση αλγορίθμων ομαδοποίησης δεδομένων του Ιστού. Επιπλέον, υλοποιούνται τρεις συγκεκριμένοι αλγόριθμοι ομαδοποίησης, η συμπεριφορά των οποίων εξετάζεται πάνω σε ένα συγκεκριμένο σύνολο δεδομένων. Στο δεύτερο στάδιο υλοποιείται σε Java αλγόριθμος που ανήκει στην ευρύτερη οικογένεια της Πιθανοτικής Ανάλυσης Κρυμμένης Σημασιολογίας. Ο συγκεκριμένος αλγόριθμος υιοθετεί ένα πιθανοτικό μοντέλο παραγωγής των δεδομένων από κάποιες μη ορατές μεταβλητές, το οποίο ονομάζεται Μοντέλο των Όψεων. Στη συνέχεια, χρησιμοποιώντας την τεχνική της Μεγιστοποίηση της Αναμενόμενης Τιμής κατά τη διάρκεια μιας διαδικασίας εκπαίδευσης, καταλήγει σε μια τοπικά βέλτιστη εκτίμηση των παραμέτρων του μοντέλου. Στο τρίτο στάδιο υλοποιούνται σε Java οι δύο αλγόριθμοι μείωσης διάστασης που αποτελούσαν από την αρχή τον βασικό στόχο της εργασίας. Ο πρώτος αλγόριθμος βασίζεται στην ομαδοποίηση και ονομάζεται Εννοιολογική Δεικτοδότηση, ενώ ο δεύτερος βασίζεται στην εκτίμηση των παραμέτρων του πιθανοτικού Μοντέλου των Όψεων. Ένας αλγόριθμος μείωσης διάστασης επιδιώκει, σε γενικές γραμμές, να απεικονίσει τα πολυδιάστατα διανύσματα των δεδομένων που του παρέχονται σε έναν χώρο μικρότερης διάστασης από τον αρχικό. Τα κίνητρα γι' αυτήν την προσπάθεια είναι αφενός η εξοικονόμηση υπολογιστικών πόρων και αφετέρου η ανακάλυψη συσχετίσεων μεταξύ στοιχείων του συνόλου δεδομένων, που δεν είναι ορατές στην πολυδιάστατη αναπαράσταση. Στο τελευταίο στάδιο της εργασίας αξιολογείται η αποτελεσματικότητα της μείωσης διάστασης ως διαδικασίας ανακάλυψης κρυμμένων συσχετίσεων. Προφανώς, εξετάζουμε τους δυο συγκεκριμένους αλγορίθμους μείωσης διάστασης που υλοποιούμε στα πλαίσια της εργασίας. Η ποσοτικοποίηση της αξιολόγησης επιτυγχάνεται με τον υπολογισμό ενός δείκτη ποιότητας, που ονομάζεται Βελτίωση Ανάκλησης, πάνω σε ένα σύνολο εγγράφων του Ιστού. Η Βελτίωση Ανάκλησης εκφράζει το κατά πόσο η μείωση διάστασης αυξάνει την ακρίβεια της ανάκλησης εγγράφων βάσει ερωτημάτων κειμένου.