PYXIDA Institutional Repository
and Digital Library
 Home
Collections :

Title :Τυχαίοι περίπατοι σε γράφους και φασματική ομαδοποίηση
Alternative Title :Random walks on graphs and spectral clustering
Creator :Κορδώνης, Σπυρίδων
Contributor :Γιαννακόπουλος, Αθανάσιος (Επιβλέπων καθηγητής)
Οικονομικό Πανεπιστήμιο Αθηνών, Τμήμα Στατιστικής (Degree granting institution)
Type :Text
Extent :147 σ.
Language :el
Abstract :Στα πρώτα κεφάλαια της παρούσας διατριβής παρουσιάζουμε το υποκείμενο θεωρητικό υπόβαθρο των τυχαίων περίπατων σε γράφους και αντίστοιχα της φασματικής ομαδοποίησης. Στη συνέχεια προσεγγίζουμε τον τυχαίο περίπατο σε έναν γράφο από τη σκοπιά των διακριτών αλυσίδων Markov. Ακολούθως κάνουμε μια διεξοδική ανάλυση της φασματικής ομαδοποίησης και των επιμέρους της σταδίων. Εξετάζουμε με ποιο τρόπο οι αλγόριθμοι της φασματικής ομαδοποίησης προσεγγίζουν τα κριτήρια αποκοπής γράφου RatioCut και NCut.Στη συνέχεια εκπληρώνοντας τον πρώτο στόχο της παρούσας διατριβής κάνουμε τη σύνδεση της φασματικής ομαδοποίησης με τον τυχαίο περίπατο και δείχνουμε υπό ποιες συνθήκες ο τυχαίος περίπατος σε έναν γράφο προσεγγίζει το NCut. Τέλος εξετάζουμε την υπολογιστική πολυπλοκότητα της φασματικής ομαδοποίησης και κάνουμε κάποιες γενικές παρατηρήσεις σε σχέση με τα επιμέρους στάδια της. Στο τελευταίο κεφάλαιο εκπληρώνουμε και τον δεύτερο στόχο της παρούσας διατριβής αφού παρουσιάζουμε τα πειραματικά αποτελέσματα από την εφαρμογή των τεχνικών της φασματικής ομαδοποίησης και τη σύγκριση τους με τον αλγόριθμο k-μέσων σε δύο πραγματικά και τέσσερα τεχνητά σύνολα δεδομένων.
Subject :Φασματική ομαδοποίηση
Τυχαίοι περίπατοι
Αλυσίδες Markov
Γράφοι
Date Issued :21-04-2017
Licence :

File: Kordonis_2017.pdf

Type: application/pdf
Copyright © 2013 Library AUEB. All rights reserved.