Αποδοτικοί αλγόριθμοι για την Συσταδοποίηση Χρονοσειρών μέσω Προσέγγισης με Gaussian Processes

Abstract

Διάφορες τεχνικές εξόρυξης δεδομένων χρησιμοποιούνται στις μέρες μας για την ανάλυση δεδομένων. Ανάμεσα τους, η συσταδοποίηση είναι η πιο διαδε- δομένη και χρησιμοποιείται σε περιπτώσεις που δεν υπάρχει κάποια προηγούμενη γνώση για τη δομή των συστάδων. Δεδομένα από πολλά πεδία όπως η οικο- νομία, η υγεία κ.α. αποθηκεύονται σε μορφή χρονοσειρών. Η συσταδοποίησή τους έχει ποικίλες εφαρμογές στο γονιδιώμα, στην ιατρική, στα οικονομικά. Το πρόβλημα είναι δύσκολο εξαιτίας του θορύβου και της μεγάλης διαστατικότητας που εκ φύσεως έχουν οι χρονοσειρές. Σε αυτή τη διπλωματική ασχολούμαστε με τη συσταδοποίηση χρονοσειρών με βάση το σχήμα τους. Το σημαντικότερο συστατικό των αλγορίθμων αυτής της κατηγορίας είναι η επιλογή του κατάλλη- λου μέτρου ομοιότητας. Το μέτρο αυτό θα πρέπει να συγκρίνει αποτελεσματικά τα σχήματα των χρονοσειρών. Η πιο διαδεδομένη τέτοια απόσταση είναι η Dy- namic Time Warping (DTW), η οποία όμως έχει τετραγωνική πολυπλοκότητα που επηρεάζει σημαντικά την πολυπλοκότητα των αλγορίθμων συσταδοποίησης. Οι περισσότερο υποσχόμενες λύσεις για τη μείωση της παραπάνω πολυ- πλοκότητας περιλαμβάνουν πρώτα την εφαρμογή μεθόδων για τη μείωση της διαστατικότητας των χρονοσειρών και έπειτα τη χρήση κλασικών αλγορίθμων συσταδοποίησης στα μειωμένης διαστατικότητας δεδομένα. Σε αυτή τη διπλω- ματική προτείνουμε μία νέα μέθοδο δύο σταδίων για τη συσταδοποίηση χρο- νοσειρών. Πρώτα μοντελοποιούμε τις χρονοσειρές με ορισμένα σημεία που ονομάζονται inducing points χρησιμοποιώντας Sparse Gaussian Process Re- gression [68], η οποία είναι μια προσεγγιστική μέθοδος για Gaussian Process Regression. Στη συνέχεια, οι χρονοσειρές περιγράφονται με τα λιγότερα σε αριθμό inducing points τα οποία οργανώνονται σε συστάδες με την εφαρμογή του αλγορίθμου k-means χρησιμοποιώντας ως μέτρο απόστασης μια τροποποι- ημένη εκδοχή της DTW. Τα πειράματα μας δείχνουν ότι η προσέγγισή μας δίνει μια γρήγορη και αποδοτική μέθοδο συσταδοποίησης.