Εξόρυξη γνώσης από βάσεις χρονοσειρών: επιλογή χαρακτηριστικών και κατηγοριοποίηση

Abstract

The objective of the thesis is to develop and apply data mining techniques in time series databases, and in particular to investigate for the most relevant time series measures to be used for feature based clustering and classification. In the course of this work, the following goals were achieved: 1) a large number of features used in time series analysis were computed, 2) new algorithms have been developed for optimal feature subset selection, 3) they have been compared to other currently favored feature selection methods on simulated and real world databases, especially epileptic electroencephalograms (EEG), 4) the proposed methods were shown to be able to find a small subset of the most useful features for classification purposes, and particularly for epileptic EEG it was shown that such a feature subset can possibly play the role of "biomarker" and distinguish the late preictal stage, and finally 5) two menu-based Matlab modules were developed, the first for the computation of a large number of measures on time series databases, and the second for feature selection, and feature-based classification and clustering. In this thesis, data mining techniques were applied on time series using a variety of measures (linear, nonlinear, oscillation related measures, and other measures) that were calculated on each time series and are supposed each to capture a different characteristic of the time series. In the study we considered various sets of features (10-312 features), including the most known measures of the analysis of scalar time series, especially the measures used in EEG analysis. Our results showed that oscillation related features are among the first to be included in the optimal feature subset. The first problem we investigated in the search of best features was the effect of standardization and normalization methods on the feature selection and subsequently the performance of the classification. We evaluated different standardization methods and proposed a new method, the transform to Gaussian distribution, which turned out to have good scaling and stability properties, and could better handle outliers. We developed two feature selection schemes that derive small and optimal feature subsets. The first scheme is called Forward Sequential Selection with CRI (FSSwCRI) and is wrapper based on the k-means clustering algorithm in order to derive the feature subset that classifies best the time series database, according to the criterion of the corrected Rand index. The second feature selection scheme we developed is a conditional mutual information filter based on nearest neighbour estimate and is called CMINN. Applications of CMINN to simulations and to ten benchmark databases showed that CMINN is superior compared to mRMR and MaxiMin and derive feature subsets of smaller cardinality. FSSwCRI was applied to classification of preictal states in epileptic EEG databases, were it was compared to Support Vector Machines with Recursive Feature Elimination (SVM-RFE) and to a simple Mutual Information (MI) filter. We concluded that a global feature subset of the 16 most frequent features selected by FFSSwCRI can play the role of a biomarker and distinguish early and late preictal states.

Ο σκοπός της διατριβής αυτής είναι η ανάπτυξη και η χρήση τεχνικών εξόρυξης δεδομένων σε βάσεις δεδομένων χρονοσειρών και ειδικότερα η διερεύνηση μεθόδων επιλογής των πιο σχετικών χαρακτηριστικών από τις χρονοσειρές τα οποία θα μπορούν να χρησιμοποιηθούν για συσταδοποίηση και κατηγοριοποίηση. Κατά την διάρκεια των εργασιών επιτεύχθηκαν οι παρακάτω στόχοι: 1) υπολογίσθηκε μεγάλο πλήθος χαρακτηριστικών που χρησιμοποιούνται στην ανάλυση χρονοσειρών, 2) αναπτύχθηκαν νέες μέθοδοι επιλογής βέλτιστου υποσυνόλου χαρακτηριστικών για κατηγοριοποίηση και συσταδοποίηση βάσεων δεδομένων, 3) έγινε σύγκριση της απόδοσης των μεθόδων αυτών με άλλες εφάμιλλες μεθόδους 4) όλες οι τεχνικές εφαρμόσθηκαν σε προσομοιωτικά και πραγματικά δεδομένα χρονοσειρών, κυρίως ηλεκτροεγκεφαλογραφημάτων (EEG), ώστε τα επιλεγμένα βέλτιστα υποσύνολα χαρακτηριστικών από τις μεθόδους που αναπτύξαμε, να παίξουν τον ρόλο χρήσιμων ¨βιοδεικτών¨ σε πραγματικές καταστάσεις και 5) αναπτύχθηκαν δύο λογισμικά βασισμένα στην πλατφόρμα του Matlab, το πρώτο εκ των οποίων υπολογίζει μεγάλο πλήθος χαρακτηριστικών από βάσεις χρονοσειρών και το δεύτερο επιλέγει βέλτιστα υποσυνόλων χαρακτηριστικών για συσταδοποίηση και κατηγοριοποίηση. Στην διατριβή αυτή οι τεχνικές εξόρυξης δεδομένων που εφαρμόσθηκαν στις χρονοσειρές χρησιμοποιούσαν μια μεγάλη ποικιλία από χαρακτηριστικά (γραμμικά, μη-γραμμικά, χαρακτηριστικά σχετικά με ταλαντώσεις καθώς και άλλα χαρακτηριστικά) τα οποία εκτιμήθηκαν σε κάθε χρονοσειρά θεωρώντας ότι το καθένα από αυτά μπορεί να συλλάβει μια ξεχωριστή της ιδιότητα. Εξετάσαμε διάφορα σύνολα χαρακτηριστικών (10–312) μέσα στα οποία συμπεριλαμβάνονται τα πιο γνωστά χαρακτηριστικά από την ανάλυση μονοδιάστατων χρονοσειρών και ειδικότερα αυτά που χρησιμοποιούνται στην ανάλυση EEG. Τα αποτελέσματά μας έδειξαν ότι τα χαρακτηριστικά που σχετίζονται με ταλαντώσεις εμπεριέχονται μέσα στα βέλτιστα υποσύνολα χαρακτηριστικών. Το πρώτο πρόβλημα που διερευνήθηκε ήταν η επίδραση των μεθόδων τυποποίησης και κανονικοποίησης στην επιλογή των βέλτιστων χαρακτηριστικών και κατά συνέπεια στην απόδοση της κατηγοριοποίησης. Αξιολογήσαμε διαφορετικές μεθόδους τυποποίησης και προτείναμε μια νέα, τον μετασχηματισμό σε Γκαουσιανή κατανομή, η οποία επιφέρει καλή κλιμάκωση των τιμών, σταθερή απόδοση και χειρίζεται καλύτερα τα ακραία σημεία. Αναπτύξαμε δύο νέες μεθόδους επιλογής χαρακτηριστικών από τις οποίες προκύπτουν μικρά και βέλτιστα υποσύνολα χαρακτηριστικών. Η πρώτη μέθοδος καλείται FSSwCRI και είναι ένα σειριακά προς τα εμπρός περιτύλιγμα επιλογής χαρακτηριστικών το οποίο βασίζεται στον αλγόριθμο k-means ώστε να επιλέγει το υποσύνολο χαρακτηριστκών που θα κατηγοριοποιεί καλύτερα τις βάσεις των χρονοσειρών σύμφωνα με το κριτήριο του διορθωμένου δείκτη Rand (CRI). Η δεύτερη μέθοδος επιλογής χαρακτηριστικών που αναπτύξαμε είναι ένα φίλτρο επιλογής χαρακτηριστικών που βασίζεται στη δεσμευμένη αμοιβαία πληροφορία με εκτιμητή κοντινότερων γειτόνων, η οποία λαμβάνει υπόψιν τις αλληλεπιδράσεις σχετικότητας και πλεονασμού μεταξύ του υποψηφίου προς επιλογή χαρακτηριστικού, της μεταβλητής των κλάσεων και του συνόλου των ήδη επιλεγμένων χαρακτηριστικών. Τη μέθοδο αυτή σε συνδυασμό με ένα νέο κριτήριο τερματισμού την ονομάσαμε CMINN. Εφαρμογές της CMINN σε προσομοιώσεις και σε δέκα βάσεις δεδομένων αναφοράς έδειξαν ότι υπερέχει έναντι των μεθόδων mRMR και MaxiMin, επιλέγοντας υποσύνολα μικρότερης πληθικότητας. Η μέθοδος FSSwCRI εφαρμόσθηκε για τον διαχωρισμό προεπιληπτικών καταστάσεων από καταγραφές EEG, όπου συγκρίθηκε με τη μέθοδο SVM-RFE και με ένα απλό φίλτρο αμοιβαίας πληροφορίας. Συμπεράναμε ότι ένα γενικό υποσύνολο χαρακτηριστικών με τα 16 πιο συχνά επιλεγμένα χαρακτηριστικά που επέλεξε ο FSSwCRI, μπορεί να παίξει το ρόλο βιοδείκτη που θα διαχωρίζει τις προεπιληπτικές καταστάσεις λίγο πριν και πολύ πριν από την επιληπτική κρίση.