DBSCAN

Η χωρική ομαδοποίηση εφαρμογών με θόρυβο με βάση την πυκνότητα ( DBSCAN ) είναι ένας αλγόριθμος ομαδοποίησης δεδομένων (clustering) που προτάθηκε από τους Martin Ester, Hans-Peter Kriegel, Jörg Sander και Xiaowei Xu το 1996. Είναι ένας μη παραμετρικός αλγόριθμος ομαδοποίησης που βασίζεται στην πυκνότητα : δεδομένου ενός συνόλου σημείων σε κάποιο χώρο, ομαδοποιεί σημεία που είναι στενά συσχετισμένα μεταξύ τους (σημεία με πολλούς κοντινούς γείτονες ), επισημαίνοντας ως ακραία σημεία που βρίσκονται μόνα τους σε περιοχές χαμηλής πυκνότητας (του οποίου οι κοντινότεροι γείτονες είναι πολύ μακριά). Το DBSCAN είναι ένας από τους πιο συνηθισμένους αλγόριθμους ομαδοποίησης και επίσης είναι απο τους πιό συχνά αναφερόμενους στην επιστημονική βιβλιογραφία. Most cited data mining articles according to Microsoft academic search; DBSCAN is on rank 24.

Το 2014, ο αλγόριθμος τιμήθηκε με το βραβείο test of time (βραβείο που δόθηκε σε αλγόριθμους που έχουν λάβει σημαντική προσοχή στη θεωρία και την πράξη) στο κορυφαίο συνέδριο εξόρυξης δεδομένων, ACM SIGKDD .   ,  η δημοσίευση "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN"  εμφανίζεται στη λίστα με τα 8 άρθρα με τις περισσότερες λήψεις του διάσημου περιοδικού ACM Transactions on Database Systems (TODS) .

 Ιστορία 
Το 1972, ο Robert F. Ling δημοσίευσε έναν στενά συνδεδεμένο αλγόριθμο στο "The Theory and Construction of k-Clusters"  στο The Computer Journal με εκτιμώμενη πολυπλοκότητα χρόνου εκτέλεσης O(n³). Το DBSCAN έχει στην χειρότερη περίπτωση O(n²) και η διατύπωση ερωτήματος εύρους προσανατολισμένη στη βάση δεδομένων (database-oriented range-query) του DBSCAN επιτρέπει την επιτάχυνση ευρετηριασμού (index acceleration). Οι αλγόριθμοι διαφέρουν ελαφρώς ως προς τον χειρισμό των συνόρων.

Παραπομπές

Κατηγορία:Αλγόριθμοι ανάλυσης συστάδων