Γενετικοί αλγόριθμοι στη βελτιστοποίηση γραφημάτων ομοιότητας, για προβλήματα ομαδοποίησης δεδομένων.
Creators: name: Χρυσούλη, Χριστίνα Εμμανουήλ
Publisher: name: Aristotle University of Thessaloniki
Year: 2013
Subjects: Γενετικοί αλγόριθμοι
Γραφήματα ομοιότητας
Ομαδοποίηση
Genetic algorithms
Similarity graphs
Clustering

description: Στην παρούσα εργασία θα ασχοληθούμε με τους γενετικούς αλγορίθμους και την επίδρασή τους σε πίνακες ομοιοτήτων. Κύριος στόχος της εργασίας αυτής είναι η ανάπτυξη μιας νέας μεθόδου, που βασίζεται στους γενετικούς αλγορίθμους, γενικής φύσης. Στην παρούσα εργασία, επικεντρωνόμαστε στην ομαδοποίηση, παρ' όλα αυτά, ο προτεινόμενος αλγόριθμος μπορεί να χρησιμοποιηθεί σε διάφορα άλλα προβλήματα που μπορούν να μοντελοποιηθούν ως γραφήματα, όπως για παράδειγμα για μείωση διάστασης (dimensionality reduction) και προβλήματα ταξινόμησης (classification problems). Πιο συγκεκριμένα, προτείνεται ένας γενετικός αλγόριθμος για τη βελτιστοποίηση της δομής ενός γραφήματος ομοιοτήτων, για την επίτευξη του οποίου χρησιμοποιούνται συναρτήσεις καταλληλότητας (fitness function). Η προτεινόμενη μέθοδος χρησιμοποιεί ως αρχικό πληθυσμό γραφήματα $k$-κοντινότερων γειτόνων, κάποιες παραλλαγές των πινάκων αυτών, όπως επίσης και κάποια εντελώς τυχαία γραφήματα. Τα γραφήματα αυτά έχουν μετασχηματιστεί κατάλληλα έτσι ώστε να αποτελέσουν τα χρωμοσώματα στον γενετικό αλγόριθμο. Διάφορες τεχνικές εξετάστηκαν για τη δημιουργία του αρχικού πληθυσμού, καθώς παρατηρήθηκε πως παίζει σημαντικό ρόλο στην απόδοση του αλγορίθμου. Ο αλγόριθμος αποτελείται από τα βασικά βήματα ενός γενετικού αλγορίθμου: επιλογή (selection), διασταύρωση (crossover), μετάλλαξη (mutation) και ελιτισμό (elitism). Πειράματα σε διάφορα πολυδιάστατα σύνολα δεδομένων διεξήχθησαν, προκειμένου να αξιολογηθεί η απόδοση του προτεινόμενου αλγορίθμου, με τη χρήση τόσο εσωτερικών (internal) όσο και εξωτερικών (external) κριτηρίων ομαδοποίησης, ως μέθοδοι αξιολόγησης, οι οποίες έδωσαν ενθαρρυντικά αποτελέσματα. Στα επόμενα κεφάλαια παρουσιάζεται τόσο το θεωρητικό υπόβαθρο για την καλύτερη κατανόηση του προβλήματος, όσο και ο αλγόριθμος που αναπτύχθηκε. Στο τελευταίο κεφάλαιο παρατίθενται τα αποτελέσματα του αλγορίθμου και τα συμπεράσματα που προέκυψαν.
description: In this thesis we deal with evolutionary algorithms and their impact on similarity matrices. The main objective of this work is to develop a new, general, method based on genetic algorithms. In this thesis, we focus on clustering, nevertheless, the proposed algorithm may be used in various other problems, that can be modeled by graphs, such as dimensionality reduction and classification problems. More specifically, an evolutionary algorithm is proposed for optimising the structure of a similarity graph, by using a fitness function, also called objective function, in order to achieve better clustering results. The proposed method makes use of nearest neighbour graphs, variants of these graphs and some arbitrary ones, in order to form the initial population. These graphs are transformed in such a way so as to play the role of chromosomes in the evolutionary algorithm. Various techniques have been examined for the creation of the initial population, since it was observed that it plays an important role to the algorithm's performance. The algorithm consists of the basic steps of an evolutionary algorithm: selection, crossover, mutation and elitism. Experiments on various multidimensional datasets were conducted, in order to evaluate the performance of the proposed algorithm, by using both internal and external clustering criteria as evaluation methods, which provided encouraging results. In the next few chapters we present both the theoretical background needed for a better understanding of the problem, and also the algorithm that it was developed in this thesis. In the last chapters we present the results of the algorithm and the conclusions drawn.