# BiModalClust: Fused Data and Neighborhood Variation for Advanced K-Means Big Data Clustering
## 3 Variable Neighborhood Search
### Main Concepts
For instance, if we aggregate all local solutions \(C=(c_{1},\ldots,c_{k})\) of the MSSC problem as defined in Equation (1) into a single set, it is likely that a significant subset of these locally optimal centroids will be clustered close to each other, while a few may deviate. This pattern suggests that the global optimum shares overlaps in certain variables (specific coordinates of the vector representations) with those found in local optima. However, identifying these overlapping variables in advance is inherently difficult. Consequently, a methodical exploration of neighborhoods surrounding the current local optimum remains prudent, continuing until a superior solution emerges. This systematic neighborhood search not only enhances the likelihood of escaping suboptimal solutions but also leverages the structural tendencies of the problem to converge more efficiently toward the global optimum. Variable Neighborhood Search (VNS) operates through two fundamental phases: the improvement phase, which refines the current solution by descending to the nearest local optimum, and the shaking (or perturbation) phase, which seeks to escape local minima traps. These phases are alternated with a neighborhood change step, and the process repeats until predefined stopping criteria are satisfied. The VNS framework revolves around three primary, iterative steps:  
1. a shaking procedure, which introduces a controlled perturbation to the current solution to explore new areas of the solution space;
2. an improvement procedure, which applies local search techniques to refine the perturbed solution, potentially reaching a local optimum;
3. a neighborhood change step, which alters the neighborhood structure, allowing exploration of different regions of the solution space. To better understand the VNS framework, let us define some essential concepts:  
The incumbent solution is the current best-known solution, denoted as \(x\), which minimizes the objective function value among all solutions examined thus far. For a given solution \(x\), its neighborhood comprises the set of solutions that can be directly obtained from \(x\) by applying a specific local change. Neighborhoods are typically defined using a metric (or quasi-metric) function, denoted as \(\delta\). For a non-negative distance threshold \(\Delta\geq 0\), the neighborhood of \(x\) is formally defined as  
\[\mathcal{N}_{\Delta}(x)=\{y\in\mathcal{F}\mid\delta(x,y)\leq\Delta\} \tag{3}\]  
Examples of neighborhoods:  
1. In continuous optimization problems over \(\mathbb{R}^{n}\), a neighborhood like \(\mathcal{N}_{1}(x)\) might represent an Euclidean ball of radius 1 centered at \(x\), while \(\mathcal{N}_{3}(x)\) could include solutions obtained by modifying exactly three coordinates of \(x\). 2. In the Traveling Salesman Problem (TSP), a common neighborhood involves all tours generated by reversing a subsequence of the current tour, an operation known as the \"2-opt\" move. Neighborhoods play a critical role in both the shaking and improvement phases, enabling VNS to effectively explore the solution space and navigate complex optimization landscapes. By iteratively combining these steps, VNS achieves a balance between diversification (escaping local optima) and intensification (refining toward better solutions), making it a powerful tool for solving global optimization problems. A neighborhood structure, denoted as \(\mathcal{N}\), is defined as an ordered collection of operators:  
\[\mathcal{N}=\{\mathcal{N}_{1},\ldots,\mathcal{N}_{k_{\max}}\},\]  
where each operator \(\mathcal{N}_{k}:\mathcal{F}\rightarrow\mathcal{P}(\mathcal{F})\) maps a solution \(x\in\mathcal{F}\) to a predefined set of neighboring solutions \(\mathcal{N}_{k}(x)\) within the feasible solution space \(\mathcal{F}\). Here, \(\mathcal{P}(\mathcal{F})\) represents the power set of \(\mathcal{F}\), and \(k\in 1,\ldots,k_{\max}\) indexes the individual neighborhoods. This hierarchical arrangement of neighborhoods is a cornerstone of the VNS framework.