K-Means Clustering Algorithm Based on Improved Differential Evolution

Clustering algorithms, as a type of unsupervised learning in data mining [1], are widely employed to uncover intrinsic associations and underlying patterns in data [2] without prior knowledge. By grouping data based on characteristics such as “similarity” or “proximity,” clustering enables the categorisation of data into distinct classes [3]. However, different algorithms or varying parameter settings within the same algorithm often lead to divergent data categorisation or reveal different clustering structures [4]. Current clustering algorithms can be broadly categorised into partition-based methods [5], such as K-means and k-medoids, density-based methods [6], such as Density-Based Spatial Clustering of Applications with Noise (DBSCAN) and Ordering Points To Identify the Clustering Structure (OPTICS), and grid-based methods [7], such as WaveCluster and Statistical Information Grid (STING). Among these, the K-means clustering algorithm, proposed by Dubey and Choubey [8], has been extensively applied in data mining and knowledge discovery due to its simple calculation and low linear time complexity [9]. Despite these advantages, the traditional K-means clustering algorithm relies on the random selection of initial cluster centres [7]. This randomness [10] can cause the initial cluster centres to deviate significantly from the dataset or become overly concentrated. As a result, clustering outcomes may be compromised, which reduces the accuracy of clustering and increases computation time and resource consumption, thereby affecting the effectiveness of clustering [11].

To address these limitations of the traditional K-means clustering algorithm [12] and improve both the effectiveness and efficiency of clustering, significant efforts have been made to refine the K-means clustering algorithm. For instance, Bai et al. [13] improved the artificial fish swarm algorithm by dynamically updating the rotation angle of quantum rotation gates and replacing the mutation strategy from NOT gates to Hadamard gates. This improved artificial fish swarm algorithm was used to select initial cluster centres for K-means, enhancing both convergence speed and clustering performance. Sun et al. [14] improved the velocity inertia weight and position update formula of the particle swarm optimisation algorithm and incorporated attribute weights into the traditional Euclidean distance metric. The improved particle swarm algorithm was used to optimise the K-means, effectively enhancing clustering performance and reducing the number of iterations required. Wang et al. [15] addressed the slow convergence and lack of diversity in the cuckoo optimisation algorithm by integrating the principles of particle swarm optimisation and applying the improved algorithm to K-means, achieving higher accuracy and greater algorithmic stability. Similarly, Wang et al. [16] employed multivariate statistical distance based on sample variance and introduced an improved artificial bee colony algorithm to determine initial cluster centres, effectively mitigating the susceptibility of K-means to local optima. Chen et al. [17] introduced a weighted Euclidean distance into the firefly optimisation algorithm, optimising the selection of initial cluster centres and reducing the impact of uncertain factors such as outliers, thereby improving both clustering performance and convergence speed. Hu et al. [18] incorporated the lion optimisation algorithm into K-means, using the optimal solution of the lion king at the end of the algorithm as the cluster centres. This approach effectively reduced the dependency of K-means on the initial cluster centre selection. In summary, leveraging intelligent optimisation algorithms to refine the selection of initial cluster centres has been shown to significantly enhance the clustering performance of the K-means clustering algorithm.

Differential evolution has been recognised as an efficient global optimisation algorithm, demonstrating robust performance in handling data while requiring relatively few parameter settings. Its simplicity in implementation and adjustment [19] further enhances its appeal. However, similar to many evolutionary algorithms, differential evolution also faces challenges such as reliance on a single evolutionary strategy, susceptibility to local optima, and slow convergence. To address these limitations in differential evolution and the K-means clustering algorithm, an improved K-means clustering algorithm based on enhanced differential evolution was proposed and its improvement effect on K-means was discussed. In contrast to traditional differential evolution, the proposed method introduces adaptive operators capable of dynamically adjusting based on the current evolutionary stage. This mechanism enables a broad exploration of the solution space during early stages while focusing on fine-tuning high-quality solutions in later stages, thereby significantly improving convergence speed. Additionally, a multi-mutation strategy based on a weighted coefficient was developed. This coefficient adjusts with the number of evolutionary iterations, allowing different mutation strategies to be employed during different evolutionary phases. This design achieves a balance between global and local search capabilities, reducing the risk of local optima caused by a single mutation strategy and further accelerating convergence. Furthermore, a Gaussian perturbation crossover operation guided by the best individual in the current population was designed. This approach not only directs individuals towards superior evolutionary directions but also maintains diversity across dimensions of the population, further reducing the likelihood of stagnation in local optima. The optimal solution generated at the termination of the improved differential evolution was employed to replace the randomly selected initial cluster centres of traditional K-means. Comparative experiments conducted using public datasets from the UCI repository and the synthetic dataset indicate that the proposed algorithm effectively reduces the dependency of K-means on the selection of initial cluster centres and captures the intrinsic structure of data more accurately, thereby enhancing clustering quality and efficiency.

In the differential evolution algorithm, mutation and crossover operations constitute the central mechanisms of the algorithm. The mutation factor ($F$) and crossover factor ($C_R$) play critical roles in the algorithm. In traditional differential evolution, these factors are set as fixed values, which limits the algorithm’s optimisation capability and convergence efficiency, thereby impeding its performance enhancement [20]. During the early stages of evolution, population diversity should be maintained to enhance global optimisation capability. In contrast, during the middle and later stages, the focus should shift towards strengthening local search capability to accelerate convergence.

To enalbe $F$ and $C_R$ to meet the varying optimisation requirements across different evolutionary stages, adaptive operators were employed in this study to dynamically balance global and local search capabilities as the algorithm evolves. The adaptive strategy for the operators is defined as follows:

where, $F_{m i n}$ and $F_{m ax}$ represent the lower and upper bounds of $F$, set to 0.3 and 0.9, respectively; $C_{Rmin}$ and $C_{Rmax}$ denote the lower and upper bounds of $C_R$, also set to 0.3 and 0.9, respectively; $G$ represents the number of iterations for the current algorithm; and $G_{m ax}$ indicates the maximum number of iterations of the algorithm.

The above equations enable the adaptive adjustment of $F$ and $C_R$, ensuring a linear decrease in both factors as the algorithm progresses. This allows the algorithm to possess a larger search space and stronger global optimisation capability during the early stages of evolution, while exhibiting enhanced local search capability in the middle and later stages. Consequently, convergence speed of the algorithm can be improved.

To enhance the optimisation capability of the differential evolution algorithm, maintaining population diversity during the early stages of evolution is critical for improving global optimisation capability. The DE/rand/1 mutation strategy is characterised by its wide optimisation range, making it well-suited for global search in the early stages of the algorithm. In contrast, during the middle and later stages of evolution, global search has already been performed, and the focus should shift to local optimisation around the best individual and its vicinity. The DE/current-to-best/2 mutation strategy is more effective during these stages due to its strong local search capability and faster optimisation speed.

Based on the characteristics of different mutation strategies, the DE/rand/1 and DE/current-to-best/2 mutation strategies were combined into an improved differential evolution algorithm based on the multi-mutation strategy. An adaptive weight coefficient $W$ was introduced to dynamically adjust the proportion of each strategy throughout the evolutionary process. This enables different mutation strategies to dominate at different stages of the algorithm, maximising their respective advantages.

where, $W$ is the weight factor, ranging from 0 to $1 ; G$ is the current iteration number; $G_{max}$ is the maximum number of iterations; $V_{i, G+1}$ denotes the mutated individual in generation $G+1 ; X_{b e s t, G}$ represents the individual with the best fitness value in the current population; and $r_1, r_2, r_3, r_4, r_5, r_6, r_7$ represents 7 random numbers that are not equal to $i$ or mutually different from each other.

The weight coefficient $W$ changed with the number of iterations, dynamically balancing the proportion of two mutation strategies in different evolution stages of the algorithm. During the early stages of evolution, the value of $W$ remained small, allowing the DE/rand/1 mutation strategy to dominate. This facilitated global optimisation across a larger search space. As the algorithm progressed to the middle and later stages, the value of $W$ increased, enabling the DE/current-to-best/2 strategy to take precedence. This transition improved the local search capability of the algorithm, guided individuals towards better evolutionary directions, and accelerated the convergence of the algorithm.

In the differential evolution algorithm, mutation and crossover operations were used to explore and exploit new solution spaces. Although the mutation and crossover factors can be adaptively adjusted, these operations typically occur along the individual “dimensions.” If the values of the population in a certain dimension converge towards a fixed value or become nearly identical, the differential evolution algorithm loses its optimisation capability in that dimension. To maintain diversity across dimensions and avoid the local optima of the algorithm, a Gaussian perturbation mechanism based on the best individual in the current population was introduced into the crossover operation. This approach leverages the best individual to guide the evolution of others, while Gaussian perturbation probabilistically generates new values in each dimension, preserving diversity of the population across dimensions. The specific steps are as follows:

Step 1: For a given dimension $n$ in a clustering problem, a random number $rand(0,1)$ was taken. If ${rand}(0,1)$, then $U_{i, G}^n=V_{i, G}^n$ and the operation for that dimension can be terminated. Otherwise, proceed to Step 2.

Step 2: Another random number ${rand}(0,1)$ was taken. If ${rand}(0,1) \leq 0.7$, then $U_{i, G}^n=X_{{best,G }}^n$. Otherwise, a new random value in the dimension can be generated using Gaussian perturbation, as defined by:

where, $C$ is the control parameter for Gaussian perturbation, set to 0.1; and $N(0,1)$ represents a random value sampled from a normal distribution with a mean of 0 and a standard deviation of 1.

The new crossover operation encouraged new individuals to move towards the individual with the best fitness value in the current population. At the same time, Gaussian perturbation was used to prevent the population from tending towards a fixed value in a certain dimension, thereby losing optimisation capability in the dimension. This prevents the algorithm from stagnating in local optima. Combined with the previously described adaptive operators $C_R$, this method allows global optimisation capability to be retained during the early stages of evolution. In the later stages, it enhances local search capability and accelerates convergence of the algorithm.

The improved differential evolution algorithm was integrated with the K-means clustering algorithm. The fitness function defined in Eq. (6) was employed to evaluate the fitness value of each individual. The improved differential evolution algorithm was used for iterative optimisation, and the optimal individual obtained at the end of the algorithm was used to replace the randomly selected initial cluster centres of the traditional K-means clustering algorithm.

In clustering algorithms, the final objective is to minimise the intra-cluster compactness while maximising the inter-cluster compactness. Therefore, the SSE [21] was adopted as the fitness function for the improved differential evolution algorithm:

where, $x_{i, k}$ represents a data point; and $c_k$ denotes the centre of the cluster to which the data point belongs. A smaller SSE indicates better clustering performance, while a larger SSE suggests poorer clustering performance.

a) The population size $NP$ was set to ten times the solution dimension $D$. The mutation factor $(F)$ and crossover factor $\left(C_R\right)$ were adaptively taken according to Eqs. (1) and (2), with $F_{{min }}=0.3$, $F_{max }=0.9$, $C_{R min }=0.3$, and $C_{R max }=0.9$. With $G$ as the current evolutionary iteration number, the maximum evolution number ($G_{m a x}$) of the algorithm was set to 1200 and the Gaussian perturbation coefficient $(C)$ was set to 0.1.

b) The population of size $N P$ was initialised.

c) The improved mutation operation, as described in Section 2.1.2, was applied to individuals $X_{i, G}$ in the population, generating mutant individuals $V_{i, G}$.

d) The improved crossover operation, as described in Section 2.1.3, was applied to both parent and mutant individuals, denoted as $X_{i, G}$ and $V_{i, G}$, to produce intermediate trial individuals $U_{i, G}$.

e) The fitness values of both the parent and intermediate trial individuals, denoted as $X_{i, G}$ and $U_{i, G}$, were computed and compared. Individuals with better fitness values were selected to form the next generation population for further evolution. Steps 3, 4, and 5 were repeated iteratively until the maximum number of evolutionary iterations was reached.

f) The optimal individual output by the algorithm was utilised as the initial cluster centre for the K-means clustering algorithm. The clustering process iterated until the stopping criterion or the maximum number of clustering iterations was met, after which the clustering results were output.

The pseudocode for the K-means clustering algorithm based on the improved differential evolution is presented as follows:

Function ImprovedDifferentialEvolution(Dimensionality):

$\quad\quad$//InitialisePopulationP

$\quad\quad$P = InitialisePopulation(N, Dimensionality)

$\quad\quad$EvaluateFitness(P)

//EvolutionaryProcess

$\quad\quad$for G from 1 to Gmax do:

$\quad\quad\quad\quad$//CalculateMutationFactor F, CrossoverFactorCR, WeightCoefficientW

$\quad\quad\quad\quad$F=Fmax -(Fmax -Fmin)*(G / Gmax)²

$\quad\quad\quad\quad$CR=CRmax-(CRmax-CRmin)*(G / Gmax)²

$\quad\quad\quad\quad$W=Wmin+(Wmax-Wmin)*(G / Gmax)²$\quad\quad$// ForEachIndividual (i)

$\quad\quad\quad\quad$for i from 1 to N do:

$\quad\quad\quad\quad\quad$//GenerateMutantIndividual(Vi)

$\quad\quad\quad\quad\quad$r1, r2, r3, r4, r5, r6, r7 = SelectRandomIndividuals(P)

$\quad\quad\quad\quad\quad$best = SelectIndividuals(P)

$\quad\quad\quad\quad\quad$Vi = GeneratedFromEquation(4)

$\quad\quad\quad\quad\quad$//PerformCrossoverOperationToGenerateIntermediateTrialIndividual(Ui)

$\quad\quad\quad\quad\quad$Ui = CreateEmptyIndividual()

$\quad\quad\quad\quad\quad$for j from 1 to Dimensionality do:

$\quad\quad\quad\quad\quad\quad$r = rand(0, 1)

$\quad\quad\quad\quad\quad\quad$if r < CR then

$\quad\quad\quad\quad\quad\quad\quad$Ui[j]=Vi[j]

$\quad\quad\quad\quad\quad\quad$else

$\quad\quad\quad\quad\quad\quad\quad$r = rand(0, 1)

$\quad\quad\quad\quad\quad\quad\quad$if r <= 0.7 then

$\quad\quad\quad\quad\quad\quad\quad$Ui[j]=Pbest[j]

$\quad\quad\quad\quad\quad\quad\quad$else

$\quad\quad\quad\quad\quad\quad\quad$Ui[j]=GeneratedFromEquation(5)

$\quad\quad\quad\quad\quad$//CalculateFitness

$\quad\quad\quad\quad\quad$fitnessP = EvaluateFitness(Pi)

$\quad\quad\quad\quad\quad$fitnessU = EvaluateFitness(Ui)

$\quad\quad\quad\quad\quad$//UpdateIndividualsToEnterTheNextGenerationPopulation

$\quad\quad\quad\quad\quad$if fitnessU < fitness P then

$\quad\quad\quad\quad\quad$Pi=Ui

$\quad\quad$//OutputTheOptimalIndividualAsTheInitialClusterCentreForK-Means

$\quad\quad$bestIndividual = BestIndividual(P)

$\quad\quad$//PerformK-MeansClustering

$\quad\quad$clusters = KMeansClustering(bestIndividual)

$\quad\quad$//OutputClusteringResults

$\quad\quad$return clusters

end function

The flowchart of the K-means clustering algorithm based on the improved differential evolution is shown in Figure 1.

To validate the effectiveness of the proposed algorithm, extensive experiments were conducted on commonly used clustering datasets from the UCI public database, including Vowel, Iris, and Glass, as well as a synthetic dataset, Jcdx. Details of the datasets are provided in Table 1. The results of the proposed algorithm were compared with the traditional K-means clustering algorithm and the following enhanced K-means clustering algorithms: K-means based on discrete particle swarm optimisation (DPSO-KM), K-means based on grey wolf optimisation (GWO-KM), K-means based on whale optimisation (WOA-KM), and K-means based on differential evolution (DE-KM).

As for the experimental environment, the experiments were performed on a system running Windows 10, with an Intel Core i5-8300H processor and 16.0 GB of memory. Programming was conducted using PyCharm 2021.3.3.

To assess the performance of the clustering algorithms, five evaluation metrics were selected: silhouette coefficient (SC), SSE, Davies-Bouldin (DB) index, Calinski-Harabasz (CH) index, and clustering time [10], [22].

a) SC

For a given sample $x_i$, let $a_i$ denote the average distance between $x_i$ and all other samples in the same cluster, and let ${ }_{b_i}$ represent the minimum average distance between $x_i$ and samples in other clusters. The SC for the sample is defined as follows:

The SC for the clustering result is the mean value of $s_i$ across all samples:

A larger SC indicates better clustering performance.

b) SSE

where, $x_{i, k}$ represents a data point; and $c_k$ denotes the centre of the cluster to which the data point belongs. A smaller SSE value signifies better clustering effectiveness.

c) DB index

where, $s_i$ denotes the average distance between data points within cluster $c_i$ and its centre; and $d_{i, j}$ represents the average distance between clusters $c_i$ and $c_j$. A smaller DB value indicates better clustering effectiveness.

d) CH index

where, $B_K$ is the between-cluster covariance matrix; and ${W_K}$ is the within-cluster covariance matrix.

where, $K$ represents the number of clusters; $c_k$ represents a cluster set centered around $c_k ; n_k$ denotes the number of samples in set $c_k ; c_x$ is the centre of the dataset; and $t r$ refers to the trace of the matrix. A larger CH value indicates better clustering effectiveness.

e) Clustering time

Clustering time is recorded as the total runtime of the algorithm under identical environmental conditions, measured in seconds.

Experiments were conducted on three public datasets and one synthetic dataset to evaluate the performance of the K-means, DPSO-KM, GWO-KM, WOA-KM, DE-KM, and the proposed AGDE-KM algorithms.

The parameter configurations for each algorithm are summarised in Table 2. Each algorithm was executed independently 30 times, and the experimental results are presented in Table 3, Table 4, Table 5, and Table 6. The convergence curves for the algorithms are shown in Figure 2, Figure 3, Figure 4, and Figure 5.

The comparisons of clustering results presented in Table 3, Table 4, Table 5 to Table 6 reveal that on the Iris dataset, due to the relatively uniform distribution of sample data and the small number of clusters, the improvement in clustering performance achieved by AGDE-KM over other algorithms is not substantial. However, the efficiency of clustering has been significantly enhanced. When the results across the Vowel, Iris, Glass, and Jcdx datasets are considered, AGDE-KM demonstrates clear advantages over the traditional K-means clustering algorithm. In terms of SC, the improvements are 1.57%, 1.61%, 24.94%, and 11.92%, respectively. In terms of SSE, the reductions are 5.65%, 19.59%, 13.31%, and 6.1%, respectively. In terms of DB index, the reductions are 4.35%, 11.49%, 12.64%, and 6.93%, respectively. In terms of CH index, the increases are 6.36%, 17.94%, 18.8%, and 12.76%, respectively. In terms of clustering time, the reductions are 83.03%, 81.33%, 77.47%, and 92.63%, respectively. From a theoretical perspective, the improvements can be attributed to the use of adaptive operators and the multi-mutation strategy in AGDE-KM. During the early stages of evolution, a larger search space is ensured, while in the later stages, the efficiency of local search and convergence speed is gradually accelerated as the number of iterations increases. Furthermore, the Gaussian perturbation crossover operation, guided by the best individual in the current population, reduces the likelihood of the algorithm becoming trapped in local optima, particularly in datasets with numerous features and clusters. This enhancement improves the precision of the algorithm's optimisation capability. The results confirm that AGDE-KM exhibits superior clustering performance and greater applicability across diverse data environments.

The convergence performance of the algorithms was validated using the curves shown in Figure 2, Figure 3, Figure 4 to Figure 5. The horizontal axis represents the number of iterations, while the vertical axis denotes the fitness value of the optimal solution found by the algorithm. The results demonstrate that, under the same number of iterations, AGDE-KM exhibits significantly faster convergence speeds and higher optimisation precision on the Vowel, Glass, and Jcdx datasets compared to the other four algorithms. On the Iris dataset, due to its relatively uniform sample distribution, the differences in optimisation precision are minimal; however, AGDE-KM still achieves notably faster convergence than the other algorithms. From a theoretical perspective, the improved algorithm, which incorporates adaptive operators and a multi-mutation strategy, retains a broad search space during the early stages of evolution. As the number of iterations increases, the effects of the improved operators and mutation strategies become more pronounced, progressively accelerating the convergence process. Additionally, the introduction of Gaussian perturbation crossover operation, guided by the best individual in the current population, reduces the likelihood of the algorithm becoming trapped in local optima. This enhancement further improves the optimisation precision of the algorithm.

To address the issues of poor stability and low efficiency in traditional K-means clustering caused by the random selection of initial cluster centres, AGDE-KM was proposed. AGDE-KM employs adaptive operators, incorporates a multi-mutation strategy with a weighted coefficient during the mutation phase, and balances the algorithm's global and local search capabilities, thereby accelerating convergence. To mitigate the risk of becoming trapped in local optima, a Gaussian perturbation crossover operation guided by the best individual in the current population was introduced. This operation provides superior evolutionary directions for individuals while preserving diversity across dimensions. This enhancement improves local search capabilities and avoids the problem of local optima. The optimal solution generated by the improved differential evolution algorithm was utilised as the initial cluster centre, replacing the initial cluster centre randomly selected by the traditional K-means. This approach effectively resolves the issues of poor clustering stability, suboptimal clustering effectiveness, and inefficiency. The improvements achieved make the clustering process more stable and better equipped to capture the intrinsic structure of data, thereby enhancing clustering quality and efficiency. The proposed algorithm provides an effective solution for clustering problems in diverse data environments, demonstrating robustness and high applicability.