# Spectral Clustering Algorithm Based on Improved Gaussian Kernel Function and Beetle Antennae Search with Damping Factor

Authors: Zhe Zhang; Xiyu Liu; Lin Wang
Journal: Computational Intelligence and Neuroscience
 (2020)

---

## Abstract

There are two problems in the traditional spectral clustering algorithm. Firstly, when it uses Gaussian kernel function to construct the similarity matrix, different scale parameters in Gaussian kernel function will lead to different results of the algorithm. Secondly, K-means algorithm is often used in the clustering stage of the spectral clustering algorithm. It needs to initialize the cluster center randomly, which will result in the instability of the results. In this paper, an improved spectral clustering algorithm is proposed to solve these two problems. In constructing a similarity matrix, we proposed an improved Gaussian kernel function, which is based on the distance information of some nearest neighbors and can adaptively select scale parameters. In the clustering stage, beetle antennae search algorithm with damping factor is proposed to complete the clustering to overcome the problem of instability of the clustering results. In the experiment, we use four artificial data sets and seven UCI data sets to verify the performance of our algorithm. In addition, four images in BSDS500 image data sets are segmented in this paper, and the results show that our algorithm is better than other comparison algorithms in image segmentation.


---

## Body

## 1. Introduction

Clustering analysis is an important research problem in the field of data mining. The purpose of clustering is to divide the data set into different clusters according to the intrinsic structure and relationship between the data so that the similarity between data points within the same cluster is higher, and the similarity between data points in different clusters is lower. The main clustering methods include partitioning-based clustering, hierarchical clustering, density-based clustering, grid-based clustering, and graph theory-based clustering. Different clustering algorithms are also applied to different fields, such as image segmentation [1–4], text clustering [5, 6], and community division [7–9].Spectral clustering is a kind of clustering algorithm based on graph theory. By spectral graph partition theory [10], the clustering problem of the data set is transformed into the graph partition problem. In spectral clustering, each data point is regarded as the vertex of the graph, and the similarity between data points is regarded as the weight of the edge. By dividing the graph, the sum of the weight of the edge in the subgraph is as high as possible, and the sum of the weight of the edge between different subgraphs is as low as possible.In 1973, Donath and Hoffman [10] first proposed the concept of graph partition based on the adjacency matrix, marking the formal birth of spectral clustering. In the same year, Fiedler [11] found that the two-way partition of the undirected graph is closely related to the eigenvector corresponding to the second small eigenvalue of the corresponding Laplacian matrix, which provides a new way to solve the problem of graph partition. In 2000, Shi and Malik [12] put forward the standard cut objective function, also known as the N-cut criterion, based on the spectral theory. In 2001, Ding et al. [13] put forward the minimum and maximum cut-set criterion based on N-cut, which balances the two requirements of minimum division loss and maximum vertex number of subgraphs, making division more inclined to balance the cut set and avoiding segmentation of smaller subgraphs with only a few vertices. In 2002, Jordan, Weiss, and Ng [14] proposed NJW algorithm, which is different from two-way division. The algorithm is based on k-way division, and it is also the most widely used spectral clustering algorithm so far. Despite the good development of spectral clustering, there are still some problems with the algorithm itself, such as how to select the scale parameters in the Gaussian kernel function. In 2004, scholars [15] have proved that the selection of scale parameters will affect the clustering results. To solve this problem, Zhang et al. [16] proposed a construction method of the similarity matrix based on local density. Nataliani and Yang [17] proposed an energy Gaussian kernel function to solve this problem.Beetle antennae search algorithm (BAS) is an optimization algorithm inspired by the beetle’s foraging principle proposed by Jiang and Li [18] in 2017. By simulating the detection function of beetle’s tentacles and the mechanism of beetle’s random walking, an optimization mechanism similar to beetle’s foraging process is realized. According to the smell of food, the moving direction of the beetle is determined. When the smell of the left tentacle is strong, it will move to the left; otherwise, it will move to the right. Through the random orientation mechanism and variable step size mechanism, a beetle can search in the global scope. Compared with other intelligent algorithms, the algorithm does not need to know the specific form of gradient information and function and has the advantages of fast convergence speed and low requirements for parameters. So, it has been applied in some fields. Wang and Liu [19] combined the reverse neural network with the BAS algorithm to predict the loss of storm disaster. Chen et al. [20] used the particle swarm optimization algorithm based on the BAS algorithm to solve the portfolio model. Wang and Chen [21] proposed a kind of bee swarm antenna search algorithm (BSAS).The main contributions of this paper are as follows: (1) A construction method of the similarity matrix is proposed, which uses the distance information of some nearest neighbors to define the scale parameterσ to overcome the influence of artificial designated scale parameter σ on the results. (2) In the clustering stage, we use the proposed beetle antennae search algorithm with damping factor (DBAS) to complete the clustering. Through such an intelligent optimization algorithm, we can overcome the impact of random initialization of the cluster center on the results when K-means is used in the traditional spectrum clustering. And the damping factor overcomes the oscillation in the iterative process and improves the stability of the algorithm.The content of this paper is organized as follows. In Section3, an improved spectral clustering algorithm based on the distance information of some nearest neighbors and beetle antennae search algorithm with damping factor is proposed. Section 4 shows the performance of the algorithm through experimental analysis. The conclusion will be presented in Section 5.


## 2. Spectral Clustering and Beetle Antennae Search Algorithm

### 2.1. Spectral Clustering

The spectral clustering algorithm uses the eigenvectors of the Laplacian matrix corresponding to the data set to cluster. In the spectral clustering algorithm, firstly, an undirected graphG=V,E is constructed according to the data points. Each vertex vi on the graph corresponds to a data point, and the weight wij on the edge is the similarity between the data points. In general, we use Gaussian kernel function to construct the similar matrix. Then, we can get a degree matrix D,dii=∑j=1nwij, whose main diagonal element is equal to the sum of the row elements corresponding to the similar matrix. There are usually three ways to construct the Laplacian matrix L: (1) denormalized Laplacian matrix, (2) normalized symmetric Laplacian matrix L=I−D−1/2WD−1/2, and (3) normalized asymmetric Laplacian matrix L=D−1WD−1. The eigenvector e1e2…ek corresponding to the first k eigenvalues of the Laplace matrix can be calculated and set U=e1e2…ek. Then, a new feature matrix F is obtained by normalizing U. Each row in the feature matrix F is regarded as a sample, which is clustered to obtain a group of clusters C1,C2,…,Ck. NJW algorithm [14] is the most commonly used spectral clustering algorithm. The basic step of the NJW algorithm is shown in Algorithm 1.


### 2.2. Beetle Antennae Search Algorithm (BAS)

Based on the principle of beetle’s foraging, three optimization strategies can be simplified: (1) The left and right antennae of the beetle are located on both sides of the individual. (2) The ratio of the step length of each action to the distance between two antennae is a fixed constant. (3) After a move, the direction of its head is random. Then, we can build an optimization model (the beetle is simplified as an individual):(1)
For an optimization problem in then-dimensional space, xl is used to represent the coordinates of the left antennae of an individual, xr represent the coordinates of the right antennae of an individual, and x is the centroid coordinate. D0 is the distance between two antennae. Since the orientation of the individual is random after each movement, the direction of the vector that the right of the individual points to the left is also random. It can be expressed by a normalized random vector dir=dir/normrandsn,1. There is xl−xr=D0∗dir.(2)
For the minimization objective functionfx, fleft=fxl and fright=fxr. If fleft is less than fright, then the individual travels in the direction of the left antennae step, otherwise, the distance step of the individual toward the right antennae direction.(1)x=x−step∗normalxl−xr∗signfleft−fright.(3)
Repeat step 1 and step 2 until the maximum number of iterations is reached or the individual does not change inM iterations.


## 2.1. Spectral Clustering

The spectral clustering algorithm uses the eigenvectors of the Laplacian matrix corresponding to the data set to cluster. In the spectral clustering algorithm, firstly, an undirected graphG=V,E is constructed according to the data points. Each vertex vi on the graph corresponds to a data point, and the weight wij on the edge is the similarity between the data points. In general, we use Gaussian kernel function to construct the similar matrix. Then, we can get a degree matrix D,dii=∑j=1nwij, whose main diagonal element is equal to the sum of the row elements corresponding to the similar matrix. There are usually three ways to construct the Laplacian matrix L: (1) denormalized Laplacian matrix, (2) normalized symmetric Laplacian matrix L=I−D−1/2WD−1/2, and (3) normalized asymmetric Laplacian matrix L=D−1WD−1. The eigenvector e1e2…ek corresponding to the first k eigenvalues of the Laplace matrix can be calculated and set U=e1e2…ek. Then, a new feature matrix F is obtained by normalizing U. Each row in the feature matrix F is regarded as a sample, which is clustered to obtain a group of clusters C1,C2,…,Ck. NJW algorithm [14] is the most commonly used spectral clustering algorithm. The basic step of the NJW algorithm is shown in Algorithm 1.


## 2.2. Beetle Antennae Search Algorithm (BAS)

Based on the principle of beetle’s foraging, three optimization strategies can be simplified: (1) The left and right antennae of the beetle are located on both sides of the individual. (2) The ratio of the step length of each action to the distance between two antennae is a fixed constant. (3) After a move, the direction of its head is random. Then, we can build an optimization model (the beetle is simplified as an individual):(1)
For an optimization problem in then-dimensional space, xl is used to represent the coordinates of the left antennae of an individual, xr represent the coordinates of the right antennae of an individual, and x is the centroid coordinate. D0 is the distance between two antennae. Since the orientation of the individual is random after each movement, the direction of the vector that the right of the individual points to the left is also random. It can be expressed by a normalized random vector dir=dir/normrandsn,1. There is xl−xr=D0∗dir.(2)
For the minimization objective functionfx, fleft=fxl and fright=fxr. If fleft is less than fright, then the individual travels in the direction of the left antennae step, otherwise, the distance step of the individual toward the right antennae direction.(1)x=x−step∗normalxl−xr∗signfleft−fright.(3)
Repeat step 1 and step 2 until the maximum number of iterations is reached or the individual does not change inM iterations.


## 3. Improved Spectral Clustering Algorithm

In this section, we improve Gaussian kernel function and BAS algorithm, respectively. After using the new Gaussian kernel function to construct the similarity matrix, we use the spectral clustering algorithm to get a new feature matrix, and then, we use the improved BAS algorithm to cluster.


### 3.1. An Improved Gaussian Kernel Function

In the traditional spectral clustering, the similarity matrix is usually constructed according to the Gaussian kernel function in the formula of Algorithm1, where σ is the scale parameter; in general, the scale parameter σ is selected artificially. In 2004, scholars [15] had proved that the selection of scale parameters will affect the clustering results. In order to solve this problem, this paper proposes a method of constructing a similarity matrix based on the distance information of some nearest neighbors:(2)wij=exp−xi−xj2σiσj,where σi=1/g∑j=1gdistxi,xj, which is the mean distance of the nearest g points from point i. g is the ratio of the total number of samples to the square of the number of clusters. g=N/k2, where N is the total number of samples and k is the number of clusters.Algorithm 1: NJW algorithm.
Step 1: use the Gaussian kernel function to construct the similar matrixW. wij=exp−xi−xj2/2σ2.Step 2: degree matrixD,dii=∑j=1nwij.Step 3: construct a normalized symmetric Laplacian matrixL=I−D−1/2WD−1/2.Step 4: calculate the feature vectorv corresponding to the first k eigenvalues of L, and construct the feature matrix U.Step 5: normalize the feature matrixU to obtain a normalized matrix Y, which contains n points in space reduced to k dimensions.Step 6: treat each row ofY as a point, and cluster them by K-means algorithm.


### 3.2. Beetle Antennae Search Algorithm with Damping Factor (DBAS)

As mentioned in Section2.2, the direction of the individual is random in each iteration. This results in more oscillations in the process of algorithm iteration. It is possible that the result of the M + 1 iteration is worse than that of the M iteration many times. We proposed to add a damping factor to the formula of the position update of the individual, which updates the position information by using the results of this iteration and the last iteration. The formula is described as(3)xt+1=xt+1∗1−damp+xt∗damp,where xt indicates the position in the t − 1th iteration, damp∈0.5,1.We use the algorithm with damping factor and the algorithm without damping factor to experiment on the Iris data set. Figure1 shows that adding damping factor to the algorithm can effectively overcome the oscillation problem in the iterative process.Figure 1
Iterative results of BAS with or without damping factor in the Iris data set. (a) BAS. (b) BAS with damping factor.
(a)(b)


### 3.3. SC-DBAS Algorithm

Firstly, we use the Gaussian kernel function based on the distance information of some nearest neighbors (formula2) to construct the similarity matrix and then calculate the corresponding degree matrix and Laplace matrix. We select the eigenvectors corresponding to the first k minimum eigenvalues of the Laplace matrix to construct an eigenmatrix and then normalize it to get a new eigenmatrix. Each row of the matrix is regarded as a sample point. For such a new data set, we randomly initialize a group of cluster centers as an individual and then use DBAS algorithm to cluster. SC-DBAS algorithm flow is given in Algorithm 2.Algorithm 2: SC-DBAS algorithm.
Input: data set X, number of clusters K, number of iterations of DBAS algorithm NStep 1: construct similarity matrix,wij=exp−xi−xj2/σiσjStep 2: construct the degree matrixD,dii=∑j=1nwijStep 3: construct Laplace matrixL=I−D−1/2WD−1/2Step 4: calculate the eigenvectore1e2…ek corresponding to the first k minimum eigenvalues of the Laplace matrix which forms the eigenmatrix UStep 5: normalize the feature matrixU to get a new feature matrix FStep 6: treat each row of the feature matrixF as a data point, and randomly initialize a group of cluster centers as an individualStep 7: randomly initialize a group of cluster centers as an individualStep 8: calculate the fitness of the right antennaefright and the left antennae fleft of the current individual, where f=min∑1K∑∀xi∈CKxi−μk2Step 9: update individual location informationxt=xt−step∗normalxt_l−xt_r∗signft_left−ft_light, xt+1=xt+1∗1−damp+xt∗dampStep 10: repeat steps 8 and 9 until the maximum number of iterations is reachedStep 11: according to the cluster center corresponding to the last individual position, the clusterC1C2…Ck is obtainedOutput:C1C2…Ck


### 3.4. Computational Complexity

The computational complexity of the proposed algorithm can be calculated as follows: the SC-DBAS algorithm is divided into three parts: (1) constructing a similar graph, which needsOn2, (2) eigenvalue decomposition, which needs On3, and (3) clustering by using DBAS algorithm, which needs Onkl, where k is the number of cluster centers and l is the number of iterations. According to the notation of big O, the computational complexity of the proposed algorithm is On3.


## 3.1. An Improved Gaussian Kernel Function

In the traditional spectral clustering, the similarity matrix is usually constructed according to the Gaussian kernel function in the formula of Algorithm1, where σ is the scale parameter; in general, the scale parameter σ is selected artificially. In 2004, scholars [15] had proved that the selection of scale parameters will affect the clustering results. In order to solve this problem, this paper proposes a method of constructing a similarity matrix based on the distance information of some nearest neighbors:(2)wij=exp−xi−xj2σiσj,where σi=1/g∑j=1gdistxi,xj, which is the mean distance of the nearest g points from point i. g is the ratio of the total number of samples to the square of the number of clusters. g=N/k2, where N is the total number of samples and k is the number of clusters.Algorithm 1: NJW algorithm.
Step 1: use the Gaussian kernel function to construct the similar matrixW. wij=exp−xi−xj2/2σ2.Step 2: degree matrixD,dii=∑j=1nwij.Step 3: construct a normalized symmetric Laplacian matrixL=I−D−1/2WD−1/2.Step 4: calculate the feature vectorv corresponding to the first k eigenvalues of L, and construct the feature matrix U.Step 5: normalize the feature matrixU to obtain a normalized matrix Y, which contains n points in space reduced to k dimensions.Step 6: treat each row ofY as a point, and cluster them by K-means algorithm.


## 3.2. Beetle Antennae Search Algorithm with Damping Factor (DBAS)

As mentioned in Section2.2, the direction of the individual is random in each iteration. This results in more oscillations in the process of algorithm iteration. It is possible that the result of the M + 1 iteration is worse than that of the M iteration many times. We proposed to add a damping factor to the formula of the position update of the individual, which updates the position information by using the results of this iteration and the last iteration. The formula is described as(3)xt+1=xt+1∗1−damp+xt∗damp,where xt indicates the position in the t − 1th iteration, damp∈0.5,1.We use the algorithm with damping factor and the algorithm without damping factor to experiment on the Iris data set. Figure1 shows that adding damping factor to the algorithm can effectively overcome the oscillation problem in the iterative process.Figure 1
Iterative results of BAS with or without damping factor in the Iris data set. (a) BAS. (b) BAS with damping factor.
(a)(b)


## 3.3. SC-DBAS Algorithm

Firstly, we use the Gaussian kernel function based on the distance information of some nearest neighbors (formula2) to construct the similarity matrix and then calculate the corresponding degree matrix and Laplace matrix. We select the eigenvectors corresponding to the first k minimum eigenvalues of the Laplace matrix to construct an eigenmatrix and then normalize it to get a new eigenmatrix. Each row of the matrix is regarded as a sample point. For such a new data set, we randomly initialize a group of cluster centers as an individual and then use DBAS algorithm to cluster. SC-DBAS algorithm flow is given in Algorithm 2.Algorithm 2: SC-DBAS algorithm.
Input: data set X, number of clusters K, number of iterations of DBAS algorithm NStep 1: construct similarity matrix,wij=exp−xi−xj2/σiσjStep 2: construct the degree matrixD,dii=∑j=1nwijStep 3: construct Laplace matrixL=I−D−1/2WD−1/2Step 4: calculate the eigenvectore1e2…ek corresponding to the first k minimum eigenvalues of the Laplace matrix which forms the eigenmatrix UStep 5: normalize the feature matrixU to get a new feature matrix FStep 6: treat each row of the feature matrixF as a data point, and randomly initialize a group of cluster centers as an individualStep 7: randomly initialize a group of cluster centers as an individualStep 8: calculate the fitness of the right antennaefright and the left antennae fleft of the current individual, where f=min∑1K∑∀xi∈CKxi−μk2Step 9: update individual location informationxt=xt−step∗normalxt_l−xt_r∗signft_left−ft_light, xt+1=xt+1∗1−damp+xt∗dampStep 10: repeat steps 8 and 9 until the maximum number of iterations is reachedStep 11: according to the cluster center corresponding to the last individual position, the clusterC1C2…Ck is obtainedOutput:C1C2…Ck


## 3.4. Computational Complexity

The computational complexity of the proposed algorithm can be calculated as follows: the SC-DBAS algorithm is divided into three parts: (1) constructing a similar graph, which needsOn2, (2) eigenvalue decomposition, which needs On3, and (3) clustering by using DBAS algorithm, which needs Onkl, where k is the number of cluster centers and l is the number of iterations. According to the notation of big O, the computational complexity of the proposed algorithm is On3.


## 4. Experimental Results and Analysis

### 4.1. Experimental Setting

All the experiments are conducted on the computer with Intel core i5-3230M CPU, 8 GB RAM. The experiment environment is Matlab 2016b. In the experiment, we compare the proposed algorithm with the K-means, NJW [14], MPSC algorithm [22], PGSC algorithm [17], and SC-NP algorithm [23] on four artificial data sets and seven UCI data sets. The proposed algorithm will also use the image in the BSDS500 data set for image segmentation. In the experimental part of image segmentation, the comparison algorithm is K-means, NJW [14], PGSC algorithm [17], and SC-NP algorithm [23].In the experiment, the parameters are set as follows: step = 0.1; step adjustment factor eta = 0.95; the ratio between step andD0 is 5; the number of iterations n = 100; and damp = 0.5. The information of data sets is shown in Table 1.Table 1
Data set information.
Data setObjectsAttributesClassesSourceIris15043UCIWine178133UCISeeds21063UCIZoo101167UCIGlass214106UCISonar208602UCIIonosphere351342UCISpiral94422ArtificialTwo moons200022ArtificialThree circles360323ArtificialZigzag100223Artificial


### 4.2. Evaluation Indicators

In the experiment, we use four indicators to evaluate the clustering results: accuracy, ARI, F1 score, and time (s).(1)
Accuracy rate: the accuracy rate represents the proportion of the number of correct clustering samples to the total number of samples, whereV is the division label and U is the real label:(4)Acc=1N∑i=1kmaxjvi∩uj,(2)
ARI: there are four cases by comparing the calculation resultsV with the real label U. SS contains sample pairs that belong to the same cluster in V and the same cluster in U. SD contains sample pairs that belong to the same cluster in V but not the same cluster in U. DS contains sample pairs that do not belong to the same cluster in V but belong to the same cluster in U. DD contains sample pairs that do not belong to the same cluster in V and do not belong to the same cluster in U. Set SS=a,SD=b,DS=c,DD=d; there are(5)ARI=2ad−bca+bb+d+a+cc+d.The larger the value of ARI means that the clustering results are more consistent with the real situation.(3)
F1 score: F1 score is one of the commonly used evaluation criteria in information retrieval. It is a weighted harmonic mean value based on precision and recall. Its definition is as follows, wherea, b, and c have been defined in the above content:(6)F1=2∗P∗RP+R,P=aa+b,R=aa+c.(4)
Time: in this paper, we use the average time of each algorithm running 100 times as the evaluation index.


### 4.3. Data Set Experiment Result Analysis

#### 4.3.1. Experimental Results of Artificial Data Sets

Table2 shows the experimental results of the six algorithms on the four artificial data sets. From Figure 2, we can see that our proposed algorithm can well divide the data sets of various structures.Table 2
Accuracy of six algorithms on artificial data sets.
Data setK-meansNJWMPSCPGSCSC-NPSC-DBASSpiral0.59751110.58901Two moons0.73371110.71701Three circles0.55541110.57531Zigzag0.70761110.72751Figure 2
Clustering results using the proposed algorithm for artificial data sets. (a) Spiral. (b) Three circles. (c) Two moons. (d) Zigzag.
(a)(b)(c)(d)


#### 4.3.2. Experimental Results of UCI Data Sets

Table3 and Figure 3 show the experimental results of the six algorithms on seven UCI data sets. By comparing the results, we can see that the algorithm proposed in this paper performs better than the other five algorithms and has a shorter running time.Table 3
Results of six algorithms on UCI data sets.
Data setEvaluation indicatorsK-meansNJWMPSCPGSCSC-NPSC-DBASIrisAccuracy0.89330.89330.90670.90000.89330.9600ARI0.55160.68500.75830.88590.87970.9195F1 score0.89180.89880.90570.89880.89180.9332Time (s)0.26100.51640.58800.06690.78410.0553WineAccuracy0.65300.67420.55050.60670.69100.7247ARI0.79430.89860.93100.56140.69380.7395F1 score0.63630.62760.60570.65100.65310.7302Time (s)0.22060.48450.40200.04430.96870.0638SeedsAccuracy0.70080.79050.71940.88100.89050.9000ARI0.70060.70220.68650.85940.86810.8787F1 score0.88970.81500.89140.88130.89130.9092Time (s)0.21950.48930.46410.04031.03810.0641ZooAccuracy0.65340.63370.81190.87130.84160.8713ARI0.63590.74410.77580.89620.89940.9012F1 score0.63190.80380.83890.81900.80450.8540Time (s)0.25610.50350.28440.05550.95380.0608GlassAccuracy0.79130.65420.81310.78970.88320.8598ARI0.73750.57180.77670.82060.85520.8817F1 score0.68120.55150.68720.75090.69730.7364Time (s)0.24180.43350.55470.05120.97100.0712SonarAccuracy0.39420.37010.43460.53850.53370.5721ARI0.08270.00220.13240.50060.49990.5080F1 score0.46230.61190.55560.53700.55930.5716Time (s)0.24220.59500.41810.05871.64580.0794IonosphereAccuracy0.35890.61820.70940.64100.64100.7379ARI0.32400.42370.47720.49890.52530.6121F1 score0.41490.68850.69020.61880.68170.7431Time (s)0.21051.0110.8920.13542.86060.1108Figure 3
Results of six algorithms on UCI data sets. (a) Accuracy. (b) ARI. (c) F1 score. (d) Time (s).
(a)(b)(c)(d)


### 4.4. Application of the SC-DBAS Algorithm to Image Segmentation

Clustering-based image segmentation is based on the similarity between image pixels; through some clustering algorithms, the pixels are divided into different clusters so as to complete the segmentation of the original image.In this section, we segment some images of the BSDS500 data set. For a 481∗321 pixels image, if we treat each pixel as a data point, there will be 154,401 data points. Therefore, in order to reduce the scale of data points, we first use SLIC algorithm [24] to perform presegmentation (superpixel segmentation) on the image. Each superpixel is an oversegmented region and is considered as a data point. Then, the proposed algorithm is used to segment the image. In the experiment, the number of superpixels of each image is 200. The comparison algorithm used in the experiment is K-means, NJW [14], PGSC algorithm [17], and SC-NP algorithm [23]. Then, we can get the results which are given in Figure 4.Figure 4
(a) Original image, (b) K-means, (c) NJW, (d) PGSC, (e) SC-NP, and (f) our proposed algorithm.From the experimental results, we can see that our algorithm can segment the object and the background better, while the other four comparison algorithms will have the wrong segmentation area. The segmentation accuracy results are shown in Table4.Table 4
Accuracy of five algorithms on images.
K-meansNJWPGSCSC-NPSC-DBASImage 10.88040.94830.94830.93040.9943Image 20.55620.55620.53470.99420.9969Image 30.95200.96960.97290.97220.9741Image 40.99020.98830.99200.99170.9924


## 4.1. Experimental Setting

All the experiments are conducted on the computer with Intel core i5-3230M CPU, 8 GB RAM. The experiment environment is Matlab 2016b. In the experiment, we compare the proposed algorithm with the K-means, NJW [14], MPSC algorithm [22], PGSC algorithm [17], and SC-NP algorithm [23] on four artificial data sets and seven UCI data sets. The proposed algorithm will also use the image in the BSDS500 data set for image segmentation. In the experimental part of image segmentation, the comparison algorithm is K-means, NJW [14], PGSC algorithm [17], and SC-NP algorithm [23].In the experiment, the parameters are set as follows: step = 0.1; step adjustment factor eta = 0.95; the ratio between step andD0 is 5; the number of iterations n = 100; and damp = 0.5. The information of data sets is shown in Table 1.Table 1
Data set information.
Data setObjectsAttributesClassesSourceIris15043UCIWine178133UCISeeds21063UCIZoo101167UCIGlass214106UCISonar208602UCIIonosphere351342UCISpiral94422ArtificialTwo moons200022ArtificialThree circles360323ArtificialZigzag100223Artificial


## 4.2. Evaluation Indicators

In the experiment, we use four indicators to evaluate the clustering results: accuracy, ARI, F1 score, and time (s).(1)
Accuracy rate: the accuracy rate represents the proportion of the number of correct clustering samples to the total number of samples, whereV is the division label and U is the real label:(4)Acc=1N∑i=1kmaxjvi∩uj,(2)
ARI: there are four cases by comparing the calculation resultsV with the real label U. SS contains sample pairs that belong to the same cluster in V and the same cluster in U. SD contains sample pairs that belong to the same cluster in V but not the same cluster in U. DS contains sample pairs that do not belong to the same cluster in V but belong to the same cluster in U. DD contains sample pairs that do not belong to the same cluster in V and do not belong to the same cluster in U. Set SS=a,SD=b,DS=c,DD=d; there are(5)ARI=2ad−bca+bb+d+a+cc+d.The larger the value of ARI means that the clustering results are more consistent with the real situation.(3)
F1 score: F1 score is one of the commonly used evaluation criteria in information retrieval. It is a weighted harmonic mean value based on precision and recall. Its definition is as follows, wherea, b, and c have been defined in the above content:(6)F1=2∗P∗RP+R,P=aa+b,R=aa+c.(4)
Time: in this paper, we use the average time of each algorithm running 100 times as the evaluation index.


## 4.3. Data Set Experiment Result Analysis

### 4.3.1. Experimental Results of Artificial Data Sets

Table2 shows the experimental results of the six algorithms on the four artificial data sets. From Figure 2, we can see that our proposed algorithm can well divide the data sets of various structures.Table 2
Accuracy of six algorithms on artificial data sets.
Data setK-meansNJWMPSCPGSCSC-NPSC-DBASSpiral0.59751110.58901Two moons0.73371110.71701Three circles0.55541110.57531Zigzag0.70761110.72751Figure 2
Clustering results using the proposed algorithm for artificial data sets. (a) Spiral. (b) Three circles. (c) Two moons. (d) Zigzag.
(a)(b)(c)(d)


### 4.3.2. Experimental Results of UCI Data Sets

Table3 and Figure 3 show the experimental results of the six algorithms on seven UCI data sets. By comparing the results, we can see that the algorithm proposed in this paper performs better than the other five algorithms and has a shorter running time.Table 3
Results of six algorithms on UCI data sets.
Data setEvaluation indicatorsK-meansNJWMPSCPGSCSC-NPSC-DBASIrisAccuracy0.89330.89330.90670.90000.89330.9600ARI0.55160.68500.75830.88590.87970.9195F1 score0.89180.89880.90570.89880.89180.9332Time (s)0.26100.51640.58800.06690.78410.0553WineAccuracy0.65300.67420.55050.60670.69100.7247ARI0.79430.89860.93100.56140.69380.7395F1 score0.63630.62760.60570.65100.65310.7302Time (s)0.22060.48450.40200.04430.96870.0638SeedsAccuracy0.70080.79050.71940.88100.89050.9000ARI0.70060.70220.68650.85940.86810.8787F1 score0.88970.81500.89140.88130.89130.9092Time (s)0.21950.48930.46410.04031.03810.0641ZooAccuracy0.65340.63370.81190.87130.84160.8713ARI0.63590.74410.77580.89620.89940.9012F1 score0.63190.80380.83890.81900.80450.8540Time (s)0.25610.50350.28440.05550.95380.0608GlassAccuracy0.79130.65420.81310.78970.88320.8598ARI0.73750.57180.77670.82060.85520.8817F1 score0.68120.55150.68720.75090.69730.7364Time (s)0.24180.43350.55470.05120.97100.0712SonarAccuracy0.39420.37010.43460.53850.53370.5721ARI0.08270.00220.13240.50060.49990.5080F1 score0.46230.61190.55560.53700.55930.5716Time (s)0.24220.59500.41810.05871.64580.0794IonosphereAccuracy0.35890.61820.70940.64100.64100.7379ARI0.32400.42370.47720.49890.52530.6121F1 score0.41490.68850.69020.61880.68170.7431Time (s)0.21051.0110.8920.13542.86060.1108Figure 3
Results of six algorithms on UCI data sets. (a) Accuracy. (b) ARI. (c) F1 score. (d) Time (s).
(a)(b)(c)(d)


## 4.3.1. Experimental Results of Artificial Data Sets

Table2 shows the experimental results of the six algorithms on the four artificial data sets. From Figure 2, we can see that our proposed algorithm can well divide the data sets of various structures.Table 2
Accuracy of six algorithms on artificial data sets.
Data setK-meansNJWMPSCPGSCSC-NPSC-DBASSpiral0.59751110.58901Two moons0.73371110.71701Three circles0.55541110.57531Zigzag0.70761110.72751Figure 2
Clustering results using the proposed algorithm for artificial data sets. (a) Spiral. (b) Three circles. (c) Two moons. (d) Zigzag.
(a)(b)(c)(d)


## 4.3.2. Experimental Results of UCI Data Sets

Table3 and Figure 3 show the experimental results of the six algorithms on seven UCI data sets. By comparing the results, we can see that the algorithm proposed in this paper performs better than the other five algorithms and has a shorter running time.Table 3
Results of six algorithms on UCI data sets.
Data setEvaluation indicatorsK-meansNJWMPSCPGSCSC-NPSC-DBASIrisAccuracy0.89330.89330.90670.90000.89330.9600ARI0.55160.68500.75830.88590.87970.9195F1 score0.89180.89880.90570.89880.89180.9332Time (s)0.26100.51640.58800.06690.78410.0553WineAccuracy0.65300.67420.55050.60670.69100.7247ARI0.79430.89860.93100.56140.69380.7395F1 score0.63630.62760.60570.65100.65310.7302Time (s)0.22060.48450.40200.04430.96870.0638SeedsAccuracy0.70080.79050.71940.88100.89050.9000ARI0.70060.70220.68650.85940.86810.8787F1 score0.88970.81500.89140.88130.89130.9092Time (s)0.21950.48930.46410.04031.03810.0641ZooAccuracy0.65340.63370.81190.87130.84160.8713ARI0.63590.74410.77580.89620.89940.9012F1 score0.63190.80380.83890.81900.80450.8540Time (s)0.25610.50350.28440.05550.95380.0608GlassAccuracy0.79130.65420.81310.78970.88320.8598ARI0.73750.57180.77670.82060.85520.8817F1 score0.68120.55150.68720.75090.69730.7364Time (s)0.24180.43350.55470.05120.97100.0712SonarAccuracy0.39420.37010.43460.53850.53370.5721ARI0.08270.00220.13240.50060.49990.5080F1 score0.46230.61190.55560.53700.55930.5716Time (s)0.24220.59500.41810.05871.64580.0794IonosphereAccuracy0.35890.61820.70940.64100.64100.7379ARI0.32400.42370.47720.49890.52530.6121F1 score0.41490.68850.69020.61880.68170.7431Time (s)0.21051.0110.8920.13542.86060.1108Figure 3
Results of six algorithms on UCI data sets. (a) Accuracy. (b) ARI. (c) F1 score. (d) Time (s).
(a)(b)(c)(d)


## 4.4. Application of the SC-DBAS Algorithm to Image Segmentation

Clustering-based image segmentation is based on the similarity between image pixels; through some clustering algorithms, the pixels are divided into different clusters so as to complete the segmentation of the original image.In this section, we segment some images of the BSDS500 data set. For a 481∗321 pixels image, if we treat each pixel as a data point, there will be 154,401 data points. Therefore, in order to reduce the scale of data points, we first use SLIC algorithm [24] to perform presegmentation (superpixel segmentation) on the image. Each superpixel is an oversegmented region and is considered as a data point. Then, the proposed algorithm is used to segment the image. In the experiment, the number of superpixels of each image is 200. The comparison algorithm used in the experiment is K-means, NJW [14], PGSC algorithm [17], and SC-NP algorithm [23]. Then, we can get the results which are given in Figure 4.Figure 4
(a) Original image, (b) K-means, (c) NJW, (d) PGSC, (e) SC-NP, and (f) our proposed algorithm.From the experimental results, we can see that our algorithm can segment the object and the background better, while the other four comparison algorithms will have the wrong segmentation area. The segmentation accuracy results are shown in Table4.Table 4
Accuracy of five algorithms on images.
K-meansNJWPGSCSC-NPSC-DBASImage 10.88040.94830.94830.93040.9943Image 20.55620.55620.53470.99420.9969Image 30.95200.96960.97290.97220.9741Image 40.99020.98830.99200.99170.9924


## 5. Conclusion

In this paper, an improved spectral clustering algorithm combined with the improved BAS algorithm is proposed. The proposed algorithm first improves the construction of the similarity matrix, which uses the distance information of some nearest neighbors of each point to calculate the corresponding scale parameters. In the stage of clustering, we proposed BAS algorithm with damping factor to cluster, which can overcome the problem that the original algorithm oscillates many times in the iterative process. The experimental results show that our algorithm is better than other algorithms in UCI data sets, artificial data sets, and image segmentation. However, in the application of image segmentation, our results will be affected by the effect of superpixel segmentation. The future work is to improve our algorithm so that it does not need to preprocess in image segmentation and can directly segment the image, and we will use more real images and medical images to verify our algorithm.



---

*Source: 1648573-2020-05-29.xml*