# Research on Clustering Method of Improved Glowworm Algorithm Based on Good-Point Set

Authors: Yaping Li; Zhiwei Ni; Feifei Jin; Jingming Li; Fenggang Li
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

As an important data analysis method in data mining, clustering analysis has been researched extensively and in depth. Aiming at the limitation ofK-means clustering algorithm that it is sensitive to the distribution of initial clustering center, Glowworm Swarm Optimization (GSO) Algorithm is introduced to solve clustering problems. Firstly, this paper introduces the basic ideas of GSO algorithm, K-means algorithm, and good-point set and analyzes the feasibility of combining them for clustering optimization. Next, it designs a clustering method of improved GSO algorithm based on good-point set which combines GSO algorithm and classical K-means algorithm together, searches data object space, and provides initial clustering centers for K-means algorithm by means of improved GSO algorithm and thus obtains better clustering results. Major improvement of GSO algorithm is to optimize the initial distribution of glowworm swarm by introducing the theory and method of good-point set. Finally, the new clustering algorithm is applied to UCI data sets of different categories and numbers for clustering test. The advantages of the improved clustering algorithm in terms of sum of squared errors (SSE), clustering accuracy, and robustness are explained through comparison and analysis.


---

## Body

## 1. Introduction

As an unsupervised data analysis method, clustering analysis is widely applied in such fields as data mining, pattern recognition, machine learning, and artificial intelligence [1]. Different from classification, clustering algorithm realizes categorization by gathering data objects through certain similarity metric and clustering criterion without any prior knowledge. As a branch of statistics, clustering analysis has been studied extensively. Clustering method can be mainly classified into division method, hierarchy method, and density-based method. The K-means algorithm proposed by James Macqueen is a typical clustering algorithm based on division [2]. However, the clustering result of K-means algorithm is greatly affected by initial clustering center point and is very sensitive to outliers. Literature [3] optimizes the K-means algorithm by integrating the coding, crossing, and aberrance thoughts of genetic algorithm (GA) with the local optimizing ability of K-means clustering algorithm and proposes the K-means clustering algorithm based on GA. Hierarchy-based clustering methods mainly include CURE algorithm [4] and Chameleon algorithm [5], of which one cluster is represented by multiple points in CURE algorithm, making the processing of nonspherical data sets better. Representative algorithms of density-based clustering methods include DBSCAN algorithm [6], which is able to effectively identify class cluster of any shape, but is very sensitive to the setting of artificial parameters (e.g., radius). Rodriguez and Laio put forward a new density-based density peaks clustering (DPC) algorithm [7] in 2014. In this algorithm, density peaks (i.e., clustering centers) are selected manually through “decision diagram” first, and then, residual data points are allocated to each clustering center on this basis to obtain corresponding clustering result. It is noteworthy that, in recent years, some scholars have started introducing the heuristic swarm optimization algorithm into clustering analysis of different fields and improving clustering effect by virtue of the global searching ability of swarm optimization algorithm. A clustering analysis method combining PSO and K-means is proposed in literature [8] through the global searching ability of particle swarm algorithm. In addition, Cuckoo algorithm, artificial bee colony algorithm, artificial fish swarm algorithm, and so forth [9–12] are also started to be introduced in the research of clustering algorithm.The GSO algorithm [13] proposed by Krishnanand and Ghose is a new swarm intelligence optimization algorithm, which is more efficient in solving multimodal problems compared with traditional swarm intelligence optimization algorithms [14]. Aljarah and Ludwig put forward a new clustering based GSO algorithm in 2013. In this algorithm, the GSO algorithm is adjusted to solve the data clustering problem to locate multiple optimal centroids [15]. An new approach for cluster analysis based on GSO algorithm and K-means has been proposed by Onan and Korukoglu [16]. Due to the multimodal nature of multimedia data, Pushpalatha and Ananthanarayana proposed the GSO algorithm based Multimedia Document Clustering (GSOMDC) algorithm to group the multimedia documents into topics in 2015 [17]. A fuzzy clustering algorithm based on GSO algorithm (GSO-KFCM) is proposed by Cheng and Bao in 2017. In this algorithm, the GSO algorithm obtains the optimal solution as the initial clustering center of the kernelized fuzzy mean clustering algorithm [18].This paper introduces GSO algorithm into clustering analysis, regards each glowworm as a feasible solution in clustering center of data object space, searches data object space through the optimization process of glowworm, and solves clustering center by obtaining multiple extreme points. In this way, it combines GSO algorithm andK-means algorithm together, provides initial clustering centers for K-means algorithm by means of GSO algorithm, solves the problem that K-means algorithm is sensitive to initial clustering centers, and thus obtains better clustering effects. Meanwhile, considering the effect of the initial distribution of glowworm swarm on clustering center search, this paper optimizes the initial glowworm swarm distribution in GSO algorithm by introducing the theory and method of good-point set [19, 20], which improves the global searching performance of GSO algorithm. The research in this paper mainly includes 3 parts. Section 2 gives explanations on relevant algorithms and theories, which puts forward the optimization idea for clustering analysis-oriented GSO algorithm. Section 3 introduces improved GSO algorithm based on good-point set, combines improved GSO algorithm with K-means algorithm together, and designs the algorithm framework and implementation steps for new clustering method (GSOK_GP algorithm). Section 4 selects UCI data sets of different categories and numbers for clustering experiment and analysis for the GSOK_GP algorithm designed in this paper.


## 2. Description of Relevant Algorithms

### 2.1.K-Means Clustering Algorithm

#### 2.1.1. Basic Ideas ofK-Means Clustering Algorithm

Basic ideas ofK-means clustering algorithm: select k data points at random in the data objects to be clustered to act as initial clustering center points, and allocate other data points to corresponding clustering center points based on their similarity with such initial clustering center points. After one round of allocation, recalculate the clustering centers of each category based on the clustering result of the round, and then, allocate residual data points to obtain the clustering result of the new round. Repeat this process for given times or until the convergence of data center points.


#### 2.1.2. Steps ofK-Means Clustering Algorithm

(  1) Problem Description. X = { x 1 , x 2 , … , x N } represents a given data object, where xi represents data vector point. Divide X into several disjoint clusters C={C1,C2,…,Ck}, where X=⋃i=1kCi,Ci∩Cj=∅,Ci≠∅.(  2) Related DefinitionsDefinition 1.
Euclidean distance between data points(1)dis⁡xi,xj=xi-xjxi-xjT2.Definition 2.
SSE of clustering results(2)SSE=∑i=1k∑xi∈zjdis⁡xi-zj,
wherezj is the cluster center of xi. SSE is taken as an important indicator for evaluating clustering result in general.(  3) Implementation Steps of K -Means AlgorithmStep 1.
Randomly selectk samples z(1)={z11,z21,…,zk1,} as initial clustering centers.Step 2.
Allocate other data points in data objectX to existing clustering center zi1 as per given principles (e.g., shortest Euclidean distance).Step 3.
Recalculate clustering centerz(2)={z12,z22,…,zk2} and zi2=(1/m)∑j=1mxj, as per clustering result, where xj is the data point allocated to clustering center point zi1.Step 4.
Ifzi1≠zi2, that is, the new clustering center is different from the original one, turn to Step 2 for iteration again, until the convergence of clustering center points or reaching maximum iterations.It can be learnt from the steps above that initial clustering centers have significant effect on the clustering result and operating efficiency ofK-means clustering algorithm and may lead to premature local optimum of K-means clustering algorithm, which causes clustering results with large difference in turn.


### 2.2. Main Ideas and Steps of GSO Algorithm

In GSO algorithm, each glowworm is deemed as a feasible solution of target problem in space. Glowworms gather towards high brightness glowworm through mutual attraction and location movement, and multiple extreme points are found out in the solution space of a target problem. In this way, the problem is solved. Its main ideas can be described as follows.Step 1.
Initialize glowworm swarmZ={z1,z2,…,zn}. Glowworm number n in swarm, step s, fluorescein initial value l0, fluorescein volatilization rate ρ, domain change rate β, decision domain initial value γ0, domain threshold γmax⁡, and other parameters related need to be initialized and assigned in the initialization.Step 2.
Calculate glowworm fitness based on objective function. Calculate the fitnessf(zi) of each glowworm zi at its location based on specific objective function y=max⁡⁡(f(z)).Step 3.
Calculate the moving direction and step of glowworm. Each glowwormzi searches for glowworms zj with higher fluorescein value li within its own decision radius ri, and determine the next moving direction and step based on fluorescein value and distance.Step 4.
Update glowworm locations. Update the location of each glowwormzi based on determined moving direction and step.Step 5.
Update the decision domain radius of glowworm.Step 6.
Judge whether the algorithm has converged or reached the maximum iterations (itmax) and determine whether to enter the next round of iteration.It can be learnt from the steps above that algorithm execution efficiency can be improved and premature local optimum of algorithm can be avoided by optimizing the initial distribution of glowworm swarm.


### 2.3. Basic Theory of Good-Point Set

Basic definition and structure of good-point set are as follows:(1) AssumeGs is a unit cube in S-dimensional Euclidean space, which is expressed as(3)x∈Gs,x=x1,x2,…,xs,where,0≤xi≤1,i=1,2,…,s.(2) AssumePn(k) is a point set with the number of n in Gs, which is expressed as(4)Pnk=x1nk,x2nk,…,xsnk,where,0≤k≤n,0≤xink≤1,i=1,2,…,s.(3) Assumer=(r1,r2,…,rs) is a given point in Gs and Nnr=Nn(r1,r2,…,rs) is the number of points not satisfying the inequality below in point set Pn(k).(5)0≤xink≤ri,where,i=1,2,…,s.φ n = sup ⁡ N n r / n - r, where r∈Gs,r=r1r2⋯rs, and φn is known as the deviation of point set Pn(k).(4) Assumeφn is the deviation of Pnk=x1n∗k,x2n∗k,…,xsn∗k,k=1,2,…,n and meets the requirements below:φ n = C ( r , ε ) n - 1 + ε, where C(r,ε) is a constant related to r and ε, ε>0.P n ( k ) is known as a good-point set and r a good point.It has been proved by applicable theorems that, with respect to approximate integration, the order of deviationφn is only relevant to n and irrelevant to the space dimensions of the sample. Therefore, good-point set can provide better support for the calculation in high-dimensional spaces [20]. Meanwhile, as for a point set object whose distribution is unknown, the deviation φn of n points Pn=x1,x2,…,xn obtained by virtue of good-point set is significantly superior to n points obtained by random method. Therefore, a better initial distribution scheme can be provided for the swarm distribution in swarm intelligence algorithm based on this feature of good-point set.


## 2.1.K-Means Clustering Algorithm

### 2.1.1. Basic Ideas ofK-Means Clustering Algorithm

Basic ideas ofK-means clustering algorithm: select k data points at random in the data objects to be clustered to act as initial clustering center points, and allocate other data points to corresponding clustering center points based on their similarity with such initial clustering center points. After one round of allocation, recalculate the clustering centers of each category based on the clustering result of the round, and then, allocate residual data points to obtain the clustering result of the new round. Repeat this process for given times or until the convergence of data center points.


### 2.1.2. Steps ofK-Means Clustering Algorithm

(  1) Problem Description. X = { x 1 , x 2 , … , x N } represents a given data object, where xi represents data vector point. Divide X into several disjoint clusters C={C1,C2,…,Ck}, where X=⋃i=1kCi,Ci∩Cj=∅,Ci≠∅.(  2) Related DefinitionsDefinition 1.
Euclidean distance between data points(1)dis⁡xi,xj=xi-xjxi-xjT2.Definition 2.
SSE of clustering results(2)SSE=∑i=1k∑xi∈zjdis⁡xi-zj,
wherezj is the cluster center of xi. SSE is taken as an important indicator for evaluating clustering result in general.(  3) Implementation Steps of K -Means AlgorithmStep 1.
Randomly selectk samples z(1)={z11,z21,…,zk1,} as initial clustering centers.Step 2.
Allocate other data points in data objectX to existing clustering center zi1 as per given principles (e.g., shortest Euclidean distance).Step 3.
Recalculate clustering centerz(2)={z12,z22,…,zk2} and zi2=(1/m)∑j=1mxj, as per clustering result, where xj is the data point allocated to clustering center point zi1.Step 4.
Ifzi1≠zi2, that is, the new clustering center is different from the original one, turn to Step 2 for iteration again, until the convergence of clustering center points or reaching maximum iterations.It can be learnt from the steps above that initial clustering centers have significant effect on the clustering result and operating efficiency ofK-means clustering algorithm and may lead to premature local optimum of K-means clustering algorithm, which causes clustering results with large difference in turn.


## 2.1.1. Basic Ideas ofK-Means Clustering Algorithm

Basic ideas ofK-means clustering algorithm: select k data points at random in the data objects to be clustered to act as initial clustering center points, and allocate other data points to corresponding clustering center points based on their similarity with such initial clustering center points. After one round of allocation, recalculate the clustering centers of each category based on the clustering result of the round, and then, allocate residual data points to obtain the clustering result of the new round. Repeat this process for given times or until the convergence of data center points.


## 2.1.2. Steps ofK-Means Clustering Algorithm

(  1) Problem Description. X = { x 1 , x 2 , … , x N } represents a given data object, where xi represents data vector point. Divide X into several disjoint clusters C={C1,C2,…,Ck}, where X=⋃i=1kCi,Ci∩Cj=∅,Ci≠∅.(  2) Related DefinitionsDefinition 1.
Euclidean distance between data points(1)dis⁡xi,xj=xi-xjxi-xjT2.Definition 2.
SSE of clustering results(2)SSE=∑i=1k∑xi∈zjdis⁡xi-zj,
wherezj is the cluster center of xi. SSE is taken as an important indicator for evaluating clustering result in general.(  3) Implementation Steps of K -Means AlgorithmStep 1.
Randomly selectk samples z(1)={z11,z21,…,zk1,} as initial clustering centers.Step 2.
Allocate other data points in data objectX to existing clustering center zi1 as per given principles (e.g., shortest Euclidean distance).Step 3.
Recalculate clustering centerz(2)={z12,z22,…,zk2} and zi2=(1/m)∑j=1mxj, as per clustering result, where xj is the data point allocated to clustering center point zi1.Step 4.
Ifzi1≠zi2, that is, the new clustering center is different from the original one, turn to Step 2 for iteration again, until the convergence of clustering center points or reaching maximum iterations.It can be learnt from the steps above that initial clustering centers have significant effect on the clustering result and operating efficiency ofK-means clustering algorithm and may lead to premature local optimum of K-means clustering algorithm, which causes clustering results with large difference in turn.


## 2.2. Main Ideas and Steps of GSO Algorithm

In GSO algorithm, each glowworm is deemed as a feasible solution of target problem in space. Glowworms gather towards high brightness glowworm through mutual attraction and location movement, and multiple extreme points are found out in the solution space of a target problem. In this way, the problem is solved. Its main ideas can be described as follows.Step 1.
Initialize glowworm swarmZ={z1,z2,…,zn}. Glowworm number n in swarm, step s, fluorescein initial value l0, fluorescein volatilization rate ρ, domain change rate β, decision domain initial value γ0, domain threshold γmax⁡, and other parameters related need to be initialized and assigned in the initialization.Step 2.
Calculate glowworm fitness based on objective function. Calculate the fitnessf(zi) of each glowworm zi at its location based on specific objective function y=max⁡⁡(f(z)).Step 3.
Calculate the moving direction and step of glowworm. Each glowwormzi searches for glowworms zj with higher fluorescein value li within its own decision radius ri, and determine the next moving direction and step based on fluorescein value and distance.Step 4.
Update glowworm locations. Update the location of each glowwormzi based on determined moving direction and step.Step 5.
Update the decision domain radius of glowworm.Step 6.
Judge whether the algorithm has converged or reached the maximum iterations (itmax) and determine whether to enter the next round of iteration.It can be learnt from the steps above that algorithm execution efficiency can be improved and premature local optimum of algorithm can be avoided by optimizing the initial distribution of glowworm swarm.


## 2.3. Basic Theory of Good-Point Set

Basic definition and structure of good-point set are as follows:(1) AssumeGs is a unit cube in S-dimensional Euclidean space, which is expressed as(3)x∈Gs,x=x1,x2,…,xs,where,0≤xi≤1,i=1,2,…,s.(2) AssumePn(k) is a point set with the number of n in Gs, which is expressed as(4)Pnk=x1nk,x2nk,…,xsnk,where,0≤k≤n,0≤xink≤1,i=1,2,…,s.(3) Assumer=(r1,r2,…,rs) is a given point in Gs and Nnr=Nn(r1,r2,…,rs) is the number of points not satisfying the inequality below in point set Pn(k).(5)0≤xink≤ri,where,i=1,2,…,s.φ n = sup ⁡ N n r / n - r, where r∈Gs,r=r1r2⋯rs, and φn is known as the deviation of point set Pn(k).(4) Assumeφn is the deviation of Pnk=x1n∗k,x2n∗k,…,xsn∗k,k=1,2,…,n and meets the requirements below:φ n = C ( r , ε ) n - 1 + ε, where C(r,ε) is a constant related to r and ε, ε>0.P n ( k ) is known as a good-point set and r a good point.It has been proved by applicable theorems that, with respect to approximate integration, the order of deviationφn is only relevant to n and irrelevant to the space dimensions of the sample. Therefore, good-point set can provide better support for the calculation in high-dimensional spaces [20]. Meanwhile, as for a point set object whose distribution is unknown, the deviation φn of n points Pn=x1,x2,…,xn obtained by virtue of good-point set is significantly superior to n points obtained by random method. Therefore, a better initial distribution scheme can be provided for the swarm distribution in swarm intelligence algorithm based on this feature of good-point set.


## 3. Design of GSOK_GP Algorithm

This paper proposes an improved GSO algorithm based on good-point set to solve clustering problems on the basis of analysis of relevant algorithms above and characteristics of clustering problems. Its main ideas can be described as firstly, optimize the initial distribution of glowworm swarm through good-point set, so as to optimize GSO algorithm. Secondly, optimize the initial clustering centers in clustering data objects, and obtain characteristics of multiple extreme points and a clustering center point set with optimized GSO algorithm. Thirdly, selectk extreme points as the initial clustering center of K-means algorithm in the clustering center point set as per maximum distance principle. Fourthly, execute the K-means algorithm with initial clustering center to figure out the clustering result. The algorithm framework is shown as Figure 1. Where t≤itmax means the iterations are no greater than maximum iterations, flag>k means the number of extreme points is greater than the numberk of initial clustering centers required.Figure 1
Flow of GSOK_GP algorithm.


### 3.1. Initial Swarm Optimization Based on Good-Point Set

Optimization of initial distribution of glowworm swarm is to represent the characteristics of solution space more scientifically utilizing glowworm swarm in essence. Randomly generated glowworm swarm cannot cover all conditions of solution space in most cases. Therefore, uniform distribution of glowworm swarm in solution space is an effective strategy. More uniform distribution of swarm can be realized with the theory and method of good-point set above.Assume the initial glowworm swarm number isn; selectn points ins-dimensional space to act as glowworm locations. Select the good-point set Pnk=x1n∗k,x2n∗k,…,xsn∗k,k=1,2,…,n composed ofn good points ins-dimensional space with good-point set theory. There are mainly three methods:(1) Square root sequence method:rk={pk,1≤k≤s}, where pk are different primes.(2) Cyclotomic field method:rk={2cos⁡2πk/p,1≤k≤s}, where p is the smallest prime meeting (p-3)/2≥s.(3) Exponential sequence method:rk={ek,1≤k≤s}.Assumings=2 and n=300, construct good-point set (i.e., initial glowworm swarm distribution) with exponential sequence method. Figures 1 and 2 show the data points (glowworms) distribution under random condition and when applying exponential sequence method, respectively.Figure 2
Randomly distributedn data points (glowworms).The comparison between Figures2 and 3 indicates that the data point distribution in exponential sequence method is more uniform, which is able to cover the solution space better. In the meantime, the structure of its good-point set is more stable; that is, the distribution effect is consistent when n is unchanged. Therefore, a better initial glowworm distribution can be obtained by applying good-point set in initial glowworm swarm distribution.Figure 3
n data points (glowworms) distributed in good-point set exponential sequence method.


### 3.2. Flow of GSOK_GP Algorithm

Glowworm individuals are deemed as the feasible solutions of a clustering center point when combining improved glowworm algorithm withK-means algorithm to solve clustering problems. In view of the characteristic that clustering center points are surrounded by data points of data objects, the density of clustering center points is represented by an extreme value of various data point densities within one domain. Therefore, take the density of glowworm individuals in data object set as their fitness, and obtain a superior initial clustering center point set through optimizing of density extreme value by glowworms. The main algorithm flow is as follows.Step 1.
Initialize with the glowworm swarm based on good-point set. As for the data setX=x1,x2,…,xN needing to be clustered, initialize and assign glowworm number n in swarm, initial location of glowworm, step s, fluorescein initial value l0, fluorescein volatilization rate ρ, domain change rate β, decision domain initial value γ0, domain threshold γmax⁡, and other parameters related in the Euclidean space where X is limited.(6)X=x1,x2,…,xN,xi=xi1,xi2,…,xis,Z=z1,z2,…,zn,zi=zi1,zi2,…,zis,zij∈min⁡xi,max⁡xi.Step 2.
Calculate glowworm fitness, namely, the numberfzi of data points in data set X=x1,x2,…,xN in the domain where glowworm zi distance is γi.(7)DsetXzi=xj∣dis⁡xj,zi<γi.fzi=countDsetziStep 3.
Update glowworm fluorescein.lit represents the fluorescein value of glowworm t in round zi of iteration.(8)lit+1=1-ρlit+λfxit.Step 4.
Determine moving direction. Glowwormzi searches the glowworm with higher fluorescein in decision domain and selects the glowworm zj with higher fluorescein through roulette approach, which acts as the moving direction of the next step. DsetZzi represents the glowworm set in the domain, DsetLzi represents the glowworm set with higher fluorescein in the domain, and PDsetLzi represents the probability of each glowworm to be selected. Choose the glowworm zj with the maximum probability to act as the moving direction of glowworm zi.(9)DsetZzi=zj∣dis⁡zj,zi<γi,j≠iDsetLzi=zj∣dis⁡zj,zi<γi,lj>li,j≠i,PDsetLzi=p1,p2,…,pmPzj=max⁡p1,p2,…,pm.Step 5.
Update location. Glowwormzi moves by the step s towards the direction of glowworm zj to complete location update of all glowworms.(10)zi=zi+zj-zizj-zi×s.Step 6.
Update decision domain.γit represents the decision radius of glowworm zi in round t iteration, nS represents the threshold of glowworm number in the domain, and nt represents the glowworm number within the decision radius.(11)γit+1=γit+βnS-nt.Step 7.
Judge the termination condition of glowworm search and enter iteration of the next round.Step 8.
Glowworm algorithm terminates, andk extreme points are output to act as the initial clustering center points for K-means algorithm.Step 9.
ExecuteK-means algorithm and output clustering result.


### 3.3. Key Strategies in GSOK_GP Algorithm

#### 3.3.1. Density-Based Fitness Function

Cluster center is a glowworm data point surrounded by adjacent points of low local density in GSOK_GP algorithm; therefore, cluster center can be interpreted as a local optimal point on fitness.(12)fzi=countDsetzicountDsetzi=∑zj∈Dsetzidijdij=1,dis⁡xj,zi<γi0,dis⁡xj,zi≥γi.


#### 3.3.2. Weighted Euclidean Distance

Since there is large difference in value range of the data object in different dimensions, partial attributes with a large value range may have greater effect on the Euclidean distance between data points if only Euclidean distance is applied, which will cause greater effect on the clustering result. Therefore, calculation of Euclidean distance needs to be adjusted through different weights allocation in the process of initial clustering center search by the glowworm if assuming each dimension of the data object has the same effect on the clustering result without prior knowledge.Assumption 3.
Value range of data objectX in each dimension is expressed as follows:(13)U=a1,b1,a1,b1,…,an,bn.Set di=bi-ai, D=(d1,d2,…,dn,).
W = ( w 1 , w 2 , … , w n , ) represents the weight to be assigned to different dimensions:(14)wi=1/di∑1/di.Improved Euclidean distance calculation method is redefined in this way.(15)dis⁡xi,xj=xi-xjxi-xjWT2.
It should be noted that adjustment for Euclidean distance calculation method is only applied in the process of searching initial clustering center in GSO algorithm, and general Euclidean distance calculation approach needs to be adopted in algorithm evaluation, so as to compare and analyze with other algorithms.


#### 3.3.3. Selection of Extreme Point

A relatively large distance between cluster centers is necessary in clustering algorithm. Therefore, selectk centers in multiple cluster centers to constitute the initial clustering centers of K-means algorithm; that is, selecting k extreme points in extreme point set J=J1,J2,…,Jp to act as the initial clustering centers of K-means algorithm needs to follow distance maximization principle. When p>k, the basic steps for selecting extreme points are as follows:(1) Firstly, select the glowworm with the highest fitness to act as the first clustering center point.(2) Secondly, calculate the distances from other clustering center points to the first clustering center point, and select the one with the largest distance to act as the second clustering center point.(3) Repeat step (2) to calculate the sum of the distances from other clustering center points to clustering centers selected, and select the one with the largest distance to act as the next clustering center point untilk clustering center points are obtained.


## 3.1. Initial Swarm Optimization Based on Good-Point Set

Optimization of initial distribution of glowworm swarm is to represent the characteristics of solution space more scientifically utilizing glowworm swarm in essence. Randomly generated glowworm swarm cannot cover all conditions of solution space in most cases. Therefore, uniform distribution of glowworm swarm in solution space is an effective strategy. More uniform distribution of swarm can be realized with the theory and method of good-point set above.Assume the initial glowworm swarm number isn; selectn points ins-dimensional space to act as glowworm locations. Select the good-point set Pnk=x1n∗k,x2n∗k,…,xsn∗k,k=1,2,…,n composed ofn good points ins-dimensional space with good-point set theory. There are mainly three methods:(1) Square root sequence method:rk={pk,1≤k≤s}, where pk are different primes.(2) Cyclotomic field method:rk={2cos⁡2πk/p,1≤k≤s}, where p is the smallest prime meeting (p-3)/2≥s.(3) Exponential sequence method:rk={ek,1≤k≤s}.Assumings=2 and n=300, construct good-point set (i.e., initial glowworm swarm distribution) with exponential sequence method. Figures 1 and 2 show the data points (glowworms) distribution under random condition and when applying exponential sequence method, respectively.Figure 2
Randomly distributedn data points (glowworms).The comparison between Figures2 and 3 indicates that the data point distribution in exponential sequence method is more uniform, which is able to cover the solution space better. In the meantime, the structure of its good-point set is more stable; that is, the distribution effect is consistent when n is unchanged. Therefore, a better initial glowworm distribution can be obtained by applying good-point set in initial glowworm swarm distribution.Figure 3
n data points (glowworms) distributed in good-point set exponential sequence method.


## 3.2. Flow of GSOK_GP Algorithm

Glowworm individuals are deemed as the feasible solutions of a clustering center point when combining improved glowworm algorithm withK-means algorithm to solve clustering problems. In view of the characteristic that clustering center points are surrounded by data points of data objects, the density of clustering center points is represented by an extreme value of various data point densities within one domain. Therefore, take the density of glowworm individuals in data object set as their fitness, and obtain a superior initial clustering center point set through optimizing of density extreme value by glowworms. The main algorithm flow is as follows.Step 1.
Initialize with the glowworm swarm based on good-point set. As for the data setX=x1,x2,…,xN needing to be clustered, initialize and assign glowworm number n in swarm, initial location of glowworm, step s, fluorescein initial value l0, fluorescein volatilization rate ρ, domain change rate β, decision domain initial value γ0, domain threshold γmax⁡, and other parameters related in the Euclidean space where X is limited.(6)X=x1,x2,…,xN,xi=xi1,xi2,…,xis,Z=z1,z2,…,zn,zi=zi1,zi2,…,zis,zij∈min⁡xi,max⁡xi.Step 2.
Calculate glowworm fitness, namely, the numberfzi of data points in data set X=x1,x2,…,xN in the domain where glowworm zi distance is γi.(7)DsetXzi=xj∣dis⁡xj,zi<γi.fzi=countDsetziStep 3.
Update glowworm fluorescein.lit represents the fluorescein value of glowworm t in round zi of iteration.(8)lit+1=1-ρlit+λfxit.Step 4.
Determine moving direction. Glowwormzi searches the glowworm with higher fluorescein in decision domain and selects the glowworm zj with higher fluorescein through roulette approach, which acts as the moving direction of the next step. DsetZzi represents the glowworm set in the domain, DsetLzi represents the glowworm set with higher fluorescein in the domain, and PDsetLzi represents the probability of each glowworm to be selected. Choose the glowworm zj with the maximum probability to act as the moving direction of glowworm zi.(9)DsetZzi=zj∣dis⁡zj,zi<γi,j≠iDsetLzi=zj∣dis⁡zj,zi<γi,lj>li,j≠i,PDsetLzi=p1,p2,…,pmPzj=max⁡p1,p2,…,pm.Step 5.
Update location. Glowwormzi moves by the step s towards the direction of glowworm zj to complete location update of all glowworms.(10)zi=zi+zj-zizj-zi×s.Step 6.
Update decision domain.γit represents the decision radius of glowworm zi in round t iteration, nS represents the threshold of glowworm number in the domain, and nt represents the glowworm number within the decision radius.(11)γit+1=γit+βnS-nt.Step 7.
Judge the termination condition of glowworm search and enter iteration of the next round.Step 8.
Glowworm algorithm terminates, andk extreme points are output to act as the initial clustering center points for K-means algorithm.Step 9.
ExecuteK-means algorithm and output clustering result.


## 3.3. Key Strategies in GSOK_GP Algorithm

### 3.3.1. Density-Based Fitness Function

Cluster center is a glowworm data point surrounded by adjacent points of low local density in GSOK_GP algorithm; therefore, cluster center can be interpreted as a local optimal point on fitness.(12)fzi=countDsetzicountDsetzi=∑zj∈Dsetzidijdij=1,dis⁡xj,zi<γi0,dis⁡xj,zi≥γi.


### 3.3.2. Weighted Euclidean Distance

Since there is large difference in value range of the data object in different dimensions, partial attributes with a large value range may have greater effect on the Euclidean distance between data points if only Euclidean distance is applied, which will cause greater effect on the clustering result. Therefore, calculation of Euclidean distance needs to be adjusted through different weights allocation in the process of initial clustering center search by the glowworm if assuming each dimension of the data object has the same effect on the clustering result without prior knowledge.Assumption 3.
Value range of data objectX in each dimension is expressed as follows:(13)U=a1,b1,a1,b1,…,an,bn.Set di=bi-ai, D=(d1,d2,…,dn,).
W = ( w 1 , w 2 , … , w n , ) represents the weight to be assigned to different dimensions:(14)wi=1/di∑1/di.Improved Euclidean distance calculation method is redefined in this way.(15)dis⁡xi,xj=xi-xjxi-xjWT2.
It should be noted that adjustment for Euclidean distance calculation method is only applied in the process of searching initial clustering center in GSO algorithm, and general Euclidean distance calculation approach needs to be adopted in algorithm evaluation, so as to compare and analyze with other algorithms.


### 3.3.3. Selection of Extreme Point

A relatively large distance between cluster centers is necessary in clustering algorithm. Therefore, selectk centers in multiple cluster centers to constitute the initial clustering centers of K-means algorithm; that is, selecting k extreme points in extreme point set J=J1,J2,…,Jp to act as the initial clustering centers of K-means algorithm needs to follow distance maximization principle. When p>k, the basic steps for selecting extreme points are as follows:(1) Firstly, select the glowworm with the highest fitness to act as the first clustering center point.(2) Secondly, calculate the distances from other clustering center points to the first clustering center point, and select the one with the largest distance to act as the second clustering center point.(3) Repeat step (2) to calculate the sum of the distances from other clustering center points to clustering centers selected, and select the one with the largest distance to act as the next clustering center point untilk clustering center points are obtained.


## 3.3.1. Density-Based Fitness Function

Cluster center is a glowworm data point surrounded by adjacent points of low local density in GSOK_GP algorithm; therefore, cluster center can be interpreted as a local optimal point on fitness.(12)fzi=countDsetzicountDsetzi=∑zj∈Dsetzidijdij=1,dis⁡xj,zi<γi0,dis⁡xj,zi≥γi.


## 3.3.2. Weighted Euclidean Distance

Since there is large difference in value range of the data object in different dimensions, partial attributes with a large value range may have greater effect on the Euclidean distance between data points if only Euclidean distance is applied, which will cause greater effect on the clustering result. Therefore, calculation of Euclidean distance needs to be adjusted through different weights allocation in the process of initial clustering center search by the glowworm if assuming each dimension of the data object has the same effect on the clustering result without prior knowledge.Assumption 3.
Value range of data objectX in each dimension is expressed as follows:(13)U=a1,b1,a1,b1,…,an,bn.Set di=bi-ai, D=(d1,d2,…,dn,).
W = ( w 1 , w 2 , … , w n , ) represents the weight to be assigned to different dimensions:(14)wi=1/di∑1/di.Improved Euclidean distance calculation method is redefined in this way.(15)dis⁡xi,xj=xi-xjxi-xjWT2.
It should be noted that adjustment for Euclidean distance calculation method is only applied in the process of searching initial clustering center in GSO algorithm, and general Euclidean distance calculation approach needs to be adopted in algorithm evaluation, so as to compare and analyze with other algorithms.


## 3.3.3. Selection of Extreme Point

A relatively large distance between cluster centers is necessary in clustering algorithm. Therefore, selectk centers in multiple cluster centers to constitute the initial clustering centers of K-means algorithm; that is, selecting k extreme points in extreme point set J=J1,J2,…,Jp to act as the initial clustering centers of K-means algorithm needs to follow distance maximization principle. When p>k, the basic steps for selecting extreme points are as follows:(1) Firstly, select the glowworm with the highest fitness to act as the first clustering center point.(2) Secondly, calculate the distances from other clustering center points to the first clustering center point, and select the one with the largest distance to act as the second clustering center point.(3) Repeat step (2) to calculate the sum of the distances from other clustering center points to clustering centers selected, and select the one with the largest distance to act as the next clustering center point untilk clustering center points are obtained.


## 4. Experiment and Analysis

### 4.1. Experimental Environment

Matlab is employed to compile GSOK_GP algorithm and two UCI data sets shown in Table1 are selected to test its effectiveness in this paper. Design parameters of GSO algorithm referring to relevant literatures, and select relevant parameters of M-GSO algorithm as follows based on actual clustering problems: N=50, ρ=0.4, λ=0.6, β=0.08, s=1, l0=5, and ns=6, with maximum iterations: 100.Table 1
Selection of experimental data set.
Data set Number of dimensions Number of categories Number of samples Iris 4 3 150 Glass 9 6 214SSE, clustering accuracy, and robustness are used to evaluate clustering effect of algorithm in this paper. SSE employs the sum of the Euclidean distances from all data objects to their cluster center points. The calculation approach is as follows:SSE = ∑ j = 1 k ∑ x i ∈ z j x i - z j x i - z j T 2, where zj is the cluster center point of xi.The clustering accuracy proposed by Gan et al. is taken as one of the clustering effect evaluation standards in this paper [21]. Clustering accuracy refers to the proportion of accurately classified samples to total samples. The definition of clustering accuracy AC⁡ is as follows:(16)AC⁡=∑i=1kain,wherek represents the number of categories of data sets, n represents the total number of samples in the data set, ai represents the number of samples accurately classified into Category i.In addition, the robustness indicators proposed in literature [22] are used to identify the algorithm stability in this paper. The algorithm robustness in this paper is calculated with the mean square error of results of multiple experiments as per the calculation formula below:(17)R=AC⁡∗-AC⁡′AC⁡∗×100%,whereAC⁡∗ is the optimal value of clustering accuracy and AC⁡′ is the average value of clustering accuracy obtained by operating the algorithm multiple times. The smaller the R is, the higher the algorithm robustness will be.


### 4.2. Experimental Results and Analysis

The data of executing GSOK_GP algorithm 20 times for Iris and Glass data sets, respectively, and independently is shown in Tables2, 3, and 4. The data of executing K-means algorithm and PSOK algorithm 20 times is cited from literature [9].Table 2
Experimental results of iris data set.
Algorithm Average value of SSEs Average value of ACs (%) Standard deviation value of ACs K-means 102.57 83.95 0.0451 PSOK 99.61 87.39 0.0420 GSOK_GP 97.32 89.33 0Table 3
Experimental results of glass data set.
Algorithm Average value of SSEs Average value of ACs (%) Standard deviation value of ACs K-means 241.03 51.70 0.0157 PSOK 233.23 52.20 0.0108 GSOK_GP 225.08 53.50 0.0090Table 4
Comparison of robustness(R) of each algorithm (%).
Algorithm Iris Glass K-means 10.7 5.73 PSOK 8.07 3.65 GSOK_GP 0 2.97There are 150 sample objects in Iris data set, each of which has 4 attributes, which can be classified into 3 categories in total. The experimental results of Iris data set are shown in Table2.There are 214 data sets in Glass data set; each object has 9 attributes, which can be classified into 6 categories in total. The experimental results of Glass data set are shown in Table3.It can be learnt from Tables2 and 3 that GSOK_GP algorithm is superior to traditional k-means algorithm and PSOK algorithm on SSE and average accuracy.Calculation results based on comparing the robustness of traditionalk-means algorithm, PSOK algorithm, and GSOK_GP algorithm are shown in Table 4.Table4 indicates that the operation results of 20 independent operations of GSOK_GP algorithm for Iris data set are consistent, which proves significant stability. And the fluctuation in the operation results of 20 independent operations for Glass data set is obviously smaller than that of k-means algorithm and PSOK algorithm. Therefore, GSOK_GP algorithm has better robustness in the experiments.


## 4.1. Experimental Environment

Matlab is employed to compile GSOK_GP algorithm and two UCI data sets shown in Table1 are selected to test its effectiveness in this paper. Design parameters of GSO algorithm referring to relevant literatures, and select relevant parameters of M-GSO algorithm as follows based on actual clustering problems: N=50, ρ=0.4, λ=0.6, β=0.08, s=1, l0=5, and ns=6, with maximum iterations: 100.Table 1
Selection of experimental data set.
Data set Number of dimensions Number of categories Number of samples Iris 4 3 150 Glass 9 6 214SSE, clustering accuracy, and robustness are used to evaluate clustering effect of algorithm in this paper. SSE employs the sum of the Euclidean distances from all data objects to their cluster center points. The calculation approach is as follows:SSE = ∑ j = 1 k ∑ x i ∈ z j x i - z j x i - z j T 2, where zj is the cluster center point of xi.The clustering accuracy proposed by Gan et al. is taken as one of the clustering effect evaluation standards in this paper [21]. Clustering accuracy refers to the proportion of accurately classified samples to total samples. The definition of clustering accuracy AC⁡ is as follows:(16)AC⁡=∑i=1kain,wherek represents the number of categories of data sets, n represents the total number of samples in the data set, ai represents the number of samples accurately classified into Category i.In addition, the robustness indicators proposed in literature [22] are used to identify the algorithm stability in this paper. The algorithm robustness in this paper is calculated with the mean square error of results of multiple experiments as per the calculation formula below:(17)R=AC⁡∗-AC⁡′AC⁡∗×100%,whereAC⁡∗ is the optimal value of clustering accuracy and AC⁡′ is the average value of clustering accuracy obtained by operating the algorithm multiple times. The smaller the R is, the higher the algorithm robustness will be.


## 4.2. Experimental Results and Analysis

The data of executing GSOK_GP algorithm 20 times for Iris and Glass data sets, respectively, and independently is shown in Tables2, 3, and 4. The data of executing K-means algorithm and PSOK algorithm 20 times is cited from literature [9].Table 2
Experimental results of iris data set.
Algorithm Average value of SSEs Average value of ACs (%) Standard deviation value of ACs K-means 102.57 83.95 0.0451 PSOK 99.61 87.39 0.0420 GSOK_GP 97.32 89.33 0Table 3
Experimental results of glass data set.
Algorithm Average value of SSEs Average value of ACs (%) Standard deviation value of ACs K-means 241.03 51.70 0.0157 PSOK 233.23 52.20 0.0108 GSOK_GP 225.08 53.50 0.0090Table 4
Comparison of robustness(R) of each algorithm (%).
Algorithm Iris Glass K-means 10.7 5.73 PSOK 8.07 3.65 GSOK_GP 0 2.97There are 150 sample objects in Iris data set, each of which has 4 attributes, which can be classified into 3 categories in total. The experimental results of Iris data set are shown in Table2.There are 214 data sets in Glass data set; each object has 9 attributes, which can be classified into 6 categories in total. The experimental results of Glass data set are shown in Table3.It can be learnt from Tables2 and 3 that GSOK_GP algorithm is superior to traditional k-means algorithm and PSOK algorithm on SSE and average accuracy.Calculation results based on comparing the robustness of traditionalk-means algorithm, PSOK algorithm, and GSOK_GP algorithm are shown in Table 4.Table4 indicates that the operation results of 20 independent operations of GSOK_GP algorithm for Iris data set are consistent, which proves significant stability. And the fluctuation in the operation results of 20 independent operations for Glass data set is obviously smaller than that of k-means algorithm and PSOK algorithm. Therefore, GSOK_GP algorithm has better robustness in the experiments.


## 5. Conclusion

TraditionalK-means clustering algorithm is widely used due to its simple principle and high execution efficiency. However, K-means algorithm relies on initial clustering centers, which leads to large difference in the clustering result, low accuracy, and lack of stability of traditional K-means algorithm. In this paper, the initial clustering centers in K-means algorithm are optimized with improved glowworm algorithm based on good-point set, and the clustering effect is improved.The GSOK_GP algorithm proposed in this paper is mainly applied to solving data object clustering problems under unsupervised learning conditions. The difference between the GSOK_GP algorithm and traditional clustering methods is that it combines GSO algorithm andK-means algorithm together to improve the clustering effect. In particular, as for the effect of initial clustering centers on clustering results, this paper provides more scientific descriptions for data object space by introducing the theory and method of good-point set and obtains superior initial clustering center points with the searching ability of GSO algorithm. Through comparison and analysis, GSOK_GP algorithm is proved to have better clustering effect and stability.In addition, the adverse effect of computing efficiency of GSOK_GP algorithm for glowworm density in case of large data object has also been noticed, which means that the convergence of GSOK_GP algorithm needs to be improved further, so as to apply it better when addressing clustering problems under large data volume.



---

*Source: 8724084-2018-03-05.xml*