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

Abstract

Στην επιστήμη των μαθηματικών οι γράφοι είναι ένας τρόπος αναπαράστασης ενός δικτύου, μιας συλλογής στοιχείων που είναι συνδεδεμένα μεταξύ τους. Οι γράφοι δομούνται από κόμβους οι οποίοι αντιπροσωπεύουν τα δεδομένα και ακμές οι οποίες χαρακτηρίζουν τις σχέσεις μεταξύ των κόμβων. Οι γράφοι οργανώνονται σε συστάδες, δηλαδή ομάδες κόμβων με περισσότερα κοινά χαρακτηριστικά εντός της ίδιας συστάδας και λιγότερο κοινά χαρακτηριστικά μεταξύ διαφορετικών συστάδων. Σε αυτή την διπλωματική εργασία στο περιβάλλον της python θα μελετηθούν τα αποτελέσματα αλγορίθμων σε σύνολα δεδομένων γράφων τα οποία θα αξιολογηθούν από δείκτες αξιολόγησης οι οποίοι έχουν προταθεί από σχετικές μελέτες. Πιο αναλυτικά θα χρησιμοποιηθούν τρία σύνολα δεδομένων γράφων και θα τμηματοποιηθούν με την χρήση δύο διαδεδομένων αλγορίθμων συσταδοποίησης, Spectral και Louvain. Κάθε αλγόριθμος θα δώσει αποτελέσματα για διαφορετικό αριθμό συστάδων, κάθε αποτέλεσμα θα αξιολογηθεί με την χρήση δύο γνωστών δεικτών, οι οποίοι είναι ο modularity και ο conductance. Ο δείκτης modularity αξιολογεί την πυκνότητα των εσωτερικών συνδέσεων της συστάδας σε σχέση με τις εξωτερικές συνδέσεις με άλλες συστάδες. Ο δείκτης Conductance μιας τομής (conductance of a cut) συγκρίνει το μέγεθος μιας τομής, δηλαδή τον αριθμό των κομμένων άκρων και το βάρος (weight) των ακμών σε οποιονδήποτε από τους δύο υπογράφους που δημιουργούνται από την τομή. Επίσης θα χρησιμοποιηθούν τρείς δείκτες αξιολόγησης οι οποίοι έχουν αναπτυχθεί και προταθεί σε μελέτες σχετικής μελέτης. Ο δείκτης Q-graph χρησιμοποιεί το degeneracy και το density τα οποία αφορούν στην πυκνότητα των κόμβων και των ακμών, για να αξιολογήσει την συνδεσιμότητα μεταξύ των γράφων εντός και εκτός της συστάδας. Ο δείκτης CDS που χρησιμοποιείται επίσης για αξιολόγηση λαμβάνει υπόψη του την πυκνότητα του γράφου και το cohesion το οποίο αξιολογεί το πόσο κοντά είναι οι κόμβοι σε ένα δίκτυο και κατά πόσο μπορούν να διαχωριστούν από άλλους. Ένας ακόμα δείκτης που υπολογίζεται είναι ο GS* ο οποίος βασίζεται στον silhouette index και αξιολογεί την ποιότητα της συσταδοποίησης με βάση την απόσταση των κόμβων. Οπτικοποιώντας τις συσταδοποιήσεις ενός πολύ γνωστού μικρού συνόλου δεδομένων και θα γίνει προσπάθεια ερμηνείας των αποτελεσμάτων των δεικτών αξιολόγησης και θα παρατηρηθεί πως η δομή των συστάδων επηρεάζει τα αποτελέσματα του. Οι δείκτες αξιολόγησης είναι πολύ σημαντική για την επικύρωση των αποτελεσμάτων, παρόλα αυτά δεν εντοπίζεται ένας ο οποίος μπορεί να είναι αξιόπιστος υπό όλες τις συνθήκες.