# BiModalClust: Fused Data and Neighborhood Variation for Advanced K-Means Big Data Clustering
## 4 The Proposed Algorithm
### Precise Description  
The pseudocode for the proposed BiModalClust algorithm is presented in Algorithm 6. In the context of the Minimum Sum-of-Squares Clustering (MSSC) problem, where \(k\) conventionally denotes the number of clusters, we adopt the variables \(p\) and \(p_{\text{max}}\) to represent the current and maximum shaking powers, respectively. This distinction ensures clarity in the algorithm's parameterization while maintaining consistency with the MSSC notation.  
The proposed Algorithm 6 builds upon the basic VNS framework outlined in Algorithm 5, incorporating the following components:  
1. The neighborhood structure \(\mathcal{N}\) utilized in the shaking phase is defined as follows: * Let \(S\subset X\) be a uniform random sample of size \(s\) from \(X\). * Let \(U=(u_{1},\ldots,u_{l})\in\mathbb{R}^{l\times n}\) represent a finite subset of points in \(X\). * Define a probability distribution \(P:X\rightarrow[0,1]\) by \[P_{U}(x)=\frac{d(x,U)}{\sum_{x^{\prime}\in X}d(x^{\prime},U)}\] (4) where \(d(x,U)\) denotes the distance from a point \(x\) to the set \(U\). This distribution corresponds to the one used in K-means++ initialization. Let \(C=(c_{1},\ldots,c_{k})\) denote the incumbent solution. Adopting the notation \(\mathbb{N}_{k}=\{1,\ldots,k\}\), the \(p\)-th neighborhood \(\mathcal{N}_{p}(C)\) of the incumbent solution is then defined as \[\mathcal{N}_{p}(C)=\{(c_{1},c_{2},\ldots,c_{l_{1}},\ldots,c_{l_{2}},\ldots,c_ {l_{p}},\ldots,c_{k})\mid\] (5) \[\text{where }l_{1}<l_{2}<\ldots<l_{p}\in\mathbb  
2. The local search procedure is based on Algorithm 4. The neighborhood structure \(N(C)\) for the incumbent solution \(C\) is defined as \[N(C)=\bigcup_{i\in\mathbb{N}_{k}}\text{Conv}(S_{i}),\] where \(S_{i}\subset S,\ i\in\mathbb{N}_{k}\), represents the set of all sample points assigned to cluster \(c_{i}\), i.e.,  
\[S_{i}=\{x\in S\ |\ \operatorname*{arg\,min}_{c\in C}d(x,c)=c_{i}\},\] and \(\text{Conv}(\cdot)\) denotes the convex hull operation. Searching within the convex hull of the sample points in each cluster is justified by a key property of the squared Euclidean distance function: * The optimal placement of the centroid (to minimize the sum of squared distances) is always within the convex hull of its assigned points.  
As the centroid approaches the mean of the assigned points, the sum of squared Euclidean distances decreases, reaching its minimum when the centroid coincides with the mean of the points [22]. Thus, the K-means algorithm is employed for local search due to its reliance on these fundamental properties.
3. The neighborhood change follows Algorithm 3. In each iteration, the shaking power \(p\) is incremented, regardless of whether the objective function has improved or not.  
Empirical studies have demonstrated that the specific combination of VNS components described above is critical to achieving the best performance of BiModalClust, both in terms of computational efficiency and the quality of the solutions obtained.  
It is important to highlight that BiModalClust does not strictly conform to the traditional VNS metaheuristic. Unlike standard VNS, both the neighborhood structure \(\mathcal{N}\) used in the shaking phase and the local search procedure operate on a sample \(S\), rather than the entire dataset \(X\). Despite this deviation, the approach aligns with the newly introduced Variable Landscape Search (VLS) metaheuristic, as detailed in [23], under which BiModalClust is formally categorized.