Recommender systems(RS) are a type of solution to the information overload problem su ered by users of websites that allow the rating of certain items. Collaborative ltering(CF) is one of the most widely used methods in personalized RS. The most critical part of collaborative ltering is to compute similarities among users using a user-item rating matrix based on which recommendations can be generated. However, CF su ers from several inherent issues, such as data sparsity and cold start, which a ect the quality of recommendation seriously. To address these problems, we propose a reconstructing trust matrix measure in this paper, which combines user similarity and weighted trust propagation. Speci cally, we rst remove the trust relationship of those users whose similarity falls below a certain threshold. We then add the users that are not in the trust matrix into it when the similarity between them exceeds a certain threshold. Finally, weighted trust propagation is considered, aiming to distinguish trusted neighbors in a shorter distance with those in a longer distance and incorporate more trusted neighbors, especially useful for cold users. Experimental results on two real-world data sets show that our method achieves superior accuracy and it can solve cold user problem as well.
Information systems ! World Wide Web; Web searching and information discovery ! Social recommendation;
The emergence of Web 2.0 applications has greatly changed usersa,r styles of online activities from searching and browsing to interacting and sharing[1]. However, it is up against the challenge of information overload meanwhile, which is well-known as requiring to spend a lot of time to nd useful information. Recommender systems (RS) are designed to cope with the problem and heavily used in e-commerce applications such as Amazon.com, Ebay.com, and Net ix.com etc.
Collaborative ltering(CF) has become the most well-known
and commonly used techniques to generate
recommendations in RS[2]. The intuition of CF is making predictions
about a usera,rs preferences or tastes based on the
preferences of a group of users that are considered similar to this
user. However, CF su ers from several inherent issues, for
example, data sparsity and cold start. Data sparsity refers
to the di culty in nding su cient and reliable similar users
due to the fact that users in general only rate a small
portion of items, while cold start includes two main problems:
(
The majority of earlier approaches for prediction in trustbased systems make predictions utilizing all the trust statements present in the data. But user A trusting user B dose not signify that the similarity between A and B will also be high and the low similarity in trust relationship will impact prediction quality adversely. Thus in this paper we rst remove the trust relationship of those users whose similarity falls below a certain threshold. We then add the users that are not in the trust matrix into it when the similarity between them exceeds a certain threshold. Besides, weighted trust propagation is considered, aiming to distinguish trusted neighbors in a shorter distance with those in a longer distance and to incorporate more trusted neighbors, which is especially useful for cold users.
The rest of the paper is organized as follows. In Section 2, we give a brief overview of related research on trust-based CF. The proposed approach is then elaborated in Section 3. Experiments on two real-world data sets are conducted in Section 4. Finally, Section 5 concludes our work. 2.
To better model user preferences for the cold users who only rated a few items, additional information is often adopted and trust is of less ambiguity and more relevant to similarity. Till now many trust-based approaches have been proposed.
Jamali et al. designed the TrustWalker approach[4] to randomly select trusted neighbors in the trust networks, where trust information of the selected neighbors is combined with an item-based technique to predict item ratings. In contrast, our work focuses on generating predictions by combining trust information with a user-based technique.
Massa et al. proposed the MoleTrust algorithm[5], which performs depth- rst search, to propagate and infer trust in the trust networks. Empirical results show that the coverage is signi cantly enlarged but the accuracy remains comparable when propagating trust.
Ray et al. presented another trusted method[6]. The trust links between two users will be removed if their similarity is lower than a threshold. But empirical results show that good performance is achieved at the cost of poor coverage, and it fails to function in cold conditions where user similarity may not be computable.
Recently, Deng et al. proposed a social network based service recommendation method with trust enhancement known as RelevantTrustWalker[7]. First, a matrix factorization method is utilized to assess the degree of trust between users in social network. Next, an extended random walk algorithm is proposed to obtain recommendation results.
Guo et al. presented a merged method called Mergex[8], which merged the ratings of trusted neighbors in order to form a new and more complete rating pro?le for the active users based on which recommendations can be generated by integrating similarity and trust into CF.
Our work focuses on generating predictions by combining weighted trust propagation with a user-based technique. In order to achieve a better result, we rst remove the trust statements between two users if their similarity is lower than a threshold considering low similarity in trust will a ect the prediction accuracy. Since high similarity in trust statements can improve the recommendation results, the trust links between two users will be added into the original trust matrix if their similarity overtops a certain threshold. Finally, weighted trust propagation will be considered aiming to distinguish trusted neighbors in a shorter distance with those in a longer distance and nd more trusted neighbors, which is especially useful for cold users.
In this section, we will present the speci c method. We will introduce how to incorporate similarity and trust to reconstruct trust matrix. Then the weighted trust propagation will be explained. 3.1
The majority of earlier approaches for prediction in trustbased systems make predictions utilizing all the trust statements present in the data. But as we all know, user A trusting user B does not mean that the correlation between A and B will be also high. So we present the method of combining similarity and trust to reconstruct trust matrix. Pearson Correlation Coe cient(PCC) is a preferable method[9] and we adopt PCC to compute similarity in recommender systems, it is de ned as follow:
Sa;b =
Pi(ra;i ra)(rb;i
rb)
pPi(ra;i
ra)2pPi(ra;i
ra)2
(
In a recommender system, T rust presents the traditional
trust matrix, and ta;b is the trust value between a and b.
Generally, the trust value is binary, namely 0 and 1, where
0 stands for distrust and 1 indicates absolutely trust. We
set two similarity threshold and when reconstructing
trust matrix. First, the low similarity in trust relationship
will reduce the quality of rating prediction, thus, for the
two trust users a and b, namely ta;b = 1, we will remove
their trust statement if Sa;b < and reserve their trust
relationship if Sa;b > . It is de ned as (
1; ta;b = 1 and Sa;b >
The high similarity in trust matrix will improve
recommendation results, accordingly, for the two users a and b
which are not in the trust matrix, namely ta;b = 0, if Sa;b >
we will add the trust relationship between a and b.
However, if Sa;b < , the trust relationship cannot be added for
a and b. It is de ned as (
Through the above steps, the trust matrix is reconstructed, which is de ned as U pT rust. 3.2
The cold users are generally de ned as the users who have rated less than ve items[10]. Since cold users are usually less active in the systems, they may not have a large number of trusted neighbors. Fortunately, trust can be propagated along with the web-of-trust. That is, if user A trusts B and B trusts C, it can be inferred that A trusts C in some degree. Therefore, it is necessary to propagate trust in order to nd more trusted neighbors for cold user problem. MoleTrust[11] is the method using the above trust propagation to infer the trust value of indirectly connected users. Note that the trust value in the reconstructed trust matrix U pT rust is binary, i.e., 0 or 1. As a result, the inferred trust value by the MoleTrust will be also binary, and thus we cannot distinguish trusted neighbors in a shorter distance with those in a longer distance. Hence, we adopt a weighting factor to devalue the inferred trust in a long distance:
t0a;b = d1 ta;b (
Where ta;b denotes the trust value in the trust matrix, t0a;b is the weighted trust value and d is the shortest distance between users a and b determined by a breath rst search algorithm. Note that the greater d is, the more trusted neighbors will be inferred. However, the more cost will be taken and more noise is likely to be incorporated. In this work, we restrict d 3 to prevent meaningless searching and save computational cost for large-scale data sets. In fact, as we will show later, our method works well enough when d is small. The trust matrix is U pT rust d after using weighted trust propagation.
According to the above description, the algorithm of RTMA and WTPA are expressed as follows:
Step1: According to user-item rating matrix and PCC algorithm, compute similarities between every two users.
Step2: Prede ne threshold and .
Step3: For two users u and v in user-item rating matrix,
reset tu;v according to de nition (
Step4: Get the U pT rust.
Step5: For two users u and v in UpTrust d, reset t0u;v
according to de nition (
Step6: Get the U pT rust d.
To verify our method, we conduct experiments on two real-world data sets using the 5-fold cross validation method. The data set is split into ve disjoint sets; for each iteration, four folds are used as training set and one as testing set. We apply the K-Nearest Neighbor(KNN) approach to select a group of similar users whose ranking is in the top K according to similarity; we vary K from 5 to 50 with step 5. The ratings of selected similar users are aggregated to predict itemsa,r ratings by a mean-centering approach[12]. 4.1
Two real-world data sets are used in our experiments, namely FilmTrust and Epinions. They are available data sets that contain both the trust matrix and user-item rating matrix.
FilmTrust is a trust-based social site in which users can rate and review movies. It includes 1986 users, 2071 movies and 35497 ratings. The ratings take values from 0.5 to 4.0with step 0.5. In addition, 1853 trust ratings that are issued by 609 users are gathered. The sparsity is 98.86%.
Epinions is a website in which users can express their opinions about items (such as movies, books, and software) by assigning numerical ratings and writing text reviews. The data set consists of 49K users who issued 664K ratings over 139K di erent items and 478K trust statements. The ratings are integers rated from 1 to 5 and the sparsity is 99.95%. The trust values of both data sets are binary (either 1 or 0). 4.2
The evaluation metrics are mean absolute error (MAE), root mean square error (RMSE) and rating coverage (RC) respectively. They are de ned as follows:
M AE = RM SE =
X (u;i)2T s X (u;i)2T jrui
rbuij=jT j jrui rbuij=jT j
Where T represents the set of prediction results and jT j is the number of the set, and rbui is the prediction rating of user u to item i.
RC =
M N
Where M and N are the number of predictable and all
the testing ratings, respectively.
(
In this section, we will verify our method of reconstructing trust matrix.
Fig. 1(a) and (b) are the performances of these approaches on FilmTrust in terms of MAE and RMSE respectively. The threshold and are set as 0.2 and 0.3 respectively. The results show that our method UpTrust d is the best method. PCC is better than Trust d and it illustrates that the low similarity in trust statement can deteriorate the prediction results. From the gure, we can observe that with the lengthening of trust propagation, Trust 3 is better than Trust 2 and Trust 2 is better than Trust 1, we may conclude that trust propagation is helpful to improve recommendation performance. However, in the method UpTrust d, UpTrust 1 is the best method and it better than UpTrust 2 and UpTrust 3. This is because although more trusted neighbors can be identi ed via trust propagation, it does not guarantee that the rating pro le will cover a lot more items and hence increase accuracy greatly. Rather, it is possibly that adding few trusted neighbors may result in some noisy ratings, and hence harm the predictive performance.
In addition, to verify whether our method can solve cold start problem, we conduct experiments on FilmTrust in terms of MAE, RMSE and RC on cold users. Similarly, we compare UpTrust 1 with PCC and the performances are shown in Fig. 3. We can get that UpTrust 1 is much better than PCC in terms of cold users which declares that our method can solve cold start problem to some extent. Table 1 is the performances of the two methods in terms of RC, which can further verify that our method can solve cold start problem e ectively.
This paper presents a reconstructing trust matrix method to improve the prediction accuracy and solve cold user problem of collaborative ltering recommender systems. Considering the similarity in trust matrix will a ect recommendation results, we reconstruct traditional trust matrix. Besides, to recommend better for cold users and distinguish trusted neighbors in a shorter distance with those in a longer distance, weighted trust propagation is considered. The experimental results on two real data sets demonstrate the e ectiveness of our methods in improving the prediction accuracy and solving cold user problem of recommender systems.