# Extension of DBSCAN in Online Clustering: An Approach Based on Three-Layer Granular Models
## 2 Related Work on DBSCAN Variants
### Extensions of DBSCAN Algorithms  
However, in some real applications, the original DBSCAN algorithm has some drawbacks, e.g., the poor robustness, and the limitations on clustering data with different densities. Therefore, modifications of the DBSCAN algorithm were proposed in the literature, e.g., VDBSCAN, FDBSCAN, Fast DBSCAN, Grid-DBSCAN, and so on [33; 34]. Here, two commonly used variants (Fuzzy-DBSCAN and Grid-DBSCAN) are reviewed.  
Fuzzy DBSCAN algorithms were proposed to improve the robustness. In original DBSCAN algorithms, a data point is determined to belong or not belong to a cluster. However, in some special cases where a cluster is adjacent to other clusters, it means that the border points of two clusters are close, or that a border point belongs to several different clusters at the same time. Therefore, the membership of fuzzy theory is usually introduced to deal with this kind of fuzzy concept. The fuzzy DBSCAN algorithms were simply called FN-DBSCAN [35], and they were commonly developed into three types: fuzzy core, fuzzy boundaries, and a combination of the previous two. The first type of extension model was based on fuzzy core, and it actually utilized fuzzy membership functions to define the density function and redefined core points [36]. It proposed a soft constraint which specified the approximative number of points in the neighborhood of core points. Then, these core points were grouped to fuzzy clusters. Contrary to standard DBSCAN algorithms, which are sensitive to the number of neighbor data points, FN-DBSCAN algorithms are sensitive to the density of neighbor data points. The second type of extension models applied the fuzzy theory to generate the fuzzy boundary [35]. These algorithms defined a membership function on the distance as a soft constraint. This definition made it possible to generate fuzzy clusters with approximate reachability properties and overlapping boundaries. The third type of models combine the previous two fuzziness, namely approximately dense fuzzy cores and reachable fuzzy boundaries [37]. All of these models allow to obtain a much more flexible extension of the DBSCAN algorithm, and to improve the scalability of clustering data points. However, FN-DBSCAN models cost more computation time than standard DBSCAN algorithms due to the fuzzification process. Their results, the same as DBSCAN algorithms, are also not numerical, limiting the extension on online testing for new data points.  
Grid-DBSCAN was proposed to deal with the issue that the original DBSCAN algorithms are not effective on grouping clusters with different densities. Its main idea is combining the idea of density-based and grid-based clustering algorithms. Therefore, it was also regarded as a representative hybrid algorithm [38]. It contains two stages to realize clustering of different density groups. At the first stage, it utilizes the grid-based idea to divide feature space into appropriate grids, and the density is similar in each grid. In this way, it forms a multiresolution grid data structure. Then, at the second stage, it aggregates grids with the same densities into groups, and those groups with appropriate density parameters are identified as the final clusters. This is actually implemented by the idea of DBSCAN algorithms. Since the computation time of Grid-DBSCAN relies on the amount of grid cells instead of that of data points, it not only has the ability of clustering different density issues, but also a better computational complexity.