Επιτάχυνση του αλγόριθμου k-means με τη μέθοδο του Moore για εφαρμογές συσταδοποίησης μεγάλων βάσεων δεδομένων

Abstract

Η αυτόματη ανίχνευση ομάδων είναι μία τεχνική data mining που ψάχνει για ομάδες στοιχείων που είναι παρόμοια μεταξύ τους. Έτσι παρόμοια στοιχεία θα συμπεριφέρονται με παρόμοιους τρόπους. Για παράδειγμα συγκεκριμένες κατηγορίες πελατών ή συμπεριφορές. Η ανίχνευση ομάδων ανήκει στην κατηγορία της Συσταδοποίησης (clustering). Ο γνωστός αλγόριθμος συσταδοποίησης K-means είναι βασικός σε εργασίες data mining, αλλά είναι αργός σε μεγάλες βάσεις δεδομένων. Ενώ συνήθως προτείνεται η δειγματοληψία δεδομένων από τη βάση άλλες εργασίες προτείνουν την επιτάχυνση του αλγορίθμου άμεσα, μέσω της μεθόδου anchor hierarchy και μετρικών δομών δεδομένων. Η μέθοδος του Moore παράγει γρήγορα μία δομή για εντοπισμό δεδομένων, που εμπλουτίζεται με πρόσθετες στατιστικές πληροφορίες, και έχει την καλύτερη προσαρμογή στην κατανομή αυτών. Η μέθοδος του Moore, χρησιμοποιεί το συνδυασμό μίας γρήγορης ευρετικής μεθόδου της anchors hierarchy (farthest-points 2-approximation από Operation Research), και την μέθοδο συγχώνευσης bottom up του Omohundro, και αποφεύγει την αναδρομική κατασκευή δενδρικών δομών. Αυτές οι δομές εμπλουτίζονται με προ-υπολογιζόμενες στατιστικές πληροφορίες (κέντρα, αριθμός σημείων κλπ) και επιτρέπουν την επιτάχυνση αλγορίθμων μάθησης. Η anchors hierarchy βρίσκει sqrt(Ν) ομάδες-σφαίρες για Ν δεδομένα και η improved bottom up, συγχωνεύει τις σφαίρες σε μία. Μετά εφαρμόζεται πάλι αναδρομικά σε κάθε μία από τις σφαίρες i που έχουν Ni δεδομένα για να βρει sqrt(Νi) ομάδες και συνεχίζει ομοίως. Παράγει έτσι από αυτές τις ομάδες μία σωστά ισορροπημένη δομή όμοια με τα Ball Trees (Omohundro) που είναι δυαδικά δέντρα που αποσυνθέτουν ιεραρχικά το χώρο σε περιοχές υπερσφαιρών, αλλά με μία μέθοδο κατασκευής που δεν είναι ούτε top-down, ούτε bottom-up, αλλά αντίθετα είναι middle-out. Συνδυάζει έτσι την ταχύτητα της μεθόδου top-down και την καλύτερη προσαρμογή στην άγνωστη στατιστική κατανομή των δεδομένων με τη μέθοδο bottom-up. Αυτή η middle-out κατασκευή εξασφαλίζει μία γραμμική πολυπλοκότητα σε όλη τη διαδικασία. Όπως αναφέραμε και στην αρχή ο κάθε αλγόριθμος έχει και τα μειονεκτήματα του. Στην προκειμένη περίπτωση ο αλγόριθμος k-means υστερεί σε βάσης δεδομένων με μεγάλο όγκο στοιχείων. Παρακάτω στις επόμενες ενότητες θα αναλύσουμε πλήρως το θέμα κάνοντας μία επεξήγηση για να γίνει εύκολη η κατανόηση του κώδικα και τη χρησιμοποιούμε για να καταφέρουμε να επιταχύνουμε τον αλγόριθμο k-means με την μέθοδο του Moore. Το όφελος θα προκύψει από την εμβάθυνση στην υλοποίηση δομών δεδομένων και τον προγραμματισμό τους καθώς και τη μελέτη των εφαρμογών τους. Στην συνέχεια αναφερόμαστε σε μετρικά δεδομένα δομημένα σε πολλές διαστάσεις ή σε μη Ευκλείδειες αποστάσεις που μας επιτρέπουν την επιτάχυνση των αλγορίθμων εκμάθησης χρησιμοποιώντας στατιστικά στοιχεία που είναι αποθηκευμένα σε μεταβλητές. Πάνω σε αυτά τα στατιστικά βασίζεται και όλη η λογική των αλγορίθμων εκμάθησης, όπου δίνοντας στον κώδικα έτοιμα στοιχεία που έχουν είδη αναλυθεί μετά από επεξεργασία, δίνουμε στην εφαρμογή μας έτοιμη και μασημένη τροφή για να μας δώσει το αποτέλεσμα που ζητάμε. Πρόσφατα έχει δειχθεί ότι για λιγότερες από δέκα διαστάσεις, προσθέτοντας kd-trees με πρόσθετα στατιστικά στοιχεία σε πίνακες, μας παρέχουν ικανοποιητική επιτάχυνση για ένα μεγάλο εύρος από τεχνικές στατιστικής εκμάθησης όπως η οπισθοδρόμηση πυρήνα (kernel regression), τοπικά βαριά οπισθοδρόμηση (locally weighted regression), k-means συσταδοποίηση (clustering), αναμειγμένη μοντελοποίηση και Bayes Net Learning. Παρακάτω θα δούμε τον ορισμό του Farthest Poit (Ιεραρχίας των Αγκυρών - Anchors hierarchy)-- μια γρήγορη δόμηση για ένα σύνολο δεδομένων μόνο σε τριγωνική-άνιση-αυστηρά μετρική απόσταση. Θα δούμε πως αυτό, μέσα σε δικά του πλαίσια, μας δίνει γρήγορη και αποτελεσματική συσταδοποίηση (clustering) δεδομένων. Αλλά το πιο σημαντικό που θα δούμε είναι πως αυτό μας προσφέρει μία εξισορροπημένη δόμηση όμοια με ένα Ball-Tree (Omohundro, 1991) ή ένα είδος μετρικού δέντρου (Uhlmann,1991;Ciaccia, Patella, & Zezula, 1997) με τέτοιο τρόπο που δεν είναι ούτε "top-down" ούτε "bottom-up" αλλά αντιθέτως "middle-out". Μετά θα δούμε πως αυτή η δόμηση, σχεδιασμένη με αποθηκευμένα στατιστικά στοιχεία, μας επιτρέπει την επιτάχυνση ενός μεγάλου εύρους αλγορίθμων με στατιστικές εκμαθήσεις, ακόμα και σε χιλιάδες διαστάσεις. Αρχικά θα ξεκινήσουμε με αναλύοντας θεωρητικά κομμάτια και στην προκειμένη περίπτωση το τι είναι η Εξόρυξη Δεδομένων (data mining).