# BiModalClust: Fused Data and Neighborhood Variation for Advanced K-Means Big Data Clustering
## 1 Introduction  
Clustering is a fundamental operation in data analysis, aiming to identify cohesive groups of objects sharing similar characteristics within a given dataset. With the rapid expansion of digital information, clustering has become indispensable across a wide array of applications, such as image analysis, customer segmentation, and beyond. Among the diverse clustering paradigms, the Minimum Sum-of-Squares Clustering (MSSC) model [1] is a cornerstone methodology. MSSC seeks an optimal partitioning of \(m\) data points in a multi-dimensional space \(X\) by minimizing the total sum of squared distances between data points and their respective cluster centroids. The mathematical formulation of MSSC is as follows:  
\[\min_{C}\ \ \ f(C,X)=\sum_{i=1}^{m}\min_{j=1,\ldots,k}|x_{i}-c_{j}|^{2} \tag{1}\]In this expression, the objective is to determine the optimal set of \(k\) centroids \(C\) such that the function \(f(C,X)\)--representing the sum of squared distances--is minimized. The notation \(|\cdot|\) denotes the Euclidean norm. Each solution to this optimization problem induces a specific partitioning of the dataset into clusters, capturing inherent structure within the data. Essentially, the primary goal of MSSC is to partition a dataset into distinct, well-defined clusters. A key characteristic of MSSC is its dual-action optimization mechanism. By minimizing the expression in Equation (1), MSSC inherently increases intra-cluster similarity while simultaneously maximizing inter-cluster dissimilarity. This balance ensures the formation of cohesive clusters that are also distinct from one another, fulfilling the core objective of clustering algorithms. Consequently, MSSC serves as both a method for generating high-quality partitions and a benchmark for evaluating clustering accuracy. Despite its conceptual simplicity, the MSSC problem is notably challenging due to its classification as NP-hard [1]. Solving MSSC is computationally intensive, especially as data volume and dimensionality increase, underscoring the need for innovative, scalable approaches to tackle this challenge effectively. For big data scenarios [2], traditional clustering methods such as K-means and K-means++ struggle to solve the MSSC problem efficiently within a reasonable allocation of resources. This limitation creates the need for innovative techniques to tackle the big data clustering challenge. MSSC is a global optimization problem, where the difficulty lies not only in the computational effort required but also in navigating the intricate solution landscape. The importance of identifying global minimizers in MSSC has been well-documented [3]. These minimizers provide a more faithful representation of the dataset's intrinsic clustering patterns. However, due to the non-convex, non-smooth nature of the objective function, which becomes aggravated in big data contexts, finding global minimizers is a formidable task that often challenges conventional optimization methods. In this work, we introduce BiModaClust, an innovative algorithm that employs a dual-modality optimization approach: (1) exploring partial solution landscapes derived from the data stream of random samples from the original dataset, and (2) iteratively traversing increasingly expansive neighborhoods within these landscapes to refine the incumbent solution. For the latter, we define a specialized neighborhood structure, where two solutions are considered neighbors if they differ in a defined subset of centroids. By strategically exploring this structure using an appropriate metaheuristic, the algorithm achieves a more informed and directed traversal of the solution space. The simultaneous exploitation of these two modalities enables the algorithm to \"shake\" the incumbent solution effectively, thereby escaping unfavorable local minima. Controlling the size of input data samples allows for significant reductions in time complexity, making the algorithm inherently scalable to large datasets.