Συντάχθηκε 16-12-2016 08:00
από Esthir Gelasaki
Email συντάκτη: egelasaki<στο>tuc.gr
Ενημερώθηκε:
16-12-2016 13:18
Ιδιότητα: υπάλληλος.
ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Μεταπτυχιακών Σπουδών
ΠΑΡΟΥΣΙΑΣΗ ΜΕΤΑΠΤΥΧΙΑΚΗΣ ΕΡΓΑΣΙΑΣ
ΙΩΑΝΝΑΣ ΒΟΥΡΛΑΚΗ
με θέμα
ΑΥΤΟΜΑΤΟΠΟΙΗΜΕΝΗ ΟΜΑΔΟΠΟΙΗΣΗ ΜΕΓΑΛΩΝ ΔΕΔΟΜΕΝΩΝ: ΕΦΑΡΜΟΓΗ ΣΤΗΝ ΕΞΑΓΩΓΗ ΚΑΤΗΓΟΡΙΩΝ ΤΟΥ ΚΑΡΚΙΝΟΥ ΤΡΑΧΗΛΟΥ ΤΗΣ ΜΗΤΡΑΣ ΑΠΟ ΚΑΜΠΥΛΕΣ ΟΠΙΣΘΟΣΚΕΔΑΣΗΣ
SELF-ORGANIZED CLUSTERING OF BIG DATA: APPLICATION ON THE EXTRACTION OF CERVICAL CLASSES FROM BACKSCATTERING CURVES
Εξεταστική Επιτροπή
Καθηγητής Μιχαήλ Ζερβάκης (επιβλέπων)
Καθηγητής Κωνσταντίνος Μπάλας
Αναπληρωτής Καθηγητής Μιχαήλ Λαγουδάκης
Περίληψη
Η εξόρυξη δεδομένων είναι ένα διεπιστημονικό πεδίο της επιστήμης των υπολογιστών. Είναι η υπολογιστική διαδικασία ανακάλυψης προτύπων σε μεγάλα σύνολα δεδομένων και περιλαμβάνει μεθόδους στη διεπαφή της τεχνητής νοημοσύνης, μηχανικής μάθησης, στατιστικής και συστημάτων ανάλυσης δεδομένων.
Στα πλαίσια αυτά, η ομαδοποίηση αποτελεί μια μη επιβλεπόμενη προσέγγιση μάθησης με στόχο να οργανώσει τα διαθέσιμα δεδομένα σε συμπαγείς κλάσεις σύμφωνα με κάποιο κριτήριο ομοιότητας. Η συμβολή της ομαδοποίησης στην ιατρική και στη βιολογία είναι πού σημαντική. Πιο συγκεκριμένα, στην διάγνωση καρκίνου, η μεθοδολογία της εξαγωγής, επεξεργασίας και ερμηνείας των σχετικών πληροφοριών από τα διαθέσιμα δεδομένα είναι υψίστης σημασίας. Με αυτήν την έννοια η παρούσα εργασία εξετάζει τις τρεις βασικές πτυχές της ομαδοποίησης, την σταθερότητα, την γενίκευση και την διαχωρισημότητα των κλάσεων. Στόχος της εργασίας είναι να αξιολογήσει και να ερμηνεύσει τις κατάλληλες πληροφορίες από τα επεξεργασμένα σύνολα δεδομένων και ιδιαίτερα να κάνει την διαδικασία ομαδοποίησης αυτοματοποιημένη και αποδοτική για την οργάνωση μεγάλου όγκου δεδομένων.
Σχετικά με τα προβλήματα σταθερότητας των αποτελεσμάτων επιχειρούμε να βελτιώσουμε το αποτέλεσμα της ομαδοποίησης αναβαθμίζοντας διαδοχικά τα κέντρα των κλάσεων στη βάση της παρούσας και προηγούμενης θέσης τους. Επίσης προσπαθούμε να αξιοποιήσουμε την αρχική κλινική πληροφορία, την μετέπειτα πληροφορία που εξάγεται από την ανάλυση των δεδομένων και την στατιστική κατανομή του εξεταζόμενου πληθυσμού. Υπό το πρίσμα αυτό, εξετάζουμε το πρόβλημα σταθερότητας του k-means αλγορίθμου, προτείνοντας ένα νέο αλγοριθμικό τρόπο για την αυτό-οργάνωση των δεδομένων, υιοθετώντας μία επαναληπτική προσέγγιση στον αλγόριθμο ομαδοποίησης k-means.
Βασιζόμενοι στην περεταίρω διερεύνηση των προβλημάτων σταθερότητας της ομαδοποίησης, προτείνουμε μια νέα αλγοριθμική προσέγγιση για την εξαγωγή πληροφοριών από το σύνολο των δεδομένων εισόδου και την αυτό-οργάνωση των δεδομένων, συνδυάζοντας την ομαδοποίηση με την επαναληπτική δειγματοληψία των δεδομένων. Χρησιμοποιώντας ανα-δειγματοληψία με αντικατάσταση επιχειρούμε να παράγουμε πολλαπλές εκδοχές του ίδιου πληθυσμού και πολλαπλά κέντρα από τον k-means. Έπειτα, ο μεγάλος αριθμός κέντρων που παράγεται, αναδιοργανώνεται σε ομάδες «μετα-δεδομένων», με τη χρήση της προσέγγισης του MSH, ο οποίος ψάχνει για τα μέγιστα στο νέο χώρο κατανομής αυτών των μετα-δεδομένων.
Σε ένα τρίτο στάδιο ανάπτυξης, εξετάζουμε την ικανότητα γενίκευσης της ομαδοποίησης k-means για την οργάνωση των μεγάλων συνόλων δεδομένων. Στοχεύοντας στην επίλυση του παραπάνω προβλήματος, εκμεταλλευόμαστε την στρατηγική της επαναληπτικής αναδιάρθρωσης (bootstrapping) δεδομένων χωρίς αντικατάσταση. Πιο συγκεκριμένα, με τη δημιουργία πολλαπλών συνόλων δεδομένων μικρού μεγέθους προσπαθούμε να καλύψουμε το σύνολο του χώρου κατανομής, χαρακτηρίζοντας τις δομικές ιδιότητες των δεδομένων μέσω των πολλαπλών κλάσεων που δημιουργούνται. Κάθε bootstrap στάδιο εκμεταλλεύεται τη διαδικασία σταθεροποίησης του αλγορίθμου k-means. Τα πολλά παραγόμενα κέντρα οργανώνονται σε κλάσεις μέσω της προσέγγισης του MSH.
Τέλος, σε συνδυασμό με τις προηγούμενες προσεγγίσεις ανα-δειγματοληψίας και αναδιάρθρωσης, εξετάζουμε την χρήση του κατάλληλου μέτρου απόστασης με στόχο την αντιμετώπιση και τη διερεύνηση του τρίτου μεγάλου προβλήματος της ομαδοποίησης, την διαχωρισημότητα των τελικών κλάσεων. Στην εργασία αυτή χρησιμοποιούνται στα δεδομένα χρονικής απόκρισης σε φασματική ακτινοβολία ιστών του τραχήλου της μήτρας. Όπως στα περισσότερα δεδομένα χρονοσειρών (time-series), οι καμπύλες των δεδομένων χαρακτηρίζονται από το μέγεθος κα το σχήμα αυτών. Η προτεινόμενη μετρική στοχεύει στο να ενσωματώσει και τις δυο αυτές πτυχές των δεδομένων σε μια ενιαία μορφή, η οποία μπορεί να προσαρμοστεί στο συγκεκριμένο πεδίο εφαρμογής.
Abstract
Data mining is an interdisciplinary subfield of computer science. It forms the computational process of discovering patterns in large data sets involving methods at the intersection of artificial intelligence, machine learning, statistics and data systems. Machine learning goes often in parallel with data mining, with the first being a supervised scheme whereas the latter focuses more on exploratory data analysis and is known as unsupervised learning. Clustering constitutes an unsupervised learning approach aiming to organize the available data into compact classes according to some notion of similarity. The contribution of clustering in medicine and biology is highly significant.
In this sense, this Master’s thesis examines three fundamental aspects of clustering, namely stability, generalizability and separability in order to discover and interpret the appropriate information from the processed data and make clustering attractive for the effective organization of large datasets.
First, (in association with stability problems), we propose a novel algorithmic approach for extracting adequate information from the input dataset and self-organizing data expanding clustering with resampling. This approach aims to derive stable and representative class centers through permutations in the initialization process implemented via the concept of data resampling. Thus, using data resampling with replacement, we produce multiple partitions from k-means based on multiple reruns of the same population. In our approach, the large number of class centroids is then reorganized into tight groups through the mean-shift approach, which rigorously searches for maxima into this new distribution space of meta-data (class centroids).
Then, by further exploring clustering stability problems, we attempt to refine and improve the clustering result by sequentially updating (instead of replacing) centers on the basis of their present and previous positions. Based on this updating strategy, we can exploit both prior expert knowledge and posterior data information from the statistical distribution of the examined population. In this part, we examine the stability problem of k-means, by proposing a novel algorithmic scheme for self-organizing data, adopting a recursive-mode k-means clustering approach.
Thirdly, we examine issues of k-means clustering association with its generalization ability in organizing big datasets. For this purpose, we exploit a data bootstrapping strategy without replacement. With the generation of multiple datasets of rather small size, we attempt to cover the entire data distribution space and capture its structural properties within the multiple classes generated. Each bootstrap stage exploits the stabilization process of the k-means algorithm. Finally, all class centroids generated from the bootstrap process are considered as (meta-data) samples of higher abstraction, which are organized into classes via the mean-shift approach, similar to the stabilization process.
In association with data re-sampling strategies, we also consider the appropriate use of distance metrics addressing another major problem of data exploratory schemes. We apply our algorithmic developments on data expressing the temporal course of tissue reflection under a specific wavelength. The process of aceto-whitening is of paramount importance in cervical cancer diagnosis and we examine clustering methodologies for extracting, processing and interpreting the relevant information from the available data. As in most time-series formulations, the response curves considered are characterized by both overall amplitude (or power) characteristics and local shape formations. The proposed metric attempts to capture both of these aspects into a single configuration, which can be parametrically adjusted to the particular application domain.
Overall, the test results indicate the importance of data resampling (and bootstrapping) in the appropriate partitioning of large datasets and the efficient operation of data mining (and clustering) schemes.
Τόπος: Λ - Κτίριο Επιστημών/ΗΜΜΥ, 137Π-39,-38
Έναρξη: 19/12/2016 14:00
Λήξη: 19/12/2016 15:00
