Using radial basis function neural network to predict dynamic resource availability in heterogeneous distributed environments

3.4.1 Decision tree for resource availability prediction

Using our enriched data in the form of {X, y}, we can model resource availability y at a time in terms of its availability attributes X. For simplicity, consider X as input and y as an output of the availability model.

In this study, our input data is numeric/nominal and output data is binary in nature. As we know that the data mining classification techniques are the most suitable for predicting binary or nominal categories [37], we consider our resource availability prediction as binary classification problem where each set of availability attributes maps to either of the two classes: available or unavailable. More specifically, we reformulate our availability prediction problem as “to find a predictive model M(X) that automatically assigns a class label y (available or unavailable) when presented with an attribute set X”. M ( X ) : X → y(1)

Since our problem is a simple two class classification problem [37], we employed Decision Tree to model y in terms of X. The motivation for choosing the Decision Tree has been multifold. First, Decision Tree effectively deals with nonlinear relationships (if any) among the attributes (here the availability attributes) without manual efforts [24]. Second, relatively little effort is required for data preparation for decision tress. Last but not the least, the modeling through Decision Tree is simple, fast and easy to understand. Among other reasons for preferring Decision Tree on other methods like neural network, is that we wanted to understand the relationship between resource availability and other its availability attributes. However, during this study, we noticed that exploring in-depth relationships of resource availability and its availability attributes requires extra efforts, and we plan it in our future work. In this paper we focus on our work on resource availability prediction. Since all of our input data was continuous, we discretized it into different intervals. During descretization, we took special care that the intervals should neither be too small to suffer from overfitting nor be too large to loose accuracy. The final discretized intervals of availability were [1,7, 7, 14, 14, 21, 21, 28, 28, 35, 35, 42, 42, 49, 49, 56, 56, 63, 63, 70, 70, 77, 77, 84, 84, 91, 91, 100].

We modeled resource availability using Classification and Regression Trees (CART) [37] in RapidMiner tool [28]. The tree induction algorithm of CART takes three parameters as inputs: the training dataset D, set of availability attributes X, and splitting criteria selection method [37]. The splitting criteria selection method defines a policy for choosing the attribute A ∈ X (along with its one value) that best separates the tuples in D into individual classes. Gini index [37] was used to select the splitting criteria. Gini index (GI) measures the impurity of D as: GI ( D ) = 1 - ∑ j = 1 m ( ρ j ) 2(2) Here, ρ _j represents the probability that a tuple in D belongs to class C _j and is given by: ρ j = number of tuples in C j number of tuples in D(3) In our case, the class label has two values: available and unavailable, so m = 2.

For each attribute A ∈ X, Gini index considers all possible binary splits. For our all continuous-valued attributes, we first sort an attribute’s values. Then, the midpoints of each pair of consecutive values are selected as split-points and GI is calculated for the midpoints. The midpoint resulting in the minimum GI for attribute A is selected as the final split-point for A. Based on the final split-points of each A ∈ X, D is partitioned into D₁ and D₂, where D₁ satisfies A≤ split-point and D₂ satisfies A> split-point. The Gini index for A is computed as a weighted sum of impurity of each partition. GI A ( D ) = | D 1 | | D | GI ( D 1 ) + | D 2 | | D | GI ( D 2 )(4) where |D|, |D₁|, and |D₂| represent number of tuples in D, D₁ and D₂, respectively.

The reduction in impurity by a binary split on A is calculated as Δ GI ( A ) = GI ( D ) - GI A ( D )(5)

The attribute resulting in maximum reduction in impurity is considered as the final splitting attribute. The final splitting attribute along with its split-point makes splitting criteria.

We used post pruning approach for pruning our CART. More specifically, ”cost complexity pruning algorithm” [37] was used.

The Naive Bayes’ Classifier estimates probability of a resource state (available or unavailable) from its likelihood and prior probability conditional to resource availability characteristics. Thus, by nature Naive Bayes’ Classifier exploits resources’ past availability patterns and properties. For our current work of two-class resource state, we describe Naive Bayes’ Classifier as follows.

Suppose C₁ and C₂ represent the two classes of resource state i.e. available and unavailable. The priori probabilities of these classes, P (C₁) and P (C₂), are calculated during characterization phase as: P (C₁) = n₁/N and P (C₂) = n₂/N, where N represents the total number of recorded events and n₁, n₂ represent the events belonging to C₁ and C₂, respectively.

As defined in Section 1, X = {x₁, x₂, x₃, . . . , x _n } represents our availability attributes. Given a set of availability attributes, X, according to Bayes’ Theorem [37]: P ( C i | X ) = P ( X | C i ) P ( C i ) P ( X )(6) The Naive Bayes’ Classifier predicts that the given X belongs to class C₁ if P (C₁|X) > P (C₂|X); otherwise C₂.

The values of availability attributes are conditionally independent of one another, given the class label. Therefore, P ( X | C i ) = ∏ k = 1 n P ( x k | C i ) = P ( x 1 | C i ) × P ( x 2 | C i ) × . . . × P ( x n | C i )(7) The probabilities P (x₁|C _i ) , P (x₂|C _i ) , . . . , P (x _n |C _i ) are estimated from the training dataset. These probabilities were estimated for individual Grid-sites. The space limit of the paper does not allow us to describe all these probabilities for individual resources here.

The Naive Bayes’ Classifier was also implemented using RapidMiner.

In current study, we used radial basis function neural network (RBF-NN) to model and predict resource availability. An RBF-NN is typical neural network (NN) that with three layers: input layer, approximation layer, and classification layer (as shown in Figure 6), but its neurons in the hidden approximation layer use radial basis function as activation function [19, 41]. The main motivation for using RBF-NN to model resource availability is its efficient and effective approximation capability. Our objective for using RBF-NN for resource availability modeling was to find an approximation function g (X) that can model resource availability y (available or unavailable) in terms its availability attributes X as g (X) : X → y. The structure of three-layered RBF-NN used in our study is shown in Figure 6. The input layer accepts values of availability attributes X = {x₁, x₂, x₃, . . . , x _n } as an input to RBF-NN. In hidden layer, each neuron j finds the Euclidean distance d _j of input X from the center C. d j = | C j - X |(8)

OPEN IN VIEWER

Fig. 6

Structure of n-j-1 RBF-NN used to model resource availability.

The center C _j was found as the center of the jth cluster determined using k-mean clustering algorithm on training dataset.

The output of the neuron j was given by applying Gaussian function (as the radial function) on d _j ψ j ( d j ) = 1 σ 2 π e - γ(9) where γ = d j 2 2 σ 2(10)

Here, σ represents standard deviation (also called width) of the Gaussian and was computed as: σ = 1 k ∑ m = 1 k | X m - C |(11) Here, k represents the number of data samples in the cluster, and X _m represents mth data sample in the cluster. The outputs of neurons in the hidden layer (ψ _j  (d _j )) are forwarded as input to output layer of RBF-NN. The output layer computes the final network response f (X) (1 for available and 0 for unavailable) as weighted sum of ψ _j  (d _j ). f ( X ) = ∑ m = 1 j ω m ψ m ( d m )(12) where ω _m represents weight for mth neuron and was obtained by solving the following linear system. [ ψ 1 ( d 1 ) ψ 2 ( d 1 ) ψ 3 ( d 1 ) … ψ n ( d 1 ) ψ 1 ( d 2 ) ψ 2 ( d 2 ) ψ 3 ( d 2 ) … ψ n ( d 2 ) ⋮ ⋮ ⋮ ⋱ ⋮ ψ 1 ( d m ) ψ 2 ( d m ) ψ 3 ( d m ) … ψ n ( d m ) ] [ ω 1 ω 2 ⋮ ω m ] = [ y 1 y 2 ⋮ y m ](13) where y _m represents state of the resource (1 for available and 0 for unavailable).

In our implementation of RBF-NN through RapidMiner tool, one layer of 18 neurons was developed. Other parameters include: learning rate=0.3; momentum=0.8. The training of RBF-NN continued till a minimum error of 0.01 was obtained or maximum 100 iterations were done.

We evaluated the prediction accuracy of our proposed model for a set of 21 resources, where 7 resources were selected at random from each of the three resource classes in Austrian Grid: dedicated resources, resources from computer labs, resources available on request. The results presented in this paper represent their average accuracy. For each resource, the accuracy of our predictions was evaluated for 290 individual days of trace period (starting from day 31; the data for first 30 days was used to enrich the data of later days). For each of the 290 days, the predictions were made for each hour of the day (0, 1, 2, 3, . . . , 23), where the exact minutes after each hour of the day were selected at random. It is noteworthy that for each prediction, the tuple corresponding to the time of prediction was excluded from the training data. This way, the proposed method was evaluated for every resource for 290 * 24 = 6960 times. The average accuracy of the 21 resources on each day is presented here as daily prediction accuracy.

Figure 7 shows daily prediction accuracy of the three proposed methods (Neural Network (ET), Decision Tree (ET), and Naive Bayes’ Classifier (ET)), three methods from related work (Pattern Matching (BT), nearest neighbor (BT), and Naive Bayes’ Classifier (BT)), and two other methods (polynomial regression (ET) and time series forecasting (ET)). Their respective prediction accuracies ranged 82.21%-99.95%, 79.95%-98.67%, 72.36%-94.77%, 51.94%-77.50%, 64%-79.81%, 66%-85%, 66.35%-86.2% and 61.97%-82.34% with standard deviation 3.88, 4.05, 4.23, 5.59,3.83, and 4.12, 4.02 and 4.19. Figure 7-avgAccu depicts overall average accuracies of these methods. The respective average accuracies of these methods were 94.36%, 91.71%, 87.87%, 66.55%, 72.83%, 80.2%, 77.49% and 74.56%. Clearly, the proposed method RBF-NN (ET) showed the highest prediction accuracy of all eight methods. The Decision Tree (ET) based method showed the second highest prediction accuracy and the Naive Bayes’ Classifier (ET) showed the third best prediction accuracy. We observed that our proposed methods using enriched trace data yielded higher accuracy than the methods using binary trace. We believe that this difference of accuracy is due to use of our identified availability attributes, which capture more information about resource availability behavior in the past. We particularly observed this difference when we compared prediction accuracies of Naive Bayes’ Classifier using enriched-trace with the same using binary-trace.

OPEN IN VIEWER

Fig. 7

Daily prediction accuracy of instant availability predictions using different prediction methods.

We also modeled nearest neighbor method and pattern matching method using enriched trace but their accuracies were less than the methods shown above. Therefore, we have not shown them in this paper.

We evaluated accuracy of duration availability predictions through the proposed methods for a set of 287 different durations beginning with 10 min. to 1440 mins (24 hrs.), i.e. {10, 15, 20, 25, . . . , 1440} minutes. Similar to our evaluations for instant availability predictions (Section 1), we evaluated our duration predictions for each 21 selected resources. We started our experiments for predictions for 10 minutes. For each resource, the date and time of the prediction was selected at random (from the available trace), and it was predicted whether the resource will be available for next 10 minutes or not. Resource’s actual availability (from the historical trace) for next 10 minutes was used as ground truth to evaluate our prediction. Similarly, experiments were conducted for other durations. The accuracy of all the resources was averaged to record the accuracy of each duration.

Figure 9 shows prediction accuracies for different time durations using eight methods. The prediction accuracies of Neural Network (ET), Decision Tree (ET) and Naive Bayes’ Classifier (ET), Pattern Matching (BT), nearest neighbor (BT), Naive Bayes’ Classifier (BT), polynomial regression (ET), and time series forecasting (ET) ranged 81.04%-99.41%, 76.08%-97.39%, 71.19%-93.64%, 51.75%-76.82%, 64.73%-84.23%, 55.72%-81.74%, 69.49%-89.55% and 65.63%-86.53% with standard deviation 3.88, 4.01, 3.11, 4.63, 2.76, 3.90, 2.86 and 3.01 respectively. Figure 9-avgAccu depicts overall average accuracies of the eight methods. Their respective average prediction accuracies were 90.06%, 86.1%, 81.66%, 64%, 74.11%, 68.69%, 78.67% and 76.15%. The RBF-NN (ET) showed the highest prediction accuracy of all eight methods. Decision Tree (ET) method showed the second highest and the Naive Bayes’ Classifier (ET) showed the third highest prediction accuracy. Once again, we observed that our proposed methods using enriched trace data yielded higher accuracy than the methods using binary trace. As described earlier, we believe that this difference of accuracy is due to use of our identified availability attributes.

OPEN IN VIEWER

Fig. 8

Average accuracy of instant availability predictions using different prediction methods.

OPEN IN VIEWER

Fig. 9

Accuracy of duration availability predictions using different prediction methods.

OPEN IN VIEWER

Fig. 10

Average accuracy of duration availability predictions using different prediction methods.

It is noteworthy that prediction accuracy of our proposed methods is not affected by the duration of a job (no such pattern is observed in our experiments). This shows that our identified availability attributes can effectively model resource availability for short as well as for long durations. The development of RBF-NN, Decision Tree and predicting the availability were both computationally efficient. For our data, using RapidMiner tool on MacBook Pro 2.3 GHz with 16 GB memory it took only 27.9 and 3.57 seconds to develop RBF-NN and Decision Tree, respectively, and a few milli seconds for each prediction.

As the process of data mining is repetitive in nature, we believe the accuracy of the proposed models will further improve when the methods will be deployed in real environment and feedback (along with more data) is used for later learning process. With our current data, the prediction accuracy decreases if we decrease data in learning phase. However, the accuracy of previous methods decreased when the trace data included more resources different availability behavior and more historical data was used in training those methods.