Ανίχνευση συστάδων με τον αλγόριθμο STING για εφαρμογές spatial data mining από συστήματα χωρικών δεδομένων

Abstract

Το θέμα της παρούσης πτυχιακής εργασίας είναι Ανίχνευση συστάδων με τον αλγόριθμο STING για εφαρμογές spatial data mining από συστήματα χωρικών δεδομένων. Η εξόρυξη χωρικής γνώσης (spatial data mining) από βάσεις χωρικών δεδομένων αφορά εφαρμογές όπως τα Γεωγραφικά Συστήματα πληροφοριών αλλά και τα συστήματα βιοϊατρικής διάγνωσης και επεξεργασίας χωρικών συσχετίσεων ιατρικών εικόνων ή δεδομένων τηλεπισκόπησης, που απαιτούν γνωρίσματα θέσης στο χώρο. Για την αποδοτική εκτέλεση χωρικών ερωτημάτων είναι χρήσιμο τα γειτονικά (χωρικά) αντικείμενα να ομαδοποιούνται σε συστάδες στο δίσκο. Ο γεωγραφικός χώρος μπορεί να διαμεριστεί σε κελιά (cells) βάσει της εγγύτητας, οπότε αυτά τα κελιά αντιστοιχούν σε φυσικές θέσεις – blocks στο δίσκο. Η Συσταδοποίηση (clustering) σε μεγάλες βάσεις δεδομένων είναι η τεχνική εξόρυξης γνώσης από δεδομένα (data mining) από τις ιδιότητες των οποίων θα πρέπει να προσδιοριστούν συστάδες (ομάδες ή συμπλέγματα ή συγκροτήματα ή κλάσεις) για περαιτέρω κατάταξη. Οι συστάδες δεν είναι προκαθορισμένες. Ο αλγόριθμος Statistical Information Grid-based (STING) χρησιμοποιεί μία ιεραρχική τεχνική διαίρεσης των χωρικών περιοχών σε ορθογώνια κελιά παρόμοια με ένα τετραδικό δένδρο. Η βάση χωρικών δεδομένων σαρώνεται μία φορά και για κάθε κελί καθορίζονται στατιστικές παράμετροι (μέση τιμή, διασπορά, μέγιστο, ελάχιστο, τύπος κατανομής). Έτσι μπορούν να απαντηθούν πολλά ερωτήματα εξόρυξης γνώσης από χωρικά δεδομένα, συμπεριλαμβανομένης και της συσταδοποίησης. Μια διάσχιση κατά πλάτος χρησιμοποιείται για την εξέταση του κατασκευασμένου δένδρου και εξετάζονται παιδιά σχετικών κόμβων. Ο υπολογισμός της πιθανότητας ένα κελί να είναι σχετικό με μία ερώτηση βασίζεται στο ποσοστό των αντικειμένων στο κελί που ικανοποιούν τους περιορισμούς της ερώτησης. Στην παρούσα πτυχιακή εργασία μελετήθηκε και ακολούθως υλοποιήθηκε ο αλγόριθμος STING σε περιβάλλον Borland C++ Builder και ένα γνωστό σύστημα βάσης δεδομένων.