# Optimization Algorithms for Scalable Stream Batch Clustering with k Estimation
## 1 Introduction  
New technologies combined with widespread access have supported the exponential increase in continuously generated data and challenging machine learning techniques such as data clustering. Although clustering algorithms are well known for _batch_ data, the traditional centralized and even some distributed approaches for clustering data streams may not be able to deal with this increasing data volume due to the limitations of scaling up such systems. On the other hand, scaling-out systems are a feasible alternative to handle rapidly increasing amounts of data, being successfully applied over batch data and data streams. Data streams are ordered sequences of objects with non-stationary data distribution [1]. The clustering of this type of data must address specific challenges [2, 3]: (i) continuously generated data, (ii) unbounded data, (iii) evolving data, represented by phenomena such as changes in clusters (concept drift) and the emergence of new clusters (concept evolution [4]), and (iv) variable number and size of clusters over the stream, which means that clusters can appear, disappear, merge, and split. The automatic estimation of the number of clusters (\(k\)) from data is a well-known problem in the clustering task since \(k\) is often unknown in real scenarios. Moreover, as the number of clusters in data streams may vary over time, static prior-defined values may notbe feasible. There are, in the literature, several approaches to estimate the number of clusters for static (non-incremental) data sets, including approaches for numeric attributes [5] and for categorial data [6]. Moreover, the dynamic estimation of \(k\) increases the quality of the model in data streams and allows the algorithm to handle evolving data [3]. The classical algorithms for clustering data streams can address the challenges of unbounded size and the continuous data generation by avoiding expensive random access, giving way to single and linear scans [3]. However, in real-world scenarios, the volume and velocity of the continuously generated data overcome the limitations of a centralized system [2], i.e., the time spent to process a single data point can be superior to the arrival of new data points. Big data techniques are successfully applied to data stream clustering algorithms [7,8], allowing data processing distribution and the scaling of learning tasks for large and incremental volumes of data. MapReduce [9] is a scalable programming model to handle big data sets. It consists of two functions, _map_ and _reduce_, which are executed in parallel over the data set, divided through the nodes of a distributed system. The MapReduce ecosystem ensures coordination, replication, fault tolerance, and other essential aspects to distribute work through unreliable hardware [9] reliably. MapReduce has been successfully applied to data clustering [10], but it was not initially designed for data streams since its functions require access to the whole data set. To handle data streams, Discretized-Stream (DS) [11] was proposed as an extension of MapReduce. It consists of ordered sequences of batches built from short time intervals of the data stream, called _micro-batches_. Instead of processing objects one by one, MapReduce buffers and processes a set of objects at once over its reliable and resilient ecosystem. Despite the effort to address the clustering of the high amount of evolving data, this is still a challenging task that involves (i) attending to the data streams' assumptions; (ii) automatically estimating the number of clusters that evolves dynamically, and (iii) using scalable models (such as MapReduce) to deal with the high volume of continuously generated data. Figure 1 shows the three main sub-fields used by the proposed work to address data clustering: MapReduce, data streams, and estimation of \(k\).