# Profit-Efficient Elastic Allocation of Cloud Resources Using Two-Stage Adaptive Workload Prediction
## 4 Prediction Method
### Adaptive Two-Stage Multi-Neural Network Based on the LSTM Prediction Method  
In this study, we focus on prediction of the task arrival workload in the Wikimedia service, as shown in Figure 5. The workload trace of the Wikimedia service contains the number of received HTTP requests, aggregated into one-hour intervals. As mentioned in Section 2, multiple-model methods can classify the workload into suitable categories and use different prediction models to fit the different categories of the workload, according to the workload's characteristics. Although the workload presents some randomness with increasing and decreasing values, we can classify the workload into two categories--namely, uphill (workload increasing) and downhill (workload decreasing)--as shown in Figure 6.  
Figure 4: Architecture of a long short-term memory (LSTM) prediction model. Based on the classification results shown in Figure 6, we propose a new workload prediction method, named the adaptive two-stage multi-neural network model based on LSTM (ATSMNN-LSTM). The structure of the ATSMNN-LSTM is shown in Figure 7.  
The proposed workload prediction method contains two main processes: (1) an adaptive classification process, which uses an NN for binary classification to classify the workload input data into the uphill or downhill category, according to the workload change  
Figure 5: Task arrival workload of the Wikimedia service. Figure 6: Classification of the task arrival workload for the Wikimedia service. Figure 7: Architecture of the proposed adaptive two-stage multi-neural network model based on long short-term memory (ATSMNN-LSTM) method. trend; and (2) a classification prediction process, in which, according to the workload classification results, the workload input data are routed to the corresponding sub-prediction model (e.g., uphill LSTM or downhill LSTM model) to predict the future workload. According to Figure 7, the workload classification task poses the following challenge: an NN for binary classification and two LSTM prediction models must be trained. However, the task arrival workload only contains time and numerical information and, so, it is difficult to build sub-training data sets for the two considered categories (i.e., uphill and downhill data sets) and label the two-category workload training data set for model training. The manual annotation method for building the two category sub-training data sets and labeling the two-category workload requires significant human and material resources. Thus, unsupervised machine learning is a suitable method for this problem. The \(k\)-means algorithm [35] is a typical unsupervised clustering algorithm, which uses the Euclidean distance--defined as \(d_{ij}=\sqrt{\sum_{k=1}^{S}\left(x_{ik}-x_{jk}\right)^{2}}\), where \(i\) and \(j\) are the labels of the \(i\)th and \(j\)th categories, respectively--to cluster the data into different categories. In Figure 8, three groups of workload data are shown, denoted as G1, G2, and G3. Here, G1 and G3 are uphill categories, while G2 is the downhill category. Figure 8 shows that the maximum distance between G1 and G2 (\(d_{12}^{max}\)) is smaller than that between G1 and G3 (\(d_{13}^{max}\)). Due to the use of the Euclidean distance as the clustering metric in the \(k\)-means algorithm, G1 and G2 might be grouped into the same cluster, while G1 and G3 could be assigned to different clusters. This may confuse the \(k\)-means algorithm when working with the original data. Therefore, a feature that represents the workload change trend is needed. Based on Figure 8, we consider that the first-order gradient can effectively represent the workload change trend. The first-order gradient feature at time slot \(t\) in a discrete-time system can be calculated as follows:  
\[\
abla x(t)=\frac{dx(t)}{dt}=\frac{x(t)-x(t-T)}{t-(t-T)}=\frac{x(t)-x(t-T)}{T}, \tag{10}\]  
where \(T\) is the time interval between two adjacent time points for workload data collection.