Hybrid Fuzzy C-Means Clustering Algorithm, Improving Solution Quality and Reducing Computational Complexity

Abstract

Fuzzy C-Means is a clustering algorithm widely used in many applications. However, its computational complexity is very large, which prevents its use for large problem instances. Therefore, a hybrid improvement is proposed for the algorithm, which considerably reduces the number of iterations and, in many cases, improves the solution quality, expressed as the value of the objective function. This improvement integrates two heuristics, one in the initialization phase and the other in the convergence phase or the convergence criterion. This improvement was called HPFCM. A set of experiments was designed to validate this proposal; to this end, four sets of real data were solved from a prestigious repository. The solutions obtained by HPFCM were compared against those of the Fuzzy C-Means algorithm. In the best case, reductions of an average of 97.65% in the number of required iterations and an improvement in quality solution of 82.42% were observed when solving the SPAM dataset. Finally, we consider that the proposed heuristics may inspire improvements in other specific purpose variants of Fuzzy C-Means.

1. Introduction

The problem addressed in this research consists of improving the efficiency of the Fuzzy C-Means algorithm without compromising the solution quality. This algorithm has been used successfully in the solution of instances from different domains, for example, image segmentation [1,2], medical applications [3,4], marketing [5], and electric vehicles [6]. However, its computational cost is very high, which prevents its application to large datasets because of its execution time. It is foreseeable that this limitation will tend to increase because, in recent years, data generation has been growing exponentially. An alternative for overcoming this limitation is improving the efficiency of the algorithm. In this sense, the main contribution of this research is a new hybrid variant, which has shown a significant increase in its efficiency through the reduction in the number of iterations for obtaining a solution. The objective of increasing the efficiency of the algorithm was achieved partially due to the study of the proposals by Ruspini [7], Dunn [8], and Bezdek [9] from the optimization perspective. In this way, it was observed that the algorithm could be initialized using a seed membership matrix or utilizing a seed centroid set. Traditionally, the membership matrix has been used for initialization; however, some advantages have been found in using centroids instead, where the main one is that it reduces the number of iterations.

Additionally, from the optimization perspective, it is more natural to define the convergence criterion considering the values of the objective value in each iteration; however, a value of the differences of the membership matrix has traditionally been used as a convergence criterion. Experimentally, benefits have been found by using the differences of the objective function values as a convergence criterion; one of them is that this reduces the number of iterations, and the other is that it allows associating a criterion of solution quality.

This article is organized into six sections: Section 2 and Section 3 describe the clustering algorithm and the related work. Section 4 presents the FCM algorithm and the new heuristics called HOFCM and HPFCM. Section 5 shows the results obtained from experimental tests. Finally, conclusions are presented in Section 6.

2. Clustering Algorithms

Clustering algorithms have been classified into hierarchical and partitional [10,11]; the most popular of the former K-means [12,13], while Fuzzy C-Means (FCM) [9] is the most representative of partitional clustering algorithms. One of the differences between FCM and K-means is that atypical data does not significantly affect its results. However, a disadvantage of FCM with respect to K-Means is its computational complexity [14]. Formally, the clustering problem was formulated as follows: let X = {x₁, …, x_n} be the set of data of n objects that should be partitioned, where x_i ∈ ℜ^d for i = 1, … n, and d is the number of attributes (or dimensions) of each object x_i, and c is the number of clusters in the range [2, n].

For the first time, the fuzzy clustering problem was formulated as an optimization problem that minimizes an objective function [7]. Later, this formulation was improved by Dunn [8] and Bezdek [9]. Next, Bezdek’s formulation is presented [9]. Equation (1) shows the objective function J_m. The decision variables are matrix U of membership degrees and the set of centroids V.

$$P:\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{z}\mathrm{e} J_m\left( U, V \right)=\sum _{i=1}^n\sum _{j=1}^c{u}_{ij}^m{\left|\right|x_i - v_j\left|\right|}^2$$

(1)

Subject to

$$u_{\mathrm{ij}}\in \left[0,1\right] 1 \le i \le n, 1 \le j \le c$$

(2)

$$\sum _{j=1}^c{u}_{ij}=1 1 \le i \le n$$

(3)

$$u_{ij}=1 \mathrm{if} x_i=v_j$$

(4)

$$0 <\sum _{i=1}^n{u}_{ij}< n 1 < j \le c$$

(5)

Next, the notation necessary for the article is defined:

i: index of object;

j: index of cluster;

m: weighting exponent or fuzzy factor, m > 1;

c: number of clusters in X;

n: number of objects in X;

ε: threshold value;

t: iteration count;

X = {x₁, …, x_n}: set of n objects to be partitioned according to a similarity criterion;

U = {u_ij}: membership degree of object i to cluster j;

V = {v₁,…,v_c}: set of centroids, where v_j is the centroid of cluster j;

T: limit number of iterations;

ΔU: convergence criterion (the difference of the membership degrees values in two consecutive iterations)

ΔV: convergence criterion (the difference of the centroids’ values in two consecutive iterations);

Δ_oldJ_m: convergence criterion (the difference of the objective function values in two consecutive iterations);

Δ_newJ_m: new convergence criterion (the difference of the objective function values, in two consecutive iterations, expressed as a percentage of its value in the next to the last one).

${\left|\right|x_i -v_j\left|\right|}^2:$ distance from object x_i to centroid v_j using the Euclidean distance.

The solution method mentioned by Bezdek in [9] consists of performing the calculation of Equations (6) and (7) alternately until satisfying a convergence criterion.

$$v_j={\displaystyle \frac{\sum _{i=1}^n{\left(u_{ij}\right)}^m{x}_i}{\sum _{i=1}^n{\left(u_{ij}\right)}^m}} 1 \le j \le c$$

(6)

$$u_{ij}={\displaystyle \frac{1}{\sum _{k=1}^c{\left(\frac{\left|\right|x_{i }- v_j\left|\right|}{\left|\right|x_i -{ v}_k\left|\right|}\right)}^{\frac{2}{\left(m-1\right)}}}} 1 \le i \le n, 1 \le j \le c$$

(7)

Equations (8) and (9) are two convergence criteria [9] applied when a stop condition is met. Traditionally, the threshold values are indicated with the symbol ε.

$${\mathsf{\Delta }U}^{\left(t\right)}=\max \left(abs\left({u_{ij}}^{(t-1)}-{u_{ij}}^{\left(t\right)}\right)\right)$$

(8)

$${\mathsf{\Delta }V}^{\left(t\right)}=\max \left(abs\left({v_{ij}}^{(t-1)}-{v_{ij}}^{\left(t\right)}\right)\right)$$

(9)

Algorithm FCM has four phases: initialization, centroid calculation, classification, and convergence [15]. For the initialization phase, the following parameters should be defined: the number of clusters c, the value of the weighting exponent m, the matrix of membership degrees U, the value of the convergence threshold ε, and the limit number of iterations.

Since the main contributions of this article are improvements in the initialization and convergence phases, the following subsections will describe the initialization and convergence approaches by other authors.

3. Related Work

This section presents the most relevant works related to this research. First, studies focusing on the algorithm’s initialization method are examined. Next, investigations centered on the convergence method are reviewed.

3.1. Initialization Methods

The general method for solving the fuzzy clustering problem consists of initializing the algorithm using the membership matrix or a set of centroids. Specifically, Bezdek proposed a method for initializing the membership matrix [16]. Many of the implementations of FCM and its variants continued to use the aforesaid method. In contrast, this article proposes centroids in the initialization phase because several advantages were experimentally observed in the algorithm behavior. In order to give an idea of the different initialization methods proposed by other authors, Table 1 is presented; its structure is the following: column one shows the publication reference, column two indicates if the initialization was performed by calculating the membership matrix using a heuristic method, column three specifies if a set of randomly generated centroids was used in the initialization, and column four indicates if the initialization was performed using centroids generated using a heuristic method.

Table 1 shows that, in the pioneering research works, FCM initialization was performed using the membership degrees matrix [7,9,16]. Only a few variants have used a sample of randomly selected objects as the set of initial centroids [17,18]. In [19], the proposed approach consisted of dividing the objects’ space into a grid and finding high-density regions for selecting the objects that would be the initial centroids. In [20,21], the FCM++ algorithm was proposed, which used the K++ heuristics [21] to select the objects that would perform the initial centroid role. Later, an improvement of K++ was proposed in [22]. In [23], the final centroids generated by the K-Means algorithm were used, which, through a transformation process called One-Hot encoding, generated the initial membership matrix for FCM. Finally, in [24], the HOFCM algorithm was proposed, which uses as initial centroids those to which the OK-Means algorithm converges [25]. It is worth mentioning that the HOFCM algorithm, in its experimental phase, was compared to three algorithms [16,20,23] and outperformed them in all the test cases, which involved large datasets. HOFCM reduced the execution time by up to 93% and improved the solution quality by up to 68.12% in the best case.

Table 1. Different methods for initializing the Fuzzy C-Means algorithm.

Reference	U Heuristic	V Random	V Heuristic
[7]	Ruspini
[8]	Dunn
[9,15,16]	Bezdek
[17,18]		Method 1
[19]			Method 2
[20,21]			K++
[20,21]			Variant K++
[23]			K-Means
[24]	OKMeans++

Table 1. Different methods for initializing the Fuzzy C-Means algorithm.

Reference	U Heuristic	V Random	V Heuristic
[7]	Ruspini
[8]	Dunn
[9,15,16]	Bezdek
[17,18]		Method 1
[19]			Method 2
[20,21]			K++
[20,21]			Variant K++
[23]			K-Means
[24]	OKMeans++

3.2. Convergence Methods

In the convergence phase of FCM, several stop criteria have been used. Figure 1 shows four convergence criteria published in [18]: (1) the largest difference of the membership degree values in two consecutive iterations, (2) the largest distance between centroid positions in two consecutive iterations, (3) the difference of the objective function in two successive iterations, and (4) the limit of the number of iterations. Some implementations use a combination of a limit in the number of iterations and the largest difference of the membership degree values in two consecutive iterations [16,26]. We remark that the most used criterion is the first one.

Table 2. Different methods for the convergence phase in the Fuzzy C-Means algorithm.

Reference	ΔU	ΔV	Jm	T
[7]	✓
[8]		✓
[9]	✓	✓
[16,26]	✓			✓
[17,27,28,29,30,31]			✓
[18]			✓

presents different convergence methods.

The structure of Table 2 is the following: column one shows the publication reference, column two indicates if the difference of the membership degrees values in two consecutive iterations (ΔU) was used, column three specifies if the difference of centroid values in two consecutive iterations (ΔV) was utilized, column four indicates if the difference of the objective function (J_m) values in two consecutive iterations was used, and the last column specifies if a limit number of iterations (T) was used as stop criterion.

Table 2 shows that, at the beginning of the FCM algorithm, ΔU and ΔV were used as convergence criteria [7,8,9]. A combination of ΔU and T was used in [16,26]. Additionally, in the specialized literature, different improvements of the algorithm have been published, which use the objective function as the stop criterion [17,27,28,29,30,31]. It is worth mentioning that none of the improvements mentioned in Table 2, in the experimental part, report an improvement in the solution quality, expressed as the objective function value.

Hybrid methods [24] can generate better results because they can overcome the combined algorithms’ disadvantages. Therefore, a hybrid improvement for the FCM algorithm is proposed, which significantly reduces the number of iterations and, in many cases, improves the solution quality in terms of the objective function value. Our proposal consists of combining the approaches of two different algorithms. From the first one, it adopts its initialization strategy [24]. From the second one, it adopts its convergence strategy [18].

4. Materials and Methods

The new algorithm that we propose in this article is inspired by three algorithms: FCM [16], HOFCM [24], and P-FCM [18]. These algorithms will be described in the following sections, emphasizing the section related to this research.

4.1. FCM Algorithm

The first formal approach for the fuzzy clustering problem as an optimization problem was proposed by Ruspini in [7]. In 1973, Dunn [8] extended the meaning of hard clustering to preliminary concepts of fuzzy means. Then, Bezdek [9] generalized Dunn’s approach for obtaining an infinite family of Fuzzy C-Means algorithms.

The pseudocode of the standard FCM algorithm [16] is shown in the

Table 3. FCM algorithm.

Input:X, c, m, ε, T
Output:V, U
1	Initialization:
2	t: = 0;
3	Calculate membership matrix U(t): using Bezdek’s method;
4	Calculate centroids:
5	Calculate the centroids using Equation (6);
6	Calculate membership matrix:
7	Update and calculate the membership matrix using Equation (7);
8	Convergence:
9	If ΔU(t) < ε or t = T:
10	Stop the algorithm;
11	Otherwise:
12	U(t): = U(t + 1) and t: = t + 1;
13	Go to Calculate centroids;
14	End of algorithm

.

The FCM algorithm has the following input parameters: the dataset X, the number of clusters c, the weighting exponent m, the threshold value ε, and the limit number of iterations T. The output parameters or decision variables are the matrix that contains the membership degrees U and the set of centroids V. In the initialization phase, the iteration counter t is set to 0, the threshold value ε is set to 0.01, and the initial matrix of membership degrees is generated using Bezdek’s random method [16]. The cycle starts at line 4, where the centroids are calculated, and at line 6, the membership matrix calculation is performed using Equations (6) and (7), respectively. Notice that line 9 defines a convergence criterion constituted by two stop conditions, such that the algorithm stops when anyone is satisfied.

4.2. HOFCM Algorithm

The HOFCM algorithm [24] introduces an improvement in the initialization phase of the standard FCM algorithm. The pseudocode of the HOFCM algorithm is shown in the

Table 4. HOFCM algorithm.

Input: X, c, m, ε, T
Output: V, U
1	Initialization:
2	ɛok: = threshold value for determining O-K-Means convergence;
3	Assign the value for c;
4	Function K++ (X, c):
5	Return V′;
6	Function O-K-Means (X, V′, ɛok, c):
7	Return V″;
8	Function S (V″):
9	Return U;
10	Determine the value of the threshold ε to determine the convergence of the algorithm;
11	Assign the value for m;
12	t: = 0;
13	Calculate centroids:
14	Calculate the centroids using Equation (6);
15	Classification:
16	Update and calculate the membership matrix using Equation (7);
17	Convergence:
18	If ΔU(t) < ε or t = T:
19	Stop the algorithm;
20	Otherwise:
21	U(t): = U(t + 1) and t: = t + 1;
22	Go to Calculate centroids

.

The HOFCM algorithm consists of four phases. The first phase is the initialization phase, during which three functions are created: (1) The K++ function, which takes the dataset X and the number of clusters as input parameters; this function returns a set of centroids denoted by the variable V′. (2) The O-K-Means function, which receives dataset X, the set of centroids V′ generated by K++, and the threshold value ɛok as input parameters to determine the algorithm’s convergence and the number of clusters; at the end of the convergence phase, it returns optimized centroids defined by the variable V″. (3) The transformation function s, which transforms the final centroids from the O-K-Means algorithm—selected based on the lowest value of the objective function—into the initial optimized values of the membership matrix; these values serve as input parameters for the FCM algorithm. The second, third, and fourth phases of the HOFCM algorithm, called calculate centroids, classification, and convergence, respectively, are typical of the standard FCM algorithm.

4.3. P-FCM Algorithm

The P-FCM algorithm [18] is a heuristic that modifies the convergence phase of the FCM algorithm. The convergence strategy evaluates the difference of the objective function in two consecutive iterations, expressed as a percentage; when the value is less than a defined threshold, the algorithm converges. The pseudocode of the P-FCM algorithm is shown in

Table 5. P-FCM algorithm.

Input:X, V, c, m, ε
Output: V, U
1	Initialization:
2	t: = 0;
3	U(t): = {u11, …, uij}; is randomly generated;
4	Calculate centroids:
5	Calculate the centroids using Equation (6);
6	Calculate membership matrix:
7	Update and calculate the membership matrix using Equation (7);
8	Convergence:
9	If ΔnewJm(t) ≤ ε:
10	Stop the algorithm;
11	Otherwise:
12	U(t): = U(t + 1) and t: = t + 1;
13	Go to Classification
14	End of algorithm

.

Line 8 shows the convergence phase, which includes the stop indicator of the P-FCM algorithm. In this phase, the value of indicator Δ_newJ_m is calculated, which expresses as a percentage the difference of the objective function in two consecutive iterations (see Equation (10)). The algorithm stops when this value is less than or equal to the convergence threshold ε.

$${\mathsf{\Delta }}_{new}{J_m}^{\left(t\right)}=100 \ast {\displaystyle \frac{({J_m}^{\left(t-1\right)}-{J_m}^{\left(t\right)})}{{J_m}^{(t-1)}}}$$

(10)

4.4. HPFCM Algorithm

It is known that the efficiency of the FCM algorithm depends, among other factors, on the initialization and convergence strategies. In this research, a new algorithm, HPFCM, is proposed. This algorithm combines two different heuristics, which considerably reduces the number of iterations and improves the solution quality in many cases. From the first heuristics, it adopts its initialization strategy [24]. From the second, it adopts its convergence strategy [18].

The pseudocode that incorporates the proposed heuristics, called HPFCM, is shown in

Table 6. HPFCM algorithm.

Input: X, c, m, ε, T
Output: V, U
1	Initialization:
2	ɛok: = threshold value for determining O-K-Means convergence;
3	Assign the value for c;
4	Function K++ (X, c):
5	Return V′;
6	Function O-K-Means (X, V′, ɛok, c):
7	Return V″;
8	Function S (V″):
9	Return U;
10	Determine the value of the threshold ε to determine the convergence of the algorithm;
11	Assign the value for m;
12	t: = 0;
13	Calculate centroids:
14	Calculate the centroids using Equation (6);
15	Classification:
16	Update and calculate the membership matrix using Equation (7);
17	Convergence:
18	If ΔnewJm(t) ≤ ε:
19	Stop the algorithm;
20	Otherwise:
21	U(t) := U(t + 1) and t := t + 1;
22	Go to Classification
23	End of algorithm

.

Algorithm HPFCM, like FCM, consists of four phases. In the initialization phase, a strategy borrowed from the HOFCM heuristics [23], three functions are executed: (1) Function K++ has as input parameters the dataset X and the number of clusters; additionally, this function has as output parameter the set of centroids, denoted by variable V′. (2) Function O-K-Means has as input parameters the dataset X, the set of centroids V′, the value of the convergence threshold ɛok, and the number of clusters; furthermore, this function has as output parameter the set of centroids, symbolized by variable V″. (3) Function S has as input parameter the set of centroids, signified by variable V″; in addition, this function has as output parameter a membership matrix, calculated from V’’. The second and third phases (called centroid calculation and classification, respectively) are phases from the standard FCM. The convergence phase is inspired by the P-FCM heuristics [18].

5. Results

Four experiments were carried out to evaluate our proposal, where four real datasets were solved. Each dataset was solved using the FCM, HOFCM, and HPFCM algorithms. The standard FCM algorithm was implemented so that other results could be compared against those from this algorithm; the HOFCM algorithm was implemented because it includes an improvement change in the initialization phase of FCM. Several executions with different configuration parameters, such as different threshold values, were performed. Altogether, 100 executions of the algorithms were performed.

5.1. Experiments Setup

The three were implemented in C language, and the GCC 7.4.0 compiler was used. The experiments were executed on an Acer Nitro 5 laptop with Intel Core i7-11800H processor at 2.30 GHz, 16 GB of RAM memory, 512 GB SSD and 1 TB HDD, and Windows 11 operating system.

5.1.1. Description of Datasets

The datasets were obtained from the UCI Machine Learning Repository [32].

Table 7. Description of real datasets.

X	n	d	n × d
WDBC	569	30	17,070
ABALONE	4177	7	29,239
SPAM	4601	57	262,257
URBAN	360,177	2	720,354

shows the characteristics of the real datasets. The structure of Table 7 is as follows: column one shows the dataset name, column two presents the number of objects, column three shows the number of attributes, and column four presents the product of columns two and three.

The first two datasets were selected because they have been used as test datasets in publications on clustering algorithms. The subsequent two datasets were chosen because other authors have used them for experimenting with large datasets and on parallel and distributed hardware.

5.1.2. Parameter Configurations for Algorithm Execution

Test cases were designed for evaluating different values of the objective function and the number of iterations carried out by the algorithms. The parameters for executing the algorithms were the following:

FCM: c = 50, m = 2, T = 500, and ε = 0.01;

HOFCM: c = 50, m = 2, εok = 0.72, and ε = 0.01;

HPFCM 0.9: c = 50, m = 2, ɛok = 0.72, and ε = 0.9;

HPFCM 0.22: c = 50, m = 2, εok = 0.72, and ε = 0.22;

HPFCM 0.06: c = 50, m = 2, εok = 0.72, and ε = 0.06.

For FCM the values of the initial membership matrix were obtained using Bezdek’s method. For HPFCM, the values of the threshold value ε were three for each experiment: ε = 0.9, ε = 0.22 and ε = 0.06. These values were proposed in [18] from a series of experiments with FCM. The value for ε = 0.9 is based on the Pareto Principle and constitutes a balance between the convenient values of the objective function and the number of iterations. The values ε = 0.22 and ε = 0.06 are associated with objective function values, which are 98% and 99% similar (i.e., equivalent to differences of 2% and 1%, respectively) to the objective function value when the algorithm has a convergence threshold of 0.00001.

5.2. Experimental Results

Each experiment consisted of executing FCM, HOFCM, and HPFCM five times because this is a representative sample in previous publications. In experiments I, II, III, and IV, the WDBC, ABALONE, SPAM, and URBAN datasets were solved respectively.

Table 8. Results from experiment I, dataset WDBC.

E	FCM		HOFCM		HPFCM 0.9		HPFCM 0.22		HPFCM 0.06
	t	OF	t	OF	t	OF	t	OF	t	OF
1	107	749,256.98	102	462,581.65	4	481,344.46	10	470,369.65	17	466,814.16
2	92	764,026.31	54	465,843.52	4	486,051.21	8	480,181.55	14	476,482.08
3	81	831,151.69	144	454,661.28	4	498,014.16	11	485,386.93	32	467,050.78
4	107	771,827.15	25	454,679.38	4	469,648.82	11	455,658.05	13	455,164.07
5	91	745,695.01	54	458,615.38	4	475,056.66	9	462,925.54	12	461,856.56
Average	95.60	772,391.43	75.80	459,276.24	4.00	482,023.06	9.80	470,904.34	17.60	465,473.53

,

Table 9. Results from experiment II, dataset ABALONE.

E	FCM		HOFCM		HPFCM 0.9		HPFCM 0.22		HPFCM 0.06
	t	OF	t	OF	t	OF	t	OF	t	OF
1	198	4.89	158	4.96	4	5.29	11	5.14	27	5.03
2	289	4.84	177	4.82	4	5.06	7	5.03	27	4.90
3	157	4.84	128	4.92	4	5.06	6	5.04	15	4.99
4	187	4.90	115	4.92	4	5.08	9	5.00	16	4.97
5	317	4.84	164	4.91	5	5.19	12	5.08	30	4.99
Average	229.60	4.86	148.40	4.91	4.20	5.14	9.00	5.06	23.00	4.98

,

Table 10. Results from experiment III, dataset SPAM.

E	FCM		HOFCM		HPFCM 0.9		HPFCM 0.22		HPFCM 0.06
	t	OF	t	OF	t	OF	t	OF	t	OF
1	327	15,512,347.05	66	2,594,609.86	5	2,743,216.21	7	2,729,787.58	17	2,672,582.12
2	246	15,346,906.74	47	2,567,788.11	4	2,641,992.34	9	2,600,034.52	20	2,576,467.98
3	433	14,389,142.01	19	2,738,174.19	4	2,800,149.19	10	2,746,694.76	13	2,741,455.53
4	326	15,663,485.28	35	2,563,461.92	7	2,658,812.92	10	2,619,088.31	12	2,615,393.81
5	459	15,254,377.61	31	2,623,242.90	4	2,700,152.82	6	2,688,707.75	19	2,638,046.71
Average	358.20	15,233,251.74	39.60	2,617,455.40	4.80	2,708,864.70	8.40	2,676,862.58	16.20	2,648,789.23

and

Table 11. Results from experiment IV, dataset URBAN.

E	FCM		HOFCM		HPFCM 0.9		HPFCM 0.22		HPFCM 0.06
	t	OF	t	OF	t	OF	t	OF	t	OF
1	78	6386.83	32	4629.85	4	4867.73	6	4845.09	22	4636.03
2	95	5819.01	33	4681.14	4	5269.01	6	5238.33	31	4681.70
3	137	6304.24	33	4858.13	3	5038.73	6	4999.36	19	4868.28
4	102	5468.40	30	4562.42	4	4734.64	6	4715.66	17	4565.79
5	105	5974.76	36	4694.16	6	4816.80	8	4795.37	17	4701.21
Average	103.40	5990.65	32.80	4685.14	4.20	4945.38	6.40	4918.76	21.20	4690.60

show the results from the five executions of each algorithm and configuration for each dataset. The structure of the tables is explained next. Column one indicates the execution number. Column two shows the results from FCM, which are subdivided into the total of iterations and the final value of the objective function. Column three presents the results from HOFCM, which are subdivided like those of column two. Columns four, five, and six show the results from HPFCM for ε = 09, ε = 0.22, and ε = 0.06, respectively, and additionally, these results are subdivided similarly as those of column two.

Four graphs were generated, one for each experiment, where the x-axis and y-axis represent the number of iterations and the objective function value. Each point on the graph represents the solution obtained by one of the three algorithms. The values on x and y were normalized in the range [0, 1] using the max-min method to observe the solution of each algorithm and compare them.

5.3. Analisis of Results

The average values of the HPFCM and FCM algorithms were compared based on the results obtained. For quantifying the differences between the results of the algorithms, two indices, α and β, were defined, where $\alpha$ expresses the reduction in the number of iterations of HPFCM with respect to FCM as a percentage of the FCM value (see details in Equation (11)). Index β expresses the reduction of the objective function of HPFCM with respect to FCM as a percentage (see Equation (12)). Notably, the FCM algorithm converged in all experimental cases when the stop criteria ΔU(t) < ε was met.

$$\alpha =100-\left(100 \ast {\displaystyle \frac{average\_t\_HPFCM}{average\_t\_FCM}}\right)$$

(11)

$$\beta =100-\left(100 \ast {\displaystyle \frac{average\_OF\_HPFCM}{average\_OF\_FCM}}\right)$$

(12)

5.3.1. Analysis of the Results of Experiment I

Based on the experimental results shown in Table 8 and Figure 2, the following observations were obtained:

(a)

FCM obtained an average of 772,391.43 for the objective function, whereas HPFCM 0.06 obtained 465,473.53 (see Table 8).

(b)

As an be observed in Figure 2, the FCM results (depicted by red circles) have large values of the objective function and number of iterations; in contrast, the HOFCM and HPFCM results (depicted by yellow, green, blue, and gray circles) are near the graph origin. Because the distance among the groups of results is large, it was proved that HPFCM had better performance than FCM. In the best case, it was observed that HPFCM 0.9 obtained a value of α = 95.82 and HPFCM 0.06 a value of β = 39.73.

5.3.2. Analysis of the Results of Experiment II

Based on the experimental results shown in Table 9 and Figure 3, the following observations were determined:

Table 9 shows that FCM obtained the best average value of the objective function. However, the number of iterations was higher with respect to HOFCM. In the best case, HPFCM 0.9 obtained a value α = 98.17 and a quality reduction β = 5.76.

5.3.3. Analysis of the Results of Experiment III

Based on the experimental results shown in Table 10 and Figure 4, the following observations were obtained:

Figure 4 shows the results for FCM (depicted by red circles), whereas the values for HOFCM and HPFCM (depicted by yellow, green, blue, and gray circles) are near the graph origin. In the best case, HPFCM 0.9 obtained a value α = 95.82, and HPFCM 0.06 attained a value of β = 39.73. According to these observations, HPFCM performed better than FCM.

5.3.4. Analysis of the Results of Experiment IV

Based on the experimental results that are shown in Table 11 and Figure 5, the following observations were determined:

FCM obtained an average value of 5990.65 for the objective function and 103.4 iterations on average, whereas HPFCM obtained small values for the objective function and number of iterations. Figure 5 shows that the FCM results (depicted by red circles) for the objective function and number of iterations were the largest, whereas the results for HOFCM and HPFCM (depicted by yellow, green, blue, and gray circles) are close to the graph origin. In the best case, HPFCM 0.9 attained a value of α = 95.94, and HPFCM 0.06 obtained a value of β = 21.7.

6. Conclusions

This article shows that it is possible to increase the efficiency and solution quality of the FCM algorithm using a hybrid approach, which integrates two heuristics: one improves the initialization phase of the algorithm, and the other improves the convergence phase.

To evaluate the HPFCM approach, we performed experiments where FCM, HOFCM, and HPFCM algorithms solved the WDBC, ABALONE, SPAM, and URBAN real datasets. Based on the obtained results, it was observed that the HPFCM algorithm generally improved the quality of the solution and needed fewer iterations than the FCM algorithm. The results from experiments II and III are remarkable: in experiment III, the best average results were obtained, and in experiment II, the worst results were attained. In experiment III, when solving the SPAM dataset with HPFCM and a value ε = 0.22 as convergence threshold, the following results were obtained: an average improvement of 82.43% in solution quality and an average reduction of 97.65% in the number of iterations with respect to FCM.

In experiment II, when solving the ABALONE dataset with HPFCM and a value ε = 0.9 as convergence threshold, the following results were obtained: the algorithm HPFCM obtained a 5.67% loss of quality, which is considered little significant, but remarkably, it achieved a 98.17% reduction in the number of iterations.

It is worth mentioning that the HPFCM algorithm contributes original elements by integrating two heuristics, which have improved the FCM algorithm in the initialization and convergence phases, where the last one has been little studied. Another contribution of our approach is the threshold values used as a convergence criterion. By leveraging such threshold values, users may make informed decisions and prioritize either the execution time or the solution quality. Finally, according to the literature surveyed, we did not find another FCM variant that improves the solution quality, expressed as the value of the objective function as the algorithm converges.

In summary, our proposal contributes to the initialization and convergence phases of the FCM algorithm and has no conflict with improvements in other phases of the algorithm, making possible its integration into other variants of FCM.