DBSCAN is one of the most commonly used clustering algorithms whose purpose is to reveal clusters of arbitrary shape by domain minimal knowledge [1,2]. DBSCAN groups points based on the notion of -neighborhood of a point and a specified minimum number of neighboring points , which further are supplemented with the notions of core points, directly reachable points, non-directly reachable points, and outliers [3,4]. Besides, to rectify the non-symmetric relation of the reachability [5,6], a symmetric notion of density-connectedness is added [7,8]. The density is defined by the neighborhood radius and number , where a cluster contains at least points. The -neighborhood is defined as a set of points falling within radius by a distance function [5,9,10]. Apart from DBSCAN hyperparameters and , the distance function is seen as an additional parameter of the DBSCAN algorithm [7,11,12].
For points in a dataset, the DBSCAN average runtime complexity is , although the worst case of is not excluded [3,4,7], especially when there is probable incompleteness in data [9,10,13] or the neighborhood radius can vary in a wide range [5,12,14]. Whereas the overall performance of DBSCAN is quite satisfactory, and it successfully reveals outliers and identifies nonglobular shapes (contrary to other commonly used clustering algorithms like, e. g., k-means [9,15,16]), it fails to handle datasets whose clusters are of much varying densities [17,18]. The second drawback is the neighborhood radius selection [8,11,14]. While datasets of planar points or points in the three-dimensional space are visualized, the neighborhood radius is well understood and assessed, but higher dimensions are problematic to "see" a meaningful distance [19,20]. Moreover, quality of features may be pretty different and may change through a domain which is clustered [8]. This hinders in obtaining accurately partitioned datasets by coarsely applying DBSCAN [17].
There are domains whose factual clusters have multiple meaningful radii of the neighborhood [11,13,20].
Both the weaknesses of DBSCAN are addressed by OPTICS [21,22], which is another algorithm whose purpose is to detect meaningful clusters in data of varying density [23,24]. OPTICS also requires two hyperparameters and , although the neighborhood radius is not necessary. The radius can be set to the maximum possible value, but this results in runtime close to [25]. Besides, OPTICS is mainly intended for hierarchical clustering, and OPTICS is reported to have an actual constant slowdown factor of 1.6 compared to DBSCAN [21,26].
Another DBSCAN drawback, being reported less frequently, is its poorer performance on large datasets [27]. This especially concerns high-dimensional data, where it is difficult to find an appropriate value for due to adjusting this hyperparameter takes significant amounts of time and computational resources. Overall, tunability of DBSCAN hyperparameters (as well in other clustering algorithms) worsens as the dataset enlarges [28,29].
Nevertheless, when a large dataset is assumed to have tightly connected or not sparsely scattered clusters, it is possible to divide the dataset into multiple subdatasets in order to apply the DBSCAN algorithm to every subdataset separately. This resembles divide-andconquer approach successfully applied to solving large combinatorial optimization problems like the traveling salesman problem with thousands of nodes and larger [30]. In particular, the traveling salesman problem nodes are grouped into a definite number of clusters, each of which corresponds to an open-tour traveling salesman subproblem subsequently solved independently of solving other subproblems [31,32].
In cluster analysis, spatial dataset division is effective when possible clusters are not sparsely scattered. Otherwise, the problem of clustering tends to be almost trivial -the distinctly distanced groups of objects can be more efficiently separated by the support vector machine (linearly inseparable data are projected onto a higher dimensional space to become linearly separable [33,34]) or other similar approaches including k-means with evaluating the optimal number of clusters using the silhouette clustering evaluation criterion [15,35,36]. To the contrary, potential clusters closely packed together are totally indistinguishable without considering spatial densities if, for instance, the clusters have at least a partially hierarchical structure [2,37,38]. A marginal example of such a structure is a dataset consisting of nonoverlapping enclosed hyperspheres or hyperellipsoids (for planar objects, they are nonoverlapping enclosed circles or ellipses), or objects of similar form being irregularly distorted or nonconvex [29,39]. Another major example frequently occurred in practice is a dataset consisting of cluster bands, where serpentine-like clusters have a resembling structure [40].
Naturally, the DBSCAN algorithm could have been easily sped up if it was generally parallelizable [1,2,7]. Unfortunately, the algorithm is of two loops, and there is the nested loop which cannot be made independent of the outside loop [1,4]. The outside loop, working with each point in a given dataset, is based on the range query which can be implemented using database indexing for better performance rather than a slow linear scanning. Although some efforts have been made in this direction to parallelize the outside loop, the gain does not seem to have a significant impact [2,17,19].
A follow-up DBSCAN algorithm named HDBSCAN [2,17] was an attempt to rectify the DBSCAN flat-result drawbacks rather its poor parallelizability. Neither did GDBSCAN advances in parallelizability [5,7], which only moved the original DBSCAN algorithm parameters and to the predicates. Issuing from unsatisfactory runtime complexity of the DBSCAN algorithm for large datasets, the goal is to suggest an approach to DBSCAN parallelization without losing much in accuracy. The approach should be algorithmized by automatically adjusting neighborhood radius to the most efficient value. A series of computational experiments is to be carried out in order to see the performance of the parallelized DBSCAN algorithm with the hyperparameter adjustment compared to the performance of the original DBSCAN algorithm. The comparative results are then to be discussed by underlining limitations and drawbacks of the suggested DBSCAN parallelization.
To adjust DBSCAN hyperparameters automatically, consider an ultimate repetition of trying to improve the accuracy. As there are more possible versions of the neighborhood radius than those of the minimum number of neighboring points, the neighborhood radius is adjusted first. For this, denote the maximum number of accuracy improvement fails by . While the minimum number of neighboring points is adjusted, the maximum number of accuracy improvement fails denoted by is used. These hyperparameters are adjusted as follows:
1. Divide the dataset into subsets.
2. Set to a minimum and apply the DBSCAN algorithm to a subset of points with known ground truth labels.
3. While the current number of accuracy improvement fails is fewer than , increase by . Once the number of outliers and redundant labels becomes fewer, set the current number of accuracy improvement fails to 0, and store the current value of as the best one; otherwise, increase the current number of accuracy improvement fails by 1.
4. Denote the best neighborhood radius by . 5. Apply the DBSCAN algorithm to the remaining subsets. 6. Set to 3 and apply the DBSCAN algorithm to the subset by the best neighborhood radius .
7. While the current number of accuracy improvement fails is fewer than , increase by 1. Once the number of outliers and redundant labels becomes fewer, set the current number of accuracy improvement fails to 0, and store the current value of as the best one; otherwise, increase the current number of accuracy improvement fails by 1.
Obviously, running the DBSCAN algorithm on the remaining subsets can be executed in parallel. Moreover, as the hyperparameters are adjusted (on a labeled subset), the size of a labeled subset can be set to a few different versions, and the adjustment can be executed in parallel on these differently sized subsets [16,37,38]. Differently sized subsets are obtained by changing number .
First of all, the DBSCAN parallelization is expected to significantly reduce the computation time. Secondly, the clustering accuracy is believed to remain comparable to the DBSCAN algorithm itself, if even the adjusted hyperparameters are used in it. The correctness of these hypotheses is going to be ascertained or falsified by computational experiments. A specificity of such experiments is that the dataset can be visualized, with better or worse extent of cluster appearance and distinguishability.
The performance of the parallelized DBSCAN algorithm with the hyperparameter adjustment is estimated by running the above-stated algorithm on planar datasets whose potential clusters are closely packed together. There are two types of such datasets: developing and enveloping. Serpentine-like clusters form a developing dataset (Figure 1). Non-overlapping enclosed circles or ellipses modulated by sinusoidal functions form an enveloping dataset (Figure 2). For abbreviation, these clusters (datasets) will be called serpentine and circular clusters (datasets), respectively.
i. e., , the dataset size is , and is the number of clusters of size each.
Besides, values and of two additional normally distributed random variables with zero mean and unit variance are used for this dataset. Thus, the horizontal component is
, ( 5) where both and are independent being chosen randomly between 3 and 4 with a step of 0.001; both and are independent being chosen randomly between 0.01 and 0.1 with a step of ; is chosen randomly between 0.0005 and 0.005 with a step of , whereupon it is set negative if ; is varied between 0.1 and 0.5 with a step of 0.1; is chosen randomly between 0.0005 and 0.005 with a step of , whereupon it is set negative if . The serpentine dataset by ( 2), ( 3), ( 1), ( 4), ( 5) is generated with three to 18 clusters, , for five versions of noise magnitude, , where each cluster contains 1000 to 10000 points with a step of 1000 points, .
Clusters contain the same number of points . The dataset is divided into subsets so that each cluster would contain the same number of points within every subset, where (6) and subset is clustered, if is even and if is odd. Therefore, for a one generation of the serpentine dataset, there are 10 versions of the dataset size, 16 versions of the dataset cluster number, five versions of noise magnitude, and five versions of the dataset division. Applied to a dataset, the parallelized DBSCAN algorithm returns the best neighborhood radius , the best minimum number of neighboring points , the number of outliers (labeled by ), the number of points incorrectly labeled as non-existing clusters (their labels are greater than , as if there are some other one or a few clusters), and the number of points incorrectly labeled as existing clusters (being between 1 and , their labels are factually incorrect or confused). The total number of missed (incorrectly labeled) points is (7) whose percentage is
The serpentine dataset generation is repeated for 100 times, whereupon the results are averaged over the 100 repetitions. The averages are presented as a array whose entry is a set of , , , , , , .
Another array presents averages of the computation time. To compare results (9) with those produced by the DBSCAN algorithm itself, the parallelized DBSCAN algorithm with the hyperparameter adjustment is also used, but with and . The original DBSCAN algorithm results are stored as a array with (9). Another array presents averages of the DBSCAN computation time. Comparative computation time statistics for the planar serpentine dataset is presented in Table 1, where every entry is an averaged ratio of the original DBSCAN algorithm computation time to the parallelized DBSCAN algorithm computation time. Ratio is a computation time function of the dataset size and the number of dataset clusters, which is a matrix preliminarily averaged over noise; is a matrix preliminarily averaged over dataset size; is a matrix preliminarily averaged over the number of dataset clusters. The advantage of the parallelized DBSCAN algorithm is quite obvious -it is much faster, while, prudently speaking, the speedup minimum is above 10 times and the speedup maximum exceeds 100 times. On overall average, the parallelized DBSCAN is 97.21 times faster. Comparative performance statistics for the planar serpentine dataset is presented in Table 2, where rows with
contain percentages, "Five intervals" stands for the parallelized DBSCAN with five versions of the dataset division, and "Best interval" stands for the parallelized DBSCAN with the version at which percentage (8) of missed (incorrectly labeled) points is minimal. Herein and below, the DBSCAN accuracy is decomposed into rates for (10) and (8). The parallelized DBSCAN misses (loses) points at a rate of about 7 %, whereas it is above 26 % by the original DBSCAN.
Points misidentified as outliers are lost at almost equal rates, although a little advantage of the parallelized DBSCAN exists whose rate is below 1.95 % (while the original DBSCAN loses above 2.1 % of points misidentified as outliers). The original DBSCAN incorrectly assigns above 3.1 % of points to non-existing clusters, but this rate is as 2.5 times as lower for the parallelized DBSCAN. The original DBSCAN confuses clusters even more exceeding 21 % of points incorrectly assigned to existing clusters, while this rate for the parallelized DBSCAN is slightly above 3.8 %. When the best interval is selected, the mentioned rates for (10) and ( 8) drop below 0.21 %, 0.26 %, 0.73 %, 1.19 %, respectively. However, the worst cases of the rates for (10) and ( 8) are not excluded even by the parallelized DBSCAN with the best interval (Figure 3). is chosen randomly between 0 and with a step of ; if and if ; is varied between 0.2 and 1 with a step of 0.2. The planar circular dataset by ( 11), ( 12), ( 1), ( 13) is generated with three to eight clusters, , for five versions of noise magnitude, , where each cluster contains 1000 to 10000 points with a step of 1000 points, .
The remaining parameters of the circular dataset and its processing including ( 6) -( 9) are the same as for the serpentine dataset, except for the array size that is now (the second dimension has 6 entries, which influences the subsequent arrays upon averaging, minimizing, and maximizing).
Presented in Table 3, comparative computation time statistics for the planar circular dataset resemble that in Table 1 for the planar serpentine dataset. Thus, the parallelized DBSCAN speedup minimum is, prudently speaking, above 15 times and the speedup maximum exceeds 125 times, by roughly the same standard deviations. On overall average, the parallelized DBSCAN is 99.67 times faster (particularly, it is due to the maximum number of clusters here is fewer than that for the planar serpentine dataset). Presented in Table 4, comparative performance statistics for the planar circular dataset confirms the advantage of the parallelized DBSCAN algorithm. The parallelized DBSCAN loses points at a rate of about 7.12 % (slightly higher than that for the planar dataset), whereas it is 11.85 % by the original DBSCAN being 2.25 times lower than that for the planar dataset. Points misidentified as outliers are lost at rates of 1 % and 1.42 % by the original and parallelized DBSCAN algorithms, respectively. So, the parallelized DBSCAN may lose more circularly located points than the original DBSCAN. The original DBSCAN incorrectly assigns above 5.59 % of points to non-existing clusters, but this rate is as 4.26 times as lower for the parallelized DBSCAN. The cluster confusion is at similar rates -it is 5.25 % and 4.39 % by the original and parallelized DBSCAN algorithms, respectively. When the best interval is selected, the mentioned rates for ( 10) and ( 8) drop below 0.7 %, 0.3 %, 1.97 %, 2.96 %, respectively. These rates are clearly higher than those for the planar serpentine dataset. Nevertheless, the planar circular dataset worst case (Figure 4) is not a complete fail like the planar serpentine dataset worst case is. It is worth noting that the dataset worst case in Figure 4 has far much more variety in its structure than that in the worst case in Figure 3. Despite this, the best-interval parallelized DBSCAN performs relatively much better than the original DBSCAN. The latter has 73.7 % of missed points versus 44.9 % of points missed by the parallelized DBSCAN with (Figure 5). The percentage of outliers, however, is 13.1 % by the parallelized DBSCAN, whereas the original DBSCAN leaves here 7.225 % of points as outliers. Meanwhile, the original DBSCAN assigns 59.925 % of points to non-existing clusters, and this rate is just 8.3 % for the parallelized DBSCAN (the black-square marked points are clearly seen in Figure 5). Due to this, the cluster confusion is lower at the original DBSCAN -it is 6.55 % versus 23.5 % at the parallelized DBSCAN. In this particular example, the parallelized DBSCAN performance significantly worsens as the dataset is divided into fewer subsets. Thus, and the rates for (10) are 6.7625 %, 13.1625 %, 28.15 % with , but and the rates for (10) are 5.9875 %, 26.9125 %, 30.7625 % with (Figure 6). Furthermore, these rates are 52.9625 %, 1.1875 %, 3.2625 %, 48.5125 % with , and 69.25 %, 0.7875 %, 1.0125 %, 67.45 % with , respectively (Figure 7), i. e. the rate of the cluster confusion grows while the rate of outliers drops. The rate of points assigned to non-existing clusters becomes lower as the subset is made larger (or, in other words, number is taken fewer).
For creating three-dimensional serpentine-like clusters, a circular dataset point
by ( 13),
, ,
and values , , of three additional normally distributed random variables with zero mean and unit variance, wherein is chosen randomly between 0.1 and 3 with a step of ; if and if ; is chosen randomly between 2 and 18 with a step of 1; is chosen randomly between 0 and with a step of ; if and is varied between 0.1 and 0.5 with a step of 0.1. Three-dimensional serpentine-like clusters form a developing dataset whose visualization is far much more complicated than that of the planar circular dataset (Figure 8). The three-dimensional serpentine dataset by ( 14) -( 16), (1), ( 13), ( 17), ( 18) is generated with three to eight clusters, , for five versions of noise magnitude, , where each cluster contains 1000 to 10000 points with a step of 1000 points, .
The remaining parameters of the three-dimensional serpentine dataset and its processing including ( 6) -( 9) are the same as for the planar circular dataset. Presented in Table 5, comparative computation time statistics for the three-dimensional serpentine dataset does not resemble that in Tables 1 and 2 for the planar datasets. Here, the parallelized DBSCAN speedup minimum is, prudently speaking, above 40 times and the speedup maximum exceeds 600 times, although standard deviations are higher than those for the planar datasets. On overall average, the parallelized DBSCAN over three-dimensional serpentine datasets is 342 times faster. Eventually presented in Table 6, comparative performance statistics for the threedimensional serpentine dataset again confirms the advantage of the parallelized DBSCAN algorithm, but if the best subset size (best interval) is selected. The parallelized DBSCAN loses points at a higher rate (roughly, 12.5 %) than the original DBSCAN does (roughly, 8.6 %), but the best-interval parallelized DBSCAN misses points at a rate of below 4.8 %. The original DBSCAN rarely "sees" outliers having their average rate below 0.1 % and its maximum below 12.5 %, but it "sees" non-existing clusters at a rate of 2.97 % and confuses clusters at a rate of 5.57 %. The respective rates of non-existing clusters and cluster confusion for the parallelized DBSCAN are 5.37 % and 4.39 %, whereas they drop to 2.086 % and 2.065 % with the bestinterval parallelized DBSCAN.
The worst three-dimensional case is in Figure 8, where 76.725 % of points are missed by the best-interval parallelized DBSCAN with the dataset division into 100 subsets. Meanwhile, the original DBSCAN performs at a rate of 24.25 % on this dataset. It is worth noting that in this case the noise magnitude is minimal. It appears to be paradoxical, but at greater noise magnitudes the best-interval parallelized DBSCAN performs even worse on some instances of the three-dimensional dataset with the maximum of clusters. The particular dataset in Figure 8 turns out to be the worst case due to the original DBSCAN performs far better on it (it could be even acceptable in some practical situations), and thus the difference between the original and best-interval parallelized DBSCAN algorithms is paradoxically huge.
Compared to the performance of the original DBSCAN algorithm, the parallelized DBSCAN performs more accurately being extremely fast. The latter is straightforwardly inferred from Tables 1, 3, 5, where the average speedup exceeds 80 times for planar datasets and exceeds 300 times for three-dimensional datasets. The gain in accuracy is not that unambiguous. While the parallelized DBSCAN outperforms the original DBSCAN on planar datasets (Tables 2 and 4), even without selecting the best size of the subset (called the best interval due to planarity), it underperforms on three-dimensional datasets without selecting the best-interval result. Only the best-interval parallelized DBSCAN outperforms the original DBSCAN on threedimensional datasets. It is likely reasoned by a higher complexity of the structure of such datasets (see Figure 8) compared to the structure of planar datasets (see Figures 1 -4). In other words, the DBSCAN parallelization by spatial dataset division and hyperparameter adjustment is less efficient on datasets with more complex structure. However, the series of computational experiments has exposed a possibility of the parallelized DBSCAN underperformance for simple-structured datasets also (see Figure 3 with the worst case of the planar serpentine dataset, although its structure is far much simpler than the structure of planar circular dataset in Figure 4). The growing number of clusters may additionally affect the parallelized DBSCAN performance. Nevertheless, as the dataset size increases and the number of clusters increases, one by one or together, the parallelized DBSCAN outperforms the original DBSCAN more. The gain in accuracy ranges from 4.9072 to 276.8096 times for the planar serpentine dataset, when an averaged over noise ratio of the original DBSCAN accuracy to the parallelized DBSCAN accuracy is considered as a function of the dataset size and the number of clusters. The accuracy gain drastically drops for the planar circular dataset ranging from 1.4636 to 5.5163 times. For the three-dimensional serpentine dataset, the accuracy gain ranges from 0.0004 to 10.9631, i. e. it is below 1 for three and four clusters (it is just 0.1007 and 0.3179 for three and four clusters, respectively). For five clusters and more, along with the dataset size increasing, the parallelized DBSCAN outperforms the original DBSCAN. The poorer performance on the fewest number of clusters is an obvious limitation of the parallelized DBSCAN.
Another limitation is the poorer performance on datasets with circularity. Dividing into intervals is uncommon for circular datasets, whose natural division would be circular-sector, especially for three-dimensional datasets. Moreover, it is hard to divide so that each cluster would contain (approximately) the same number of points within every subset. In addition, the DBSCAN parallelization efficiency is impossible to estimate without known ground truth labels.
The DBSCAN parallelization efficiency expectedly deteriorates when density is changeable. The dataset in Figure 3 is seemingly the case, where each serpentine has significantly thinner and thicker intervals observable via zoom-in. This is the most common drawback of densitybased clustering methods, although they all, and the DBSCAN algorithm in particular, are intended to handle varying densities of points. However, the datasets used for the computational experiments have density-modulated regions (i. e., varying density of regions of changeable densities of points), which have served as a close-to-the-worst-case scenario in order to reveal weaknesses of the suggested DBSCAN parallelization.
Overall, it is a promising approach to speed up arbitrary-shape clustering without losing in accuracy. Posed as a local optimization versus global optimization, the parallelized DBSCAN performs well on serpentine datasets but not limited only to them. The hyperparameters, neighborhood radius and minimum-neighbors number, are gradually adjusted with some steps, which are tunable also (basically, the neighborhood radius increment step). Apart from the subsets of the divided dataset, the suggested modification of the DBSCAN algorithm can be run in parallel for multiple labeled subset sizes, as well as for a few versions of the neighborhood radius increment step.