A Review of Quantum-Inspired Metaheuristic Algorithms for Automatic Clustering

Abstract

In real-world scenarios, identifying the optimal number of clusters in a dataset is a difficult task due to insufficient knowledge. Therefore, the indispensability of sophisticated automatic clustering algorithms for this purpose has been contemplated by some researchers. Several automatic clustering algorithms assisted by quantum-inspired metaheuristics have been developed in recent years. However, the literature lacks definitive documentation of the state-of-the-art quantum-inspired metaheuristic algorithms for automatically clustering datasets. This article presents a brief overview of the automatic clustering process to establish the importance of making the clustering process automatic. The fundamental concepts of the quantum computing paradigm are also presented to highlight the utility of quantum-inspired algorithms. This article thoroughly analyses some algorithms employed to address the automatic clustering of various datasets. The reviewed algorithms were classified according to their main sources of inspiration. In addition, some representative works of each classification were chosen from the existing works. Thirty-six such prominent algorithms were further critically analysed based on their aims, used mechanisms, data specifications, merits and demerits. Comparative results based on the performance and optimal computational time are also presented to critically analyse the reviewed algorithms. As such, this article promises to provide a detailed analysis of the state-of-the-art quantum-inspired metaheuristic algorithms, while highlighting their merits and demerits.

1. Introduction

Data clustering is considered an unsupervised method for dividing unlabelled data into several groups according to some dissimilarity measures [1,2]. Clustering or cluster analysis is the process of segregating groups with similar objects based on some similarity measures. The segregated groups are called clusters, wherein the objects within a cluster resemble one another more than those within other clusters. When there is no external information about the objects, the clustering task is considered an instance of unsupervised learning [3,4]. Exploratory data analysis is performed in clustering to uncover the concealed patterns in a dataset. Data clustering has various applications in various fields as it uses valuable hidden information within groups. The application areas of clustering include computer science, medical science, engineering, life science, Earth science, economics and bioinformatics, to name a few [3]. Examples of a few particular real-world uses of clustering are available in [5,6,7,8,9,10].

• Data mining: Data mining is the practice of analysing data from different perspectives to extract valuable information from a huge amount of data to develop new products, reduce costs and improve decision-making tasks.
• Marketing: The common uses of cluster analysis include market segmentation to identify the groups of several entities, viz., people, products, services and structure of an organisation, understanding customer behaviour, identifying the opportunities of new products and so on.
• Community detection: The application area of community detection includes the analysis of social networks (e.g., LinkedIn^®, Facebook^®, Twitter^®, etc.), politics (e.g., influence of political parties, astroturfing, etc.), public health (e.g., growth of epidemic spread, detection of cancer, tumours, etc.), smart advertising, criminology (e.g., criminal identification, fraud detection, criminal activity detection, etc.) and so on.
• Insurance: Clustering is used to identify groups of insurance policyholders, assist insurers in taking the necessary measures for mitigating the impact of mortality deviations on the economy and help comprehend the company’s experience with the emergence of death claims and fraud identification.
• Image segmentation: Clustering is widely used in image segmentation for processing satellite images, medical images, real-life images, surveillance images, benchmark datasets, object identification, criminal investigations and security system in airports, to name a few.

The process of data clustering is divided into seven levels, viz., data collection, preliminary data screening, data representation, evaluating the clustering tendency, configuring the clustering strategy, data validation and finally, the interpretation of the clustering [11]. Clustering algorithms are chosen based on the availability of data and on the specific purpose and application. The major classification of clustering methods includes hierarchical algorithms, partitional algorithms, density-based algorithms, grid-based algorithms and model-based algorithms [12,13,14,15,16].

Hierarchical clustering [17,18,19] constructs a hierarchy or tree structure of clusters for data objects. The hierarchical clustering technique is divided into two types, viz., agglomerative and divisive [20,21] clustering. Agglomerative hierarchical clustering [20] is also known as the bottom–up approach, which initially considers each data point as a singleton cluster. After that, in each iteration, all similar clusters are merged to form new clusters until only a single cluster is left. On the other hand, divisive hierarchical clustering [21] is a top–down approach in which the clustering process begins with a single cluster and interactively produces smaller clusters by dividing them.

Partitional clustering initially constructs a set of disjoint clusters with K number of partitions by decomposing a dataset. After that, it uses an iterative relocation process that moves objects from one group to another to enhance the dataset’s segmentation. The partitional clustering algorithms [18] are further classified into two basic types, viz., soft and hard clustering [10]. In soft clustering, the data objects are assigned to two or more clusters with a degree of membership value. Examples of these types of clustering methods include Fuzzy C-Means (FCM) [22], Fuzzy C-Shells (FCS) [23] and Mountain Method [24]. On the other hand, in hard clustering, the data objects are partitioned into disjoint clusters with respect to the objective function. The hard clustering method is classified into three categories, viz., K-means-based, histogram-based thresholding and metaheuristics-based clustering [10]. Examples of some prominent partitional clustering algorithms [18] include the K-means algorithm [25], K-mediods algorithm [26], CLARA [27] and CLARANS [28], to name a few.

Density-based clustering is an unsupervised learning method that identifies distinctive clusters by separating the data points from a contiguous region of high point density to low point density [18,29]. Some well-known density-based clustering methods include the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) [30], Ordering Points To Identify the Clustering Structure (OPTICS) [31] and Mean-shift [32].

Grid-based clustering uses a multi-resolution grid data structure in which the object space is quantised into a finite number of cells. The quantised space is used for performing all the required clustering operations. The advantage of the grid-based method is its fast processing capability. Its processing time depends on the number of cells in each dimension in the quantised space. The grid-based methods include Clustering In QUEst (CLIQUE) [33], Statistical Information Grid (STING) [34], Merging of Adaptive Intervals Approach to Spatial Data Mining (MAFIA) [35] and Wave Cluster [36], to name a few.

Model-based clustering is a probabilistic approach. The mixture of various probability distributions generates the data in which each component represents different clusters. Model-based clustering includes two approaches: classification likelihood and mixture likelihood approaches. In the classification likelihood approach, the estimation of parameters is maximised. The sum of weighted component densities in the mixture likelihood approach represents the probability function. Examples of some model-based clustering algorithms include the expectation maximisation (EM) algorithm [37], Gaussian mixture density decomposition (GMDD) [38], COOLCAT [39] and STUCCO [40], to name a few.

Although the K-means algorithm [25] is considered the best performing algorithm among other clustering algorithms, it requires a priori information regarding the number of clusters in a dataset. Sometimes, knowing the exact number of clusters belonging to a dataset in advance becomes exceedingly difficult due to insufficient and improper information about it. Several researchers have stressed the need for automatic clustering to overcome this issue. The crucial issue of automatic clustering is to not only identify the appropriate number of clusters in a given dataset but it is also essential to evaluate the goodness of the outcome. It is possible to compare several findings and select the best satisfying one in the context of a given application. Thus, clustering can be considered an optimisation problem where the set of parameters that can be changed comprises the number of clusters, the similarity measure and other parameters in addition to the cluster memberships of all the input patterns.

In recent years, metaheuristic algorithms have been well suited for solving complex optimisation and engineering problems. Several nature-inspired metaheuristic algorithms for automatic clustering have evolved to date to mitigate the drawbacks of classical algorithms. Nature-inspired metaheuristic algorithms include evolutionary algorithms, swarm intelligence and stochastic and population-based algorithms. The examples of some metaheuristic algorithms for automatic clustering include Genetic Algorithm (GA) [41], Differential Evolution (DE) [42], Particle Swarm Optimisation (PSO) [43], Firefly Algorithm (FA) [44], Artificial Bee Colony (ABC) [45], Symbiotic Organism Search algorithm (SOS) [46], Bacterial Evolutionary Algorithm (BEA) [47], Grey Wolf Optimiser (GWO) [48], Bat Algorithm (BA) [49], Cuckoo Search (CS) [50] and Teaching Learning-Based Optimisation (TLBO) [51], to name a few. Other notable metaheuristic algorithms include the Starling Murmuration Optimiser (SMO) [52] and the Binary Starling Murmuration Optimiser (BSMO) [53].

The metaheuristic algorithms are well suited for solving optimisation problems but can still experience early convergence. Classical metaheuristic algorithms are hybridised by combining with other algorithms or incorporating quantum computing features to overcome this problem. The term quantum-inspired metaheuristic algorithm [54,55,56] has been introduced by combining the fundamental ideas of quantum computing with classical metaheuristic algorithms. Quantum-inspired metaheuristic algorithms were invented to run algorithms on nonquantum machines. They incorporate the principles of quantum mechanical phenomena with nature-inspired metaheuristic algorithms to achieve supremacy in the performance of the algorithms while running on classical machines. Several quantum-inspired metaheuristic algorithms have been proposed in different fields [54].

This study puts forward an exhaustive review of the state-of-the-art metaheuristic algorithms for automatic data clustering starting from the classical metaheuristics to the quantum-inspired metaheuristics. The relevant papers for this study were collected from the DBLP-Citationnetwork V12 dataset. The DBLP-Citationnetwork V12 dataset [57] contains papers from various domains such as computer science, mathematics and economics. The citation data are collected from various sources, viz., the DBLP, ACM and Microsoft Academic Graph (MAG). Among 6,593,446 publications from the aforementioned dataset, information from 951 research papers on automatic clustering algorithms and 2818 publications for quantum algorithms were collected. Then, the inverted indexed abstracts were used to select the relevant topics with higher topic coherence by adopting the procedure presented in [58]. The publications collected from [57] on automatic clustering algorithms during the period 1970–2023 are presented in Figure 1. The total number of citations of the published papers are computed from the DBLP-Citationnetwork V12 dataset [57] and are presented in Figure 2. During this study, it has been seen that publications on quantum algorithms have significant growth. The incremental growth in publications in quantum algorithms over time is depicted in Figure 3. Thus, it is evident from Figure 1, Figure 2 and Figure 3 that the field of quantum computing is flourishing at a tremendous rate along with the publications regarding automatic clustering, thereby establishing the importance of quantum algorithms in this direction.

The wide application areas of clustering include pattern recognition, information retrieval, bioinformatics, optimisation, data mining, web analysis, machine learning, image segmentation and many more [3,59,60,61,62,63]. Among these major areas of clustering, the contribution of this work is enlightened within the domain of the automatic clustering of various types of datasets in single- and multi-objective environments. In this study, the challenges of the automatic clustering problem are demonstrated in nearly chronological order by employing classical approaches, metaheuristic approaches and quantum-inspired approaches. Figure 4 presents a graphical representation of these different clustering approaches for better visualisation. This study is organised to offer a qualitative insight into the pros and cons of the mentioned algorithms for better comprehension and understanding. This article can be considered a unique avenue that can assist experienced researchers to easily access a wide range of meaningful works at the same place and judge the amount of work that has already been performed in this area. This article might serve as a starting point for aspiring researchers who want to explore the domain of quantum computing framework for the automatic clustering of various types of datasets. It would also serve as a reference for fellow researchers who wish to continue working on the issues commonly encountered in the problem of automatic clustering.

The purpose of this study was to present a thorough analysis of various algorithms for addressing the automatic clustering of various types of datasets. Moreover, comparative results based on the performance and optimal computational time are presented to substantiate the relative merits/limitations of the reviewed algorithms.

The rest of this paper is structured as follows. Section 2 presents a detailed description of the fundamentals of quantum computing. Automatic clustering is defined and described in Section 3. A discussion about a few major cluster validity indices is presented in Section 4. A brief discussion about the automatic clustering techniques based on classical, metaheuristic and quantum-inspired metaheuristic methods is provided in Section 5, Section 6 and Section 7. Finally, the study is concluded in Section 8. The different abbreviations used throughout the paper are presented in the abbreviations part.

2. Quantum Computing Fundamentals

A quantum computer emulates quantum mechanical principles to perform tasks that are difficult to complete using the laws of classical physics. As such, these machines can more effectively model complex real-life processes [64]. Quantum algorithms outperform all potential classical algorithms regarding speed or other efficiency improvements when executed on a quantum computer. Quantum algorithms can be classified into two basic types: pure quantum algorithms and quantum-inspired algorithms. Pure quantum algorithms can run on a quantum computer. The website Quantum Algorithm Zoo offers an extensive collection of quantum algorithms [65]. Quantum algorithms are useful for solving various problems such as searching and optimisation, cryptography, simulation of quantum systems and large systems of linear equations. Quantum machines can describe the structure and physical properties of atoms and subatomic particles and their effects on the intersection. In the 1970s, a few physicists and computer scientists introduced the concept of quantum computing to computing devices [66]. Computing operations in these devices are reversible in nature in contrast to classical computers where electrical energy is dissipated in the form of heat energy during bit manipulation.

Paul Benioff’s idea for creating a computer using the principles of quantum physics was initially conceived in 1981 [67,68]. After that, in 1982, Sir Richard Feynman first demonstrated that fundamental computations could be performed on a quantum system [69,70,71]. The first universal quantum Turing machine (QTM) was proposed by David Deutsch in 1985 [72], which led to the development of Deutsch–Josza’s oracle [72] and Simon’s oracle [73] in 1992 and 1994, respectively. Shor’s factorisation technique, proposed in 1994, is considered a turning point in the advancement of quantum computing [74]. Then, in 1996, Grover proposed a fast database search algorithm referred to as Grover’s algorithm [75].

In contrast to the conventional computer, a quantum computer employs quantum bits or qubits as a memory unit [76]. The manipulation of information in a quantum computer is performed by a quantum bit or qubit, which uses the two-state quantum-mechanical phenomena of superposition, entanglement and interference [77]. In quantum mechanics, the superposition state, $|\Psi \rangle$, is basically a combination of two basis states, $|0\rangle$ and $|1\rangle$. The information stored in the state $|0\rangle$, $|1\rangle$ or $|\Psi \rangle$ is used to realise a single qubit. Mathematically, the superposition state $|\Psi \rangle$ is represented as follows.

$$|\Psi \rangle =\alpha |0\rangle +\beta |1\rangle$$

(1)

The two complex numbers $\alpha$ and $\beta$ represent the probability amplitudes corresponding to the states $|0\rangle$ and $|1\rangle$, respectively. The values of ${\left|\alpha \right|}^2$ and ${\left|\beta \right|}^2$ determine which of these two states ($|0\rangle$ or $|1\rangle$) will collapse when the superposition state is destroyed out of measurement. The realisation of the superposition state can be modelled as follows.

$$|\Psi \rangle =\left\{\begin{array}{ccc}& |0\rangle ,& \mathrm{if}{\left|\alpha \right|}^2>{\left|\beta \right|}^2\\ & |1\rangle ,\end{array}\right.$$

(2)

Otherwise, the Dirac notation corresponding to states $|0\rangle$, $|1\rangle$ and $|\Psi \rangle$ are $|0\rangle =\left[\begin{array}{c}1\\ 0\end{array}\right]$, $|1\rangle =\left[\begin{array}{c}0\\ 1\end{array}\right]$ and $|\Psi \rangle =\alpha |0\rangle +\beta |1\rangle =\left[\begin{array}{c}\alpha \\ \beta \end{array}\right]$, respectively, where ${\left|\alpha \right|}^2+{\left|\beta \right|}^2=1$.

Several representation strategies attest to the superiority of a quantum bit over a classical bit. A quantum bit can concurrently store the values $|0\rangle$ and $|1\rangle$ in a single register, whereas a classical bit can only store 0 or 1 at a time. A classical computer can produce one of the four numbers 00, 01, 10 or 11 by combining two bits. Hence, it requires four registers to store the information. Contrarily, in a quantum computer, two quantum bits can simultaneously process and store four states of information, viz., $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$, using just two registers. Similarly, for an $\mathit{n}$ qubit configuration, $\mathit{n}$ is the number of quantum registers required to simultaneously store $2^{\mathit{n}}$ number of states. All $2^{\mathit{n}}$ states can be linearly superposed into a single sate $|\Psi \rangle$ as

$$|\Psi \rangle =\sum _{\mathit{a}=1}^{2^{\mathit{n}}}{\mathit{P}}_{\mathit{a}}|S_a\rangle$$

(3)

where ${\mathit{P}}_{\mathit{a}}\in \mathbb{C}$ and ${\sum }_{\mathit{a}=1}^{2^{\mathit{n}}}{\left|{\mathit{P}}_{\mathit{a}}\right|}^2=1$.

For a single qubit, Equation (3) transforms into

$$|\Psi \rangle =\alpha |0\rangle +\beta |1\rangle$$

(4)

where

$${\left|\alpha \right|}^2+{\left|\beta \right|}^2=1$$

(5)

In quantum computing, the linear superposition of the basis states $|\Psi \rangle$ is referred to as coherence and is represented by Equation (3). At the time of observation, all existing superposition states are forcefully destroyed and collapse into a single state, also called decoherence.

Quantum entanglement [78] is a phenomenon that occurs when two or more particles become correlated in such a way that their states cannot be separately characterised from one another, even when a large distance physically separates them. When two particles are entangled, measuring the state of one particle will instantaneously determine the state of the other particle, regardless of how far apart they are. Entanglement is a strange and fascinating property of quantum mechanics and it has become a subject of research.

In quantum computing, a qutrit [79,80] is a three-level quantum state consisting of three basis states, viz., $|0\rangle$, $|1\rangle$ and $|2\rangle$. In such a case, the superposition state can be represented as

$$|\Psi \rangle ={\alpha }_0|0\rangle +{\alpha }_1|1\rangle +{\alpha }_2|2\rangle$$

(6)

where $\forall {\alpha }_i\in \mathbb{C}$, s.t. $i=0,1,2$ and the normalisation constraint is ${\alpha }_0^2+{\alpha }_1^2+{\alpha }_2^2$. Qutrits have potential applications in quantum computing and communication, where they can encode more information per quantum state than a qubit. In particular, they can be used to improve the security of quantum key distribution protocols and enhance the capacity of quantum channels for transmitting information. However, the manipulation and control of qutrits are more challenging than those of qubits due to the higher dimensionality of their state space. Therefore, the study of qutrits is an emerging research topic in the realm of quantum information, and progress is being made towards their practical use in quantum technologies.

Qudits [81,82,83] are quantum systems with a state space with more than two dimensions. The term qudit is a generalisation of the term qubit to systems with higher dimensional state spaces. A qudit provides a larger state space to store and process information, which can reduce the complexity of the circuit, simplify the experimental setup and improve the algorithm’s performance. A vector in the n-dimensional Hilbert space can be used to describe the state of a qudit [84], which is a quantum version of n-ary digits that can be represented by Equation (3). Qudits have potential applications in quantum information processing, including quantum computing and quantum communication, where they can be used to increase the information encoding capacity of quantum systems. Nowadays, in quantum information, the study of qudits is an active research area, and steps are being taken to make these systems useful in quantum technology.

A quantum computer employs a variety of quantum logic gates [85] to develop quantum algorithms. In essence, these gates are a collection of hardware components. The names of a few popular quantum gates include the Hadamard gate, NOT gate or Pauli-X gate, Pauli-Y gate, Pauli-Z gate, C-NOT gate, CCNOT gate or Toffoli gate, controlled phase-shift gate, Fredkin gate and Rotation gate [86,87].

Quantum evolutionary algorithms (QEAs) form a class of evolutionary algorithms which can run on both a classical computer and a quantum simulator [88] with minor changes in the code. In 2004, Yang et al. [89] proposed the QEA, which utilises the concept of quantum chromosomes, quantum mutation and quantum crossover. The QEA combines quantum theory with an evolutionary algorithm that runs on a classical computer with the flavour of quantum computing. In 2021, Acampora and Vitiello [88] proposed a new algorithm called HQGA, which uses a hybrid classical/quantum architecture to design a genetic algorithm. HQGA can run on a quantum processor and a simulator in the IBM Q Experience initiative. In order to experience the speed up in the classical computer, new versions of quantum algorithms have evolved, referred to as the quantum-inspired metaheuristic algorithms, which only run on classical computers. Quantum-inspired metaheuristic algorithms are further divided into three types, viz., single-objective-based [90], multi-objective-based [91] and many-objective-based [92] algorithms. In single-objective-based approaches, a single objective function is considered to obtain a single solution. Some examples of this type of approach include the Quantum-Inspired Genetic Algorithm (QIGA) [90] proposed by Narayanan and Moore in 1996, the Quantum-Based Avian Navigation Optimiser Algorithm (QANA) [93] proposed by Zamani et al. in 2021 and the Binary Quantum-Based Avian Navigation Optimiser Algorithm (BQANA) [94] proposed by Nadimi-Shahraki et al. in 2022, to name a few. In multi-objective-based approaches, more than one objective function is considered to obtain a set of Pareto optimal solutions. An example of this type of approach is the Multi-Objective Quantum-Inspired Genetic Algorithm (Mo-QIGA), which was proposed by Konar et al. in 2018 [91]. The many-objective-based approach is a multi-objective approach with a large number of objectives. This approach considers more than four objectives to obtain a set of Pareto optimal solutions. In 2022, Balicki [92] proposed the Many-Objective Quantum-Inspired Particle Swarm Optimisation Algorithm (MQPSO) to ensure the diversity in a particle population by introducing quantum gates in PSO.

3. Automatic Clustering

As the name suggests, automatic clustering refers to the process of clustering in which the optimal number of clusters needs to be automatically identified before the clustering process in those situations where no a priori knowledge of the exact number of clusters belonging to a dataset is available [95,96,97]. Examples of some typical application areas of automatic clustering include browsing through personal photographs from a collection of photographs [95], database query execution plans [98], categorising colour images from synthetic data and a real-world COREL dataset [99], image segmentation [96,100] and automatic clustering of real-life datasets [97], to name a few.

Automatic clustering algorithms are required for the applications mentioned above as, most of the time, it is very difficult to analyse or cluster datasets without having prior information about them. It is seen that, in most cases, the dataset contains insufficient information. In this scenario, automatic clustering is crucial in identifying the exact number of clusters from the dataset for further processing.

Let us consider that the initial dataset, $D=\{x_1,x_2,x_3,\dots ,x_n\}$ contains n number of data points before clustering as depicted in Figure 5. The following conditions should be satisfied for a successful clustering of this dataset into K number of clusters.

$${\mathit{C}}_{\mathit{i}}\ne 0,fori=1,2,\dots ,\mathit{K}$$

(7)

$${\mathit{C}}_{\mathit{i}}\bigcap {\mathit{C}}_{\mathit{j}}=0,fori,j=1,2,\dots ,\mathit{K}andi\ne j$$

(8)

$$\bigcup _{i=1}^{\mathit{K}}{\mathit{C}}_{\mathit{i}}=\mathit{D}$$

(9)

where ${\mathit{C}}_{\mathit{i}}$ designates the individual clusters. However, if the number of clusters is unknown, an automatic clustering algorithm must group the data points in D into some groups or clusters. This grouping is performed based on some similarity measures. Hence, the main objective of an automatic clustering algorithm is to automatically identify a suitable number of clusters (k). The clustered dataset $C=\{C_1,C_2,C_3,\dots ,C_k\}$ containing a k number of clusters, thereby obtained, can be depicted as shown in Figure 6.

Cluster validity indices (CVI) play a crucial role in assessing the quality of clustering. However, there is no CVI that can guarantee accurate results for different data structures. In this regard, automatic clustering can be considered an optimisation problem to ensure more satisfactory results within a minimum time frame [101,102,103]. Considering it as an optimisation problem, researchers have designed algorithms which fall into three categories based on single-objective evolutionary approaches [101], based on multi-objective evolutionary approaches [103] and based on hybrid metaheuristic approaches [102]. Although the evolutionary algorithms provide almost ideal results within a minimum time frame, they nonetheless have the propensity to get stuck in local optima. A new research direction has cropped up which entails quantum-inspired frameworks associated with classical metaheuristic approaches [104,105] to address this issue.

4. Cluster Validity Indices

The cluster validity index (CVI) evaluates the goodness of a clustering algorithm by considering the information in the data themselves [106,107,108,109,110,111,112,113,114,115]. CVI is a mathematically justifiable function which can be either maximised or minimised. It defines a relationship between cluster cohesiveness and cluster separation to estimate the effectiveness of a clustering solution. In metaheuristic algorithms, CVI is utilised as an objective function to be optimised. Some well-known cluster validity indices are discussed as follows.

4.1. Davies–Bouldin Index (DB)

The Davies–Bouldin index ($DB$) [116] was proposed by Davies and Bouldin in 1979. It has a positive correlation for the “within-class” scenario and a negative correlation for the “between-class” scenario. Mathematically, it is expressed as

$$DB=\frac{1}{N_c}\sum _{i=1}^{N_c}{R}_i$$

(10)

where $R_i$ is computed as

$$R_i=\underset{i\ne j}{max}{R}_{ij},$$

(11)

$$R_{ij}=\frac{S_i+S_j}{D_{ij}},$$

(12)

$$S_i={\left[\frac{1}{N_i}\sum _{l=1}^{N_i}{∥X_l^{\left(i\right)}-Z_i∥}^2\right]}^{\frac{1}{2}},$$

(13)

and

$$D_{ij}=∥Z_i-Z_j∥$$

(14)

Here, $S_i$ measures dispersal inside the cluster i, $N_c$ represents the number of clusters, $X_l^{\left(i\right)}$ is a feature vector assigned to cluster i, $Z_i$ is the centre of cluster i, $N_i$ represents the cluster i and the Euclidean distance between the two centres of clusters i and j is represented by $D_{ij}$. The optimal result is achieved for a minimum value of the $DB$-index. A detailed explanation of the $DB$-index is available in [116].

4.2. Dunn Index (DI)

The Dunn index ($DI$) [117] was proposed by Dunn in 1973. It attempts to identify compact and well-separated sets of clusters. Mathematically, it is expressed as

$$DI=\underset{1\le i\le N_c}{min}\left(\underset{i+1\le j\le N_c}{min}\left(\frac{dist(C_i,C_j)}{\underset{1\le p\le N_c}{max}diam\left(C_p\right)}\right)\right)$$

(15)

where $dist(C_i,C_j)$ represents the distance from cluster $C_i$ to cluster $C_j$ and $diam\left(C_p\right)$ represents the diameter of cluster $C_p$.

A maximum value of $DI$ indicates the optimal result. A detailed explanation of $DI$ is available in [117].

4.3. Calinski–Harabasz Index (CH)

The Calinski–Harabasz index ($CH$) [118] was proposed by Caliński and Harabasz in 1974. In this index, the cohesiveness is calculated based on a measurement of the separation between the cluster points and their centroids. Mathematically, it is expressed as

$$CH=\frac{{\sum }_{i=1}^k{n}_i{d}_e^2({\mu }_i,\mu )/(k-1)}{{\sum }_{i=1}^k{\sum }_{x\in C_i}{d}_e^2(x,{\mu }_i)/(n-k)}$$

(16)

where k represents the total number of clusters in a dataset with n data points, $n_i$ and ${\mu }_i$ represent the number of points and the centroid of the $i_{th}$ cluster, respectively, $\mu$ is the global centroid and $d_e^2({\mu }_i,\mu )={∥{\mu }_i-\mu ∥}^2$. A maximum value of the $CH$ index indicates the optimal result. A detailed explanation of the $CH$ index is available in [118].

4.4. Silhouette Index (SI)

In 1987, Rousseeuw [119] proposed the Silhouette index ($SI$). This index compares the pairwise difference in distances within and between clusters to validate the clustering performance. Mathematically, it is expressed as

$$SI=\frac{1}{K}\sum _{i=1}^{K}S\left(C_i\right)$$

(17)

where K is the number of clusters and for a given cluster $C_i$, $S\left(C_i\right)$ is referred to as the Silhouette width of a point x and can be defined as

$$S\left(C_i\right)=\frac{1}{n_i}\sum _{x\in C_i}\frac{b\left(x\right)-a\left(x\right)}{max\left(a\right(x),b(x\left)\right)}$$

(18)

where $C_i$ consists of $n_i$ number of patterns. The mean distance within a cluster and the shortest mean distance between two points are represented by $a\left(x\right)$, while $b\left(x\right)$ indicates the patterns in a different cluster. The average of the separations between x and the other patterns in the same cluster is used for this purpose. The value of $S\left(C_i\right)$ lies between −1 and 1. A value near 1 indicates that the sample is well clustered and assigned to a very appropriate cluster. Misclassifications can be identified for values closer to −1.

A maximum value of $SI$ indicates the optimal result. A detailed explanation of $SI$ is available in [117].

4.5. Xie–Beni Index (XB)

The Xie–Beni index ($XB$) [107] was proposed by Xie and Beni in 1991. It is an index for fuzzy clustering that also applies to crisp clustering. It is described as the ratio of the mean quadratic error to the smallest possible minimal squared distance between the points in the cluster. Mathematically, it is expressed as

$$XB=\frac{J}{D_{min}}$$

(19)

where

$$J=\frac{1}{N}\sum _{i=1}^C\sum _{j=1}^N{u}_{i,j}^m{d}^2(X_j,C_i)$$

(20)

$$d^2(X_j,C_i)={(X_j-C_i)}^{T}A(X_j-C_i)$$

(21)

and

$$D_{min}=\underset{i,j}{min}\left[d^2(C_i,C_j)\right]$$

(22)

where $u_{i,j}^m$ and $C_i$ represent the fuzzy membership value and cluster centroid, respectively. The number of clusters and data points are represented by C and N, respectively. A represents a $p\times p$ positive definite matrix, p is the dimension of $X_j(j=1,2,\dots ,n)$ and $m>1$ is the fuzzy index [120].

A minimum value of $XB$ indicates the optimal result. A detailed explanation of $XB$ is available in [107].

4.6. S_Dbw Index

The $S\_Dbw$ Index [121] was proposed by Halkidi and Vazirgiannis in 2001. It determines the compactness value of the clusters using the standard deviations of a set of objects and the standard deviations of a partition, where the distance between the centres of the clusters determines the separation value. It is a ratio-type index in which the density of clusters is considered. Mathematically, it is expressed as

$$S\_Dbw=\frac{1}{k}\sum _{C_i\in C}\frac{\sigma \left(C_i\right)}{\sigma \left(X\right)}+\frac{1}{k(k-1)}\sum _{C_i\in C}\sum _{C_j\in C,C_i\ne C_j}\frac{Den(C_i,C_j)}{max\left\{Den\left(C_i\right),Den\left(C_j\right)\right\}}$$

(23)

where $Den$ represents the density of the cluster defined as

$$Den\left(C_i\right)=\sum _{x_p\in C_i}f(x_p,{\mu }_i)$$

(24)

and

$$Den(C_i,C_j)=\sum _{x_p\in C_i\bigcup C_j}f\left(x_p,\frac{{\mu }_i+{\mu }_j}{2}\right)$$

(25)

where

$$f(x_p,{\mu }_i)=\left\{\begin{array}{ccc}0,& & d_e(x_p,{\mu }_i)>\sigma \left(C\right),\\ 1,& & otherwise.\end{array}\right.$$

(26)

The lowest value of $S\_Dbw$ identifies the ideal outcome. A detailed explanation of $S\_Dbw$ is available in [121].

4.7. I Index

In 2002, Maulik et al. [122] proposed the I index. It is made up of three different components, viz., $\frac{1}{\mathcal{K}}$, $\frac{{\mathcal{E}}_1}{{\mathcal{E}}_{\mathcal{K}}}$ and ${\mathcal{D}}_{\mathcal{K}}$, and can be described as follows.

$$I={\left(\frac{1}{\mathcal{K}}\times \frac{{\mathcal{E}}_1}{{\mathcal{E}}_{\mathcal{K}}}\times {\mathcal{D}}_{\mathcal{K}}\right)}^{\rho }$$

(27)

where $\mathcal{K}$ represents the number of clusters in the dataset, $\mathcal{DS}$. The power $\rho$ controls the various configurations of clusters. A constant ${\mathcal{E}}_1$ represents the total distance of all data points from the centre of $\mathcal{DS}$. ${\mathcal{E}}_1$ is defined as

$${\mathcal{E}}_1=\sum _{\mathcal{P}\in \mathcal{DS}}∥\mathcal{P}-\mathcal{V}∥$$

(28)

where the centre of the patterns, $\mathcal{P}\in \mathcal{DS}$, is represented by $\mathcal{V}$. ${\mathcal{E}}_{\mathcal{K}}$ describes the total cluster scatters inside a pattern. It is defined as

$${\mathcal{E}}_{\mathcal{K}}=\sum _{i=1}^{\mathcal{K}}\sum _{j=1}^{\mathcal{N}}{\mathcal{U}}_{ij}∥{\mathcal{P}}_j-{\mathcal{V}}_i∥$$

(29)

where the number of data points belonging to a dataset $\mathcal{DS}$ is represented by $\mathcal{N}$. The ith cluster centre is represented by ${\mathcal{V}}_i$ and a partition matrix, $\mathbf{U}\left(\mathcal{DS}\right)={\left[{\mathcal{U}}_{ij}\right]}_{\mathcal{K}\times \mathcal{N}}$ is used to partition the data points. The cluster separation measure ${\mathcal{D}}_{\mathcal{K}}$ is defined as

$${\mathcal{D}}_{\mathcal{K}}=\underset{i,j=1}{\overset{\mathcal{K}}{max}}∥{\mathcal{V}}_i-{\mathcal{V}}_j∥$$

(30)

A maximum value of I indicates the optimal result. In reference [122], an elaborate discussion is presented on the individual contributions of $\frac{1}{\mathcal{K}}$, $\frac{{\mathcal{E}}_1}{{\mathcal{E}}_{\mathcal{K}}}$ and ${\mathcal{D}}_{\mathcal{K}}$.

4.8. CS-Measure (CSM)

The CS-Measure ($CSM$) [123] was proposed by Chou et al. in 2004. The ratio of the sum of the within-cluster scatter and between-cluster separation is used to generate this index. Mathematically, it is expressed as

$$CSM=\frac{{\displaystyle \sum _{i=1}^{{\mathcal{N}}_{\mathcal{C}}}}\left[\frac{1}{\parallel {\mathcal{N}}_i\parallel }{\displaystyle \sum _{{{\mathcal{D}}_{\mathcal{P}}}_i\in {{\mathcal{D}}_{\mathcal{SET}}}_i}}\underset{{{\mathcal{D}}_{\mathcal{P}}}_{mx}\in {{\mathcal{D}}_{\mathcal{SET}}}_i}{max}{D}_F({{\mathcal{D}}_{\mathcal{P}}}_i,{{\mathcal{D}}_{\mathcal{P}}}_{mx})\right]}{{\displaystyle \sum _{i=1}^{{\mathcal{N}}_{\mathcal{C}}}}\left[\underset{j\in {\mathcal{N}}_{\mathcal{C}},j\ne i}{min}{D}_F({{\mathcal{C}}_{\mathcal{C}}}_i,{{\mathcal{C}}_{\mathcal{C}}}_j)\right]}$$

(31)

where ${\mathcal{N}}_i$ represents the total number of data points (${{\mathcal{D}}_{\mathcal{P}}}_i$) belonging to the ith cluster ${{\mathcal{D}}_{\mathcal{SET}}}_i$ and $D_F({{\mathcal{D}}_{\mathcal{P}}}_i,{{\mathcal{D}}_{\mathcal{P}}}_j)$ provides the distance between any two data points ${{\mathcal{D}}_{\mathcal{P}}}_i$ and ${{\mathcal{D}}_{\mathcal{P}}}_j$.

A minimum value of $CSM$ indicates the optimal result. A detailed explanation of $CSM$ is available in [123].

4.9. PBM Index (PBM)

In 2004, Pakhira et al. [124] proposed a CVI referred to as the $PBM$ index ($PBM$). Mathematically, it is expressed as

$$PBM={\left(\frac{1}{N_C}\times \frac{E_0}{E_{N_C}}\times D_{N_C}\right)}^2$$

(32)

where $N_C$ represents the number of clusters. A constant term, $E_0$, represents the summation of distances of all the data points in a pattern $P_T$ from the centre of a dataset $D_{SET}$. $E_0$ can be measured as follows.

$$E_0=\sum _{P_T\in D_{SET}}∥P_T-V_C∥$$

(33)

where $V_C$ is the centre of the pattern $P_T\in D_{SET}$.

$E_{N_C}$ defines the total cluster scatter belonging to $P_T$ and is measured as

$$E_{N_C}=\sum _{i=1}^{N_C}\sum _{j=1}^{D_P}P{M}_{ij}∥P_{T_j}-V_{C_i}∥$$

(34)

where $D_P$ denotes the number of data points in $D_{SET}$ and $V_{C_i}$ represents the ith cluster centre and ${\left[P{M}_{ij}\right]}_{N_C\times D_P}$ denotes the partition matrix of $D_P$. The term $D_{N_C}$ represents the cluster separation measure and can be measured as follows.

$$D_{N_C}=\underset{i,j=1}{\overset{N_C}{max}}∥V_{C_i}-V_{C_j}∥$$

(35)

$PBM$ is generated after balancing the three factors, viz., $\frac{1}{N_C}$, $\frac{E_0}{E_{N_C}}$ and $D_{N_C}$.

A maximum value of $PBM$ indicates the optimal result. A detailed explanation of $PBM$ is available in [124].

4.10. Local Cores-Based Cluster Validity (LCCV) Index

The Local Cores-Based Cluster Validity ($LCCV$) Index [125] was proposed by Cheng et al. in 2019 to improve the performance of the $SI$ index [119]. Arbitrary-shaped clusters can be effectively evaluated by this index. The performance of $SI$ is enhanced by the $LCCV$ index, which measures the dissimilarity between local cores using graph-based distance. Mathematically, it is expressed as

$$LCCV=\frac{1}{n}\sum _{i=1}^{n_l}\left(LCCV\left(i\right)\times n_i\right)$$

(36)

where n is the total number of objects in a dataset X. $n_l$ represents the total number of local cores and $n_i$ represents the total number of points in the ith local core and

$$LCCV\left(i\right)=\frac{b\left(i\right)-a\left(i\right)}{max\left\{b\left(i\right),a\left(i\right)\right\}}$$

(37)

where

$$a\left(i\right)=\left(\frac{1}{n_l\left(A\right)}-1\right)\sum _{j\in A,j\ne i}D(i,j)$$

(38)

and

$$b\left(i\right)=mi{n}_{C\ne A}\left\{d(i,C)\right\}$$

(39)

where A represents the cluster in which a local core $i\in X$ is assigned and the total number of local cores in cluster A is represented by $n_l\left(A\right)$. $a\left(i\right)$ represents the average distance in a graph between the local core i and other local cores in A. $a\left(i\right)$ is computed by Equation (38). $d(i,C)$ represents the average distance in a graph between the local core i and the local cores in another cluster C, which is evaluated as follows.

$$d(i,C)=\left(\frac{1}{n_l\left(C\right)}\right)\sum _{j\in C}D(i,j)$$

(40)

$b\left(i\right)$ is selected as the smallest one among all $d(i,C)$ after considering all clusters C$(C\ne A)$. The value of $LCCV\left(i\right)$ varies in the range of (−1, 1). A better clustering result can be achieved for a maximum value of $LCCV$. A detailed explanation of the $LCCV$ index is available in [125].

5. Classical Approaches to Automatic Clustering

Classical approaches refer to those well-known methods that have been widely used and studied for a long time and have been evidenced to be reliable and effective solutions to the problem of automatic clustering. These algorithms iteratively improve the clustering solution by computing the means of current clusters and reassigning observations to the nearest cluster until the cluster means no longer changes or a maximum number of iterations is reached.

In 2004, Husain et al. proposed an efficient automatic clustering technique referred to as Similarity Index Fuzzy C-Means Clustering [126] to generate a more optimal Generalised Regression Neural Network (GRNN) [127,128] structure. This technique is used for dynamic system identification and modelling. In this work, the conventional fuzzy C-means clustering [22] algorithm and a similarity indexing technique were used to automatically cluster the relevant input data in a system. The proposed algorithm was compared with the existing clustering strategies, which rely on fuzzy C-means and a self-organising map. The outcome proved the supremacy of the proposed algorithm over others from the same domain.

An automatic clustering approach based on an adaptive influence function called ADACLUS was proposed by Nosovskiy et al. in 2008 for automatic clustering and boundary detection [129]. This algorithm can automatically identify the number of clusters from various two-dimensional datasets with complex shapes and diverse densities. The experimental results were found to be favourable towards the proposed algorithm.

In 2011, Li et al. [130] proposed an automatic classification method to classify the uncertain data by a soft classifier. The proposed classifier combines fuzzy C-means with a fuzzy distance function and an evaluation function to categorise the fuzzy objects in an ambiguous database. The experimental results indicated that the proposed classifier performs well in various types of databases that contain uncertain data. For experimental purposes, a location service environment was simulated by a synthetic dataset. The generation of the synthetic dataset involved a two-stage process. During the simulation process, a Gaussian random variable generator generated the deterministic dataset D having n number of objects in the ${[0,1]}^m$ unit space. After that, D was decomposed into two sets with $\frac{n}{2}$ number of objects. Experiments were conducted on two synthetic datasets (Synthetic I and Synthetic II) and the sensor database (Sensor). This paper compared the Automatic Fuzzy C-Means with Randomly Selected Initial Centres (AFCR) with Automatic Fuzzy C-Means with Selected Initial Centres by Histogram (AFCH). As per the experimental results, AFCH outperformed AFCR regarding running time.

In 2015, Zhang et al. [131] designed a clustering method referred to as Multi-Document Summarisation (MDS) to generate a summary from a given set of sentences by selecting appropriate sentences from the documents. The study described a multi-document summarising technique based on density peaks sentence clustering (DPSC) [132]. The proposed method can automatically find the best cluster centres and assign a rank to all the data points. In this paper, the experiments were conducted on the DUC2004 dataset [133]. The overall time complexity for the proposed method was found to be $O\left(K^2\right)$, where K represents the total number of sentences in the document. The proposed DPSC-based MDS method outperformed other comparable MDS methods, viz., DUC04Best [134], Centroid [135], ClusterHITS [136], SNMF [137], RTC [138], FGB [139] and the state-of-the-art unsupervised MDS methods such as LexRank [140] and CSFO [141], while providing similar results such as the WCS method [142].

In 2016, Wang and Song proposed an automatic clustering algorithm based on outward statistical testing on density metrics referred to as Statistical Test-Based Clustering (STClu)[143], which effectively clustered the objects by properly identifying the clustering centres. STClu provides a unique clustering approach to overcome the drawbacks of RLClu [132]. The robustness of STClu lies behind the local density evaluation metric, K-density $\widehat{\rho }$. It is reliable in detecting clustering centres compared to $\rho$ in RLClu. The effectiveness of the proposed algorithm depends upon the number of nearest neighbours K. The distance of a cluster centre from its K nearest neighbours is generally less than the total distances between other non-clustering centres and their K neighbours. As a result, the K-density $\widehat{\rho }$ can more easily distinguish between several objects than the local density $\rho$ in RLClu. The proposed algorithm performs three tasks, viz., extracting metrics, identifying cluster centres and clustering of objects. For experimental purposes, five groups of benchmark clustering datasets, viz., S-sets, A-sets, shape sets, high-dimensional datasets and real-world datasets were used [132,144]. The time complexity of STClu is $\left(O(n^2.O\left(dist\right))\right)$ which depends upon the distance (dist) between two objects. As a result, both STClu and RLClu exhibit the same time complexity. However, in most cases, STClu is more efficient than RLClu in identifying the clustering centres.

In 2018, Chen et al. proposed an automatic clustering algorithm based on region segmentation (CRS) [145]. Initially, it identifies an optimal number of clusters from a dataset. After that, depending on the data density, the clusters of the datasets evolve. In this work, all the experiments were conducted on six groups of synthetic datasets, viz., Can383, Jain, Aggregation, S1, S2 and S3 [146,147], and seven real-world datasets, viz., three UCI datasets, Geo-referenced Event Dataset of the Uppsala Conflict Data Program (UCDP) and three image datasets [148,149]. The overall time complexity of CRS is $O\left(n^2\right)$, where n is the number of data points in a given dataset. In this paper, the comparable algorithms included DBSCAN [30], IS-DBSCAN [146], DP [132], SCDOT [147] and STClu [143]. According to the experimental results, the proposed algorithm proved superior to other comparable algorithms and remained unaffected by the parameter settings.

In 2019, the authors proposed a fuzzy clustering algorithm referred to as AP-FA-FCM [150] for automatically determining the number of clusters in an image. This not only provided a solution for the automatic segmentation of images but also improved the quality of the image segmentation. Initially, this work determined the number of clusters using the Affinity Propagation (AP) clustering algorithm [151] by constructing a similarity matrix from the features of the extracted image. After that, the obtained number of clusters was used as an input to the fuzzy C-means (FCM) algorithm [22]. Then, the clustering centre was subsequently optimised using the FA [44]. The outcome of the experiments proved that the proposed algorithm has an excellent effect and can efficiently realise automatic image segmentation.

In 2020, Studiawan et al. proposed a graph-based automatic clustering technique referred to as Automatic Security Log Clustering (ASLoC) for security log clustering [152]. In this work, a graph data structure is used to represent the security logs, in which the logs are grouped by connecting their log entries for some similarity measures. This method used the $CH$ [118] and $DB$ indices [116] as the objective functions to validate the clustering results. For experimental purposes, five publicly available security log datasets, viz., SSH brute-force attacks records kept in authentication logs [153], event logs kept in the SecRepo (Security Repository) website provided by Sconzo [154], Snort IDS logs from The Honeynet Project by Chuvakin [155], Snort IDS log dataset produced by the National CyberWatch Center in the Mid-Atlantic Collegiate Cyber Defense Competition [156] and syslog from a real-world honeypot installed in a RedHat-based Linux server were used [157]. The experimental results proved that ASLoC could be efficiently used to group the security logs and provides better clustering than others.

In 2021, Sahoo and Parida proposed an automatic clustering technique for brain tumour extraction from MRI images [158]. This work uses the Communication with Local Agents (CLA) [159] clustering technique and morphological post-processing methods to extract the tumour regions from the white matter regions of the human brain. In order to identify the meningiomas, gliomas and pituitary tumours present in MRI images [158,159,160], this work uses the intensity clustering approach. The algorithm performed well in meningioma tumour detection compared to the other two tumour detection methods. It was also found to be capable of extricating tumours from the nearest location of the skull. The outcome proved the effectiveness of the suggested algorithm over other comparable algorithms.

A detailed study of the contributions made in the domain of classical approaches to automatic clustering is demonstrated in

Table 1. Classical approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[126]	This paper presents an efficient automatic clustering technique referred to as the Similarity Index Fuzzy C-Means Clustering to generate a more optimal GRNN (Husain et al., 2004).	Used techniques include the conventional fuzzy C-means clustering algorithm and a similarity indexing technique.	Two benchmark problems, viz., the gas furnace data of Box and Jenkins and the MackeyGlass model for producing WBC, served as a simulation for the proposed approach.	Merits: 1. It is suitable for online dynamic GRNN-based modelling. Demerits: 1. Only two dynamic time series are considered for simulating the work.
[129]	This paper presents an automatic clustering and boundary detection algorithm referred to as ADACLUS (Nosovskiy et al., 2008).	It is based on a local-adaptive influence function which is not predefined as in DBSCAN and DENCLUE.	It has been applied to various two-dimensional datasets with arbitrary shapes and densities. Two shape features (circular/non-circular and concave/non-concave) of the clusters in the datasets were considered.	Merits: 1. It is suitable for large-scale real-time applications. 2. It can efficiently identify the clusters of datasets with arbitrary shapes and non-uniform densities on the run. 3. It can also easily detect the boundary of the clusters. 4. It is more robust to noise resistance than other competitive algorithms. Demerits: 1. It is not designed for model-based clustering and hence cannot distinguish overlapping clusters.
[130]	This paper presents an automatic soft classifier to classify uncertain data in synthetic datasets (Li et al., 2011).	The proposed classifier includes fuzzy C-means with a fuzzy distance function and an evaluation function.	It has been applied to two synthetic datasets (Synthetic I, Synthetic II) and the sensor database (sensor).	Merits: 1. The proposed classifier performed effectively on different types of data containing uncertain data. 2. The required running time was found to be $50\%$ less than others. Demerits: 1. No significant difference was achieved in the rate of error.
[131]	This paper presents a clustering method referred to as MDS (Zhang et al., 2015).	It uses the DPSC technique to automatically produce a summary from a given set of sentences by selecting the appropriate sentences from those documents.	The DUC2004 dataset has been used to conduct the experiments.	Merits: 1. It verifies that DPSC can effectively handle MDS. Demerits: 1. Sentence similarity matrix is required to improve the query-based multi-document summarisation method preparation.

,

Table 2. Classical approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[143]	This study introduces the automatic clustering algorithm, STClu, which is based on external statistical testing on density metrics (Wang et al., 2016).	It introduces a local density evaluation metric K-density $\widehat{\rho }$ which offers more robustness than detecting the clustering centre $\rho$ from RLClu.	It has been applied to five groups of benchmark clustering datasets.	Merits: 1. STClu is efficient in identifying the clustering centres in most cases. Demerits: 1. No significant improvement in terms of the time complexity $\left(O(n^2.O\left(dist\right))\right)$ is found in STClu when compared with RLClu.
[145]	This paper presents an automatic clustering algorithm referred to as CRS (Chen et al., 2018).	It uses a region segmentation mechanism, which is unaffected by the parameter settings, the shape of the cluster and the density of the data.	For experimental purposes, six groups of synthetic datasets and seven real-world datasets were used.	Merits: 1. It can efficiently and automatically identify the optimal number of clusters and the clusters of the dataset. Demerits: 1. Before the execution, it requires an approximate value of the number of nearest neighbour K.
[150]	This study introduces a fuzzy clustering algorithm referred to as AP-FAFCM for automatic clustering (Yangyang et al., 2019).	In this algorithm, the number of clusters is initially estimated using the AP clustering algorithm. After that, the FCM algorithm receives the obtained number of clusters, and then the FA is used to optimise the clustering centre.	It has been applied to three randomly selected images.	Merits: 1. It not only resolves the issue of automatic segmentation but also significantly raises the level of segmentation quality while maintaining the effect of segmentation. Demerits: 1. Very few datasets have been chosen. 2. The effect of segmentation has not been considered for all the datasets.

and

Table 3. Classical approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[152]	This paper presents a graph-theoretic approach for ASLoC (Studiawan et al., 2020).	This method incorporates three steps of operation to maximise the number of percolations and intensity threshold for clique percolation, starting with a graph-theoretic approach, including intensity threshold and ultimately using a simulated annealing process.	Five publicly available security log datasets were used for experimental purposes.	Merits: 1. It automatically determines the used parameters without the intervention of user input. 2. It provides more significant results than comparable algorithms in all scenarios. Demerits: 1. The deployment of event log clustering is not yet achieved for anomaly detection. 2. A multi-objective framework still needs to be addressed.
[158]	This study describes an effective way to extract brain tumours by employing the CLA clustering technique (Sahoo et al., 2021).	All image slices are subjected to skull stripping using a morphological operation and a histogram-based methodology.	Three different types of tumours, viz., meningiomas, gliomas and pituitary tumours, have been taken into account from a publicly available brain tumour dataset.	Merits: 1. It shows $99.64\%$ accuracy and outperforms other comparable algorithms in finding meningioma tumours near the skull regions compared to other types of tumours. Demerits: 1. Among three types of tumour, viz., meningiomas, gliomas and pituitary tumours, it only performs better for the meningioma tumours.

. The listed algorithms dating between 2004 and 2021, are compared based on the aim of the concerned works, used mechanisms, data specifications, merits and demerits. All the listed algorithms significantly outperform their competing algorithms.

6. Metaheuristic Approaches to Automatic Clustering

Generally, classical algorithms do not always guarantee global optimality as they rely on the local search strategy. Thus, the results often depend on the initial starting point. In real-world scenarios, the manual recognition and categorisation of data points are often difficult as the datasets generally contain unlabelled data points. This problem limits the performance of the classical algorithms. Furthermore, classical algorithms are mostly seen to be problem-specific, and they also struggle to deal with discontinuity issues.

Nature-inspired metaheuristic algorithms have evolved to overcome the limitations of classical algorithms. The nature-inspired metaheuristic algorithms are classified into two broad categories: single-objective and multi-objective [161,162]. In the case of single-objective optimisation problems, a single objective function is used to compute the fitness of the individuals belonging to a solution or population. In real-world scenarios, a single objective function can properly tackle most problems. In other types of optimisation, the problem can be handled using multi-objective optimisation techniques in which more than one objective function is simultaneously optimised [163,164,165,166]. In this case, a set of Pareto optimal solutions is generated. The search gradually converges to the true Pareto front by identifying the solutions from the frontier of the Pareto efficient set. Metaheuristic algorithms have often been used to solve the problems of automatic clustering [167,168].

The following subsections present an extensive investigation of the most important nature-inspired metaheuristic algorithms used to deal with the problem of automatic clustering.

6.1. Single-Objective Approaches

In these approaches, a single candidate solution is used, and over time, it uses a local search strategy to improve this solution. However, the solution obtained by executing a single-objective-based metaheuristic may get stuck in the local optima [161,169]. Some examples of single-objective-based metaheuristics include simulated annealing [170], Tabu search (TS) [171], microcanonical annealing (MA) [172] and guided local search (GLS) [173].

This section presents some of the current metaheuristic algorithms for solving the problem of automatic clustering of different types of datasets by satisfying a single objective function.

The earliest attempt for automatic clustering based on GA was proposed by Tseng and Yang in 2001 [97]. The proposed algorithm CLUSTERING with a heuristic strategy can automatically find the exact number of clusters. The proposed algorithm has been compared with three other conventional algorithms, viz., K-means, Single link and Complete link [25,174,175]. All the experiments were performed on one real-life and two artificial datasets [176], which proved that CLUSTERING outperformed its counterparts.

In 2003, Merwe and Engelbret proposed two new PSO-based approaches for data clustering [177]. In the first approach, PSO was used to find the centroids of a user-specified number of clusters. In the second approach, PSO was used to refine the clusters formed by the K-means algorithm [25] to seed the initial swarm. In this paper, the proposed algorithms were executed on six datasets. To prove the efficiency of the proposed algorithms, they were contrasted with the K-means clustering algorithm.

In 2004, Garai and Chaudhuri proposed a Genetically Based Clustering Algorithm (GCA) to automatically find the correct number of clusters using a two-stage split-and-merge strategy [178]. GCA is composed of two algorithms, viz., the cluster decomposition algorithm (CDA) and the hierarchical cluster merging algorithm (HCMA) [179,180]. One real-life and nine artificial datasets were used for experimental purposes. A comparison was made between the proposed GCA [178] and the CURE [181], DBScan [30] and Chameleon [182] clustering methods to prove the superiority of GCA [178].

Das et al. [183] proposed an improved differential evolution algorithm in 2008 to automatically cluster real-life datasets. The $CS$-measure [123] and $DB$-index [116] were used as the cluster validity indices. The proposed algorithm was compared with two other state-of-the-art automatic clustering techniques, viz., GA [184] and PSO [185]. The comparison was made based on the accuracy of the final clustering results, convergence speed and robustness. The analysis of the experimental results revealed that the proposed algorithm performed better than all other competitive algorithms.

In 2011, Karaboga and Ozturk proposed the ABC [186] algorithm for data clustering on benchmark datasets. This algorithm is inspired by the foraging behaviour of honey bees, which has been used to solve numerical optimisation problems [45]. The ABC [186] algorithm was compared with nine other clustering methods, including PSO [187]. The experimental results showed that ABC [186] was the best-performing algorithm over others.

In 2018, Kapoor et al. proposed an automatic clustering technique using the GWO for satellite image segmentation [48]. The main objective of the work was to demonstrate how the infrastructure and urbanisation around New Delhi are expanding while the amount of greenery is declining. The performance of this algorithm was assessed by the $DB$-index [116], inter-cluster distance and intra-cluster distance [48]. The proposed algorithm was compared with three other well-known algorithms, viz., GA [184], DE [183] and PSO [188]. The experimental results proved the efficiency of the proposed algorithm.

In 2018, Pacheco et al. [189] introduced an automatic clustering algorithm called Anthill which was motivated by the collaborative intelligent behaviour of ants. The proposed algorithm addressed the problem of an automatic grouping which is admittedly considered an NP-difficult problem. In order to quickly derive the solutions, it uses an adaptive strategy. The quality of the clustering and effectiveness of the algorithm was measured with the help of two different criteria: the $SI$ index and visual inspection. The outcome of the experiments indicated that the proposed algorithm was more effective than other compared algorithms.

An automatic clustering algorithm known as ASOSCA was proposed by Elaziz et al. in 2019 [190]. Its foundation lies in a hybridised version of the Atom Search Optimisation (ASO) [191] technique along with the Sine Cosine Algorithm (SCA) [192]. ASOSCA used SCA as a local search operator to enhance the performance of ASO. The proposed algorithm used different cluster validity indices, viz., $DI$ [117], $SI$ [119], $DB$ [116] and $CH$ indices [118] to validate the goodness of clustering. In this work, sixteen clustering datasets were used for all experiments. The experimental results showed that the ASOSCA is superior to comparable hybrid metaheuristics.

A hybrid metaheuristic algorithm known as the Firefly Particle Swarm Optimisation (FAPSO) [44] algorithm for the automatic clustering of real-life datasets was proposed by Agbaje et al. in 2019. The merits of the FA [44] and PSO [43] algorithms were incorporated into FAPSO to improve its performance. In this paper, the proposed algorithm was compared with six different algorithms, viz., Automatic Clustering DE (ACDE) [183], Genetic Clustering With an unknown Number of Clusters K (GCUK) [184], Dynamic Clustering Particle Swarm Optimisation (DCPSO) [185], Classical DE [42], Classical FA [44] and Classical PSO [43]. The $CS$-measure [123] and the $DB$-index [116] were used as the cluster validity indices. As per the experimental results, it can be claimed that the FAPSO [44] algorithm performed better than all other participating algorithms.

The ABC [186] algorithm suffers from balancing exploration and exploitation. In 2021, Alrosan et al. proposed the mean artificial bee colony (MeanABC) optimisation algorithm [193] referred to as AC-MeanABC for the purpose of automatic clustering. It was designed to enhance the performance of the ABC [186] algorithm by effectively exploring the search space. The algorithm also possesses the capability to explore the entire search space ranging from positive to negative directions to determine the exact number of clusters. The balance between exploration and exploitation was efficiently addressed. The effectiveness of this algorithm was evaluated by experimenting on eleven benchmark real-life datasets, viz., Iris, Ecoli, Wisconsin, Wine, Dermatology, Glass, Aggregation, R15, D31, Libras movement, and Wholesaler Customers, and a set of natural images from the Berkeley1 segmentation dataset, viz., the Lena, Jet plane, MorroBay, Mandril and Pepper images [194,195]. The outcome indicated that the proposed algorithm outperformed competitive algorithms in the same domain.

A detailed study of the contributions made in the field of single-objective metaheuristic approaches to automatic clustering is presented in

Table 4. Single-objective metaheuristic approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[97]	This study introduces the CLUSTERING algorithm to automatically identify the exact number of clusters and to also simultaneously classify the objects into these clusters (Tseng et al., 2001).	This work proposes a genetic clustering algorithm in which, initially, the single-linkage algorithm is employed to decrease the size of the large dataset. After that, a heuristic strategy is used to select the appropriate clustering.	Spectral feature vectors derived from the TIMIT database were used for this study.	Merits: 1. Almost all types of data can be effectively clustered by CLUSTERING. Demerits: 1. A good clustering result is only achieved for some specified settings of parameters.
[177]	This study presents two new PSO-based approaches for clustering data vectors (Merwe et al., 2003).	A standard gbest PSO and a hybrid approach were used in which the swarm individuals are seeded by the result of the K-means algorithm.	Two artificial classification problems and four publicly available datasets, viz., Iris Plants Database, Wine, Breast Cancer and Automotives were used for experimental purposes.	Merits: 1. It is successful with respect to faster convergence to reduce quantisation errors and provides higher inter-cluster distances and lower intra-cluster distances. Demerits: 1. For early convergence, it gets stuck in local optima.
[178]	This study demonstrates a GCA to automatically recognise the correct number of clusters using a two-stage split-and-merge strategy (Garai et al., 2004).	GCA uses two algorithms, viz., the CDA and the HCMA.	One real-life and nine artificial datasets were used for this study.	Merits: 1. It provides simple codes for implementation. 2. It shows quite encouraging results compared with other performing algorithms. Demerits: 1. Flexibility is decreased due to the fixed values of crossover and mutation operators.
[183]	This study presents an improved differential evolution algorithm for automatically clustering real-life datasets (Das et al., 2008).	An improved version of the DE algorithm was implemented in this study.	The experimental datasets include the Iris Plants Database, Glass, Wisconsin Breast Cancer Dataset, Wine and Vowel Dataset. This algorithm was also used to segment five 256 × 256 grey-scale images.	Merits: 1. It is easy to implement. 2. It proves to be superior to other competitive algorithms. Demerits: 1. It may not outperform DCPSO or GCUK for every dataset.
[48]	This paper presents an automatic clustering technique referred to as GWO for satellite image segmentation (Kapoor et al., 2018).	The proposed work is based on the Grey Wolf Optimisation algorithm.	The dataset comprises two satellite images of New Delhi.	Merits: 1. It has good convergence speed. 2. It can avoid local optima. Demerits: 1. It is unable to explore the entire search space.

and

Table 5. Single-objective metaheuristic approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[189]	This paper provides an automatic clustering algorithm referred to as Anthill, which is influenced by the collaborative intelligent behaviour of ants (Pacheco et al., 2018).	It is based on the Ant Colony Optimisation (ACO) algorithm. In Anthill, the solution is represented by a set of solutions produced by the entire colony, formed from the partial digraphs and obtained by acquiring the highly connected components.	The experimental datasets include the Wine Dataset, Iris Dataset, Breast Cancer Wisconsin (Original) Dataset, Pima Indians Diabetes Dataset and Haberman’s Survival Dataset from the UCI machine learning database.	Merits: 1. It uses an iterated racing parameter calibrator for automatically configuring the algorithm. Demerits: 1. It has low convergence speed.
[190]	This study presents an automatic clustering algorithm known as ASOSCA to identify the exact number of centroids along with their positions on the run (Elaziz et al., 2019).	It uses the hybridisation of the ASO and the SCA.	Sixteen clustering datasets were used for all the experiments.	Merits: 1. It can achieve global optima. Demerits: 1. It is not suitable for all types of datasets.
[44]	This study introduces a hybrid metaheuristic algorithm, FAPSO algorithm, for the automatic clustering of real-life datasets (Agbaje et al., 2019).	FAPSO incorporates the basic features of the FA algorithm and PSO algorithms.	Twelve benchmark datasets have been taken from the UCI machine learning data repository of the University of California for this study.	Merits: 1. It can reach the global optima. 2. FAPSO performs significantly better than other state-of-the-art clustering algorithms. Demerits: 1. Convergence speed is low.
[193]	This paper proposes an automatic clustering algorithm referred to as AC-MeanABC, which incorporates an improved exploration process of the ABC algorithm (Alrosan et al., 2021).	The unsupervised data clustering method, AC-MeanABC, uses the MeanABC capability of balancing between exploration and exploitation and its capacity to explore the positive and negative directions in search space to determine the optimal result.	Eleven benchmark real-life datasets and natural images from the Berkeley1 segmentation dataset were considered for the experiments.	Merits: 1. It can explore and exploit the search space in both positive and negative directions. Demerits: 1. It has a lower convergence speed.

. The listed algorithms dating between 2001 and 2021 were compared based on the aim of the concerned works, used mechanisms, data specifications, merits and demerits. All the listed algorithms significantly outperform their competing algorithms.

6.2. Multi-Objective Approaches

In a multi-objective optimisation problem [163,164,165,166], the decision variable vector ${\overline{x}}^{*}={\left[x_1^{*},x_2^{*},\dots ,x_n^{*}\right]}^T$ generally optimises M number of objectives simultaneously by satisfying m inequality and n equality constraints as follows.

$$g_i\left(\overline{x}\right)\ge 0,i=1,2,\dots ,m$$

(41)

and

$$h_i\left(\overline{x}\right)\ge 0,i=1,2,\dots ,n$$

(42)

where the optimisation vector is given by

$$f\left(\overline{x}\right)={\left[f_1\left(\overline{x}\right),f_2\left(\overline{x}\right),\dots ,f_M\left(\overline{x}\right)\right]}^T$$

(43)

while considering a maximisation problem, a solution $\overline{x_j}$ is said to be dominated by a solution $\overline{x_i}$ if the following criteria are met.

$$\forall k\in 1,2,\dots ,M,f_k\left(\overline{x_i}\right)\ge f_k\left(\overline{x_j}\right)$$

(44)

and

$$\exists k\in 1,2,\dots ,M,s.t.f_k\left(\overline{x_i}\right)>f_k\left(\overline{x_j}\right)$$

(45)

The solutions that are not dominated by any member of the set of solutions comprise the non-dominated set of solutions. This non-dominated set of solutions is referred to as the Pareto optimal front.

This section presents a few metaheuristic algorithms based on the multi-objective optimisation framework for automatic clustering.

In 2009, Suresh et al. [196] presented a comparison between four multi-objective variants of DE [197,198,199,200,201,202]—viz., the Multi-Objective DE (MODE) [197], the Pareto DE (PDE) [198,200], DE for Multi-objective Optimisation (DEMO) [199], and the Non-Dominated Sorting DE (NSDE)—with Non-Dominated Sorting Genetic Algorithm (NSGA-II) [201] and the Multi-Objective Clustering with an Unknown Number of Clusters K (MOCK) [202]. All the experiments were conducted on six artificial datasets (Dataset_1 to Dataset_6) and four real-life datasets, viz., Iris, Wine, Breast Cancer and the Yeast Sporulation data with a varying range of complexities [203,204]. After analysing the experimental results, it was found that MODE [196] happened to be the best promising candidate algorithm among others for devising a multi-objective clustering framework for the automatic clustering of artificial and real-life datasets.

In 2009, Kundu et al. [205] proposed the hybrid multi-objective optimisation algorithm, GADE, for solving the automatic fuzzy clustering problem. The proposed algorithm is a hybridisation of GA [201] and DE [197,206,207] algorithms. In this work, two conflicting fuzzy validity indices, viz., $XB$ [107] and fuzzy C-means (FCM) measure ($J_m$) [208], were simultaneously optimised to solve the automatic fuzzy clustering problem. All the experiments were conducted on six artificial datasets (Dataset_1–Dataset_6) and four real-life datasets, viz., Iris, Wine, Breast Cancer and the Yeast Sporulation data [203,204]. The computational results indicated that GADE performed better than two other compared algorithms, viz., NSGA-II [201] and MOCK [202].

In 2013, Saha and Bandyopadhyay [209] proposed an automatic clustering algorithm called GenClustMOO for the automatic clustering of artificial and real-life datasets. GenClustMOO uses a simulated annealing-based multi-objective framework, AMOSA [165], to identify the optimal number of clusters and the appropriate partitioning from datasets with a variety of cluster structures. All the experiments were conducted on nineteen artificial datasets, viz., symmetrically shaped clusters (Sym_5_2, Sym_3_2, Ellip_2_2, Ring_3_2, and Rect_3_2) [210], hyperspherical shaped clusters (Sph_5_2, Sph_3_4, Sph_6_2, Sph_10_2, and Sph_9_2) [184], well-separated clusters of different shapes, sizes and convexities (Pat1, Pat2, Long1, Sizes5, Spiral, Square1, Square4, Twenty and Forty) [211] and seven real-life datasets, viz., Iris, Cancer, Newthyroid, Wine, LiverDisorder, LungCancer and Glass [203,204]. The proposed algorithm, GenClustMOO, was compared with the multi-objective clustering technique, MOCK [197], and the single-objective clustering technique, VGAPS [210]. GenClustMOO was found to be superior to other comparable algorithms. The superiority of GenClustMOO was also established by performing the statistical superiority tests, viz., Friedman test [212] and Nemenyi’s test [213].

In 2015, Abubaker et al. [214] proposed an automatic clustering algorithm referred to as the Multi-Objective Particle Swarm Optimisation and Simulated Annealing (MOPSOSA). MOPSOSA is designed by combining the principles of two multi-objective-based algorithms, viz. the multi-objective-based particle swarm optimisation (MPSO) [215] and the multi-objective simulated annealing (MOSA) [216]. In MOPSOSA, three different cluster validity indices, viz., $DB$-index [116], Sym-index [210] and Conn-index [110] were simultaneously used to optimise the obtained results. Experiments were conducted on fourteen artificial and five real-life datasets [217]. The proposed algorithm successfully identified the number of clusters from various overlapping and non-convex datasets with different shapes. The experimental results proved its superiority in all respects while comparing it to other multi-objective and single-objective algorithms.

In 2018, Paul and Shill [218] proposed two multi-objective automatic clustering methods, viz., Fuzzy Relational Clustering with NSGA-II (FRC-NSGA) and Improved FRC with NSGA-II (IFRC-NSGA). FRC-NSGA incorporates the features of FRC [219] and NSGA-II [166]. This method can perform fuzzy clustering without knowing the cluster numbers beforehand. In FRC-NSGA, NSGA-II was used to simultaneously optimise the cluster validity indices of separation and cohesion, while FRC was employed to deal with the overlapping characteristics of clusters. IFRC-NSGA provides an enhanced version of FRC-NSGA by reducing the randomness of the initial membership values of FRC-NSGA. In this paper, the proposed methods were compared with three other existing multi-objective clustering methods, viz., VAMOSA [166], MOCK [197] and FCM-NSGA [220], and with a single-objective clustering method VGAPS [221]. All the experiments were conducted on two types of datasets: gene expression and non-gene expression data. The gene expression data included four microarray datasets, viz., Prostate Tumor [222], Leukemia [221], Colon Cancer [223] and the DLBCL datasets [224]. The Non-Gene Expression data included synthetic datasets, viz., AD_5_2 [224], AD_10_2 [223], Square-1, Square-4 and Long-1 [197], and real-life datasets, viz., Iris, Glass, Wine and Liver Disorders [225]. In contrast to the previously existing methods, the proposed methods efficiently identified well-separated, hyperspherical, non-compact and overlapping clusters. For the Colon dataset, Prostate Tumor dataset, Leukemia dataset and Lymphoma dataset, IFRC-NSGA achieved $90.0\%$, $94.11\%$, $94.44\%$ and $97.0\%$ accuracy. In contrast, FRC-NSGA showed accuracies of $90.0\%$, $93.14\%$, $94.44\%$ and $97.0\%$, respectively, for the same dataset. Based on the experimental findings, the supremacy of the IFRC-NSGA algorithm over others was established.

In 2019, Dutta et al. [226] proposed a multi-objective-based automatic clustering algorithm called MOGA-KP for automatically determining the exact number of clusters from some real-life benchmark datasets having numeric or categorical features. This work is based on the working principle of a multi-objective Genetic Algorithm (MOGA) [227] in which, at every generation of MOGA, a single iteration of K-prototypes [228] is performed to conduct a local search. The performance of the proposed work was compared with seven algorithms, viz., K-Prototypes (KPs) [228], fuzzy C-means (FCMs) [229], Mean Shift (MS) [230], Hierarchical Clustering [231], Density-Based Spatial Clustering of Applications with Noise (DBSCAN) [30], Self-Organising Map (SOM) [232] and the Single-Objective Genetic Algorithm with K-Means (SGA-KP) [233]. In this work, the performance of the proposed algorithm was measured by experimenting on twenty-five benchmark datasets taken from the University of California at Irvine (UCI) machine learning repository [234]. The MOGA-based automatic data clustering algorithm MOGA-KP is regarded as the first to handle both continuous and categorical information. Two statistical tests, viz., the Friedman’s test [212] and a non-parametric equivalent of the repeated-measures ANOVA test [235], proved the superiority of the proposed algorithm over others.

In 2021, Qu et al. [236,237] proposed an automatic clustering algorithm based on MOGA referred to as NSGAII-GR. NSGAII-GR incorporates the features of the well-known Non-Dominated Sorting Genetic Algorithm-II (NSGAII) [166] along with a gene rearrangement technique. Two internal cluster validity indices, viz., the sum of generalised sample variance and $CH$ index [118], were used in this paper to simultaneously optimise the results. The well-known $DB$-index determines the best result from the Pareto optimal front [116]. Finally, the $SI$ coefficient [119] was used to judge the optimal result. Experiments were conducted on five two-dimensional artificial datasets, viz., T9_1, Tb_1 [197], Square1, Square4 and Long1 [238], five real-world datasets, viz., Iris, Wine, NewThyroid, WBC and WDBC from the UCI machine learning dataset [225], and ten datasets 10d-4c-No.(0–9) having the characteristics of 10 dimensions and 4 clusters, and ten datasets 10d-10c-No.(0–9) having the characteristics of 10 dimensions and 10 clusters [239]. This work presents a comparison between the proposed algorithm and the Fuzzy C-Means Non-Dominated Sorting Genetic Algorithm II (FCM-NSGA-II) [220] and the MOCK [197]. The experimental results indicate the superiority of the multi-objective optimisation method over all other single-objective optimisation methods while using the same objective function. The remarkable advantage offered by the algorithm is that the gene rearrangement processes and the inter-cluster merging do not increase the time complexity.

A detailed study of the contributions made in the field of multi-objective metaheuristic approaches to automatic clustering is presented in

Table 6. Multi-objective metaheuristic approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[196]	This study presents a comparison between four multi-objective variants of DE for the automatic clustering of artificial and real-life datasets (Suresh et al., 2009).	The comparable algorithms include the MODE, the PDE and DE for Multi-Objective Optimisation (DEMO) and the NSDE.	In this study, six artificial and four real-life datasets were considered.	Merits: 1. It can handle multi-objective optimisation problems. Demerits: 1. Time and space complexity are higher.
[205]	This paper presents the hybrid multi-objective optimisation algorithm, GADE, for solving the automatic fuzzy clustering problem (Kundu et al., 2009).	It is a hybridisation of GA and DE algorithms.	Six artificial and four real-life datasets have been used.	Merits: 1. It is based on the multi-objective framework. Demerits: 1. Time and space complexity are higher.
[209]	This work presents an automatic clustering algorithm referred to as GenClustMOO for the automatic clustering of artificial and real-life datasets (Saha et al., 2013).	GenClustMOO uses a simulated annealing-based multi-objective framework, AMOSA, to identify the optimal number of clusters and the appropriate partitioning from datasets with various cluster structures.	All the experiments were conducted on nineteen artificial and seven real-life datasets.	Merits: 1. It is based on a multi-objective framework and generates a set of Pareto optimal fronts. Demerits: 1. Convergence rate is lower.
[214]	This study introduces an automatic clustering algorithm referred to as MOPSOSA for the automatic identification of the exact number of clusters in a dataset (Abubaker et al., 2015).	It combines the features of MPSO and the MOSA.	During the experiments, with fourteen artificial and five real-life datasets being considered.	Merits: 1. It can solve the multi-objective optimisation problem. 2. MOPSOSA outperforms all its competitors. Demerits: 1. Suffers from a low convergence rate.
[218]	This paper presents two multi-objective automatic clustering algorithms, viz., FRC-NSGA and IFRC-NSGA (Paul et al., 2018).	The proposed FRC-NSGA algorithm incorporates the features of the well-known FRC and NSGA-II algorithms. The proposed algorithm IFRC-NSGA is designed to improve the performance of FRC-NSGA.	Several Gene Expression data and Non-Gene Expression data were considered to conduct the experiments.	Merits: 1. Multi-objective framework is used to handle real-life problems. Demerits: 1. Space requirement is higher.

and

Table 7. Multi-objective metaheuristic approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[226]	This paper introduces a multi-objective-based automatic clustering algorithm referred to as MOGA-KP (Dutta et al., 2019).	This work combines the features of MOGA and K-Prototypes (KPs) to automatically identify the exact number of clusters from some real-life benchmark datasets with multiple numeric or categorical features.	Twenty-five benchmark datasets from the UCI machine learning repository were used for experimental purposes.	Merits: 1. It can provide a set of Pareto optimal solutions. 2. It can handle different features, viz., continuous and categorical and missing feature values. 3. It can also deal with the missing features. Demerits: 1. It does not give priority to the features in clustering.
[237]	This study demonstrates a multi-objective-based automatic clustering algorithm referred to as NSGAII-GR for the automatic clustering of different types of real-life and artificial datasets (Qu et al., 2021).	It is based on the principle of the well-known Non-Dominated Sorting Genetic Algorithm-II (NSGAII) with a gene rearrangement technique.	The experiments have been conducted on five two-dimensional artificial datasets, five real-world datasets and twenty ten-dimensional datasets with various clusters.	Merits: 1. The remarkable advantage offered by the algorithm is that it prevents the time complexity from increasing while conducting the gene rearrangement process and inter-cluster merging process. Demerits: 1. It cannot properly handle uneven overlapping datasets.

. The listed algorithms dating between 2001 and 2021 are compared based on the aim of the concerned works, used mechanisms, data specifications, merits and demerits. All the listed algorithms significantly outperform their competing algorithms.

7. Quantum-Inspired Metaheuristic Approaches for Automatic Clustering

In 1995, Narayanan and Moore introduced a new concept following the basic principles of quantum mechanics to obtain more efficient evolutionary methods [240]. Quantum computing principles are incorporated in these quantum-inspired metaheuristics with the backbone of several metaheuristics to enhance the performance of the existing ones. The first two pioneer works based on the concepts and principles of quantum computing are the Genetic Quantum Algorithm (GQA) [241] and Quantum-Inspired Evolutionary Algorithm (QEA) [242]. These algorithms use the concept of quantum bits and the superposition states. After that, several quantum-inspired metaheuristic algorithms have been developed to date to address different categories of optimisation issues, viz., Quantum-Inspired Particle Swarm Optimisation (QIPSO) [243], Quantum-Inspired Firefly Algorithm with PSO [244] and Quantum-Inspired Acromyremx Evolutionary Algorithm [245], to name a few.

A brief illustration of some metaheuristic algorithms influenced by quantum mechanisms, which automatically cluster different types of datasets using single- and multi-objective frameworks, is presented in this section.

7.1. Single-Objective Approaches

This section presents a few single-objective quantum-inspired metaheuristic algorithms for addressing the problem of the automatic clustering of datasets.

In 2010, Ramdane et al. proposed the Quantum-Inspired Evolutionary Algorithm for Data Clustering (QEAC) [246]. The proposed algorithm was applied to four synthetic and four real-world datasets. This work explored the applicability of the QEA to data clustering [184]. QEAC was compared with the GA designed by Maulik and Bandyopadhyay [247] for data clustering and QEA for gene expression data clustering developed by Zhou et al. [248]. As per the experimental results, the applicability and effectiveness of QEAC were duly established.

In 2014, Dey et al. proposed an automatic clustering algorithm influenced by quantum mechanics for multi-level image thresholding [249]. In this work, the principles of quantum computing were incorporated with the well-known genetic algorithm [41] for automatically identifying the optimal number of clusters from an image dataset. This work used the $CS$-measure [123] as a fitness function. The proposed algorithm was compared with its classical counterparts. The supremacy of the proposed algorithm over its classical equivalent was proven by several metrics, viz., standard deviation and standard error.

In 2017, Dey et al. proposed a quantum-inspired automatic clustering algorithm for the automatic clustering of grey-scale images [250]. This work presented the Quantum-Inspired Particle Swarm Optimisation (QIPSO) algorithm and the Quantum-Inspired Differential Evolution (QIDE) algorithm and the comparison with their classical counterparts. These algorithms outperformed two other state-of-the-art classical clustering algorithms both computationally and statistically. According to the experimental results, the QIPSO algorithm was found to excel over all other competitive algorithms in performance.

In 2018, Dey et al. proposed a quantum-inspired automatic clustering algorithm for grey-scale images [251,252]. This work incorporated the quantum computing principle with the single-solution-based Simulated Annealing algorithm. The proposed algorithm was compared with its classical equivalent. The supremacy of the proposed algorithm over its classical equivalent was established with respect to mean fitness value, standard deviation, standard error and optimum computational time.

In 2018, Dey et al. proposed an automatic clustering algorithm called the Quantum-Inspired Automatic Clustering Technique using Ant Colony Optimisation algorithm [253]. This technique was developed to determine the appropriate number of grey-scale image clusters. The superiority of the proposed technique was established based on the optimal number of clusters, computed fitness value, computational time, the mean, standard deviation of the fitness value, standard errors and an unpaired two-tailed t-test [254].

In 2018, the Quantum Spider Monkey Optimisation (QSMO) algorithm was proposed by Bhattacharyya et al. for the automatic clustering of grey-scale images [255]. The efficiency of this proposed algorithm inspired the researchers to develop Quantum-Inspired Ageist Spider Monkey Optimisation (QIASMO) [256] algorithm for the same purpose. This work explored the QIPSO algorithm [256], Quantum-Inspired Spider Monkey Optimisation algorithm [256] and QIASMO algorithm [256] for the automatic clustering of grey-scale images. The quantum-inspired algorithms were compared with their classical counterparts. In all cases, the quantum-inspired algorithms outperformed the state-of-the-art algorithms. QIASMO [256] was found to be the most effective algorithm.

In 2019, the Quantum-Inspired BAT (QIBAT) algorithm was proposed by Dey et al. to solve the problem of automatic clustering of grey-scale images [257]. After that, this work was extended in 2020 [258] where two quantum-inspired metaheuristic algorithms, viz., QIBA and QIGA, were introduced. In all aspects, the quantum versions of these algorithms were found to be superior to the state-of-the-art algorithms. The computational results showed that QIBA was the best-performing algorithm.

In 2021, Dey et al. proposed a quantum-inspired metaheuristic algorithm for the automatic clustering of colour images [259]. In this paper, the Crow Search Optimisation Algorithm (CSOA) [260] and Intelligent Crow Search Optimisation Algorithm (ICSOA) [261] were used as the underlying metaheuristic algorithms. The experimental results proved that the quantum-inspired algorithms were superior to their corresponding classical alternatives in all aspects. Moreover, among all other algorithms, the quantum-inspired intelligent crow search optimisation algorithm was found to be the best-performing algorithm in terms of performance.

Dutta et al. [262] developed an Automatic Clustering-Based Qutrit version of Particle Swarm Optimisation (AC-QuPSO) in 2021 to automatically cluster hyperspectral images. The space complexity was reduced using the band fusion approach, as it minimised the number of bands present in each image. Shannon entropy [263] was used to choose the minimum number of bands for implementing the modified improved subspace decomposition technique [263]. In this paper, the authors introduced a new concept called qutrit instead of qubits. The proposed work was compared with the classical PSO [43,264] algorithm based on four metrics, viz., peak signal-to-noise ratio (PSNR) [265], Jaccard Index [266], Sørensen–Dice Similarity Index [267] and the computational time. All the experiments were conducted on the Salinas Dataset [268]. All the outcomes of the experiments, along with the statistical superiority test, viz., the unpaired t-test [254] proved the supremacy of the proposed algorithm over its classical alternative. Moreover, greater progress was made in reducing space and time complexity using the concept of qutrit.

A Quantum-Inspired Manta Ray Foraging Optimisation (QIMRFO) algorithm for the automatic clustering of colour images [269] was proposed by Dey et al. in 2022. This work presented a comparison between the proposed algorithm and the classical version of the Manta Ray Foraging Optimisation (MRFO) algorithm [270] as well as with the well-known GA [41]. The PBM index [122] was used as an objective function to demonstrate the goodness of the clustering results. The computational results indicated that the QIMRFO quantitatively and qualitatively outperformed other comparative algorithms.

In 2022, Dey et al. proposed two quantum-inspired metaheuristic algorithms, viz., QIPSO algorithm and the Quantum-Inspired Enhanced Particle Swarm Optimisation (QIEPSO) algorithm, for the automatic clustering of colour images [271]. In this work, the proposed algorithms were compared with their corresponding classical counterparts as well as three different well-known classical algorithms, viz., ABC [272], DE [206] and Covariance Matrix Adaption Evolution Strategies (CMA-ES) [273]. In this work, the goodness of the clustering was measured using three different cluster validity indices, viz., $PBM$ [122], $CSM$ [123] and $DI$ [117]. During the experiments, ten Berkeley colour images [274] and ten real-life colour images [275] with different sizes were used. According to the experimental results, QIEPSO proved to be a potential candidate for the automatic clustering of colour images.

A detailed study of the contributions made in the field of single-objective quantum-inspired metaheuristic approaches to automatic clustering is presented in

Table 8. Single-objective quantum-inspired metaheuristic approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[249]	This study introduces an automatic clustering algorithm referred to as QIAGA for multi-level image thresholding which is capable of automatically identifying the optimal number of clusters from an image dataset (Dey et al., 2014).	This work incorporates the quantum computing mechanism with the well-known GA.	The test images include four real-life grey-scale images.	Merits: 1. It has a good convergence rate. 2. Experimental results statistically prove the efficiency and effectiveness of the proposed algorithm. Demerits: 1. Time complexity is higher.
[252]	This study presents a quantum-inspired automatic clustering algorithm for grey-scale images (Dey et al., 2018).	It incorporates the quantum computing principles with the single solution-based Simulated Annealing algorithm.	For experimental purposes, four real-life grey-scale images and four Berkeley images of different dimensions were used.	Merits: 1. It has a higher convergence rate. 2. The supremacy of the proposed algorithm over its classical equivalent has been established with respect to some metrics. Demerits: 1. It suffers from premature convergence.
[253]	This study introduces an automatic clustering algorithm referred to as the Quantum-Inspired Automatic Clustering Technique Using the Ant Colony Optimisation algorithm for the automatic identification of the optimal number of clusters in a grey-scale image (Dey et al., 2018).	The Ant Colony Optimisation algorithm was chosen as the underlying algorithm to be incorporated in a quantum computing framework. The Xie–Beni cluster validity measure was used as the objective function for this study.	All the experiments were conducted on four real-life grey-scale images.	Merits: 1. The proposed technique is found to be superior to its classical counterpart with regard to several factors such as accuracy, stability, computational speed and standard errors. Demerits: 1. It does not always attain global optimum.
[258]	This study introduces two quantum-inspired metaheuristic algorithms, viz., QIBA and QIGA, for the automatic clustering of grey-scale images (Dey et al., 2019).	Quantum computing principles are incorporated in this work with the classical Bat optimisation algorithm and GA. $DB$-index was used to validate the clustering process.	All the experiments were performed on four Berkeley images and two real-life grey-scale images.	Merits: 1. QIBA can efficiently balance exploration and exploitation in the search space. 2. Computational results indicate that QIBA outperforms others. Demerits: 1. The time complexity is higher.
[256]	This study presents three automatic clustering algorithms for grey-scale images (Dey et al., 2020).	This work includes the QIPSO, Quantum-Inspired Spider Monkey Optimisation algorithm (QISMO) and QIASMO algorithm (QIASMO).	All the experiments were conducted on five Berkeley images, five real-life images and four mathematical benchmark functions.	Merits: 1. QIASMO has better convergence speed than the others. 2. The quantum-inspired algorithms outperform state-of-the-art algorithms in all cases. 3. QIASMO has been regarded as being the most effective algorithm out of these three. Demerits:1. QIPSO may get stuck in the local optima.

and

Table 9. Single-objective quantum-inspired metaheuristic approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[259]	This study presents two quantum-inspired metaheuristic algorithms referred to as the Quantum-Inspired Crow Search Optimisation Algorithm (QICSOA) and Quantum-Inspired Intelligent Crow Search Optimisation Algorithm (QIICSOA) for automatically clustering colour images (Dey et al., 2021).	For this study, the underlying metaheuristic algorithms include the CSOA and ICSOA. This work uses four cluster validity indices, viz., $PBM$-index, I-index, Silhouette (SIL) index and $CS$-Measure (CSM).	Fifteen Berkeley colour images and five publicly available real-life colour images with varied dimensions were used for experimental purposes.	Merits: 1. All of them have good convergence speed. 2. QIICSOA is found to be the most promising algorithm in terms of performance. Demerits: 1. Time complexity is higher.
[262]	This study introduces an automatic clustering algorithm for hyper-spectral images, which is referred to as AC-QuPSO (Dutta et al., 2021).	A new concept called qutrit was introduced to reduce space and time complexity.	All the experiments were performed on the Salinas Dataset.	Merits: 1. It has good convergence speed. 2. The supremacy of AC-QuPSO over its conventional alternatives was realised by performing the unpaired t-test. Demerits: 1. It has difficulties in the placement of the controller.
[269]	This study presents the QIMRFO algorithm for clustering of colour images on the run (Dey et al., 2022).	Quantum computing framework was combined with the classical version of the MRFO algorithm.	Four Berkeley colour images and four publicly available real-life colour images were used for experimental purposes.	Merits: 1. It has a good convergence rate. 2. It is capable of efficiently exploring and exploiting the search space. 3. Experimental results indicate that the QIMRFO quantitatively and qualitatively outperforms other comparative algorithms. Demerits: 1. In QIMRFO, the space requirement is high.
[271]	This paper presents two algorithms, viz., QIPSO algorithm and QIEPSO algorithm, for the automatic clustering of colour images (Dey et al., 2022).	Quasi quantum operations were performed to achieve the goal.	All the experiments were conducted on ten Berkeley images and ten real-life colour images.	Merits: 1. QIEPSO has good convergence speed. 2. The QIEPSO algorithm has enough potential to be a viable candidate for the automatic clustering of colour images. Demerits: 1. QIPSO does not always find an optimal solution.

. The listed algorithms dating between 2001 and 2021 are compared based on the aim of the concerned works, used mechanisms, data specifications, merits and demerits. All the listed algorithms significantly outperform their competing algorithms.

7.2. Multi-Objective Approaches

Nowadays, researchers have intended to achieve multi-objective optimisation based on quantum-inspired frameworks to solve several types of optimisation problems, specifically clustering problems [276]. In quantum-inspired multi-objective optimisation techniques, the superposition of quantum states generates the search space, thereby providing a good population diversity and increasing the search capabilities. Examples of a few quantum-inspired multi-objective optimisation techniques include the Quantum-Inspired Multi-Objective Evolutionary Clustering (QMEC) algorithm [276], a self-organising PSO algorithm based on the principle of the quantum computing mechanism to handle multi-modal multi-objective optimisation problems (MMO_SO_QPSO) [277], a new quantum-based multi-objective simulated annealing technique for bi-level thresholding [278], and an optimal VSM model based on a multi-objective Quantum-Inspired Genetic Algorithm to retrieve web information [279], to name a few. This section presents a few quantum-inspired metaheuristic algorithms based on the multi-objective optimisation framework for automatic clustering.

In 2019, the Automatic Clustering Using Multi-Objective Emperor Penguin Optimiser (ACMOEPO) algorithm was developed by Kumar et al. [280] to automatically determine the optimal number of clusters from real-life datasets. Furthermore, this algorithm was also applied to four colour images, viz., Mandrill, Airplane, Peppers and House, for segmentation purposes. Two cluster validity indices were used to design a novel fitness function to maintain the balance between inter-cluster and intra-cluster distances. The superiority of this algorithm was established by comparing it with four other multi-objective clustering algorithms, viz., GenClustMOO [209], Multi-Objective Invasive Weed Optimisation algorithm for clustering (MOIWO) [281], automatic clustering using MOPSOSA [214] and an evolutionary approach to MOCK [197]. The performance of the participating algorithms was measured with respect to the obtained number of clusters, mean and standard deviation. Finally, the superiority of the algorithm was established by performing the unpaired t-test [254] on all the participating algorithms.

In 2022, the Quantum-Inspired Multi-Objective NSGA-II algorithm for the Automatic Clustering of Grey-Scale Images (QIMONSGA-II) was proposed by Dey et al. [282] to automatically determine the exact number of clusters in a grey-scale image. This work compared the proposed algorithm and the well-known Non-Dominated Sorting Genetic Algorithm II (NSGA-II) [166,283]. QIMONSGA-II performs quasi-quantum computation to optimise two different objectives, viz., $CS$-Measure (CSM) [123] and $DB$-index [116] simultaneously. All the experiments were conducted over six Berkeley [274] grey-scale images of different sizes. In most cases, the experimental outcome achieved better results for the proposed QIMONSGA-II [282] algorithm. Finally, the superiority of the proposed algorithm was proved using the Minkowski score [284] and $SI$ index [119].

A detailed study of the contributions made in the field of multi-objective quantum-inspired metaheuristic approaches to automatic clustering is presented in

Table 10. Multi-objective quantum-inspired metaheuristic approaches to automatic clustering.

Ref.	Aim of the Work	Mechanism Used	Data Specifications	Merits and Demerits
[280]	This paper presents the Automatic Clustering using Multi-Objective Emperor Penguin Optimiser (ACMOEPO) algorithm to automatically determine the optimal number of clusters from real-life datasets (Kumar et al., 2019).	To maintain the balance between inter-cluster and intra-cluster distances, a unique fitness function is suggested, which comprises multiple cluster validity indices.	The test dataset includes nine real-life benchmark datasets.	Merits: 1. It can handle very large datasets. 2. This type of algorithm is helpful in data mining applications. 3. The superiority of ACMOEPO was proved by performing the unpaired t-test among all the participating algorithms. Demerits: 1. Space requirement is higher.
[282]	This paper introduces the QIMONSGA-II for the automatic clustering of grey-scale images (Dey et al., 2022).	QIMONSGA-II performs quasi-quantum computation and simultaneously optimises two objectives, viz., the $CS$-Measure (CSM) and $DB$-index.	All the experiments were conducted over six Berkeley grey-scale images of varied dimensions.	Merits: 1. It can identify optimal results in a multi-objective environment. 2. The superiority of QIMONSGA-II was proven by utilising the Minkowski score and $SI$ Demerits: 1. Space requirement is higher.

. The listed algorithms dating between 2001 and 2021 are compared based on the aim of the concerned works, used mechanisms, data specifications, merits and demerits. All the listed algorithms significantly outperform their competing algorithms.

8. Conclusions

This paper presents an overview of metaheuristic algorithms for automatic clustering. A brief overview of the automatic clustering process is presented. The basics of the quantum computing paradigm have also been highlighted for the sake of self-sufficiency. Different state-of-the-art nature-inspired metaheuristic and automatic clustering algorithms based on the quantum-inspired framework were reviewed to identify common inspiring sources, classifications, merits and demerits. The major objective of this study was to present a clear view towards different clustering algorithms and their application areas. From the study, it is quite evident that the quantum-inspired metaheuristics prove to be superior to their classical counterparts when it comes to the automatic clustering of datasets. Moreover, these algorithms seem to be robust, time-efficient and fail-safe compared to their classical counterparts. The focus of this study was limited to providing examples of the most widely used clustering techniques. Further research in this direction would entail higher-level quantum states for designing higher-level quantum-inspired metaheuristics.