# Optimization Algorithms for Scalable Stream Batch Clustering with k Estimation
## 2 Related Work  
Our work involves three sub-fields of partitional and fuzzy clustering, as shown in Figure 1: (i) dynamic estimation of the number of clusters, (ii) scalable and distributed data clustering, and (iii) data stream clustering. Although several works approach one of these sub-fields, few works combine two, and fewer combine them all. Here, we present state-of-the-art algorithms that consider these three sub-fields separately and the few works that combine them. The \(k\)-means algorithm [15] is one of the ten most influential algorithms for machine learning [16]. It is a local search of polynomial complexity that consists of seeding a set of centroids and adjusting them until convergence or another stop criterion is achieved. Despite its simplicity and low complexity, the algorithm has two main limitations: the sensibility to the initialization of the seeds and a prefixed number of clusters (\(k\)) that must be previously defined. Several algorithms focused on overcoming these limitations for static and centralized data sets [17; 18; 19], but few for data stream clustering. The \(k\)-means algorithm inspires most of the algorithms presented here. G-means [20] is a clustering algorithm that estimates the number of Gaussian-shaped clusters in data sets. It consists of splitting the clusters from the last iteration that does not fit the null hypothesis of normality. This hypothesis is tested over the cluster's data points projected over a one-dimensional vector, which is defined by two centroids resulting from \(k\)-means with \(k=2\). Using \(k\)-means in this step is an alternative to principal component analysis with a lower computational cost. The algorithm applies the Anderson-Darling (AD) test to assess normality over the projected data, which reduces the computational complexity, thus making the algorithm faster [20]. The clusters are split until all of them achieve normal distribution. Additional stopping criteria may be adopted, e.g., a maximum value for \(k\). G-means has been used to cluster centralized and distributed data [10], but it was not applied over data streams. In this work, novel algorithms based on G-means are proposed to cluster scalable amounts of data streams in a distributed way. One of the main drawbacks of G-means, pointed out by [19], is the overestimation of \(k\) depending on the data set distribution. Data projection implies information loss, and split clusters based on a projection may produce low-quality partitions. PG-means [19] was proposed to overcome this drawback. Instead of a single projection, several projections are performed to analyze different views of the multi-dimensional space. Moreover, the whole data set is tested against the learned clusters (current model) using a goodness-of-fit test, instead of testing each cluster against the Gaussian distribution. If the null hypothesis is rejected, new prototypes are chosen, and new models are refined by the expectation-maximization (EM) algorithm. The authors showed that PG-means is more accurate than G-means, mainly in non-hyperspherical clustered data sets. PG-means can cluster data sets and estimate the number of clusters in a centralized way, but no distributed version has been presented in the literature. Moreover, PG-means was designed to cluster data sets structured in batches and cannot handle data streams. The present work also presents a novel algorithm based on PG-means to handle scalable data streams. F-EAC [17] is an evolutionary algorithm able to overcome both limitations of \(k\)-means. It builds several partition candidates (as the population), evolves them with mutation operators, which increases and decreases the number of clusters, and improves each individual with \(k\)-means. When the stop criterion is reached, the fittest model (according to a relative quality index) produced during the evolutionary search is returned. Furthermore, the random initialization of the population and the mutations promote diversity and various clustering solutions, which are improved through evolutionary search.