DBSCAN

Η χωρική ομαδοποίηση εφαρμογών με θόρυβο με βάση την πυκνότητα ( DBSCAN ) είναι ένας αλγόριθμος ομαδοποίησης δεδομένων (clustering) που προτάθηκε από τους Martin Ester, Hans-Peter Kriegel, Jörg Sander και Xiaowei Xu το 1996.[1] Είναι ένας μη παραμετρικός αλγόριθμος ομαδοποίησης που βασίζεται στην πυκνότητα : δεδομένου ενός συνόλου σημείων σε κάποιο χώρο, ομαδοποιεί σημεία που είναι στενά συσχετισμένα μεταξύ τους (σημεία με πολλούς κοντινούς γείτονες ), επισημαίνοντας ως ακραία σημεία που βρίσκονται μόνα τους σε περιοχές χαμηλής πυκνότητας (του οποίου οι κοντινότεροι γείτονες είναι πολύ μακριά). Το DBSCAN είναι ένας από τους πιο συνηθισμένους αλγόριθμους ομαδοποίησης και επίσης είναι απο τους πιό συχνά αναφερόμενους στην επιστημονική βιβλιογραφία.[2]

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

Ιστορία

[Επεξεργασία | επεξεργασία κώδικα]

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

Παραπομπές

[Επεξεργασία | επεξεργασία κώδικα]
  1. ↑ «A density-based algorithm for discovering clusters in large spatial databases with noise». Αρχειοθετήθηκε από το πρωτότυπο στις 2022-07-09. https://web.archive.org/web/20220709225703/https://aaai.org/Papers/KDD/1996/KDD96-037.pdf. Ανακτήθηκε στις 2022-11-08. 
  2. ↑ «Microsoft Academic Search: Papers». Αρχειοθετήθηκε από το πρωτότυπο στις 21 Απριλίου 2010. Ανακτήθηκε στις 18 Απριλίου 2010.  Most cited data mining articles according to Microsoft academic search; DBSCAN is on rank 24.
  3. ↑ «2014 SIGKDD Test of Time Award». ACM SIGKDD. 18 Αυγούστου 2014. Ανακτήθηκε στις 27 Ιουλίου 2016. 
  4. ↑ Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei (July 2017). «DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN». ACM Trans. Database Syst. 42 (3): 19:1–19:21. doi:10.1145/3068335. ISSN 0362-5915. https://www.vitavonni.de/research/acm.html#item3068335. 
  5. ↑ «TODS Home». tods.acm.org (στα Αγγλικά). Association for Computing Machinery. Ανακτήθηκε στις 16 Ιουλίου 2020. 
  6. ↑ 6,0 6,1 Ling, R. F. (1972-01-01). «On the theory and construction of k-clusters» (στα αγγλικά). The Computer Journal 15 (4): 326–332. doi:10.1093/comjnl/15.4.326. ISSN 0010-4620. https://academic.oup.com/comjnl/article/15/4/326/351493.