Πώς να τοποθετήσετε έναν ελέφαντα σε ένα υπολογιστικό φύλλο

Πίνακας συνδέσμων

Περίληψη και 1 Εισαγωγή

2 Προκαταρκτικά και Σχετικές Εργασίες

2.1 Σχετικά με τις στρατηγικές δειγματοληψίας

2.2 Άλλες στρατηγικές Coreset

2.3 Coresets για εφαρμογές βάσεων δεδομένων

2.4 Ενσωματώσεις τετραδέντρων

3 Fast-Coresets

4 Μείωση του αντίκτυπου της διάδοσης

4.1 Υπολογισμός ενός ακατέργαστου άνω ορίου

4.2 Από το κατά προσέγγιση διάλυμα στη μειωμένη εξάπλωση

5 Γρήγορη συμπίεση στην πράξη

5.1 Στόχος και Πεδίο της Εμπειρικής Ανάλυσης

5.2 Πειραματική ρύθμιση

5.3 Αξιολόγηση Στρατηγικών Δειγματοληψίας

5.4 Ρύθμιση ροής και 5.5 Takeaways

6 Συμπέρασμα

7 Ευχαριστίες

8 Αποδείξεις, ψευδοκώδικας και επεκτάσεις και 8.1 Απόδειξη συμπερασμάτων 3.2

8.2 Αναγωγή του k-means σε k-median

8.3 Εκτίμηση του βέλτιστου κόστους σε ένα δέντρο

8.4 Επεκτάσεις στον Αλγόριθμο 1

Αναφορές

Περίληψη

Μελετάμε τα θεωρητικά και πρακτικά όρια χρόνου εκτέλεσης των k-means και k-median ομαδοποίησης σε μεγάλα σύνολα δεδομένων. Δεδομένου ότι ουσιαστικά όλες οι μέθοδοι ομαδοποίησης είναι πιο αργές από τον χρόνο που απαιτείται για την ανάγνωση του συνόλου δεδομένων, η ταχύτερη προσέγγιση είναι η γρήγορη συμπίεση των δεδομένων και η εκτέλεση της ομαδοποίησης στη συμπιεσμένη αναπαράσταση. Δυστυχώς, δεν υπάρχει καθολική καλύτερη επιλογή για τη συμπίεση του αριθμού των σημείων – ενώ η τυχαία δειγματοληψία εκτελείται σε υπογραμμικό χρόνο και οι πυρήνες παρέχουν θεωρητικές εγγυήσεις, η πρώτη δεν επιβάλλει την ακρίβεια ενώ η δεύτερη είναι πολύ αργή καθώς ο αριθμός των σημείων και των συστάδων αυξάνεται. Πράγματι, έχει υποτεθεί ότι οποιαδήποτε κατασκευή βασισμένη σε ευαισθησία απαιτεί υπερ-γραμμικό χρόνο στο μέγεθος του συνόλου δεδομένων.

Εξετάζουμε αυτή τη σχέση δείχνοντας πρώτα ότι υπάρχει ένας αλγόριθμος που λαμβάνει πυρήνες μέσω δειγματοληψίας ευαισθησίας σε αποτελεσματικά γραμμικό χρόνο – εντός των λογαριασμών του χρόνου που απαιτείται για την ανάγνωση των δεδομένων. Οποιαδήποτε προσέγγιση που βελτιώνει σημαντικά αυτό πρέπει στη συνέχεια να καταφύγει σε πρακτικές ευρετικές μεθόδους, οδηγώντας μας να εξετάσουμε το φάσμα των στρατηγικών δειγματοληψίας τόσο σε πραγματικά όσο και σε τεχνητά σύνολα δεδομένων στις ρυθμίσεις στατικής και ροής. Μέσω αυτού, δείχνουμε τις συνθήκες υπό τις οποίες οι πυρήνες είναι απαραίτητες για τη διατήρηση της εγκυρότητας του συμπλέγματος καθώς και τις ρυθμίσεις στις οποίες επαρκούν ταχύτερες, πιο ακατέργαστες στρατηγικές δειγματοληψίας. Ως αποτέλεσμα, παρέχουμε ένα ολοκληρωμένο θεωρητικό και πρακτικό σχέδιο για αποτελεσματική ομαδοποίηση ανεξάρτητα από το μέγεθος των δεδομένων. Ο κώδικάς μας είναι δημόσια διαθέσιμος στην πηγή και έχει σενάρια για την αναδημιουργία των πειραμάτων.

1 Εισαγωγή

Ο σύγχρονος αναλυτής δεδομένων δεν έχει έλλειψη αλγορίθμων ομαδοποίησης για να επιλέξει, αλλά, δεδομένου του διαρκώς αυξανόμενου μεγέθους των σχετικών συνόλων δεδομένων, πολλοί είναι συχνά πολύ αργοί για να είναι πρακτικά χρήσιμοι. Αυτό είναι ιδιαίτερα σημαντικό για αγωγούς μεγάλων δεδομένων, όπου οι αλγόριθμοι ομαδοποίησης χρησιμοποιούνται συνήθως για συμπίεση. Ο στόχος είναι να αντικατασταθεί ένα πολύ μεγάλο σύνολο δεδομένων από ένα μικρότερο, πιο διαχειρίσιμο για εργασίες κατάντη, με την ελπίδα ότι αντιπροσωπεύει καλά την αρχική εισαγωγή. Ο αλγόριθμος του Lloyd [49] εισήχθη ακριβώς για αυτόν τον λόγο και ελαχιστοποιεί το σφάλμα κβαντισμού – το άθροισμα της τετραγωνικής απόστασης από κάθε σημείο εισόδου στον αντιπρόσωπό του στο συμπιεσμένο σύνολο δεδομένων. Αναμφισβήτητα ο πιο δημοφιλής αλγόριθμος ομαδοποίησης, ο Lloyd's εκτελείται για πολλαπλές επαναλήψεις μέχρι τη σύγκλιση με κάθε επανάληψη που απαιτεί χρόνο O(ndk), όπου n είναι ο αριθμός των σημείων, d ο αριθμός των χαρακτηριστικών και k είναι ο αριθμός των συστάδων – ή το μέγεθος της στοχευμένης συμπίεσης. Για τέτοιες εφαρμογές, ο αριθμός των σημείων μπορεί εύκολα να είναι εκατοντάδες εκατομμύρια και, καθώς η ποιότητα της συμπίεσης αυξάνεται με k, οι τυπικοί στόχοι μπορούν να έχουν k σε χιλιάδες [41, 4]. Σε τέτοιες ρυθμίσεις, οποιοσδήποτε αλγόριθμος O(ndk) είναι απαγορευτικά αργός.

Παραδείγματα σαν αυτά έχουν προκαλέσει την άνοδο αλγορίθμων μεγάλων δεδομένων που παρέχουν τόσο θεωρητικές όσο και πρακτικές βελτιώσεις χρόνου εκτέλεσης. Ωστόσο, οι προοπτικές της θεωρητικής ορθότητας και της πρακτικής αποτελεσματικότητας είναι συχνά σε αντίθεση μεταξύ τους. Από τη μία πλευρά, οι θεωρητικές εγγυήσεις παρέχουν τη βεβαιότητα ότι ο αλγόριθμος θα λειτουργήσει ανεξάρτητα από τις άτυχες εισροές που λαμβάνει. Από την άλλη πλευρά, μπορεί να είναι δύσκολο να πείσει κανείς τον εαυτό του να εφαρμόσει τον θεωρητικά βέλτιστο αλγόριθμο όταν υπάρχουν πιο ακατέργαστες μέθοδοι που λειτουργούν πιο γρήγορα και αποδίδουν καλά στην πράξη.

Δεδομένου ότι τα σύνολα δεδομένων μπορεί να είναι μεγάλα ως προς τον αριθμό των σημείων n ή/και τον αριθμό των χαρακτηριστικών d, οι μέθοδοι μεγάλων δεδομένων πρέπει να μετριάζουν τις επιπτώσεις και των δύο. Όσον αφορά τον χώρο χαρακτηριστικών, η ερώτηση ουσιαστικά κλείνει καθώς οι τυχαίες προβολές είναι γρήγορες (εκτελούνται σε ουσιαστικά γραμμικό χρόνο), πρακτικές στην εφαρμογή [50] και παρέχουν αυστηρές εγγυήσεις για το μέγεθος και την ποιότητα της ενσωμάτωσης. Η προοπτική είναι λιγότερο σαφής όταν μειώνεται ο αριθμός των σημείων n και υπάρχουν δύο ξεχωριστά παραδείγματα που το καθένα παρέχει ξεχωριστά πλεονεκτήματα. Από τη μία πλευρά, έχουμε ομοιόμορφη δειγματοληψία, η οποία εκτελείται σε υπογραμμικό χρόνο, αλλά μπορεί να χάσει σημαντικά υποσύνολα των δεδομένων και επομένως μπορεί να εγγυηθεί την ακρίβεια μόνο υπό ορισμένες ισχυρές υποθέσεις για τα δεδομένα [45]. Από την άλλη πλευρά, οι πιο ακριβείς στρατηγικές δειγματοληψίας παρέχουν την ισχυρή εγγύηση βασικού συνόλου, όπου το κόστος οποιασδήποτε λύσης στα συμπιεσμένα δεδομένα είναι εντός ενός συντελεστή ε του κόστους αυτής της λύσης στο αρχικό σύνολο δεδομένων [25].

Οι συνεισφορές μας Μελετάμε και τα δύο παραδείγματα (ομοιόμορφη δειγματοληψία και ισχυροί πυρήνες) σε σχέση με ένα κλασικό πρόβλημα - συμπίεση για τους στόχους k-μέσου και k-μέσου. Ενώ η ομοιόμορφη δειγματοληψία παρέχει τη βέλτιστη ταχύτητα, αλλά δεν εγγυάται την ακρίβεια στη χειρότερη περίπτωση, όλες οι διαθέσιμες κατασκευές πυρήνων έχουν χρόνο λειτουργίας τουλάχιστον Ω˜(nd + nk) όταν αποδίδουν στενά όρια στον ελάχιστο αριθμό δειγμάτων που απαιτούνται για ακριβή συμπίεση.

Είναι εύκολο να δείξουμε ότι κάθε αλγόριθμος που επιτυγχάνει εγγύηση συμπίεσης πρέπει να διαβάζει ολόκληρο το σύνολο δεδομένων[1]. Επομένως, ένα ξεκάθαρο ανοιχτό ερώτημα είναι ποιες εγγυήσεις μπορούν να επιτευχθούν σε γραμμικό ή σχεδόν γραμμικό χρόνο. Πράγματι, οι επί του παρόντος διαθέσιμοι αλγόριθμοι γρήγορης δειγματοληψίας για ομαδοποίηση [6, 5] δεν μπορούν να επιτύχουν ισχυρές εγγυήσεις βασικού συνόλου. Πρόσφατα, ο [31] πρότεινε μια μέθοδο για ισχυρούς πυρήνες που τρέχει σε χρόνο O˜(nd + nk) και υπέθεσε ότι αυτό είναι το βέλτιστο για k-διάμεσο και k-μέσο.

Ενώ αυτό το όριο είναι αποτελεσματικά βέλτιστο για μικρές τιμές του k, υπάρχουν πολλές εφαρμογές όπως η υπολογιστική όραση [34] ή η αλγοριθμική δικαιοσύνη [18] όπου ο αριθμός των συστάδων μπορεί να είναι μεγαλύτερος από τον αριθμό των χαρακτηριστικών κατά πολλές τάξεις μεγέθους. Σε τέτοιες ρυθμίσεις, το ζήτημα των βέλτιστων χρονικά πυρήνων παραμένει ανοιχτό. Δεδομένου ότι το ζήτημα του προσδιορισμού ενός πυρηνικού συνόλου βέλτιστου μεγέθους έχει πρόσφατα κλείσει [25, 28, 44], αυτό είναι αναμφισβήτητα το κύριο ανοιχτό πρόβλημα στην έρευνα βασικών συνόλων για ομαδοποίηση με βάση το κέντρο. Το επιλύουμε αυτό δείχνοντας ότι υπάρχει ένας εύκολος στην εφαρμογή αλγόριθμος που κατασκευάζει πυρήνες σε χρόνο O˜(nd) – μόνο λογαριθμικοί παράγοντες μακριά από το χρόνο που χρειάζεται για την ανάγνωση στο σύνολο δεδομένων.

Ωστόσο, αυτό δεν φωτίζει πλήρως το τοπίο μεταξύ των αλγορίθμων δειγματοληψίας για ομαδοποίηση στην πράξη. Αν και ο αλγόριθμός μας επιτυγχάνει τόσο βέλτιστο χρόνο εκτέλεσης όσο και βέλτιστη συμπίεση, είναι βεβαίως πιθανό άλλες, πιο ωμές μέθοδοι να είναι εξίσου βιώσιμες για όλους τους πρακτικούς σκοπούς. Αυτό το δηλώνουμε επίσημα στην ακόλουθη ερώτηση: Πότε είναι απαραίτητες οι βέλτιστες κ-μέσες και κ-μέσες πυρήνες και ποια είναι η πρακτική αντιστάθμιση μεταξύ της ταχύτητας και της ακρίβειας του πυρήνα;

o απαντήστε σε αυτό, πραγματοποιούμε μια διεξοδική σύγκριση σε όλο το εύρος των αλγορίθμων δειγματοληψίας που είναι ταχύτεροι από την προτεινόμενη μέθοδο. Μέσω αυτού επαληθεύουμε ότι, ενώ αυτές οι ταχύτερες μέθοδοι είναι επαρκώς ακριβείς σε πολλά σύνολα δεδομένων πραγματικού κόσμου, υπάρχουν κατανομές δεδομένων που προκαλούν καταστροφική αποτυχία για καθεμία από αυτές. Πράγματι, αυτές οι περιπτώσεις μπορούν να αποφευχθούν μόνο με μια μέθοδο ισχυρού πυρήνα. Έτσι, ενώ πολλές πρακτικές ρυθμίσεις δεν απαιτούν την πλήρη εγγύηση πυρήνα, δεν μπορεί κανείς να κόψει τις γωνίες εάν θέλει να είναι σίγουρος για τη συμπίεσή τους. Επαληθεύουμε ότι αυτό επεκτείνεται στο παράδειγμα ροής και ισχύει για προσεγγίσεις κατάντη ομαδοποίησης.

Συνοπτικά, οι συνεισφορές μας είναι οι εξής:

• Δείχνουμε ότι μπορεί κανείς να αποκτήσει ισχυρούς πυρήνες για k-μέσο και k-διάμεσο σε χρόνο O˜(nd). Αυτό επιλύει μια εικασία σχετικά με τον απαραίτητο χρόνο εκτέλεσης για τους πυρήνες k-means [31] και είναι θεωρητικά βέλτιστος μέχρι τους log-factors.

• Μέσω μιας περιεκτικής ανάλυσης μεταξύ των συνόλων δεδομένων, των εργασιών και των παραδειγμάτων ροής/μη ροής, επαληθεύουμε ότι υπάρχει μια απαραίτητη αντιστάθμιση μεταξύ ταχύτητας και ακρίβειας μεταξύ των μεθόδων δειγματοληψίας γραμμικού και υπογραμμικού χρόνου. Αυτό δίνει στον επαγγελματία της ομαδοποίησης ένα σχέδιο σχετικά με το πότε πρέπει να χρησιμοποιήσει κάθε αλγόριθμο συμπίεσης για αποτελεσματικά αποτελέσματα ομαδοποίησης στον ταχύτερο δυνατό χρόνο.