# Extension of DBSCAN in Online Clustering: An Approach Based on Three-Layer Granular Models
## 5 Experiment and Discussion
### Synthetic Data
#### 5.1.1 Optimal Prototypes and Granules Construction of Input Space  
After DBSCAN clustering, clusters with arbitrary shapes are obtained. In order to make use of these cluster information in online clustering, some representative points are selected to describe these clusters, called prototypes in the above context. At the beginning, we could choose these prototypes randomly, and express them as (3). Then, these prototypes are adjusted to obtain the strongest representativeness. Finally, an information granule centering on this prototype is constructed. The concrete algorithms are described as follows. Step 1: initiating prototypes and IGs. \(c\) prototypes in each cluster are chosen randomly, denoted as \(\{z_{i}\mid I=1,2,\cdots,c\}\). Then, IGs are constructed according to the description in Section 4.1. To initialize the IGs' size, the upper and lower bounds are calculated in a dimension-by-dimension way, seeing the granule construction in two-dimensional space, as seen in Figure 6. Firstly, the initialized prototypes and whole data points are projected at each one-dimension axis, and sorted in ascending order, e.g., \(\{\min(X_{1}),z_{1,1},z_{2,1},z_{3,1},z_{4,1},\max(X_{1})\}\) at axis \(X_{1}\). Then, the two closet prototypes are selected to compute their upper (or lower) bound through (17):  
\[u_{i,k}=l_{i+1,k}=\frac{z_{i,k}+z_{i+1,k}}{2} \tag{17}\]  
Figure 5: Distribution of data points in toy dataset. (**a**) Original data distribution; (**b**) DBSCAN clustering results (two clusters in red and green points, noise in blue points). where \(z_{i,k}\) and \(z_{j,k}\) are the values of two prototypes (\(z_{i}\) and \(z_{i+1}\)) at axis \(X_{k}\). This process is repeated to determine the bounds of all IGs. When the prototype, \(z_{i}\), is closet to \(0/1\), its bounds can be determined directly as \(l_{i,k}=\min(X_{k})\) or \(u_{i,k}=\max(X_{k})\), e.g., \(l_{1,1}\) and \(u_{4,1}\) in Figure 6.  
Step 2: updating prototypes. In Figure 6, it is seen that the initialized prototypes (red points) are not always the centroids of IGs. In order to improve the prototypes' representativeness, original prototypes can be updated after granule construction, as below:  
\[z_{i}^{\prime}=\left[\frac{u_{i,1}+l_{i,1}}{2},\ \ \frac{u_{i,2}+l_{i,2}}{2},\ \ \ldots,\ \ \frac{u_{i,n}+l_{i,n}}{2}\right] \tag{18}\]  
where \(z_{i}^{\prime}\) is the new prototype which is the centroid of the corresponding granule. Moreover, considering the randomness in the initial selection, the prototypes are not distributed uniformly, so the coverage and specificity performance may be affected. For example, when two prototypes close to each other, their granules are easily overlapped. Taking these issues into account, prototypes need to be updated further. Here, to evaluate the suitability of the updated prototypes, a metric is defined in (19) which requires the distance of all data points to their belonging prototypes as the minimum:  
\[\min Q=\sum_{i=1}^{c}\sum_{x\in G_{i}}\left\|x-z_{i}\right\|^{2} \tag{19}\]  
where \(Q\) is the objective function for updating prototypes; \(G_{i}\) is the \(i\)th information granule based on prototype \(z_{i}\); \(c\) is the number of granules; \(\left\|x-z_{i}\right\|^{2}\) is the Euclidean distance of point x to its corresponding prototype. When this objective function converges to a given threshold, the updated prototypes are regarded as optimal. Step 3: adjusting the size of IGs. By repeating Step 1 and Step 2, the optimal prototypes are determined, and IGs can be constructed. However, it is seen from Figure 6 that these primary granules can not achieve a good coverage, so it is necessary to adjust the size of granules based on Equations (6)-(8). Though there are \(2\times n\) parameters in (8), it will cost a lot of computation overhead in the adjustment process. Considering the prototypes are updated as the centroids of granules in Step 2, we could consider only one parameter here to adjust the granule size, namely the increment parameter (\(\epsilon\)) to the boundary.