# Optimization Algorithms for Scalable Stream Batch Clustering with k Estimation
## 4 Scalable Distribution-Based Clustering Algorithms
### Spgms  
The second algorithm proposed, _Scalable PG-Means for Stream_ (SPGMS), is based on our scalable version of PG-means [19], called SPG-means. We chose PG-means rather than G-means as the former achieved higher-quality results on no incremental batch clustering in [19]. Similar to SGMS, SPGMS has the same incremental update and change-detection components described for the ISESC-CD in Section 2, replacing the full-clustering component with SPG-means. SPG-means consists of learning one cluster by iteration, beginning from the single-cluster partition. In each iteration, a statistical test is used to verify the goodness-of-fit of the model against the data under several projections and decide whether to create or not a new cluster. If so, the algorithm derives new clusters from the learned ones based on different prototypes: some are randomly selected (to promote diversity); others are chosen among the data points most unfit for the test (to promote intensification). After this, the algorithm refines the selected clusters and adds the best-evaluated to the current clustering model. A more detailed view of SPG-means is presented in Algorithm 2. A scalable version of the expectation-maximization (EM) algorithm [25] initializes the model \(M\) for \(k=1\) at line 2. Similar to PG-means, SPG-means executes the Kolmogorov-Smirnov test (KS) [26] under several projection vectors \(V\) (built at line 3) in order to reinforce the goodness-of-fit of data against the model. The number of projections \(r\) is an input parameter and may be defined as \(-2.6198\cdot\log(\epsilon)\), being \(\epsilon\) the desired error rate, as presented in [19]. In line 4, a distributed map job projects the data points of the whole time window (\(X\)) over the projection vectors \(V\). The result is \(|X|*r\) pairs, where the projection index \(j\) is the key, and the projected value is the pair value. Additionally, the centroids of the clusters in the model \(M\) are also projected against the same projection vectors \(V\) (line 5), but in a centralized way this time, as the number of centroids is small and can be quickly calculated. ```
Data:\(X\), confidence level \(\alpha\), number of projections \(r\) Result: clustering model \(M\)
1 let \(k\gets 1\);
2 model \(M\leftarrow\operatorname{EM}(X,k)\);
3\(V\leftarrow\) draw randomly \(r\) projection vectors;
4\(p_{j}\leftarrow\) projection of \(X\) against \(v_{j}\), \(\forall j\in V\);
5\(m_{j}\leftarrow\) projection of \(M\) against \(v_{j}\), \(\forall j\in V\);
6\(ks_{j}\leftarrow\operatorname{KS}(p_{j},\,m_{j},\,\alpha)\), \(\forall j\in V\);
7 ifno\(ks_{j}\) rejected null hypothesis, \(\forall j\in V\)then
8 return \(M\);
9
10 end if
11 for\(l=1..10\)do
12\(c_{k+1}\leftarrow\) select a new prototype;
13\(M^{\prime}_{l}\leftarrow\operatorname{EM}(X,M+c_{k+1})\);
14
15 end for
16\(M\leftarrow\) best \(M^{\prime}_{l}\) according to likelihood;
17\(k\gets k+1\);
18 if\(k=k_{max}\)then
19 return \(M\);
20
21 end if
22 go to line 3;
```  
**Algorithm 2**SPG-means overview  
The sixth line of Algorithm 2 consists of testing the goodness-of-fit of projected data against the projected model. In order to obtain the KS statistics, each \(p_{j}\) for all \(j\in V\) must be sorted and ranked. The sort and rank implementations of Apache Spark [25] were used, and its return is a rank index for each object of the data set. The projected data point and rank index are used in a map job to obtain: (i) the cumulative probability of each data point, given the distribution mixture of the projected model \(m_{j}\), and (ii) the distance between the cumulative probabilities of the projected data and model. Then, a reduce job is used to apply the supremum math function in order to obtain the KS statistics. Finally, the result is compared with the critical values to reject or accept the null hypothesis of both data and model belonging to the same distribution mixture.