DBSCAN

La agrupació espacial d'aplicacions amb soroll basada en densitat (DBSCAN) és un algorisme de agrupació de dades proposat per Martin Ester, Hans-Peter Kriegel, Jörg Sander i Xiaowei Xu el 1996. És un algorisme no paramètric d'agrupament basat en la densitat: donat un conjunt de punts en algun espai, agrupa els punts que estan estretament empaquetats (punts amb molts veïns propers), marcant com a punts atípics que es troben sols en regions de baixa densitat. (els veïns més propers estan massa lluny). DBSCAN és un dels algorismes d'agrupació més comuns i més citats.

El 2014, l'algoritme va rebre el premi de prova del temps (un premi atorgat a algorismes que han rebut una atenció substancial en teoria i pràctica) a la conferència de mineria de dades líder, ACM SIGKDD.^[1] A 2020^[update], el document de seguiment "DBSCAN Revisited, Revisited: Why and How You Should (Still) Use DBSCAN" ^[2] apareix a la llista dels 8 articles més descarregats de la prestigiosa revista ACM Transactions on Database Systems (TODS).^[3]

El popular seguiment HDBSCAN* va ser publicat inicialment per Ricardo JG Campello, David Moulavi i Jörg Sander el 2013, després es va ampliar amb Arthur Zimek el 2015.^[4] Revisa algunes de les decisions originals, com ara els punts de frontera, i produeix un resultat jeràrquic en lloc d'un resultat pla.

En aquest diagrama, minPts=4. El punt A i els altres punts vermells són punts centrals, perquè l'àrea que envolta aquests punts en un radi $ε$ conté almenys 4 punts (incloent el punt mateix). Com que tots són accessibles els uns dels altres, formen un únic clúster. Els punts B i C no són punts centrals, però són accessibles des de A (mitjançant altres punts centrals) i per tant també pertanyen al clúster. El punt N és un punt de soroll que no és ni un punt central ni directament accessible.

↑ «2014 SIGKDD Test of Time Award» (en anglès). ACM SIGKDD, 18-08-2014. [Consulta: 27 juliol 2016].
↑ Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei ACM Trans. Database Syst., 42, 3, July 2017, pàg. 19:1–19:21. DOI: 10.1145/3068335. ISSN: 0362-5915.
↑ «TODS Home» (en anglès). tods.acm.org. Association for Computing Machinery. [Consulta: 16 juliol 2020].
↑ Campello, Ricardo J. G. B.; Moulavi, Davoud; Zimek, Arthur; Sander, Jörg ACM Transactions on Knowledge Discovery from Data, 10, 1, 2015, pàg. 1–51. DOI: 10.1145/2733381. ISSN: 1556-4681.

[1] «2014 SIGKDD Test of Time Award» (en anglès). ACM SIGKDD, 18-08-2014. [Consulta: 27 juliol 2016].

[tods-2] Schubert, Erich; Sander, Jörg; Ester, Martin; Kriegel, Hans Peter; Xu, Xiaowei ACM Trans. Database Syst., 42, 3, July 2017, pàg. 19:1–19:21. DOI: 10.1145/3068335. ISSN: 0362-5915.

[3] «TODS Home» (en anglès). tods.acm.org. Association for Computing Machinery. [Consulta: 16 juliol 2020].

[hdbscan2-4] Campello, Ricardo J. G. B.; Moulavi, Davoud; Zimek, Arthur; Sander, Jörg ACM Transactions on Knowledge Discovery from Data, 10, 1, 2015, pàg. 1–51. DOI: 10.1145/2733381. ISSN: 1556-4681.

[1]

[2]

[3]

[4]