Τεχνικές ομαδοποίησης και ταξινόμησης με εφαρμογές στην ανθρωποκεντρική ανάλυση εικόνων και εικονοσειρών
Creators: name: Τσάπανος, Νικόλαος Γ.
Publisher: name: Aristotle University of Thessaloniki
Year: 2015
Subjects: Ταξινόμηση δεδομένων
Ομαδοποίηση δεδομένων
Ταυτοποίηση σχημάτων
Κατανεμημένη επεξεργασία
Data classification
Data clustering
Shape matching
Distributed processing

description: Σε αυτή τη διδακτορική διατριβή, θα παρουσιάσουμε τα αποτελέσματα της έρευνας που διεξήχθει στις περιοχές της ομαδοποίησης και της ταξινόμησης δεδομένων με εφαρμογές στην ανθρωποκεντρική ανάλυση εικόνων και εικονοσειρών. Η κύρια συνεισφορά μας στο πεδίο της ταξινόμησης σχετίζεται με την εισαγωγή μιας δομής δεδομένων αναζήτησης σχημάτων βασισμένη στα δυαδικά δένδρα για τη γρήγορη ταυτοποίηση σχημάτων. Σύμφωνα τις ιδιότητες ενός ισορροπημένου δυαδικού δένδρου, μπορούμε να εισάγουμε, να αναζητούμε και να διαγράφουμε σχήματα σε λογαριθμικό χρόνο. Σε κάθε κόμβο του δένδρου ένας ασθενής ταξινομητής αποφασίζει σε ποιο μονοπάτι θα κατευθύνει την αναζήτηση. Στην αρχική του μορφή, το δένδρο κατασκευάζεται αυξητικά. Ξεκινώντας από ένα άδειο δένδρο, η δομή συμπληρώνεται εισάγοντας τα σχήματα στο δένδρο. Οι ταξινομητές σε κάθε κόμβο εκπαιδεύονται με έναν απλό και γρήγορο αλγόριθμο εκπαίδευσης.Η μετεξέλιξη αυτών των δένδρων εκμεταλλεύεται ολόκληρο το σύνολο εκπαίδευσης, σκοπεύοντας στη βελτίωση της ταχύτητας και της επίδοσης της προτεινόμενης δομής. Η κατασκευή του δένδρου και η εκπαίδευση των ταξινομητών των κόμβων πραγματοποιείται με πιο εκλεπτισμένους αλγόριθμους. Ο αλγόριθμος εκπαίδευσης των ταξινομητών μεγιστοποιεί την εκ των υστέρων πιθανότητα ένα σχήμα εισόδου να κατευθυνθεί στο σωστό υποδένδρο με βάση τα σχήματα που βρίσκονται στο κάθε υποδένδρο. Ο αλγόριθμος κατασκευής του δένδρου οργανώνει τα σχήματα με τέτοιον τρόπο, ώστε η εκπαίδευση κάθε ταξινομητή να είναι όσο πιο εύκολη γίνεται, ενώ παράλληλα το δένδρο να παραμένει ισορροπημένο.Στη συνέχεια θα παρουσιάσουμε τις συνεισφορές μας στο πεδίο της ομαδοποίησης δεδομένων με χρήση πινάκων ομοιότητας. Η πρώτη και σημαντικότερη συνεισφορά μας σε αυτόν τον τομέα αφορά την περικοπή του πίνακα πυρήνων του αλγόριθμου των κ-μέσων με χρήση πυρήνα. Ο προτεινόμενος αλγόριθμος περικοπής προσπαθεί να εκτιμήσει τον πληθάριθμο της ομάδας στην οποία ανήκει κάθε δείγμα και περικόπτει την αντίστοιχη γραμμή με βάση αυτήν την εκτίμηση. Αυτό έχει ως αποτέλεσμα τη συρρίκνωση του πίνακα πυρήνων και τη βελτίωση των επιδόσεων του αλγόριθμου των κ-μέσων με χρήση πυρήνα. Περιγράφεται, επίσης, μια κατανεμημένη υλοποίηση του προτεινόμενου αλγόριθμου. Ακόμα, δείχνουμε πως ο υπολογισμός του πίνακα πυρήνων μπορεί να πραγματοποιηθεί πολύ γρήγορα σε σύγχρονους επεξεργαστές και χρησιμοποιώντας κατάλληλο λογισμικό. Τέλος, παρουσιάζουμε μια στοχαστική μέθοδο ομαδοποίησης γραφημάτων βασισμένη στον Διακριτό Μετασχηματισμό Συνημιτόνου.
description: In this thesis, we will present the results of the research conducted in the fields of data clustering and classification with applications in the anthropocentric analysis of images and video. Our main contribution in the field of classification involves the introduction of a data structure based on binary search trees for the fast matching of shapes. According to the properties of a balanced binary search tree, we can insert, search and delete shapes in logarithmic time. In each node of the tree a weak classifier decides which search path it will direct the search to. In its initial form, the tree is constructed incrementally. Starting from an empty tree, the data structure is filled in by inserting shapes in the tree. The classifiers in each node are trained with a simple and fast training algorithm. The more advanced form of these trees takes advantage of the entire training set, aiming to improve the speed and performance of the proposed data structure. The construction of the tree and the training of the nodes are performed by more sophisticated algorithms. The classifier training algorithm maximizes the a posteriori probability that an input shape will be directed to the correct subtree based on the template shapes that are stored in each subtree. The tree construction algorithm organizes the templates in such a manner, that the training of every classifier is as easy as possible, while still maintaining the balance of the tree.Subsequently, we will present our contributions to the field of data clustering through the use of similarity matrices. Our first and most significant contribution in this field concerns the trimming of the kernel matrix used by the kernel k-means algorithm. The proposed trimming algorithm attempts to estimate the cardinality of the cluster which each sample belongs to and trims the corresponding kernel matrix line based on this estimation. This results in the reduction of the kernel matrix size and the improvement of the kernel k-means algorithm. Additionally, we describe a distributed implementation of the proposed algorithm. Furthermore, we show how the computation of kernel matrices can be performed very fast on modern processors and using the proper software. Finally, we present a stochastic method for graph clustering based on the Discreet Cosine Transform.