Βιβλιοθήκη ΟΠΑ - Ψηφιακό Αποθετήριο

ΠΥΞΙΔΑ Ιδρυματικό Αποθετήριο
και Ψηφιακή Βιβλιοθήκη

Όνομα χρήστη
Κωδικός πρόσβασης

Συλλογές :	Ιδρυματικό Αποθετήριο ΟΠΑ / AUEB Institutional Repository Σχολή Επιστημών και Τεχνολογίας της Πληροφορίας / School of Informatics Τμήμα Στατιστικής / Department of Statistics Μεταπτυχιακές Εργασίες / Postgraduate dissertations

Τίτλος :	Τυχαίοι περίπατοι σε γράφους και φασματική ομαδοποίηση

Εναλλακτικός τίτλος :	Random walks on graphs and spectral clustering

Δημιουργός :	Κορδώνης, Σπυρίδων

Συντελεστής :	Γιαννακόπουλος, Αθανάσιος (Επιβλέπων καθηγητής) Οικονομικό Πανεπιστήμιο Αθηνών, Τμήμα Στατιστικής (Degree granting institution)

Τύπος :	Text

Φυσική περιγραφή :	147 σ.

Γλώσσα :	el

Περίληψη :	Στα πρώτα κεφάλαια της παρούσας διατριβής παρουσιάζουμε το υποκείμενο θεωρητικό υπόβαθρο των τυχαίων περίπατων σε γράφους και αντίστοιχα της φασματικής ομαδοποίησης. Στη συνέχεια προσεγγίζουμε τον τυχαίο περίπατο σε έναν γράφο από τη σκοπιά των διακριτών αλυσίδων Markov. Ακολούθως κάνουμε μια διεξοδική ανάλυση της φασματικής ομαδοποίησης και των επιμέρους της σταδίων. Εξετάζουμε με ποιο τρόπο οι αλγόριθμοι της φασματικής ομαδοποίησης προσεγγίζουν τα κριτήρια αποκοπής γράφου RatioCut και NCut.Στη συνέχεια εκπληρώνοντας τον πρώτο στόχο της παρούσας διατριβής κάνουμε τη σύνδεση της φασματικής ομαδοποίησης με τον τυχαίο περίπατο και δείχνουμε υπό ποιες συνθήκες ο τυχαίος περίπατος σε έναν γράφο προσεγγίζει το NCut. Τέλος εξετάζουμε την υπολογιστική πολυπλοκότητα της φασματικής ομαδοποίησης και κάνουμε κάποιες γενικές παρατηρήσεις σε σχέση με τα επιμέρους στάδια της. Στο τελευταίο κεφάλαιο εκπληρώνουμε και τον δεύτερο στόχο της παρούσας διατριβής αφού παρουσιάζουμε τα πειραματικά αποτελέσματα από την εφαρμογή των τεχνικών της φασματικής ομαδοποίησης και τη σύγκριση τους με τον αλγόριθμο k-μέσων σε δύο πραγματικά και τέσσερα τεχνητά σύνολα δεδομένων.

Περίληψη :

Στα πρώτα κεφάλαια της παρούσας διατριβής παρουσιάζουμε το υποκείμενο θεωρητικό υπόβαθρο των τυχαίων περίπατων σε γράφους και αντίστοιχα της φασματικής ομαδοποίησης. Στη συνέχεια προσεγγίζουμε τον τυχαίο περίπατο σε έναν γράφο από τη σκοπιά των διακριτών αλυσίδων Markov. Ακολούθως κάνουμε μια διεξοδική ανάλυση της φασματικής ομαδοποίησης και των επιμέρους της σταδίων. Εξετάζουμε με ποιο τρόπο οι αλγόριθμοι της φασματικής ομαδοποίησης προσεγγίζουν τα κριτήρια αποκοπής γράφου RatioCut και NCut.Στη συνέχεια εκπληρώνοντας τον πρώτο στόχο της παρούσας διατριβής κάνουμε τη σύνδεση της φασματικής ομαδοποίησης με τον τυχαίο περίπατο και δείχνουμε υπό ποιες συνθήκες ο τυχαίος περίπατος σε έναν γράφο προσεγγίζει το NCut. Τέλος εξετάζουμε την υπολογιστική πολυπλοκότητα της φασματικής ομαδοποίησης και κάνουμε κάποιες γενικές παρατηρήσεις σε σχέση με τα επιμέρους στάδια της. Στο τελευταίο κεφάλαιο εκπληρώνουμε και τον δεύτερο στόχο της παρούσας διατριβής αφού παρουσιάζουμε τα πειραματικά αποτελέσματα από την εφαρμογή των τεχνικών της φασματικής ομαδοποίησης και τη σύγκριση τους με τον αλγόριθμο k-μέσων σε δύο πραγματικά και τέσσερα τεχνητά σύνολα δεδομένων.

Λέξη κλειδί :	Φασματική ομαδοποίηση Τυχαίοι περίπατοι Αλυσίδες Markov Γράφοι

Ημερομηνία έκδοσης :	21-04-2017

Άδεια χρήσης :

Αρχείο: Kordonis_2017.pdf

Τύπος: application/pdf

Είσοδος