Συλλογές
Τίτλος Τυχαίοι περίπατοι σε γράφους και φασματική ομαδοποίηση
Εναλλακτικός τίτλος Random walks on graphs and spectral clustering
Δημιουργός Κορδώνης, Σπυρίδων
Συντελεστής Γιαννακόπουλος, Αθανάσιος
Οικονομικό Πανεπιστήμιο Αθηνών, Τμήμα Στατιστικής
Τύπος Text
Φυσική περιγραφή 147 σ.
Γλώσσα el
Περίληψη Στα πρώτα κεφάλαια της παρούσας διατριβής παρουσιάζουμε το υποκείμενο θεωρητικό υπόβαθρο των τυχαίων περίπατων σε γράφους και αντίστοιχα της φασματικής ομαδοποίησης. Στη συνέχεια προσεγγίζουμε τον τυχαίο περίπατο σε έναν γράφο από τη σκοπιά των διακριτών αλυσίδων Markov. Ακολούθως κάνουμε μια διεξοδική ανάλυση της φασματικής ομαδοποίησης και των επιμέρους της σταδίων. Εξετάζουμε με ποιο τρόπο οι αλγόριθμοι της φασματικής ομαδοποίησης προσεγγίζουν τα κριτήρια αποκοπής γράφου RatioCut και NCut.Στη συνέχεια εκπληρώνοντας τον πρώτο στόχο της παρούσας διατριβής κάνουμε τη σύνδεση της φασματικής ομαδοποίησης με τον τυχαίο περίπατο και δείχνουμε υπό ποιες συνθήκες ο τυχαίος περίπατος σε έναν γράφο προσεγγίζει το NCut. Τέλος εξετάζουμε την υπολογιστική πολυπλοκότητα της φασματικής ομαδοποίησης και κάνουμε κάποιες γενικές παρατηρήσεις σε σχέση με τα επιμέρους στάδια της. Στο τελευταίο κεφάλαιο εκπληρώνουμε και τον δεύτερο στόχο της παρούσας διατριβής αφού παρουσιάζουμε τα πειραματικά αποτελέσματα από την εφαρμογή των τεχνικών της φασματικής ομαδοποίησης και τη σύγκριση τους με τον αλγόριθμο k-μέσων σε δύο πραγματικά και τέσσερα τεχνητά σύνολα δεδομένων.
Λέξη κλειδί Φασματική ομαδοποίηση
Τυχαίοι περίπατοι
Αλυσίδες Markov
Γράφοι
Ημερομηνία έκδοσης 21-04-2017
Άδεια χρήσης https://creativecommons.org/licenses/by/4.0/