Γραφο-θεωρητικές μέθοδοι συσταδοποίησης και ο αλγόριθμος Jarvis-Patrick σε βάσεις δεδομένων Oracle

Abstract

Συσταδοποίηση ή ομαδοποίηση σε βάσεις δεδομένων είναι η τεχνική εξόρυξης γνώσης από δεδομένα (data mining) που οργανώνονται σε συστάδες (ομάδες ή κλάσεις ή συγκροτήματα) για περαιτέρω κατάταξη. Ενώ πολλοί αλγόριθμοι που βασίζονται σε αποστάσεις όπως οι DBSCAN και CURE χρησιμοποιήθηκαν για την επίλυση προβλημάτων σε δεδομένα λίγων διαστάσεων, η ύπαρξη πολλών διαστάσεων φέρνει πρόσθετες προκλήσεις που περιέχουν το κύριο πρόβλημα της διαστασιμότητας, καθώς οι συναρτήσεις απόστασης μεταξύ των σημείων που καθορίζουν την ομοιότητά τους, γίνονται σχεδόν ομοιόμορφες δυσκολεύοντας το διαχωρισμό τους σε ομάδες. Οι ιδέες και έννοιες της θεωρίας γράφων διευκολύνουν την περιγραφή των προβλημάτων ανίχνευσης ομάδων δεδομένων μέσω γράφων. Οι κορυφές (κόμβοι) V ενός ζυγισμένου γράφου G αντιστοιχούν σε σημεία δεδομένων στο χώρο των προτύπων και οι ακμές Ε απεικονίζουν τη γειτνίαση μεταξύ ζευγών σημείων. Μία προσέγγιση ομοιότητας βασισμένη σε γράφο κοινών κοντινών γειτόνων όπως προτάθηκε από τους Jarvis-Patrick και μετέπειτα στον αλγόριθμο ROCK, είναι μία προτεινόμενη μέθοδος λύσης και για το παραπάνω πρόβλημα, καθώς επίσης και για την συσταδοποίηση μη-αριθμητικών δεδομένων κατηγοριών. Η ομοιότητα δύο σημείων καθορίζεται όχι σύμφωνα με κάποια απόσταση αλλά με τον αριθμό των κοντινών γειτόνων που μοιράζονται. Έτσι ο αλγόριθμος Jarvis-Patrick εισήγαγε τον γράφο γειτνίασης k-πλησιέστερων κορυφών και τον γράφο κοινών κοντινών γειτόνων (shared nearest neighbour graph). Ο αλγόριθμος Jarvis- Patrick μοιάζει έπειτα ως προς τα αποτελέσματα με την τεχνική της ιεραρχικής συσωρευτικής συσταδοποίησης απλού συνδέσμου και ο ROCK με αυτή του μέσου συνδέσμου. Ο αλγόριθμος Jarvis-Patrick είναι ο πρώτος μη ιεραρχικός αλγόριθμος που εισήγαγε τον γράφο κοινών κοντινών γειτόνων. Ομοίως ο αλγόριθμος ROCK μετασχηματίζει τις αρχικές ομοιότητες μεταξύ δύο αντικειμένων, που υπολογίζονται με συντελεστές Jaccard, σε ομοιότητες που αντανακλούν τον αριθμό των κοινών γειτόνων τους. Οι αλγόριθμοι που ακολούθησαν όπως οι Chameleon, Min-cut, HCS (highly connected subgraphs), CLICK (clustering identification via connectivity kernels), CAST (cluster affinity search technique), AMOEBA, SNN, C2P αποδεικνύουν την δημοφιλία της χρήσης των γράφων γειτνίασης k-πλησιέστερων κορυφών και των γράφων κοινών κοντινών γειτόνων σε παρόμοιες εφαρμογές. Οι δύο τελευταίοι αλγόριθμοι SNN και C2P που είναι και πρόσφατοι εμπεριέχουν στα βήματά τους τον αρχικό αλγόριθμο Jarvis-Patrick, και έπειτα συνεχίζουν ο πρώτος με τον DBSCAN και ο δεύτερος με τον MST.