# An Adaptive Multiobjective Genetic Algorithm with Fuzzyc-Means for Automatic Data Clustering

Authors: Ze Dong; Hao Jia; Miao Liu
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

This paper presents a fuzzy clustering method based on multiobjective genetic algorithm. The ADNSGA2-FCM algorithm was developed to solve the clustering problem by combining the fuzzy clustering algorithm (FCM) with the multiobjective genetic algorithm (NSGA-II) and introducing an adaptive mechanism. The algorithm does not need to give the number of clusters in advance. After the number of initial clusters and the center coordinates are given randomly, the optimal solution set is found by the multiobjective evolutionary algorithm. After determining the optimal number of clusters by majority vote method, theJm value is continuously optimized through the combination of Canonical Genetic Algorithm and FCM, and finally the best clustering result is obtained. By using standard UCI dataset verification and comparing with existing single-objective and multiobjective clustering algorithms, the effectiveness of this method is proved.


---

## Body

## 1. Introduction

Clustering is a common unsupervised learning method in the field of machine learning. It has been widely used in many fields, such as data mining, pattern recognition, information retrieval, and other fields. In these fields, most of the data is unlabeled data with multiple attributes. In this high-dimensional space, it is very difficult for us to get the required information through the graph. Therefore, the ultimate goal of clustering is to achieve unsupervised classification of these few labeled or unlabeled complex data.FuzzyC-means algorithm (FCM) is a widely used clustering algorithm in the field of machine learning. It was proposed by Bezdek et al. in 1984 [1]. It is different from the traditional non-A or B hard clustering methods. By introducing the fuzzy membership matrix, the fuzzy C-means algorithm allows data points to belong to multiple classes according to their fuzzy membership degree. We choose the class with the highest value of the current data point in the fuzzy membership matrix as the final clustering result. This method solves the problem of clustering overlap of traditional hard clustering algorithms (such as k-means method [2]), and more in line with the actual situation in data clustering. However, FCM has two serious shortcomings. Firstly, it easily falls into local minima. Secondly, it is necessary to specify the number of clusters and the algorithm is very sensitive to the initial center [3, 4].To overcome the first shortcoming, some global optimization techniques have been introduced to deal with data clustering problems in the past years, for example, simulated annealing- (SA-) based [5], particle swarm optimization- (PSO-) based [6–8], genetic algorithms- (GA-) based [9–11], and quantum genetic algorithms- (QGA-) based techniques [12]. In recent years, genetic algorithms have been used to automatically determine the number of clusters by using variable-length strings [13, 14]. In [15], FCM combined with genetic algorithm, which has been successfully applied to remote sensing imagery in [16].Most optimization based clustering algorithms are single-objective optimization algorithms, because only one validity measure of effectiveness is optimized. Noted that a single validity measure can only reflect some of the inherent segmentation attributes, for example, the compactness of clusters, the spatial separation between the clusters, and the cluster’s symmetry. If there are several classes of geometric shapes present in the same dataset, the clustering algorithms that use a single clustering validity index will not be able to process such datasets. Therefore, it is necessary to optimize several clustering validity indexes that can capture different data features at the same time. Based on this consideration, data clustering should be considered as a multiobjective optimization problem.In recent years, multiobjective optimization problems have received extensive attention. Many scholars have conducted extensive researches on multiobjective evolutionary algorithms and have achieved extensive applications in feature extraction, data classification, and clustering.In [17], a new method of classification feature extraction is proposed. A probability-based encoding technology and an effective hybrid operator, together with the ideas of the crowding distance, the external archive, and the Pareto domination relationship, are applied to PSO. By using this way to improve the search capability of the algorithm, the experimental comparison proves the effectiveness of the algorithm. In [18], a new multilabel feature selection algorithm is proposed to use an improved multiobjective particle swarm optimization (PSO), with the purpose of searching for a Pareto set of nondominated solutions (feature subsets). Two new operators are proposed to improve the performance of the proposed PSO-based algorithm. Finally, the effectiveness of the algorithm is verified by experiments.Multiobjective evolutionary algorithms (MOEAs) have been proven to provide promising solutions to the problem of single-objective clustering algorithms that provide efficient search performance [19]. In [20], a multiobjective clustering technique, MOCK, is proposed to recognize the appropriate partitioning from the data sets that contain either hyperspherical shaped clusters or well-separated clusters. In [21], a multiobjective clustering technique is proposed, called VAMOSA. The algorithm optimizes two clustering validity indices simultaneously, so that the algorithm can evolve proper partitioning from the clustering data set with any shape, size, or convexity. In [22], a fuzzy clustering algorithm named MOmoDEFC based on improved multiobjective differential evolution was proposed. By using XB Index [23] and FCM measure (Jm) as objective functions, the algorithm can optimize both the compactness and separation of clusters simultaneously. It also improved the clustering effect.Based on the above consideration, we developed a fuzzy clustering algorithm by using the multiobjective optimization framework, combined the knowledge of FCM and general genetic algorithm. The algorithm is aimed to achieve the functions as follows:(1) automatically determine the number of clusters; (2) improve clustering performance.The rest of this paper is arranged as follows. Section2 introduces the related theories, including the FCM algorithm and the multiobjective genetic algorithm NSGA-II. Section 3 introduces the improved multiobjective optimization framework and the adaptive multiobjective dynamic fuzzy clustering algorithm ADNSGA2-FCM. In Section 4, experiments results were carried out by using some standard UCI datasets. The experimental results were compared with many clustering algorithms in detail. Finally, conclusions are drawn in Section 5.


## 2. Theoretical Basis

### 2.1. FuzzyC-Means Algorithm

Suppose that fuzzyc-means (FCM) partitions a set of n data objects X={x1,x2,…,xn}n×p into c  (1≤c≤n) fuzzy clusters, where each object has p attributes. Let V={v1,v2,…,vc}c×p be a set of cluster centers. Let U=uikc×n be a c×n matrix of membership degrees in which uik is the membership degree of kth object to the cth cluster center. The matrix satisfies the conditions(1)∑i=1cuik=1,uik≥0,uik∈0,1.The FCM algorithm uses the objective function to solve the optimal clustering, which is a clear difference from the hard clustering algorithm. The objective functionJFCM can be defined as follows:(2)JFCM=∑i=1c∑k=1nuikmxk-vi.In (2), m is the fuzzification coefficient, representing the fuzzy degree of clustering. Define m=2. xk-vi means the Euclidean distance between the kth data points and the first ith cluster centers, which represents the in-class similarity. A good clustering algorithm should ensure that the distance between similar points in the clustering result is as compact as possible. The standard FCM uses the JFCM as a cost function to be minimized.The minimization ofJFCM can be achieved by Lagrange multiplier method under constraint ∑i=1cuik=1, k=1,2,…,n, while the membership degrees matrix U and cluster centers are updated according to(3)uik=∑t=1cxk-vixk-vt-2/m-1,(4)vi=∑k=1nuikmxk∑k=1nuikm.By iteration, the algorithm ends when conditionJFCM(t)-JFCM(t+1)<ε is satisfied, where ε is a small positive number representing the end of iteration threshold.


### 2.2. Multiobjective Optimization Based on Genetic Algorithm

Unlike single-objective optimization algorithms, the multiobjective optimization algorithm optimizes multiple objective functions simultaneously. Because it is necessary to optimize multiple conflicting objectives simultaneously, it is often difficult to find a solution to make all the objective functions reach the optimum simultaneously. For multiobjective optimization algorithms, each objective function is considered equally important when the relative importance of the goals is unknown. Therefore, the multiobjective optimization problem is not to optimize one solution, but to optimize one solution set, which is characterized by improving any objective function without impairing other objective functions. We call this solution a nondominated solution or a Pareto optimal solution, which is defined as follows [24].For minimizing the multiobjective problem, a vector ofn target components fi(i=1,…,n) is (5)f¯X¯=f1X¯,f2X¯,…,fnX¯,where X¯u∈U is the decision variable. If X¯u is the Pareto optimal solution, it needs to be satisfied: only if X¯v∈U, there is no decision variable v=f(X¯v)=(v1,v2,…,vn), dominating u=f(X¯u)=(u1,u2,…,un).There are different approaches to solving multiobjective optimization problems [24, 25], for example, aggregating, population based non-Pareto and Pareto-based techniques. Vector evaluated genetic algorithm (VEGA) is a technique in the population based non-Pareto approach in which different subpopulations are used for the different objectives. Multiple objective GA (MOGA), nondominated sorting GA (NSGA), and niched Pareto GA (NPGA) constitute a number of techniques under the Pareto-based nonelitist approaches [25]. NSGA-II [26], SPEA [27], and SPEA2 [28] are some recently developed multiobjective elitist techniques.As a multiobjective genetic algorithm, NSGA-II algorithm is a mature multiobjective elite selection algorithm. Compared with the NSGA, the NSGA-II has been improved in three aspects:(1) when constructing the Pareto optimal solution set, the time complexity of the algorithm is reduced from O(mN3) to O(mN2) by adopting a new rank-based fast nondominated sorting method. (2) The elitist reservation mechanism is proposed. After selection, offsprings from breeding individuals compete with their parents to produce the next generation. The new optimal individual reservation mechanism can not only improve the performance of multiobjective evolutionary algorithm (MOEA) but also effectively prevent the loss of the optimal solution and improve the overall evolutionary level of the population. (3) In order to calibrate the fitness values of different elements at the same level after rapid nondominated sorting and to make the individuals in the Pareto frontier extend to the front of the entire frontier Pareto, the crowded distance comparison operator is used instead of the original fitness sharing method.The present paper uses NSGA-II as the underlying multiobjective algorithm for developing the proposed fuzzy clustering method.


## 2.1. FuzzyC-Means Algorithm

Suppose that fuzzyc-means (FCM) partitions a set of n data objects X={x1,x2,…,xn}n×p into c  (1≤c≤n) fuzzy clusters, where each object has p attributes. Let V={v1,v2,…,vc}c×p be a set of cluster centers. Let U=uikc×n be a c×n matrix of membership degrees in which uik is the membership degree of kth object to the cth cluster center. The matrix satisfies the conditions(1)∑i=1cuik=1,uik≥0,uik∈0,1.The FCM algorithm uses the objective function to solve the optimal clustering, which is a clear difference from the hard clustering algorithm. The objective functionJFCM can be defined as follows:(2)JFCM=∑i=1c∑k=1nuikmxk-vi.In (2), m is the fuzzification coefficient, representing the fuzzy degree of clustering. Define m=2. xk-vi means the Euclidean distance between the kth data points and the first ith cluster centers, which represents the in-class similarity. A good clustering algorithm should ensure that the distance between similar points in the clustering result is as compact as possible. The standard FCM uses the JFCM as a cost function to be minimized.The minimization ofJFCM can be achieved by Lagrange multiplier method under constraint ∑i=1cuik=1, k=1,2,…,n, while the membership degrees matrix U and cluster centers are updated according to(3)uik=∑t=1cxk-vixk-vt-2/m-1,(4)vi=∑k=1nuikmxk∑k=1nuikm.By iteration, the algorithm ends when conditionJFCM(t)-JFCM(t+1)<ε is satisfied, where ε is a small positive number representing the end of iteration threshold.


## 2.2. Multiobjective Optimization Based on Genetic Algorithm

Unlike single-objective optimization algorithms, the multiobjective optimization algorithm optimizes multiple objective functions simultaneously. Because it is necessary to optimize multiple conflicting objectives simultaneously, it is often difficult to find a solution to make all the objective functions reach the optimum simultaneously. For multiobjective optimization algorithms, each objective function is considered equally important when the relative importance of the goals is unknown. Therefore, the multiobjective optimization problem is not to optimize one solution, but to optimize one solution set, which is characterized by improving any objective function without impairing other objective functions. We call this solution a nondominated solution or a Pareto optimal solution, which is defined as follows [24].For minimizing the multiobjective problem, a vector ofn target components fi(i=1,…,n) is (5)f¯X¯=f1X¯,f2X¯,…,fnX¯,where X¯u∈U is the decision variable. If X¯u is the Pareto optimal solution, it needs to be satisfied: only if X¯v∈U, there is no decision variable v=f(X¯v)=(v1,v2,…,vn), dominating u=f(X¯u)=(u1,u2,…,un).There are different approaches to solving multiobjective optimization problems [24, 25], for example, aggregating, population based non-Pareto and Pareto-based techniques. Vector evaluated genetic algorithm (VEGA) is a technique in the population based non-Pareto approach in which different subpopulations are used for the different objectives. Multiple objective GA (MOGA), nondominated sorting GA (NSGA), and niched Pareto GA (NPGA) constitute a number of techniques under the Pareto-based nonelitist approaches [25]. NSGA-II [26], SPEA [27], and SPEA2 [28] are some recently developed multiobjective elitist techniques.As a multiobjective genetic algorithm, NSGA-II algorithm is a mature multiobjective elite selection algorithm. Compared with the NSGA, the NSGA-II has been improved in three aspects:(1) when constructing the Pareto optimal solution set, the time complexity of the algorithm is reduced from O(mN3) to O(mN2) by adopting a new rank-based fast nondominated sorting method. (2) The elitist reservation mechanism is proposed. After selection, offsprings from breeding individuals compete with their parents to produce the next generation. The new optimal individual reservation mechanism can not only improve the performance of multiobjective evolutionary algorithm (MOEA) but also effectively prevent the loss of the optimal solution and improve the overall evolutionary level of the population. (3) In order to calibrate the fitness values of different elements at the same level after rapid nondominated sorting and to make the individuals in the Pareto frontier extend to the front of the entire frontier Pareto, the crowded distance comparison operator is used instead of the original fitness sharing method.The present paper uses NSGA-II as the underlying multiobjective algorithm for developing the proposed fuzzy clustering method.


## 3. Dynamic Fuzzy Clustering Method Based on Adaptive NSGA-II

### 3.1. Chromosome Representation

In general, there are two kinds of chromosome coding schemes to solve the clustering problem by using genetic algorithm:(1) numerical coding based on the clustering center; (2) encoding based on the partition matrix U [29]. Since the genetic operator in this paper uses the variable chromosome length operation, the first chromosome coding scheme is adopted.DefinitionQi denotes a chromosome that represents ci(1<ci<n) cluster centers with d dimensional attribute space. The coding form can be expressed as(6)Qi=g11,g21,…,gd1,g12,g22,…,gd2,…,g1ci,g2ci,…,gdci.Figure 1 shows an example of a chromosome comprising five centers {C1,C2,C3,C4,C5} in two dimensions.Figure 1
Chromosome representation.It uses the sequence form of real value to describe the chromosome, avoids the complex encoding form of binary form, and can display the practical significance of the representation more intuitively.


### 3.2. Population Initialization

The selection of initial cluster centers will have a great impact on the final clustering results. However, due to the crossover operator that dynamically changes the chromosome length, the fixed initial cluster centers are not conducive to maintaining the diversity of the population. Therefore, this paper uses the most common method of random given initial cluster centers to initialize the population.Note that, for the sample datasets, the range ofd attribute values may not be the same, which can have a significant impact on the calculation of the NSGA-II algorithm. Therefore, it is necessary to standardize the sample data set, Max-Min Normalization first needs to be performed on the sample dataset to reduce the possible error. The Max-Min Normalization is defined as follows:(7)xnormalization=x-MinMax-Min.


### 3.3. Selection of Fitness Function

The performance of multiobjective optimization is highly dependent on the choice of objective function, which can produce good results by reasonably selecting the objective function. The selection of objective functions should be such so that they can balance each other critically and are possibly contradictory in nature. Contradiction in the objective functions is beneficial since it guides to global optimum solution. It also ensures that no single clustering objective is optimized leaving the other probable significant objectives unnoticed.In this paper, two kinds of fitness functions, DB Index and IndexI, are used as objective functions for NSGA-II algorithm. The two fitness functions are described in detail below.


#### 3.3.1. Davies-Bouldin (DB) Index

DB Index [30] is a commonly used cluster validity index. This index is the ratio function of the sum of within-cluster scatter to between-cluster separation.Define the scatter of theith class as(8)Si=1Ci∑j=1Cixj-ziq1/q,where xj denotes the data point in the ith class and zi denotes the center of the ith class; |Ci| represents the number of data points in the ith class; q is an index value. The distance between cluster center zi and zj, is defined as Mij=zi-zj. The similarity between ith cluster and jth cluster is defined as(9)Rij=maxi,i≠j⁡Si+SjMij.The Davies-Bouldin (DB) index is then defined as(10)DB=1N∑i=1NRij.The objective is to minimize the DB index for achieving proper clustering.


#### 3.3.2. IndexI

IndexI [31] is another commonly used cluster validity index. (11)Ic=1c×E1Ec×DcP,where c is the number of clusters. Here, Ec stand for within-cluster scatter, defined as(12)Ec=∑i=1c∑j=1nuijxj-zi,D c stand for between-cluster separation, defined as(13)Dc=maxi,j=1czi-zj,E 1 and p are correlation coefficients. The power p is used to control the contrast between the different cluster configurations, in general, p≥1. In this article, we have taken p=1.  E1 is a constant for a given dataset, normalized to avoid the minimum value of the indicator. The value of K for which I(c) is maximized is considered to be the correct number of clusters.The goal in this paper is to minimizeDB and 1/I(c) simultaneously. At the same time, pay attention to adjust the correlation coefficient E1 in I(c). By adjusting the parameters, the values of DB and 1/I(c) are in the same order of magnitude, avoiding the selection error caused by too large a target value. At the same time, in the use of the algorithm, it can be found that, with the increase of the number of clusters c, the value of 1/I(c) begins to decrease, and the value of DB begins to increase, which conforms to the conflicting requirements of the two objective functions mentioned earlier.


### 3.4. Genetic Manipulation

#### 3.4.1. Selection

The two individuals are randomly selected to play a tournament and the winner is selected by the crowded comparison operator. This operator takes into account two attributes of the nondominant rank and the crowded distance. If two individuals are at different levels, the lower level is preferred. If both individuals are at the same level, choose a solution that has less crowded region.


#### 3.4.2. Crossover

After selection, the selected chromosomes are placed in the mating pool. The performance of crossover operator will determine the performance of genetic manipulation to a great extent. Because of the variable-length encoding used in chromosome coding, the conventional one-point crossover approach does not apply to the current situation. In this paper, the following two crossover methods are used to perform crossover operation with the same probability.(  1) Based on the Nearest Neighbor Matching Crossover Operation. Let two parents S1=[a1,a2,…,ac1] and S2=[b1,b2,…,bc2] denote parent solutions with c1 and c2 cluster centers. Assume that we are in the case of c1≤c2, select the gene string ai=(ai1,ai2,…,aid) in turn, which represents each cluster center in S1, and select the nearest distance ai string bi=(bi1,bi2,…,bid) from S2 to match them. Already paired gene strings are no longer involved in pairing. Reordering the previous c1 gene strings in S2, choose a point randomly from within 0~c1×d. For S1 and S2, traditional crossover operations are used to generate new offspring S3 and S4.By using this crossover method, the offsprings maintain the same number of cluster centers as their parents and maintain the stability of the population. Using gene rearrangements before crossover can make the different chromosomes have the most similar cluster centers in the same position, avoid the generation of poor offspring when crossing and then lead to population degradation. The crossover operation can be illustrated in Figure2.Figure 2
Crossover method 1.(  2) Based on the Truncation and Stitching Cross Operation.Different from the first method, the crossover operation based on truncation and stitching will produce the offsprings which are different from the number of the parent cluster centers, so as to maintain the diversity of the population. In this crossover operation, the string representing each cluster center is indivisible and can only be crossed at different gene strings.The operation is described as follows:S1 and S2 are two parent individuals, where(14)S1c1×d=a1,a2,…,at1∣at1+1,…,ac1,S2c2×d=b1,b2,…,bt2∣bt2+1,…,bc2.Suppose that the intersection points ofS1 and S2 are t1 and t2, respectively. The offsprings S3 and S4 generated after crossing can be expressed as(15)S3c2+t1-t2×d=a1,a2,…,at1∣bt2+1,…,bc2,S4c1+t2-t1×d=b1,b2,…,bt2∣at1+1,…,ac1.The number of cluster centers represented byS3 and S4 is (c2+t1-t2) and (c1+t2-t1), respectively. The crossover operation can be illustrated in Figure 3.Figure 3
Crossover method 2.


#### 3.4.3. Mutation

Individuals are mutated according to gene loci, and random variation is usually made according to the variation probabilityPm. If the chromosome is selected for mutation, the location of the mutated gene will be selected randomly. After mutating, the floating point number at the gene site is replaced by another uniform random number.


#### 3.4.4. Adaptive Operation

By using the adaptive strategy of crossover probabilityPc and mutation probability Pm, the two parameters can be automatically changed according to the fitness of the current population. For the whole population, when the fitness value of the population tends to be consistent or tends to local optimum, the Pc and Pm increase appropriately; when the fitness value is dispersed, Pc and Pm are appropriately reduced. For an individual in a population, when its fitness is higher than the average fitness of the population, the lower Pc and Pm values make it more likely to enter the next generation; when the current fitness value is lower than the average fitness value, the higher Pc and Pm values will be given to make it more likely to be eliminated. Thus, the adaptive strategy can provide the best Pc and Pm for the solution [32]. Pc and Pm are calculated as follows:(16)Pc=pc1-0.6fmax-f∗fmax-fmeanf∗≥fmeanpc1f∗<fmeanPm=pm1-0.001fmax-ffmax-fmeanf≥fmeanpm1f<fmean,where f∗ is the larger fitness value of two individuals to be cross-operated, f is the fitness value of the current individual, fmax is the maximum fitness value of the current generation, and fmean is the average fitness of the current generation, pc1=0.9, pm1=0.1. It should be noted that the fitness value mentioned here is the sum of two objective function values. When an individual’s fitness value is the maximum fitness value of a contemporary population, we set its Pc and Pm to 0.6 and 0.001, respectively.


#### 3.4.5. Selecting a Solution from the Nondominated Set

In this paper, the majority voting method is used to determine the number of clustersc. That is to say, in the dominant set, the number of occurrences of a cluster in the whole dominating cluster is more than 50% of the total number of occurrences, and the same number continuously appears more than 5 generations; we think it is the optimal cluster number. If the algorithm still cannot choose the optimal cluster number at the specified maximum number of iterations, c corresponding to the best individual in the final generation is taken as the optimal cluster number.


#### 3.4.6. Determine the Final Clustering Result

After the number of clusters is determined, all the individuals whose population number is equal toc are selected to form a new population for clustering. The method is to use a combination of Canonical Genetic Algorithm (CGA) and FCM algorithms. The crossover operation used here only uses the nearest neighbor matching cross operation mentioned above, so it will not change the number of clusters. By combining the global optimization algorithm with FCM, this can effectively overcome the problem that the FCM algorithm can only obtain the local optimal solution. Finally, the algorithm will terminate after the objective function value JFCM no longer changes obviously, and the obtained result is the optimal clustering result.At this point, the relevant concepts of the algorithm have been described. Algorithm1 shows the steps of the ADNSGA2-FCM algorithm.Algorithm 1:ADNSGA2-FCM.
input: Dataset ( 1 ) Initialize parameters FCM and NSGA-II including population size Pop, itermax, ε, m, pc1, pm1, Tmax. ( 2 ) Random to select initial number of clusters c and random to generate initial cluster centers to create a initialize population P(0). ( 3 ) Decode each individual to obtain the cluster centers, and calculate the membership degrees U using Eq. (3). ( 4 ) Calculate new cluster centers V of each individual using Eq. (4) based on U and V ( 5 ) Calculate the JFCM of each individual using Eq. (2) based on U and V ( 6 ) Calculate fitness values f1 and f2 of each individual using Eq. (10) and (11). Calculate f = f 1 + f 2, store fmax and fmean at each iteration. ( 7 ) Non-dominated sorting and crowding distance operation for population. ( 8 ) Using the crowded comparison operator to select. ( 9 ) Calculate Pc and Pm using Eq. (16). ( 10 ) Generate offspring using genetic operation. ( 11 ) Recombination current generation and offspring to select next generation using elitism operation. ( 12 ) Using majority voting technique to determine the number of cluster c. ( 13 ) If the number c satisfies the selection condition, go to step (14); else go to step (3). ( 14 ) Find all chromosomes whose cluster numbers are equal to c from the population in step (11). The new population is composed of these chromosomes. ( 15 ) Decode each individual to obtain the cluster centers, and calculate the membership degrees U using Eq. (3). ( 16 ) Calculate new cluster centers V of each individual using Eq. (4) based on U and V ( 17 ) Calculate the JFCM of each individual using Eq. (2) based on U and V ( 18 ) Calculate fitness values f1 and f2 of each individual using Eq. (10) and (11). Calculate f=f1+f2, store fmax and fmean at each iteration. ( 19 ) Non-dominated sorting and crowding distance operation for population. ( 20 ) Using the crowded comparison operator to select. ( 21 ) Calculate Pc and Pm using Eq. (16). ( 22 ) Generate offspring using genetic operation. ( 23 ) Recombination current generation and offspring to select next generation using elitism operation. ( 24 ) If ADNSGA2-FCM has not met the stopping criterion (ft+1¯-ft¯<ε and t<Tmax), else t=t+1 and go to step (14). ( 25 )  Return the best individual (min⁡JFCM(t)).


### 3.5. Time Complexity

The ADNSGA2-FCM algorithm has a worse-caseO(GPNcmaxd) time complexity, where G denotes the number of generations, P is population size, N is the size of data, cmax is maximum number of clusters, and d are data dimensions.(1)
In the initial stage of population, the time required iscmaxd and each string contains d dimensional features until the population size P is full. Therefore, this construction requires O(Pcmaxd).(2)
In FCM clustering for each individual, suppose the number of data in the current data set isN, both procedures of membership assignment and updating of center values take Ncmaxd time. For the population, the time complexity is O(PNcmaxd).(3)
The time complexity of the two objective functions DB Index and IndexI are both O(N).(4)
The time complexity of each execution of crossover and mutation operators isO(Pcmaxd).(5)
The nondominated sorting in NSGA-II needsMP time for each solution to compare with every other solution to find if it is dominated. M is the number of objectives and a maximum number of the nondominated solutions equals the population size P. The comparison for all population members therefore requires O(MP2) time, where M=2.(6)
In the label assignment for each nondominated solution,Ncmaxd time is required to assign label for every data point. To select the best solution from P nondominated solutions, this yields O(PNcmaxd) time.It can be seen that the time complexity of the algorithm is worse, and the complexity of each generation in the worst case isO(PNcmaxd). Assuming that the algorithm runs G generation, the time complexity is O(GPNcmaxd).


## 3.1. Chromosome Representation

In general, there are two kinds of chromosome coding schemes to solve the clustering problem by using genetic algorithm:(1) numerical coding based on the clustering center; (2) encoding based on the partition matrix U [29]. Since the genetic operator in this paper uses the variable chromosome length operation, the first chromosome coding scheme is adopted.DefinitionQi denotes a chromosome that represents ci(1<ci<n) cluster centers with d dimensional attribute space. The coding form can be expressed as(6)Qi=g11,g21,…,gd1,g12,g22,…,gd2,…,g1ci,g2ci,…,gdci.Figure 1 shows an example of a chromosome comprising five centers {C1,C2,C3,C4,C5} in two dimensions.Figure 1
Chromosome representation.It uses the sequence form of real value to describe the chromosome, avoids the complex encoding form of binary form, and can display the practical significance of the representation more intuitively.


## 3.2. Population Initialization

The selection of initial cluster centers will have a great impact on the final clustering results. However, due to the crossover operator that dynamically changes the chromosome length, the fixed initial cluster centers are not conducive to maintaining the diversity of the population. Therefore, this paper uses the most common method of random given initial cluster centers to initialize the population.Note that, for the sample datasets, the range ofd attribute values may not be the same, which can have a significant impact on the calculation of the NSGA-II algorithm. Therefore, it is necessary to standardize the sample data set, Max-Min Normalization first needs to be performed on the sample dataset to reduce the possible error. The Max-Min Normalization is defined as follows:(7)xnormalization=x-MinMax-Min.


## 3.3. Selection of Fitness Function

The performance of multiobjective optimization is highly dependent on the choice of objective function, which can produce good results by reasonably selecting the objective function. The selection of objective functions should be such so that they can balance each other critically and are possibly contradictory in nature. Contradiction in the objective functions is beneficial since it guides to global optimum solution. It also ensures that no single clustering objective is optimized leaving the other probable significant objectives unnoticed.In this paper, two kinds of fitness functions, DB Index and IndexI, are used as objective functions for NSGA-II algorithm. The two fitness functions are described in detail below.


### 3.3.1. Davies-Bouldin (DB) Index

DB Index [30] is a commonly used cluster validity index. This index is the ratio function of the sum of within-cluster scatter to between-cluster separation.Define the scatter of theith class as(8)Si=1Ci∑j=1Cixj-ziq1/q,where xj denotes the data point in the ith class and zi denotes the center of the ith class; |Ci| represents the number of data points in the ith class; q is an index value. The distance between cluster center zi and zj, is defined as Mij=zi-zj. The similarity between ith cluster and jth cluster is defined as(9)Rij=maxi,i≠j⁡Si+SjMij.The Davies-Bouldin (DB) index is then defined as(10)DB=1N∑i=1NRij.The objective is to minimize the DB index for achieving proper clustering.


### 3.3.2. IndexI

IndexI [31] is another commonly used cluster validity index. (11)Ic=1c×E1Ec×DcP,where c is the number of clusters. Here, Ec stand for within-cluster scatter, defined as(12)Ec=∑i=1c∑j=1nuijxj-zi,D c stand for between-cluster separation, defined as(13)Dc=maxi,j=1czi-zj,E 1 and p are correlation coefficients. The power p is used to control the contrast between the different cluster configurations, in general, p≥1. In this article, we have taken p=1.  E1 is a constant for a given dataset, normalized to avoid the minimum value of the indicator. The value of K for which I(c) is maximized is considered to be the correct number of clusters.The goal in this paper is to minimizeDB and 1/I(c) simultaneously. At the same time, pay attention to adjust the correlation coefficient E1 in I(c). By adjusting the parameters, the values of DB and 1/I(c) are in the same order of magnitude, avoiding the selection error caused by too large a target value. At the same time, in the use of the algorithm, it can be found that, with the increase of the number of clusters c, the value of 1/I(c) begins to decrease, and the value of DB begins to increase, which conforms to the conflicting requirements of the two objective functions mentioned earlier.


## 3.3.1. Davies-Bouldin (DB) Index

DB Index [30] is a commonly used cluster validity index. This index is the ratio function of the sum of within-cluster scatter to between-cluster separation.Define the scatter of theith class as(8)Si=1Ci∑j=1Cixj-ziq1/q,where xj denotes the data point in the ith class and zi denotes the center of the ith class; |Ci| represents the number of data points in the ith class; q is an index value. The distance between cluster center zi and zj, is defined as Mij=zi-zj. The similarity between ith cluster and jth cluster is defined as(9)Rij=maxi,i≠j⁡Si+SjMij.The Davies-Bouldin (DB) index is then defined as(10)DB=1N∑i=1NRij.The objective is to minimize the DB index for achieving proper clustering.


## 3.3.2. IndexI

IndexI [31] is another commonly used cluster validity index. (11)Ic=1c×E1Ec×DcP,where c is the number of clusters. Here, Ec stand for within-cluster scatter, defined as(12)Ec=∑i=1c∑j=1nuijxj-zi,D c stand for between-cluster separation, defined as(13)Dc=maxi,j=1czi-zj,E 1 and p are correlation coefficients. The power p is used to control the contrast between the different cluster configurations, in general, p≥1. In this article, we have taken p=1.  E1 is a constant for a given dataset, normalized to avoid the minimum value of the indicator. The value of K for which I(c) is maximized is considered to be the correct number of clusters.The goal in this paper is to minimizeDB and 1/I(c) simultaneously. At the same time, pay attention to adjust the correlation coefficient E1 in I(c). By adjusting the parameters, the values of DB and 1/I(c) are in the same order of magnitude, avoiding the selection error caused by too large a target value. At the same time, in the use of the algorithm, it can be found that, with the increase of the number of clusters c, the value of 1/I(c) begins to decrease, and the value of DB begins to increase, which conforms to the conflicting requirements of the two objective functions mentioned earlier.


## 3.4. Genetic Manipulation

### 3.4.1. Selection

The two individuals are randomly selected to play a tournament and the winner is selected by the crowded comparison operator. This operator takes into account two attributes of the nondominant rank and the crowded distance. If two individuals are at different levels, the lower level is preferred. If both individuals are at the same level, choose a solution that has less crowded region.


### 3.4.2. Crossover

After selection, the selected chromosomes are placed in the mating pool. The performance of crossover operator will determine the performance of genetic manipulation to a great extent. Because of the variable-length encoding used in chromosome coding, the conventional one-point crossover approach does not apply to the current situation. In this paper, the following two crossover methods are used to perform crossover operation with the same probability.(  1) Based on the Nearest Neighbor Matching Crossover Operation. Let two parents S1=[a1,a2,…,ac1] and S2=[b1,b2,…,bc2] denote parent solutions with c1 and c2 cluster centers. Assume that we are in the case of c1≤c2, select the gene string ai=(ai1,ai2,…,aid) in turn, which represents each cluster center in S1, and select the nearest distance ai string bi=(bi1,bi2,…,bid) from S2 to match them. Already paired gene strings are no longer involved in pairing. Reordering the previous c1 gene strings in S2, choose a point randomly from within 0~c1×d. For S1 and S2, traditional crossover operations are used to generate new offspring S3 and S4.By using this crossover method, the offsprings maintain the same number of cluster centers as their parents and maintain the stability of the population. Using gene rearrangements before crossover can make the different chromosomes have the most similar cluster centers in the same position, avoid the generation of poor offspring when crossing and then lead to population degradation. The crossover operation can be illustrated in Figure2.Figure 2
Crossover method 1.(  2) Based on the Truncation and Stitching Cross Operation.Different from the first method, the crossover operation based on truncation and stitching will produce the offsprings which are different from the number of the parent cluster centers, so as to maintain the diversity of the population. In this crossover operation, the string representing each cluster center is indivisible and can only be crossed at different gene strings.The operation is described as follows:S1 and S2 are two parent individuals, where(14)S1c1×d=a1,a2,…,at1∣at1+1,…,ac1,S2c2×d=b1,b2,…,bt2∣bt2+1,…,bc2.Suppose that the intersection points ofS1 and S2 are t1 and t2, respectively. The offsprings S3 and S4 generated after crossing can be expressed as(15)S3c2+t1-t2×d=a1,a2,…,at1∣bt2+1,…,bc2,S4c1+t2-t1×d=b1,b2,…,bt2∣at1+1,…,ac1.The number of cluster centers represented byS3 and S4 is (c2+t1-t2) and (c1+t2-t1), respectively. The crossover operation can be illustrated in Figure 3.Figure 3
Crossover method 2.


### 3.4.3. Mutation

Individuals are mutated according to gene loci, and random variation is usually made according to the variation probabilityPm. If the chromosome is selected for mutation, the location of the mutated gene will be selected randomly. After mutating, the floating point number at the gene site is replaced by another uniform random number.


### 3.4.4. Adaptive Operation

By using the adaptive strategy of crossover probabilityPc and mutation probability Pm, the two parameters can be automatically changed according to the fitness of the current population. For the whole population, when the fitness value of the population tends to be consistent or tends to local optimum, the Pc and Pm increase appropriately; when the fitness value is dispersed, Pc and Pm are appropriately reduced. For an individual in a population, when its fitness is higher than the average fitness of the population, the lower Pc and Pm values make it more likely to enter the next generation; when the current fitness value is lower than the average fitness value, the higher Pc and Pm values will be given to make it more likely to be eliminated. Thus, the adaptive strategy can provide the best Pc and Pm for the solution [32]. Pc and Pm are calculated as follows:(16)Pc=pc1-0.6fmax-f∗fmax-fmeanf∗≥fmeanpc1f∗<fmeanPm=pm1-0.001fmax-ffmax-fmeanf≥fmeanpm1f<fmean,where f∗ is the larger fitness value of two individuals to be cross-operated, f is the fitness value of the current individual, fmax is the maximum fitness value of the current generation, and fmean is the average fitness of the current generation, pc1=0.9, pm1=0.1. It should be noted that the fitness value mentioned here is the sum of two objective function values. When an individual’s fitness value is the maximum fitness value of a contemporary population, we set its Pc and Pm to 0.6 and 0.001, respectively.


### 3.4.5. Selecting a Solution from the Nondominated Set

In this paper, the majority voting method is used to determine the number of clustersc. That is to say, in the dominant set, the number of occurrences of a cluster in the whole dominating cluster is more than 50% of the total number of occurrences, and the same number continuously appears more than 5 generations; we think it is the optimal cluster number. If the algorithm still cannot choose the optimal cluster number at the specified maximum number of iterations, c corresponding to the best individual in the final generation is taken as the optimal cluster number.


### 3.4.6. Determine the Final Clustering Result

After the number of clusters is determined, all the individuals whose population number is equal toc are selected to form a new population for clustering. The method is to use a combination of Canonical Genetic Algorithm (CGA) and FCM algorithms. The crossover operation used here only uses the nearest neighbor matching cross operation mentioned above, so it will not change the number of clusters. By combining the global optimization algorithm with FCM, this can effectively overcome the problem that the FCM algorithm can only obtain the local optimal solution. Finally, the algorithm will terminate after the objective function value JFCM no longer changes obviously, and the obtained result is the optimal clustering result.At this point, the relevant concepts of the algorithm have been described. Algorithm1 shows the steps of the ADNSGA2-FCM algorithm.Algorithm 1:ADNSGA2-FCM.
input: Dataset ( 1 ) Initialize parameters FCM and NSGA-II including population size Pop, itermax, ε, m, pc1, pm1, Tmax. ( 2 ) Random to select initial number of clusters c and random to generate initial cluster centers to create a initialize population P(0). ( 3 ) Decode each individual to obtain the cluster centers, and calculate the membership degrees U using Eq. (3). ( 4 ) Calculate new cluster centers V of each individual using Eq. (4) based on U and V ( 5 ) Calculate the JFCM of each individual using Eq. (2) based on U and V ( 6 ) Calculate fitness values f1 and f2 of each individual using Eq. (10) and (11). Calculate f = f 1 + f 2, store fmax and fmean at each iteration. ( 7 ) Non-dominated sorting and crowding distance operation for population. ( 8 ) Using the crowded comparison operator to select. ( 9 ) Calculate Pc and Pm using Eq. (16). ( 10 ) Generate offspring using genetic operation. ( 11 ) Recombination current generation and offspring to select next generation using elitism operation. ( 12 ) Using majority voting technique to determine the number of cluster c. ( 13 ) If the number c satisfies the selection condition, go to step (14); else go to step (3). ( 14 ) Find all chromosomes whose cluster numbers are equal to c from the population in step (11). The new population is composed of these chromosomes. ( 15 ) Decode each individual to obtain the cluster centers, and calculate the membership degrees U using Eq. (3). ( 16 ) Calculate new cluster centers V of each individual using Eq. (4) based on U and V ( 17 ) Calculate the JFCM of each individual using Eq. (2) based on U and V ( 18 ) Calculate fitness values f1 and f2 of each individual using Eq. (10) and (11). Calculate f=f1+f2, store fmax and fmean at each iteration. ( 19 ) Non-dominated sorting and crowding distance operation for population. ( 20 ) Using the crowded comparison operator to select. ( 21 ) Calculate Pc and Pm using Eq. (16). ( 22 ) Generate offspring using genetic operation. ( 23 ) Recombination current generation and offspring to select next generation using elitism operation. ( 24 ) If ADNSGA2-FCM has not met the stopping criterion (ft+1¯-ft¯<ε and t<Tmax), else t=t+1 and go to step (14). ( 25 )  Return the best individual (min⁡JFCM(t)).


## 3.4.1. Selection

The two individuals are randomly selected to play a tournament and the winner is selected by the crowded comparison operator. This operator takes into account two attributes of the nondominant rank and the crowded distance. If two individuals are at different levels, the lower level is preferred. If both individuals are at the same level, choose a solution that has less crowded region.


## 3.4.2. Crossover

After selection, the selected chromosomes are placed in the mating pool. The performance of crossover operator will determine the performance of genetic manipulation to a great extent. Because of the variable-length encoding used in chromosome coding, the conventional one-point crossover approach does not apply to the current situation. In this paper, the following two crossover methods are used to perform crossover operation with the same probability.(  1) Based on the Nearest Neighbor Matching Crossover Operation. Let two parents S1=[a1,a2,…,ac1] and S2=[b1,b2,…,bc2] denote parent solutions with c1 and c2 cluster centers. Assume that we are in the case of c1≤c2, select the gene string ai=(ai1,ai2,…,aid) in turn, which represents each cluster center in S1, and select the nearest distance ai string bi=(bi1,bi2,…,bid) from S2 to match them. Already paired gene strings are no longer involved in pairing. Reordering the previous c1 gene strings in S2, choose a point randomly from within 0~c1×d. For S1 and S2, traditional crossover operations are used to generate new offspring S3 and S4.By using this crossover method, the offsprings maintain the same number of cluster centers as their parents and maintain the stability of the population. Using gene rearrangements before crossover can make the different chromosomes have the most similar cluster centers in the same position, avoid the generation of poor offspring when crossing and then lead to population degradation. The crossover operation can be illustrated in Figure2.Figure 2
Crossover method 1.(  2) Based on the Truncation and Stitching Cross Operation.Different from the first method, the crossover operation based on truncation and stitching will produce the offsprings which are different from the number of the parent cluster centers, so as to maintain the diversity of the population. In this crossover operation, the string representing each cluster center is indivisible and can only be crossed at different gene strings.The operation is described as follows:S1 and S2 are two parent individuals, where(14)S1c1×d=a1,a2,…,at1∣at1+1,…,ac1,S2c2×d=b1,b2,…,bt2∣bt2+1,…,bc2.Suppose that the intersection points ofS1 and S2 are t1 and t2, respectively. The offsprings S3 and S4 generated after crossing can be expressed as(15)S3c2+t1-t2×d=a1,a2,…,at1∣bt2+1,…,bc2,S4c1+t2-t1×d=b1,b2,…,bt2∣at1+1,…,ac1.The number of cluster centers represented byS3 and S4 is (c2+t1-t2) and (c1+t2-t1), respectively. The crossover operation can be illustrated in Figure 3.Figure 3
Crossover method 2.


## 3.4.3. Mutation

Individuals are mutated according to gene loci, and random variation is usually made according to the variation probabilityPm. If the chromosome is selected for mutation, the location of the mutated gene will be selected randomly. After mutating, the floating point number at the gene site is replaced by another uniform random number.


## 3.4.4. Adaptive Operation

By using the adaptive strategy of crossover probabilityPc and mutation probability Pm, the two parameters can be automatically changed according to the fitness of the current population. For the whole population, when the fitness value of the population tends to be consistent or tends to local optimum, the Pc and Pm increase appropriately; when the fitness value is dispersed, Pc and Pm are appropriately reduced. For an individual in a population, when its fitness is higher than the average fitness of the population, the lower Pc and Pm values make it more likely to enter the next generation; when the current fitness value is lower than the average fitness value, the higher Pc and Pm values will be given to make it more likely to be eliminated. Thus, the adaptive strategy can provide the best Pc and Pm for the solution [32]. Pc and Pm are calculated as follows:(16)Pc=pc1-0.6fmax-f∗fmax-fmeanf∗≥fmeanpc1f∗<fmeanPm=pm1-0.001fmax-ffmax-fmeanf≥fmeanpm1f<fmean,where f∗ is the larger fitness value of two individuals to be cross-operated, f is the fitness value of the current individual, fmax is the maximum fitness value of the current generation, and fmean is the average fitness of the current generation, pc1=0.9, pm1=0.1. It should be noted that the fitness value mentioned here is the sum of two objective function values. When an individual’s fitness value is the maximum fitness value of a contemporary population, we set its Pc and Pm to 0.6 and 0.001, respectively.


## 3.4.5. Selecting a Solution from the Nondominated Set

In this paper, the majority voting method is used to determine the number of clustersc. That is to say, in the dominant set, the number of occurrences of a cluster in the whole dominating cluster is more than 50% of the total number of occurrences, and the same number continuously appears more than 5 generations; we think it is the optimal cluster number. If the algorithm still cannot choose the optimal cluster number at the specified maximum number of iterations, c corresponding to the best individual in the final generation is taken as the optimal cluster number.


## 3.4.6. Determine the Final Clustering Result

After the number of clusters is determined, all the individuals whose population number is equal toc are selected to form a new population for clustering. The method is to use a combination of Canonical Genetic Algorithm (CGA) and FCM algorithms. The crossover operation used here only uses the nearest neighbor matching cross operation mentioned above, so it will not change the number of clusters. By combining the global optimization algorithm with FCM, this can effectively overcome the problem that the FCM algorithm can only obtain the local optimal solution. Finally, the algorithm will terminate after the objective function value JFCM no longer changes obviously, and the obtained result is the optimal clustering result.At this point, the relevant concepts of the algorithm have been described. Algorithm1 shows the steps of the ADNSGA2-FCM algorithm.Algorithm 1:ADNSGA2-FCM.
input: Dataset ( 1 ) Initialize parameters FCM and NSGA-II including population size Pop, itermax, ε, m, pc1, pm1, Tmax. ( 2 ) Random to select initial number of clusters c and random to generate initial cluster centers to create a initialize population P(0). ( 3 ) Decode each individual to obtain the cluster centers, and calculate the membership degrees U using Eq. (3). ( 4 ) Calculate new cluster centers V of each individual using Eq. (4) based on U and V ( 5 ) Calculate the JFCM of each individual using Eq. (2) based on U and V ( 6 ) Calculate fitness values f1 and f2 of each individual using Eq. (10) and (11). Calculate f = f 1 + f 2, store fmax and fmean at each iteration. ( 7 ) Non-dominated sorting and crowding distance operation for population. ( 8 ) Using the crowded comparison operator to select. ( 9 ) Calculate Pc and Pm using Eq. (16). ( 10 ) Generate offspring using genetic operation. ( 11 ) Recombination current generation and offspring to select next generation using elitism operation. ( 12 ) Using majority voting technique to determine the number of cluster c. ( 13 ) If the number c satisfies the selection condition, go to step (14); else go to step (3). ( 14 ) Find all chromosomes whose cluster numbers are equal to c from the population in step (11). The new population is composed of these chromosomes. ( 15 ) Decode each individual to obtain the cluster centers, and calculate the membership degrees U using Eq. (3). ( 16 ) Calculate new cluster centers V of each individual using Eq. (4) based on U and V ( 17 ) Calculate the JFCM of each individual using Eq. (2) based on U and V ( 18 ) Calculate fitness values f1 and f2 of each individual using Eq. (10) and (11). Calculate f=f1+f2, store fmax and fmean at each iteration. ( 19 ) Non-dominated sorting and crowding distance operation for population. ( 20 ) Using the crowded comparison operator to select. ( 21 ) Calculate Pc and Pm using Eq. (16). ( 22 ) Generate offspring using genetic operation. ( 23 ) Recombination current generation and offspring to select next generation using elitism operation. ( 24 ) If ADNSGA2-FCM has not met the stopping criterion (ft+1¯-ft¯<ε and t<Tmax), else t=t+1 and go to step (14). ( 25 )  Return the best individual (min⁡JFCM(t)).


## 3.5. Time Complexity

The ADNSGA2-FCM algorithm has a worse-caseO(GPNcmaxd) time complexity, where G denotes the number of generations, P is population size, N is the size of data, cmax is maximum number of clusters, and d are data dimensions.(1)
In the initial stage of population, the time required iscmaxd and each string contains d dimensional features until the population size P is full. Therefore, this construction requires O(Pcmaxd).(2)
In FCM clustering for each individual, suppose the number of data in the current data set isN, both procedures of membership assignment and updating of center values take Ncmaxd time. For the population, the time complexity is O(PNcmaxd).(3)
The time complexity of the two objective functions DB Index and IndexI are both O(N).(4)
The time complexity of each execution of crossover and mutation operators isO(Pcmaxd).(5)
The nondominated sorting in NSGA-II needsMP time for each solution to compare with every other solution to find if it is dominated. M is the number of objectives and a maximum number of the nondominated solutions equals the population size P. The comparison for all population members therefore requires O(MP2) time, where M=2.(6)
In the label assignment for each nondominated solution,Ncmaxd time is required to assign label for every data point. To select the best solution from P nondominated solutions, this yields O(PNcmaxd) time.It can be seen that the time complexity of the algorithm is worse, and the complexity of each generation in the worst case isO(PNcmaxd). Assuming that the algorithm runs G generation, the time complexity is O(GPNcmaxd).


## 4. Experiment Study

In this paper, for the purpose of verifying the performance of the method proposed in this paper (ADNSGA2-FCM), some clustering algorithms are chosen for extensive comparative analysis. There are two kinds of soft subspace clustering algorithms ESSC [33] and MOEASSC [34]. MOEASSC is a multiobjective method and ESSC is a single-objective one. There are three kernel-based attribute weighting algorithms, VKCM-K-LP [35], VKFCM-K-LP [36], and MOKCW [37]. The MOKCW method is a multiobjective method; VKCM-K-LP and VKFCM-K-LP are single-objective methods. The VKCM-K-LP method is crisp version of clustering method, and the VKFCM-K-LP method is a fuzzy clustering method. The NSGA-II-FCM method is the nonadaptive version of ADNSGA2-FCM and used fixed parameters.


### 4.1. Datasets and Parameter Setting

For the purpose of comparison, there are two groups of data sets, artificial and real-life data sets. The three artificial data sets are Square 1, Square 4, and Sizes 5 from [20]. The six real-life data sets are obtained from the UCI Machine Learning Repository [38], namely, Iris, Wine, Newthyroid, Vertebral, Image, and Abalone. As shown in Table 1 the data sets considered are briefly described, where C is the true number of classes and d and n are, respectively, the number of features and objects. For most SSC algorithms, the experiments are conducted on the data sets standardized into the interval [0,1], which can alleviate the uneven impact of different attributes’ ranges on updating the weights. Therefore, the standardization is based on the minimum and maximum values of each attribute.Table 1
The characters of datasets.
Datasets C d n Square 1 4 2 1000 Square 4 4 2 1000 Sizes 5 4 2 1000 Iris 3 4 150 Wine 3 13 178 Newthyroid 3 5 215 Vertebral 3 6 310 Image 7 16 2310 Abalone 3 8 4177The parameters of the ADNSGA2-FCM algorithm are set as shown in Table2, the parameters of other algorithms are set as shown in Table 3.Table 2
Parameter settings for the ADNSGA2-FCM algorithm.
Parameter Setting Population size 40 Max number of generations 300 C m i n 2 C m a x n p c 1 0.9 p m 1 0.1Table 3
Parameter settings for other algorithms.
Algorithm Parameter setting ESSC m = m i n ( n , D - 1 ) m i n ( n , D - 1 ) - 2, γ=100, η=0.1 VKCM-K-LP m = 2 VKFCM-K-LP m = 2 MOEASSC P c = 0.5, Pm=KD, σ=10-7 MOKCW P m = 0.1, α=0.1 NSGA-II-FCM P c = 0.9, Pm=0.05


### 4.2. Experiment Result and Analysis

In the first experiment, the above nine data sets (Square 1, Square 4, Sizes 5, Iris, Wine, Newthyroid, Vertebral, Image, and Abalone) and the adjusted Rand Index (ARI) [39] are used here to evaluate the clustering quality of ADNSGA2-FCM algorithm, which is to be maximized. Table 4 summarizes the result obtained from ADNSGA2-FCM. The real number of clusters can be obtained by the ADNSGA2-FCM algorithm in nine datasets. From the ARI value, the ADNSGA2-FCM algorithm has a big difference to the nine data sets. This is mainly because the ADNSGA2-FCM algorithm uses the fuzzy c-means (FCM) method as the clustering method, but the FCM algorithm is suitable for allocating the data of the spherical clusters. Therefore, for six datasets of Square 1, Square 4, Sizes 5, Iris, Wine, and Newthyroid, the effect is better, and the effect of the other three data sets is poor. It also can be observed from Table 4 that, in all data sets, the optimal clustering result is obtained by the algorithm.Table 4
Adjusted Rand index (ARI) and the number of the clusters (C) obtained by ADNSGA2-FCM.
Dataset ActualC ADNSGA2-FCM C ARI Square 1 4 4 0.971 Square 4 4 4 0.830 Sizes 5 4 4 0.838 Iris 3 3 0.802 Wine 3 3 0.865 Newthyroid 3 3 0.843 Vertebral 3 3 0.316 Image 7 7 0.490 Abalone 3 3 0.160Figures4–6 compare the results from the three synthetic data sets (Square 1, Square 4, and Sizes 5) of data partitioning obtained by ADNSGA2-FCM with center markings and the true data partitioning. The algorithm performs well under the well-separated structures of Square 1 (Figure 4) and Square 4 (Figure 5) as well as the unequally sized clusters of Sizes 5 (Figure 6). The overlapping and unequally sized characteristic causes more misclassification of the data points which are at the borderline between clusters.Figure 4
Square 1 (C=4): (a) true solution and (b) data partition using ADNSGA2-FCM (ARI = 0.971).
(a) (b)Figure 5
Square 4 (C=4): (a) true solution and (b) data partition using ADNSGA2-FCM (ARI = 0.830).
(a) (b)Figure 6
Sizes 5 (C=4): (a) true solution and (b) data partition using ADNSGA2-FCM (ARI = 0.838).
(a) (b)In order to evaluate the performance of the clustering result of seven algorithms, three well-known external CVIs accuracy (Acc), rand index (RI) [40], and normalized mutual information (NMI) [33] are adopted here. They all take their values from the interval [0,1], in which 1 means the best match between the result and the true partition, whereas 0 means the worst result. In this experiment, all algorithms are executed 30 times independently, and their performances are compared in terms of the best case of Acc, RI, and NMI shown in Table 5. Among them, the best result is expressed in bold.Table 5
The result of all algorithms on Acc, RI and NMI.
DataSet ESSC VKCM-K-LP VKFCM-K-LP MOEASSC MOKCW NSGA-II-FCM ADNSGA2-FCM Iris Acc 0.839 0.955 0.947 0.900 0.960 0.920 0.927 RI 0.844 0.944 0.934 0.886 0.950 0.906 0.912 NMI 0.716 0.858 0.832 0.778 0.864 0.777 0.790 Wine Acc 0.955 0.907 0.938 0.956 0.921 0.944 0.955 RI 0.940 0.883 0.919 0.942 0.897 0.925 0.940 NMI 0.847 0.733 0.796 0.854 0.768 0.823 0.847 Newthyroid Acc 0.893 0.864 0.809 0.888 0.946 0.953 0.954 RI 0.826 0.834 0.737 0.818 0.913 0.922 0.922 NMI 0.620 0.655 0.541 0.603 0.772 0.786 0.787 Vertebral Acc 0.474 0.510 0.517 0.479 0.506 0.655 0.655 RI 0.633 0.667 0.661 0.623 0.697 0.683 0.685 NMI 0.269 0.350 0.330 0.249 0.431 0.286 0.302 Image Acc 0.606 0.624 0.623 0.620 0.635 0 0.658 RI 0.862 0.869 0.871 0.863 0.874 0 0.874 NMI 0.624 0.625 0.649 0.628 0.631 0 0.598 Abalone Acc 0.507 0.512 0.513 0.503 0.512 0.492 0.516 RI 0.612 0.619 0.619 0.610 0.619 0.610 0.625 NMI 0.163 0.162 0.165 0.161 0.163 0.166 0.168It can be firstly observed from Table5 that, in all data sets, the optimal clustering result is obtained by the multiobjective algorithm. This result can prove that the multiobjective clustering algorithm has some advantages compared with the single-objective clustering algorithm. For most data sets, the ADNSGA-FCM algorithm proposed in this paper can obtain the best results.For the data set Iris and Vertebral, the kernel-based multiobjective clustering algorithm MOKCW can achieve the best results. Compared with MOKCW algorithm and VKCM-K-LP algorithm, the two results are similar, and the result of ADNSGA2-FCM is worse. For the Vertebral data set, the ADNSGA2-FCM algorithm obtains the best Acc value. For the Wine data set, the MOEASSC algorithm can achieve the best effect, and the ADNSGA-FCM effect is very close to it. It shows that two kinds of multiobjective clustering methods based on evolutionary computation can obtain the best global results on Wine datasets. In the three datasets of Newthyroid, Image, and Abalone, ADNSGA2-FCM proposed in this paper has obvious advantages over other algorithms.From Table5 we can also see that the effect of the ADNSGA2-FCM algorithm using the adaptive mechanism is significantly better than the NSGA-II-FCM algorithm. Except that the two indicators are the same as ADNSGA2-FCM algorithm, the other indicators of NSGA-II-FCM are quite different from ADNSGA2-FCM algorithm. More obviously, in the Image dataset, the NSGA-II-FCM algorithm cannot obtain the correct number of clustering by 30 independent executions. Through careful analysis, we conclude that the adaptive mechanism makes the ADNSGA2-FCM algorithm finally find the correct number of clusters. This is mainly due to the fact that the adaptive mechanism effectively controls the speed of crossover and mutation of genetic algorithms. Because the NSGA-II-FCM algorithm does not adopt the adaptive mechanism, it leads to its premature convergence to the local optimal solution, which leads to the final clustering number being wrong. Looking at the other five data sets. Because the parameter values of NSGA-II-FCM are fixed, this leads to the fact that the algorithm does not make full use of data information in the optimization process, and the rate of convergence is too fast. Although the correct number of clusters was eventually found, the clustering effect was poor. With the increasing number of data and attributes in the data set, this trend is even more obvious. From this set of experiments, we can see that using an adaptive mechanism does improve the clustering effect.From this result, it is easy to think that because the clustering problem lacks prior knowledge of the data set, and the genetic algorithm is also a random search algorithm, it is difficult to give suitable crossover probability and mutation probability. However, adopting an adaptive mechanism here can avoid giving fixed global parameters directly.From the above analysis, we believe that the adoption of an adaptive mechanism is effective.Table6 shows the average performance rankings of all algorithms on the 6 datasets regarding Acc, RI, and NMI computed from Table 5, making a more evident comparison. From Table 6, we can see that the ADNSGA2-FCM algorithm proposed in this paper ranks first in Acc and RI, ranking second on NMI, mainly due to the fact that NMI indicators are not consistent with Acc and RI indicators. On Acc, the ADNSGA2-FCM algorithm has a greater advantage than the second algorithm. On RI, the ADNSGA2-FCM algorithm performs slightly better than the second algorithm. In NMI, ADNSGA2-FCM algorithm is worse than MOKCW algorithm, but it is not much different. It shows that the ADNSGA2-FCM algorithm has some advantages over the other 6 algorithms on the three indexes of Acc, RI, and NMI, and better clustering results can be obtained.Table 6
Average performance rankings of different algorithms on all datasets regarding Acc, RI and NMI.
Algorithms Acc RI NMI ESSC 5.2 7 5.2 6 4.8 6 VKCM-K-LP 4.2 4 3.8 3 4.2 4 VKFCM-K-LP 4.0 3 4.2 4 3.7 3 MOEASSC 4.8 6 5.2 6 4.8 6 MOKCW 3.3 2 2.3 2 2.8 1 NSGA-II-FCM 4.3 5 4.5 5 4.3 5 ADNSGA2-FCM 1.7 1 1.8 1 3.0 2Figure7 shows the histogram of mean values of the three indices in comparison for different algorithms. As can be observed from Tables 5 and 6 and Figure 7, the performance of our proposed method has obvious advantages in the Acc index and has a slight advantage in the RI index, which is not as good as the MOKCW algorithm in the NMI index.Figure 7
Mean values of Acc, RI, and NMI using different algorithms in the 6 real-life datasets.The final Pareto optimal front obtained by ADNSGA2-FCM clustering technique on the real-life data sets, Iris, Wine, Newthyroid, Vertebral, Image, and Abalone is illustrated in Figures8–10, respectively.Figure 8
Pareto optimal front obtained by the proposed ADNSGA2-FCM algorithm for Iris data set and Wine data set.Figure 9
Pareto optimal front obtained by the proposed ADNSGA2-FCM algorithm for Newthyroid data set and Vertebral data set.Figure 10
Pareto optimal front obtained by the proposed ADNSGA2-FCM algorithm for Image data set and Abalone data set.


## 4.1. Datasets and Parameter Setting

For the purpose of comparison, there are two groups of data sets, artificial and real-life data sets. The three artificial data sets are Square 1, Square 4, and Sizes 5 from [20]. The six real-life data sets are obtained from the UCI Machine Learning Repository [38], namely, Iris, Wine, Newthyroid, Vertebral, Image, and Abalone. As shown in Table 1 the data sets considered are briefly described, where C is the true number of classes and d and n are, respectively, the number of features and objects. For most SSC algorithms, the experiments are conducted on the data sets standardized into the interval [0,1], which can alleviate the uneven impact of different attributes’ ranges on updating the weights. Therefore, the standardization is based on the minimum and maximum values of each attribute.Table 1
The characters of datasets.
Datasets C d n Square 1 4 2 1000 Square 4 4 2 1000 Sizes 5 4 2 1000 Iris 3 4 150 Wine 3 13 178 Newthyroid 3 5 215 Vertebral 3 6 310 Image 7 16 2310 Abalone 3 8 4177The parameters of the ADNSGA2-FCM algorithm are set as shown in Table2, the parameters of other algorithms are set as shown in Table 3.Table 2
Parameter settings for the ADNSGA2-FCM algorithm.
Parameter Setting Population size 40 Max number of generations 300 C m i n 2 C m a x n p c 1 0.9 p m 1 0.1Table 3
Parameter settings for other algorithms.
Algorithm Parameter setting ESSC m = m i n ( n , D - 1 ) m i n ( n , D - 1 ) - 2, γ=100, η=0.1 VKCM-K-LP m = 2 VKFCM-K-LP m = 2 MOEASSC P c = 0.5, Pm=KD, σ=10-7 MOKCW P m = 0.1, α=0.1 NSGA-II-FCM P c = 0.9, Pm=0.05


## 4.2. Experiment Result and Analysis

In the first experiment, the above nine data sets (Square 1, Square 4, Sizes 5, Iris, Wine, Newthyroid, Vertebral, Image, and Abalone) and the adjusted Rand Index (ARI) [39] are used here to evaluate the clustering quality of ADNSGA2-FCM algorithm, which is to be maximized. Table 4 summarizes the result obtained from ADNSGA2-FCM. The real number of clusters can be obtained by the ADNSGA2-FCM algorithm in nine datasets. From the ARI value, the ADNSGA2-FCM algorithm has a big difference to the nine data sets. This is mainly because the ADNSGA2-FCM algorithm uses the fuzzy c-means (FCM) method as the clustering method, but the FCM algorithm is suitable for allocating the data of the spherical clusters. Therefore, for six datasets of Square 1, Square 4, Sizes 5, Iris, Wine, and Newthyroid, the effect is better, and the effect of the other three data sets is poor. It also can be observed from Table 4 that, in all data sets, the optimal clustering result is obtained by the algorithm.Table 4
Adjusted Rand index (ARI) and the number of the clusters (C) obtained by ADNSGA2-FCM.
Dataset ActualC ADNSGA2-FCM C ARI Square 1 4 4 0.971 Square 4 4 4 0.830 Sizes 5 4 4 0.838 Iris 3 3 0.802 Wine 3 3 0.865 Newthyroid 3 3 0.843 Vertebral 3 3 0.316 Image 7 7 0.490 Abalone 3 3 0.160Figures4–6 compare the results from the three synthetic data sets (Square 1, Square 4, and Sizes 5) of data partitioning obtained by ADNSGA2-FCM with center markings and the true data partitioning. The algorithm performs well under the well-separated structures of Square 1 (Figure 4) and Square 4 (Figure 5) as well as the unequally sized clusters of Sizes 5 (Figure 6). The overlapping and unequally sized characteristic causes more misclassification of the data points which are at the borderline between clusters.Figure 4
Square 1 (C=4): (a) true solution and (b) data partition using ADNSGA2-FCM (ARI = 0.971).
(a) (b)Figure 5
Square 4 (C=4): (a) true solution and (b) data partition using ADNSGA2-FCM (ARI = 0.830).
(a) (b)Figure 6
Sizes 5 (C=4): (a) true solution and (b) data partition using ADNSGA2-FCM (ARI = 0.838).
(a) (b)In order to evaluate the performance of the clustering result of seven algorithms, three well-known external CVIs accuracy (Acc), rand index (RI) [40], and normalized mutual information (NMI) [33] are adopted here. They all take their values from the interval [0,1], in which 1 means the best match between the result and the true partition, whereas 0 means the worst result. In this experiment, all algorithms are executed 30 times independently, and their performances are compared in terms of the best case of Acc, RI, and NMI shown in Table 5. Among them, the best result is expressed in bold.Table 5
The result of all algorithms on Acc, RI and NMI.
DataSet ESSC VKCM-K-LP VKFCM-K-LP MOEASSC MOKCW NSGA-II-FCM ADNSGA2-FCM Iris Acc 0.839 0.955 0.947 0.900 0.960 0.920 0.927 RI 0.844 0.944 0.934 0.886 0.950 0.906 0.912 NMI 0.716 0.858 0.832 0.778 0.864 0.777 0.790 Wine Acc 0.955 0.907 0.938 0.956 0.921 0.944 0.955 RI 0.940 0.883 0.919 0.942 0.897 0.925 0.940 NMI 0.847 0.733 0.796 0.854 0.768 0.823 0.847 Newthyroid Acc 0.893 0.864 0.809 0.888 0.946 0.953 0.954 RI 0.826 0.834 0.737 0.818 0.913 0.922 0.922 NMI 0.620 0.655 0.541 0.603 0.772 0.786 0.787 Vertebral Acc 0.474 0.510 0.517 0.479 0.506 0.655 0.655 RI 0.633 0.667 0.661 0.623 0.697 0.683 0.685 NMI 0.269 0.350 0.330 0.249 0.431 0.286 0.302 Image Acc 0.606 0.624 0.623 0.620 0.635 0 0.658 RI 0.862 0.869 0.871 0.863 0.874 0 0.874 NMI 0.624 0.625 0.649 0.628 0.631 0 0.598 Abalone Acc 0.507 0.512 0.513 0.503 0.512 0.492 0.516 RI 0.612 0.619 0.619 0.610 0.619 0.610 0.625 NMI 0.163 0.162 0.165 0.161 0.163 0.166 0.168It can be firstly observed from Table5 that, in all data sets, the optimal clustering result is obtained by the multiobjective algorithm. This result can prove that the multiobjective clustering algorithm has some advantages compared with the single-objective clustering algorithm. For most data sets, the ADNSGA-FCM algorithm proposed in this paper can obtain the best results.For the data set Iris and Vertebral, the kernel-based multiobjective clustering algorithm MOKCW can achieve the best results. Compared with MOKCW algorithm and VKCM-K-LP algorithm, the two results are similar, and the result of ADNSGA2-FCM is worse. For the Vertebral data set, the ADNSGA2-FCM algorithm obtains the best Acc value. For the Wine data set, the MOEASSC algorithm can achieve the best effect, and the ADNSGA-FCM effect is very close to it. It shows that two kinds of multiobjective clustering methods based on evolutionary computation can obtain the best global results on Wine datasets. In the three datasets of Newthyroid, Image, and Abalone, ADNSGA2-FCM proposed in this paper has obvious advantages over other algorithms.From Table5 we can also see that the effect of the ADNSGA2-FCM algorithm using the adaptive mechanism is significantly better than the NSGA-II-FCM algorithm. Except that the two indicators are the same as ADNSGA2-FCM algorithm, the other indicators of NSGA-II-FCM are quite different from ADNSGA2-FCM algorithm. More obviously, in the Image dataset, the NSGA-II-FCM algorithm cannot obtain the correct number of clustering by 30 independent executions. Through careful analysis, we conclude that the adaptive mechanism makes the ADNSGA2-FCM algorithm finally find the correct number of clusters. This is mainly due to the fact that the adaptive mechanism effectively controls the speed of crossover and mutation of genetic algorithms. Because the NSGA-II-FCM algorithm does not adopt the adaptive mechanism, it leads to its premature convergence to the local optimal solution, which leads to the final clustering number being wrong. Looking at the other five data sets. Because the parameter values of NSGA-II-FCM are fixed, this leads to the fact that the algorithm does not make full use of data information in the optimization process, and the rate of convergence is too fast. Although the correct number of clusters was eventually found, the clustering effect was poor. With the increasing number of data and attributes in the data set, this trend is even more obvious. From this set of experiments, we can see that using an adaptive mechanism does improve the clustering effect.From this result, it is easy to think that because the clustering problem lacks prior knowledge of the data set, and the genetic algorithm is also a random search algorithm, it is difficult to give suitable crossover probability and mutation probability. However, adopting an adaptive mechanism here can avoid giving fixed global parameters directly.From the above analysis, we believe that the adoption of an adaptive mechanism is effective.Table6 shows the average performance rankings of all algorithms on the 6 datasets regarding Acc, RI, and NMI computed from Table 5, making a more evident comparison. From Table 6, we can see that the ADNSGA2-FCM algorithm proposed in this paper ranks first in Acc and RI, ranking second on NMI, mainly due to the fact that NMI indicators are not consistent with Acc and RI indicators. On Acc, the ADNSGA2-FCM algorithm has a greater advantage than the second algorithm. On RI, the ADNSGA2-FCM algorithm performs slightly better than the second algorithm. In NMI, ADNSGA2-FCM algorithm is worse than MOKCW algorithm, but it is not much different. It shows that the ADNSGA2-FCM algorithm has some advantages over the other 6 algorithms on the three indexes of Acc, RI, and NMI, and better clustering results can be obtained.Table 6
Average performance rankings of different algorithms on all datasets regarding Acc, RI and NMI.
Algorithms Acc RI NMI ESSC 5.2 7 5.2 6 4.8 6 VKCM-K-LP 4.2 4 3.8 3 4.2 4 VKFCM-K-LP 4.0 3 4.2 4 3.7 3 MOEASSC 4.8 6 5.2 6 4.8 6 MOKCW 3.3 2 2.3 2 2.8 1 NSGA-II-FCM 4.3 5 4.5 5 4.3 5 ADNSGA2-FCM 1.7 1 1.8 1 3.0 2Figure7 shows the histogram of mean values of the three indices in comparison for different algorithms. As can be observed from Tables 5 and 6 and Figure 7, the performance of our proposed method has obvious advantages in the Acc index and has a slight advantage in the RI index, which is not as good as the MOKCW algorithm in the NMI index.Figure 7
Mean values of Acc, RI, and NMI using different algorithms in the 6 real-life datasets.The final Pareto optimal front obtained by ADNSGA2-FCM clustering technique on the real-life data sets, Iris, Wine, Newthyroid, Vertebral, Image, and Abalone is illustrated in Figures8–10, respectively.Figure 8
Pareto optimal front obtained by the proposed ADNSGA2-FCM algorithm for Iris data set and Wine data set.Figure 9
Pareto optimal front obtained by the proposed ADNSGA2-FCM algorithm for Newthyroid data set and Vertebral data set.Figure 10
Pareto optimal front obtained by the proposed ADNSGA2-FCM algorithm for Image data set and Abalone data set.


## 5. Conclusion

This paper presents a fuzzy clustering method based on multiobjective genetic algorithm. The ADNSGA2-FCM algorithm was developed to solve the clustering problem by combining the fuzzy clustering algorithm (FCM) with the multiobjective genetic algorithm (NSGA-II) and introducing an adaptive mechanism. In this paper, NSGA-II algorithm uses two cluster validity indexes of IndexI and DB Index as its objective function, so as to control multiobjective optimization. The algorithm does not need to give the number of clusters in advance. After the number of initial clusters and the center coordinates are given randomly, the optimal solution set is found by the multiobjective evolutionary algorithm. After determining the optimal number of clusters by majority vote method, the Jm value is continuously optimized through the combination of Canonical Genetic Algorithm and FCM, and finally the best clustering result is obtained.In addition to the basic framework of multiobjective genetic algorithm, the appropriate objective function is also one of the success factors of ADNSGA2-FCM algorithm. This paper does not use a single cluster evaluation index but uses two comprehensive evaluation indicators. These two indexes take into account both the within-cluster scatter and the between-cluster separation. The experimental results show that the multiobjective clustering method is better than the single-objective clustering method, and the better clustering results can be obtained by choosing a reasonable objective function.Although the ADNSGA2-FCM algorithm performs well, it also has some inherent problems. Since the algorithm adopts the NSGA-II framework, the multiobjective genetic algorithm can only compromise among multiple objective functions, so the method can only approach the real Pareto front. Because the NAGA-II algorithm is a kind of genetic algorithm and there is strong randomness, we can find the optimal solution through the randomness, or we can not find the optimal solution through the randomness. So we cannot guarantee the optimal clustering solution is absolutely right.In the following work, we hope to improve the selection and clustering accuracy of the optimal clustering results.



---

*Source: 6123874-2018-05-13.xml*