# A Fast Multiscale Clustering Approach Based on DBSCAN

Authors: Runzi Chen; Shuliang Zhao; Meishe Liang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Multiscale brings great benefits for people to observe objects or problems from different perspectives. It has practical significance for clustering on multiscale data. At present, there is a lack of research on the clustering of large-scale data under the premise that clustering results of small-scale datasets have been obtained. If one does cluster on large-scale datasets by using traditional methods, two disadvantages are as follows: (1) Clustering results of small-scale datasets are not utilized. (2) Traditional method will cause more running overhead. Aims at these shortcomings, this paper proposes a multiscale clustering framework based on DBSCAN. This framework uses DBSCAN for clustering small-scale datasets, then introduces algorithm Scaling-Up Cluster Centers (SUCC) generating cluster centers of large-scale datasets by merging clustering results of small-scale datasets, not mining raw large-scale datasets. We show experimentally that, compared to traditional algorithm DBACAN and leading algorithms DBSCAN++ and HDBSCAN, SUCC can provide not only competitive performance but reduce computational cost. In addition, under the guidance of experts, the performance of SUCC is more competitive in accuracy.


---

## Body

## 1. Introduction

Clustering is one of the vital data mining and machine learning techniques and that aims to group similar objects into the same cluster and separate dissimilar objects into different clusters [1]. It is so prominent and recently attracted significant attention of researchers and practitioners from different domains of science and engineering [2]. Thousands of papers have been published [3–6]. However, these investigations concentrate on clustering from a single perspective.The scale can be equivalent to the following concept: generic concept, level of abstraction or perspective of observation, the same problem, or system can be perceived at different scales based on particular needs [7]. That is called multiscale phenomena and has been widely applied to the academic fields, such as geoscience [8, 9] and mathematics [10]. Multiscale clustering has gained popularity in recent years. However, these studies either focus on specific application scenarios [11–13] or rely on specific clustering methods [14–16], and they perform clustering based on raw data, which is highly time consuming. Figure 1 shows two implementations of multiscale clustering, which can help users conduct clustering analysis on multiscale datasets. The straightforward way of obtaining the knowledge of every scale is to apply the traditional mining algorithms to each scale dataset, which is very inefficient. In this study, we concentrate on Scaling-Up Cluster Centers (SUCC) from small scale to large scale and avoid repetitive clustering on raw datasets, with competitive efficiency.Figure 1
Two implementing measures for multiscale data mining.


### 1.1. Motivations

The multiscale phenomenon is a widely accepted concept that helps people understand problems from different levels of abstraction. Clustering analysis on multiscale datasets considerably influences knowledge discovery when capturing the essence of the problem. For example, assume that a telecommunication supplier has many filiales, and each filiale accomplishes clustering analysis for its customers. After that, the controlling corporation also needs to conduct clustering analysis for all customers. It is inefficient that clustering at each scale data by using the traditional method, i.e., reclustering, while SUCC can improve efficiency by computing cluster centers belonged small-scale data and obtaining large scale’s clusters. In addition, the concept of “fine-grained and more fine-grained” in the RFID domain [17–19] and the strategy of dividing and conquering, i.e., separating tags into many small subsets, then handling in sequence [20–23], can motivate our work.


### 1.2. Contributions

We provide a mathematical model (multiscale clustering framework), then design a novel algorithm named Scaling-Up Cluster Centers (SUCC) from small scale to large scale, which avoids repetitive clustering on raw datasets.We conducted extensive experiments to evaluate our work. Experimental results show that the SUCC is efficient and reduces runtime consumption with competitive accuracy compared to traditional methods and the leading algorithms, which need to deal with raw data that is much more than cluster centers belonged small-scale data in most instances.


### 1.3. Structure of the Paper

The rest of this paper is organized as follows. Section2 discusses the related work. The problem is described detailedly in Section 3. The framework of multiscale clustering and algorithm SUCC is designed in Section 4. Section 5 details the comparison experiments, and Section 6 concludes our work and provides some future research directions.


## 1.1. Motivations

The multiscale phenomenon is a widely accepted concept that helps people understand problems from different levels of abstraction. Clustering analysis on multiscale datasets considerably influences knowledge discovery when capturing the essence of the problem. For example, assume that a telecommunication supplier has many filiales, and each filiale accomplishes clustering analysis for its customers. After that, the controlling corporation also needs to conduct clustering analysis for all customers. It is inefficient that clustering at each scale data by using the traditional method, i.e., reclustering, while SUCC can improve efficiency by computing cluster centers belonged small-scale data and obtaining large scale’s clusters. In addition, the concept of “fine-grained and more fine-grained” in the RFID domain [17–19] and the strategy of dividing and conquering, i.e., separating tags into many small subsets, then handling in sequence [20–23], can motivate our work.


## 1.2. Contributions

We provide a mathematical model (multiscale clustering framework), then design a novel algorithm named Scaling-Up Cluster Centers (SUCC) from small scale to large scale, which avoids repetitive clustering on raw datasets.We conducted extensive experiments to evaluate our work. Experimental results show that the SUCC is efficient and reduces runtime consumption with competitive accuracy compared to traditional methods and the leading algorithms, which need to deal with raw data that is much more than cluster centers belonged small-scale data in most instances.


## 1.3. Structure of the Paper

The rest of this paper is organized as follows. Section2 discusses the related work. The problem is described detailedly in Section 3. The framework of multiscale clustering and algorithm SUCC is designed in Section 4. Section 5 details the comparison experiments, and Section 6 concludes our work and provides some future research directions.


## 2. Related Work

Clustering has not been a precise definition; there are a lot of different clustering approaches towards various techniques. In this section, we review the clustering approaches in two aspects.


### 2.1. Conventional Clustering Techniques

Han et al. suggested the following four categories for dividing clustering techniques: partitioning methods, hierarchical methods, density-based methods, and grid-based methods [24].Partitioning method assigns a dataset intok clusters such that each cluster must contain at least one element. k-means algorithm proposed by MacQueen in 1967 is the most classical representation of Partitioning method [25], and that is one of the best-known and simplest clustering algorithms [26]. Dunn developed Fuzzy c-means algorithm (FCM) for clustering data in 1973 [27]. FCM [28] allows one element to belong to two or more clusters unlike k-means where only one cluster is assigned to each element and improved by Bezdek in 1981. However, the time complexity of k-means is much less than that of FCM; thus, k-means work faster than FCM [29]. The advantages of partitioning algorithms include that they are (1) relatively scalable and simple and (2) suitable for finding spherical-shaped clusters. However, disadvantages of these algorithms include (1) the necessity for the user to specify the number of clusters in advance; (2) high sensitivity to value of initialization, noise, and outliers; and (3) failure to deal with nonconvex clusters [30].Hierarchical clustering can be divided into agglomerative method and divisive method [31]. The former follows the bottom-up strategy, which generates clusters starting with single element and then merging these small clusters into larger and larger clusters, until all of the elements are in a single cluster or otherwise until certain termination conditions are satisfied. The latter follows the top-down strategy, which breaks up cluster placed all objects into smaller and smaller clusters, until each cluster containing only one element or until certain termination conditions are satisfied. There are three forms of the agglomerative method, namely, single-linkage clustering [32], complete-linkage clustering [33], and average-linkage clustering [34]. After that, some enhanced hierarchical clustering methods are introduced, such as BIRCH [35, 36], CURE [37], ROCK [38], and CHAMELEON [39].Ester et al. demonstrated an algorithm called DBSCAN (density-based spatial clustering of applications with noise) [40], which discovers clusters of arbitrary shapes and is efficient for large spatial databases. Other well-known density-based techniques [41] are as follows: SNOB proposed by Wallace and Dowe in 1994 and MCLUST [42] introduced by Fraley and Raftery in 1998. Among these methods, the expectation-maximization (EM) algorithm is the most popular [41, 43].These methods partition the space into a finite number of cells that form a grid structure on which all of the operations for clustering are performed. The main advantage of the approach is its fast processing time [24], no need of distance computations, and easy to determine which clusters are neighbouring. There are many other interesting grid-based techniques including STING (statistical information grid approach) [44] by Wang et al. in 1997, one of the highly scalable algorithm and has the ability to decompose the dataset into various levels of detail. CLIQUE [45] is developed by Agrawal et al. in 1998, which can be considered as both density-based and grid-based clustering methods. It automatically finds subspaces of high dimensional data space that allows better clustering than original space. The accuracy of the clustering result may be degraded at the expense of simplicity of the method CLIQUE.


### 2.2. Multilevel Clustering

In recent years, the researchers introduced the idea of stratification into clustering. Psomopoulos et al. presented a multiple level clustering algorithm for detecting inter- and intragenome gene clusters, by introducing the notion of a hierarchy. This method is experimentally proven to be consistent with the phylogenetic relation and position of the genes involved [46]. Vu et al. developed a new multithreaded tool, fMLC, addressed the problem of clustering large-scale DNA sequences [12]. A multilevel clustering for star/galaxy separation was designed in 2016, consisting of three phases: coarsening clustering, representative data clustering, and merging [47]. In 2019, Zunic et al. proposed a multilevel clustering algorithm that is used on Internal Banking Payment System in a bank of Bosnia and Herzegovina and explained how the parameter effects on results and execution time in algorithm [13]. [11] presented a multilevel clustering approach that addressed the issue that conventional algorithms spent too much execution time clustering physical activity data. [48] proposed an MCT to identify local communities termed microcosms this year. These algorithms all aim to a specific application and solve the corresponding problem. To settle the problem of clustering partial labeled data, Liu et al. proposed a feasible solution [49]. [16] applied multilevel to spectral clustering and proposed multilevel approximate spectral clustering method, while Nouretdinov et al. applied multilevel to conformal clustering and proposed MLCC [15]. [14] improved the synchronization clustering by using an idea of “divide and collect” and presented MLSynC. One of these algorithms improved a specific algorithm by introducing the idea of multilevel. This paper proposes a general framework that transfers cluster center from small scale to large scale, which is independent of the conventional algorithm.


## 2.1. Conventional Clustering Techniques

Han et al. suggested the following four categories for dividing clustering techniques: partitioning methods, hierarchical methods, density-based methods, and grid-based methods [24].Partitioning method assigns a dataset intok clusters such that each cluster must contain at least one element. k-means algorithm proposed by MacQueen in 1967 is the most classical representation of Partitioning method [25], and that is one of the best-known and simplest clustering algorithms [26]. Dunn developed Fuzzy c-means algorithm (FCM) for clustering data in 1973 [27]. FCM [28] allows one element to belong to two or more clusters unlike k-means where only one cluster is assigned to each element and improved by Bezdek in 1981. However, the time complexity of k-means is much less than that of FCM; thus, k-means work faster than FCM [29]. The advantages of partitioning algorithms include that they are (1) relatively scalable and simple and (2) suitable for finding spherical-shaped clusters. However, disadvantages of these algorithms include (1) the necessity for the user to specify the number of clusters in advance; (2) high sensitivity to value of initialization, noise, and outliers; and (3) failure to deal with nonconvex clusters [30].Hierarchical clustering can be divided into agglomerative method and divisive method [31]. The former follows the bottom-up strategy, which generates clusters starting with single element and then merging these small clusters into larger and larger clusters, until all of the elements are in a single cluster or otherwise until certain termination conditions are satisfied. The latter follows the top-down strategy, which breaks up cluster placed all objects into smaller and smaller clusters, until each cluster containing only one element or until certain termination conditions are satisfied. There are three forms of the agglomerative method, namely, single-linkage clustering [32], complete-linkage clustering [33], and average-linkage clustering [34]. After that, some enhanced hierarchical clustering methods are introduced, such as BIRCH [35, 36], CURE [37], ROCK [38], and CHAMELEON [39].Ester et al. demonstrated an algorithm called DBSCAN (density-based spatial clustering of applications with noise) [40], which discovers clusters of arbitrary shapes and is efficient for large spatial databases. Other well-known density-based techniques [41] are as follows: SNOB proposed by Wallace and Dowe in 1994 and MCLUST [42] introduced by Fraley and Raftery in 1998. Among these methods, the expectation-maximization (EM) algorithm is the most popular [41, 43].These methods partition the space into a finite number of cells that form a grid structure on which all of the operations for clustering are performed. The main advantage of the approach is its fast processing time [24], no need of distance computations, and easy to determine which clusters are neighbouring. There are many other interesting grid-based techniques including STING (statistical information grid approach) [44] by Wang et al. in 1997, one of the highly scalable algorithm and has the ability to decompose the dataset into various levels of detail. CLIQUE [45] is developed by Agrawal et al. in 1998, which can be considered as both density-based and grid-based clustering methods. It automatically finds subspaces of high dimensional data space that allows better clustering than original space. The accuracy of the clustering result may be degraded at the expense of simplicity of the method CLIQUE.


## 2.2. Multilevel Clustering

In recent years, the researchers introduced the idea of stratification into clustering. Psomopoulos et al. presented a multiple level clustering algorithm for detecting inter- and intragenome gene clusters, by introducing the notion of a hierarchy. This method is experimentally proven to be consistent with the phylogenetic relation and position of the genes involved [46]. Vu et al. developed a new multithreaded tool, fMLC, addressed the problem of clustering large-scale DNA sequences [12]. A multilevel clustering for star/galaxy separation was designed in 2016, consisting of three phases: coarsening clustering, representative data clustering, and merging [47]. In 2019, Zunic et al. proposed a multilevel clustering algorithm that is used on Internal Banking Payment System in a bank of Bosnia and Herzegovina and explained how the parameter effects on results and execution time in algorithm [13]. [11] presented a multilevel clustering approach that addressed the issue that conventional algorithms spent too much execution time clustering physical activity data. [48] proposed an MCT to identify local communities termed microcosms this year. These algorithms all aim to a specific application and solve the corresponding problem. To settle the problem of clustering partial labeled data, Liu et al. proposed a feasible solution [49]. [16] applied multilevel to spectral clustering and proposed multilevel approximate spectral clustering method, while Nouretdinov et al. applied multilevel to conformal clustering and proposed MLCC [15]. [14] improved the synchronization clustering by using an idea of “divide and collect” and presented MLSynC. One of these algorithms improved a specific algorithm by introducing the idea of multilevel. This paper proposes a general framework that transfers cluster center from small scale to large scale, which is independent of the conventional algorithm.


## 3. Problem Description

To facilitate the discussion in the remainder of the paper, we outline some basic concepts in this section. Formally, let a dataset ofn objects X=x1,x2,⋯,xn, xi=Ii1,Ii2,⋯,Iid∈A be a data object, and each object has d attributes denoted by A. Clustering is the process of distributing the objects in X into k clusters, c1,c2,⋯,ck, that is ci ⸦ D and ci∩cj=Ø for (1≤i,j≤k).Definition 1.
Scale partition: a set can be divided into one or more than one group by some scale, and each object has same scale value.Example 1.
There is “mod 2” scale onX, and it can divide X into Xmod2=1=x1,x3,⋯,x2m−1, and Xmod2=0=x2,x4,⋯,x2m, where m=n/2. So, scale partition of X is defined as follows: X/mod2=Xmod2=1,Xmod2=0.Definition 2.
Multiscale datasets: if there are multiple scales on a dataset, these scales have a partial order relation, denoted by “≺.” Multiscale datasets consist of multiple partitions set divided by multiple scales.Example 2.
Letπ1 be mod 4, π2 be mod 2, and π3 be mod 1; then, π1≺π2≺π3, where π1 is small scale, π3 is large scale, and π2 is small scale about to π3 and large scale about to π1. Multiscale dataset on X is X/π1,X/π2,X/π3, where X/π1= {{x1,x5,⋯,x4m−3}, x2,x6,⋯,x4m−2, {x3,x7,⋯,x4m−1}, and {x4,x8,⋯,x4m}}; X/π2= {x1,x3,⋯,x2m−1,x2,x4,⋯,x2m}; and X/π3= {x1,x2,⋯,xn}.Definition 3.
Similarity: letxi and xj be two elements of X or the cluster centers; then, the similarity between xi and xj is defined as follows:
(1)Sxi,xj=11+∑t=1Awtxit−xjt,where |A| represents for the number of attribute and is equal to d and wt is the weight of t-th attribute.Definition 4.
The estimated clusters of large scale: assume thatc1,c2,⋯, and cp are p cluster centers of small scales, 1≤i,j≤p, and satisfy Sci,cj≥δ. The objects belonged these two clusters of small scale. The cluster centers of which are named ci and cj together constitute the estimated clusters of large scale.From Figure1, k2 can be obtained by two mathematical models: (1) k2=MD2,D2=TD1, and (2) k2=Tk1, k1=MD1, where TD1 is scale partition, Tk1 is transferring knowledge from small scale, and M is mining knowledge from dataset. In multiscale data mining, MD1 is assumed to be accomplished. So, we apply the second model to mine the knowledge on large-scale dataset.


## 4. Proposed Framework

In this section, we firstly propose the framework of multiscale clustering; then, the scaling-up algorithm is designed to implement our framework; an example is given to explain our work in the end.


### 4.1. Framework

In this paper, cluster centers are used as a medium for knowledge transformation from small scales to large scales. The framework of multiscale clustering is shown in Figure2. It calculates cluster centers of large scale according to cluster centers of small scales rather than clustering on large-scale datasets repeatedly. The process is listed as follows: (1) construct multiscale datasets, (2) clustering on small-scale datasets using conventional method, (3) compute the similarity among cluster centers of small scale and construct relation matrix of cluster centers, (4) found relation the graph of cluster centers, and (5) produce connected component of the graph. In particular, it applies formula (2) to found the graph of cluster centers,
(2)mij=1ifSxi,xj≥δ0otherwise,where Sxi,xj is computing according (1).Figure 2
Overview of multiscale clustering.


### 4.2. Design

Multiscale clustering uses three algorithms to discuss its workflow. Algorithm1 and Algorithm 2 are invoked sequentially, where algorithm 2 uses Algorithm 3 to obtain the connected component. In Algorithm 1, variable lengthD and labels represent the length of original dataset D and the predicted label of small scale, where its length is lengthD (line 1). Dataset is divided into multiple scales, and the smallest scale datasets will be cluster (line 2). Then, it clusters on every partition of the scale by using conventional method; the result is cluster center list and their corresponding cluster label list (lines 3-6); in particular, the label value of listi+1 starts from the label value of listi+cluster’s number of Dssi.Algorithm 1: Clustering on small-scale dataset.
Input: Original datasetDOutput:Cluster center list (cs1, cs2, …, csp), clusters list of small scale (labels)1.lengthD←len(D), labels ←NULL2. divide data set into multiple scales, smallest scale data is represented as Dss, P is the number of data set on Dss3. for each datasetDssi do4.ci, listi ←clustering on Dssi // the label value of listi+1 starts from the label value of listi+1 + cluster’s number of Dssi5.labels ←labels + listi6. end forAlgorithm2 produces clusters of large scale. The p_centers is the combination of all cluster centers belonged small scale, and center_dic is dictionary and used to record cluster center and its corresponding cluster label list (line 1). The mapping relationship between cluster center and its clusters’ object index list is established (lines 2-9). Then, the relation matrix is computed (lines 10-12). Finally, it returns the clustering result (cluster label) of large scale, where getConnectCompont is invoked to produce new cluster by merging the close cluster of small scale (lines 13-22).Algorithm 2: Scaling-Up Cluster Centers.
Input: Cluster center list (cs1, cs2, …, csp), clusters list of small scale (labels), parameter δOutput:Clusters list of large scale (labell)1.p_centers ← cs1+ cs2 + … +csp, center_dic←NULL2. for eachi in len(p_centers) do3.index← NULL4.  for eachj in len((labels) do5.    iflabels[j]=i then6.      index.add(j)7.    end if8.center_dic[p_centers[i]] ←index9. end for10.for eachi,j in len(p_centers) do11.  computeMij according to (2)12. end for13.k←0, visitlabel[]←0, labell[]←NULL14.for eachi in len(labels) do15.  ifvisitlabel [i]=0 then16.temp←getConnectCompont (M, i)17.    for eachx in temp do18.      labell[x] ←k19.    end for20.k←k+121.  end if22.end forAlgorithm3 applies the mind of deep first search to relation matrix M and generates the cluster center list of which have close relation, and these indexes form a new cluster center of large scale.Algorithm 3: getConnectCompont.
Input:M, i: M is graph of cluster center relation, i is the point of beginningOutput:list_i: list of point connected to i1.list_i ← i2. for eachj in len(M) do3.  ifMij=1 and j not be handled then4.list_i ← j+list_i5.list_i ← list_i + getConnectCompont (M, j)6. end for


### 4.3. Analysis

In this section, we analyze execution time and memory consumption in detail. It should be noticed that the characteristic of our framework is that clustering of large scale is based on cluster center of small scale not primitive large-scale dataset. So, we need to consider Algorithm2 that needs invoke Algorithm 3. Algorithm 3 computes one point’s connected component using recursion; let m be the number of small-scale cluster center, then both the cost of its time and memory are Om. There are three main works in Algorithm 2 as follows: (1) construct the dictionary that is the relation between cluster center and the index list of data elements belonged that cluster, (2) compute the relation matrix M of small-scale cluster center, and (3) generate the clustering result of large scale. Let the number of D be n, their time complexity is Onm, Om2, and Onm, respectively, and their space complexity is On, Om2, and Om. In general, m is far less than n, so time complexity of Scaling-Up Cluster Centers is Onm, and space complexity is On that is used to construct the dictionary.


### 4.4. Case Study

This section describes the framework using the datasetD that has two scale, where D=0,2,0,1,1,2,1,1,2,3,8,9,7,8,9,9,8,8,7,9,4,4,4,5,5,6,6,5. The small scale divides D into two partitions denoted by Ds1 and Ds2, and the large scale divides D into only one partition denoted by Dl, where Ds1=0,2,0,1,1,2,1,1,2,3,8,9,7,8, Ds2=9,9,8,8,7,9,4,4,4,5,5,6,6,5, and Dl=D. Let parameter δ be 0.6. The remainder of process performs as follows:
(1)
We apply DBSCAN algorithm toDs1 and Ds2, where parameters eps and min_samples both are 2. The result of clustering is as follows: labels1=0000011, labels2=0001111, and labels=00000112223333. There are four clusters denoted by {[[0.8, 1.8]: [0, 1, 2, 3, 4]], [[7.5, 8.5]: [5, 6]], [[8.0, 8.667]: [7–9]], [[4.75, 5.0]: [10–13]]}.(2)
The similarity of four cluster centers is computed as follows:(3)1.00.0950.0910.1640.0951.00.6550.1830.0910.6551.00.1700.1640.1830.1701.0.(3)
After settingδ=0.6, the cluster centers’ relation graph is constructed. Then, we combinate the second and third cluster(4)1000011001100001.(4)
The ultimate clustering result shows the label of large scale is [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2], which is equivalent to the result that directly applies DBSCAN algorithm to the dataset of large scale and obtains, with more efficiency


## 4.1. Framework

In this paper, cluster centers are used as a medium for knowledge transformation from small scales to large scales. The framework of multiscale clustering is shown in Figure2. It calculates cluster centers of large scale according to cluster centers of small scales rather than clustering on large-scale datasets repeatedly. The process is listed as follows: (1) construct multiscale datasets, (2) clustering on small-scale datasets using conventional method, (3) compute the similarity among cluster centers of small scale and construct relation matrix of cluster centers, (4) found relation the graph of cluster centers, and (5) produce connected component of the graph. In particular, it applies formula (2) to found the graph of cluster centers,
(2)mij=1ifSxi,xj≥δ0otherwise,where Sxi,xj is computing according (1).Figure 2
Overview of multiscale clustering.


## 4.2. Design

Multiscale clustering uses three algorithms to discuss its workflow. Algorithm1 and Algorithm 2 are invoked sequentially, where algorithm 2 uses Algorithm 3 to obtain the connected component. In Algorithm 1, variable lengthD and labels represent the length of original dataset D and the predicted label of small scale, where its length is lengthD (line 1). Dataset is divided into multiple scales, and the smallest scale datasets will be cluster (line 2). Then, it clusters on every partition of the scale by using conventional method; the result is cluster center list and their corresponding cluster label list (lines 3-6); in particular, the label value of listi+1 starts from the label value of listi+cluster’s number of Dssi.Algorithm 1: Clustering on small-scale dataset.
Input: Original datasetDOutput:Cluster center list (cs1, cs2, …, csp), clusters list of small scale (labels)1.lengthD←len(D), labels ←NULL2. divide data set into multiple scales, smallest scale data is represented as Dss, P is the number of data set on Dss3. for each datasetDssi do4.ci, listi ←clustering on Dssi // the label value of listi+1 starts from the label value of listi+1 + cluster’s number of Dssi5.labels ←labels + listi6. end forAlgorithm2 produces clusters of large scale. The p_centers is the combination of all cluster centers belonged small scale, and center_dic is dictionary and used to record cluster center and its corresponding cluster label list (line 1). The mapping relationship between cluster center and its clusters’ object index list is established (lines 2-9). Then, the relation matrix is computed (lines 10-12). Finally, it returns the clustering result (cluster label) of large scale, where getConnectCompont is invoked to produce new cluster by merging the close cluster of small scale (lines 13-22).Algorithm 2: Scaling-Up Cluster Centers.
Input: Cluster center list (cs1, cs2, …, csp), clusters list of small scale (labels), parameter δOutput:Clusters list of large scale (labell)1.p_centers ← cs1+ cs2 + … +csp, center_dic←NULL2. for eachi in len(p_centers) do3.index← NULL4.  for eachj in len((labels) do5.    iflabels[j]=i then6.      index.add(j)7.    end if8.center_dic[p_centers[i]] ←index9. end for10.for eachi,j in len(p_centers) do11.  computeMij according to (2)12. end for13.k←0, visitlabel[]←0, labell[]←NULL14.for eachi in len(labels) do15.  ifvisitlabel [i]=0 then16.temp←getConnectCompont (M, i)17.    for eachx in temp do18.      labell[x] ←k19.    end for20.k←k+121.  end if22.end forAlgorithm3 applies the mind of deep first search to relation matrix M and generates the cluster center list of which have close relation, and these indexes form a new cluster center of large scale.Algorithm 3: getConnectCompont.
Input:M, i: M is graph of cluster center relation, i is the point of beginningOutput:list_i: list of point connected to i1.list_i ← i2. for eachj in len(M) do3.  ifMij=1 and j not be handled then4.list_i ← j+list_i5.list_i ← list_i + getConnectCompont (M, j)6. end for


## 4.3. Analysis

In this section, we analyze execution time and memory consumption in detail. It should be noticed that the characteristic of our framework is that clustering of large scale is based on cluster center of small scale not primitive large-scale dataset. So, we need to consider Algorithm2 that needs invoke Algorithm 3. Algorithm 3 computes one point’s connected component using recursion; let m be the number of small-scale cluster center, then both the cost of its time and memory are Om. There are three main works in Algorithm 2 as follows: (1) construct the dictionary that is the relation between cluster center and the index list of data elements belonged that cluster, (2) compute the relation matrix M of small-scale cluster center, and (3) generate the clustering result of large scale. Let the number of D be n, their time complexity is Onm, Om2, and Onm, respectively, and their space complexity is On, Om2, and Om. In general, m is far less than n, so time complexity of Scaling-Up Cluster Centers is Onm, and space complexity is On that is used to construct the dictionary.


## 4.4. Case Study

This section describes the framework using the datasetD that has two scale, where D=0,2,0,1,1,2,1,1,2,3,8,9,7,8,9,9,8,8,7,9,4,4,4,5,5,6,6,5. The small scale divides D into two partitions denoted by Ds1 and Ds2, and the large scale divides D into only one partition denoted by Dl, where Ds1=0,2,0,1,1,2,1,1,2,3,8,9,7,8, Ds2=9,9,8,8,7,9,4,4,4,5,5,6,6,5, and Dl=D. Let parameter δ be 0.6. The remainder of process performs as follows:
(1)
We apply DBSCAN algorithm toDs1 and Ds2, where parameters eps and min_samples both are 2. The result of clustering is as follows: labels1=0000011, labels2=0001111, and labels=00000112223333. There are four clusters denoted by {[[0.8, 1.8]: [0, 1, 2, 3, 4]], [[7.5, 8.5]: [5, 6]], [[8.0, 8.667]: [7–9]], [[4.75, 5.0]: [10–13]]}.(2)
The similarity of four cluster centers is computed as follows:(3)1.00.0950.0910.1640.0951.00.6550.1830.0910.6551.00.1700.1640.1830.1701.0.(3)
After settingδ=0.6, the cluster centers’ relation graph is constructed. Then, we combinate the second and third cluster(4)1000011001100001.(4)
The ultimate clustering result shows the label of large scale is [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2], which is equivalent to the result that directly applies DBSCAN algorithm to the dataset of large scale and obtains, with more efficiency


## 5. Performance Evaluations

In this section, firstly we perform conventional algorithm DBSCAN on small-scale dataset and get clustering result, then run SUCC and obtain the clustering result belonged large-scale dataset. Secondly, we evaluate the accuracy and efficiency of SUCC by comparing it with DBSCAN [40] that is classical clustering algorithm, HDBSCAN [50] and DBSCAN++ [51], which are leading algorithms in the field of clustering and performed on large-scale dataset. HDBSCAN and SUCC have been implemented with python. DBSCAN comes from sklearn library. We directly use the relevant result of DBSCAN++ but proportionally calculate the run time by DBSCAN. These programs have been performed on a computer with a Inter(R) Core (TM) i7 Dual-Core 2.8GHz CPU, 16GB RAM, and the windows 10×64 Home operating system.


### 5.1. Data Preprocessing

There are 10 real datasets in this article, as shown in Table1, where C is the number of clusters, A is the number of features, n is the number of transactions in D, and size represents dataset size. In this section, we firstly divide each dataset into two parts, then divide them into three parts. These two partitions are used two methods: the first is sequence, and the second is interval. That is to say, the first partition is dividing the data into two equal parts; one method (2A) is that the data is divide into former one second and latter one second. Another method (2B) is odd rows as the first partition and even rows as the second partition. The second method has also similar two methods (3A, 3B). It is straightforward that original data is large-scale data, and its partitions are small-scale data.Table 1
Properties of the datasets used for experimental analysis.
NONameCAnSize (KB)1Iris3415052Wine313178113Spam25746016874Images719210355PCA_MNIST102060000258036Libras15903602517Mobile42020001208Zoo71610159Seeds7192101010Letters261620000696


### 5.2. Performance Comparison

We evaluate the performance via two widely used clustering scores: the adjusted RAND index (ARI) [52] and adjusted mutual information score (AMI) [53], which are computed against the ground truth. We let min_samples be 10 for all procedures throughout experiments.Comparison result of ARI values is shown in Table2. SUCC (3A or 3B) surpasses the compared algorithms on 6 datasets, and the average ARI value of SUCC (3A or 3B) in 10 datasets is also the highest. We analyze that the distribution of 6 datasets (such as Iris and Wine) is relatively uniform, and the cluster densities among different divisions are similar, which is conducive to our algorithm. The results in Table 2 show that DBSCAN++ gives better performance compared to HDBSCAN and DBSCAN with respect to optimal parameter ε. In contrast, SUCC (2B or 3B) suffers more on PCA_MNIST, Mobile, Zoo, and Letters. The reason can be explained by that the distribution of the data divided by interval partition is quite different from that of the raw data, which causes SUCC to underperform. Therefore, our algorithm works better under the guidance of professional background.Table 2
ARI of SUCC vs. compared algorithms.
DatasetSUCCDBSCANDBSCAN++HDBSCAN2A2B3A3BIris0.7960.53210.4310.5680.6630.568Wine0.8040.4470.950.5090.2850.3690.242Spambase0.6090.5910.4570.730.2850.3690.021Images0.2390.2390.3960.3960.2920.3850.082PCA_MNIST0.1110.00001340.0960.00001720.0840.1420.026Libras0.120.120.2430.2430.0940.210.042Mobile0.0640.0030.0890.0020.0550.1740.012Zoo0.4160.0110.1220.0210.6850.7340.636Seeds0.6510.535110.4040.4990.303Letters0.0470.000014240.0190.00009670.0620.090.022Average0.3860.2480.4370.3330.2810.3640.195The AMI values of four algorithms are shown in Table3; the highest score of the row is in italic. We see that SUCC performs better than DBSCAN++ on 7 out of 10 datasets, while SUCC performs better than HDBSCAN on 9 out of 10 datasets, and SUCC performs better than DBSCAN on all datasets. It is obvious that the index AMI of algorithms is basically consistent with index ARI, except for on dataset Letters, where algorithm HDBSCAN has the best performance. An explanation of HDBSCAN has the highest score on Letters. It is not optimal that the parameter min_samples=10 in algorithms SUCC, DBSCAN, and DBSCAN++ with respect to letters, but algorithm HDBSCAN does not need this parameter.Table 3
AMI of SUCC vs. compared algorithms.
DatasetSUCCDBSCANDBSCAN++HDBSCAN2A2B3A3BIris0.7740.64410.5590.5770.730.732Wine0.7660.5260.9280.630.3590.4150.372Spambase0.5730.5460.5320.6410.3590.4150.057Images0.4440.4440.5940.5940.4940.560.264Fashion MNIST0.3091.33E-040.2941.33E-040.1740.3770.075Libras0.3730.3730.5680.5680.2170.4660.145Mobile0.2090.0040.220.0060.2120.2590.017Zoo0.4110.0170.230.010.6350.7460.633Seeds0.690.598110.440.5060.283Letters0.4012.36E-040.350.0010.3820.3960.423Average0.4950.3150.5720.4010.3840.4870.3Table4 shows the runtime (milliseconds) and standard errors for each algorithm and data. The runtime of SUCC (2A) is similar to that of SUCC (2B), while the runtime of SUCC (3A) is similar to that of SUCC (3B), so we omit the runtime of algorithm SUCC (2B) and SUCC (3B). The conclusions can be found from Table 4 as follows. At first, the runtime of SUCC on the three partitions is more than that on the two partitions with respect to every dataset. This is intuitive, because SUCC needs to merge more cluster centers belonged each partition on 3 partitions than that on 2 partitions. Then, an explanation of why SUCC spends shorter runtime clustering than compared algorithms did. SUCC deals with cluster cores belonged each division, while the compared algorithms run on raw dataset. In addition, there is no doubt that DBSCAN++ runs faster than DBSCAN and HDBSCAN on every dataset, because DBSCAN++ only computes the density estimates for a subset of the original dataset.Table 4
Runtime of SUCC vs. compared algorithms.
DatasetSUCCDBSCANDBSCAN++HDBSCAN3A2AUniformK-centerIris1.05 (±0.02)1.01 (±0.03)2.25 (±0.07)1.15 (±0.08)1.87 (±0.01)3.22 (±0.47)Wine1.07 (±0.03)1.03 (±0.11)1.87 (±0.08)1.2 (±0.07)0.72 (±0.02)5.46 (±0.18)Spambase25.2 (±1.8)22.5 (±1.31)375 (±25.8)25.6 (±0.93)50.2 (±0.13)360 (±25.8)Images0.45 (±0.01)0.43 (±0.02)1.97 (±0.08)0.61 (±0.04)0.53 (±0.03)1.57 (±0.01)Fashion MNIST46.7 (±2.23)41.2 (±2.31)2346 (±57.3)54.74 (±5.71)110 (±5.5)12346 (±99.3)Libras6.58 (±0.19)5.66 (±0.48)36.58 (±0.48)7.97 (±0.17)9.6 (±0.21)42.4 (±6.48)Mobile7.11 (±0.07)5.89 (±0.12)48.11 (±0.37)8.19 (±0.11)10.93 (±0.11)200.7 (±3.7)Zoo0.89 (±0.03)0.88 (±0.02)1.41 (±0.08)1.03 (±0.03)1.07 (±0.01)4.88 (±0.18)Seeds0.78 (±0.04)0.68 (±0.04)1.56 (±0.07)0.81 (±0.02)0.86 (±0.02)5.73 (±0.07)Letters26.8 (±3.55)23.5 (±1.15)1296 (±37.5)67.39 (±6.97)19.5 (±0.71)14711 (±49.5)


### 5.3. Robustness to Hyperparameterp

In this section, clustering on small-scale dataset is performed firstly by DBSCAN in 6 datasets in which SUCC is dominant, where parametermin_samples is fixed 10 and eps is between 10 and 50, with interval of 4. Then, we adjust the parameter p from 0.01 to 1 and generate the clustering results of large-scale data by using the cluster cores belonged small-scale datasets and p. The clustering indexes are shown in Figures 3–8 on 6 datasets. On the whole, the clustering results of large-scale data are correlated with parameter p, except for Wine and Images. This explains the reason that the distribution of these two datasets is particularly uniform, or the data distribution is consistent with data partition method. In addition, the clustering result is greatly affected by the value of p on some datasets, such as Libras. Therefore, we declare that the result of SUCC is more guaranteed under the guidance of experts.Figure 3
ARI and AMI on Iris.Figure 4
ARI and AMI on Wine.Figure 5
ARI and AMI on Spasebase.Figure 6
ARI and AMI on Images.Figure 7
ARI and AMI on Libras.Figure 8
ARI and AMI on Seeds.


## 5.1. Data Preprocessing

There are 10 real datasets in this article, as shown in Table1, where C is the number of clusters, A is the number of features, n is the number of transactions in D, and size represents dataset size. In this section, we firstly divide each dataset into two parts, then divide them into three parts. These two partitions are used two methods: the first is sequence, and the second is interval. That is to say, the first partition is dividing the data into two equal parts; one method (2A) is that the data is divide into former one second and latter one second. Another method (2B) is odd rows as the first partition and even rows as the second partition. The second method has also similar two methods (3A, 3B). It is straightforward that original data is large-scale data, and its partitions are small-scale data.Table 1
Properties of the datasets used for experimental analysis.
NONameCAnSize (KB)1Iris3415052Wine313178113Spam25746016874Images719210355PCA_MNIST102060000258036Libras15903602517Mobile42020001208Zoo71610159Seeds7192101010Letters261620000696


## 5.2. Performance Comparison

We evaluate the performance via two widely used clustering scores: the adjusted RAND index (ARI) [52] and adjusted mutual information score (AMI) [53], which are computed against the ground truth. We let min_samples be 10 for all procedures throughout experiments.Comparison result of ARI values is shown in Table2. SUCC (3A or 3B) surpasses the compared algorithms on 6 datasets, and the average ARI value of SUCC (3A or 3B) in 10 datasets is also the highest. We analyze that the distribution of 6 datasets (such as Iris and Wine) is relatively uniform, and the cluster densities among different divisions are similar, which is conducive to our algorithm. The results in Table 2 show that DBSCAN++ gives better performance compared to HDBSCAN and DBSCAN with respect to optimal parameter ε. In contrast, SUCC (2B or 3B) suffers more on PCA_MNIST, Mobile, Zoo, and Letters. The reason can be explained by that the distribution of the data divided by interval partition is quite different from that of the raw data, which causes SUCC to underperform. Therefore, our algorithm works better under the guidance of professional background.Table 2
ARI of SUCC vs. compared algorithms.
DatasetSUCCDBSCANDBSCAN++HDBSCAN2A2B3A3BIris0.7960.53210.4310.5680.6630.568Wine0.8040.4470.950.5090.2850.3690.242Spambase0.6090.5910.4570.730.2850.3690.021Images0.2390.2390.3960.3960.2920.3850.082PCA_MNIST0.1110.00001340.0960.00001720.0840.1420.026Libras0.120.120.2430.2430.0940.210.042Mobile0.0640.0030.0890.0020.0550.1740.012Zoo0.4160.0110.1220.0210.6850.7340.636Seeds0.6510.535110.4040.4990.303Letters0.0470.000014240.0190.00009670.0620.090.022Average0.3860.2480.4370.3330.2810.3640.195The AMI values of four algorithms are shown in Table3; the highest score of the row is in italic. We see that SUCC performs better than DBSCAN++ on 7 out of 10 datasets, while SUCC performs better than HDBSCAN on 9 out of 10 datasets, and SUCC performs better than DBSCAN on all datasets. It is obvious that the index AMI of algorithms is basically consistent with index ARI, except for on dataset Letters, where algorithm HDBSCAN has the best performance. An explanation of HDBSCAN has the highest score on Letters. It is not optimal that the parameter min_samples=10 in algorithms SUCC, DBSCAN, and DBSCAN++ with respect to letters, but algorithm HDBSCAN does not need this parameter.Table 3
AMI of SUCC vs. compared algorithms.
DatasetSUCCDBSCANDBSCAN++HDBSCAN2A2B3A3BIris0.7740.64410.5590.5770.730.732Wine0.7660.5260.9280.630.3590.4150.372Spambase0.5730.5460.5320.6410.3590.4150.057Images0.4440.4440.5940.5940.4940.560.264Fashion MNIST0.3091.33E-040.2941.33E-040.1740.3770.075Libras0.3730.3730.5680.5680.2170.4660.145Mobile0.2090.0040.220.0060.2120.2590.017Zoo0.4110.0170.230.010.6350.7460.633Seeds0.690.598110.440.5060.283Letters0.4012.36E-040.350.0010.3820.3960.423Average0.4950.3150.5720.4010.3840.4870.3Table4 shows the runtime (milliseconds) and standard errors for each algorithm and data. The runtime of SUCC (2A) is similar to that of SUCC (2B), while the runtime of SUCC (3A) is similar to that of SUCC (3B), so we omit the runtime of algorithm SUCC (2B) and SUCC (3B). The conclusions can be found from Table 4 as follows. At first, the runtime of SUCC on the three partitions is more than that on the two partitions with respect to every dataset. This is intuitive, because SUCC needs to merge more cluster centers belonged each partition on 3 partitions than that on 2 partitions. Then, an explanation of why SUCC spends shorter runtime clustering than compared algorithms did. SUCC deals with cluster cores belonged each division, while the compared algorithms run on raw dataset. In addition, there is no doubt that DBSCAN++ runs faster than DBSCAN and HDBSCAN on every dataset, because DBSCAN++ only computes the density estimates for a subset of the original dataset.Table 4
Runtime of SUCC vs. compared algorithms.
DatasetSUCCDBSCANDBSCAN++HDBSCAN3A2AUniformK-centerIris1.05 (±0.02)1.01 (±0.03)2.25 (±0.07)1.15 (±0.08)1.87 (±0.01)3.22 (±0.47)Wine1.07 (±0.03)1.03 (±0.11)1.87 (±0.08)1.2 (±0.07)0.72 (±0.02)5.46 (±0.18)Spambase25.2 (±1.8)22.5 (±1.31)375 (±25.8)25.6 (±0.93)50.2 (±0.13)360 (±25.8)Images0.45 (±0.01)0.43 (±0.02)1.97 (±0.08)0.61 (±0.04)0.53 (±0.03)1.57 (±0.01)Fashion MNIST46.7 (±2.23)41.2 (±2.31)2346 (±57.3)54.74 (±5.71)110 (±5.5)12346 (±99.3)Libras6.58 (±0.19)5.66 (±0.48)36.58 (±0.48)7.97 (±0.17)9.6 (±0.21)42.4 (±6.48)Mobile7.11 (±0.07)5.89 (±0.12)48.11 (±0.37)8.19 (±0.11)10.93 (±0.11)200.7 (±3.7)Zoo0.89 (±0.03)0.88 (±0.02)1.41 (±0.08)1.03 (±0.03)1.07 (±0.01)4.88 (±0.18)Seeds0.78 (±0.04)0.68 (±0.04)1.56 (±0.07)0.81 (±0.02)0.86 (±0.02)5.73 (±0.07)Letters26.8 (±3.55)23.5 (±1.15)1296 (±37.5)67.39 (±6.97)19.5 (±0.71)14711 (±49.5)


## 5.3. Robustness to Hyperparameterp

In this section, clustering on small-scale dataset is performed firstly by DBSCAN in 6 datasets in which SUCC is dominant, where parametermin_samples is fixed 10 and eps is between 10 and 50, with interval of 4. Then, we adjust the parameter p from 0.01 to 1 and generate the clustering results of large-scale data by using the cluster cores belonged small-scale datasets and p. The clustering indexes are shown in Figures 3–8 on 6 datasets. On the whole, the clustering results of large-scale data are correlated with parameter p, except for Wine and Images. This explains the reason that the distribution of these two datasets is particularly uniform, or the data distribution is consistent with data partition method. In addition, the clustering result is greatly affected by the value of p on some datasets, such as Libras. Therefore, we declare that the result of SUCC is more guaranteed under the guidance of experts.Figure 3
ARI and AMI on Iris.Figure 4
ARI and AMI on Wine.Figure 5
ARI and AMI on Spasebase.Figure 6
ARI and AMI on Images.Figure 7
ARI and AMI on Libras.Figure 8
ARI and AMI on Seeds.


## 6. Conclusions

In this study, we focus on multiscale clustering and propose an approach SUCC that generates clusters belonged large-scale data, which just needs to merge the cluster cores belonged small-scale data, not the raw dataset. In general, the size of cluster cores belonged small-scale data is much smaller than that of the original data, so SUCC needs smaller time overhead. The experimental results show that algorithm SUCC is efficient and effective on the dataset whose distribution is uniform. SUCC can perform better if that is under expert guidance in practice.In future work, we mainly focus on the practical application of our study; we will consider applying multiscale clustering to radio-frequency identification [54, 55], collision detection [56–59], time series analysis [60–62], brain-computer interface [63–67], and scheduling [68, 69] based on previous researches.



---

*Source: 4071177-2021-08-01.xml*