Η παρούσα διπλωματική εργασία έχει ως βασικό στόχο τη μελέτη και την αξιολόγηση της απόδοσης αλγορίθμων συσταδοποίησης ακολουθιακών χωροχρονικών δεδομένων, χρησιμοποιώντας κάθε φορά διαφορετικά μέτρα απόστασης/ομοιότητας με σκοπό την ανάδειξη των πλεονεκτημάτων και των μειονεκτημάτων τους. Συγκεκριμένα, εφαρμόζονται μετρικές συναρτήσεις απόστασης (Ευκλείδεια, Manhattan, Chebyshev, Ευκλείδια STARTEND), και μη μετρικές συναρτήσεις απόστασης είτε βασισμένες στη δυναμική χρονική στρέβλωση (Dynamic Time Warping), είτε βασισμένες στην "επεξεργασία" της απόστασης (Edit Distance on Real sequence) ή βασισμένες στη μεγαλύτερη κοινή υποαλληλουχία (Longest Common Subsequence). Ποικίλοι μετασχηματισμοί τροχιών (επαναδειγματολειψία, προσθήκη θορύβου και μετατόπιση σημείου) ελεγχόμενοι από δυο παραμέτρους, τον ρυθμό και την απόσταση, εφαρμόζονται σε πραγματικά και συνθετικά σύνολα δεδομένων τροχιών. Για κάθε μετασχηματισμό, αξιολογείται η ομαδοποίηση του αρχικού συνόλου δεδομένων και των μετασχηματισμένων συνόλων δεδομένων ανάλογα με την τιμή της παραμέτρου που "τρέχει". Τα εξαγόμενα αποτελέσματα της εκτενούς πειραματικής μελέτης χρησιμοποιούνται για την αξιολόγηση της εγκυρότητας των ομαδοποιήσεων που επιτυγχάνονται από τον αλγόριθμο optics και την ιεραρχική ομαδοποίηση με τη μέθοδο Ward, αντίστοιχα.
This thesis has as main objective to study and evaluate the performance of clustering algorithms considering sequential spatiotemporal data, each time using a different distance/similarity measure in order to highlight its advantages and disadvantages. Specifically, we apply metric distance functions (Euclidean, Manhattan, Chebyshev EuclideanSTARTEND), as well as non-metric distance functions, based either on dynamic time warping (DTW), or on editing distance on real sequence (EDR) or on longest common subsequence (LCSS). Various trajectories transformations (re-sampling, adding noise and point shift) controlled by two parameters, the rate and distance, are applied to real and synthetic trajectory datasets. For each transformation, the clustering of the original data set and the transformed data sets is evaluated depending on the value of the parameter which is not fixed. The results derived from the extensive experimental study are used to assess the validity of clusters obtained by the Optics clustering algorithm and hierarchical clustering via the Ward method, respectively.
