# Bootstrap-CURE: A Novel Clustering Approach for Sensor Data--An Application to 3D Printing Industry
## 5 Methodology
### Preprocessing
#### 5.1.1 The Proposed Bootstrap-CURE Approach  
As said before, the CURE algorithm accelerates the hierarchical clustering processes so as to increase the capacity to deal with bigger datasets, but this is still not sufficient to deal with sensor datasets that provide millions of readings per second. In this work, a modification of CURE is proposed to overcome this limitation. (Figure 2 shows an overview of the proposal.) The proposed modification is based on the well-known mathematical fact that, given a data set of size \(n\), decomposed in \(S\) disjunct subsets of size \(n_{s}\) such that  
\[n=\sum_{s=1}^{S}n_{s} \tag{1}\]  
then the square of the total size is bigger than or equal to the sum of squares of individual components  
\[n^{2}=(\sum_{s=1}^{S}n_{s})^{2}\gg\sum_{s=1}^{S}{n_{s}}^{2} \tag{2}\]  
Consequently, any quadratic algorithm running on the entire dataset of size \(n\) will be more expensive from the computational point of view than its replication on the \(S\) samples. There is no need to run any experiment to demonstrate this property since it is based on an analytical geometrical property of the sum of squares. This means that applying the bootstrap technique to hierarchical clustering by repeating clustering of small samples from the original dataset several times will surely decrease the complexity of the total process as compared to the global clustering of the entire dataset. The authors introduce the _bootstrap_ technique in the process in the following. As mentioned earlier, the CURE initialization step in the original definition of the method involves taking a small sample of data, applying hierarchical clustering on it, and further identifying a set of representative points to be used to extend the clusters to the whole dataset. The whole CURE algorithm is based on the idea that the initialization sample is representative of the total population and that other objects assigned in the completion step follow the same cluster structure as the one discovered in the sample. This is quite a strong hypothesis that might not necessarily hold when we are sampling a subset of data, sufficiently small to process hierarchical clustering (quadratic) in a big data dynamic environment. Hence, the authors propose to use the _bootstrap_ principle to extract \(S\) small samples (\(n_{s}\ll n\)), with \(n\) being the size of the original dataset and \(n_{s}\) being the size of the \(s\)th sample from the initial dataset for the initial clustering step. This proposal is based on the idea that each sample is clustered under a hierarchical method independently, thus resulting in \(S\) dendrograms. A subsequent intermediate step of super classification is proposed as well to encompass the results of independent sample clusters. The super classification performs over the set of class representatives (centroids) coming from all the samples processed and thus the final set of clusters is more robust than the original CURE algorithm and eventually, has better representation and lower computational cost. To assign class labels to the remaining objects, the following steps are followed:  
1. Draw \(S\) random samples of a single reference dataset \(I\), each of same size \(n_{s}\), without replacement. 2. Subject each sample to hierarchical clustering (in this work with _Euclidean_ distance and _Ward's_ method), and obtain the \(S\) dendrograms. Figure 2: Comparison between original and _bootstrap–CURE_ processing. Cut the \(S\) sample dendrograms and retrieve a set of clusters for each sample. In Section 5.2, a method to automatically determine the number of clusters in each dendrogram is proposed. 4. Compute the centroid of all clusters found in the previous step and build a final dataset with all centroids. 5. Super-classification step: Apply hierarchical clustering on the centroids dataset. 6. Cut the resulting dendrogram by using the automatic criterion proposed in Section 5.2 and find the set of centroids belonging to each super-class. 7. Compute the super-centroids of each super-class. 8.