# Optimization Algorithms for Scalable Stream Batch Clustering with k Estimation
## 4 Scalable Distribution-Based Clustering Algorithms
### Sgms  
Scalable G-Means for Stream (SGMS) is based on the scalable version of G-means (SG) [10]. The algorithm has the same incremental update and change-detection components described for the ISESC-CD in Section 2 but adopts the SG procedure in the full-clustering component instead. When its change-detection component triggers, the full-clustering component is executed over the data in the time window (\(X\)). It applies SG to estimate the number of clusters and build a new model. Starting from one cluster with all the data, SG consists of iteratively splitting the unstable clusters of the model, i.e., clusters that did not fit the Gaussian distribution. The process is repeated until all clusters fit the Gaussian distribution with a prior-defined confidence level and become stable. Other stopping criteria may be adopted, e.g., a maximum number of splits or iterations. In order to reduce the computational cost, the goodness-of-fit tests are applied over one-dimensional projections of the clusters. G-means is guided by the goodness-of-fit of Gaussian distribution over the clusters, which assumes that the structures of the data sets resemble this distribution. Consequently, such an assumption holds for SG and SGMS. An overview of SG is presented in Algorithm 1. It starts with two sets: \(A\) for unstable clusters and \(B\) for stable ones. Thus, the current partition of each iteration is defined by \(A\cup B\). The first cluster \(c_{1}\) is built from the mean of \(X\) and added to \(A\). The algorithm begins its iterations by assigning each data point with its closest cluster of the current partition using a map job (line 5). Following this, a subset \(w_{j}\) of data points is created for each unstable cluster \(a_{j}\), \(\forall j\in A\). A job maps each data point \(x_{i}\) into a pair of \(<\)_j_, \(x_{i}\)\(>\), where \(j\) is the index of the assigned subset. At line 7, the scalable version of \(k\)-means is executed for each subset \(w_{j}\) with \(k=2\), as defined in the original G-means [20]. Usually, during the execution of the scalable version of \(k\)-means, each data point is mapped with the index of its cluster as a key [24]. However, the clustering of each subset \(w_{j}\) must be done independently, i.e., isolated from the others. Such independence is provided by mapping the data points with keys formed by the index of their clusters and their subset index \(j\). This independence allows the partitioning of all clusters at once by a single pair of maps and reduce jobs by \(k\)-means iteration. The result is a set of models \(m_{j}\) obtained for each \(w_{j}\) subset, which is used to create a collection of projection vectors [20] (line 8). In line 9, a map job is used to project each data point within \(w_{j}\) against its projection vector \(v_{j}\). After this, each subset \(p_{j}\) of the projected data points is shuffled through the distributed system to fit a single node and allow the Anderson-Darling (AD) statistical test application. Each \(p_{j}\) is sorted in parallel by the nodes, and the test is applied with the confidence level \(a\), yielding a set of statistics \(t_{j}\) (line 10). For each \(j\), if the statistics of \(t_{j}\) accepts the null hypothesis that \(p_{j}\) fits the Gaussian distribution, its original cluster \(a_{j}\) is considered stable and moved to \(B\). Otherwise, the cluster \(a_{j}\) is split, which means adding into \(A\) the clusters \(m_{j}\) resulting from \(w_{j}\), and deleting their original cluster \(a_{j}\). The iterations continue until the algorithm reaches a stop criterion (line 4). The algorithm stops if all clusters are stable or a predefined maximum number of iterations is reached in this work. \begin{table}
\begin{tabular}{l l} \hline \hline
**Algorithm** & **Worst Case** \\ \hline SESC & \(O((n_{mb}*d*mc)/m)\) \\ \hline ISESC & \(O((n_{w}*d*k_{m}*i*g*|P|)/m)\) \\ \hline ISESC-CD & \(O((n_{w}*d*k_{m}*i*g*|P|)/m)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Asymptotic computational complexity analysis of the evolutionary algorithms.