# Optimization Algorithms for Scalable Stream Batch Clustering with k Estimation
## 3 Scalable Evolutionary Clustering Algorithms
### Sesc  
Scalable Evolutionary Stream Clustering (SESC) [13] is an evolutionary algorithm able to cluster batch streams by using the largely widespread data summarization [3]. The algorithm has two main steps, the data summarization (abstraction phase), done over distributed data, and the data clustering (clustering phase), performed by applying F-EAC over the summarized data.  
The data are summarized as micro-clusters [22], which have four components: \(n\) (the number of data points), \(ls\) (the linear sum of the data points), \(ssq\) (the sum of squared data points), and \(ts\) (the timestamp of the most recent data point of the micro-cluster). Given a micro-cluster \(M\) formed by a set of data points \(M=\{x_{1},\ldots,x_{n}\}\), where \(n\) is the number of data points belonging to it, the linear sum of \(M\) is given by a vector \(ls=\sum_{i=1}^{n}x_{i}\) and its sum of square \(ssq=\sum_{i=1}^{n}x_{i}^{2}\). The representative of a micro-cluster \(M\) is given by its centroid (mean vector from data points of \(M\)) \(m=\frac{ls}{n}\). Micro-clusters have two relevant capabilities: the incrementality, which allows adding a single point \(i\) to a micro-cluster \(j\) (by summing up \(x_{i}\) with the components of \(M_{j}\), \(x_{i}+ls_{j}\) and \((x_{i})^{2}+ssq_{j}\)), and the additivity, which allows combining two micro-clusters, simply adding their three first components (\(n\), \(ls\), and \(ssq\)) and taking the maximum \(ts\). An outdated \(ts\) (related to the time window) means that the micro-cluster is no longer updated.  
Figure 3 shows an overview of the algorithm. When the \(t\)-th micro-batch is received, the objects are distributed through the nodes by the DS framework. When the accumulated objects (micro-batch) are delivered to SESC, each node works in a parallel and independent way to maintain a set of \(q\) micro-clusters. After the initial micro-clusters are obtained by applying \(k\)-means in the first portion of data, the received objects (by the node) are inserted into the micro-cluster model according to the CluStream update method [22]: a data point \(x_{i}\) is inserted into a micro-cluster \(M_{j}\) if the Euclidean distance between \(x_{i}\) and the centroid \(m_{j}\), \(dist(x_{i},m_{j})=\left\|x_{i}-m_{j}\right\|_{2}\), is less than the \(m_{j}\) boundary; otherwise, a new micro-cluster is created considering the \(ls=x_{i}\), \(ssq=(x_{i})^{\sim}2\), and \(n=1\). There is a threshold for the number of micro-clusters (\(q\)); thus, an extra action is necessary to fix the model when the limit is exceeded. They are removed if there are outdated micro-clusters (\(ts\) is outside of the time window). Otherwise, the closest pair is merged into a single micro-cluster.  
When all the nodes finish the micro-cluster model update, which is executed in parallel, a set composed of the union of all the micro-clusters (from all the nodes) is used as weighted data points by the centralized F-EAC algorithm in order to estimate the number of clusters and build a (macro-)clustering model. It is expected that the number of micro-clusters is higher than the number of macro-clusters (\(q>>k\)) and much smaller than the data stream size (\(q<<n\)). Thus, it is expected that the centralized system can handle the summarized data.