Μελέτη και ανάπτυξη προσεγγίσεων αξιολόγησης αποτελεσμάτων συσταδοποίησης σε γράφους

Abstract

Η παρούσα διπλωματική εργασία έχει ως αντικείμενο μία μελέτη στο πρόβλημα της αξιολόγησης των αποτελεσμάτων τμηματοποίησης ενός γράφου. Το πρόβλημα της αξιολόγησης των αποτελεσμάτων συσταδοποίησης έχει μελετηθεί ευρέως και υπάρχει ένας μεγάλος αριθμός από δείκτες αξιολόγησης των αποτελεσμάτων συσταδοποίησης. Τα τελευταία χρόνια έχει γίνει αρκετή δουλειά σε τεχνικές συσταδοποίησης (clustering) γράφων μέσω web applications, social networks, βιοΐατρικά δεδομένα.

Ο στόχος της παρούσας εργασίας είναι η μελέτη επεκτάσεων προσεγγίσεων αξιολόγησης αποτελεσμάτων συσταδοποίησης σε γράφων (graph clustering techniques) ώστε να δούμε αυτές οι προσεγγίσεις σε τι φάση βρίσκονται, ποιες μετρικές λαμβάνουν υπόψη και ποιες από αυτές μπορούν να δώσουν ασφαλή συμπεράσματα.

Η παρούσα εργασία είναι δομημένη σε τέσσερα μέλη, στο πρώτο θα περιγράψουμε τεχνικές που αφορούν τη συσταδοποίηση δεδομένων σε μορφή γράφων τις οποίες θα τις σχολιάσουμε. Στο δεύτερο μέρος θα περιγράψουμε το πρόβλημα της αξιολόγησης αποτελεσμάτων συσταδοποίησης σε γράφους, θα μελετήσουμε προσεγγίσεις που αξιολογούν την ποιότητα αυτών των αποτελεσμάτων και θα τις σχολιάσουμε. Στο τρίτος μέρος θα γίνει η παρουσίαση μιας πειραματικής προσέγγισης των όσων περιγράφονται στα δύο πρώτα μέρη. Εκεί θα επιλέξουμε τέσσερα datasets διαφορετικού μεγέθους το καθένα, τα οποία θα έχουν μορφή γράφων. Θα τα υποβάλλουμε σε δύο διαφορετικές τεχνικές συσταδοποίησης δεδομένων σε γράφους και θα αξιολογήσουμε τα αποτελέσματα βάση τριών δεικτών. Τέλος στο τέταρτο και τελευταίο μέρος θα σχολιάσουμε τα αποτελέσματα που πήραμε από τη πειραματική μελέτη μας και θα προβούμε σε κάποια συμπεράσματα.