HWKPA: Optimized Ensemble Clustering with Hybrid Weighted K-Means Pollination with Major Voting Consensus Function for Enhancing Cluster Quality

With an emphasis on consistency and quality improvement, a clustering ensemble aims to combine many clustering models to produce a better result than separate clustering methods. It includes a range of methods based on different distance measurements.

Examples of methods that expand the vocabulary include Affinity Propagation (graph distance), Mean-shift (point-to-point distance), Gaussian Mixtures (Mahalanobis distance to centroids), Spectral Clustering (graph distance), DBSCAN (nearest point distance), K-means (point-to-point distance) and so forth. DBSCAN is a popular clustering technique for clustering and data processing shown in Figure 2. It groups data points based on their density and labels outliers as noise and clusters of high-density zones. DBSCAN is a fundamental method for density-based clustering. Even in the presence of noise and abnormalities, it is able to recognize clusters of different sizes and configurations from large datasets.

2.jpg

Figure 2. Proposed architecture

3.1 Dataset description

Table 1. Dataset description

Table 2. Sample datas

3.2 Data pre-processing

A critical step in getting raw data ready for clustering algorithms is data pre-processing, which frequently entails a number of methods to clean and standardize the information. Managing missing values, normalizing or standardizing information, and addressing outliers are examples of typical pre-processing procedures. To prepare the data for clustering algorithms and ensure high-quality clusters, preprocessing steps such as handling missing values, normalization/standardization, and outlier detection are essential.

3.2.1 Handling missing values

 Missing values can distort clustering results by making it difficult to define proper clusters. There are different techniques to handle missing values based on the type of data and the extent of missingness:

Mean Imputation: For numerical features, missing values can be replaced by the mean of the feature.

$i_{missing}=\frac{1}{N} \sum_{x=1}^N i_x$                (1)

where, $i_{missing}$ is the missing value, and N is the total number of available data points for the feature.

Median Imputation: Alternatively, missing values can be replaced by the median value of the feature, which is more robust to outliers.

$i_{{missing}}={Median}\left(i_1, i_2, \ldots, i_N\right)$                (2)

Mode Imputation: For categorical features, missing values can be replaced by the mode (most frequent value) of the feature.

3.2.2 Normalization / Standardization

Normalization and standardization are important preprocessing steps when the data features have different scales, especially for distance-based algorithms like K-means clustering. These methods scale the data to bring all features to a comparable range.

Min-Max Normalization: Scales the data to a fixed range, usually [0, 1], by transforming each feature's values based on its minimum and maximum values.

$i_{ {norm }}=\frac{i-i_{\min }}{i_{\max }-i_{\min }}$               (3)

where, i is the original data point, $i_{\min }$ and $i_{\max }$ are the minimum and maximum values of the feature, respectively.

Z-score Standardization (Standardization): Centers the data by subtracting the mean and scales it by dividing by the standard deviation.

$i_{{standardized }}=\frac{i-\mu}{\sigma}$              (4)

where, i is the data point, μ is the mean of the feature, σ is the standard deviation of the feature.

3.2.3 Handling outliers

Outliers can significantly affect clustering algorithms, particularly when using distance-based methods. Several techniques are used to detect and handle outliers:

Z-score Method: This method identifies outliers by measuring how far a data point is from the mean in terms of standard deviations. Points with a Z-score greater than a threshold (commonly 3) are considered outliers.

$Z=\frac{i-\mu}{\sigma}$                (5)

where, Z is the Z-score; i is the data point; µ is the mean of the feature; σ is the standard deviation. If |Z|>3, the data point is considered an outlier.

Interquartile Range (IQR) Method: The IQR is the range between the 25th (Q1) and 75th (Q3) percentiles of the data. Data points outside the range defined by $Q 1-1.5 \times I Q R$ and $Q 3+1.5 \times I Q R$ are considered outliers.

$I Q R=Q 3-Q 1$               (6)

where, Q1 is the first quartile (25th percentile), Q3 is the third quartile (75th percentile), IQR is the interquartile range.

Data points with values outside $[Q 1-1.5 \times I Q R, Q 3+1.5 \times I Q R]$ are outliers.

Winsorization: This technique replaces outliers with the nearest valid values within a specified range (e.g., replacing values beyond 1.5 IQR with the 1st or 3rd quartile values).

Enhancing the quality of grouping findings requires the pre-processing procedures outlined here: managing missing variables, normalization/standardization, and outlier identification. These procedures guarantee that clustering algorithms operate at their best and generate precise, significant clusters, particularly ones that depend on distance measurements like K-means. Three components make up the collective clustered architecture procedure: the design of the agreement operations, the base clustering choice procedure, and the base clustering generation mechanism such structure is shown in Figure 3.

3.jpg

Figure 3. Ensemble clustering framework

3.3 Ensemble cluster level of uncertainty

In the context of ensemble grouping, cluster-level uncertainty is the degree of ambiguity or discrepancy between the clustering outcomes from various models or methods. Uncertainty occurs when data points are located close to the borders of clusters or when several clustering methods yield disparate results. Cluster-level uncertainty is usually expressed quantitatively using a consensus function that combines the output of many basic clustering methods. By calculating the consistency with which each data point is allocated to clusters across several base models, the resulting consensus function offers an indicator of uncertainty.

3.3.1 Cluster-level uncertainty via consensus matrix

Let $C=\left\{C_1, C_2, \ldots, C_m\right\}$ be a set of clustering solutions from m base clustering models, where $C_x$ represents the clustering result from the i-th model, and each $C_x$ assigns n data points to k clusters. The consensus matrix R is a matrix where each element Rij represents the similarity or agreement between data points x and y across the clustering solutions.

The consensus matrix R is typically computed as:

$R_{x y}=\frac{1}{m} \sum_{x=1}^m 1_{C_x(x)=C_x(y)}$               (7)

where, 1 is the indicator function that is 1 if data points x and y are assigned to the same cluster in clustering solution $C_x$, and 0 otherwise. m is the number of base clustering models. $C_x(x)$ and $C_x(y)$ refer to the cluster assignments for data points x and y in clustering solution $C_x$.

3.3.2 Cluster-level uncertainty calculation

Once the consensus matrix R is formed, cluster-level uncertainty can be computed based on the agreement between data points within a cluster and the consistency of cluster assignments. A high level of uncertainty indicates that the data points within a cluster are inconsistently assigned across different base models, while a low level of uncertainty implies stable and consistent assignments.

Uncertainty for Each Cluster: For a given cluster $C_k$, the uncertainty $U\left(C_k\right)$ can be defined as the average dissimilarity (or disagreement) between all pairs of data points within the cluster across all base clustering solutions.

$U\left(C_k\right)=\frac{1}{\left|C_k\right|^2} \sum_{x, y \in C_k}\left(1-R_{x y}\right)$               (8)

where, $\left|C_k\right|$ is the number of data points in cluster $C_k$. $R_{x y}$ is the element of the consensus matrix representing the agreement between points x and y.

The term $\left(1-R_{x y}\right)$ reflects the disagreement or uncertainty between points x and y.

Total Cluster-Level Uncertainty: The total cluster-level uncertainty U for the ensemble can then be defined as the sum of uncertainties across all clusters:

$U=\sum_{k=1}^k U\left(C_k\right)$                (9)

where, K is the total number of clusters, $U\left(C_k\right)$ is the uncertainty of cluster $C_k$.

3.3.3 Uncertainty based on soft assignments (soft clustering)

In cases of soft clustering (e.g., fuzzy clustering), where data points can belong to multiple clusters with different membership degrees, cluster-level uncertainty can also be expressed in terms of the fuzzy membership values $\mu_{x k}$, which indicate the degree to which point i belongs to cluster $C_k$.

The uncertainty for data point x in cluster $C_k$ can be defined as the inverse of the membership degree:

$U_x\left(C_k\right)=1-\mu_{x k}$                (10)

where, $\mu_{x k}$ is the membership degree of point x in cluster $C_k$.

Then, the overall cluster-level uncertainty for the ensemble is averaged over all data points:

$U=\frac{1}{n} \sum_{x=1}^n \sum_{k=1}^K\left(1-\mu_{x k}\right)$                (11)

where, n is the number of data points, K is the number of clusters.

The degree of consistency with which the various base clustering models allocate every group is measured by cluster-level uncertainty. By evaluating the degree of agreement or disagreement between several grouping models, the consensus matrix offers a basis for computing the level of uncertainty. This metric aids in the understanding of cluster quality in ensemble clustering systems and also in the assessment of the reliability and consistency of the grouping outcomes in ensemble techniques.

3.4 Proposed algorithm: HWKPA

HWKPA approach is used to increase the efficiency of the grouping. Once the grouped information has been collected using the K-means technique, the weighted flower pollination method uses the training information to select the best information. The most promising information is then sent into the spectral clustering technique to cluster its information appropriately. The agreement on clustering is then provided by implementing the main vote concept for K means and HWKPA-based spectral grouping. To optimize quality and save calculation time, HWKPA selects the finest information at hand. The number of features in the dataset increases exponentially with the level of complexity of the proposed solution space. To improve the standard and efficacy of grouping in complicated datasets, the HWKPA is a novel clustering technique that combines the advantages of the K-means clustering method with the Pollination Algorithm (PA). The K-means method, which is renowned for its effectiveness in dividing information into discrete clusters, serves as the foundation clustering technique in this hybrid approach. K-means frequently suffer from sensitivity to starting centroids and local minima, which can lower grouping efficiency. This is addressed by HWKPA's Pollination Algorithm, which is based on the natural pollination process and uses a weighted method to balance the effect of various information points while intelligently searching for the best centroids. By using guided random searches to more efficiently explore the search space, the method of pollination aids in getting over K-means' drawbacks. The method's weighted element makes sure that during centroid developments, information elements that are more important or have a bigger impact on the clustering result are given more weight. Thus, this hybrid strategy improves the reliability and precision of the clustering outcomes by utilizing the Pollination Technique's worldwide search abilities in addition to K-means' rapid convergence and ease of use. To lower uncertainty and improve cluster quality, the approach determines the final cluster allocations using a major voting consensus function. In general, HWKPA offers improved performance in terms of cluster coherence and quality, making it a more reliable option for clustering in high-dimensional and varied datasets.

Algorithm: Proposed algorithm

Step 1: Initialization

Let $I=\left\{i_1, i_2, \ldots, i_n\right\}$ be the dataset with n data points.

Define K as the number of clusters.

Initialize weights $w_x$ for each data point $i_x$.

Randomly select initial centroids $\mu_1, \mu_2, \ldots, \mu_k$ for each cluster $C_k$ where $k=1,2, \ldots, K$.

Set the maximum number of iterations max_iter and the convergence threshold δ.

Step 2: K-means Assignment

For each data point 2, compute the Euclidean distance to each centroid μι:

$d\left(i_x, \mu_k\right)=\left\|i_x-\mu_k\right\|_2$               (12)

Assign $i_x$ to the cluster $C_k$ with the nearest centroid.

Step 3: Weighted Centroid Update

Update the centroid $\mu_k$ of each cluster $C_k$ using the weighted average of all data points $i_x$ in the cluster:

$\mu_k=\frac{\sum_{i_{x \in C_k}} w_x . i_x}{\sum_{i_{x \in C_k}} w_x}$                 (13)

This step ensures that data points with higher weights $w_x$ have a greater influence on centroid positioning.

Step 4: Pollination-Based Optimization

Global Pollination (Cross-Pollination):

With probability p, update each centroid $\mu_k$ by performing a global search based on Lévy flight:

$\mu_k^{{new }}=\mu_k+\gamma L\left(i-g_{ {best }}\right)$                (14)

where, $\gamma$ is a scaling factor. $L\left(i-g_{b e s t}\right)$ follows a Lévy distribution. $g_{{best }}$ is the globally best centroid found so far across all clusters.

Local Pollination (Self-Pollination):

With probability 1 p, perform a local search by adjusting centroids within the existing cluster:

$\mu_k^{ {new }}=\mu_k+\varepsilon\left(i_x-\mu_k\right)$              (15)

where, $\varepsilon$ is a random number in [0,1]. $i_x$ is a randomly selected data point within cluster $C_k$.

Select the Best Centroid: For each centroid $\mu_k$, keep the updated centroid $\mu_k^{ {new }}$ if it improves the clustering quality based on minimized distance to data points in $C_k$; otherwise, retain the original $\mu_k$.

Step 5: Consensus Voting for Cluster Assignment

After a few iterations of steps 2-4, apply a consensus function to finalize the cluster assignments. For each data point $i_x$, aggregate assignments from previous iterations and assign, $i_x$ to the cluster most frequently assigned:

$C\left(i_x\right)={mode}\left(\left\{C_k^{(1)}, C_k^{(2)}, \ldots, C_k^{(m)}\right\}\right)$                 (16)

where, $C_k^{(y)}$ denotes the assignment of $i_x$ to cluster $C_k$ in the y^th iteration. The mode selects the most frequent assignment, improving stability of clustering results.

Step 6: Convergence Check

Compute the change in centroids between the previous and existing iterations. If the change for all centroids is below the threshold δ or the maximum number of iterations max_iter is reached, stop the algorithm:

$\left\|\mu_k^{\text {new }}-\mu_k\right\|<\delta, \forall k=1,2, \ldots, k$                  (17)

Step 7: Output

The final centroids $\left\{\mu_1, \mu_2, \ldots, \mu_k\right\}$ and cluster assignments for each data point.

The HWKPA algorithm iteratively combines weighted K-means with global and local pollination- based optimization, adjusting centroids dynamically to avoid local minima and refine cluster boundaries. By incorporating both global exploration and local adjustments, the algorithm stabilizes cluster assignments through consensus voting and achieves high-quality clustering. This hybrid approach results in enhanced cluster coherence and quality, making it well-suited for complex data distributions.