# Optimal Partitioning of Unbalanced Datasets for BGP Anomaly Detection
## 3 Proposed Approach
### Optimal Partitioning (OP)  
Dataset partitioning is a challenging task; it consists of dividing a given dataset into multiple subsets while preserving the key attributes of the original dataset in each subset. This work is a fundamental part of different data analysis processes, such as grouping, assigning, and anomaly recognition. We applied this idea to balance the dataset by separating the samples from the dominant classes into multiple sub-class clusters. The process virtually increases the number of classes but makes the class distribution even. To achieve this, in the presented work, we propose the optimal partitioning scheme, which utilizes the Gray Wolf Optimization (GWO) [12] algorithm to optimally partition the data samples from the majority classes. The GWO algorithm, modeled after how gray wolves hunt and coordinate, has become a favorite optimization scheme, as it had been shown in several optimization domains to be a very powerful tool. The capability of imitating the leadership order found among wolves as well the cooperation shared among the pack members make it a sensible candidate for optimizing complex problems. This synergy between GWO and dataset partitioning is explored in the proposals. Its aim is to develop an algorithm that is efficient at processing imbalanced datasets. The goal is to assign data instances from the majority classes to partitions (clusters) in such a way that class imbalance reduction, better classification accuracy, and class distribution balance are provided. The class evenness of each partition is kept as well. In the proposed methodology, the GWOalgorithm is tuned to detect the best partitioning criterion as far as the imbalanced dataset is concerned. The GWO algorithm's search mechanism performs this to determine the best partitioning scheme that seeks to maximize the inter-cluster separability and minimize the intra-cluster variance. With this, it is ensured that every subset created during the partitioning step keeps the ratio of the various classes present in the balanced dataset. To achieve this, the GWO algorithm is customized to treat the problem of dataset partitioning as a multi-objective optimization task. The algorithm iteratively adjusts the boundaries of each data subset based on the fitness function, which quantifies the quality of the partitioning. The fitness function considers factors such as the class distribution, data density, and intra-class similarity. The whole process can be explained as follows:  
Objective: The Gray Wolf Optimization (GWO) algorithm optimizes the clustering with a given number of clusters (\(N\)), maximizing the inter-class separability and minimizing the intra-class variance. The GWO searches for the best positions of the centroids to achieve this goal;  
Objective Function: The objective is to minimize the intra-class variance (within-cluster sum of squares (\(WSS\))) while maximizing the inter-class separability (between-cluster sum of squares (\(BSS\))). However, these goals are inherently balanced in a clustering context because minimizing the \(WSS\) typically leads to maximizing the \(BSS\). Thus, our fitness function can primarily focus on minimizing the \(WSS\), with the \(BSS\) being indirectly affected. We also need to adjust the fitness evaluation to penalize deviations from equal cluster sizes. Considering the \(WSS\), \(BSS\), and penalty for unequal cluster sizes, the representation of the objective function is as follows:  
\[F=\frac{BSS}{WSS+\lambda\times P} \tag{2}\]  
where \(\lambda\) is a regularization parameter which is used for controlling the impact of the cluster size penalty (\(P\)). The goal is to maximize the \(F\), thus minimizing the \(WSS\), maximizing the \(BSS\), and enforcing cluster size balance.