# Extension of DBSCAN in Online Clustering: An Approach Based on Three-Layer Granular Models
## 1 Introduction
However, to improve the efficiency of clustering, large data are still a problem, e.g., how to accelerate the online clustering process, and how to reduce the total computing overhead. To address the issues mentioned above in online spatial data clustering, this paper proposes an advanced approach. This method is an extension of the DBSCAN algorithm combined with granular models. Referring to the idea of model-based methods, the proposed method consists of three layers. First, data are clustered by the DBSCAN algorithm in the original data space. Then, each DBSCAN cluster is described by information granules (IG) via granular computing (GrC) [19]. These granules have the structure information from DBSCAN, and are used as structural descriptors. Second, these structural granules are mapped into a hidden layer, which forms rules for determining the data's cluster belonging. In this medium space, the reconstruction metric and justifiable granulating are applied in the fuzzy rule formation. Finally, a rule-based model combining structural granules in input space and rules in medium space is constructed in the output space, and is used to guide the final online clustering. The major contributions of this proposed method are presented as the following three points:  
1. The superiority of using DBSCAN algorithms on the nonlinearly-inseparable data: DBSCAN is one of the typical density-based algorithms which group data points of dense regions, and separate regions of low density [14]. It has advantages at solving nonlinear inseparable issues by discovering clusters with arbitrary shapes, namely applicable on spatial data clustering. The second advantage of DBSCAN compared to other methods is the ignorance of expert knowledge on parameter setting, which is helpful to reduce human interference. 2. The usage of granular models in data description and rule-based modeling: according to human beings' knowledge, GrC divides an object into information granules, and builds granular models for description [20]. By making use of granular models, the shaped clusters in DBSCAN could be broken up into granules which slip the shape's influence. Moreover, granules could reconstruct a cluster with arbitrary shapes. With the information carried in each granule, it is easy to satisfy the expression of new data and complete their online clustering. 3. The proposed method has an advantage in reducing the computation cost in online clustering. Compared with other clustering algorithms, DBSCAN has a relatively acceptable computation complexity, and even has good efficiency on large data sets [21; 22]. Additionally, by using a limited number of granules and rules to guide the online clustering, the time of new data clustering can be significantly reduced. The rest of the paper is structured as follows. In Section 2, some related works on DBSCAN variants are reviewed. Section 3 describes the framework of the proposed method. Moreover, necessary data preprocessing and an introduction on DBSCAN are also presented. Section 4 describes the methodology of the proposed method, involving granule construction in the input space, granular rule formation in the medium space, the mapping and rule-based modeling process in the output space, and the online clustering process. Section 5 presents the experiment studies on both synthetic data and a typical spatial dataset. Finally, Section 6 concludes all of the studies in this paper.