A Hybrid Clustering Method Based on the Several Diverse Basic Clustering and Meta-Clustering Aggregation Technique

Abstract

In hybrid clustering, several basic clustering is first generated and then for the clustering aggregation, a function is used in order to create a final clustering that is similar to all the basic clustering as much as possible. The input of this function is all basic clustering and its output is a clustering called clustering agreement. However, this claim is correct if some conditions are met. This study has provided a hybrid clustering method. This study has used the basic k-means clustering method as a basic cluster. Also, this study has increased the diversity of consensus by adopting some measures. Here, the aggregation process of the basic clusters is done by the meta-clustering technique, where the primary clusters are re-clustered to form the final clusters. The proposed hybrid clustering method has the advantages of k-means, its high speed, as well as it does not have its major weaknesses, the inability to detect non-spherical and non-uniform clusters. In the empirical studies, we have evaluated the proposed hybrid clustering method with other up-to-date and robust clustering methods on the different datasets and compared them. According to the simulation results, the proposed hybrid clustering method is stronger than other clustering methods.

Keywords:

• Aggregation techniques
• diversity of clustering
• hybrid clustering
• meta-clustering

1. Introduction

Nowadays, clustering plays an important role in most research fields such as engineering, medicine, biology, and data mining (Sun et al. 2018; Tan et al. 2020). Clustering is one of the fields of unsupervised learning and is an automatic process during which samples are divided into categories whose members are similar to each other, and these categories are called clusters. Therefore, a cluster is a collection of samples in which the samples are similar to each other and are not similar to the samples in other clusters (Wei et al. 2019; Trik, Pour Mozaffari, and Bidgoli 2021). Different criteria can be considered for similarity. For example, the distance criterion can be used for clustering and samples that are closer to each other can be considered as a cluster. This type of clustering is known as distance-based clustering. In simple words, the purpose is to separate groups with similar features and divide them into clusters (Yang et al. 2021; Ma et al. 2021).

Clustering methods take the data and form these groups using some kind of similarity criterion. The results obtained from these clusters/groups can be used on many applications such as image processing, pattern recognition, social network analysis, recommendation engine and information retrieval (Zhao et al. 2019). In the process of machine learning for clustering, a similarity measure based on distance plays a pivotal role in clustering decision (Ghobaei-Arani and Shahidinejad 2021). In all kinds of clustering methods, two main objectives should be considered in order to obtain the least error: one, the similarity between one data point with another point and the second, the distinction of those similar data points with other points (Forouzandeh et al. 2021; Berahmand et al. 2021). The basis for such divisions begins with our ability to scale large datasets, and this is a starting point. Another challenge in clustering is the different types of features in the data. Data can be structured, unstructured, hierarchical, and continuous (Ghobaei-Arani 2021; Shahidinejad, Ghobaei-Arani, and Esmaeili 2020). Also, it is evident that the data is not dimensionally limited and is multidimensional in nature.

Basically, a suitable distance measure can be very effective in clustering. However, the appearance of the clusters can be geometric, so this challenge must also be considered. On the other hand, the results of the clustering method should be understandable in order to solve business problems. Therefore, scalability, features, dimensions, appearance, noises, and interpretability are the things that clustering methods should consider to solve the problem (Nasiri et al. 2022; Jadidi and Dizadji 2021). In general, performing clustering using different methods have a similar architecture. This is while the differences among the clustering methods include the distance/similarity criteria, initial cluster values and how to form the final clusters. These differences have led to the development of different clustering methods over time. Basically, there are five main classes of clustering methods including Density-based Clustering (DC), Grid-based Clustering (GC), Model-based Clustering (MC), Hierarchical Clustering (HC), and Partitional Clustering (PC), as shown in Figure 1 (Wei, Li, and Zhang 2018).

Figure 1. Taxonomy of clustering methods.

Since most of the basic clustering methods emphasize on specific aspects of the data, they are efficient on specific datasets (Niu et al. 2020; Li, Qian, and Wang 2021). For this reason, there is a need for approaches that can create better results by using the combination of these methods and considering their strengths. Meanwhile, hybrid clustering is a new clustering method that is obtained by combining the results of different clustering methods. Accuracy, correctness, and stability are important characteristics of a hybrid clustering method compared to classical clustering methods (Zheng et al. 2021; Zhu et al. 2021; Tan et al. 2020). In fact, the main purpose of hybrid clustering is to search for better and stronger results, using the combination of information and results obtained from several primary clustering (as partitions). So far, many studies have been done on hybrid clustering. Recent research in this field has shown that data clustering can significantly benefit from the combination of several data parts. In addition, their parallelization power has a natural adaptation to the need of distributed data mining. Hybrid clustering can provide better solutions in terms of robustness, scalability, stability, and flexibility than basic clustering methods (as individual).

Basically, hybrid clustering includes two main steps: (1) producing different results from basic clustering methods and (2) combining the results obtained from basic clustering methods to produce final clusters (Zhu et al. 2021). The first is related to the creation of partitions with dispersion and diversity by different methods, and the second refers to an agreement function to combine the results (Wei et al. 2019). Usually, in the first step of hybrid clustering, a number of primary clusters are created, each of which emphasizes a specific feature of the data. Applying a clustering method on several different parts of the data or using several different clustering methods can cause dispersion and diversity in the partition results (Yang et al. 2021). After the primary partitions are formed, these results are usually combined by using an agreement function. One of the most common methods of combining the results is using the correlation matrix. A hybrid clustering framework is shown in Figure 2, where the results of several basic clustering methods are combined to achieve more stable, scalable, and quality clustering.

Figure 2. Hybrid clustering framework.

Therefore, nowadays instead of addressing the making a strong global clustering method, more attention has been paid to building frameworks that integrate several weak clusters (Zhao et al. 2019; Trik et al. 2022). In this regard, the “hybrid cluster” or “clusters aggregation”, has been provided for improving the strength and quality of the clustering process (Tan et al. 2020). The k-means clustering method, which is one of the flat approaches, is known as a very fast and fairly efficient method (Yang et al. 2021; Ma et al. 2021). This method, as a weak clustering method, is one of the best basic clustering methods for contributing to consensus building in hybrid clustering. This paper addresses the existing problems by presenting valid local cluster theory. Here, the similarity between valid local clusters is estimated by applying an inter-cluster and intra-cluster similarity metric. In the next step of the method, the aggregation process of the basic clusters is done by the meta-clustering technique, where the primary clusters are re-clustered to form the final clusters. Eventually, the output of these clusters is considered along with the average credits to optimize the final agreement. The proposed hybrid clustering method has the advantages of k-means, its high speed, as well as it does not have its major weaknesses.

The main contribution of this paper is as follows:

• The aggregation process of the basic clusters with a new meta-clustering technique.

• Definition of valid local clusters by considering the data around the cluster centers in k-means.

• Generating diverse primary clusters by applying a duplicate strategy on nonappearance data in valid local clusters.

• Perform extensive experiments to demonstrate the efficacy of the proposed clustering method and give credence to our idea.

The rest of the paper is organized as follows. A brief discussion of related works in the literature is provided in Section 2. The formulation of the problem is provided in Section 3. The proposed clustering method is presented in Section 4. Experimental results are demonstrated in Section 5. Finally, Section 6 concludes the paper.

2. Related Works

So far, many studies have been presented by the research community on the development of clustering methods (Jain 2010; Hansen and Mladenović 2001; Zhang, Hsu, and Dayal 2000). The k-means method is one of the popular clustering approaches with many improved versions. For example, H-means solves the empty cluster problem in k-means (Jain 2010; Walid et al. 2021). Problems of k-means such as outliers, sensitive to noise and local optimum are considered by J-means method (Hansen and Mladenović 2001). This method can also solve the problem of degeneracy in k-means. Jiang et al. (2010) proposed K-Harmonic Means (KHM) to solve the primary clustering problem in k-means. KHM has succeeded in obtaining high-quality results by considering the harmonic mean of intervals as the objective function. However, KHM is not suitable for global optimization. In this regard, Swarm Intelligence techniques are being developed to replace KHM. The ACOKHM (Ant Colony Optimization and K-Harmonic Means) method for clustering with a global approach was presented by Bouyer and Hatamlou (2018). Although ACOKHM provides high-quality and accurate results, it has a slow convergence to the global optimum.

Hybrid clustering has become very popular as a technique to improve clustering results. The results of hybrid clustering using basic clustering methods with higher diversity and more quality are far more accurate (Bouyer and Hatamlou 2018). However, obtaining more accurate results by having more diversity in some collections has not yet been proven (Azimi and Fern 2009). Link-based Cluster Ensemble (LCE) was proposed as a hybrid clustering method by Jain (2010). LCE is an improved version of Hybrid Bipartite Graph Formulation (HBGF) in which bipartite graph is used. The authors first create a dense graph for each pair of samples and clusters and then form the final clusters using spectral clustering. Niu et al. (2020) proposed a hybrid clustering method that they developed based on the hybrid of locally reliable cluster solutions. This method is configured based on k-medoids and provides the concept of valid local clusters. Here, weighted undirected graph is used to find relationships between clusters.

Huang, Wang, and Lai (2017) proposed Locally Weighted Meta-Clustering (LWMC) to improve hybrid clustering methods. Here, the Jaccard coefficient is used to calculate the weight of connections between clusters. LWMC uses the normalized cut method to create meta-clusters, where each meta-cluster contains several clusters (Huang et al. 2020). The authors use a weighted voting-based technique to create the final clusters. Consensus clustering by partitioning similarity graph was proposed by Hamidi, Akbari, and Motameni (2019). This method uses graph pruning for clustering, where the number of clusters is automatically estimated. The authors use meta-cluster and majority vote as an aggregation function to create the final clusters. Here, the Jaccard coefficient is used to calculate the similarity. Iterative Combining Clustering Method (ICCM) was proposed by Khedairia and Khadir (2022). ICCM uses an iteratively based technique to analyze data and create primary clusters. Here a voting method is used to create a set of partitions. For this, each sample votes for its own sub-cluster so that samples with higher votes are assigned to the corresponding sub-clusters. In the meantime, the samples that do not get the highest vote are clustered in the next iterations.

The hybrid clustering is still considered as a tool as well as a research field of the theory studied. A review paper is presented by Golalipour et al. (2021) for a variety of these methods. Due to the fact that precision in clustering does not have a straightforward meaning such as classification, an alternative concept is presented for it, which states that a precise clustering is clustering which is most similar to other clusters formed on the given data, in other words, a better clustering means a more stable clustering. For a reason similar to the reason for the suitability of a diverse collection of classifiers for hybrid classification, a set of the clustering is considered as a goof set, if its basic clustering is varied (Bai, Liang, and Cao 2020). In order to generate a diverse clustering consensus, a weak clustering method must be applied to the data several times.

We use the k-means clustering method as a weak cluster for solving this problem (Abapour, Shafiesabet, and Mahboub 2021). Four sub-problems in hybrid clustering are presented as follows: (1) The problem of recognizing relatively correct labels in clustering: Unlike categorization, there is no real information about labels in clustering. (2) The problem of obtaining a variety of clustering that describe the entire data: In hybrid learning, while several poor learners are combined as strong learners, whatever the basic learners more complement each other, the hybrid learner acts better (Rezaeipanah, Nazari, and Ahmadi 2019; Rezaeipanah et al. 2021). That is, any weak clustering will cover the rest of the clustering. Therefore, for this purpose, we need to create several complementary clustering by applying k-means clustering methods. (3) The problem of determining the appropriateness between clusters: Unlike classifications in which each label is exclusively assigned to a category, the labels do not have a single meaning in clustering, and they simply represent that data has the same cluster (Mojarad et al. 2021). The clusters with the same name in two different clustering do not imply any truth. Therefore, before doing anything in hybrid clustering, the label of different clustering should be re-labeled based on correspondence. In addition, even two clusters of the same clustering are likely to signify a real cluster. (4) The problem of combining the results of matched basic clustering: In different clustering, each sample may have different labels. So, we have to determine a final label called an agreement label. In hybrid learning, while several poor learners are combined as a strong learner, whatever the action is more effective, the hybrid learner acts better (Li, Rezaeipanah, and El Din 2022).

3. Problem Formulation

A dataset is defined as a set of data samples that each data sample itself is a numerical vector (or feature vector). The dataset is shown by $X$ and each data sample is shown by $x_i$ and obviously $x_i\in X.$ The $j$-th feature of the $x_i$ data sample is shown by $x_{\mathrm{ij}}.$ The size of each dataset $X$ is shown by $\left|X\right|.$ The number of features of the dataset $X$ is shown by $\left|x_1\right|.$ Let $N$ be the number of samples and $M$ the number of features from a dataset. Let $c$ be the subset of data as clustered/partitioned. When the union of all subsets is equivalent to the original data set and each pair of subsets has no intersection, then each subset can be defined as a cluster. A clustering is shown by $\pi =\left\{{\pi }^1,{\pi }^2,\dots ,{\pi }^c\right\},$ where ${\pi }^i$represents the $i$-th cluster. Obviously, $\bigcup _{i=1}^c{\pi }^i=X$ and $\forall i,j\in \left\{1,2,\dots ,c\right\}:{\pi }^i\cap {\pi }^j=\mathrm{\varnothing }.$ The center of each cluster ${\pi }^i$ is shown by $C^{{\pi }^i},$ and its $j$-th feature is defined as Eq. (1)(1) $$C_j^{{\pi }^i}=\frac{\sum _{k\in {\pi }^i}{x}_{\mathrm{kj}}}{\left|{\pi }^i\right|}$$(1) (1) $$C_j^{{\pi }^i}=\frac{\sum _{k\in {\pi }^i}{x}_{\mathrm{kj}}}{\left|{\pi }^i\right|}$$(1)

A valid sub-cluster from a cluster ${\pi }^i$ is shown by $r_{{\pi }^i}$ and is defined according to Eq. (2)(2) $$r_{{\pi }^i}=\left\{x_k:{\pi }^i|\sqrt{\sum _{j=1}^{\left|x_1\right|}{\left|C_j^{{\pi }^i}-x_{\mathrm{kj}}\right|}^2}\le \gamma \right\}$$(2) (2) $$r_{{\pi }^i}=\left\{x_k:{\pi }^i|\sqrt{\sum _{j=1}^{\left|x_1\right|}{\left|C_j^{{\pi }^i}-x_{\mathrm{kj}}\right|}^2}\le \gamma \right\}$$(2) where $\gamma$ is a threshold parameter. It should be noted that a sub-cluster can be considered as a cluster.

Basically, there are many similarity/distance measures in the literature to define the difference between two clusters. In this paper, we define the similarity metric between the two clusters ${\pi }^i$ and ${\pi }^j,$ which is shown by $\mathit{sim}\left({\pi }^i,{\pi }^j\right),$ and defined as Eq. (3)(3) $$\mathit{sim}\left({\pi }^i,{\pi }^j\right)=\{\begin{array}{cc}\frac{{\pi }^i\cap {\pi }^j}{{\pi }^i\cup {\pi }^j}+\frac{{\bigcup }_{q=1}^9{T}_q\left({\pi }^i,{\pi }^j\right)-\left({\pi }^i\cup {\pi }^j\right)}{\sqrt{\sum _{w=1}^{\left|x_1\right|}{\left|C_w^{{\pi }^i}-C_w^{{\pi }^j}\right|}^2}}& \sqrt{\sum _{w=1}^{\left|x_1\right|}{\left|C_w^{{\pi }^i}-C_w^{{\pi }^j}\right|}^2}\le 4\gamma \\ 0& O\mathit{therwise}\end{array}$$(3) (3) $$\mathit{sim}\left({\pi }^i,{\pi }^j\right)=\{\begin{array}{cc}\frac{{\pi }^i\cap {\pi }^j}{{\pi }^i\cup {\pi }^j}+\frac{{\bigcup }_{q=1}^9{T}_q\left({\pi }^i,{\pi }^j\right)-\left({\pi }^i\cup {\pi }^j\right)}{\sqrt{\sum _{w=1}^{\left|x_1\right|}{\left|C_w^{{\pi }^i}-C_w^{{\pi }^j}\right|}^2}}& \sqrt{\sum _{w=1}^{\left|x_1\right|}{\left|C_w^{{\pi }^i}-C_w^{{\pi }^j}\right|}^2}\le 4\gamma \\ 0& O\mathit{therwise}\end{array}$$(3) where $T_q\left({\pi }^i,{\pi }^j\right)$ is calculated using Eq. (4)(4) $$T_q\left({\pi }^i,{\pi }^j\right)=\left\{x_k:X|\sqrt{\sum _{w=1}^{\left|x_1\right|}{\left|p_{\mathrm{qw}}\left({\pi }^i,{\pi }^j\right)-x_{\mathrm{kw}}\right|}^2}\le \gamma \right\}$$(4) (4) $$T_q\left({\pi }^i,{\pi }^j\right)=\left\{x_k:X|\sqrt{\sum _{w=1}^{\left|x_1\right|}{\left|p_{\mathrm{qw}}\left({\pi }^i,{\pi }^j\right)-x_{\mathrm{kw}}\right|}^2}\le \gamma \right\}$$(4) where $p_q\left({\pi }^i,{\pi }^j\right)$ is a point and $w$-th feature is denied as Eq. (5)(5) $$p_{\mathrm{qw}}\left({\pi }^i,{\pi }^j\right)=\frac{\left(q\right)\times C_w^{{\pi }^i}+\left(10-q\right)\times C_w^{{\pi }^i}}{10}$$(5) (5) $$p_{\mathrm{qw}}\left({\pi }^i,{\pi }^j\right)=\frac{\left(q\right)\times C_w^{{\pi }^i}+\left(10-q\right)\times C_w^{{\pi }^i}}{10}$$(5)

Let $X=\left\{x_1,x_2,\dots ,x_i,\dots ,x_n\right\}$ be a set of $n$ samples of the dataset $X,$ where $x_i=\left[x_1^i,x_2^i,\dots ,x_j^i,\dots ,x_d^i\right]$ is an $i$-th sample with $d$ features. Also, let $\Pi =\left\{{\pi }_1,{\pi }_2,\dots ,{\pi }_k,\dots ,{\pi }_m\right\}$ be a hybrid of $m$ individual clustering method, where ${\pi }_k$ is the $k$-th member of the hybrid. Each ${\pi }_k\in \Pi$ returns a set of clusters ${\pi }_k=\left[c_1^k,c_2^k,\dots c_l^k,\dots ,c_{\left|{\pi }_k\right|}^k\right]$ (as a partition), where $\left|{\pi }_k\right|$ refers to the number of clusters created by ${\pi }_k.$ For each $x_i\in X,$ ${\pi }_k(x_i)$ represents the cluster label belonging to $x_i$ in ${\pi }_k.$ Here, the problem of hybrid clustering is defined as finding a new partition ${\pi }_{\mathrm{*}}=\left[c_1^{\mathrm{*}},c_2^{\mathrm{*}},\dots c_l^{\mathrm{*}},\dots ,c_K^{\mathrm{*}}\right]$ from the consensus results of set $\Pi ,$ where $K$ is the number of final clusters.

A weighting graph corresponding to a consensus of the clustering is shown by $\Pi$ with $G(\Pi )$ and is defined as $G(\Pi )=\left[V(\Pi ),E(\Pi )\right].$ The vertex set of this graph is also the valid subsets of all consensus’s clusters, namely, $V\left(\mathrm{\Pi }\right)=\left\{r_{{\pi }_1^1},\dots ,r_{{\pi }_1^{c_1}},r_{{\pi }_2^1},\dots ,r_{{\pi }_2^{c_2}},\dots r_{{\pi }_B^1},\dots ,r_{{\pi }_B^{c_B}}\right\}.$ The weight of the edges between the vertices of this graph or the cluster-cluster connections is considered as the similarity value, as shown in Eq. (6)(6) $$E\left(v_1,v_2\right)=\mathit{sim}\left(v_j,v_i\right)$$(6) (6) $$E\left(v_1,v_2\right)=\mathit{sim}\left(v_j,v_i\right)$$(6)

Basically, the k-means clustering method is considered as an unsupervised learning method, where it is used to process unlabeled data. The purpose of this clustering is to find the best group in the data and $k$ determines the number of clusters. The data is placed in clusters based on the degree of similarity. In such a way that the data with the most similarity are placed in one group and have the least similarity with other groups. Here, $k$ specifies the number of clusters and means the averaging. Clusters have a number of characteristics. The first feature: all the data in a cluster must be most similar to each other. The second feature: the data in different clusters should have the greatest difference. The time complexity of the k-means method is $O(N.k.I),$ so that $I$ is the number of iterations.

The pseudocode for k-means-based hybrid clustering is shown in Algorithm 1. In this pseudocode, the original dataset is saved as $\mathrm{TX}$ and then an improved version of k-means is called sequentially to find and store the clustering results.

Algorithm 1.

The hybrid clustering method based on k-means method.

01: $\mathrm{\Pi }=\mathrm{\varnothing };$

02: $\mathrm{TX}=X;$

03: For $i$ = 1 to $B$ do

04: ${\pi }_i$ = modified k-means ($\mathrm{TX},$$c_i$);

05: $\mathrm{TX}=\mathrm{TX}-\bigcup _{j=1}^{c_i}{r}_{{\pi }_i^j};$

06: $\Pi =\Pi \cup \left\{{\pi }_i\right\};$

07: End

Since the difference between basic clustering is a prerequisite for the effectiveness of the cluster group, in the following, how to obtain several k-means clustering with different valid local labels will be discussed. For the first time, we define an optimization problem for generating basic clustering as Eqs. (7)(7) $$\begin{array}{c}\min \\ \pi \end{array}\left[z\left(\pi \right)=\sum _{h=1}^N\sum _{i=1}^T{\theta }_h\left(X_i\right)\mathrm{ }⋋\left({\pi }_h\mathrm{ }\right(X_i\left)\right)d\left(X_i\mathrm{ },\mathrm{ }{V}_{\mathrm{\pi h}}\mathrm{ }\left(X_i\right)\right))\right]$$(7) and (8)(8) $$\sum _{h=1}^T{\theta }_h\left(X_i\right)\mathrm{ }{⋋}_h\left(X_i\right)=1\mathrm{ },\mathrm{ }1\le i\le N\mathrm{ }$$(8) (7) $$\begin{array}{c}\min \\ \pi \end{array}\left[z\left(\pi \right)=\sum _{h=1}^N\sum _{i=1}^T{\theta }_h\left(X_i\right)\mathrm{ }⋋\left({\pi }_h\mathrm{ }\right(X_i\left)\right)d\left(X_i\mathrm{ },\mathrm{ }{V}_{\mathrm{\pi h}}\mathrm{ }\left(X_i\right)\right))\right]$$(7) (8) $$\sum _{h=1}^T{\theta }_h\left(X_i\right)\mathrm{ }{⋋}_h\left(X_i\right)=1\mathrm{ },\mathrm{ }1\le i\le N\mathrm{ }$$(8) where ${\theta }_h\left(X_i\right)$ is a Boolean variable that if is equal to 1, $X_i\mathrm{ }$will partly play a role in the production of the basic cluster $h.$ ${\theta }_h\left(X_i\right)\mathrm{ }$ is provided to control this issue that how many times do each sample play.

Here, constraint is required to each of the samples is applied only once simultaneously to produce basic clustering that is provided by cluster centers in clustering. The purpose of minimizing the objective function $Z$ is to create cluster centers in each basic cluster to indicate that samples are in the valid local and possible spaces. We suggest an incremental learning method for solving the optimization problem. This method gradually produces the productive basic clustering by trying to optimize an incremental problem in each step. The incremental problem is as Eq. (9)(9) $$\mathit{Min}\mathrm{ Z}(\mathrm{ }{\Pi }^{\mathrm{\prime }}\mathrm{ }\cup \{{\pi }_{g+1}\}$$(9) . Given that $\Pi$ has gained the first basic cluster $g(0<g<T).$ (9) $$\mathit{Min}\mathrm{ Z}(\mathrm{ }{\Pi }^{\mathrm{\prime }}\mathrm{ }\cup \{{\pi }_{g+1}\}$$(9)

In addition, ${\theta }_{h+1i}$ is estimated through Eq (10)(10) $${\theta }_{h+1i}=\{\begin{array}{c}1,\mathrm{ }\sum _{h=I}^g{⋋}_h\left(X_i\right)=0,\mathrm{ }\\ 0,\mathrm{ }\mathit{otherwise}\mathrm{ }\end{array}$$(10) (10) $${\theta }_{h+1i}=\{\begin{array}{c}1,\mathrm{ }\sum _{h=I}^g{⋋}_h\left(X_i\right)=0,\mathrm{ }\\ 0,\mathrm{ }\mathit{otherwise}\mathrm{ }\end{array}$$(10) where $1\le i\le N.$

Given this constraint, we see that samples which are obtained by cluster centers and not shown in $\Pi$ play an important role in basic clustering $g+1.$ The incremental learning method is as follows: We first set $h=1,$ ${\theta }_h\left(X_i\right)=\mathrm{ }1$ for $1\le i\le N$ and $S=X.$ At each step, we select $k$ samples as the primary cluster centers from $S$ randomly and use k-means with limitation for its cluster. In the clustering method, the cluster centers are limited, which can be seen only in relation to their neighborhoods in Eq. (9)(9) $$\mathit{Min}\mathrm{ Z}(\mathrm{ }{\Pi }^{\mathrm{\prime }}\mathrm{ }\cup \{{\pi }_{g+1}\}$$(9) . This will cause the final cluster centers obtained to show samples in local spaces to be valid. After executing k-means, we will update $S=S-S\mathrm{\prime },$ where $S\mathrm{\prime }$ is a set of samples that have valid local labels in the $k_h$ basic clustering. Additionally, we will update $h=h+1,$ if $x_i\in S,$ then ${\theta }_h\left(X_i\right)=1,$ otherwise, for $1\le i\le N,$ it will be 0.

The above method repeats until the number of samples in $S$ is less than $k_h^2.$ Updating the cluster centers at each step through the iteration mechanism leads to the production of the final cluster centers. It can guarantee data description by multiple clustering. On the other hand, the importance of satisfying the final conditions should be determined. Many researchers argued that the maximum number of clustering in the set $S$ of samples should be less than $\sqrt{\left|S\right|}$ (Zheng et al. 2021; Zhu et al. 2021; Tan et al. 2020). Thus, while the number of samples in $S$ is less than $k_h^2,$ we assume that $S$ cannot be divided into $k_h$ clusters. Finally, if these conditions are met, the repetition can be stopped.

Algorithm 2.

Pseudocode of the MKM scheme.

Input: $X,$ $k,$ $\epsilon$

Output: $\Pi ,$ $V$

01: $\Pi =\varnothing ,V=\varnothing ,S=X,h=0;$

02: ${\theta }_h\left(X_i\right)=1,\mathrm{ }\mathit{for}\mathrm{ }1\le i\le N;$

03: Randomly select $k_h$ primary cluster centers as $v_h$ on $S;$

04: While $F<F\prime$ do

05: $F\prime =F;$

06: Given $v_h,$ ${\widehat{\pi }}_h$ is updated by $\underset{l=1\dots k_h}{\mathit{argmin}}d\left(X_i, v_{h_l}\right)$

07: For $X_i\in \mathrm{ S};$

08: Given ${\pi }_h,$ ${\widehat{v}}_h$ is updated by ${\widehat{v}}_h=\raisebox{1ex}{$\sum _{X_{i\in D}}{X}_i$}\!\left/ \!\raisebox{-1ex}{$\left|D\right|$}\right.,$

09: where $D=\left|\left\{\mathrm{\pi }\left(X_i\right)=\mathrm{l }\bigwedge {\mathrm{ X}}_i\in B\left(v_{\mathrm{hl}}\right),X_i\in \mathrm{S }\right\}\right|$

10: For $1\le l\le k_h;$

11: $F={\sum }_{l=1\mathrm{ }{\mathrm{\pi }}_{\mathrm{h}}\left(X_i\right)=l\mathrm{ },X_i\mathrm{ }\in \mathrm{ S}\mathrm{ }}^{k_h}\sum d(X_i,{v_{\mathrm{hl}})}^2$

12: $S^{\mathrm{\prime }}=\left\{{⋋}_h\left(X_i\right)=1,\mathrm{ }{X}_i\in S\mathrm{ }\right\};$

13: End For

13: For $i$ = 1 to $N$ do

14: If $X_i\in S^{\text{' }}$ then

15: ${\theta }_{h+1}\left(X_i\right)=0;$

16: else

17: ${\theta }_{h+1}\left(X_i\right)={\theta }_h\left(X_i\right);$

18: End If

19: End For

20: $\Pi =\Pi \cup \left\{{\pi }_h\right\};$

21: $V=V\cup v_h;$

22: $S=S-S\prime ;$

23: End For

24: End While

The incremental method is called the Modified k-means (MKM) clustering method, which is formally described in Algorithm 2. The time complexity of MKM, $O(\mathrm{Nt}\mathrm{ T}{k}_h),$ where $T$ is the number of partitions generated. The outputs of the algorithm have been the clustering set $\Pi =\left\{{\pi }_h,\mathrm{ }1\le h\le T\right\}$ and also the set of cluster centers, which is equal to $V=\left\{v_h,\mathrm{ }1\le h\le T\right\}.$ In order to simplify the basic clustering generation process, we determine a number of clusters in each basic clustering as $k,$ $k_h=k,\mathrm{ }1\mathrm{ }\le h\le T.$ We continue the following example in Figure 3. Here, we obtain a set of data as $\epsilon =0.8$ on the dataset as well as 10 cluster bases. Part (d) shows the partition lines of these basic clusters generated by the MKM scheme. We observe that these basic clusters are somewhat different, which is useful for the cluster group.

Figure 3. An example of MKM: (a) real class labels, (b) clustering from k-means, (c) local hypothesis of the clusters, and (d) multiple partitions by MKM.

Note that the number of $T$ basic cluster depends on the parameter $\epsilon .$ When the amount of $\epsilon$ decreases, the $T$ value must be increased, because a small amount of $\epsilon$ indicates that each basic cluster contains a number of local modifications. Therefore, while the $\epsilon$ is set to a smaller value, we need a more basic clustering to describe the whole data. The setting of $\epsilon$ depends on the needs of users, so that users can set the parameter to control the basic cluster number based on their needs.

4. Proposed Clustering Method

This study has provided a hybrid clustering method. This study has used the basic k-means clustering method as a basic cluster. Also, this study has increased the diversity of aggregation by adopting some measures. Here, the aggregation process of the basic clusters is done by the meta-clustering technique, where the primary clusters are re-clustered to form the final clusters. The proposed hybrid clustering method has the advantages of k-means, its high speed, as well as it does not have its major weaknesses.

In general, the labels in the dataset represent classes, but the labels in clustering only represent groups. Therefore, the labels in the clustering cannot be used for comparisons and cluster analysis. In this regard, it is necessary to align labels in clustering. Additionally, since the k-means method can only detect spherical and uniform clusters, two of the same clustering can represent a clustering. Hence, analysis of the relationship between clusters through similar clustering in needed. Now, there are inconsistent measures among the clusters proposed in the research literature (Yang et al. 2021; Ma et al. 2021). An example of this can be seen in chain clustering, where the intersection between clusters is determined by the distance between the farthest/closest sample between two clusters (Zhao et al. 2019). This method is sensitive to noise because it depends on a few specific samples to determine the final clusters. On the other hand, the distance between centers in center-based clustering approaches is defined as the absence of correlation. This method does not have the ability to effectively identify the border between clusters, but it has high computational efficiency and is resistant to noise.

In general, the similarity between two clusters in different partitions can be estimated based on the number of samples belonging to those clusters. This strategy cannot reflect samples with wrong labels in the cluster. However, some of these samples can have a high impact on the similarity calculation. Also, two clusters from the same partition share no sample, which is the reason for the inability of this metric to calculate similarity. Although there is good practice coordination between measures, they are not suitable for hybrid clustering. As mentioned, the labels of the created base partitions are different from the valid local labels. In other words, the validity of labels of each cluster may be low or high. Hence, the calculation of differences between clusters should be considered based on local labels. However, due to the use of MKM to generate initial partitions, the overlap between local labels should be relatively small. In this regard, we use an indirect overlap technique to calculate the similarity between clusters.

If $c_{h_l}$ and $c_{g_i}$ are two clusters, $V_{h_l}$ and $V_{g_i}$ are their cluster centers and $\left(V_{h_l}+V_{g_i}\right)/2$ is the middle point of two centers. We assume there is a hidden cluster $c_z$ whose cluster center is $\left(V_{h_l}+V_{g_i}\right)/2$ for hidden for the cluster. Let the probability of samples being in valid local locations be greater with the density of samples. If there is a hidden cluster and the distance between $V_{h_l}$ and $V_{g_i}$ is not greater than $4\times \epsilon ,$ valid local spaces from the clusters $c_{h_l}$ and $c_{g_i}$ are overlapping with the hidden clusters $c_z,$ as shown in Figure 4. In this case, the valid local spaces $c_{h_l}$ and $c_{g_i}$ are indirectly overlapping with the hidden cluster. For clusters $c_{h_l}$ and $c_{g_i},$ we consider these parameters to estimate the similarity between clusters.

Figure 4. Hidden cluster between clusters.

The distance between cluster centers is estimated based on the probability of a hidden cluster between them. As we know, whatever $d\left(V_{h_l},V_{g_i}\right)$ is smaller, the valid local spaces between them and $c_z$ will more overlap. In this respect, it is a fact that their similarity is inversely related to $d\left(V_{h_l},V_{g_i}\right).$ Also, k-means is a clustering approach with a linear mechanism and can identify the border of two clusters through a line between their centers. If the range around them is among several samples, they can be clearly identified. We use the following example in Figure 5.

Figure 5. Similarity between clusters.

It is clearly seen that clusters B and C have centers with larger distances compared to clusters A and B. Meanwhile, it is easier to determine the border between clusters A and B. Hence, the distance between the centers of clusters A and B may be increased considering the clarity of the boundary identification. According to this hypothesis, let the similarity between two clusters be estimated through a hidden cluster. Formally, similarity is measured as Eq (11)(11) $$\delta \left(c_{h_l},c_{g_i}\right)=\{\begin{array}{cc}\frac{\left|B\mathrm{ }\left(\frac{V_{h_l}+V_{g_i}}{2}\right)\right|}{d\left(V_{h_l},V_{g_i}\right)}& d\left(V_{h_l},V_{g_i}\right)\le 4\times \epsilon \\ 0& O\mathit{therwise}\end{array}$$(11) (11) $$\delta \left(c_{h_l},c_{g_i}\right)=\{\begin{array}{cc}\frac{\left|B\mathrm{ }\left(\frac{V_{h_l}+V_{g_i}}{2}\right)\right|}{d\left(V_{h_l},V_{g_i}\right)}& d\left(V_{h_l},V_{g_i}\right)\le 4\times \epsilon \\ 0& O\mathit{therwise}\end{array}$$(11)

Given the defined similarity matrix, we use an undirected weight graph (e.g., $G=<A,W>$) to describe the relationships between clusters. In this graph, $A$ refers to the set of nodes that represent the cluster labels in $\Pi .$ On the other hand, $W$ in $G$ refers to the weight of edges, which expresses the similarity between clusters. Hence, the similarity of both clusters is the concept of the weight of the edges between them, for example, ${x,\mathrm{ y}\mathrm{ }\in \mathrm{ A}\mathrm{ },\mathrm{ w}}_{\mathrm{Xy}}=\delta \left(c_x,c_y\right),$ and whatever there is similarity between them. By calculating the weighted graph, the relationships between the clusters can be mapped to the normal graph discharge challenge, which is as Eq. (12)(12) $$\begin{array}{c}\min \\ \Omega \end{array}\left[Q\left(\Omega \right)=\frac{1}{k}\sum _{l=1}^K\frac{\sum _{x\in A_l\mathrm{ },\mathrm{ y}\in A-A_l}{\mathrm{ w}}_{\mathrm{xy}}}{\sum _{x\in A_l\mathrm{ },\mathrm{ z}\in A}{w}_{\mathrm{xz}}}\right]$$(12) (12) $$\begin{array}{c}\min \\ \Omega \end{array}\left[Q\left(\Omega \right)=\frac{1}{k}\sum _{l=1}^K\frac{\sum _{x\in A_l\mathrm{ },\mathrm{ y}\in A-A_l}{\mathrm{ w}}_{\mathrm{xy}}}{\sum _{x\in A_l\mathrm{ },\mathrm{ z}\in A}{w}_{\mathrm{xz}}}\right]$$(12) where $\Omega =A_l,\mathrm{ }\forall l=1,2,...,k$ is a partition of nodes in $G$ and $A_l$ is one of the subsets of $A.$

Our goal is to measure this partition using the minimization of the objective function $Q.$ This is achieved by creating a partition that has high similarity between nodes in similar subsets and low similarity with nodes in other subsets. To solve this problem and create partition A, the normalized spectral clustering method has been used, where nodes in similar subsets represent a cluster. Hence, if $L(c_x)$ is the label of the subset which $c_x$ belongs to it, then we will have $L\left(C_x\right)=l,$ if $C_{x\mathrm{ }}\in A_l.$ If $1<l<k$ and $x\in A,$ the time complexity of the making of the cluster relationship is $O\left(N{\left(T.k_h\right)}^2\right).$

The use of hybrid clustering leads to the mapping of the clustering problem from the sample level to the cluster level. Assume that $\mathrm{PC}$ is a set containing all primary clusters created from all basic methods. Taking each cluster as a sample, the clustering process is applied again, where this time the clusters are clustered. This technique can create meta-clusters, where each meta-cluster contains several clusters. Meta-clusters have more knowledge about the data than clusters because they combine the latent knowledge from different clustering methods. Here, the clusters’ clustering method is done using k-means. Let the similarity of two samples from the available dataset be $s\left(x_i,x_j\right).$ Anyway, in meta-clusters the concept of similarity is extended from the sample level to the cluster level. We define the similarity measure of clusters in a meta-cluster through Eq. (13)(13) $$\begin{array}{c}\Psi \left({\mathrm{mc}}_{\alpha },{\mathrm{mc}}_{\beta }\right)=\frac{1}{\left|{\mathrm{mc}}_{\alpha }\right|.\left|{\mathrm{mc}}_{\beta }\right|}\sum _{v=1}^{\left|{\mathrm{mc}}_{\alpha }\right|}\sum _{w=1}^{\left|{\mathrm{mc}}_{\alpha }\right|}\left[\frac{\sum _{i=1}^{\left|c_v\right|}\sum _{j=1}^{\left|c_w\right|}\mathrm{\Gamma }(x_i,x_j)}{\left|c_v\right|.\left|c_w\right|}\right]\\ \forall x_i\in c_v,{\mathrm{ x}}_j\in c_w\end{array}$$(13) (13) $$\begin{array}{c}\Psi \left({\mathrm{mc}}_{\alpha },{\mathrm{mc}}_{\beta }\right)=\frac{1}{\left|{\mathrm{mc}}_{\alpha }\right|.\left|{\mathrm{mc}}_{\beta }\right|}\sum _{v=1}^{\left|{\mathrm{mc}}_{\alpha }\right|}\sum _{w=1}^{\left|{\mathrm{mc}}_{\alpha }\right|}\left[\frac{\sum _{i=1}^{\left|c_v\right|}\sum _{j=1}^{\left|c_w\right|}\mathrm{\Gamma }(x_i,x_j)}{\left|c_v\right|.\left|c_w\right|}\right]\\ \forall x_i\in c_v,{\mathrm{ x}}_j\in c_w\end{array}$$(13) where ${\mathrm{mc}}_{\alpha }$ and ${\mathrm{mc}}_{\beta }$ are two meta-clusters, and $\Psi \left({\mathrm{mc}}_{\alpha },{\mathrm{mc}}_{\beta }\right)$ refers to the average similarity between them. Also, $\left|{\mathrm{mc}}_{\alpha }\right|$ and $\left|{\mathrm{mc}}_{\beta }\right|$ are the number of clusters in ${\mathrm{mc}}_{\alpha }$ and ${\mathrm{mc}}_{\beta },$ respectively. Moreover, $\left|c_v\right|$ and $\left|c_w\right|$ describe the number of samples in $c_v$ and $c_w,$ respectively.

We create the final clusters by considering meta-clusters, where each instance of the dataset is assigned to a meta-cluster with maximum similarity. Meanwhile, the number of suitable clusters can be recognized by merging the initial clusters and applying a threshold value. Therefore, $k$ is determined as the number of optimal clusters by merging the initial clusters until the threshold $\theta$ is reached, as defined in Eq. (14)(14) $$\begin{array}{cc}\mathrm{if}\mathrm{ \sigma }\left(c_a,c_b\right)\ge \mathrm{ }\mathrm{\theta }⟹\mathrm{ }\{\begin{array}{c}\begin{array}{cc}\mathit{hence merged}& T\mathit{rue}\end{array}\\ \begin{array}{cc}\mathrm{not}\mathrm{ }\mathit{merged}& \mathrm{ }\mathit{False}\end{array}\end{array},& \forall a,b\in \mathrm{PC}\end{array}$$(14) . In other words, clusters are merged until the similarity of each existing pair of clusters is greater than $\theta .$ (14) $$\begin{array}{cc}\mathrm{if}\mathrm{ \sigma }\left(c_a,c_b\right)\ge \mathrm{ }\mathrm{\theta }⟹\mathrm{ }\{\begin{array}{c}\begin{array}{cc}\mathit{hence merged}& T\mathit{rue}\end{array}\\ \begin{array}{cc}\mathrm{not}\mathrm{ }\mathit{merged}& \mathrm{ }\mathit{False}\end{array}\end{array},& \forall a,b\in \mathrm{PC}\end{array}$$(14) where $c_a$ and $c_b$ are two clusters of the $\mathrm{PC}.$ Also, $\sigma \left(c_a,c_b\right)$ defines to the average similarity between $c_a$ and $c_b.$

5. Experimental Results

This section is related to the evaluation of the proposed clustering method based on four synthetic datasets and five real datasets. Here, the efficiency of the proposed method is evaluated through the analysis of different validation methods and runtime. The evaluation of the proposed method is compared with some state-of-the-art methods such as COllaborative-Single Link (CO-SL) (Fred and Jain 2005), COllaborative-Average Link (CO-AL) (Fred and Jain 2005), Combined Similarity Measure-Single Link (CSM-SL) (Iam-On et al. 2011), Combined Similarity Measure-Average Link (CSM-AL) (Iam-On et al. 2011), Weighted Triple Quality-Single Link (WTQ-SL) (Iam-On et al. 2011), Weighted Triple Quality-Average Link (WTQ-AL) (Iam-On et al. 2011), Weighted Connection Triple-Single Link (WCT-SL) (Iam-On et al. 2011), Weighted Connection Triple-Average Link (WCT-AL) (Iam-On et al. 2011), Meta-Clustering Algorithm (MCLA) (Strehl and Ghosh 2002), HyperGraph Partitioning Algorithm (HGPA) (Strehl and Ghosh 2002), Cluster-based Similarity Partitioning Algorithm (CSPA) (Strehl and Ghosh 2002), Selective Voting (SV) (Zhou and Tang 2006), Selective Weighted Voting (SWV) (Zhou and Tang 2006), Iterative Voting Consensus (IVC) (Nguyen and Caruana 2007), Expectation–Maximization (EM) (Topchy, Jain, and Punch 2005), Normalized Spectral Clustering (NSC) (Ng, Jordan, and Weiss 2001), Density Based Spatial Clustering of Applications with Noise (DBCAN) (Ester et al. 1996), and Clustering by Fast Search and Find of Density Peaks (CFSFDP) (Rodriguez and Laio 2014).

5.1. Experiment Settings

A number of settings for these compared methods are listed below to ensure that the comparisons are in uniform environment. The number of clusters per basic cluster is equal to the actual number of classes in each of the desired datasets. k-means is also used as a productive of basic clustering. There are two methods for basic clustering: (1) Multiple implementations of the k-means $T,$ each with a random amount of cluster centers. Let $N$ refer to the number of samples. A set of the group $T$ is set based on the dataset scale. If $N\le 500,$ then $T=25,$ if $500\le N<1,000,$ then $T=45$ and if $N\ge 1,000,$ then $T=15.$ (2) Implement the proposed method. The method requires an input parameter $\epsilon ,$ which is adapted to the size of the $T$ group, as required. Here, the size of the group $T$ is essentially consistent with the first plan.

We implemented all these methods with MATLAB 2019a simulator for experiments. The simulations are based on a synthetic fog environment on the Dell Latitude Laptop with Intel^® Atom^TM processor N550 (Core i7 at 3.3 GHz) and 16 GB of RAM. Meanwhile, the proposed method has some parameters as input whose values are adjusted using Taguchi approach (Yang et al. 2021).

5.2. Evaluation Criteria

Given the availability of real labels from the original dataset, we use two common measures based on unsupervised learning to estimate the similarity between the results and the correct division of the dataset of different methods. Given a dataset $X$ and two partitions of these samples, namely $C=\left\{c_1,c_2,\mathrm{ }\dots ,\mathrm{ }{c}_k\right\}$ (clustering result) and $P=\left\{p_1,p_2,\mathrm{ }\dots ,\mathrm{ }{p}_{k\mathrm{\prime }}\right\}$ (real partition), the values associated with $C$ and $P$ can be provided in a contingency table (Table 1), so that $n_{\mathrm{ij}}$ indicants the number of same nodes in the clusters $c_i$and $p_j:\mathrm{ }{n}_{\mathrm{ij}}=\left|c_i\cap p_j\right|.$

Table 1. The default table to compare two partitions.

$C\backslash P$	$p_1$	$p_2$	$p_{k\mathrm{\text{'}}}$	Sums
$c_1$	$n_{11}$	$n_{12}$	$n_{1k\mathrm{\text{'}}}$	$b_1$
$c_2$	$n_{21}$	$n_{22}$	$n_{2k\mathrm{\text{'}}}$	$b_2$
$⋮$	$⋮$	$⋮$	$\ddots$	$⋮$
$c_k$	$n_{k1}$	$n_{k2}$	$n_{\mathrm{kk}\mathrm{\text{'}}}$	$b_k$
Sums	$d_1$	$d_2$	$d_{\text{k'}}$	–

Normalized Mutual Information (NMI) and Adjust Rand Index (ARI) are evaluation metrics in experiments. The details of these criteria are described below.

5.2.1. NMI

Let ${\pi }_{\alpha }=\left[c_1^{\alpha },c_2^{\alpha },\dots ,c_{\left|{\pi }_{\alpha }\right|}^{\alpha }\right]$ and ${\pi }_{\beta }=\left[c_1^{\beta },c_2^{\beta },\dots ,c_{\left|{\pi }_{\beta }\right|}^{\beta }\right]$ be the results of two basic clustering methods as two partitions with $\left|{\pi }_{\alpha }\right|$ and $\left|{\pi }_{\beta }\right|$ clusters, respectively. Accordingly, the $\mathrm{NMI}({\pi }_{\alpha },{\pi }_{\beta })$ defines the diversity value for these partitions (Li, Qian, and Wang 2021), as shown in Eq. (15)(15) $$\mathrm{NMI}({\pi }_{\alpha },{\pi }_{\beta })=\frac{2\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\sum _{j=1}^{\left|{\pi }_{\beta }\right|}{n}_{\mathrm{ij}}\mathrm{l}\mathrm{og}\left(\frac{n.n_{\mathrm{ij}}}{n_{\mathrm{i\alpha }}.n_{\mathrm{\beta j}}}\right)}{\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}{n}_{\mathrm{i\alpha }}\mathrm{ }\log \left(\frac{n_{\mathrm{i\alpha }}}{n}\right)+\sum _{j=1}^{\left|{\pi }_{\beta }\right|}{n}_{\mathrm{\beta j}}\mathrm{ }\log \left(\frac{n_{\mathrm{\beta j}}}{n}\right)}$$(15) (15) $$\mathrm{NMI}({\pi }_{\alpha },{\pi }_{\beta })=\frac{2\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\sum _{j=1}^{\left|{\pi }_{\beta }\right|}{n}_{\mathrm{ij}}\mathrm{l}\mathrm{og}\left(\frac{n.n_{\mathrm{ij}}}{n_{\mathrm{i\alpha }}.n_{\mathrm{\beta j}}}\right)}{\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}{n}_{\mathrm{i\alpha }}\mathrm{ }\log \left(\frac{n_{\mathrm{i\alpha }}}{n}\right)+\sum _{j=1}^{\left|{\pi }_{\beta }\right|}{n}_{\mathrm{\beta j}}\mathrm{ }\log \left(\frac{n_{\mathrm{\beta j}}}{n}\right)}$$(15) where $n$ is the number of samples, $n_{\mathrm{ij}}$ is the same number of samples in $c_i^{\alpha }$ and $c_j^{\beta },$ $n_{\mathrm{i\alpha }}$ is the number of samples in $c_i^{\alpha },$ and $n_{\mathrm{\beta j}}$ is the number of samples in $c_j^{\beta }.$

5.2.2. ARI

This measure is often used in cluster validation and can indicate agreement between two partitions (Niu et al. 2020). The ARI is calculated based on the Rand Index, as defined in Eq. (16)(16) $$\mathrm{ARI}({\pi }_{\alpha },{\pi }_{\beta })=\frac{\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\sum _{j=1}^{\left|{\pi }_{\beta }\right|}\left(\begin{array}{c}{n}_{\mathrm{ij}}\\ 2\end{array}\right)-\left[\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\left(\frac{n_{\mathrm{i\alpha }}}{2}\right)\sum _{j=1}^{\left|{\pi }_{\beta }\right|}\left(\frac{n_{\mathrm{\beta j}}}{2}\right)\right]/\left(\frac{n}{2}\right)}{\frac{1}{2}\left[\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\left(\frac{n_{\mathrm{i\alpha }}}{2}\right)+\sum _{j=1}^{\left|{\pi }_{\beta }\right|}\left(\frac{n_{\mathrm{\beta j}}}{2}\right)\right]-\left[\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\left(\frac{n_{\mathrm{i\alpha }}}{2}\right)\sum _{j=1}^{\left|{\pi }_{\beta }\right|}\left(\frac{n_{\mathrm{\beta j}}}{2}\right)\right]/\left(\frac{n}{2}\right)}$$(16) (16) $$\mathrm{ARI}({\pi }_{\alpha },{\pi }_{\beta })=\frac{\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\sum _{j=1}^{\left|{\pi }_{\beta }\right|}\left(\begin{array}{c}{n}_{\mathrm{ij}}\\ 2\end{array}\right)-\left[\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\left(\frac{n_{\mathrm{i\alpha }}}{2}\right)\sum _{j=1}^{\left|{\pi }_{\beta }\right|}\left(\frac{n_{\mathrm{\beta j}}}{2}\right)\right]/\left(\frac{n}{2}\right)}{\frac{1}{2}\left[\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\left(\frac{n_{\mathrm{i\alpha }}}{2}\right)+\sum _{j=1}^{\left|{\pi }_{\beta }\right|}\left(\frac{n_{\mathrm{\beta j}}}{2}\right)\right]-\left[\sum _{i=1}^{\left|{\pi }_{\alpha }\right|}\left(\frac{n_{\mathrm{i\alpha }}}{2}\right)\sum _{j=1}^{\left|{\pi }_{\beta }\right|}\left(\frac{n_{\mathrm{\beta j}}}{2}\right)\right]/\left(\frac{n}{2}\right)}$$(16) where $n$ is the number of samples, $n_{\mathrm{ij}}$ is the same number of samples in $c_i^{\alpha }$ and $c_j^{\beta },$ $n_{\mathrm{i\alpha }}$ is the number of samples in $c_i^{\alpha },$ and $n_{\mathrm{\beta j}}$ is the number of samples in $c_j^{\beta }.$

5.3. Datasets

Experimental evaluations were performed on nine datasets. More information describing the datasets used in the experiments can be found in Table 2. The cluster distribution of this synthetic 2D dataset is shown in Figure 6. The real datasets are derived from the UCI machine learning repository (Golrou et al. 2018; Movahhed Neya, Saberi, and Rezaie 2022).

Figure 6. Distribution of four synthetic datasets: (a) imbalance, (b) aggregation, (c) banana, and (d) ring.

Table 2. Description of the datasets used.

Type dataset	Datasets	Number of samples	Number of features	Number of clusters
Artificial dataset	Imbalance	2,250	2	2
	Aggregation	788	2	7
	Banana	2,000	2	2
	Ring	1,500	2	3
Real dataset	Wine	178	13	3
	Iris	150	4	3
	Digits	5,620	63	10
	WBCD	569	30	2
	KDD-CUP99	1,048,576	39	2

5.4. Compared Methods

The proposed hybrid clustering method is evaluated in comparison with a wide range of clustering methods. Most of the clustering methods used for comparison are state-of-the-art and hybrid clustering methods. These methods include CO-average as a dual similarity approach that performs clustering through shared similarity matrix (Fred and Jain 2005). Similarity matrices based on CSM, WTQ, and WCT also belong to dual similarity approaches and are considered for comparison (Iam-On et al. 2011). Here, CO, CSM, WTQ, and WCT are analyzed through Single-Link (SL) and Average-Link (AL) hierarchical clustering methods to calculate the final results.

Also, HGPA, MCLA, and CSPA are hybrid clustering methods presented by Strehl and Ghosh (2002). These methods are also considered for comparison and evaluation of the proposed method. In addition, we use SV and SWV as analysis-based weighted clustering methods for comparison work (Zhou and Tang 2006). Here, two feature-based clustering methods including IVC and EM are also used for comparison. IVC is presented by Nguyen and Caruana (2007) and EM by Topchy, Jain, and Punch (2005).

We also evaluated the proposed method in comparison with some Strong clustering approaches. Here, DBCAN, NSC, and CFSFDP were used for comparison. NSC is presented by Ng, Jordan, and Weiss (2001), DBCAN by Ester et al. (1996), and CFSFDP by Rodriguez and Laio (2014).

5.5. Results and Discussions

This section analyzes the results of the proposed method in comparison with existing clustering methods. First, the parameter $\epsilon$ is analyzed as an effective input parameter for the proposed method. In general, setting the parameter $\epsilon$ is an important challenge in the proposed method. We discussed that the selection of this parameter depends on the number of basic clustering considered by the users. Then, we examined the effect of the parameter $\epsilon$ on the performance of proposed method with performing relevant tests. For example, this problem has been analyzed on Wine and Iris datasets. As shown in part (a) in Figures 7 and 8, the number of basic clusters generated by the MKM scheme decreases with increasing $\epsilon .$ However, as shown in part (b) in these figures, the quality of the clustering results does not increase, hence the value of $\epsilon$ should be slightly increased. On the other hand, the results clearly show that the number of basic clustering methods considered is not suitable. In other words, the number of methods considered to produce high-quality final clusters is high or low. Therefore, we must select an appropriate value of $\epsilon$ to control the number of basic clustering on each dataset.

Figure 7. Analysis of the $\epsilon$ parameter of the proposed method on the Wine dataset. (a) number of basic clusters generated and (b) quality of clustering results.

Figure 8. Analysis of the $\epsilon$ parameter of the proposed method on the Iris dataset. (a) number of basic clusters generated and (b) quality of clustering results.

In the following, the proposed method is evaluated in comparison with other hybrid clustering methods. Based on the NMI and ARI credit criteria, the performance of different clustering methods has been compared on synthetic and real datasets. Table 3 shows the results of the comparisons for the synthetic dataset based on NMI, and the results of this measure for the real dataset are reported in Table 4. These comparisons for ARI are presented in Tables 5 and 6, respectively. Here, the last two columns indicate the average and Standard Deviation (SD) of each method for this dataset based on MKM. As illustrated, the superiority of the proposed method in creating high-quality and high-accuracy clusters on synthetic data sets is clear. This issue is confirmed by observing the results of the subject clustering methods. The proposed method has succeeded in creating higher quality clusters due to the use of valid local clustering theory as well as the use of meta-clusters. Therefore, the proposed method identifies the final clusters more effectively and increases the efficiency.

Table 3. Results of evaluations on synthetic datasets based on NMI metric.

Methods	Imbalance		Aggregation		Banana		Ring		Average	SD
	Random	MKM	Random	MKM	Random	MKM	Random	MKM	MKM	MKM
CO-SL	0.269	0.007	0.875	0.631	0.402	0.001	0.693	0.693	0.333	0.238
CO-AL	0.269	0.231	0.875	0.841	0.402	0.415	0.210	0.194	0.420	0.261
CSM-SL	0.269	0.314	0.872	0.765	0.402	0.412	0.220	0.189	0.420	0.258
CSM-AL	0.269	0.001	0.872	0.024	0.402	0.002	0.020	0.001	0.007	0.310
WTQ-SL	0.269	0.009	0.875	0.550	0.402	0.002	0.539	0.693	0.314	0.225
WTQ-AL	0.269	0.205	0.869	0.887	0.402	0.432	0.216	0.237	0.440	0.257
WCT-SL	0.269	0.004	0.875	0.631	0.402	0.002	0.119	0.002	0.160	0.283
WCT-AL	0.269	0.298	0.875	0.863	0.402	0.395	0.215	0.118	0.418	0.260
MCLA	0.269	0.238	0.838	0.678	0.402	0.384	0.001	0.006	0.326	0.303
HGPA	0.004	0.007	0.628	0.678	0.001	0.007	0.001	0.129	0.205	0.271
CSPA	0.160	0.160	0.736	0.678	0.391	0.438	0.377	0.122	0.350	0.206
SV	0.269	0.001	0.386	0.304	0.402	0.230	0.174	0.163	0.174	0.093
SWV	0.269	0.002	0.617	0.435	0.402	0.003	0.247	0.148	0.147	0.147
IVC	0.269	0.223	0.893	0.810	0.402	0.395	0.380	0.170	0.399	0.240
EM	0.269	0.320	0.874	0.828	0.003	0.003	0.148	0.148	0.325	0.331
Proposed method	0.817	0.997	0.981	0.981	0.693	0.999	0.763	0.995	0.993	0.106

Table 4. Results of evaluations on real datasets based on NMI metric.

Methods	Wine		Iris		Digits		WBCD			Average	SD
	Random	MKM	Random	MKM	Random	MKM	Random	MKM	Random	MKM	Random
CO-SL	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760
CO-AL	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725
CSM-SL	0.836	0.464	0.760	0.670	0.732	0.474	0.625	0.007	0.836	0.464	0.760
CSM-AL	0.836	0.023	0.760	0.027	0.005	0.005	0.625	0.007	0.836	0.023	0.760
WTQ-SL	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760
WTQ-AL	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725
WCT-SL	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760	0.760
WCT-AL	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725	0.725
MCLA	0.836	0.548	0.760	0.772	0.764	0.605	0.625	0.473	0.836	0.548	0.760
HGPA	0.172	0.374	0.162	0.725	0.495	0.005	0.002	0.002	0.172	0.374	0.162
CSPA	0.779	0.582	0.682	0.725	0.787	0.594	0.300	0.444	0.779	0.582	0.682
SV	0.020	0.020	0.020	0.020	0.020	0.020	0.020	0.020	0.020	0.020	0.020
SWV	0.243	0.243	0.243	0.243	0.243	0.243	0.243	0.243	0.243	0.243	0.243
IVC	0.730	0.585	0.682	0.711	0.722	0.688	0.043	0.336	0.730	0.585	0.682
EM	0.799	0.558	0.674	0.731	0.729	0.717	0.541	0.532	0.799	0.558	0.674
Proposed method	0.888	0.856	0.816	0.806	0.903	0.861	0.614	0.668	0.888	0.856	0.816

Table 5. Results of evaluations on synthetic datasets based on ARI metric.

Methods	Imbalance		Aggregation		Banana		Ring		Average	SD
	Random	MKM	Random	MKM	Random	MKM	Random	MKM	MKM	MKM
CO-SL	0.247	0.001	0.795	0.419	0.505	0.001	0.502	0.502	0.231	0.194
CO-AL	0.247	0.181	0.795	0.752	0.505	0.511	0.132	0.110	0.388	0.255
CSM-SL	0.247	0.323	0.794	0.710	0.505	0.507	0.146	0.104	0.411	0.251
CSM-AL	0.247	0.001	0.794	0.008	0.505	0.001	0.006	0.002	0.003	0.293
WTQ-SL	0.247	0.001	0.795	0.379	0.505	0.001	0.413	0.502	0.221	0.199
WTQ-AL	0.247	0.134	0.790	0.784	0.505	0.527	0.140	0.168	0.403	0.251
WCT-SL	0.247	−0.013	0.795	0.419	0.505	0.001	0.027	0.002	0.102	0.287
WCT-AL	0.247	0.297	0.795	0.766	0.505	0.491	0.140	0.020	0.394	0.253
MCLA	0.247	0.193	0.704	0.485	0.505	0.481	0.002	0.007	0.291	0.265
HGPA	0.001	0.001	0.493	0.485	0.001	0.001	0.002	0.122	0.152	0.213
CSPA	0.051	0.051	0.551	0.485	0.494	0.546	0.318	0.086	0.292	0.195
SV	0.247	−0.004	0.310	0.231	0.505	0.117	0.086	0.063	0.102	0.150
SWV	0.247	0.001	0.372	0.300	0.505	0.005	0.182	0.032	0.084	0.124
IVC	0.247	0.167	0.821	0.775	0.505	0.491	0.325	0.119	0.388	0.221
EM	0.247	0.333	0.826	0.743	0.005	0.005	0.032	0.032	0.278	0.330
Proposed method	0.423	1.000	0.906	0.988	0.670	1.000	0.508	0.993	0.996	0.184

Table 6. Results of evaluations on real datasets based on ARI metric.

Methods	Wine		Iris		Digits		WBCD			Average	SD
	Random	MKM	Random	MKM	Random	MKM	Random	MKM	Random	MKM	Random
CO-SL	0.732	0.732	0.729	0.732	0.732	0.732	0.732	0.732		0.732	0.001
CO-AL	0.567	0.567	0.564	0.567	0.567	0.567	0.567	0.567		0.567	0.001
CSM-SL	0.849	0.356	0.729	0.655	0.616	0.298	0.732	0.004		0.328	0.082
CSM-AL	0.849	0.002	0.729	0.002	0.001	0.001	0.732	0.004		0.002	0.336
WTQ-SL	0.732	0.732	0.729	0.732	0.732	0.732	0.732	0.732		0.732	0.001
WTQ-AL	0.567	0.567	0.564	0.567	0.567	0.567	0.567	0.567		0.567	0.001
WCT-SL	0.732	0.732	0.729	0.732	0.732	0.732	0.732	0.732		0.732	0.001
WCT-AL	0.567	0.567	0.564	0.567	0.567	0.567	0.567	0.567		0.567	0.001
MCLA	0.732	0.732	0.729	0.732	0.732	0.732	0.732	0.732		0.732	0.001
HGPA	0.733	0.733	0.730	0.733	0.733	0.733	0.733	0.733		0.733	0.001
CSPA	0.849	0.849	0.846	0.849	0.849	0.849	0.849	0.849		0.849	0.001
SV	0.008	0.008	0.005	0.008	0.008	0.008	0.008	0.008		0.008	0.001
SWV	0.164	0.164	0.161	0.164	0.164	0.164	0.164	0.164		0.164	0.001
IVC	0.689	0.539	0.596	0.689	0.602	0.600	0.050	0.354		0.545	0.253
EM	0.787	0.493	0.599	0.698	0.622	0.620	0.634	0.599		0.603	0.074
Proposed method	0.913	0.870	0.773	0.758	0.844	0.786	0.680	0.771		0.796	0.086

Basically, the performance of the proposed method is better than other methods in the real dataset. However, improving the accuracy of the proposed method in the real dataset is less than that of the synthetic dataset. One of the most important reasons for this is that the dimensions of real data sets are much larger than synthetic datasets. In addition, according to the results, it can be stated that most of the compared clustering methods have performed better than the MKM scheme considering the random scheme. Because any basic cluster generated by the MKM scheme only includes the local modification of clusters in a dataset. However, these existing methods do not recognize or consider local modification. Therefore, they cannot get the results of a good group in the MKM scheme. The proposed method has better performance in MKM scheme than other methods. Note that the proposed method implements only in the MKM scheme, because the MKM scheme is part of it. We observe that the proposed method in the MKM scheme works better in terms of NMI and ARI based on other methods in the randomized scheme.

In the following, the proposed method is evaluated in comparison with other strong clustering methods. The results of comparing the proposed method with three strong clustering methods (i.e., NSC, DBCAN, and CFSFDP) based on the synthetic and real datasets are reported in Tables 7 and 8, respectively. Here, the last two rows refer to the mean and SD in each clustering method. As shown in these experiments, the clustering quality provided by the proposed method is better or promising compared to other methods. As the simulation results show, the proposed method can simulate strong simulation results and realize “a few clusters equal to a strong cluster.”

Table 7. Results of evaluations on synthetic datasets.

Synthetic datasets	NSC		DBSCAN		CFSFDP		Proposed method
	ARI	NMI	ARI	NMI	ARI	NMI	ARI	NMI
Imbalance	0.9989	0.9992	0.9987	0.9993	0.9990	0.9988	0.9995	0.9989
Aggregation	0.9931	0.9919	0.8076	0.8887	0.9866	0.9811	0.9860	0.9809
Banana	0.9989	0.9992	0.9987	0.9993	0.9990	0.9988	0.9995	0.9989
Ring	0.9989	0.9992	0.9987	0.9993	0.3217	0.3780	0.9995	0.9989
Average	0.9975	0.9974	0.9509	0.9717	0.8266	0.8392	0.9961	0.9944
SD	0.0025	0.0032	0.0827	0.0479	0.2915	0.2664	0.0058	0.0078

Table 8. Results of evaluations on real datasets.

Synthetic datasets	NSC		DBSCAN		CFSFDP		Proposed method
	ARI	NMI	ARI	NMI	ARI	NMI	ARI	NMI
Wine	0.9297	0.9003	0.3574	0.4438	0.7401	0.7515	0.8674	0.8529
Iris	0.7442	0.7967	0.5149	0.5891	0.7015	0.7264	0.7552	0.8029
Digits	0.7523	0.8106	0.5039	0.7150	0.7571	0.8632	0.7828	0.8580
WBCD	0.7480	0.6315	0.0465	0.0290	0.7292	0.6139	0.7687	0.6654
KDD-CUP99	0.6346	0.6276	0.2843	0.3551	0.5853	0.5907	0.6346	0.6356
Average	0.7618	0.7533	0.3414	0.4264	0.7026	0.7091	0.7617	0.7630
SD	0.0948	0.1072	0.1715	0.2337	0.0614	0.0989	0.0747	0.0943

In another experiment, the computational complexity of clustering methods is evaluated through runtime analysis. The efficiency of the proposed method on the KDD-CUP99 dataset was tested. We set $k=2$ and $\epsilon =0.14.$ The runtime of the method with a number of samples (i.e., $N$) is shown in Table 9. It is clearly evident that the number of $T$ basic clustering increases with increasing number of samples. Given the time complexity of the proposed method, the runtime with $T$ is second order. Given the runtime of the proposed method, the runtime with $T$ is second order. However, since that $T<N$ and $T$ slowly increase in comparison with $N$ growth, the cost of increasing $T$ growth time is acceptable. As depicted, the cost of runtime of the method proposed is proportional to the number of linear samples. Therefore, the proposed method must be able to quickly obtain the final clustering in a large-scale dataset. As illustrated, the proposed method is very efficient.

Table 9. Performance of the proposed method based on runtime (s) on the KDD-CUP99 dataset.

Number of samples	$\mathit{T}$	CSPA	MCLA	SWV	IVC	CFSFDP	Proposed method
5,000	44	11.82	6.24	10.85	12.39	18.81	5.96
10,000	107	41.18	39.87	39.74	39.70	53.26	26.14
15,000	110	67.98	62.21	54.08	51.37	63.20	39.54
20,000	114	99.11	88.15	70.79	65.01	74.91	55.11
25,000	114	123.91	108.81	83.65	75.26	83.01	67.51
30,000	119	156.64	136.09	101.38	89.81	95.75	83.87
35,000	119	183.18	158.21	115.20	100.87	104.60	97.14
40,000	179	316.56	269.36	192.11	166.36	168.89	163.83
45,000	232	505.95	427.18	297.38	254.11	249.69	258.53
50,000	234	562.69	474.46	327.19	278.09	269.27	286.92

6. Conclusion

Among the clustering methods, hybrid clustering is one of the popular methods with high stability and robustness, which provides the ability to discover hidden patterns with high accuracy. Hybrid clustering can adapt itself to the input dataset by using the knowledge of different methods and increase the quality of the final solution. The different quality of partitions from basic clustering methods is one of the arguments of hybrid clustering, which can achieve better results by combining them. Although k-means is a poor clustering method, it has a low computational cost, which makes it unsuitable for clustering results. Therefore, this study used the k-means clustering method as the basic cluster. Here, we presented a different definition of valid local clusters by considering the data around the cluster centers in k-means. To increase the diversity in the primary clusters, we used a duplicate strategy on nonappearance data in valid local clusters. Also, we used the inter-cluster and intra-cluster similarity measure to estimate the similarity between valid local clusters. This process has resulted in the production of a weighted graph in which the weight of the edges expresses the degree of similarity between the clusters. An aggregation function based on meta-clustering was used to create the final clusters, in which the primary clusters were re-clustered to obtain the final clusters. In general, the idea of the proposed method is to understand the concept of several weak clusters equal to a strong cluster by k-means. The results obtained from the proposed hybrid clustering method are more consistent with the real data structure. This method has reported better results compared to state-of-the-art methods on different datasets. Based on the results, the proposed method is effective for dealing with large-scale datasets. According to the concept of granular computing, how to extract the relationship between basic clustering methods and primary partitions is worth studying in future work. Also, the proposed method can appear more effective considering feature extraction/selection approaches. On the other hand, it is recommended to use techniques of increasing diversity such as bagging to select suitable basic clustering methods for future works.

Data availability

Data sharing not applicable to this manuscript as no datasets were generated or analyzed during the current study.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by Training plan for young backbone teachers in Henan Province (No.2018GGJS267).