<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>Density-based spatial clustering of applications with noise (DBSCAN) is a commonly known and used algorithm for data clustering. It applies a density-based approach and can produce clusters of any shape. However, it has a drawback—its worst-case computational complexity is <italic>O</italic>(<italic>n</italic><sup>2</sup>) with regard to the number of data items <italic>n</italic>. The paper presents GrDBSCAN: a granular modification of DBSCAN with reduced complexity. The proposed GrDBSCAN first granulates data into fuzzy granules and then runs density-based clustering on the resulting granules. The complexity of GrDBSCAN is linear with regard to the input data size and higher only for the number of granules. That number is, however, a parameter of the GrDBSCAN algorithm and is (significantly) lower than that of input data items. This results in shorter clustering time than in the case of DBSCAN. The paper is accompanied by numerical experiments. The implementation of GrDBSCAN is freely available from a public repository.</p>
</abstract>

Density-based spatial clustering of applications with noise (DBSCAN) is a commonly known and used algorithm for data clustering. It applies a density-based approach and can produce clusters of any shape. However, it has a drawback—its worst-case computational complexity is O(n2) with regard to the number of data items n. The paper presents GrDBSCAN: a granular modification of DBSCAN with reduced complexity. The proposed GrDBSCAN first granulates data into fuzzy granules and then runs density-based clustering on the resulting granules. The complexity of GrDBSCAN is linear with regard to the input data size and higher only for the number of granules. That number is, however, a parameter of the GrDBSCAN algorithm and is (significantly) lower than that of input data items. This results in shorter clustering time than in the case of DBSCAN. The paper is accompanied by numerical experiments. The implementation of GrDBSCAN is freely available from a public repository.

GrDBSCAN: A Granular Density–Based Clustering Algorithm

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"GrDBSCAN: A Granular Density\u2013Based Clustering Algorithm"}

Density-based spatial clustering of applications with noise (DBSCAN) is a commonly known and used algorithm for data clustering. It applies a density-based...

GrDBSCAN: A Granular Density–Based Clustering Algorithm

Data publikacji: 23 cze 2023

Zakres stron: 297 - 312

Otrzymano: 13 wrz 2022

Przyjęty: 23 sty 2023

DOI: https://doi.org/10.34768/amcs-2023-0022

Słowa kluczowe
granular computing, DBSCAN, clustering, GrDBSCAN

© 2023 Dawid Suchy et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

GrDBSCAN: A Granular Density–Based Clustering Algorithm

Data publikacji: 23 cze 2023

Zakres stron: 297 - 312

Otrzymano: 13 wrz 2022

Przyjęty: 23 sty 2023

DOI: https://doi.org/10.34768/amcs-2023-0022

Słowa kluczowegranular computing, DBSCAN, clustering, GrDBSCAN

© 2023 Dawid Suchy et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Słowa kluczowe
granular computing, DBSCAN, clustering, GrDBSCAN