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

Abstract

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