Web service QoS prediction by neighbor information combined non-negative matrix factorization

Abstract

Strongly promoted by the development of Service-Oriented Computing and Cloud Computing technologies, a large number of functionally equivalent web services emerge on the Internet. Quality of Service (QoS) is becoming a key factor to distinguish different web services. Although many Collaborative Filtering (CF) based approaches are recently proposed to predict the QoS of web services, the prediction accuracy are not satisfactory, since they rarely take full use of the neighbor information and latent feature information contained in the historical QoS data. Especially when the real-world QoS data is highly sparse, the previous works fail to detect the actual relationships between services. In this paper, we present a novel hybrid web service QoS prediction approach that systematically combines the memory-based CF and model-based CF. Firstly a non-negative matrix factorization model for web service QoS prediction is presented. Then an Expectation-Maximization (EM) based approach is designed to learn the model for making further prediction. The service neighbor information, which integrates the direct similarity and transitive indirect similarity of services to handle the data sparsity problem, is introduced into EM based learning process to make the prediction results more accurate. Large-scale real-world experiments are conducted using the WSDREAM QoS dataset. The experimental results demonstrate that our approach can achieve better prediction accuracy than other state-of-the-art approaches.

Keywords

Web service QoS prediction collaborative filtering non-negative matrix factorization EM Data sparsity similarity transition

1 Introduction

Web service is a platform-independent, loosely coupled and self-described software component, which is designed to support interoperable machine-to-machine interaction over a network via XML-based standard interfaces and communication protocols [1]. Strongly promoted by the emerging Service-Oriented Architecture (SOA) and Cloud Computing technologies, web services are broadly developed and utilized to build service-oriented application over the Internet. A service-oriented application generally consists of multiple atomic services, which may be provided by geographically distributed developers all over the world, integrating and interacting with each other [2]. With the rapid growth of web service, a large number of functionally equivalent web services emerge on networks. Quality of Service (QoS), which is a set of properties that describe the non-functional characteristics of web services, becomes a major concern for service customers when deciding which services should be selected to form the application [3 –5].

In practical application, the user-dependent QoS properties of web services (e.g., response time, throughput, etc.) may vary widely among users due to their different network conditions, heterogeneous environments and locations [6]. Personalized QoS values evaluation are thus essential for assisting QoS based services selection approaches [7, 8]. The most straightforward approach to obtain the QoS values of web services is to make an exhaustive evaluation on all the candidate services in the client-side. However, the exhaustive approach is although accurate but time consuming and resource consuming, besides the invocations on some services may be charged, which make it impractical in real world [9, 10].

Inspired by the success of Collaborative Filtering (CF) techniques achieved in many commercial recommender systems such as Amazon, YouTube and Netflix etc, many recent research works employ the CF based approaches to predict the QoS of web services [11 –15]. CF mainly consists of two types: memory-based CF [10 , 14] and model-based CF [1 , 15]. Memory-based CF commonly utilize the information of similar users or items to predict the unknown values of target users or items. For instance, suppose that user A and B have similar ratings on some movies, then if user A provided a high rating on a movie, the rating of user B on this movie should probably be predicted to be a high score and this movie should consequently be recommended to user B. Similarly, the historical QoS data could be applied to predict the QoS of the web services for those users who have not invoked them before. Model-based CF, which is also known as matrix factorization technique, presume that users experiences are determined by some latent factors, then employ a linear factor model to fit the observed historical data and use this factor model to make further predictions for users. Generally speaking, Memory-based CF make use of the similarity relationship among users or items which is known as local information of user-item matrix, while Model-based CF utilize the global information of the whole matrix for making prediction. However, neither of the memory-based CF nor model-based CF can achieve a satisfactory prediction accuracy, especially when the historical QoS data are highly sparse, as is the case in real-world system. Since the number of users and web services on the Internet are very huge, most users may only invoked few web services, which make the user-service QoS matrix extremely sparse.

In this paper, we present a novel web service QoS prediction approach by systematically combining the local neighbor information and the global latent feature information of the observed QoS data. Firstly, based on the assumption that the observed QoS data are combinations of a linear model and Gaussian noise, a matrix factor model for web service QoS prediction is presented. Then an EM (Expectation-Maximization) estimation scenario is designed to learn the model based on the observed QoS data. Finally, we propose a neighbor information combined non-negative matrix factorization algorithm NCNMF to implement the scenario. The main contributions of our work are three-fold:

(1) We establish the non-negative matrix factorization model for web service QoS prediction and employ an EM based approach to learn the model, which is very important to make the prediction results be more interpretable compared with other matrix factorization based approaches.

(2) The proposed NCNMF QoS prediction algorithm exploits the advantages of memory-based approach and model-based approach, which fully utilizes the local and global information of the observed QoS data and is proved to be more accurate than other state-of-the-art algorithms by conducting a large-scale real-world experiment.

(3) To attack with the data sparsity challenge, we reform the traditional similarity computation method by introducing a similarity transition approach to evaluate the indirect similarity between services. By integrating the direct and indirect similarity, the relationship between services can be more accurately detected for improving the effectiveness of the service-based CF towards a highly sparse data condition. Besides, the similarity transition approach can be applied to user-based CF either.

2 Problem statement and methodology

QoS attributes are a set of non-functional properties that usually be used to describe the quality of web services. The generic QoS attributes include price, response time, throughput, reliability and availability etc. [16]. Given an QoS prediction system consisting of n web services and m service users, the n × m user-service QoS matrix R can be used to represent the historical web service invocation QoS data of users, in which each entry R_ij denotes the value of a certain QoS property of web service i observed by user j. Table 1 illustrates a simple example of user-service QoS matrix, where each entry is the value of response time of a web service observed by a user. Since most service users only invoked few services in real world, the QoS matrix R contains many missing entries (e.g., R₁₁ and R₁₃ in Table 1). The target of prediction system is to obtain the missing values by employing the observed values in the QoS matrix.

2.1 QoS prediction model

We hope to find a low-dimensional linear model X = UV to approximate the QoS matrix R by matrix factorization technique, then the missing value can be predicted as the inner product of the ith row of U and the jth column of V. In the model, U is a n × k matrix and V is a k × m matrix, where k represents the number of factors. More specifically, U is called QoS basis matrix and denoted as column vectors $U = (\vec{U_{1}}, \vec{U_{2}}, \dots, \vec{U_{k}})$ , where $\vec{U_{d}} (d = 1, 2, \dots, k)$ represents the dth factor vector’s impact factor on the QoS of services. V is called weight matrix, in which each column represents the weights assigned to these k factors by user, reflecting the users affinities for these factors. Hence, the QoS of service i invoked by user j can be predicted as a linear combination of the impact factor of factor vectors on service i, with the weight coefficients assigned by user j, which can be depicted as Equation (1). $X_{ij} = \sum_{d = 1}^{k} U_{id} \times V_{dj}$ (1)

Where X_ij is the predicted QoS of service i invoked by user j, U_id is the impact factor of the dth factor on the QoS of service i, V_dj is the weights assigned by user j to the dth factor.

The entries in matrix U should be in a non-negative range, due to the real-world QoS properties (such as response time, throughput, reliability and availability etc.) should only take non-negative values. As referred above, the QoS of a service observed by user can be regarded as a linear combination of the impact factor of factor vectors on the service. In other words, the whole QoS experience of users on a service can be formed by combining their part experience on these factor vectors. To coordinate with the intuition that the whole is generated by additively combining the parts, the entries in V should be non-negative too. Like [1 , 18], we presume that the users QoS experience can be represented as the low-dimensional linear model X plus a Gaussian distributed noise matrix Z, where Z_ij follows a Gaussian distribution with zero mean and standard deviation σ_ij. Hence, the non-negative matrix factorization model for QoS prediction can be expressed as follows: $\begin{matrix} R = X + Z, Z_{ij} \sim N (0, σ_{ij}^{2}) \\ X = UV, U_{ij} ⩾ 0, V_{ij} ⩾ 0 \\ 1 ⩽ i ⩽ n, 1 ⩽ j ⩽ m . \end{matrix}$ (2)

For simplicity, we assume that the standard deviation of Gaussian distribution σ_ij are all equal to σ. Thus R_ij follows a Gaussian distribution with X_ij mean and σ standard deviation, denoted as R_ij ∼ N (X_ij, σ²). From the above definition, X_ij are unknow parameters that should be estimated.

2.2 Parameter estimation of QoS prediction model

Since R_ij ∼ N (X_ij, σ²), the probability density function of R_ij can be expressed as follows: $P (R_{ij}) = \frac{1}{\sqrt{2 π σ}} e^{\frac{- {(R_{ij} - X_{ij})}^{2}}{2 σ^{2}}}$ (3)

If we assume that the QoS of different services observed by users are independent, then the entries in QoS matrix R are statistically independent. Therefore, the likelihood of the variable X given R follows as $like (R | X) = \prod_{i = 1}^{n} \prod_{j = 1}^{m} \frac{1}{\sqrt{2 π σ}} e^{\frac{- {(R_{ij} - X_{ij})}^{2}}{2 σ^{2}}}$ (4)

Then, the log-likelihood function is given by

$\begin{matrix} log like (R | X) \\ = - mnlog (\sqrt{2 π} σ) - \frac{1}{2 σ^{2}} \sum_{i = 1}^{n} \sum_{j = 1}^{m} {(R_{ij} - X_{ij})}^{2} \end{matrix}$ (5)

Thus, if the QoS matrix R is fully observed, the X can be estimated by maximizing the above log-likelihood function. $X = arg max_{X} log like (R | X)$ (6)

In real-world system, the QoS matrix R contains many missing values, which means the matrix is incomplete. To deal with this situation, we employ an EM procedure to estimate the model X by maximizing the available values in QoS matrix.

EM algorithm is usually used to find the maximum likelihood parameters of a model when the data are incomplete [19, 20]. EM algorithm commonly includes two steps in every iteration: Expectation step and Maximization step. In Expectation step, the expected expression of complete-data log-likelihood is computed by using the estimated value of unobserved data. In Maximization step, the model parameter is estimated by maximizing the expected expression obtained in current Expectation step, then the estimated parameter will be utilized in the Expectation step of next iteration. By repeatedly executing the Expectation step and Maximization step, the model parameter will ultimately be convergent.

We can denote the observed data in QoS matrix R as R^o and unobserved data as R^u. If the estimated value of X in the tth iteration of the EM procedure is denoted as X^t, then the (t + 1)th iteration includes two steps:

A . Expectation step computes the expected express of complete QoS matrix data log-likelihood, denoted as: $Q (X | X^{t}) = E (log like (R^{o}, R^{u} | X))$ (7)

Let $L = - mn log (\sqrt{2 π} σ)$ and take Equation (5) into (7), it follows that: $\begin{matrix} Q (X | X^{t}) & = & E (L - \frac{1}{2 σ^{2}} \sum_{R_{ij} \in R^{o}} {(R_{ij} - X_{ij})}^{2}) \\ + E (L - \frac{1}{2 σ^{2}} \sum_{R_{ij} \in R^{u}} {(R_{ij} - X_{ij})}^{2}) \\ = & 2 L - \frac{1}{2 σ^{2}} {(\sum_{R_{ij} \in R^{o}} (R_{ij} - X_{ij})}^{2} \\ + \sum_{R_{ij} \in R^{u}} E (R_{ij} - X_{ij})^{2}) \end{matrix}$ (8)

Since ∀R_ij ∈ R^u, $R_{ij} \sim N (X_{ij}^{t}, σ^{2})$ then

$\begin{matrix} \sum_{R_{ij} \in R^{u}} E {(R_{ij} - X_{ij})}^{2} \\ = \sum_{R_{ij} \in R^{u}} ({(X_{ij}^{t} - X_{ij})}^{2} + σ^{2}) \end{matrix}$ (9)

Let the number of elements in R^u be C and take Equation (9) into (8), it follows that:

$\begin{matrix} Q (X | X^{t}) = 2 L - \frac{C}{2} - \frac{1}{2 σ^{2}} {(\sum_{R_{ij} \in R^{o}} (R_{ij} - X_{ij})}^{2} \\ + \sum_{R_{ij} \in R^{u}} (X_{ij}^{t} - X_{ij})^{2}) \end{matrix}$ (10)

B . Maximization step estimates the variable X by maximizing Q (X|X^t). $\begin{matrix} X & = & arg max_{X} Q (X | X^{t}) = arg max_{X} (2 L - \frac{C}{2} - \frac{1}{2 σ^{2}} \\ (\sum_{R_{ij} \in R^{o}} (R_{ij} - X_{ij})^{2} + \sum_{R_{ij} \in R^{u}} (X_{ij}^{t} - X_{ij})^{2})) \end{matrix}$ (11)

Since m, n, σ and C are all constant, therefore,

$\begin{matrix} X = arg min_{X} \\ (\sum_{R_{ij} \in R^{o}} (R_{ij} - X_{ij})^{2} + \sum_{R_{ij} \in R^{u}} (X_{ij}^{t} - X_{ij})^{2}) \end{matrix}$ (12)

The complete matrix in (t + 1)th iteration is denoted as R^t+1, where the missing entries R_ij ∈ R^u are replaced with the estimated parameter $X_{ij}^{t}$ obtained in the tth iteration. By taking Equation (1) into (12), we have $\begin{matrix} X & = & arg min_{X} (\sum_{i = 1}^{n} \sum_{j = 1}^{m} {(R_{ij}^{t + 1} - X_{ij})}^{2}) \\ = & arg min_{X} (\sum_{i = 1}^{n} \sum_{j = 1}^{m} {(R_{ij}^{t + 1} - \sum_{d = 1}^{k} U_{id} \times V_{dj})}^{2}) \\ = & arg min_{X} (∥ R^{t + 1} - UV ∥_{F}^{2}) \\ U_{ij}, V_{ij} ⩾ 0; 1 ⩽ i ⩽ n, 1 ⩽ j ⩽ m \end{matrix}$ (13) where ∥ • ∥ _F represents the Frobenius norm of matrix.

According to Equation (13), we can obtain the estimated value of X in current maximization step by finding the non-negative QoS basis matrix U and the weight matrix V that minimize $∥ R^{t + 1} - UV ∥_{F}^{2}$ . Taking $∥ R^{t + 1} - UV ∥_{F}^{2}$ as the object function, we can find the matrix U and V by performing non-negative matrix factorization(NMF) on R^t+1.

The updating formulas of NMF were presented in [21, 22]: $\begin{matrix} V_{dj} \leftarrow V_{dj} \frac{{(U^{T} R^{t + 1})}_{dj}}{{(U^{T} UV)}_{dj}} \\ U_{id} \leftarrow U_{id} \frac{{(R^{t + 1} V^{T})}_{id}}{{({UVV}^{T})}_{id}}, U_{id} = \frac{U_{id}}{\sum_{i} U_{id}} \end{matrix}$ (14)

In [22], Lee proves that the object function $∥ R^{t + 1} - UV ∥_{F}^{2}$ will be nondecreasing and ensured to converge using the above updating formulas. Meanwhile, the elements in matrix U and V are ensured to be non-negative.

After performing NMF on R^t+1, we will obtain the approximate matrix X (X = UV) of R^t+1. The estimated model parameter X will be used in next Expectation step.

In summary, the process of estimating the model parameter X by EM procedure can be defined as follows. Firstly, the model parameter X is initialized with some random numbers. Then, in each iteration, the missing entries in QoS matrix R are replaced with the corresponding values in the current estimated X which are obtained in last expectation step. Further, in the maximization step, we perform NMF on the filled-in matrix to obtain the approximate matrix UV to update the model parameter X. After several iterations, the model parameter X will be convergent.

2.3 QoS prediction algorithm NCNMF

Matrix Factorization algorithm like NMF can effectively mine the latent feature information of user-service QoS matrix for prediction. However, NMF algorithm is poor at detecting the associations among a set of closely related similar users or services [1], which can significantly improve the QoS prediction accuracy. Especially when the available QoS matrix is very sparse, as is the case in real-world system, neither of the NMF approach nor neighbor based approach can achieve an optimal prediction accuracy. In this section, we present a hybrid QoS prediction approach that systematically combines neighbor based approach and NMF approach, which is named NCNMF (Neighbor Information Combined Non-negative Matrix Factorization).

In our approach, we firstly predict the missing entries in R by IPCC-ST approach (Item-based collaborative filtering based on similarity transition) to obtain a filled-in complete QoS matrix. Then, the model parameter X of the EM procedure referred in Section 2.2 is initialized with the filled-in QoS matrix obtained by IPCC-ST instead of the random numbers. Our approach introduces the neighbor priori information into the EM procedure of estimating the model parameter, thus the convergence speed and quality are improved and the QoS prediction accuracy and efficiency are ensured.

The IPCC-ST approach mainly contains two parts: service similarity computation and item-based collaborative filtering prediction.A . Service similarity computation

The Pearson Correlation Coefficient (PCC) has been widely employed for similarity computation in many recommender systems, since PCC can achieve high accuracy and can be easily implemented [14]. The similarity between different services is computed as follows: $sim (i, r) = \frac{\sum_{j \in U_{ir}} (R_{ij} - {\bar{R}}_{i}) (R_{rj} - {\bar{R}}_{r})}{\sqrt{\sum_{j \in U_{ir}} {(R_{ij} - {\bar{R}}_{i})}^{2}} \sqrt{\sum_{j \in U_{ir}} {(R_{rj} - {\bar{R}}_{r})}^{2}}}$ (15)

Where sim (i, r) is the similarity between service i and r. sim (i, r) is in the interval of [–1, 1], where a larger value indicates a higher service similarity. U_ir = U_i ∩ U_r is the subset of users who invoked both service i and service r. R_ij is the historical QoS value of service i observed by user j, ${\bar{R}}_{i}$ represents the average QoS value of service i observed by different users.

Figure 1 illustrates the services similarity graph generated from the instance of user-service QoS matrix shown in Table 1. In Fig. 1, a total of 4 services (nodes s₁ ∼ s₄) are connected with 6 edges, where the value of each edge represents the similarity between two services connected by this edge. After similarity calculation, a set of Top-N similar services can be identified as the neighbor of target services based on the PCC values. However, due to the number of users and web services on the Internet are very huge, most users may only invoked few web services, which make the user-service QoS matrix extremely sparse. In this case, many users may have few co-invoked web services and many services may have few common users (e.g., s₁ and s₂ in Table 1 have no common users). The PCC, which calculates the similarity based on the common set, may underestimates or overestimates the similarities between services. For instance, s₁ and s₂ in Table 1 have no common users, the similarity of them is calculated as 0, which may be a underestimated value, while s₁ and s₄ only have one common users, the similarity is overestimated as 1 by PCC.

To attack with the inaccurate similarity computation problem caused by data sparsity, we propose a similarity transition approach to evaluate the IndirectSimilarity between services. The IndirectSimilarity between two services indicates the relationship transitted from other services who have common users with both of the two services. The similarity transition, which is inspired from the idea of Social Network, is based on the assumption that if A is similar with B and B is similar with C, then A is similar with C to some extent, even they have no common users. To distinguish with the Indirect Similarity, the similarity between services computed by PCC is named Direct Similarity.

Figure 2 shows the similarity transition graph of web services, where each node represents a web service, and the value of each edge indicates the Direct Similarity between two services connected by this edge, the path that connect two indirect services is called transitive path. Due to the decay property of similarity transition, only one middle service is included in each transitive path. The Indirect Similarity between service i and service r in our approach is expressed as the integration of all direct similarity on the transitive paths, denoted as: ${sim}_{I} (i, r) = \frac{\sum_{k = 1}^{n} {sim}_{D} (i, k) {sim}_{D} (k, r)}{n}$ (16)

sim_D (i, k) indicates the Direct Similarity between service i and k,which is computed by PCC shown in Equation (15). sim_I (i, r) represents the Indirect Similarity between service i and r, n is the number of transitive paths.

Since different data sets may have different natures, we employ a similarity weightα_ir to balance the Direct Similarity and the Indirect Similarity when computing the similarity between service i and r. The final similarity is defined as: ${sim}^{'} (i, r) = α_{ir} {sim}_{D} (i, r) + (1 - α_{ir}) {sim}_{I} (i, r)$ (17)

Where the weight α_ir is computed as: $α_{ir} = \frac{| U_{i} \cap U_{r} |}{| U_{i} \cup U_{r} |}$ (18)

Where |U_i ∩ U_r| is the number of common users that have invoked both of service i and r, |U_i ∪ U_r| is the number of users that have invoked either of service i or r. Equation (18) indicates that when the number of common users |U_i ∩ U_r| is small, the similarity weight α_ir will decrease the contribution of Direct Similarity while increasing the contribution of Indirect Similarity in similarity evaluation. Since the value of α_ir is in the interval of [1], and both of sim_D (i, r) and sim_I (i, r) are in the interval of [–1, 1], the value of sim′ (i, r) is in the interval of [–1, 1].

After similarity computation, a set of Top-N similar services T (i) can be identified as the neighbor set of target service i.B . Item - based collaborative filtering prediction

Item-based collaborative filtering methods apply neighbor set to predict the missing QoS values by employing the following equation. $R_{ia} = {\bar{R}}_{i} + \frac{\sum_{r \in T (i)} {Sim}^{'} (i, r) (R_{ra} - {\bar{R}}_{r})}{\sum_{r \in T (i)} {Sim}^{'} (i, r)}$ (19)

Where R_ia is the QoS value to be predicted. Sim′ (i, r) is the similarity between service i and r. Service r is the neighbor of service i, T (i) is the neighbor set of service i. R_ra is the QoS of service r observed by user a. Due to the sparsity of QoS matrix, R_ra is likely to be equal to zero, in which case the predicted QoS value is not accurate. To solve this problem, we use the average QoS values of services to replace the missing entries before collaborative filtering. The predicted QoS values computed by Equation (19) may be negative due to the similarities could be negative. However, the QoS of real-world service are non-negative, thus we use the average QoS values of services to replace the negative entries either.

By applying the above IPCC-ST approach, the missing entries of QoS matrix are predicted. Then we can obtain a complete QoS matrix by filling the missing entries with the prediction values. The complete QoS matrix will be used to initialize the model parameter X in algorithm NCNMF.

2.4 Complexity analysis

The time complexity of NCNMF includes three parts: similarity computation, Top-N neighbors collaborative filtering and parameter estimation of QoS prediction model by EM procedure. Since both of the direct similarities and indirect similarities between services can be offline computed and stored in real systems, we only consider the complexity of Top-N neighbors collaborative filtering and parameter estimation of QoS prediction model by EM procedure. Given the n × m QoS matrix R has W missing entries and denoting the number of iterations of EM procedure as t_max, the maximum number of iterations of NMF as q_max, the factor numbers as k, then the computational complexity of Top-N neighbors collaborative filtering is O (NW). The computational complexity of performing NMF on R once is O (q_maxkmn). Since the parameter estimation of QoS prediction model by EM procedure includes t_max NMF operations, its computational complexity is O (t_maxq_maxkmn). Therefore, the total computational complexity of NCNMF is O (NW + t_maxq_maxkmn). Due to W ⩽ mn and N, t_max, q_max, k are all constant, the computational time of our algorithm is linear with respect to the number of entries mn in the QoS matrix. This complexity analysis indicates that our approach is very efficient and applicable to large-scale QoS prediction problem.

3 Experiments

In this section, we utilize the real-world QoS dataset WS-DREAM [6] to evaluate the prediction accuracy and time performance of NCNMF algorithm. WS-DREAM records the historical invocation QoS information of 5825 web services from 73 countries evaluated by 339 distributed users from 30 countries. By processing the dataset, we obtain two 300 × 3000 QoS matrix, which are response time matrix and throughput matrix, respectively. The experiments were conducted on a Lenovo E540 machine with Intel Core i5-4210M 2.60GHz processors and 4 GB RAM. The machine is running under Windows XP and Matlab 7.1.

3.1 Prediction accuracy evaluation

Mean absolute error (MAE) metric, which indicates the average absolute deviation of the predicted value and the actual value, is usually used to measure the prediction accuracy in recommender systems [23]. The MAE metrics is defined as: $MAE = \frac{\sum_{i, j} (R_{ij} - {\hat{R}}_{ij})}{W}$ (20)

Where W is the number of missing entries in QoS matrix, R_ij is the QoS of service i observed by user j, ${\hat{R}}_{ij}$ is the predicted QoS value. Since different QoS attributes of web service have different value ranges, we use the Normalized Mean Absolute Error (NMAE) metric to measure the prediction accuracy, where smaller NMAE value means higher prediction accuracy. The NMAE metric is defined as: $NMAE = \frac{MAE}{\sum_{i, j} R_{ij} / W}$ (21)

To study the QoS prediction accuracy, we compare our approach with other existing methods. We divide the QoS dataset into 5 different 300 × 600 matrices and make predictions on these 5 matrices respectively. The average NMAE value of these 5 evaluations are obtained as the final experimental results. In the experiment, we randomly remove entries from the QoS matrix to make the matrix sparser, as is the case in real-world, and then use the removed QoS entries as the expected values to study the prediction performance. In order to study the prediction accuracy of NCNMF under different matrix density condition, the density of QoS matrix is increased from 0.04 to 0.13 with a step value of 0.01.

Figures 3 and 4 show the prediction results of response time and throughput by different appro-aches. IPCC represents the traditional item-based collaborative filtering method, where the parameter Top-N is set to 10. IPCC-ST represents the item-based collaborative filtering approach based on similarity transition that presented in section 2.3, where the parameter Top-N is set to 10. WSRec is the hybrid collaborative filtering proposed by Zheng et al. [14], where the parameters of Top-N and λ are set to 10 and 0.2 respectively. BNMF is the basic non-negative matrix factorization algorithm proposed by Lee et al. [21]. BNMF factorizes the sparse QoS matrix to make further prediction without considering the sparsity of matrix and the neighbor information in matrix. The parameters of factor numbers and iteration numbers in BNMF are set to 15 and 100. NCNMF is the approach proposed in this paper, where the parameter settings are Top-N = 10, q_max = 100 and k = 15. In Figure 3 and 4, NCNMF with 1EM means that the number of iterations of EM procedure t_max is set to 1 and NCNMF with 5EM means that t_max is set to 5, etc.

The results of Figure 3 and 4 both show that the NMAE value of all approaches decrease with the increase of the density of QoS matrix. This is because when the density of QoS matrix increases, the QoS matrix provides more information and the neighbor information and latent feature information in matrix could be better detected, which may improve the prediction accuracy. From Figure 3 and 4, we can find that the IPCC-ST approach achieves better prediction accuracy than IPCC and WSRec in different data density condition, especially when the data is highly sparse. The results indicate that the introducing of indirect similarity in IPCC-ST can significantly improve the effectiveness of memory-based prediction approach, since it fully utilizes the similarity information of QoS matrix. Figure 3 and 4 also demonstrate that the proposed NCNMF algorithm, which systematically combines the IPCC-ST (memory-based approach) and NMF (model-based approach), achieves better prediction accuracy than each single one. The results indicate that our approach exploits the advantages of memory-based approach and model-based approach by fully utilizing the local and global information of the observed QoS data. From Figure 3 and 4 we also find that the performance of NCNMF can be effectively improved by increasing the iteration numbers t_max of EM procedure. We also notice that with the increasing of t_max, the improvement of prediction accuracy tend to be slower and converge after 20 iterations in response time prediction and 25 iterations in throughput prediction, respectively. The results indicate that the prediction accuracy can be improved by increasing the EM iterations, but the performance improvement is not infinite.

3.2 Time performance evaluation

In this section we compare the time performance of NCNMF with other approaches. In this experiment, the number of users is fixed to 300 and the number of web services varies from 100 to 1000 with a step value of 100, thus the time performance of our approaches can be evaluated by different QoS matrices with different scale. The parameter settings of all approaches are same as Section 3.1. The density of QoS matrix is fixed to 0.1.

Figure 5 shows that the computational time of all approaches increase with the increase of matrix scale, where BNMF is the most efficient approach and WSRec is the most inefficient approach. The results indicates that model-based approaches are commonly more efficient than memory-based approaches. The computational time of IPCC-ST is approximate to that of IPCC, which indicates that the introducing of indirect similarity computation will not take extra burden to the prediction system, since the indirect similarities between services can be offline computed. The computational time of NCNMF is near with IPCC and IPCC-ST, which are all linear with respect to the scale of QoS matrix. The linear computational time indicates that our approach is applicable to the large-scale QoS prediction problem. We also observe that the computational time of NCNMF is linear with the increase of the iteration numbers t_max of EM procedure. Combined with the results shown in Figure 3 and 4, we can find that the increase of the iteration numbers t_max may bring the improvement of prediction accuracy, whereas cause an additional time cost. Therefore, there is a trade-off between prediction accuracy and time performance in practical applications.

3.3 Impact of factor numbers

The parameter k determines the number of factors employed in our NCNMF approach. In this section we study the impact of k on the prediction accuracy. In this experiment, the parameters of t_max, Top-N, q_max and density of matrix are set to 1, 10, 100 and 0.05, respectively. The parameter of factor numbers k increases from 6 to 60 with a step value of 6, thus the impact of k on the prediction performance could be evaluated.

Figure 6 and 7 shows the impact of k on the prediction results, where Fig. 6 is the experimental result of response time and Fig. 7 is the experimental result of throughput. The results is the average value of 10 independently conducted experiments. Figure 6 and 7 demonstates that no matter for response time or throughput, as k increases, the NMAE values decrease at first and increase after k reaching to a certain threshold. This is because when k is small, the latent feature information detected from the QoS matrix is too little to make accurate prediction, on the other hand a large k may cause the overfitting problem. In Fig. 6, the optimal value of k is around 25 for response time prediction. In Fig. 7, the optimal value of k is around 35 for throughput prediction. The observation indicates that the optimal value of k varies with different datasets. In practical application, we can set k to an experiential value that subjects to k ⪡ mn/(m + n) to achieve acceptable prediction accuracy.

4 Related work

QoS plays a critical role in Service-Oriented Computing domain and Cloud Computing domain. Many QoS-based problems have been widely discussed in a number of recent research investigations, covering the topic of service selection [24, 25], service discovery [26], service composition [27] and composite service reliability prediction [28], etc. Most existing QoS-based approaches presume that the QoS of web service are pre-existing and can be easily obtained from service providers or a third-party organization with guaranteed accuracy. However the QoS advertised by service providers or a third-party may be not applicable for different users, since some QoS properties (e.g., response time and throughput, etc.) may vary widely among users due to the unpredictable network conditions and heterogeneous environments [2]. Therefore, the accurate client-side evaluation of web service QoS is essential for the successful implementation of QoS-based approaches. This paper focus on accurately predicting the client-side QoS values of web services for service users by collaborative filtering (CF) approaches.

CF technique has been recently employed to tackle the web service QoS prediction problem. Zheng et al. [6] conducted a large-scale distributed QoS evaluation for real-world web services and released the WSDREAM QoS dataset to promote QoS related research. There are two main types of CF approaches discussed in QoS prediction: memory-based CF and model-based CF. Memory-based CF employs the similarity relation between users or services in the QoS matrix for making prediction. Shao et al. [11] propose a user-based CF approach to predict the missing QoS values. Zheng et al. [14] propose a hybrid CF approach WSRec, which combines the user-based and item-based CF method to fully utilize the information of observed QoS data. Chen et al. [10, 29] propose an effective hybrid CF approach which takes the physical locations of users into consideration for QoS prediction. Hu et al. [13] propose a hybrid time-aware CF approach, in which the time information is integrated into similarity measurement to tackle the time-varing problem of QoS.

Model-based CF usually employ the observed historical data to train a predefined factor model and use the factor model to make further predictions. Zhang et al. [2] present a time-aware approach WSPred which analyzes the latent features of user, service and time by matrix factorization technique to make QoS prediction. Lo et al. [30] propose a local neighborhood matrix factorization QoS prediction approach that integrates the geographical domain knowledge into factor model based on the assumption that the geographically close users may have similar QoS experience.

As referred at the beginning of this paper, neither of the memory-based CF nor model-based CF can achieve an optimal prediction accuracy in condition of the highly sparse QoS data in real-world. To make full use of the information of QoS matrix for making accurate prediction, several hybrid approaches that combining memory-based and model-based approach are proposed. Zheng et al. [1] propose a user neighborhood integrated MF approach which employs both the user^′s information and the users neighbors^′ information in the learning process. Yin et al. [31] propose a service neighborhood-enhanced PMF model, in which the predicted value is learned from the services feature vectors as well as the feature vectors of its neighbors who are with the same company. The proposed NCNMF in this paper is a hybrid approach. Different from the above research work, we establishes the non-negative matrix factorization model for web service QoS prediction and employs an EM based approach to learn the model for further prediction. Our approach employs both direct similarity and indirect similarity between services to fully detect the local information of QoS matrix towards highly sparse data, which was ignored by the above literatures. Our approach exploits the advantages of memory-based approach and model-based approach, which fully utilizes the local and global information of the observed QoS data. The proposed approach is efficient and effective in predicting the missing QoS values as analyzed inSection 3.

5 Conclusion and future work

In this paper, we present a novel hybrid web service QoS prediction approach that systematically combines the memory-based CF and model-based CF. A non-negative matrix factorization model for web service QoS prediction is firstly presented. Then an EM based approach is designed to learn the model for making further prediction. The neighbor information of QoS data are mined and introduced into the EM learning process. To attack with the data sparsity problem, we integrate the direct similarity and indirect similarity between services to fully detect the neighbor information in QoS matrix. Our approach take advantages of the local information and global information of the historical invocation QoS data. Large-scale real-world experimental evaluations show the effectiveness and efficiency of our approach.

CF based QoS prediction approaches treat QoS as subject data that depend on the users preference like movie ratings or music ratings etc. However, some QoS properties are sort of objective data (e.g., response time and throughput, etc.) which are determined by some objective factors and cannot be controlled by service users. In future work, we will conduct more studies on the WSDREAM QoS dataset and improve the prediction algorithm to be more applicable to objective QoS data. Besides, the variety of QoS is not only existing among different users, even the invocations on a service by a same user during different time period may obtain different QoS values. We plan to study the influence of service invocation time on the QoS performance for more accurate prediction in the future.

Footnotes

Acknowledgments

This research work was supported by the Pre-research Funds from PLA General Armament of China (No. 9140A04020215JB11050).

References

Zibin

, Hao

, Michael

and Irwin

, Collaborative web service QoS prediction via neighborhood integrated Matrix factorization, IEEE Trans on Services Computing6(3) (2013), 289–299.

Yilei

, Zibin

and Michael

, WSPred: A time-aware personalized QoS prediction framework for web services, IEEE Int^′l Symposium on Software Reliability Engineering (2011), 210–219.

Neeraj

and Inderveer

, Job migration with fault tolerance based QoS scheduling using hash table functionality in social Grid computing, Journal of Intelligent & Fuzzy Systems27 (2014), 2821–2833.

Sukhpal

and Inderveer

, EARTH: Energy-aware autonomic resource scheduling in cloud computing, Journal of Intelligent & Fuzzy Systems (2015), 1–16. DOI: https://dx-doi-org.web.bisu.edu.cn/10.3233/IFS-151866.

Jieming

, Pinjia

, Zibin

and Michael

, A Privacy-Preserving QoS Prediction Framework for Web Service Recommendation, IEEE International Conference on Web Services (2015), pp. 241–248.

Zibin

, Yilei

and Michael

, Distributed QoS evaluation for real-world web services, IEEE Int^′l Conf on Web Services (2010), pp. 83–90.

Tsai

W.-T.

, Zhou

, Chen

and Bai

, On testing and evaluating service-oriented software, IEEE Computer41(8) (2008), 40–46.

, Wei

, Qiao

and Li

, A Bayesian Network Based QoS Assessment Model for Web Services, International Conference on Services Computing (2007), pp. 498–505.

Zibin

, Xinmiao

, Yilei

, Michael

and Jianmin

, QoS ranking prediction for cloud services, IEEE Trans on Parallel and Distributed Systems24(6) (2013), 1213–1222.

10.

, Zibin

, Xudong

, Zicheng

and Hailong

, Personalized QoS-aware web service recommendation and visualization, IEEE Trans on Services Computing6(1) (2013), 35–47.

11.

Lingshuang

, Jing

, Yongand

and Junfeng

, Personalized QoS prediction for web service via collaborative filtering, IEEE Int^′l Conf on Web Services (2007), pp. 439–446.

12.

Lina

, Quan

, Anne

, Jian

and Aviv

, Unified collaborative and content-based web service recommendation, IEEE Trans on Services Computing8(3) (2015), 453–465.

13.

Yan

, Qimin

and Xiaohui

, A Time-Aware and Data S-Parsity Tolerant Approach for Web Service Recommendation, IEEE International Conference on Web Services (2014), pp. 33–40.

14.

Zibin

, Hao

, Michael

and Irwin

, QoS-aware web service recommendation by collaborative filtering, IEEE Trans on Services Computing4(2) (2011), 140–152.

15.

Wei

, Jianwei

, Shuiguang

, Ying

and Zhaohui

, Collaborative Web Service QoS Prediction with Location-Based Regularization, IEEE International Conference on Web Services (2012), pp. 464–471.

16.

Yutu

, Anne

and Liangzhao

, QoS computation and policing in dynamic Web service selection, In Proc of the WWW, ACM (2004), 66–73.

17.

Sheng

, Weihong

, James

, Fillia

, Learning from incomplete ratings using non-negative matrix factorization, pp, 6th SIAM Conference on Data Mining (2006), 548–552.

18.

Ruslan

and Andriy

, Probabilistic matrix factorization, Proc Advances in Neural Information Processing Systems (2007), pp. 1257–1264.

19.

Sheng

, Weihong

, James

and Fillia

, Using singular value decomposition approximation for collaborative filtering, In Proc of the Seventh IEEE Int^′l Conf on E-Commerce Technology (2005), pp. 1–8.

20.

Nathan

and Tommi

, Weighted low rank approximation,, Proc of the 20th Int^′l Conf on Machine Learning , 2003.

21.

Daniel

and Sebastian

S.H.

, Learning the parts of objects by non-negative matrix factorization, Nature401(6755) (1999), 788–791.

22.

Daniel

and Sebastian

S.H.

, Algorithms for non-negative matrix factorization, Proc Advances in Neural Information Processing Systems (2000), pp. 556–562.

23.

Rong

and Pearl

, Enhancing collaborative filtering systems with personality information, In Proc of The Fifth ACM Conf on Recommender Systems (2011), pp. 197–204.

24.

Tao

, Yue

and Kwei

, Efficient algorithms for web services selection with end-to-end QoS constraints, ACM Trans on the Web1(1) (2007), 1–26.

25.

Kai

, Liangli

, Xiaoming

and Yufei

, An efficient parameter adaptive genetic algorithm for service selection with end-to-end QoS constraints, Journal of Computational Information Systems10(2) (2014), 581–588.

26.

Meditskos

and Bassiliades

, Structural and role-oriented web service discovery with taxonomies in owl-s, Trans Knowl Data Eng22(2) (2010), 278–290.

27.

Mohammad

and Thomass

, Combining Global Optimization with Local Selection for Efficient QoS-aware Service Composition, In Proc of the 18th Int^′l Conf On World Wide Web (2009), 881–882.

28.

Zibin

and Michael

, Collaborative reliability prediction for service-oriented systems, In Proc of IEEE/ACM 32nd Int^′l Conf Software Eng(ICSE^′ 10) (2010), pp. 35–44.

29.

, Xudong

, Zicheng

and Hailong

, RegionKNN: A Scalable Hybrid Collaborative Filtering Algorithm for Personalized Web Service Recommendation, IEEE International Conference on Web Services (2010), pp. 9–16.

30.

Wei

, Jianwei

, Ying

and Zhaohui

, Efficient web service QoS prediction using local neighborhood matrix factorization, Engineering Applications of Artificial Intelligence38 (2015), 14–23.

31.

Jianwei

and Yueshen

, Personalized QoS-based web service recommendation with service neighborhood-enhanced matrix factorization, International Journal of Web and Grid Services11(1) (2015), 39–56.