# Optimization Algorithms for Scalable Stream Batch Clustering with k Estimation
## 3 Scalable Evolutionary Clustering Algorithms
### Isesc  
Differently from SESC, the _Incremental Scalable Evolutionary Stream Clustering_ (IS-ESC) [13] was designed to cluster raw data directly instead of summarizing them into micro-clusters. Storing the data requires more resources such as memory and processing time than micro-clusters but provides more information and higher accuracy. Distributed and scalable frameworks (such as MapReduce) were designed to provide such resources. SF-EAC provides the first macro-clustering model over an initial data portion, using distributed and parallel computation. These macro-clusters use a data structure extended from the micro-cluster concept, providing incrementality and additivity capabilities. Besides the components \(n\), \(ls\), \(ssq\), and \(ts\), the macro-cluster structure also keeps the lowest simplified silhouette index (SS) value (\(lss\)) among its data points. The SS index considers the compactness  
Figure 3: SESC overview [13]. and the separation of the data point \(x_{i}\) belonging to a micro-cluster \(M_{j}\), which are represented by two terms, \(a_{i}\) and \(b_{i}\), respectively. Specifically, the \(a_{i}\) term is given by \(dist(x_{i},m_{j})\) and \(b_{i}=dist(x_{i},m_{c})\), where \(m_{c}\) is the closest neighbor micro-cluster centroid to \(m_{j}\). Then, the SS index is calculated as \(SS(x_{i})=1-\frac{a_{i}}{b_{i}}\). The average SS index for all data points gives an estimate of full clustering quality, which ranges from 0 to 1 (under \(k\)-means assumption). The cluster radius (\(rd\)) can be calculated according to Equation (1), which results in the standard deviation, and \(\alpha\) defines how many standard deviations compose the radius (\(\alpha\geq 1\)). \[rd=\alpha\sqrt{\frac{ls}{n}-(\frac{ss}{n})^{T}(\frac{ss}{n})} \tag{1}\]  
Figure 4 presents an overview of ISESC. After SF-EAC clusters the first micro-batch, the incremental update component of the algorithm updates the model with new data from the following micro-batches. If the component detects a change (concept drift) during the update, the full-clustering component (SF-EAC) is executed to estimate the number of clusters and build a new model. Inspired by FEAC-Stream [23], the incremental update component searches for evidence of a significant change (e.g., the emergence of a new cluster) and, if there is none, updates the clusters incrementally. For each data point, the component calculates the shortest Euclidean distance between the point and the centroids (\(d\)), and its SS value (\(ss\)) [21] associated with the closest cluster. Evidence of a significant change is a data point for which \(d\) is higher than the radius of the closest cluster (\(rd\)) or has an SS value inferior to the lowest SS value of the points of the associated cluster (\(ss<ls\)). If any data point of the micro-batch matches this evidence criterion, the full-clustering component is executed; otherwise, the associated cluster is updated, and the incremental update component continues. All distances, SS, and tests of evidence are made in a distributed fashion through map jobs of MapReduce. The evidence criterion is represented and visualized as two boundaries for each cluster. Figure 5 is a partial representation of a bi-dimensional clustering model, where \(C_{3}\) and \(C_{4}\) are cluster centroids and \(p_{i}:i\in\{1,2,3,4\}\) are data points. The dotted lines represent the clusters' radius (\(rd\)) boundaries, and the dashed lines represent the irregular and convex lowest simplified silhouette (\(lss\)) boundaries given by the SS function. In this illustrative scenario, \(p_{1}\) is within the \(lss\) boundary of \(C_{3}\) but not within that of \(rd\). The \(lss\) boundary can assume such irregular and wide areas that may even encompass new clusters, and then this object will be treated as evidence of a significant change. In turn, \(p_{2}\) is within overlapping \(rd\) boundaries but is not within any \(lss\) area. Inserting \(p_{2}\) in either \(C_{3}\) or \(C_{4}\) may not be considered correct, as it does not truly merge these two clusters.