# A Fast Multiobjective Fuzzy Clustering with Multimeasures Combination

Authors: Cong Liu; Qianqian Chen; Yingxia Chen; Jie Liu
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

Most of the existing clustering algorithms are often based on Euclidean distance measure. However, only using Euclidean distance measure may not be sufficient enough to partition a dataset with different structures. Thus, it is necessary to combine multiple distance measures into clustering. However, the weights for different distance measures are hard to set. Accordingly, it appears natural to keep multiple distance measures separately and to optimize them simultaneously by applying a multiobjective optimization technique. Recently a new clustering algorithm called ‘multiobjective evolutionary clustering based on combining multiple distance measures’ (MOECDM) was proposed to integrate Euclidean and Path distance measures together for partitioning the dataset with different structures. However, it is time-consuming due to the large-sized genes. This paper proposes a fast multiobjective fuzzy clustering algorithm for partitioning the dataset with different structures. In this algorithm, a real encoding scheme is adopted to represent the individual. Two fuzzy clustering objective functions are designed based on Euclidean and Path distance measures, respectively, to evaluate the goodness of each individual. An improved evolutionary operator is also introduced accordingly to increase the convergence speed and the diversity of the population. In the final generation, a set of nondominated solutions can be obtained. The best solution and the best distance measure are selected by using a semisupervised method. Afterwards, an updated algorithm is also designed to detect the optimal cluster number automatically. The proposed algorithms are applied to many datasets with different structures, and the results of eight artificial and six real-life datasets are shown in experiments. Experimental results have shown that the proposed algorithms can not only successfully partition the dataset with different structures, but also reduce the computational cost.


---

## Body

## 1. Introduction

With the rapid development of informatization, there are large amounts of data generating in all walks of life every day; meanwhile, the quantity continues to grow rapidly. It is necessary to design many powerful and intelligent data analysis tools to explore the valuable knowledge from these data. Clustering analysis is such a tool and it partitions a dataset into some subgroups such that objects within a group should be as similar as possible while objects in different groups should be as dissimilar as possible. Most of clustering algorithms have been developed in recent years in various fields, such as image segmentation [1], data mining [2], pattern recognition, and computer vision [3]. Generally, the most popular clustering techniques can be simply divided into partitioning clustering [4], hierarchical clustering [5], and density clustering [6]. Among these clustering algorithms, partitioning clustering is the most popular one and has attracted more and more attention in recent years.Although partitioning clustering algorithms are developing rapidly, they still have a limitation in partitioning the dataset with different structures. The reason is that these clustering algorithms usually employ Euclidean distance to design their clustering criterion [7]. Euclidean distance measure is suitable for detecting the spherical structures, whereas it often fails for detecting the irregular structures [8]. Many algorithms apply other strategies to measure the similarity between clusters. Hierarchical clustering and density clustering are two kinds of traditional methods which are effective to partition the dataset with different structures. Hierarchical clustering [5] utilizes single link, average link, and complete link to measure the similarity between clusters. Density clustering [6] applies density function to measure the similarity between two objects. Apart from them, many algorithms employ non-Euclidean distance measures such as Path distance [9], Manifold distance [10], and Kernel distance [11, 12] to partition the dataset with different structures. However, it is hard to select an appropriate distance measure for a given dataset. A good solution is to assign different weights to different distance measures, but the appropriate weights are also difficult to set. Francisco proposed two algorithms ‘dynamic hard clustering algorithm based on multiple dissimilarity matrices estimated locally and globally’ (MRDCA-RWG and MRDCA-RWL) [13], which are two dynamic hard clustering algorithms with relevant weight for each dissimilarity matrix. The relevant weights change at each algorithm iteration and can either be the same for all clusters or different from one cluster to another. Shortly afterwards, Francisco proposed another two algorithms ‘partitioning fuzzy Kmedoids clustering algorithm based on multiple dissimilarity matrices estimated locally and globally’ (MFCMdd-RWG and MFCMdd-RWL) [14], which are two fuzzy clustering algorithms with relevant weight for each dissimilarity matrix. The relevant weights are obtained by the same strategy with MRDCA-RWG and MRDCA-RWL. Nevertheless, similar with weighting kmeans (Wkmeans) [15], these algorithms will lead to assigning a larger weight to the distance measure that has a smaller sum of the within-cluster distances and a smaller one to the distance measure that has a larger sum of the within-cluster distances.In addition, many algorithms which can automatically detect the optimal cluster number are also designed based on Euclidean distance measure. Validity index[16] is the most widely used approach that can detect the cluster number automatically. Many validity indices such as XB index (Vxb) [17], OS index (Vos) [18], and LZZ index (Vlzz) [19] are also designed based on Euclidean distance measure. Hence, they usually work well on the dataset with spherical structures and fail on the dataset with irregular structures. Some other algorithms, such as gap algorithm [20], affinity propagation [21], two phase method [22], and L-method [23], can detect the optimal cluster number for the dataset with different structures by using different distance measures. However, the distance measure should be set in advance. Mok proposed ‘robust adaptive clustering with kmeans’ (RAC-Kmeans) [24], which detected the optimal cluster number by using a specific graph-partitioning process and was not sensitive to distance measure. However, this algorithm is computationally expensive by counting the breadth first search algorithm for each subgraph matrix.Recently, as an effective tool to get a global optimal solution, the evolutionary algorithms (EAs) are more and more used for cluster analysis. Bandyopadhyay proposed ‘genetic clustering for unknownk’ (GCUK) [25], which took DB index (Vdb) for clustering and could detect the optimal cluster number automatically. Maulik and Saha proposed ‘modified differential evolution based automatic fuzzy clustering’ (MoDEAFC) [26], which employed Vxb index as the objective function and was optimized by using a modified differential evolution. In recent years, as a new trend, multiobjective optimization has also been used in cluster analysis [27]. Handl proposed ‘multiobjective clustering with automatic k-determination’ (MOCK) [28], which took the compactness and connectedness as two objective functions for clustering and were optimized simultaneously by using the ‘Pareto envelope-based selection algorithm version 2’ (PESA-II) [29]. Prakash proposed ‘two-stage diversity mechanism in multiobjective particle swarm optimization’ (TSMPSO) [30], which employed the same objective functions as MOCK for clustering and were optimized by using an improved multiobjective particle swarm optimization. Saha proposed ‘multiobjective modified differential evolution based fuzzy clustering’ (MOMoDEFC) [31], which used mean squared error (Jmse) and Vxb index as two objective functions for clustering and were optimized by a modified differential evolution. Zhao developed ‘multiobjective spatial fuzzy clustering algorithm’ (MSFCA) [32], which partitioned an image by optimizing the global fuzzy compactness with spatial information and fuzzy separation among the clusters. Hu proposed ‘multiobjective evolutionary approach based soft subspace clustering’ (MOEASSC) [33], which applied within-cluster dispersion as the first objective function and the information of the negative weight entropy and the separation between clusters as the second objective function. This algorithm is suitable for partitioning high-dimensional dataset. Although above algorithms can get many satisfactory clustering results for datasets with spherical structures, they fail on datasets with irregular structures because most of them are based on Euclidean distance measure.In this paper, integrating multiple distance measures into clustering is studied. More recently, we proposed a novel approach ‘multiobjective evolutionary clustering based on combining multiple distance measures’ (MOECDM) to partition the dataset with different structures and an updated approach ‘multiobjective evolutionary automatic clustering based on combining multiple distance measures’ (MOEACDM) to detect the optimal cluster number [34]. Although both of the two approaches can get promising results, they have two limitations. (1) The individual is designed by label encoding scheme, which is time-consuming due to the large-sized genes and (2) it is a hard clustering algorithm, which may not be able to reflect the structure of the dataset with overlaps. Based on the above analysis, in this study, we proposed a fast multiobjective fuzzy clustering algorithm based on multiple distance measures (F-MFCMDM) to partition the dataset with different structures. Moreover, we also propose an updated algorithm, F-MFCMDM with unknownk (F-MFCMDM-UK), to detect the optimal cluster number automatically. The contributions of the paper can be summarized as follows.(i)
We propose F-MFCMDM to partition the dataset with different structures.(ii)
An improved evolutionary operator is proposed to increase the convergence speed.(iii)
We propose F-MFCMDM-UK to detect the optimal cluster number of the dataset with different structures.(iv)
F-MFCMDM and F-MFCMDM-UK provide better accuracy compared with several other approaches not only in partitioning dataset with different structures but also in increasing the convergence speed.The rest of this paper is arranged as follows. Section2 introduces some related works concerning fuzzy clustering and multiobjective evolutionary technique. Section 3 presents the proposed algorithms, F-MFCMDM and F-MFCMDM-UK, in detail. The experiment results are shown in Section 4. Finally, Section 5 provides the conclusion.


## 2. Related Works

### 2.1. Fuzzy Clustering Problem

In this subsection, we make a brief introduction of fuzzy clustering by a widely used clustering algorithm, fuzzy c-means (FCM) [35]. Firstly, most notations used in clustering should be summarized as follows. Let X=[xj]n be a set of n unlabel data objects and j∈{1,…,n}, where xj=(xj,1,…,xj,h1)∈R1h1 is a h1-dimensional point in the continuous feature space. C=[Ci]k represents k clusters, where i∈{1,…,k}. O=[oi]k represents k cluster centers, where oi is the center of the cluster Ci. m is the fuzzy factor. U=[uij]k∗n is the fuzzy matrix, where uij represents the membership of the xj to the cluster Ci. It satisfies ∑i=1kuij=1 and uij≥0. The objective function of the standard FCM algorithm can be written as in(1)JFCMU,O=∑i=1k∑j=1nuijmdxj,oi.By minimizing the objective function in (1) using the Lagrange multiplier algorithm, the updating equations of the fuzzy memberships and the cluster centers are as shown in (2) and (3), respectively:(2)uij=∑s=1kdxj,oidxj,os1/m-1-1.(3)oi=∑j=1nuijmxj∑j=1nuijm.Based on the analysis in Section1, the traditional fuzzy clustering methods have two obvious limitations. The first limitation is that they are usually based on a single distance measure. Although some fuzzy clustering methods such as MFCMdd-RWG and MFCMdd-RWL [14] also combine multiple distance measures, the appropriate weights for multiple distance measures are difficult to set. The second limitation is that they are quite sensitive to the initialization and may sometimes get stuck at a suboptimal solution. In this paper, we are trying to solve the two limitations.


### 2.2. Multiobjective Optimization Problem

In many real world applications, a certain problem can be solved by optimizing several objective functions simultaneously. It is a multiobjective optimization problem (MOP). Two strategies can be used to solve the MOP. The first is to convert the MOP into a single objective optimization problem by combining all objectives with a weighted formula. However, the objectives in many real world problem are often conflicted with each other and the best weights are difficult to set. The second is to employ Pareto solution approach, in which dominance relation is applied to evaluate the intermediate and final solutions. From a mathematical viewpoint, a general MOP problem can be formulated as in the following:(4)FP=F1P,…,FMPT,where P=(p1,…,ph2) is a h2-dimensional decision vector. F is an objective vector and it consists of M objective functions. All the objective functions will be optimized simultaneously and several solutions may be considered superior to the rest of the solutions in the search space. The winning solutions are called nondominated solutions and the losing solutions are called dominated solutions. All the nondominated solutions can be considered acceptable because none of them are absolutely better than the others. For example, considering a minimization problem, a solution P∗ is called nondominated solution if and only if no solution P′ exists such that Fq(P′)<Fq(P∗) for at least one q∈{1,…,M} and Fq(P′)≤Fq(P∗) for the remaining cases.


## 2.1. Fuzzy Clustering Problem

In this subsection, we make a brief introduction of fuzzy clustering by a widely used clustering algorithm, fuzzy c-means (FCM) [35]. Firstly, most notations used in clustering should be summarized as follows. Let X=[xj]n be a set of n unlabel data objects and j∈{1,…,n}, where xj=(xj,1,…,xj,h1)∈R1h1 is a h1-dimensional point in the continuous feature space. C=[Ci]k represents k clusters, where i∈{1,…,k}. O=[oi]k represents k cluster centers, where oi is the center of the cluster Ci. m is the fuzzy factor. U=[uij]k∗n is the fuzzy matrix, where uij represents the membership of the xj to the cluster Ci. It satisfies ∑i=1kuij=1 and uij≥0. The objective function of the standard FCM algorithm can be written as in(1)JFCMU,O=∑i=1k∑j=1nuijmdxj,oi.By minimizing the objective function in (1) using the Lagrange multiplier algorithm, the updating equations of the fuzzy memberships and the cluster centers are as shown in (2) and (3), respectively:(2)uij=∑s=1kdxj,oidxj,os1/m-1-1.(3)oi=∑j=1nuijmxj∑j=1nuijm.Based on the analysis in Section1, the traditional fuzzy clustering methods have two obvious limitations. The first limitation is that they are usually based on a single distance measure. Although some fuzzy clustering methods such as MFCMdd-RWG and MFCMdd-RWL [14] also combine multiple distance measures, the appropriate weights for multiple distance measures are difficult to set. The second limitation is that they are quite sensitive to the initialization and may sometimes get stuck at a suboptimal solution. In this paper, we are trying to solve the two limitations.


## 2.2. Multiobjective Optimization Problem

In many real world applications, a certain problem can be solved by optimizing several objective functions simultaneously. It is a multiobjective optimization problem (MOP). Two strategies can be used to solve the MOP. The first is to convert the MOP into a single objective optimization problem by combining all objectives with a weighted formula. However, the objectives in many real world problem are often conflicted with each other and the best weights are difficult to set. The second is to employ Pareto solution approach, in which dominance relation is applied to evaluate the intermediate and final solutions. From a mathematical viewpoint, a general MOP problem can be formulated as in the following:(4)FP=F1P,…,FMPT,where P=(p1,…,ph2) is a h2-dimensional decision vector. F is an objective vector and it consists of M objective functions. All the objective functions will be optimized simultaneously and several solutions may be considered superior to the rest of the solutions in the search space. The winning solutions are called nondominated solutions and the losing solutions are called dominated solutions. All the nondominated solutions can be considered acceptable because none of them are absolutely better than the others. For example, considering a minimization problem, a solution P∗ is called nondominated solution if and only if no solution P′ exists such that Fq(P′)<Fq(P∗) for at least one q∈{1,…,M} and Fq(P′)≤Fq(P∗) for the remaining cases.


## 3. Fast Multiobjective Fuzzy Clustering Based on Multiple Distance Measures

In this section, F-MFCMDM and F-MFCMDM-UK are introduced. The two algorithms employ the ‘regularity model based multiobjective estimation of distribution algorithm’ (RMMEDA) [36] as the optimizer, and a series of changes are applied to improve the ability of the algorithm. Next, we will introduce the details as follows.


### 3.1. Distance Measures Definition

F-MFCMDM and F-MFCMDM-UK are designed based on two distance measures; therefore, we introduce the two distance measures in this subsection. We need to consider which two distance measures should be selected. As we all know, Euclidean distance measure is very suitable for the dataset with spherical structures and Path distance measure [9] is suitable for the dataset with irregular structures. Hence, in our paper, we employ Euclidean and Path distance measures as two distance measures. The two distance measures are also used in [34]. Since the Path distance needs to visit all of the path, it is very time-consuming. Therefore, we can get two distance matrices, DM1 and DM2, in one run firstly and they are defined as follows:(5)DM1DM2=d1x1,x1d2x1,x1⋯d1x1,xnd2x1,xnd1x2,x1d2x2,x1⋯d1x2,xnd2x2,xn⋮⋮⋮d1xn,x1d2xn,x1⋯d1xn,xnd2xn,xn.where d1(xj1,xj2) and d2(xj1,xj2) represent the Euclidean distance and Path distance between xj1 and xj2, respectively, where j1,j2∈{1,…,n}.


### 3.2. Objective Function Computation

The objective functions used in many existing multiobjective evolutionary clustering algorithms are usually based on the Euclidean distance measure and it is not equally appropriate for the dataset with different structures. In here, we define two new objective functions based on Euclidean distance measure and Path distance measure, respectively, as shown in the following:(6)F1U,O=∑i=1k∑j=1nuijmd1xj,oi,F2U,O=∑i=1k∑j=1nuijmd2xj,oi.F1 and F2 are two objective functions based on Euclidean distance and Path distance, respectively. uij and oi are the same as those in (1). d1(xj,oi) and d2(xj,oi) denote the distance measures between xj and oi in two distance measures, respectively. U and O are two kinds of parameters that can be used as the tradeoff solution between the two objective functions F1 and F2. However, it is hard to implement due to two problems. The first problem is that the cluster centers become invalid in many non-Euclidean distance spaces; in other words, O is meaningless in Path distance space. A good solution to this problem is that we employ the cluster medoids to replace the cluster centers. Unlike the cluster center, a cluster medoid is one of the real objects in the dataset [37]. The two objective functions are modified as (7)F1U,δ=∑i=1k∑j=1nuijmd1xj,δi,F2U,δ=∑i=1k∑j=1nuijmd2xj,δi,where δ=[δi]k represents k cluster medoids and δi is the medoid of the cluster Ci. The second problem is that the distance measure in F1 is different from that in F2. To solve this problem, we only use δ as the tradeoff solution between F1 and F2. The two objective functions are modified again as follows:(8)F1δ=∑i=1k∑j=1nu1ijmd1xj,δi,F2δ=∑i=1k∑j=1nu2ijmd2xj,δi.It is noted that the u1ij is different from u2ij. By minimizing F1 and F2, the two memberships u1ij and u2ij are obtained by using the following:(9)u1ij=∑s=1kd1xj,δid1xj,δs1/m-1-1,u2ij=∑s=1kd2xj,δid2xj,δs1/m-1-1.Next, we will look for the set of tradeoff cluster medoids by some evolutionary operators.


### 3.3. Encoding and Initialization Schemes

The encoding and initialization schemes are introduced in this subsection. Most notations used in multiobjective evolutionary algorithms are summarized as follows.pop_size is the population size. P(g)=[cl(g)]pop_size is the population of the gth generation and l∈{1,…,pop_size}, where cl(g) is the lth individual. An encoding scheme should be selected to map k cluster medoids into an individual, where k is the cluster number. Many encoding schemes have been proposed in the literature [4]. In F-MFCMDM, we propose a real encoding scheme to represent the individual. Each individual is a real vector of k genes and each gene corresponds to a cluster medoid. For example, the lth individual cl(g) in P(g) can be written as in (10)clg=c1lg,…,cklg,where cil(g)(i∈{1,…,k}) is a real number in the range (0,n] and n is the number of data objects. Next, cil(g) is mapped into an integer ⌈cil(g)⌉, which represents the index of x⌈cil(g)⌉. It means that we use x⌈cil(g)⌉ as the ith cluster medoid δil(g) for the individual cl(g). All the k cluster medoids can be gotten as (11)δlg=δ1lg,…,δklg,where δil(g)=x⌈cil(g)⌉.In order to make the population have a higher probability to fall into the promising regions of the solution space, the initial populationP(0)=[cl(0)]pop_size(l∈{1,…,pop_size}) is generated by using a random strategy and a preclustering strategy. pop_α is a parameter that determines the proportion of individuals generated by using the random strategy to the whole individuals. pop_α∗pop_size and (1-pop_α)∗pop_size individuals are generated by using the random strategy and preclustering strategy, respectively. In our algorithm, each individual is a tradeoff between Euclidean distance and Path distance measures; that is to say, each individual implies a combination of Euclidean distance measure and Path distance measure. Hence, the preclustering strategy is performed by using a preclustering algorithm based on several different distance combinations. By adjusting the weights for Euclidean distance and Path distance measures, we can get many different distance combinations. For simplicity, we set four distance combinations including only Euclidean distance (ED), only Path distance (PD), combining the Euclidean and Path distances directly (EPD), and normalizing the Euclidean and Path distances within the range [0,1] (NEPD). Kmedoids algorithm can be used as the preclustering algorithm. Hence, (1-pop_α)∗pop_size individuals are generated by using four preclustering algorithms, which are (1) Kmedoids algorithm based on ED (KM(ED)), (2) Kmedoids algorithm based on PD (KM(PD)), (3) Kmedoids algorithm based on EPD (KM(EPD)), and (4) Kmedoids algorithm based on NEPD (KM(NEPD)). We hope that the individuals generated by using different preclustering algorithms have the same number, which is (1-pop_α)∗pop_size/4. The procedure of initialization of F-MFCMDM is shown in Algorithm 1.Algorithm 1:Initialization of F-MFCMDM.
Input: Dataset X=[xj]n, cluster number k, population size pop_size, proportion parameter pop_α, four distance combinationsED, PD, EPD and NEPD. Output:Initial population P(0)=[cl(0)]pop_size. for each individual c l ( 0 ) ( l = 1 : p o p _ α ∗ p o p _ s i z e ) do Setcil(0)(i=1:k)= a random real number from (0,n]. end while l < p o p _ s i z e do Setl=l+1, cl(0)=KM(ED,k). Setl=l+1, cl(0)=KM(PD,k). Setl=l+1, cl(0)=KM(EPD,k). Setl=l+1, cl(0)=KM(NEPD,k). end


### 3.4. Evolutionary Operators

In this subsection, the(g+1)th generation population P(g+1)=[cl(g+1)]pop_size is generated by applying some evolutionary operators on the gth generation population P(g)=[cl(g)]pop_size, where l∈{1,…,pop_size}. Next, we introduce the details of each evolutionary operator in turn.


#### 3.4.1. RMMEDA Operator

RMMEDA employs the estimation of distribution algorithms (EDA) to generate the offspring population. In RMMEDA, an assumption is that the Pareto set of a multiobjective optimization problem (MOP) is an(M-1)-dimensional piecewise continuous manifold, which is a regularity property of a continuous MOP [36]. According to this assumption, a probability model will be built by employing local principal component analysis (PCA) algorithm and the new offspring solutions are sampled from this model. We call it RMMEDA operator and it mainly consists of two operators, modeling operator and reproduction operator. The offspring population RP(g)=[crl(g)]pop_size generated by RMMEDA operator is shown in Algorithm 2.Algorithm 2:RMMEDA operator.
Input: The gth generation population, P(g)=[cl(g)]pop_size. Output: The offspring population, RP(g)=[crl(g)]pop_size. (a)Step1: Modeling operator: Learn the distribution of the solutions in P(g) and build the probability model. (i) PartitionP(g) into a set of disjoint clusters by the local PCA algorithm. (ii) For each cluster, find the first(M-1) principal subspaces. (iii) Extend each of the directions in each cluster to cover the whole Pareto front. (b)Step2: Reproduction operator: Sample pop size individuals from the probability model to generate the offspring populationRP(g)=[crl(g)]pop_size.


#### 3.4.2. Differential Evolution Operator

RMMEDA operator works very well when the regularity of solutions is obvious. However, in the initial generations, the solutions have no obvious regularity. Thus, it makes the convergence speed of population very slow. In order to overcome this limitation, we apply differential evolution operator (DE operator) to generate another offspring population,DP(g)=[cdl(g)]pop_size. It is noted that DE operator works on P(g). For the lth individual cdl(g) in DP(g), it is generated by considering two operators. The first operator is used to increase the diversity of population and it is shown in the following:(12)cdilg=cir1g+λ1·cir2g-cir3gifrandi0,1<Cr1ori=irand,cilgotherwise,where r1, r2, and r3 are three integers that are selected randomly from {1,…,pop_size}. cil(g) is the ith gene in the individual cl(g). λ1 is a scaling factor, which controls the weights of different individuals. randi(0,1) is a uniformly distributed random number from [0,1], which is generated for each gene i. Cr1∈[0,1] is the crossover control parameter. irand is a randomly chosen integer from {1,…,k} and it ensures that at least one of genes in cdil is different with that in cil.The second operator is used to push the population quickly towards the global optima and it is shown in(13)cdilg=cibestlg+λ2·cir1g-cilgifrandi0,1<Cr2ori=irand,cilgotherwise,where λ2 and Cr2 are similar with λ1 and Cr1, respectively. cbestl(g) is the best individual in the Pareto front of P(g) for cil(g).Generally speaking, a Pareto front contains more than one solution. For thelth individual cl(g), only one solution in Pareto front can be used as cbestl(g) in (13). In this paper, cbestl(g) is selected from the Pareto front by using the nearest criterion. Firstly, we calculate the Euclidean distances in objective function between the individual cl(g) and each nondominated solution in the Pareto front. Secondly, the nondominated solution with the minimum Euclidean distance is used as the cbestl(g). For example, as shown in Figure 1, there are four nondominated solutions, PF1, PF2, PF3, and PF4, in Pareto front. By computing the Euclidean distance from each nondominated solution to the cl(g) in objective function, PF3 is the nearest one to cl(g). Hence, we select PF3 as cbestl(g) for cl(g).Figure 1
An illustration of finding the best individual forcl(g).The offspring populationDP(g)=[cdl(g)]pop_size generated by DE operator is shown in Algorithm 3. Note that only one operator is used for generating the cdl(g) and which one can be selected depends on a mutation parameter muta_α. muta_α is computed by using (14). The value of muta_α decreases in the range between [0,1] as the number of generations g increases. In the initial stage, the first operator may be selected in a higher probability. On the contrary, the second operator may be selected in a higher probability in the later stage. randl(0,1) is a uniformly distributed random number from [0,1], which is generated for the lth individual.(14)muta_α=exp⁡1-max_gmax_g+1-g.Algorithm 3:DE operator.
Input: The gth generation population, P(g)=[cl(g)]pop_size. Output: The offspring population, DP(g)=[cdl(g)]pop_size. Computemuta_α by using Eq. (14). for each individual c d l ( g ) ( l = 1 : p o p _ s i z e ) do if r a n d l ( 0,1 ) ≤ m u t a _ α then Generate cdl(g) by using Eq. (12). else Generate cdl(g) by using Eq. (13). end end


#### 3.4.3. Selection Operator

After RMMEDA and DE operators, we can get three populations, i.e., current populationP(g)=[cl(g)]pop_size, the offspring population generated by RMMEDA operator RP(g)=[crl(g)]pop_size, and the offspring population generated by DE operator DP(g)=[cdl(g)]pop_size. To ensure that the population size is equal with the pop_size and the favorable solutions are preserved, a selection operator is executed to preserve individuals with higher fitness and to eliminate individuals with lower fitness. In F-MFCMDM, crowded binary tournament selection method proposed in [38] is employed to select the better individuals. In selection operator, all of the individuals in P(g)∪RP(g)∪DP(g) are ranked based on nondominated sorting and assigned with crowding distance. The individuals with lower ranking and higher crowding distance can be selected as the new population P(g+1).


### 3.5. Outputting the Best Clustering Result

In the final generation of F-MFCMDM, the Pareto front is obtained. As we all know, all the solutions in the Pareto front are equally important and each solution corresponds tok cluster medoids. In most real world problems, a single solution should be selected from these solutions. There are two widely used strategies to select the best solution. The first strategy is to employ an additional validity index such as VI [32] to select the best solution. And the second strategy is to use a semisupervised method [39] to select it. Since some additional validity indices are also based on Euclidean distance, we use the semisupervised method to achieve our goal in this paper.In the semisupervised method, some data objects are chosen as the test patterns and their class labels are known. Firstly, each individual in Pareto front is decoded intok cluster medoids by using (11). Secondly, the class label of each test pattern is assigned based on the nearest medoid criterion. A data object xj should be assigned into the ith cluster if it satisfies the following:(15)i=mini∈1,…,k⁡dxj,δi.However, the distance measures in F-MFCMDM are not unique. And each individual needs to be decoded by using an appropriate distance measure. As introduced in Section 3.3, each individual implies a combination of Euclidean distance and Path distance. In this subsection, we apply ED, PD, EPD, and NEPD as four candidate distance combinations that can be selected for each individual. Based on this analysis, each individual in Pareto front can be decoded into four clustering results by using four distance combinations. If the number of individuals in Pareto front is Nnon, we can obtain Nnon∗4 clustering results for the test patterns. Thirdly, Minkowski Score is used to measure the amount of misclassification. The Minkowski score (MS) is then defined as in (16)MS=sd+dsss+sd,where ss is the number of object pairs having same class labels belonging to the same clusters, sd is the number of object pairs having different class labels belonging to the same clusters, and ds is the number of object pairs having same class labels belonging to different clusters. A lower score indicates a better solution and a better distance combination. Finally, after the scores of Nnon∗4 clustering results have been calculated and the solution and the distance combination with the minimum Minkowski score are chosen as the best solution and the best distance combination, respectively, they can be used to partition the remaining objects.


### 3.6. F-MFCMDM-UK

As mentioned in the previous section, the cluster number should be provided by user in advance. However, in most of real world applications, this parameter is difficult to get. In this subsection, we try to get it automatically by designing two appropriate objective functions. We call it ‘multiobjective fuzzy clustering based on multiple distance measures with unknownk’ (F-MFCMDM-UK). Many operators in F-MFCMDM-UK are similar with those in F-MFCMDM. We will mainly introduce the different operators, which are objective function computation and initialization scheme.


#### 3.6.1. Objective Function Computation

Validity index is a widely used approach to detect the optimal cluster number automatically and it works by looking for a balance between the compactness of each cluster and separation between each pair of clusters. Most of existing validity indices are inapplicable in here. Similar to the analysis above, most of them are designed based on Euclidean distance. Therefore, we need to construct two new objective functions based on two distance spaces, respectively. Unlike F-MFCMDM, each objective function in F-MFCMDM-UK should consider the balance between compactness and separation in order to detect optimal cluster number automatically. Based on this analysis, the two new objective functions are rewritten as(17)V1δ=F1mini1≠i2⁡d1δi1,δi2,V2δ=F2mini1≠i2⁡d2δi1,δi2,where i1,i2∈{1,…,k}. Let us make the following comments on the two objective functions. V1 and V2 are two ratios of compactness and separation based on Euclidean distance and Path distance respectively. On the one hand, two factors F1 and F2 tend to decrease as the cluster number k increases. On the other hand, two factors, d1(δi1,δi2) and d2(δi1,δi2), measuring the minimum separations between each pair of clusters, also tend to decrease as the cluster number k increases. Each individual is a tradeoff not only between Euclidean distance and Path distance but also between compactness and separation. By optimizing V1 and V2 simultaneously, we can detect the optimal cluster number k∗ automatically.


#### 3.6.2. Encoding and Initialization Schemes

The optimal cluster numberk∗ in F-MFCMDM-UK is unknown and it is assumed to lie in the range of {kmin,…,kmax}, where kmin and kmax are the acceptable lower bound and upper bound of the cluster number, respectively. The length of an individual in F-MFCMDM-UK is kmax+1. The first kmax genes represent the cluster medoids and the last gene is an additional label denoting how many medoids are used for clustering. The lth individual cl can be written as in the following:(18)cl=c1l,…,ckmaxl,cll,where {c1l,…,ckmaxl} are the first kmax genes, cil∈(0,n], and i∈{1,…,kmax}. cll is the last position, which is a real number and cll∈[kmin,kmax]. In F-MFCMDM-UK, the first ⌈cll⌉ genes are the valid genes for the objective functions calculation. The valid individual cvl can be expressed as in (19)cvl=c1l,…,cclll.The ⌈cll⌉ medoids can be gotten by using (11).In F-MFCMDM-UK, the random strategy and the preclustering strategy are also used to generate the initial populationP(0)=[cl(0)]pop_size, where l∈{1,…,pop_size}. Similar to Section 3.3, pop_α∗pop_size and (1-pop_α)∗pop_size individuals are generated by using the random strategy and the preclustering strategy, respectively. Since the cluster number is unknown in F-MFCMDM-UK, (1-pop_α)∗pop_size individuals are generated by using the preclustering strategy not only with different distance combinations but also with different cluster numbers. There are four distance combinations and (kmax-kmin+1) different cluster numbers can be selected; in other words, the (1-pop_α)∗pop_size individuals are generated by using 4∗(kmax-kmin+1) preclustering algorithms. In addition, the label gene cll in the lth individual corresponds to the cluster number of the individual. If the individual cl is generated with k′ cluster number, the cll in cl is set to k′-0.5. The procedure of initialization of F-MFCMDM-UK is shown in Algorithm 4.Algorithm 4:Initialization of F-MFCMDM-UK.
Input: Dataset X=[xj]n, population size pop_size, proportion parameter pop_α, the lower and the upper bound of the cluster numberkmin and kmax, four distance measures ED, PD, EPD and NEPD. Output: Initial population P(0)=[cl(0)]pop_size. for each individual c l ( 0 ) ( l = 1 : p o p _ α ∗ p o p _ s i z e ) do Setcil(0)(i=1:kmax)= a random real number from (0,n] andcll(0)= a random real number from [kmin,kmax]. end k t e m p = k m i n. while l < p o p _ s i z e do ifktemp≥kmaxthen ktemp=kmin. end l=l+1, cil(0)(i=1:kmax)=KM(ED,ktemp), cll(0) is set to ktemp-0.5. l=l+1, cil(0)(i=1:kmax)=KM(PD,ktemp), cll(0) is set to ktemp-0.5. l=l+1, cil(0)(i=1:kmax)=KM(EPD,ktemp), cll(0) is set to ktemp-0.5. l=l+1, cil(0)(i=1:kmax)=KM(NEPD,ktemp), cll(0) is set to ktemp-0.5. end


### 3.7. Procedure of F-MFCMDM and F-MFCMDM-UK

The framework of the proposed algorithm is shown in Figure2.Figure 2
Flowchart of F-MFCMDM (F-MFCMDM-UK).


## 3.1. Distance Measures Definition

F-MFCMDM and F-MFCMDM-UK are designed based on two distance measures; therefore, we introduce the two distance measures in this subsection. We need to consider which two distance measures should be selected. As we all know, Euclidean distance measure is very suitable for the dataset with spherical structures and Path distance measure [9] is suitable for the dataset with irregular structures. Hence, in our paper, we employ Euclidean and Path distance measures as two distance measures. The two distance measures are also used in [34]. Since the Path distance needs to visit all of the path, it is very time-consuming. Therefore, we can get two distance matrices, DM1 and DM2, in one run firstly and they are defined as follows:(5)DM1DM2=d1x1,x1d2x1,x1⋯d1x1,xnd2x1,xnd1x2,x1d2x2,x1⋯d1x2,xnd2x2,xn⋮⋮⋮d1xn,x1d2xn,x1⋯d1xn,xnd2xn,xn.where d1(xj1,xj2) and d2(xj1,xj2) represent the Euclidean distance and Path distance between xj1 and xj2, respectively, where j1,j2∈{1,…,n}.


## 3.2. Objective Function Computation

The objective functions used in many existing multiobjective evolutionary clustering algorithms are usually based on the Euclidean distance measure and it is not equally appropriate for the dataset with different structures. In here, we define two new objective functions based on Euclidean distance measure and Path distance measure, respectively, as shown in the following:(6)F1U,O=∑i=1k∑j=1nuijmd1xj,oi,F2U,O=∑i=1k∑j=1nuijmd2xj,oi.F1 and F2 are two objective functions based on Euclidean distance and Path distance, respectively. uij and oi are the same as those in (1). d1(xj,oi) and d2(xj,oi) denote the distance measures between xj and oi in two distance measures, respectively. U and O are two kinds of parameters that can be used as the tradeoff solution between the two objective functions F1 and F2. However, it is hard to implement due to two problems. The first problem is that the cluster centers become invalid in many non-Euclidean distance spaces; in other words, O is meaningless in Path distance space. A good solution to this problem is that we employ the cluster medoids to replace the cluster centers. Unlike the cluster center, a cluster medoid is one of the real objects in the dataset [37]. The two objective functions are modified as (7)F1U,δ=∑i=1k∑j=1nuijmd1xj,δi,F2U,δ=∑i=1k∑j=1nuijmd2xj,δi,where δ=[δi]k represents k cluster medoids and δi is the medoid of the cluster Ci. The second problem is that the distance measure in F1 is different from that in F2. To solve this problem, we only use δ as the tradeoff solution between F1 and F2. The two objective functions are modified again as follows:(8)F1δ=∑i=1k∑j=1nu1ijmd1xj,δi,F2δ=∑i=1k∑j=1nu2ijmd2xj,δi.It is noted that the u1ij is different from u2ij. By minimizing F1 and F2, the two memberships u1ij and u2ij are obtained by using the following:(9)u1ij=∑s=1kd1xj,δid1xj,δs1/m-1-1,u2ij=∑s=1kd2xj,δid2xj,δs1/m-1-1.Next, we will look for the set of tradeoff cluster medoids by some evolutionary operators.


## 3.3. Encoding and Initialization Schemes

The encoding and initialization schemes are introduced in this subsection. Most notations used in multiobjective evolutionary algorithms are summarized as follows.pop_size is the population size. P(g)=[cl(g)]pop_size is the population of the gth generation and l∈{1,…,pop_size}, where cl(g) is the lth individual. An encoding scheme should be selected to map k cluster medoids into an individual, where k is the cluster number. Many encoding schemes have been proposed in the literature [4]. In F-MFCMDM, we propose a real encoding scheme to represent the individual. Each individual is a real vector of k genes and each gene corresponds to a cluster medoid. For example, the lth individual cl(g) in P(g) can be written as in (10)clg=c1lg,…,cklg,where cil(g)(i∈{1,…,k}) is a real number in the range (0,n] and n is the number of data objects. Next, cil(g) is mapped into an integer ⌈cil(g)⌉, which represents the index of x⌈cil(g)⌉. It means that we use x⌈cil(g)⌉ as the ith cluster medoid δil(g) for the individual cl(g). All the k cluster medoids can be gotten as (11)δlg=δ1lg,…,δklg,where δil(g)=x⌈cil(g)⌉.In order to make the population have a higher probability to fall into the promising regions of the solution space, the initial populationP(0)=[cl(0)]pop_size(l∈{1,…,pop_size}) is generated by using a random strategy and a preclustering strategy. pop_α is a parameter that determines the proportion of individuals generated by using the random strategy to the whole individuals. pop_α∗pop_size and (1-pop_α)∗pop_size individuals are generated by using the random strategy and preclustering strategy, respectively. In our algorithm, each individual is a tradeoff between Euclidean distance and Path distance measures; that is to say, each individual implies a combination of Euclidean distance measure and Path distance measure. Hence, the preclustering strategy is performed by using a preclustering algorithm based on several different distance combinations. By adjusting the weights for Euclidean distance and Path distance measures, we can get many different distance combinations. For simplicity, we set four distance combinations including only Euclidean distance (ED), only Path distance (PD), combining the Euclidean and Path distances directly (EPD), and normalizing the Euclidean and Path distances within the range [0,1] (NEPD). Kmedoids algorithm can be used as the preclustering algorithm. Hence, (1-pop_α)∗pop_size individuals are generated by using four preclustering algorithms, which are (1) Kmedoids algorithm based on ED (KM(ED)), (2) Kmedoids algorithm based on PD (KM(PD)), (3) Kmedoids algorithm based on EPD (KM(EPD)), and (4) Kmedoids algorithm based on NEPD (KM(NEPD)). We hope that the individuals generated by using different preclustering algorithms have the same number, which is (1-pop_α)∗pop_size/4. The procedure of initialization of F-MFCMDM is shown in Algorithm 1.Algorithm 1:Initialization of F-MFCMDM.
Input: Dataset X=[xj]n, cluster number k, population size pop_size, proportion parameter pop_α, four distance combinationsED, PD, EPD and NEPD. Output:Initial population P(0)=[cl(0)]pop_size. for each individual c l ( 0 ) ( l = 1 : p o p _ α ∗ p o p _ s i z e ) do Setcil(0)(i=1:k)= a random real number from (0,n]. end while l < p o p _ s i z e do Setl=l+1, cl(0)=KM(ED,k). Setl=l+1, cl(0)=KM(PD,k). Setl=l+1, cl(0)=KM(EPD,k). Setl=l+1, cl(0)=KM(NEPD,k). end


## 3.4. Evolutionary Operators

In this subsection, the(g+1)th generation population P(g+1)=[cl(g+1)]pop_size is generated by applying some evolutionary operators on the gth generation population P(g)=[cl(g)]pop_size, where l∈{1,…,pop_size}. Next, we introduce the details of each evolutionary operator in turn.


### 3.4.1. RMMEDA Operator

RMMEDA employs the estimation of distribution algorithms (EDA) to generate the offspring population. In RMMEDA, an assumption is that the Pareto set of a multiobjective optimization problem (MOP) is an(M-1)-dimensional piecewise continuous manifold, which is a regularity property of a continuous MOP [36]. According to this assumption, a probability model will be built by employing local principal component analysis (PCA) algorithm and the new offspring solutions are sampled from this model. We call it RMMEDA operator and it mainly consists of two operators, modeling operator and reproduction operator. The offspring population RP(g)=[crl(g)]pop_size generated by RMMEDA operator is shown in Algorithm 2.Algorithm 2:RMMEDA operator.
Input: The gth generation population, P(g)=[cl(g)]pop_size. Output: The offspring population, RP(g)=[crl(g)]pop_size. (a)Step1: Modeling operator: Learn the distribution of the solutions in P(g) and build the probability model. (i) PartitionP(g) into a set of disjoint clusters by the local PCA algorithm. (ii) For each cluster, find the first(M-1) principal subspaces. (iii) Extend each of the directions in each cluster to cover the whole Pareto front. (b)Step2: Reproduction operator: Sample pop size individuals from the probability model to generate the offspring populationRP(g)=[crl(g)]pop_size.


### 3.4.2. Differential Evolution Operator

RMMEDA operator works very well when the regularity of solutions is obvious. However, in the initial generations, the solutions have no obvious regularity. Thus, it makes the convergence speed of population very slow. In order to overcome this limitation, we apply differential evolution operator (DE operator) to generate another offspring population,DP(g)=[cdl(g)]pop_size. It is noted that DE operator works on P(g). For the lth individual cdl(g) in DP(g), it is generated by considering two operators. The first operator is used to increase the diversity of population and it is shown in the following:(12)cdilg=cir1g+λ1·cir2g-cir3gifrandi0,1<Cr1ori=irand,cilgotherwise,where r1, r2, and r3 are three integers that are selected randomly from {1,…,pop_size}. cil(g) is the ith gene in the individual cl(g). λ1 is a scaling factor, which controls the weights of different individuals. randi(0,1) is a uniformly distributed random number from [0,1], which is generated for each gene i. Cr1∈[0,1] is the crossover control parameter. irand is a randomly chosen integer from {1,…,k} and it ensures that at least one of genes in cdil is different with that in cil.The second operator is used to push the population quickly towards the global optima and it is shown in(13)cdilg=cibestlg+λ2·cir1g-cilgifrandi0,1<Cr2ori=irand,cilgotherwise,where λ2 and Cr2 are similar with λ1 and Cr1, respectively. cbestl(g) is the best individual in the Pareto front of P(g) for cil(g).Generally speaking, a Pareto front contains more than one solution. For thelth individual cl(g), only one solution in Pareto front can be used as cbestl(g) in (13). In this paper, cbestl(g) is selected from the Pareto front by using the nearest criterion. Firstly, we calculate the Euclidean distances in objective function between the individual cl(g) and each nondominated solution in the Pareto front. Secondly, the nondominated solution with the minimum Euclidean distance is used as the cbestl(g). For example, as shown in Figure 1, there are four nondominated solutions, PF1, PF2, PF3, and PF4, in Pareto front. By computing the Euclidean distance from each nondominated solution to the cl(g) in objective function, PF3 is the nearest one to cl(g). Hence, we select PF3 as cbestl(g) for cl(g).Figure 1
An illustration of finding the best individual forcl(g).The offspring populationDP(g)=[cdl(g)]pop_size generated by DE operator is shown in Algorithm 3. Note that only one operator is used for generating the cdl(g) and which one can be selected depends on a mutation parameter muta_α. muta_α is computed by using (14). The value of muta_α decreases in the range between [0,1] as the number of generations g increases. In the initial stage, the first operator may be selected in a higher probability. On the contrary, the second operator may be selected in a higher probability in the later stage. randl(0,1) is a uniformly distributed random number from [0,1], which is generated for the lth individual.(14)muta_α=exp⁡1-max_gmax_g+1-g.Algorithm 3:DE operator.
Input: The gth generation population, P(g)=[cl(g)]pop_size. Output: The offspring population, DP(g)=[cdl(g)]pop_size. Computemuta_α by using Eq. (14). for each individual c d l ( g ) ( l = 1 : p o p _ s i z e ) do if r a n d l ( 0,1 ) ≤ m u t a _ α then Generate cdl(g) by using Eq. (12). else Generate cdl(g) by using Eq. (13). end end


### 3.4.3. Selection Operator

After RMMEDA and DE operators, we can get three populations, i.e., current populationP(g)=[cl(g)]pop_size, the offspring population generated by RMMEDA operator RP(g)=[crl(g)]pop_size, and the offspring population generated by DE operator DP(g)=[cdl(g)]pop_size. To ensure that the population size is equal with the pop_size and the favorable solutions are preserved, a selection operator is executed to preserve individuals with higher fitness and to eliminate individuals with lower fitness. In F-MFCMDM, crowded binary tournament selection method proposed in [38] is employed to select the better individuals. In selection operator, all of the individuals in P(g)∪RP(g)∪DP(g) are ranked based on nondominated sorting and assigned with crowding distance. The individuals with lower ranking and higher crowding distance can be selected as the new population P(g+1).


## 3.4.1. RMMEDA Operator

RMMEDA employs the estimation of distribution algorithms (EDA) to generate the offspring population. In RMMEDA, an assumption is that the Pareto set of a multiobjective optimization problem (MOP) is an(M-1)-dimensional piecewise continuous manifold, which is a regularity property of a continuous MOP [36]. According to this assumption, a probability model will be built by employing local principal component analysis (PCA) algorithm and the new offspring solutions are sampled from this model. We call it RMMEDA operator and it mainly consists of two operators, modeling operator and reproduction operator. The offspring population RP(g)=[crl(g)]pop_size generated by RMMEDA operator is shown in Algorithm 2.Algorithm 2:RMMEDA operator.
Input: The gth generation population, P(g)=[cl(g)]pop_size. Output: The offspring population, RP(g)=[crl(g)]pop_size. (a)Step1: Modeling operator: Learn the distribution of the solutions in P(g) and build the probability model. (i) PartitionP(g) into a set of disjoint clusters by the local PCA algorithm. (ii) For each cluster, find the first(M-1) principal subspaces. (iii) Extend each of the directions in each cluster to cover the whole Pareto front. (b)Step2: Reproduction operator: Sample pop size individuals from the probability model to generate the offspring populationRP(g)=[crl(g)]pop_size.


## 3.4.2. Differential Evolution Operator

RMMEDA operator works very well when the regularity of solutions is obvious. However, in the initial generations, the solutions have no obvious regularity. Thus, it makes the convergence speed of population very slow. In order to overcome this limitation, we apply differential evolution operator (DE operator) to generate another offspring population,DP(g)=[cdl(g)]pop_size. It is noted that DE operator works on P(g). For the lth individual cdl(g) in DP(g), it is generated by considering two operators. The first operator is used to increase the diversity of population and it is shown in the following:(12)cdilg=cir1g+λ1·cir2g-cir3gifrandi0,1<Cr1ori=irand,cilgotherwise,where r1, r2, and r3 are three integers that are selected randomly from {1,…,pop_size}. cil(g) is the ith gene in the individual cl(g). λ1 is a scaling factor, which controls the weights of different individuals. randi(0,1) is a uniformly distributed random number from [0,1], which is generated for each gene i. Cr1∈[0,1] is the crossover control parameter. irand is a randomly chosen integer from {1,…,k} and it ensures that at least one of genes in cdil is different with that in cil.The second operator is used to push the population quickly towards the global optima and it is shown in(13)cdilg=cibestlg+λ2·cir1g-cilgifrandi0,1<Cr2ori=irand,cilgotherwise,where λ2 and Cr2 are similar with λ1 and Cr1, respectively. cbestl(g) is the best individual in the Pareto front of P(g) for cil(g).Generally speaking, a Pareto front contains more than one solution. For thelth individual cl(g), only one solution in Pareto front can be used as cbestl(g) in (13). In this paper, cbestl(g) is selected from the Pareto front by using the nearest criterion. Firstly, we calculate the Euclidean distances in objective function between the individual cl(g) and each nondominated solution in the Pareto front. Secondly, the nondominated solution with the minimum Euclidean distance is used as the cbestl(g). For example, as shown in Figure 1, there are four nondominated solutions, PF1, PF2, PF3, and PF4, in Pareto front. By computing the Euclidean distance from each nondominated solution to the cl(g) in objective function, PF3 is the nearest one to cl(g). Hence, we select PF3 as cbestl(g) for cl(g).Figure 1
An illustration of finding the best individual forcl(g).The offspring populationDP(g)=[cdl(g)]pop_size generated by DE operator is shown in Algorithm 3. Note that only one operator is used for generating the cdl(g) and which one can be selected depends on a mutation parameter muta_α. muta_α is computed by using (14). The value of muta_α decreases in the range between [0,1] as the number of generations g increases. In the initial stage, the first operator may be selected in a higher probability. On the contrary, the second operator may be selected in a higher probability in the later stage. randl(0,1) is a uniformly distributed random number from [0,1], which is generated for the lth individual.(14)muta_α=exp⁡1-max_gmax_g+1-g.Algorithm 3:DE operator.
Input: The gth generation population, P(g)=[cl(g)]pop_size. Output: The offspring population, DP(g)=[cdl(g)]pop_size. Computemuta_α by using Eq. (14). for each individual c d l ( g ) ( l = 1 : p o p _ s i z e ) do if r a n d l ( 0,1 ) ≤ m u t a _ α then Generate cdl(g) by using Eq. (12). else Generate cdl(g) by using Eq. (13). end end


## 3.4.3. Selection Operator

After RMMEDA and DE operators, we can get three populations, i.e., current populationP(g)=[cl(g)]pop_size, the offspring population generated by RMMEDA operator RP(g)=[crl(g)]pop_size, and the offspring population generated by DE operator DP(g)=[cdl(g)]pop_size. To ensure that the population size is equal with the pop_size and the favorable solutions are preserved, a selection operator is executed to preserve individuals with higher fitness and to eliminate individuals with lower fitness. In F-MFCMDM, crowded binary tournament selection method proposed in [38] is employed to select the better individuals. In selection operator, all of the individuals in P(g)∪RP(g)∪DP(g) are ranked based on nondominated sorting and assigned with crowding distance. The individuals with lower ranking and higher crowding distance can be selected as the new population P(g+1).


## 3.5. Outputting the Best Clustering Result

In the final generation of F-MFCMDM, the Pareto front is obtained. As we all know, all the solutions in the Pareto front are equally important and each solution corresponds tok cluster medoids. In most real world problems, a single solution should be selected from these solutions. There are two widely used strategies to select the best solution. The first strategy is to employ an additional validity index such as VI [32] to select the best solution. And the second strategy is to use a semisupervised method [39] to select it. Since some additional validity indices are also based on Euclidean distance, we use the semisupervised method to achieve our goal in this paper.In the semisupervised method, some data objects are chosen as the test patterns and their class labels are known. Firstly, each individual in Pareto front is decoded intok cluster medoids by using (11). Secondly, the class label of each test pattern is assigned based on the nearest medoid criterion. A data object xj should be assigned into the ith cluster if it satisfies the following:(15)i=mini∈1,…,k⁡dxj,δi.However, the distance measures in F-MFCMDM are not unique. And each individual needs to be decoded by using an appropriate distance measure. As introduced in Section 3.3, each individual implies a combination of Euclidean distance and Path distance. In this subsection, we apply ED, PD, EPD, and NEPD as four candidate distance combinations that can be selected for each individual. Based on this analysis, each individual in Pareto front can be decoded into four clustering results by using four distance combinations. If the number of individuals in Pareto front is Nnon, we can obtain Nnon∗4 clustering results for the test patterns. Thirdly, Minkowski Score is used to measure the amount of misclassification. The Minkowski score (MS) is then defined as in (16)MS=sd+dsss+sd,where ss is the number of object pairs having same class labels belonging to the same clusters, sd is the number of object pairs having different class labels belonging to the same clusters, and ds is the number of object pairs having same class labels belonging to different clusters. A lower score indicates a better solution and a better distance combination. Finally, after the scores of Nnon∗4 clustering results have been calculated and the solution and the distance combination with the minimum Minkowski score are chosen as the best solution and the best distance combination, respectively, they can be used to partition the remaining objects.


## 3.6. F-MFCMDM-UK

As mentioned in the previous section, the cluster number should be provided by user in advance. However, in most of real world applications, this parameter is difficult to get. In this subsection, we try to get it automatically by designing two appropriate objective functions. We call it ‘multiobjective fuzzy clustering based on multiple distance measures with unknownk’ (F-MFCMDM-UK). Many operators in F-MFCMDM-UK are similar with those in F-MFCMDM. We will mainly introduce the different operators, which are objective function computation and initialization scheme.


### 3.6.1. Objective Function Computation

Validity index is a widely used approach to detect the optimal cluster number automatically and it works by looking for a balance between the compactness of each cluster and separation between each pair of clusters. Most of existing validity indices are inapplicable in here. Similar to the analysis above, most of them are designed based on Euclidean distance. Therefore, we need to construct two new objective functions based on two distance spaces, respectively. Unlike F-MFCMDM, each objective function in F-MFCMDM-UK should consider the balance between compactness and separation in order to detect optimal cluster number automatically. Based on this analysis, the two new objective functions are rewritten as(17)V1δ=F1mini1≠i2⁡d1δi1,δi2,V2δ=F2mini1≠i2⁡d2δi1,δi2,where i1,i2∈{1,…,k}. Let us make the following comments on the two objective functions. V1 and V2 are two ratios of compactness and separation based on Euclidean distance and Path distance respectively. On the one hand, two factors F1 and F2 tend to decrease as the cluster number k increases. On the other hand, two factors, d1(δi1,δi2) and d2(δi1,δi2), measuring the minimum separations between each pair of clusters, also tend to decrease as the cluster number k increases. Each individual is a tradeoff not only between Euclidean distance and Path distance but also between compactness and separation. By optimizing V1 and V2 simultaneously, we can detect the optimal cluster number k∗ automatically.


### 3.6.2. Encoding and Initialization Schemes

The optimal cluster numberk∗ in F-MFCMDM-UK is unknown and it is assumed to lie in the range of {kmin,…,kmax}, where kmin and kmax are the acceptable lower bound and upper bound of the cluster number, respectively. The length of an individual in F-MFCMDM-UK is kmax+1. The first kmax genes represent the cluster medoids and the last gene is an additional label denoting how many medoids are used for clustering. The lth individual cl can be written as in the following:(18)cl=c1l,…,ckmaxl,cll,where {c1l,…,ckmaxl} are the first kmax genes, cil∈(0,n], and i∈{1,…,kmax}. cll is the last position, which is a real number and cll∈[kmin,kmax]. In F-MFCMDM-UK, the first ⌈cll⌉ genes are the valid genes for the objective functions calculation. The valid individual cvl can be expressed as in (19)cvl=c1l,…,cclll.The ⌈cll⌉ medoids can be gotten by using (11).In F-MFCMDM-UK, the random strategy and the preclustering strategy are also used to generate the initial populationP(0)=[cl(0)]pop_size, where l∈{1,…,pop_size}. Similar to Section 3.3, pop_α∗pop_size and (1-pop_α)∗pop_size individuals are generated by using the random strategy and the preclustering strategy, respectively. Since the cluster number is unknown in F-MFCMDM-UK, (1-pop_α)∗pop_size individuals are generated by using the preclustering strategy not only with different distance combinations but also with different cluster numbers. There are four distance combinations and (kmax-kmin+1) different cluster numbers can be selected; in other words, the (1-pop_α)∗pop_size individuals are generated by using 4∗(kmax-kmin+1) preclustering algorithms. In addition, the label gene cll in the lth individual corresponds to the cluster number of the individual. If the individual cl is generated with k′ cluster number, the cll in cl is set to k′-0.5. The procedure of initialization of F-MFCMDM-UK is shown in Algorithm 4.Algorithm 4:Initialization of F-MFCMDM-UK.
Input: Dataset X=[xj]n, population size pop_size, proportion parameter pop_α, the lower and the upper bound of the cluster numberkmin and kmax, four distance measures ED, PD, EPD and NEPD. Output: Initial population P(0)=[cl(0)]pop_size. for each individual c l ( 0 ) ( l = 1 : p o p _ α ∗ p o p _ s i z e ) do Setcil(0)(i=1:kmax)= a random real number from (0,n] andcll(0)= a random real number from [kmin,kmax]. end k t e m p = k m i n. while l < p o p _ s i z e do ifktemp≥kmaxthen ktemp=kmin. end l=l+1, cil(0)(i=1:kmax)=KM(ED,ktemp), cll(0) is set to ktemp-0.5. l=l+1, cil(0)(i=1:kmax)=KM(PD,ktemp), cll(0) is set to ktemp-0.5. l=l+1, cil(0)(i=1:kmax)=KM(EPD,ktemp), cll(0) is set to ktemp-0.5. l=l+1, cil(0)(i=1:kmax)=KM(NEPD,ktemp), cll(0) is set to ktemp-0.5. end


## 3.6.1. Objective Function Computation

Validity index is a widely used approach to detect the optimal cluster number automatically and it works by looking for a balance between the compactness of each cluster and separation between each pair of clusters. Most of existing validity indices are inapplicable in here. Similar to the analysis above, most of them are designed based on Euclidean distance. Therefore, we need to construct two new objective functions based on two distance spaces, respectively. Unlike F-MFCMDM, each objective function in F-MFCMDM-UK should consider the balance between compactness and separation in order to detect optimal cluster number automatically. Based on this analysis, the two new objective functions are rewritten as(17)V1δ=F1mini1≠i2⁡d1δi1,δi2,V2δ=F2mini1≠i2⁡d2δi1,δi2,where i1,i2∈{1,…,k}. Let us make the following comments on the two objective functions. V1 and V2 are two ratios of compactness and separation based on Euclidean distance and Path distance respectively. On the one hand, two factors F1 and F2 tend to decrease as the cluster number k increases. On the other hand, two factors, d1(δi1,δi2) and d2(δi1,δi2), measuring the minimum separations between each pair of clusters, also tend to decrease as the cluster number k increases. Each individual is a tradeoff not only between Euclidean distance and Path distance but also between compactness and separation. By optimizing V1 and V2 simultaneously, we can detect the optimal cluster number k∗ automatically.


## 3.6.2. Encoding and Initialization Schemes

The optimal cluster numberk∗ in F-MFCMDM-UK is unknown and it is assumed to lie in the range of {kmin,…,kmax}, where kmin and kmax are the acceptable lower bound and upper bound of the cluster number, respectively. The length of an individual in F-MFCMDM-UK is kmax+1. The first kmax genes represent the cluster medoids and the last gene is an additional label denoting how many medoids are used for clustering. The lth individual cl can be written as in the following:(18)cl=c1l,…,ckmaxl,cll,where {c1l,…,ckmaxl} are the first kmax genes, cil∈(0,n], and i∈{1,…,kmax}. cll is the last position, which is a real number and cll∈[kmin,kmax]. In F-MFCMDM-UK, the first ⌈cll⌉ genes are the valid genes for the objective functions calculation. The valid individual cvl can be expressed as in (19)cvl=c1l,…,cclll.The ⌈cll⌉ medoids can be gotten by using (11).In F-MFCMDM-UK, the random strategy and the preclustering strategy are also used to generate the initial populationP(0)=[cl(0)]pop_size, where l∈{1,…,pop_size}. Similar to Section 3.3, pop_α∗pop_size and (1-pop_α)∗pop_size individuals are generated by using the random strategy and the preclustering strategy, respectively. Since the cluster number is unknown in F-MFCMDM-UK, (1-pop_α)∗pop_size individuals are generated by using the preclustering strategy not only with different distance combinations but also with different cluster numbers. There are four distance combinations and (kmax-kmin+1) different cluster numbers can be selected; in other words, the (1-pop_α)∗pop_size individuals are generated by using 4∗(kmax-kmin+1) preclustering algorithms. In addition, the label gene cll in the lth individual corresponds to the cluster number of the individual. If the individual cl is generated with k′ cluster number, the cll in cl is set to k′-0.5. The procedure of initialization of F-MFCMDM-UK is shown in Algorithm 4.Algorithm 4:Initialization of F-MFCMDM-UK.
Input: Dataset X=[xj]n, population size pop_size, proportion parameter pop_α, the lower and the upper bound of the cluster numberkmin and kmax, four distance measures ED, PD, EPD and NEPD. Output: Initial population P(0)=[cl(0)]pop_size. for each individual c l ( 0 ) ( l = 1 : p o p _ α ∗ p o p _ s i z e ) do Setcil(0)(i=1:kmax)= a random real number from (0,n] andcll(0)= a random real number from [kmin,kmax]. end k t e m p = k m i n. while l < p o p _ s i z e do ifktemp≥kmaxthen ktemp=kmin. end l=l+1, cil(0)(i=1:kmax)=KM(ED,ktemp), cll(0) is set to ktemp-0.5. l=l+1, cil(0)(i=1:kmax)=KM(PD,ktemp), cll(0) is set to ktemp-0.5. l=l+1, cil(0)(i=1:kmax)=KM(EPD,ktemp), cll(0) is set to ktemp-0.5. l=l+1, cil(0)(i=1:kmax)=KM(NEPD,ktemp), cll(0) is set to ktemp-0.5. end


## 3.7. Procedure of F-MFCMDM and F-MFCMDM-UK

The framework of the proposed algorithm is shown in Figure2.Figure 2
Flowchart of F-MFCMDM (F-MFCMDM-UK).


## 4. Experimental Results and Analysis

In this section, four groups of experiments are set up to evaluate the performance of F-MFCMDM and F-MFCMDM-UK. The first experiment is to show that F-MFCMDM can partition the dataset with different structures by combining Euclidean distance and Path distance. The second experiment is to test the efficiency of the new evolutionary operator by combining DE operator and RMMEDA operator. The third experiment is to show that F-MFCMDM-UK can not only partition the dataset with different structures but also detect the optimal cluster number automatically. And the fourth experiment is to show the computation cost of F-MFCMDM and F-MFCMDM-UK, which have less time cost than the related works.Fourteen datasets are used to evaluate the proposed algorithms. These datasets can be divided into three groups and they are spherical-type datasets as shown in Figure3(a), irregular-type datasets as shown in Figure 3(b), and real-life datasets. The spherical-type datasets contain four artificial datasets and each cluster in these datasets is distributed with a spherical structure. The clusters in Separated1 and Separated2 are separated with each other, and the clusters in Connected1 and Connected2 are overlapped with each other. The four datasets are used to test the validity of F-MFCMDM for Euclidean distance. For the irregular-type datasets, the two datasets Spiral and Flame are widely used datasets in many other literatures [40, 41] and the other two datasets, Circle and Rect, are generated artificially. The four datasets have clusters with irregular structures and can be used to test the validity of F-MFCMDM for Path distance. And the real-life datasets contain six datasets, named Iris, Glass, Soybean, Seeds Wine, and Liver, which are widely used UCI datasets and can be used to test the validity of F-MFCMDM for real world datasets. The details of these datasets in terms of the number of objects, the number of dimensions, and the number of clusters are summarized in Table 1.Table 1
The information of the test datasets.
Datasets Number of objects Number of dimensions Number of clusters Separated1 150 2 3  Separated2 250 3 5  Connected1 150 2 3  Connected2 250 2 5  Spiral 312 2 3  Flame 240 2 2  Circle 1000 2 3  Rect 1200 2 3  Iris 150 4 3  Glass 214 8 6  Soybean 47 35 4  Seeds 210 7 3  Wine 178 13 3  Liver 345 6 2Figure 3
(a) Spherical-type datasets, (b) Irregular-type datasets.
(a) (b)


### 4.1. Experiments for F-MFCMDM

This subsection will test the validity of F-MFCMDM. The parameters of F-MFCMDM are as follows. We setpop_α to 0.5 to ensure that the individuals generated at random have a large proportion. Since the remaining individuals are generated by four preclustering algorithms, the pop_size should satisfy (20)1-pop_α∗pop_size4≥β,where β is a parameter that can avoid the influence arising from each preclustering algorithm if it runs only once, and it should satisfy β>2. Taking pop_α=0.5 into (20), the pop_size should satisfy (21)pop_size≥8∗β.Meanwhile, the nondominated solutions in the final generation are in fact less than 100. Therefore, we set pop_size to 100 and it is sufficient to store all nondominated solutions for all the test datasets in the following experiments. It is clear that the accuracy of the best clustering result may be improved by increasing the max_g. Nevertheless, the Pareto front had not changed in less iterations because some initial individuals are generated by using four preclustering algorithms in Algorithm 1. Hence, we set max_g to 100 in this experiment. The λ1 and λ2 are all set to 1.0 and the Cr1 and Cr2 are set to 0.5 and 0.9, respectively. The parameters of F-MFCMDM are listed in Table 2.Table 2
Parameters setting of F-MFCMDM algorithm.
Parameters Description Setting pop_size Population size 100 max_g Maximum number of generations 100 p o p _ α Initialization parameter 0.5 λ1 Scaling factor 1 λ 2 Scaling factor 1 C r 1 Crossover control parameter 0.5 C r 2 Crossover control parameter 0.9Three metrics, Rand index (RI), F-measure (F), and Minkowski score (MS) (as shown in (16)), are used to evaluate the performance of the algorithms quantitatively. RI and F are defined in (22). It is noted that the class label of each object is known beforehand in the three metrics.(22)RI=ss+ddss+sd+ds+dd,F=2∗Precision∗RecallPrecision+Recall,where Precision=ss/ss+sd and Recall=ss/ss+ds. ss, sd, and ds have been defined in Section 3.5. dd is the number of object pairs having different class labels belonging to different clusters. Note that the higher the value of RI(F) is, the better the clustering will be.Firstly, we analyze the Pareto front obtained by using F-MFCMDM in a single run. Connected1 and Circle are chosen as the test datasets because Connected1 has three spherical clusters and Circle has three irregular clusters. The Pareto front of Connected1 is presented in Figure4(a). There are 40 nondominated solutions in the Pareto front. From left to right in Figure 4(a), F1 increases as F2 decreases. We select three meaningful nondominated solutions to analyze the Pareto front. All the three nondominated solutions are decoded into four clustering results based on four candidate distance combinations. Figures 4(b)–4(d) correspond to the nondominated solutions marked with red, green, and blue color in the Pareto front, respectively. The first subfigure in Figure 4(c) is the best clustering result and it is obtained by the nondominated solution marked with green color based on ED. We can know that the nondominated solution marked with green color corresponds to the best solution and ED is the best distance combination for Connected1.Figure 4
(a) The Pareto front of Connected1 obtained by using F-MFCMDM in a single run, (b)-(d) The clustering results correspond to the nondominated solutions marked with red, green and blue color in Pareto front respectively.
(a) (b) (c) (d)The Pareto front of Circle is presented in Figure5(a). There are 61 nondominated solutions in the Pareto front. Figures 5(b)–5(d) correspond to the nondominated solutions marked with red, green, and blue color in the Pareto front, respectively. Among the twelve subfigures, three of them are the best clustering results including the second subfigure in Figure 5(c) and the second and the fourth subfigures in Figure 5(d). The second subfigure in Figure 5(c) corresponds to the nondominated solution marked with green color in the Pareto front based on PD. The second and the fourth subfigures in Figure 5(d) correspond to the nondominated solution marked with blue color in the Pareto front based on PD and NEPD, respectively. For this dataset, Path distance is more dominant than Euclidean distance. The two experiments show that Euclidean distance is suitable for datasets with spherical structures and PD is suitable for datasets with irregular structures.Figure 5
(a) The Pareto front of Circle obtained by using F-MFCMDM in a single run, (b)-(d) The clustering results correspond to the nondominated solutions marked with red, green and blue color in Pareto front respectively.Secondly, we compare F-MFCMDM with some other fuzzy clustering algorithms based on different distance combination strategies. The first compared method is SFCMdd, which is the fuzzy Kmedoids clustering algorithm based on a single distance measure. SFCMdd(ED) and SFCMdd(PD) represent the SFCMdd based onED and PD, respectively. The second compared method is MFCMdd, which is the fuzzy Kmedoids clustering algorithm based on multiple distance measures. MFCMdd(EPD) and MFCMdd(NEPD) represent the MFCMdd based on EPD and NEPD, respectively. The third compared method is MFCMdd-RWL, which is the fuzzy Kmedoids clustering algorithm with relevant weights for multiple distance matrices estimated locally. The fourth compared method is MFCMdd-RWG, which is the fuzzy Kmedoids clustering algorithm with relevant weights for multiple distance matrices estimated globally. Both MFCMdd-RWL and MFCMdd-RWG are executed based on ED and PD. All the above four algorithms are from [14] and they apply the cluster medoid to represent a cluster. The fifth compared method is FCM, which applies the cluster center to represent a cluster. The fuzzy factor m is set to 2 for all algorithms and the weight factor is set to 2 for MFCMdd-RWL and MFCMdd-RWG.Table3 presents the comparative results of the aforementioned algorithms for the fourteen datasets in 10 independent runs. For each compared algorithm, we can obtain a clustering result in a single run. For F-MFCMDM, we can get a Pareto front in a single run and the best clustering result is selected by using the semisupervised method introduced in Section 3.5. Hence, we can get 10 clustering results for each algorithm on each dataset in 10 runs. The average and the best values of RI, F, and MS of the 10 clustering results are listed in this table. As can be seen from this table, F-MFCMDM is found to provide the best performance for eleven datasets not only in the average values but also in the best values of the three measures. For Iris, although the best values of the three measures obtained by F-MFCMDM are worse than those obtained by SFCMdd(ED), MFCMdd(NEPD), MFCMdd-RWL, and MFCMdd-RWG, the average values of the three measures obtained by F-MFCMDM are also the best. For Wine, the best values of the RI and MS obtained by F-MFCMDM are worse than those obtained by SFCMdd(PD), but the average values of the two measures obtained by F-MFCMDM are better than those obtained by SFCMdd(PD). All the algorithms can get the best values of the three measures for Separated1, since this dataset has three clearly separated clusters. It is observed from the experiments that (1) the algorithms based on two distance measures can get better performance than the ones based on a single distance measure. (2) F-MFCMDM outperforms fuzzy Kmedoids clustering algorithms with the same four distance combinations(SFCMdd(ED), SFCMdd(PD), MFCMdd(EPD), and MFCMdd(NEPD)). The reasons might be that (1) the nondominated solutions in the Pareto front not only imply the four distance combinations but also imply some other distance combinations and (2) F-MFCMDM is based on an evolutionary algorithm, which can get the global solution in a higher probability. Interestingly, both MFCMdd-RWL and MFCMdd-RWG perform well on three measures for the four irregular-type datasets; the reason might be that the compactness of each cluster based on Path distance is smaller than that of Euclidean distance. Hence, both of the two algorithms give greater weight to Path distance. This reason has been confirmed by observing the final weights for all the datasets.Table 3
The average/the bestRI, F and MS obtained by using different algorithms.
Datasets  FCM SFCMdd SFCMdd MFCMdd MFCMdd MFCMdd MFCMdd F-MFCMDM (ED) (PD) (EPD) (NEPD) -RWL -RWG Separated1 RI 1.000/1.000 0.996/1.000 0.839/1.000 0.889/1.000 0.922/1.000 0.944/1.000 0.972/1.000 1.000/1.000 F 1.000/1.000 0.993/1.000 0.816/1.000 0.866/1.000 0.908/1.000 0.933/1.000 0.967/1.000 1.000/1.000 MS 0/0 0.081/0 0.582/0 0.365/0 0.265/0 0.183/0 0.091/0 0/0  Separated2 RI 1.000/1.000 0.931/0.997 0.902/0.985 0.912/0.997 0.905/0.997 0.914/0.997 0.920/0.997 1.000/1.000 F 1.000/1.000 0.847/0.992 0.804/0.962 0.821/0.992 0.825/0.992 0.845/0.992 0.844/0.992 1.000/1.000 MS 0/0 0.516/0.126 0.674/0.276 0.585/0.126 0.591/0.126 0.536/0.126 0.551/0.126 0/0  Connected1 RI 0.947/0.947 0.937/0.940 0.718/0.879 0.918/0.940 0.877/0.940 0.860/0.921 0.790/0.921 0.957/0.957 F 0.930/0.930 0.917/0.921 0.714/0.839 0.893/0.921 0.864/0.921 0.842/0.898 0.786/0.898 0.942/0.942 MS 0.377/0.377 0.409/0.399 0.851/0.568 0.464/0.399 0.531/0.399 0.579/0.458 0.705/0.458 0.340/0.339  Connected2 RI 0.944/0.944 0.867/0.873 0.739/0.850 0.879/0.899 0.880/0.940 0.667/0.758 0.696/0.806 0.954/0.956 F 0.861/0.861 0.696/0.710 0.575/0.689 0.726/0.770 0.867/0.921 0.538/0.615 0.567/0.652 0.884/0.890 MS 0.529/0.529 0.816/0.796 1.131/0.865 0.775/0.709 0.524/0.399 1.274/1.099 1.214/0.984 0.482/0.469  Spiral RI 0.556/0.556 0.535/0.538 0.866/1.000 0.540/0.542 1.000/1.000 0.926/1.000 1.000/1.000 1.000/1.000 F 0.334/0.334 0.375/0.376 0.845/1.000 0.386/0.395 1.000/1.000 0.896/1.000 1.000/1.000 1.000/1.000 MS 1.154/1.154 1.181/1.178 0.491/0 1.174/1.172 0/0 0.259/0 0/0 0/0  Flame RI 0.745/0.745 0.655/0.788 0.572/0.920 0.667/0.751 0.684/0.861 0.976/0.983 0.980/0.983 0.964/0.975 F 0.755/0.755 0.671/0.802 0.705/0.928 0.692/0.765 0.714/0.871 0.978/0.985 0.982/0.985 0.967/0.977 MS 0.689/0.689 0.791/0.629 0.877/0.385 0.782/0.681 0.752/0.508 0.208/0.175 0.190/0.175 0.249/0.214  Circle RI 0.580/0.584 0.578/0.638 0.894/1.000 0.625/0.693 0.835/1.000 1.000/1.000 1.000/1.000 1.000/1.000 F 0.391/0.400 0.441/0.496 0.875/1.000 0.485/0.554 0.774/1.000 1.000/1.000 1.000/1.000 1.000/1.000 MS 1.122/1.117 1.124/1.042 0.398/0 1.059/0.960 0.640/0 0/0 0/0 0/0  Rect RI 0.622/0.622 0.615/0.669 0.890/1.000 0.638/0.711 1.000/1.000 0.944/1.000 0.888/1.000 1.000/1.000 F 0.480/0.480 0.492/0.562 0.856/1.000 0.513/0.607 1.000/1.000 0.924/1.000 0.857/1.000 1.000/1.000 MS 0.986/0.986 0.994/0.923 0.410/0 0.963/0.862 0/0 0.207/0 0.415/0 0/0  Iris(3) RI 0.881/0.881 0.819/0.958 0.805/0.913 0.786/0.795 0.801/0.974 0.796/0.974 0.798/0.974 0.942/0.942 F 0.823/0.823 0.764/0.937 0.764/0.872 0.734/0.738 0.761/0.961 0.766/0.961 0.756/0.961 0.914/0.914 MS 0.599/0.599 0.722/0.356 0.755/0.511 0.801/0.784 0.757/0.279 0.765/0.279 0.760/0.279 0.417/0.417  Glass RI 0.713/0.713 0.568/0.585 0.570/0.649 0.566/0.602 0.493/0.622 0.517/0.593 0.533/0.661 0.731/0.731 F 0.414/0.414 0.508/0.516 0.463/0.511 0.504/0.518 0.479/0.528 0.486/0.518 0.488/0.510 0.459/0.459 MS 1.044/1.044 1.280/1.255 1.274/1.154 1.282/1.230 1.381/1.198 1.350/1.244 1.326/1.134 1.012/1.012  Soybean RI 0.835/0.835 0.835/0.837 0.841/0.935 0.854/0.862 0.844/0.853 0.843/0.853 0.848/0.853 0.935/0.935 F 0.685/0.685 0.720/0.741 0.758/0.875 0.770/0.786 0.766/0.779 0.751/0.779 0.771/0.779 0.875/0.875 MS 0.786/0.786 0.786/0.782 0.742/0.495 0.738/0.718 0.765/0.742 0.766/0.742 0.754/0.742 0.495/0.495  Seeds RI 0.875/0.875 0.843/0.891 0.673/0.722 0.849/0.891 0.711/0.720 0.656/0.755 0.680/0.726 0.901/0.901 F 0.813/0.813 0.771/0.837 0.637/0.679 0.777/0.838 0.673/0.687 0.644/0.688 0.660/0.687 0.852/0.852 MS 0.613/0.613 0.682/0.571 0.986/0.913 0.670/0.571 0.930/0.916 0.997/0.857 0.970/0.907 0.545/0.545  Wine RI 0.712/0.712 0.703/0.716 0.631/0.744 0.682/0.697 0.672/0.722 0.641/0.716 0.615/0.714 0.725/0.725 F 0.580/0.580 0.582/0.623 0.564/0.625 0.589/0.625 0.588/0.601 0.590/0.607 0.558/0.627 0.679/0.679 MS 0.918/0.918 0.931/0.912 1.036/0.866 0.965/0.941 0.977/0.902 1.023/0.912 1.059/0.914 0.898/0.898  Liver RI 0.501/0.501 0.507/0.509 0.510/0.513 0.507/0.510 0.509/0.511 0.508/0.512 0.508/0.512 0.515/0.515 F 0.602/0.602 0.645/0.654 0.668/0.676 0.650/0.667 0.666/0.674 0.665/0.676 0.662/0.676 0.677/0.677 MS 0.986/0.986 0.981/0.979 0.978/0.975 0.980/0.978 0.978/0.977 0.979/0.976 0.980/0.976 0.973/0.973


### 4.2. Experiment for the New Evolutionary Operator

In this paper, we proposed a new evolutionary operator (RM+DE) which combines RMMEDA operator (RM) and Evolution operator (DE) to increase the convergence speed of F-MFCMDM. In this experiment, the new operator (RM+DE) is compared with the traditional RMMEDA operator (RM) by using the same encoding scheme and objective functions in F-MFCMDM. The two operators are executed on all of the fourteen datasets in 10 runs, respectively. Two widely used metrics, coverage (C) and diversity (D) [30], are used to assess the Pareto fronts obtained. For each dataset, we can get two Pareto fronts A and B by RM+DE and RM, respectively, in a single run. Coverage metric C can compare the relative quality of the two Pareto fronts A and B based on domination relationship. C(A,B) evaluates the proportion of solutions in B, which are dominated by solutions in A. It can be defined as shown in the following:(23)CA,B=∑b∈BI∃a∈A∧a⪯bB,where I is a truth indicator function. b is a solution in Pareto front B and a is a solution in Pareto front A. a⪯b represents that the solution b is dominated by solution a. |B| represents the number of nondominated solutions in the Pareto front B. The range of C(A,B) falls into [0,1]. A higher value of C(A,B) shows that the Pareto front A is better than the Pareto front B. C(A,B)=1 represents that each solution of B is dominated by at least one solution of A. On the other hand, C(A,B)=0 represents that no solution of B is dominated by any solution of A.Distribution metric (D) can assess the distribution of a Pareto front. It is obtained by a relative distance measure between all of nondominated solutions in the Pareto front. Given a Pareto front A, the distribution of A can be described as in (24)DA=∑l=1A-1dl-d¯A-1,where |A| represents the number of nondominated solutions in the final Pareto front. dl=∑q=1MFql+1-Fql is the sum of difference in nondominated objective function values between the lth solution and (l+1)th solution in Pareto front A. Since F-MFCMDM has two objective functions, the value of M is 2. d¯ is the mean of {d1,…,d|A|-1}. It is noted that smaller values of D indicate better uniformly distributed solutions.Table4 presents the comparative results of the average/best coverage metric C and distribution metric D obtained by using RM+DE and RM in 10 runs. Firstly, the values of C(A,B) and C(B,A) are shown in the second and third columns, respectively. The values of C(A,B) are larger than C(B,A) for most of datasets, which can show that the Pareto fronts obtained by RM+DE are superior to those obtained by RM. In particular, the best values of C(A,B) are 1 for Separated2, Connected2, Circle, Rect, and Glass in 10 runs. It shows that all solutions by RM are dominated by at least one solution by RM+DE. On the other hand, the values of C(B,A) are 0 for most of datasets, which indicates that no solutions by using RM+DE are dominated by any solution by using RM. The values of C(A,B) and C(B,A) are 0 for Spiral, which indicates that RM+DE and RM can get similar Pareto front in all runs. Secondly, the values of D(A) and D(B) are shown in the fourth and fifth columns, respectively. The Pareto fronts obtained by RM+DE have smaller average/best distribution than those obtained by using RM for almost all test datasets except Iris in 10 runs, which indicates that the Pareto fronts by using RM+DE are more uniform than those by using RM.Table 4
The average/the best ofC and D for the test datasets by using RM+DE and RM in 10 runs.
Datasets C(A,B) C(B,A) D(A) D(B) Separated1 0.520/0.720 0/0 0.594/0.593 0.797/0.595  Separated2 1.000/1.000 0/0 0.082/0.073 0.288/0.170  Connected1 0.446/0.657 0/0 0.456/0.450 0.614/0.492  Connected2 1.000/1.000 0/0 2.848/2.081 10.466/1.960  Spiral 0/0 0/0 7.962/7.944 8.294/7.967  Flame 0.015/0.039 0/0 85.255/85.255 88.659/88.659  Circle 0.965/1.000 0.005/0.206 33.169/29.562 124.349/101.061  Rect 0.959/1.000 0.007/0.040 2.846/2.180 7.761/3.846  Iris 0.215/0.333 0/0 13.204/13.204 11.604/10.315  Glass 0.992/1.000 0/0 0.892/0.737 2.347/1.515  Soybean 0.170/0.667 0/0 2.081/2.807 3.302/1.530  Seeds 0.584/0.778 0/0 9.105/8.956 13.722/11.223  Wine 0.790/0.889 0.003/0.017 12951/12522 17056/14900  Liver 0.239/0.316 0/0 4042/3998 4678/4335


### 4.3. Experiments for F-MFCMDM-UK

This subsection will test the validity of the updated algorithm F-MFCMDM-UK, which can detect the optimal cluster number for datasets with different structures. The acceptable lower bound of the cluster numberkmin is set to 2. The acceptable upper bound of the cluster number kmax is difficult to set because it determines the length of an individual. On the one hand, a too large kmax causes a waste of memory and time cost. On the other hand, a too small one will lead to the probability of leaving of the optimal cluster number. For simplicity, we set kmax to 10. The pop_α, λ1, λ2, Cr1, and Cr2 are the same as those in F-MFCMDM. Since (1-pop_α)∗pop_size individuals are generated by 4∗(kmax-kmin+1) preclustering algorithms, the population size pop_size should satisfy (25)1-pop_α∗pop_size4∗kmax-kmin+1≥β.Taking the pop_α, kmin, and kmax into (25), we can get the condition in (26)pop_size≥72∗β.In addition, the length of an individual in F-MFCMDM-UK is larger than that in F-MFCMDM. Hence, we set pop_size to 200 for F-MFCMDM-UK. Similarly, the max_g of F-MFCMDM-UK also needs to be greater than that of F-MFCMDM. We set max_g to 200 in F-MFCMDM-UK. The parameters settings of F-MFCMDM-UK are listed in Table 5.Table 5
Parameters setting of F-MFCMDM-UK algorithm.
Parameters Description Setting pop_size Population size 200 max_g Maximum number of generations 200 kmin Acceptable lower bound of the cluster number 2 kmax Acceptable upper bound of the cluster number 10In this subsection, we also analyze the Pareto front obtained by using F-MFCMDM-UK in a single run. Separated2 and Flame are chosen as the test datasets. The Pareto front of Separated2 is presented in Figure6(a). We can get 31 nondominated solutions in the Pareto front. Three nondominated solutions are also selected to analyze the Pareto front. Each selected nondominated solution is decoded into four clustering results based on four distance measure combinations. Apart from RI, F, and MS, the optimal cluster number (ON) is also recorded. Figures 6(b)–6(d) correspond to the nondominated solutions marked with red, green, and blue color in Pareto front, respectively. There are four subfigures which get the best clustering result and the optimal cluster number. They are the first and third subfigures in Figure 6(b) and the first and third figures in Figure 6(c). It is noted that the nondominated solution marked with red color and the nondominated solution marked with green color are very close. Furthermore, with the increment of V1 and the decrement of V2, the values of ON, RI, F, and MS are all getting worse. We can conclude that the nondominated solution marked with red or green color corresponds to the best solution. In addition, ED or EPD can be as the best distance combination. The Pareto front of Flame is presented in Figure 7(a). We can get 15 nondominated solutions in the Pareto front. Figures 7(b)–7(d) correspond to the nondominated solutions marked with red, green, and blue color in Pareto front, respectively. The nondominated solutions marked with red and green color have the same optimal cluster number (ON=3) and nondominated solution marked with blue color has another view (ON=2). By looking for the minimum MS, the second subfigure in Figure 7(c) is the best clustering result in spite of the error optimal cluster number.Figure 6
(a) The Pareto front of Separated2 obtained by using F-MFCMDM-UK in a single run, (b)-(d) The optimal cluster numbers and the clustering results correspond to the nondominated solutions marked with red, green and blue color in Pareto front respectively.
(a) (b)
O N = 5 (c)
O N = 5 (d)
O N = 2Figure 7
(a) The Pareto front of Flame obtained by using F-MFCMDM-UK in a single run, (b)-(d) The optimal cluster numbers and the clustering results correspond to the nondominated solutions marked with red, green and blue color in Pareto front respectively.
(a) (b)
O N = 3 (c)
O N = 3 (d)
O N = 2F-MFCMDM-UK is compared with some other methods. Many compared methods can be used in here. Firstly, we consider the validity index which is the most used approach to determine the optimal cluster number automatically.Vxb and Vpbm indices are used in our experiment. Secondly, some clustering algorithms based on evolutionary algorithm which can automatically detect the optimal cluster number are also used. The first is GCUK [25], which is a single objective clustering algorithm and can find the optimal cluster number by optimizing Vdb index. The second is MoMODEFC [31], which is a multiobjective clustering algorithm and can find the optimal cluster number by optimizing Jmse and Vxb simultaneously. Four compared algorithms are all based on Euclidean distance and they are not suitable for irregular-type datastes. Hence, RAC-Kmeans [24] is also used as the compared method. It detects the optimal cluster number by using a specific graph-partitioning process and is not sensitive to the choice of distance measure.The parameters of the compared methods need to be set in advance. ForVxb, Vpbm, GCUK, and MoMODEFC, both kmin and kmax are set to 2 and ⌊n⌋ [42], respectively. For RAC-Kmeans, the two parameters are set to 2 and n, respectively, and Kmeans is used as the underlying clustering technique. For GCUK and MODEFC, the pop_size and max_g are set to 200 and 200, respectively.Table6 summarizes the clustering results obtained by using F-MFCMDM-UK and the compared algorithms for several test datasets in 10 runs. ON(num) represents that the optimal cluster ON is obtained num times in 10 runs. AVE_RI, AVE_F, and AVE_MS represent the average values of RI, F, and MS, respectively, in 10 runs. F-MFCMDM-UK can get the best ON, AVE_RI, AVE_F, and AVE_MS for Separated1, Separated2, Spiral, Circle, and Iris in all runs. It indicates that F-MFCMDM-UK can detect the best optimal cluster numbers for datasets with different structures. For Connected1, all of the algorithms can detect the best ON. However, the values of AVE_RI, AVE_F, and AVE_MS obtained by F-MFCMDM-UK are worse than those obtained by Vxb, Vpbm, GCUK, and MODEFC. The reason might be that the separation in (17) influences the clustering results. Although F-MFCMDM-UK does not detect the best ON for Flame, the values of AVE_RI, AVE_F, and AVE_MS are the best. For Iris, all the algorithms indicate the best optimal cluster number. However, even among them, the values of AVE_RI, AVE_F, and AVE_MS obtained by F-MFCMDM-UK are the best. The reason is that Path distance is the best choice for this dataset with ON=2. Most of the compared algorithms except RAC-Kmeans can get acceptable clustering results for Separated1, Separated2, Connected1, Iris, and Soybean, but they get worse results for Spiral, Circle, and Flame. The reason is that these algorithms are based on Euclidean distance. RAC-Kmeans shows well for Separated1, Spiral, and Circle; nevertheless, it fails for the remaining datasets. The reason is that RAC-Kmeans is suitable for datasets with separated clusters and unsuitable for datasets with connected clusters. As can be seen from this experiment, F-MFCMDM-UK can detect the optimal cluster number not only for datasets with spherical structures but also for datasets with irregular structures.Table 6
TheON, RI, F and MS obtained by using F-MFCMDM-UK and the compared algorithms.
Datasets  Vxb Vpbm GCUK MoMODEFC RAC-Kmeans F-MFCMDM-UK Separated1 ON(num) 3(10) 3 ( 10 ) 3(10) 3 ( 10 ) 3(10) 3 ( 10 ) (3) AVE_RI 1.00 1.00 1.00 1.00 1.00 1.00 AVE_F 1.00 1.00 1.00 1.00 1.00 1.00 AVE_MS 0 0 0 0 0 0  Separated2 ON(num) 5(10) 2(10) 5 ( 9 ) , 4 ( 1 ) 5 ( 10 ) 4 ( 10 ) 5(10) (5) AVE_RI 1.00 0.68 0.99 1.00 0.920 1.00 AVE_F 1.00 0.56 0.98 1.00 0.833 1.00 AVE_MS 0 1.27 0.06 0 0.633 0  Connected1 ON(num) 3 ( 10 ) 3 ( 10 ) 3 ( 8 ) , 4 ( 2 ) 3 ( 10 ) 3(10) 3(10) (3) AVE_RI 0.95 0.95 0.92 0.93 0.68 0.91 AVE_F 0.93 0.93 0.89 0.91 0.69 0.88 AVE_MS 0.38 0.38 0.44 0.44 0.93 0.50  Spiral ON(num) 14 ( 10 ) 2(10) 3(10) 14 ( 10 ) 3(10) 3(10) (3) AVE_RI 0.68 0.50 0.56 0.68 1.00 1.00 AVE_F 0.23 0.40 0.34 0.20 1.00 1.00 AVE_MS 0.97 1.22 1.16 0.98 0 0  Circle ON(num) 6(10) 5(10) 6 ( 9 ) , 7 ( 1 ) 14(10) 3(10) 3 ( 10 ) (3) AVE_RI 0.73 0.79 0.78 0.72 1.00 1.00 AVE_F 0.47 0.62 0.59 0.38 1.00 1.00 AVE_MS 0.90 0.80 0.81 0.91 0 0  Flame ON 4(10) 2 ( 10 ) 3(10) 4 ( 10 ) 2(10) 3 ( 10 ) (2) AVE_RI 0.70 0.75 0.73 0.69 0.54 0.96 AVE_F 0.62 0.75 0.69 0.62 0.70 0.96 AVE_MS 0.75 0.69 0.71 0.75 0.92 0.26  Iris ON 2 ( 10 ) 2 ( 10 ) 2(10) 2 ( 10 ) 2 ( 10 ) 2 ( 10 ) (2 or 3) AVE_RI 0.96 0.96 0.96 0.96 0.96 1.00 AVE_F 0.96 0.96 0.96 0.96 0.96 1.00 AVE_MS 0.27 0.27 0.27 0.27 0.27 0  Soybean ON 3(10) 2 ( 10 ) 3 ( 10 ) 5(10) 3(9),4(1) 3 ( 10 ) (4) AVE_RI 0.85 0.76 0.85 0.83 0.86 0.85 AVE_F 0.78 0.69 0.78 0.66 0.79 0.78 AVE_MS 0.76 0.96 0.76 0.98 0.73 0.74


### 4.4. Experiment for the Computational Cost

According to our motivation, F-MFCMDM and F-MFCMDM-UK should have smaller computational cost than the previous algorithms MOECDM and MOEACDM. In this subsection, we illustrate the computational cost on several test datasets for the four algorithms and analyze the reasons of the results. Notice that the cluster numbers of F-MFCMDM and MOECDM are predefined in advance and those of F-MFCMDM-UK and MOEACDM are unknown. Hence, F-MFCMDM and F-MFCMDM-UK are compared with MOECDM and MOEACDM, respectively. Each algorithm is conducted in10 runs. For the sake of fairness, the proposed methods and compared methods have the same parameters (max_g, pop_size). All algorithms are performed on a personal computer with a 2.5 ghz intel core central processing unit and 4 GB memory and the code programmed in Matlab R2014b. The average running time obtained by using four algorithms is recorded in Table 7. The running time obtained by F-MFCMDM is less than that obtained by MOECDM in all test datasets. And the running time obtained by F-MFCMDM-UK is also less than that obtained by MOEACDM in all test datasets.Table 7
Average running time of MOECDM, F-MFCMDM, MOEACDM, and F-MFCMDM-UK with the samemax_g and pop_size.
Datasets (max_g,pop_size) MOECDM F-MFCMDM MOEACDM F-MFCMDM-UK Separated1 (200,200) 127 38 181 61 (500,500) 950 214 1471 356  Connected1 (200,200) 95 43 165 59 (500,500) 708 224 1163 338  Spiral (200,200) 128 52 267 86 (500,500) 928 287 1625 500  Iris (200,200) 107 43 172 69 (500,500) 868 227 1641 406  Soybean (200,200) 88 38 98 43 (500,500) 760 199 1154 247Let us discuss the reasons by analyzing the differences between the proposed algorithms and the compared algorithms. There are four main aspects in each algorithm as shown in Table8. For encoding scheme, MOECDM and MOEACDM apply label encoding to construct an individual. F-MFCMDM and F-MFCMDM-UK apply real encoding to construct an individual. The length of an individual in MOECDM, MOEACDM, F-MFCMDM, and F-MFCMDM-UK is n, n, k, and kmax, respectively. For evolutionary operator, MOECDM and MOEACDM apply crossover, mutation, and selection operators to generate the new population. F-MFCMDM and F-MFCMDM-UK apply RM+DE and selection operators to generate the new population. For objective function computation, MOECDM applies compactness between objects as objective function. MOEACDM applies the compactness in MOECDM and separation between clusters as objective function. F-MFCMDM applies compactness between objects and medoids as objective function. F-MFCMDM-UK applies compactness in F-MFCMDM and separation between medoids as objective function.Table 8
The differences of four algorithms in four aspects.
Four aspects MOECDM MOEACDM F-MFCMDM F-MFCMDM-UK  Encoding scheme label encoding real encoding  Individual length n n k k m a x  Evolutionary operator crossover, mutation and selection operators R M + D E and selection operators  Objective function compactness compactness and separation compactness compactness and separationAccording to these differences, the length of the individual greatly influences the computational cost. In MOECDM and MOEACDM, the individual is an integer vector ofn genes, where n is the number of data objects and the ith gene represents the ith data object. In F-MFCMDM, the individual is a real vector of k genes, where k is the number of clusters and the ith gene represents the ith cluster medoid. Generally speaking, for a dataset, k is much smaller than n, so the running time obtained by F-MFCMDM is less than that obtained by MOECDM. In F-MFCMDM-UK, the individual is a real vector of kmax+1 genes. In this paper, kmax+1 is also much smaller than n, so the running time obtained by F-MFCMDM-UK is also less than that obtained by MOECDM.


## 4.1. Experiments for F-MFCMDM

This subsection will test the validity of F-MFCMDM. The parameters of F-MFCMDM are as follows. We setpop_α to 0.5 to ensure that the individuals generated at random have a large proportion. Since the remaining individuals are generated by four preclustering algorithms, the pop_size should satisfy (20)1-pop_α∗pop_size4≥β,where β is a parameter that can avoid the influence arising from each preclustering algorithm if it runs only once, and it should satisfy β>2. Taking pop_α=0.5 into (20), the pop_size should satisfy (21)pop_size≥8∗β.Meanwhile, the nondominated solutions in the final generation are in fact less than 100. Therefore, we set pop_size to 100 and it is sufficient to store all nondominated solutions for all the test datasets in the following experiments. It is clear that the accuracy of the best clustering result may be improved by increasing the max_g. Nevertheless, the Pareto front had not changed in less iterations because some initial individuals are generated by using four preclustering algorithms in Algorithm 1. Hence, we set max_g to 100 in this experiment. The λ1 and λ2 are all set to 1.0 and the Cr1 and Cr2 are set to 0.5 and 0.9, respectively. The parameters of F-MFCMDM are listed in Table 2.Table 2
Parameters setting of F-MFCMDM algorithm.
Parameters Description Setting pop_size Population size 100 max_g Maximum number of generations 100 p o p _ α Initialization parameter 0.5 λ1 Scaling factor 1 λ 2 Scaling factor 1 C r 1 Crossover control parameter 0.5 C r 2 Crossover control parameter 0.9Three metrics, Rand index (RI), F-measure (F), and Minkowski score (MS) (as shown in (16)), are used to evaluate the performance of the algorithms quantitatively. RI and F are defined in (22). It is noted that the class label of each object is known beforehand in the three metrics.(22)RI=ss+ddss+sd+ds+dd,F=2∗Precision∗RecallPrecision+Recall,where Precision=ss/ss+sd and Recall=ss/ss+ds. ss, sd, and ds have been defined in Section 3.5. dd is the number of object pairs having different class labels belonging to different clusters. Note that the higher the value of RI(F) is, the better the clustering will be.Firstly, we analyze the Pareto front obtained by using F-MFCMDM in a single run. Connected1 and Circle are chosen as the test datasets because Connected1 has three spherical clusters and Circle has three irregular clusters. The Pareto front of Connected1 is presented in Figure4(a). There are 40 nondominated solutions in the Pareto front. From left to right in Figure 4(a), F1 increases as F2 decreases. We select three meaningful nondominated solutions to analyze the Pareto front. All the three nondominated solutions are decoded into four clustering results based on four candidate distance combinations. Figures 4(b)–4(d) correspond to the nondominated solutions marked with red, green, and blue color in the Pareto front, respectively. The first subfigure in Figure 4(c) is the best clustering result and it is obtained by the nondominated solution marked with green color based on ED. We can know that the nondominated solution marked with green color corresponds to the best solution and ED is the best distance combination for Connected1.Figure 4
(a) The Pareto front of Connected1 obtained by using F-MFCMDM in a single run, (b)-(d) The clustering results correspond to the nondominated solutions marked with red, green and blue color in Pareto front respectively.
(a) (b) (c) (d)The Pareto front of Circle is presented in Figure5(a). There are 61 nondominated solutions in the Pareto front. Figures 5(b)–5(d) correspond to the nondominated solutions marked with red, green, and blue color in the Pareto front, respectively. Among the twelve subfigures, three of them are the best clustering results including the second subfigure in Figure 5(c) and the second and the fourth subfigures in Figure 5(d). The second subfigure in Figure 5(c) corresponds to the nondominated solution marked with green color in the Pareto front based on PD. The second and the fourth subfigures in Figure 5(d) correspond to the nondominated solution marked with blue color in the Pareto front based on PD and NEPD, respectively. For this dataset, Path distance is more dominant than Euclidean distance. The two experiments show that Euclidean distance is suitable for datasets with spherical structures and PD is suitable for datasets with irregular structures.Figure 5
(a) The Pareto front of Circle obtained by using F-MFCMDM in a single run, (b)-(d) The clustering results correspond to the nondominated solutions marked with red, green and blue color in Pareto front respectively.Secondly, we compare F-MFCMDM with some other fuzzy clustering algorithms based on different distance combination strategies. The first compared method is SFCMdd, which is the fuzzy Kmedoids clustering algorithm based on a single distance measure. SFCMdd(ED) and SFCMdd(PD) represent the SFCMdd based onED and PD, respectively. The second compared method is MFCMdd, which is the fuzzy Kmedoids clustering algorithm based on multiple distance measures. MFCMdd(EPD) and MFCMdd(NEPD) represent the MFCMdd based on EPD and NEPD, respectively. The third compared method is MFCMdd-RWL, which is the fuzzy Kmedoids clustering algorithm with relevant weights for multiple distance matrices estimated locally. The fourth compared method is MFCMdd-RWG, which is the fuzzy Kmedoids clustering algorithm with relevant weights for multiple distance matrices estimated globally. Both MFCMdd-RWL and MFCMdd-RWG are executed based on ED and PD. All the above four algorithms are from [14] and they apply the cluster medoid to represent a cluster. The fifth compared method is FCM, which applies the cluster center to represent a cluster. The fuzzy factor m is set to 2 for all algorithms and the weight factor is set to 2 for MFCMdd-RWL and MFCMdd-RWG.Table3 presents the comparative results of the aforementioned algorithms for the fourteen datasets in 10 independent runs. For each compared algorithm, we can obtain a clustering result in a single run. For F-MFCMDM, we can get a Pareto front in a single run and the best clustering result is selected by using the semisupervised method introduced in Section 3.5. Hence, we can get 10 clustering results for each algorithm on each dataset in 10 runs. The average and the best values of RI, F, and MS of the 10 clustering results are listed in this table. As can be seen from this table, F-MFCMDM is found to provide the best performance for eleven datasets not only in the average values but also in the best values of the three measures. For Iris, although the best values of the three measures obtained by F-MFCMDM are worse than those obtained by SFCMdd(ED), MFCMdd(NEPD), MFCMdd-RWL, and MFCMdd-RWG, the average values of the three measures obtained by F-MFCMDM are also the best. For Wine, the best values of the RI and MS obtained by F-MFCMDM are worse than those obtained by SFCMdd(PD), but the average values of the two measures obtained by F-MFCMDM are better than those obtained by SFCMdd(PD). All the algorithms can get the best values of the three measures for Separated1, since this dataset has three clearly separated clusters. It is observed from the experiments that (1) the algorithms based on two distance measures can get better performance than the ones based on a single distance measure. (2) F-MFCMDM outperforms fuzzy Kmedoids clustering algorithms with the same four distance combinations(SFCMdd(ED), SFCMdd(PD), MFCMdd(EPD), and MFCMdd(NEPD)). The reasons might be that (1) the nondominated solutions in the Pareto front not only imply the four distance combinations but also imply some other distance combinations and (2) F-MFCMDM is based on an evolutionary algorithm, which can get the global solution in a higher probability. Interestingly, both MFCMdd-RWL and MFCMdd-RWG perform well on three measures for the four irregular-type datasets; the reason might be that the compactness of each cluster based on Path distance is smaller than that of Euclidean distance. Hence, both of the two algorithms give greater weight to Path distance. This reason has been confirmed by observing the final weights for all the datasets.Table 3
The average/the bestRI, F and MS obtained by using different algorithms.
Datasets  FCM SFCMdd SFCMdd MFCMdd MFCMdd MFCMdd MFCMdd F-MFCMDM (ED) (PD) (EPD) (NEPD) -RWL -RWG Separated1 RI 1.000/1.000 0.996/1.000 0.839/1.000 0.889/1.000 0.922/1.000 0.944/1.000 0.972/1.000 1.000/1.000 F 1.000/1.000 0.993/1.000 0.816/1.000 0.866/1.000 0.908/1.000 0.933/1.000 0.967/1.000 1.000/1.000 MS 0/0 0.081/0 0.582/0 0.365/0 0.265/0 0.183/0 0.091/0 0/0  Separated2 RI 1.000/1.000 0.931/0.997 0.902/0.985 0.912/0.997 0.905/0.997 0.914/0.997 0.920/0.997 1.000/1.000 F 1.000/1.000 0.847/0.992 0.804/0.962 0.821/0.992 0.825/0.992 0.845/0.992 0.844/0.992 1.000/1.000 MS 0/0 0.516/0.126 0.674/0.276 0.585/0.126 0.591/0.126 0.536/0.126 0.551/0.126 0/0  Connected1 RI 0.947/0.947 0.937/0.940 0.718/0.879 0.918/0.940 0.877/0.940 0.860/0.921 0.790/0.921 0.957/0.957 F 0.930/0.930 0.917/0.921 0.714/0.839 0.893/0.921 0.864/0.921 0.842/0.898 0.786/0.898 0.942/0.942 MS 0.377/0.377 0.409/0.399 0.851/0.568 0.464/0.399 0.531/0.399 0.579/0.458 0.705/0.458 0.340/0.339  Connected2 RI 0.944/0.944 0.867/0.873 0.739/0.850 0.879/0.899 0.880/0.940 0.667/0.758 0.696/0.806 0.954/0.956 F 0.861/0.861 0.696/0.710 0.575/0.689 0.726/0.770 0.867/0.921 0.538/0.615 0.567/0.652 0.884/0.890 MS 0.529/0.529 0.816/0.796 1.131/0.865 0.775/0.709 0.524/0.399 1.274/1.099 1.214/0.984 0.482/0.469  Spiral RI 0.556/0.556 0.535/0.538 0.866/1.000 0.540/0.542 1.000/1.000 0.926/1.000 1.000/1.000 1.000/1.000 F 0.334/0.334 0.375/0.376 0.845/1.000 0.386/0.395 1.000/1.000 0.896/1.000 1.000/1.000 1.000/1.000 MS 1.154/1.154 1.181/1.178 0.491/0 1.174/1.172 0/0 0.259/0 0/0 0/0  Flame RI 0.745/0.745 0.655/0.788 0.572/0.920 0.667/0.751 0.684/0.861 0.976/0.983 0.980/0.983 0.964/0.975 F 0.755/0.755 0.671/0.802 0.705/0.928 0.692/0.765 0.714/0.871 0.978/0.985 0.982/0.985 0.967/0.977 MS 0.689/0.689 0.791/0.629 0.877/0.385 0.782/0.681 0.752/0.508 0.208/0.175 0.190/0.175 0.249/0.214  Circle RI 0.580/0.584 0.578/0.638 0.894/1.000 0.625/0.693 0.835/1.000 1.000/1.000 1.000/1.000 1.000/1.000 F 0.391/0.400 0.441/0.496 0.875/1.000 0.485/0.554 0.774/1.000 1.000/1.000 1.000/1.000 1.000/1.000 MS 1.122/1.117 1.124/1.042 0.398/0 1.059/0.960 0.640/0 0/0 0/0 0/0  Rect RI 0.622/0.622 0.615/0.669 0.890/1.000 0.638/0.711 1.000/1.000 0.944/1.000 0.888/1.000 1.000/1.000 F 0.480/0.480 0.492/0.562 0.856/1.000 0.513/0.607 1.000/1.000 0.924/1.000 0.857/1.000 1.000/1.000 MS 0.986/0.986 0.994/0.923 0.410/0 0.963/0.862 0/0 0.207/0 0.415/0 0/0  Iris(3) RI 0.881/0.881 0.819/0.958 0.805/0.913 0.786/0.795 0.801/0.974 0.796/0.974 0.798/0.974 0.942/0.942 F 0.823/0.823 0.764/0.937 0.764/0.872 0.734/0.738 0.761/0.961 0.766/0.961 0.756/0.961 0.914/0.914 MS 0.599/0.599 0.722/0.356 0.755/0.511 0.801/0.784 0.757/0.279 0.765/0.279 0.760/0.279 0.417/0.417  Glass RI 0.713/0.713 0.568/0.585 0.570/0.649 0.566/0.602 0.493/0.622 0.517/0.593 0.533/0.661 0.731/0.731 F 0.414/0.414 0.508/0.516 0.463/0.511 0.504/0.518 0.479/0.528 0.486/0.518 0.488/0.510 0.459/0.459 MS 1.044/1.044 1.280/1.255 1.274/1.154 1.282/1.230 1.381/1.198 1.350/1.244 1.326/1.134 1.012/1.012  Soybean RI 0.835/0.835 0.835/0.837 0.841/0.935 0.854/0.862 0.844/0.853 0.843/0.853 0.848/0.853 0.935/0.935 F 0.685/0.685 0.720/0.741 0.758/0.875 0.770/0.786 0.766/0.779 0.751/0.779 0.771/0.779 0.875/0.875 MS 0.786/0.786 0.786/0.782 0.742/0.495 0.738/0.718 0.765/0.742 0.766/0.742 0.754/0.742 0.495/0.495  Seeds RI 0.875/0.875 0.843/0.891 0.673/0.722 0.849/0.891 0.711/0.720 0.656/0.755 0.680/0.726 0.901/0.901 F 0.813/0.813 0.771/0.837 0.637/0.679 0.777/0.838 0.673/0.687 0.644/0.688 0.660/0.687 0.852/0.852 MS 0.613/0.613 0.682/0.571 0.986/0.913 0.670/0.571 0.930/0.916 0.997/0.857 0.970/0.907 0.545/0.545  Wine RI 0.712/0.712 0.703/0.716 0.631/0.744 0.682/0.697 0.672/0.722 0.641/0.716 0.615/0.714 0.725/0.725 F 0.580/0.580 0.582/0.623 0.564/0.625 0.589/0.625 0.588/0.601 0.590/0.607 0.558/0.627 0.679/0.679 MS 0.918/0.918 0.931/0.912 1.036/0.866 0.965/0.941 0.977/0.902 1.023/0.912 1.059/0.914 0.898/0.898  Liver RI 0.501/0.501 0.507/0.509 0.510/0.513 0.507/0.510 0.509/0.511 0.508/0.512 0.508/0.512 0.515/0.515 F 0.602/0.602 0.645/0.654 0.668/0.676 0.650/0.667 0.666/0.674 0.665/0.676 0.662/0.676 0.677/0.677 MS 0.986/0.986 0.981/0.979 0.978/0.975 0.980/0.978 0.978/0.977 0.979/0.976 0.980/0.976 0.973/0.973


## 4.2. Experiment for the New Evolutionary Operator

In this paper, we proposed a new evolutionary operator (RM+DE) which combines RMMEDA operator (RM) and Evolution operator (DE) to increase the convergence speed of F-MFCMDM. In this experiment, the new operator (RM+DE) is compared with the traditional RMMEDA operator (RM) by using the same encoding scheme and objective functions in F-MFCMDM. The two operators are executed on all of the fourteen datasets in 10 runs, respectively. Two widely used metrics, coverage (C) and diversity (D) [30], are used to assess the Pareto fronts obtained. For each dataset, we can get two Pareto fronts A and B by RM+DE and RM, respectively, in a single run. Coverage metric C can compare the relative quality of the two Pareto fronts A and B based on domination relationship. C(A,B) evaluates the proportion of solutions in B, which are dominated by solutions in A. It can be defined as shown in the following:(23)CA,B=∑b∈BI∃a∈A∧a⪯bB,where I is a truth indicator function. b is a solution in Pareto front B and a is a solution in Pareto front A. a⪯b represents that the solution b is dominated by solution a. |B| represents the number of nondominated solutions in the Pareto front B. The range of C(A,B) falls into [0,1]. A higher value of C(A,B) shows that the Pareto front A is better than the Pareto front B. C(A,B)=1 represents that each solution of B is dominated by at least one solution of A. On the other hand, C(A,B)=0 represents that no solution of B is dominated by any solution of A.Distribution metric (D) can assess the distribution of a Pareto front. It is obtained by a relative distance measure between all of nondominated solutions in the Pareto front. Given a Pareto front A, the distribution of A can be described as in (24)DA=∑l=1A-1dl-d¯A-1,where |A| represents the number of nondominated solutions in the final Pareto front. dl=∑q=1MFql+1-Fql is the sum of difference in nondominated objective function values between the lth solution and (l+1)th solution in Pareto front A. Since F-MFCMDM has two objective functions, the value of M is 2. d¯ is the mean of {d1,…,d|A|-1}. It is noted that smaller values of D indicate better uniformly distributed solutions.Table4 presents the comparative results of the average/best coverage metric C and distribution metric D obtained by using RM+DE and RM in 10 runs. Firstly, the values of C(A,B) and C(B,A) are shown in the second and third columns, respectively. The values of C(A,B) are larger than C(B,A) for most of datasets, which can show that the Pareto fronts obtained by RM+DE are superior to those obtained by RM. In particular, the best values of C(A,B) are 1 for Separated2, Connected2, Circle, Rect, and Glass in 10 runs. It shows that all solutions by RM are dominated by at least one solution by RM+DE. On the other hand, the values of C(B,A) are 0 for most of datasets, which indicates that no solutions by using RM+DE are dominated by any solution by using RM. The values of C(A,B) and C(B,A) are 0 for Spiral, which indicates that RM+DE and RM can get similar Pareto front in all runs. Secondly, the values of D(A) and D(B) are shown in the fourth and fifth columns, respectively. The Pareto fronts obtained by RM+DE have smaller average/best distribution than those obtained by using RM for almost all test datasets except Iris in 10 runs, which indicates that the Pareto fronts by using RM+DE are more uniform than those by using RM.Table 4
The average/the best ofC and D for the test datasets by using RM+DE and RM in 10 runs.
Datasets C(A,B) C(B,A) D(A) D(B) Separated1 0.520/0.720 0/0 0.594/0.593 0.797/0.595  Separated2 1.000/1.000 0/0 0.082/0.073 0.288/0.170  Connected1 0.446/0.657 0/0 0.456/0.450 0.614/0.492  Connected2 1.000/1.000 0/0 2.848/2.081 10.466/1.960  Spiral 0/0 0/0 7.962/7.944 8.294/7.967  Flame 0.015/0.039 0/0 85.255/85.255 88.659/88.659  Circle 0.965/1.000 0.005/0.206 33.169/29.562 124.349/101.061  Rect 0.959/1.000 0.007/0.040 2.846/2.180 7.761/3.846  Iris 0.215/0.333 0/0 13.204/13.204 11.604/10.315  Glass 0.992/1.000 0/0 0.892/0.737 2.347/1.515  Soybean 0.170/0.667 0/0 2.081/2.807 3.302/1.530  Seeds 0.584/0.778 0/0 9.105/8.956 13.722/11.223  Wine 0.790/0.889 0.003/0.017 12951/12522 17056/14900  Liver 0.239/0.316 0/0 4042/3998 4678/4335


## 4.3. Experiments for F-MFCMDM-UK

This subsection will test the validity of the updated algorithm F-MFCMDM-UK, which can detect the optimal cluster number for datasets with different structures. The acceptable lower bound of the cluster numberkmin is set to 2. The acceptable upper bound of the cluster number kmax is difficult to set because it determines the length of an individual. On the one hand, a too large kmax causes a waste of memory and time cost. On the other hand, a too small one will lead to the probability of leaving of the optimal cluster number. For simplicity, we set kmax to 10. The pop_α, λ1, λ2, Cr1, and Cr2 are the same as those in F-MFCMDM. Since (1-pop_α)∗pop_size individuals are generated by 4∗(kmax-kmin+1) preclustering algorithms, the population size pop_size should satisfy (25)1-pop_α∗pop_size4∗kmax-kmin+1≥β.Taking the pop_α, kmin, and kmax into (25), we can get the condition in (26)pop_size≥72∗β.In addition, the length of an individual in F-MFCMDM-UK is larger than that in F-MFCMDM. Hence, we set pop_size to 200 for F-MFCMDM-UK. Similarly, the max_g of F-MFCMDM-UK also needs to be greater than that of F-MFCMDM. We set max_g to 200 in F-MFCMDM-UK. The parameters settings of F-MFCMDM-UK are listed in Table 5.Table 5
Parameters setting of F-MFCMDM-UK algorithm.
Parameters Description Setting pop_size Population size 200 max_g Maximum number of generations 200 kmin Acceptable lower bound of the cluster number 2 kmax Acceptable upper bound of the cluster number 10In this subsection, we also analyze the Pareto front obtained by using F-MFCMDM-UK in a single run. Separated2 and Flame are chosen as the test datasets. The Pareto front of Separated2 is presented in Figure6(a). We can get 31 nondominated solutions in the Pareto front. Three nondominated solutions are also selected to analyze the Pareto front. Each selected nondominated solution is decoded into four clustering results based on four distance measure combinations. Apart from RI, F, and MS, the optimal cluster number (ON) is also recorded. Figures 6(b)–6(d) correspond to the nondominated solutions marked with red, green, and blue color in Pareto front, respectively. There are four subfigures which get the best clustering result and the optimal cluster number. They are the first and third subfigures in Figure 6(b) and the first and third figures in Figure 6(c). It is noted that the nondominated solution marked with red color and the nondominated solution marked with green color are very close. Furthermore, with the increment of V1 and the decrement of V2, the values of ON, RI, F, and MS are all getting worse. We can conclude that the nondominated solution marked with red or green color corresponds to the best solution. In addition, ED or EPD can be as the best distance combination. The Pareto front of Flame is presented in Figure 7(a). We can get 15 nondominated solutions in the Pareto front. Figures 7(b)–7(d) correspond to the nondominated solutions marked with red, green, and blue color in Pareto front, respectively. The nondominated solutions marked with red and green color have the same optimal cluster number (ON=3) and nondominated solution marked with blue color has another view (ON=2). By looking for the minimum MS, the second subfigure in Figure 7(c) is the best clustering result in spite of the error optimal cluster number.Figure 6
(a) The Pareto front of Separated2 obtained by using F-MFCMDM-UK in a single run, (b)-(d) The optimal cluster numbers and the clustering results correspond to the nondominated solutions marked with red, green and blue color in Pareto front respectively.
(a) (b)
O N = 5 (c)
O N = 5 (d)
O N = 2Figure 7
(a) The Pareto front of Flame obtained by using F-MFCMDM-UK in a single run, (b)-(d) The optimal cluster numbers and the clustering results correspond to the nondominated solutions marked with red, green and blue color in Pareto front respectively.
(a) (b)
O N = 3 (c)
O N = 3 (d)
O N = 2F-MFCMDM-UK is compared with some other methods. Many compared methods can be used in here. Firstly, we consider the validity index which is the most used approach to determine the optimal cluster number automatically.Vxb and Vpbm indices are used in our experiment. Secondly, some clustering algorithms based on evolutionary algorithm which can automatically detect the optimal cluster number are also used. The first is GCUK [25], which is a single objective clustering algorithm and can find the optimal cluster number by optimizing Vdb index. The second is MoMODEFC [31], which is a multiobjective clustering algorithm and can find the optimal cluster number by optimizing Jmse and Vxb simultaneously. Four compared algorithms are all based on Euclidean distance and they are not suitable for irregular-type datastes. Hence, RAC-Kmeans [24] is also used as the compared method. It detects the optimal cluster number by using a specific graph-partitioning process and is not sensitive to the choice of distance measure.The parameters of the compared methods need to be set in advance. ForVxb, Vpbm, GCUK, and MoMODEFC, both kmin and kmax are set to 2 and ⌊n⌋ [42], respectively. For RAC-Kmeans, the two parameters are set to 2 and n, respectively, and Kmeans is used as the underlying clustering technique. For GCUK and MODEFC, the pop_size and max_g are set to 200 and 200, respectively.Table6 summarizes the clustering results obtained by using F-MFCMDM-UK and the compared algorithms for several test datasets in 10 runs. ON(num) represents that the optimal cluster ON is obtained num times in 10 runs. AVE_RI, AVE_F, and AVE_MS represent the average values of RI, F, and MS, respectively, in 10 runs. F-MFCMDM-UK can get the best ON, AVE_RI, AVE_F, and AVE_MS for Separated1, Separated2, Spiral, Circle, and Iris in all runs. It indicates that F-MFCMDM-UK can detect the best optimal cluster numbers for datasets with different structures. For Connected1, all of the algorithms can detect the best ON. However, the values of AVE_RI, AVE_F, and AVE_MS obtained by F-MFCMDM-UK are worse than those obtained by Vxb, Vpbm, GCUK, and MODEFC. The reason might be that the separation in (17) influences the clustering results. Although F-MFCMDM-UK does not detect the best ON for Flame, the values of AVE_RI, AVE_F, and AVE_MS are the best. For Iris, all the algorithms indicate the best optimal cluster number. However, even among them, the values of AVE_RI, AVE_F, and AVE_MS obtained by F-MFCMDM-UK are the best. The reason is that Path distance is the best choice for this dataset with ON=2. Most of the compared algorithms except RAC-Kmeans can get acceptable clustering results for Separated1, Separated2, Connected1, Iris, and Soybean, but they get worse results for Spiral, Circle, and Flame. The reason is that these algorithms are based on Euclidean distance. RAC-Kmeans shows well for Separated1, Spiral, and Circle; nevertheless, it fails for the remaining datasets. The reason is that RAC-Kmeans is suitable for datasets with separated clusters and unsuitable for datasets with connected clusters. As can be seen from this experiment, F-MFCMDM-UK can detect the optimal cluster number not only for datasets with spherical structures but also for datasets with irregular structures.Table 6
TheON, RI, F and MS obtained by using F-MFCMDM-UK and the compared algorithms.
Datasets  Vxb Vpbm GCUK MoMODEFC RAC-Kmeans F-MFCMDM-UK Separated1 ON(num) 3(10) 3 ( 10 ) 3(10) 3 ( 10 ) 3(10) 3 ( 10 ) (3) AVE_RI 1.00 1.00 1.00 1.00 1.00 1.00 AVE_F 1.00 1.00 1.00 1.00 1.00 1.00 AVE_MS 0 0 0 0 0 0  Separated2 ON(num) 5(10) 2(10) 5 ( 9 ) , 4 ( 1 ) 5 ( 10 ) 4 ( 10 ) 5(10) (5) AVE_RI 1.00 0.68 0.99 1.00 0.920 1.00 AVE_F 1.00 0.56 0.98 1.00 0.833 1.00 AVE_MS 0 1.27 0.06 0 0.633 0  Connected1 ON(num) 3 ( 10 ) 3 ( 10 ) 3 ( 8 ) , 4 ( 2 ) 3 ( 10 ) 3(10) 3(10) (3) AVE_RI 0.95 0.95 0.92 0.93 0.68 0.91 AVE_F 0.93 0.93 0.89 0.91 0.69 0.88 AVE_MS 0.38 0.38 0.44 0.44 0.93 0.50  Spiral ON(num) 14 ( 10 ) 2(10) 3(10) 14 ( 10 ) 3(10) 3(10) (3) AVE_RI 0.68 0.50 0.56 0.68 1.00 1.00 AVE_F 0.23 0.40 0.34 0.20 1.00 1.00 AVE_MS 0.97 1.22 1.16 0.98 0 0  Circle ON(num) 6(10) 5(10) 6 ( 9 ) , 7 ( 1 ) 14(10) 3(10) 3 ( 10 ) (3) AVE_RI 0.73 0.79 0.78 0.72 1.00 1.00 AVE_F 0.47 0.62 0.59 0.38 1.00 1.00 AVE_MS 0.90 0.80 0.81 0.91 0 0  Flame ON 4(10) 2 ( 10 ) 3(10) 4 ( 10 ) 2(10) 3 ( 10 ) (2) AVE_RI 0.70 0.75 0.73 0.69 0.54 0.96 AVE_F 0.62 0.75 0.69 0.62 0.70 0.96 AVE_MS 0.75 0.69 0.71 0.75 0.92 0.26  Iris ON 2 ( 10 ) 2 ( 10 ) 2(10) 2 ( 10 ) 2 ( 10 ) 2 ( 10 ) (2 or 3) AVE_RI 0.96 0.96 0.96 0.96 0.96 1.00 AVE_F 0.96 0.96 0.96 0.96 0.96 1.00 AVE_MS 0.27 0.27 0.27 0.27 0.27 0  Soybean ON 3(10) 2 ( 10 ) 3 ( 10 ) 5(10) 3(9),4(1) 3 ( 10 ) (4) AVE_RI 0.85 0.76 0.85 0.83 0.86 0.85 AVE_F 0.78 0.69 0.78 0.66 0.79 0.78 AVE_MS 0.76 0.96 0.76 0.98 0.73 0.74


## 4.4. Experiment for the Computational Cost

According to our motivation, F-MFCMDM and F-MFCMDM-UK should have smaller computational cost than the previous algorithms MOECDM and MOEACDM. In this subsection, we illustrate the computational cost on several test datasets for the four algorithms and analyze the reasons of the results. Notice that the cluster numbers of F-MFCMDM and MOECDM are predefined in advance and those of F-MFCMDM-UK and MOEACDM are unknown. Hence, F-MFCMDM and F-MFCMDM-UK are compared with MOECDM and MOEACDM, respectively. Each algorithm is conducted in10 runs. For the sake of fairness, the proposed methods and compared methods have the same parameters (max_g, pop_size). All algorithms are performed on a personal computer with a 2.5 ghz intel core central processing unit and 4 GB memory and the code programmed in Matlab R2014b. The average running time obtained by using four algorithms is recorded in Table 7. The running time obtained by F-MFCMDM is less than that obtained by MOECDM in all test datasets. And the running time obtained by F-MFCMDM-UK is also less than that obtained by MOEACDM in all test datasets.Table 7
Average running time of MOECDM, F-MFCMDM, MOEACDM, and F-MFCMDM-UK with the samemax_g and pop_size.
Datasets (max_g,pop_size) MOECDM F-MFCMDM MOEACDM F-MFCMDM-UK Separated1 (200,200) 127 38 181 61 (500,500) 950 214 1471 356  Connected1 (200,200) 95 43 165 59 (500,500) 708 224 1163 338  Spiral (200,200) 128 52 267 86 (500,500) 928 287 1625 500  Iris (200,200) 107 43 172 69 (500,500) 868 227 1641 406  Soybean (200,200) 88 38 98 43 (500,500) 760 199 1154 247Let us discuss the reasons by analyzing the differences between the proposed algorithms and the compared algorithms. There are four main aspects in each algorithm as shown in Table8. For encoding scheme, MOECDM and MOEACDM apply label encoding to construct an individual. F-MFCMDM and F-MFCMDM-UK apply real encoding to construct an individual. The length of an individual in MOECDM, MOEACDM, F-MFCMDM, and F-MFCMDM-UK is n, n, k, and kmax, respectively. For evolutionary operator, MOECDM and MOEACDM apply crossover, mutation, and selection operators to generate the new population. F-MFCMDM and F-MFCMDM-UK apply RM+DE and selection operators to generate the new population. For objective function computation, MOECDM applies compactness between objects as objective function. MOEACDM applies the compactness in MOECDM and separation between clusters as objective function. F-MFCMDM applies compactness between objects and medoids as objective function. F-MFCMDM-UK applies compactness in F-MFCMDM and separation between medoids as objective function.Table 8
The differences of four algorithms in four aspects.
Four aspects MOECDM MOEACDM F-MFCMDM F-MFCMDM-UK  Encoding scheme label encoding real encoding  Individual length n n k k m a x  Evolutionary operator crossover, mutation and selection operators R M + D E and selection operators  Objective function compactness compactness and separation compactness compactness and separationAccording to these differences, the length of the individual greatly influences the computational cost. In MOECDM and MOEACDM, the individual is an integer vector ofn genes, where n is the number of data objects and the ith gene represents the ith data object. In F-MFCMDM, the individual is a real vector of k genes, where k is the number of clusters and the ith gene represents the ith cluster medoid. Generally speaking, for a dataset, k is much smaller than n, so the running time obtained by F-MFCMDM is less than that obtained by MOECDM. In F-MFCMDM-UK, the individual is a real vector of kmax+1 genes. In this paper, kmax+1 is also much smaller than n, so the running time obtained by F-MFCMDM-UK is also less than that obtained by MOECDM.


## 5. Conclusion and Future Work

Distance measure plays an important role in clustering because it can measure the relationship between each pair of points. Most of the popular clustering algorithms depend too much on Euclidean distance. This causes incorrect evaluation of the dataset with different structures. In this paper, a multiobjective fuzzy clustering algorithm called F-MFCMDM is proposed to partition the dateset with different structures and to reduce the computational cost. In contrast to the problem that most clustering algorithms are usually based on the Euclidean distance, F-MFCMDM is based on two distance measures, i.e., Euclidean distance and Path distance. Therefore, it can partition the datasets not only with spherical structures but also with irregular structures. Meanwhile, the two objective functions are optimized simultaneously by using a multiobjective evolutionary algorithm with some modified operators. A real encoding scheme is implemented to set up the individual, which consists ofk cluster medoids. An improved evolutionary operator has been proposed to increase the diversity of population and convergence speed of F-MFCMDM. In the final generation, we can get a set of nondominated solutions and each solution can be regarded as a tradeoff between Euclidean distance and Path distance. Afterwards, each solution is mapped into four clustering results by using four distance measure combinations. A semisupervised method is used to select the best nondominated solution and the best candidate distance combination. Moreover, we also update this algorithm to detect the optimal cluster number automatically by looking for the balance between compactness and separation. The work reported in this paper is very preliminary and there are some possible ways to improve the performance of our approach. Furthermore, more than two distance measures can be added into the model to partition the dataset with more structures. Moreover, the best nondominated solution should be selected by using an unsupervised method.



---

*Source: 3821025-2019-01-17.xml*