PYXIDA Institutional Repository
and Digital Library
 Home
Collections :

Title :Clustering time series data
Alternative Title :Συσταδοποίηση χρονοσειρών
Creator :Pierrakos, Georgios
Πιερράκος, Γεώργιος
Contributor :Karlis, Dimitrios (Επιβλέπων καθηγητής)
Ntzoufras, Ioannis (Εξεταστής)
Chatziantoniou, Damianos (Εξεταστής)
Athens University of Economics and Business, Department of Management Science and Technology (Degree granting institution)
Type :Text
Extent :105p.
Language :en
Identifier :http://www.pyxida.aueb.gr/index.php?op=view_object&object_id=8222
Abstract :The present thesis aims to examine all the factors that need to be defined when applying clustering methodologies to time series data. However, the adaptation of existing methodologies to time series is not straightforward; the intricacies of high dimensionality, ordered and correlated observations need also to be addressed. The problem definition amounts to two separate tasks: (i) identifying the criteria to assess the value of time series clustering methodologies and then, (ii) identifying which clustering methodology works best. The former task reveals that the problem is one of multi-objective optimization: both accuracy (measured by the Silhouette cvi – cluster validity index) and efficiency (measured by algorithm execution times) need to be maximized so that meaningful methodologies can be proposed. The latter task entails testing a number of methodologies using a sample dataset. A set of such methodologies use static data clustering approaches, hierarchical, partitioning and fuzzy, using time series distance definitions. Bibliography reveals that the most prominent distance definition is dynamic time warping. A number of related parameters need to be examined: step pattern, window size and sample timeseries selection (for algorithms that build clusters around representative timeseries). Another set of methodologies use a hierarchical algorithm fed with clipped series, Pearson correlation and Lp-norm (euclidean and Manhattan) distance definitions. The sample dataset consists of the diurnal variation of bike rental commencements of the Capital Bikeshare scheme in Washington DC, USA across the various stations. Results obtained are also examined on the map, to check whether time series clusters lead to geographical clusters as well. Main conclusions are that: (i) no single distance definition is best in all cases, the semantics of the underlying process need to be very well understood and (ii) while the dtw improves on standard Lp-norm distance definitions, it is associated with a heavy time cost, reducing scalability.
Η παρούσα μελέτη στοχεύει στην εξέταση των παραγόντων που χρειάζεται να καθοριστούν όταν εφαρμόζονται μεθοδολογίες συσταδοποίησης σε χρονοσειρές. Ωστόσο, η προσαρμογή καθιερωμένων μεθοδολογιών σε χρονοσειρές δεν είναι απλή· οι περιπλοκές των πολυδιάστατων δειγματοχώρων και των διατεταγμένων και συσχετισμένων παρατηρήσεων πρέπει να αντιμετωπιστούν. Ο ορισμός του προβλήματος αντιστοιχεί σε δυο ξεχωριστά σκέλη: (α) αναγνώριση των κριτηρίων που χρειάζονται για να εκτιμήσουν την αξία της κάθε μεθοδολογίας και, μετά, (β) αναγνώριση ποια από τις προτεινόμενες μεθοδολογίες λειτουργεί καλύτερα. Το πρώτο σκέλος αποκαλύπτει ότι πρόκειται για ένα πρόβλημα πολυπαραγοντικής βελτιστοποίησης: πρέπει τόσο η ακρίβεια όσο και η αποδοτικότητα να είναι οι μέγιστες δυνατές, ούτως ώστε να προταθούν μεθοδολογίες με νόημα. Το δεύτερο περιλαμβάνει δοκιμασία ενός αριθμού απο μεθοδολογίες στο διαθέσιμο σύνολο δεδομένων. Μια ομάδα από αυτές χρησιμοποιεί προϋπάρχουσες προσεγγίσεις συσταδοποίησης για στατικά δεδομένα, ιεραρχικές, διαμεριστικές και ασαφείς, με ορισμούς αποστάσεων που είναι κατάλληλοι για χρονοσειρές. Η βιβλιογραφία αποκαλύπτει ότι ο προεξάρχων ορισμός απόστασης μεταξύ χρονοσειρών είναι η δυναμική χρονική στρέβλωση. Οι σχετιζόμενες παράμετροι πρέπει επίσης να εξεταστούν: πρότυπο βηματισμού, μέγεθος παραθύρου, επιλογή αντιπροσωπευτικής χρονοσειράς. Μια άλλη ομάδα χρησιμοποιεί τον ιεραρχικό αλγόριθμο που τροφοδοτείται από ορισμούς αποστάσεων περικομμένων χρονοσειρών, συσχέτισης κατά Pearson και Lp-νόρμας (ευκλίδειας και Μανχάταν απόστασης). Το σύνολο δεδομένων που χρησιμοποιήθηκε είναι η ημερήσια διακύμανση στην έναρξη ενοικιάσεων ποδηλάτων μεταξύ των σταθμών που συμμετέχουν στο σύστημα Capital Bikeshare στην Ουάσιγκτον των ΗΠΑ. Τα αποτελέσματα που εξάγονται εξετάζονται στον χάρτη για να φανεί αν οι ομαδοποιημένες χρονοσειρές αντιστοιχούν και σε γεωγραφικές συστάδες. Βασικά συμπεράσματα της μελέτης είναι ότι: (α) δεν υπάρχει ένας ορισμός απόστασης που να είναι ο καλύτερος σε κάθε περίπτωση, πρέπει να γίνεται πάντα κατανοητή η φύση της διεργασίας που παράγει τη χρονοσειρά και (β) αν και η δυναμική χρονική στρέβλωση δίνει καλύτερα αποτελέσματα από τις Lp-νόρμες, σχετίζεται όμως με ένα μεγάλο κόστος χρόνου που περιορίζει την επεκτασιμότητά των σχετιζόμενων αλγορίθμων.
Subject :Unsupervised learning
Time series
Clustering
Dynamic time warping
Μη εποπτευόμενη μάθηση
Χρονοσειρές
Συσταδοποίηση
Δυναμική χρονική στρέβλωση
Date Available :2021-01-08 05:33:35
Date Issued :08/26/2020
Date Submitted :2021-01-08 05:33:35
Access Rights :Free access
Licence :

File: Pierrakos_2020.pdf

Type: application/pdf