Εξόρυξη πληροφορίας από χρονοσειρές: Προγραμματιστική υλοποίηση μέτρων ομοιότητας

Abstract

Η παρούσα εργασία παρουσιάζει διάφορες τεχνικές που χρησιμοποιούνται για την αποτελεσματική και αξιόπιστη εξόρυξη πληροφορίας από χρονοσειρές. Οι κύριες ενέργειες που πραγματοποιούνται με την εφαρμογή τεχνικών αυτών είναι η συσταδιοποίηση, η κατηγοριοποίηση, η ανακάλυψη κανόνων συσχέτισης και η ανάκτηση όμοιων εγγράφων. Στο επίκεντρο των ενεργειών αυτών βρίσκεται η έννοια της ομοιότητας και της μέτρησης της. Η χρονική διάσταση των δεδομένων όμως θέτει δύο βασικά ζητήματα τα οποία θα πρέπει να λαμβάνονται σοβαρά υπόψη κατά την αναζήτηση ομοιοτήτων. Το πρώτο ζήτημα είναι η επιλογή ενός κατάλληλου μέτρου ομοιότητας το οποίο θα επιτρέπει τον εντοπισμό όμοιων χρονοσειρών , οι οποίες δεν ταυτίζονται απαραιτήτως. Το δεύτερο ζήτημα αφορά στην αναπαράσταση των χρονοσειρών με στόχο τη μείωση της υψηλής διαστατικότητας τους (dimensionality). Η εργασία εστιάζεται κυρίως στη μέτρηση της ομοιότητας μεταξύ των χρονοσειρών με την εφαρμογή ενός μέτρου ομοιότητας, όπως είναι η Ευκλείδια απόσταση , το Dynamic Time Warping (DTW) με ή χωρίς τους περιορισμούς Sakoe/Chiba και Itakura. Με τη χρήση της βιβλιοθήκης ελεύθερου λογισμικού java-ml και στο περιβάλλον ανάπτυξης λογισμικού Eclipse τροποποιήθηκε ο αλγόριθμος DTW, υλοποιήθηκαν τα φίλτρα Sakoe/Chiba και Itatura και ενσωματώθηκαν στην βιβλιοθήκη java-ml. Επίσης πραγματοποιήθηκαν πολλά πειράματα για να αξιολογηθεί η αποδοτικότητα και η αξιοπιστία αυτών των τεχνικών αναζήτησης ομοιότητας χρησιμοποιώντας αλγόριθμο του Εγγύτερου Γείτονα (1-Nearest Neighbor) της java-ml. Η πειραματική αξιολόγηση αφορά τους αλγόριθμους της Ευκλείδιας απόστασης , του Dynamic Time Warping , του Sakoe/Chiba και του Itakura, ώστε να εντοπιστούν οι διαφορές και οι ομοιότητες τους σε σχέση με τα ποσοστά εσφαλμένης κατηγοριοποίησης και τους χρόνους απόκρισης τους κατά τη διάρκεια της αναζήτησης όμοιων χρονοσειρών.