Expert Systems with Applications 39(2012)1183-1190 Contents lists available at ScienceDirect Expert Systems with Applications ELSEVIER journalhomepagewww.elsevier.com/locate/eswa Trust based recommender system using ant colony for trust computation Punam bedi. Ravish sh arna Department of Computer Science, Faculty of Mathematical Sciences, Opposite Daulat Ram College, University of Delhi, Delhi 110007, India ARTICLE FO A BSTRACT ywords Collaborative Filtering(CF) technique has proven to be promising for implementing large scale recom- lender systems but its success depends mainly on locating similar neighbors. Due to data sparsity of the user-item rating matrix, the process of finding similar neighbors does not often succeed. In addition Recommender system to this. it also suffers from the new user(cold start)problem as finding possible neighborhood and giving Pheromone updating commendations to user who has not rated any item or rated very few items is difficult. In this paper. ur proposed Trust based Ant Recommender System (TARS)produces valuable recommendations by incorporating a notion of dynamic trust between users and selecting a small and best neighborhood based on biological metaphor of ant colonies. Along with the predicted ratings, displaying additional information for explanation of recommendations regarding the strength and level of connectedness in trust graph from where recommendations are generated, items and number of neighbors involved in pre- dicting ratings can help active user make better decisions. Also, new users can highly benefit from pher- omone updating strategy known from ant algorithms as positive feedback in the form of aggregated dynamic trust pheromone defines"popularity"of a user as recommender over a period of time The vo formance of tARS is evaluated using two of different sparsity levels viz. Jester dataset lovieLens dataset (available online) and approach for generating recommendations. e 2011 Elsevier Ltd. All rights reserved. 1 Introduction techniques ie content based, knowledge-based, demographic, or utility based and is called Hybrid approach. The complexity of the recommendation problem is due to its vast CF takes its roots from something humans have been doing space of possibilities. Recommender systems are important tools centuries i.e. sharing opinions with others and brings together the that overcome the information overload by sifting through the large opinions of large interconnected communities on the web(Schafer, set of data and recommending information relevant to the user. Rec- Frankowski, Herlocker, Sen, 2007). Collaborative Filtering based ommendation techniques have a number of possible classifications recommenders work best for a user who fits into a niche with including content based, collaborative, knowledge-based, demo- neighbors of similar taste. This approach doesnot need a represen- valent three approaches to developing recommender systems. In of item viz. papers, news, web sites, movies, song), obs anye of based(Burke, 2002; Resnick Varian, 1997: tation of the items in terms of features but is Schafer, Konstan, Reidl, 1999: Terveen Hill, 2001). Collaborative judgment of the user community. Because of its Filtering, Content based approach and Hybrid methods are the pre- theory and implementation, CF can be applied Collaborative Filtering(CF)approach, opinions from users in the locations of holidays, stocks etc. The three-step conceptual for orm of ratings on various items are collected. The recommendations of the operation of the Collaborative Filtering process is as roduced are based only on the opinions of users similar to the active user. Active user refers to recommendation seeker for whom recom- (i Construct rating matrix using user-item data. endations are generated. Content based approach suggests items Locate people (neighbors) with similar profiles(similar hat are similar to the ones the active user has shown a preference rences for in the past rather than on the preferences of other users Mostly (iii) Unify neighbors ratings to form recommendations CF technique is combined with one or more recommendation There are several limitations and challenges to CF based recom mender systems due to traditional emphasis on user similarit Sector 62 Noida 201301 U.P. India Tel: +9109313907606: fax: +911127662553 One of the main limitations is that it provides recommendation E-mail addresses: pbedi@cs. duac in(P Bedi), sharma_ravish123@rediffmail con based solely on the opinion of the users whose preferences best matches the taste of active user. Approaches incorporating trust 0957-4174/s- see front matter o 2011 Elsevier Ltd. All rights reserved doi:10.1016/eswa2011.07.124
Trust based recommender system using ant colony for trust computation Punam Bedi, Ravish Sharma ⇑ Department of Computer Science, Faculty of Mathematical Sciences, Opposite Daulat Ram College, University of Delhi, Delhi 110007, India article info Keywords: Collaborative Filtering Trust Recommender system Ant colony Pheromone updating abstract Collaborative Filtering (CF) technique has proven to be promising for implementing large scale recommender systems but its success depends mainly on locating similar neighbors. Due to data sparsity of the user–item rating matrix, the process of finding similar neighbors does not often succeed. In addition to this, it also suffers from the new user (cold start) problem as finding possible neighborhood and giving recommendations to user who has not rated any item or rated very few items is difficult. In this paper, our proposed Trust based Ant Recommender System (TARS) produces valuable recommendations by incorporating a notion of dynamic trust between users and selecting a small and best neighborhood based on biological metaphor of ant colonies. Along with the predicted ratings, displaying additional information for explanation of recommendations regarding the strength and level of connectedness in trust graph from where recommendations are generated, items and number of neighbors involved in predicting ratings can help active user make better decisions. Also, new users can highly benefit from pheromone updating strategy known from ant algorithms as positive feedback in the form of aggregated dynamic trust pheromone defines ‘‘popularity’’ of a user as recommender over a period of time. The performance of TARS is evaluated using two datasets of different sparsity levels viz. Jester dataset and MovieLens dataset (available online) and compared with traditional Collaborative Filtering based approach for generating recommendations. 2011 Elsevier Ltd. All rights reserved. 1. Introduction The complexity of the recommendation problem is due to its vast space of possibilities. Recommender systems are important tools that overcome the information overload by sifting through the large set of data and recommending information relevant to the user. Recommendation techniques have a number of possible classifications including content based, collaborative, knowledge-based, demographic, and utility based (Burke, 2002; Resnick & Varian, 1997; Schafer, Konstan, & Reidl, 1999; Terveen & Hill, 2001). Collaborative Filtering, Content based approach and Hybrid methods are the prevalent three approaches to developing recommender systems. In Collaborative Filtering (CF) approach, opinions from users in the form of ratings on various items are collected. The recommendations produced are based only on the opinions of users similar to the active user. Active user refers to recommendation seeker for whom recommendations are generated. Content based approach suggests items that are similar to the ones the active user has shown a preference for in the past rather than on the preferences of other users. Mostly CF technique is combined with one or more recommendation techniques i.e. content based, knowledge-based, demographic, or utility based and is called Hybrid approach. CF takes its roots from something humans have been doing for centuries i.e. sharing opinions with others and brings together the opinions of large interconnected communities on the web (Schafer, Frankowski, Herlocker, & Sen, 2007). Collaborative Filtering based recommenders work best for a user who fits into a niche with neighbors of similar taste. This approach doesnot need a representation of the items in terms of features but is based only on the judgment of the user community. Because of its simplicity in both theory and implementation, CF can be applied to virtually any kind of item viz. papers, news, web sites, movies, songs, books, jokes, locations of holidays, stocks etc. The three-step conceptual model of the operation of the Collaborative Filtering process is as follows: (i) Construct rating matrix using user–item data. (ii) Locate people (neighbors) with similar profiles (similar preferences). (iii) Unify neighbors’ ratings to form recommendations. There are several limitations and challenges to CF based recommender systems due to traditional emphasis on user similarity. One of the main limitations is that it provides recommendations based solely on the opinion of the users whose preferences best matches the taste of active user. Approaches incorporating trust 0957-4174/$ - see front matter 2011 Elsevier Ltd. All rights reserved. doi:10.1016/j.eswa.2011.07.124 ⇑ Corresponding author. Address: B-408, Flex Apartments, Plot No. C-58/22, Sector 62, Noida 201301, U.P., India. Tel.: +91 09313907606; fax: +91 11 27662553. E-mail addresses: pbedi@cs.du.ac.in (P. Bedi), sharma_ravish123@rediffmail.com (R. Sharma). Expert Systems with Applications 39 (2012) 1183–1190 Contents lists available at ScienceDirect Expert Systems with Applications journal homepage: www.elsevier.com/locate/eswa
P Bedi, R Sharma/ Expert Systems with Applications 39(2012)1183-1190 models into recommender systems are gaining momentum, syn- time t. Due to its dynamic property, it is called Dynamic Trust Pher thesizing recommendations based upon opinions from trusted omone(DTP)and is updated using pheromone updating strategy peers rather than most similar ones(ziegler& Nilcolas, 2007). In known from ant algorithms As the time passes, recommendations nline recommendation generation process, a number of users are produced by continuously updating dynamic trust between form a virtual social network where trust relationship is the key users and selecting a small and best neighborhood using ant colony of users' human relations and trust relationship of mutual interde- metaphor. Also, new users can highly benefit from pheromone pendence forms a so-called Web of trust (Wei, 2007). The three updating strategy known from ant algorithms. oroperties assigned to trust as discussed in literature(ries, Kanga- The rest of the paper is organized as follows: Section 2 reviews sharju, MuhIhauser, 2006) are as follows: the related research work and presents the motivation for our work. Our proposed system TARS with a detailed description of (i) Trust is subjective and therefore asymmetric. each step is presented in Section 3. Section 4 explains the experi (i) Trust is context dependent. mental methodology employed and the two datasets used in our iii) Trust is dynamic which means that it can increase with posi- experiments. Section 5 concludes the paper ve experience and decrease with negative experience or over time without any experience. 2. Related work The dynamic property of trust can be viewed as trust intensity In this section, review of literature related to recommender sys- among the users. For example, the trust intensity between recom- tems and motivation for our work is presented. recommendations generated by the recommender Trust intensity mia and the industry. Using stereotypes, the Grundy system was being time-based information, can be analyzed using pheromone developed to build individual user models which were used to rec- updating strategy known from ant algorithms. Ant algorithms are ommend relevant books to each user(rich, 1979). Later on, the based on emulation of behavior of real ants and build better solu- Tapestry system relied on each user to identify like-minded users tions by communicating through artificial pheromone In many ant manually(Goldberg. nicholas, Oki, Terry, 1992). GroupLens species, ants tend to lay a substance called pheromone while walk-( Konstan et al 1997: Resnick, Lakovou, Sushak, Bergstrom, riedl ing from their nests to food source and vice versa. Ants do not com- 1994)in the domain of Usenet newsgroup articles, Bellcore's Video unicate directly with each other, but they follow pheromone Recommender(hill, Stead, Rosenstein, Furnas, 1995)in the trails laid by other ants. Ants are attracted by pheromones coming domain of movies and Ringo( Shardanand Maes, 1995) in the do from fellow type(members of same species)ants and repulsed by main of music and musical artists were the first systems to use Col- pheromone of non-fellow type ants. As the time passes, paths that laborative Filtering algorithms to automate predictions. Other are marked by stronger amount of pheromone are chosen with examples of collaborative recommender systems include the book robability than those that have weaker recommendation system from Amazon. com, the PHOAKS system mone deposit(Blum, 2005: Bonabeau, Dorigo, Theraulaz, 1999: that helps people find relevant information on the www(Terveen, Dorigo, Maniezzo, Colorni, 1996: Dorigo& Stutzle, 2004). One Hill, Amento, McDonald, Creter, 1997), and the jester system that of the basic ingredients of the ant algorithms is a randomized gree recommends jokes(goldberg, roeder, Gupta, Perkins, 2001). Dif- dy construction heuristic in which each option is selected with a ferent item-based recommendation algorithms are analyzed by probability proportional to its perceived quality. As the algorithm Sarwar, Karypis, Konstan, and riedl(2001). progresses, the probabilities are altered to encourage the selection Researchers have also applied Swarm Intelligence techniques to of elements that have featured good solutions. Ant algorithms recommender systems. Ujin and Bentley(2003)have described repeatedly construct new solutions from scratch throughout the Particle Swarm Optimization(PSO) recommender system in which duration of the search. Moreover, this collaborative behavior be- PSO algorithm has been employed to learn personal preferences of tween fellow type ants has an analogy with the collaborative world users and provide tailored suggestions. A system called CASIS has as people mostly collect opinions from their like-minded friends, been developed combining case based reasoning approach with eighbors etc. Work by Bedi, Sharma, and Kaur(2009)and sharma, metaphor from colonies of social insects, namely the honey bee Singh, Makkar, Kaur, and Bedi(2007)combine artificial pheromone dance. This combination has been used in the retrieval step of information with similarity measure for choosing best matching the recommendation cycle (Lorenzi, Santos, Bazzan, 2005 ). users providing active user with good set of alternative recom Web-based system user interface hybrid recommendation method are marked by stronger amount of pheromone have the higher for selecting the most optimal path in the user interface graph o mendations. In addition to the taste of active user, clusters that is presented in( Sobecki, 2007)where ant colony metaphor is used probability of being chosen than those that have weaker amount In addition to traditional emphasis on user similarity, trustor- of pheromone deposit. Also, one of the fundamental challenges thiness of users has been an important consideration by research- for recommender systems is to improve the quality of the pre ers. they have suggested that the advantage of combining users dicted ratings. In such a scenario, pheromone updating strategy trust network and user-item rating matrix solves CF sparsene of ants guides the search to a better recommendation. The positive problem to some extent. Two computational models of trust feedback in the form of pheromone deposition results in achieving namely profile-level trust and item level trust have been developed an emergent, unified behavior for the recommender system as a and incorporated into standard collaborative Filtering frameworks whole, and produces a robust system capable of finding improved (ODonovan and Smith, 2005 ). Work by Massa and bhattacharje commendations. Still, there is a need for producing valu-(2004)and Massa and Avesani(2009, 2007, 2004)focus on using dations due to data sparsity of input-rating matrix the explicit trust as input along with user-item rating matrix to and solving new user problem. These problems are intrinsic in the predict ratings. They have analyzed explicit trust from the popular rocess of finding similar neighbors. In our proposed approach Internet web site epinions. com and shown that by exploiting the TARS (Trust based Ant Recommender System), sparseness in user web of trust, it is possible to propagate trust and infer an additional similarity due to data sparsity of input matrix is reduced while weight for other users. New users can also benefit from trust prop- creating directed trust graph for each user Weight on the edge rep- agation as long as the users least one trusted friend resents strength of connectedness i.e. trust intensity between the Although the explicit trus two recommendation partners(recommender and active user)at have high rating prediction and high rating prediction
models into recommender systems are gaining momentum, synthesizing recommendations based upon opinions from trusted peers rather than most similar ones (Ziegler & Nilcolas, 2007). In online recommendation generation process, a number of users form a virtual social network where trust relationship is the key of users’ human relations and trust relationship of mutual interdependence forms a so-called Web of trust (Wei, 2007). The three properties assigned to trust as discussed in literature (Ries, Kangasharju, & Muhlhauser, 2006) are as follows: (i) Trust is subjective and therefore asymmetric. (ii) Trust is context dependent. (iii) Trust is dynamic which means that it can increase with positive experience and decrease with negative experience or over time without any experience. The dynamic property of trust can be viewed as trust intensity among the users. For example, the trust intensity between recommender and active user may increase or decrease depending on recommendations generated by the recommender. Trust intensity being time-based information, can be analyzed using pheromone updating strategy known from ant algorithms. Ant algorithms are based on emulation of behavior of real ants and build better solutions by communicating through artificial pheromone. In many ant species, ants tend to lay a substance called pheromone while walking from their nests to food source and vice versa. Ants do not communicate directly with each other, but they follow pheromone trails laid by other ants. Ants are attracted by pheromones coming from fellow type (members of same species) ants and repulsed by pheromone of non-fellow type ants. As the time passes, paths that are marked by stronger amount of pheromone are chosen with higher probability than those that have weaker amount of pheromone deposit (Blum, 2005; Bonabeau, Dorigo, & Theraulaz, 1999; Dorigo, Maniezzo, & Colorni, 1996; Dorigo & Stutzle, 2004). One of the basic ingredients of the ant algorithms is a randomized greedy construction heuristic in which each option is selected with a probability proportional to its perceived quality. As the algorithm progresses, the probabilities are altered to encourage the selection of elements that have featured good solutions. Ant algorithms repeatedly construct new solutions from scratch throughout the duration of the search. Moreover, this collaborative behavior between fellow type ants has an analogy with the collaborative world as people mostly collect opinions from their like-minded friends, neighbors etc. Work by Bedi, Sharma, and Kaur (2009) and Sharma, Singh, Makkar, Kaur, and Bedi (2007) combine artificial pheromone information with similarity measure for choosing best matching clusters providing active user with good set of alternative recommendations. In addition to the taste of active user, clusters that are marked by stronger amount of pheromone have the higher probability of being chosen than those that have weaker amount of pheromone deposit. Also, one of the fundamental challenges for recommender systems is to improve the quality of the predicted ratings. In such a scenario, pheromone updating strategy of ants guides the search to a better recommendation. The positive feedback in the form of pheromone deposition results in achieving an emergent, unified behavior for the recommender system as a whole, and produces a robust system capable of finding improved quality recommendations. Still, there is a need for producing valuable recommendations due to data sparsity of input-rating matrix and solving new user problem. These problems are intrinsic in the process of finding similar neighbors. In our proposed approach TARS (Trust based Ant Recommender System), sparseness in user similarity due to data sparsity of input matrix is reduced while creating directed trust graph for each user. Weight on the edge represents strength of connectedness i.e. trust intensity between the two recommendation partners (recommender and active user) at time t. Due to its dynamic property, it is called Dynamic Trust Pheromone (DTP) and is updated using pheromone updating strategy known from ant algorithms. As the time passes, recommendations are produced by continuously updating dynamic trust between users and selecting a small and best neighborhood using ant colony metaphor. Also, new users can highly benefit from pheromone updating strategy known from ant algorithms. The rest of the paper is organized as follows: Section 2 reviews the related research work and presents the motivation for our work. Our proposed system TARS with a detailed description of each step is presented in Section 3. Section 4 explains the experimental methodology employed and the two datasets used in our experiments. Section 5 concludes the paper. 2. Related work In this section, review of literature related to recommender systems and motivation for our work is presented. Many collaborative systems have been developed in the academia and the industry. Using stereotypes, the Grundy system was developed to build individual user models which were used to recommend relevant books to each user (Rich, 1979). Later on, the Tapestry system relied on each user to identify like-minded users manually (Goldberg, Nicholas, Oki, & Terry, 1992). GroupLens (Konstan et al., 1997; Resnick, Lakovou, Sushak, Bergstrom, & Riedl, 1994) in the domain of Usenet newsgroup articles, Bellcore’s Video Recommender (Hill, Stead, Rosenstein, & Furnas, 1995) in the domain of movies and Ringo (Shardanand & Maes, 1995) in the domain of music and musical artists were the first systems to use Collaborative Filtering algorithms to automate predictions. Other examples of collaborative recommender systems include the book recommendation system from Amazon.com, the PHOAKS system that helps people find relevant information on the WWW (Terveen, Hill, Amento, McDonald, & Creter, 1997), and the Jester system that recommends jokes (Goldberg, Roeder, Gupta, & Perkins, 2001). Different item-based recommendation algorithms are analyzed by Sarwar, Karypis, Konstan, and Riedl (2001). Researchers have also applied Swarm Intelligence techniques to recommender systems. Ujjin and Bentley (2003) have described Particle Swarm Optimization (PSO) recommender system in which PSO algorithm has been employed to learn personal preferences of users and provide tailored suggestions. A system called CASIS has been developed combining case based reasoning approach with a metaphor from colonies of social insects, namely the honey bee dance. This combination has been used in the retrieval step of the recommendation cycle (Lorenzi, Santos, & Bazzan, 2005). Web-based system user interface hybrid recommendation method is presented in (Sobecki, 2007) where ant colony metaphor is used for selecting the most optimal path in the user interface graph. In addition to traditional emphasis on user similarity, trustworthiness of users has been an important consideration by researchers. They have suggested that the advantage of combining users’ trust network and user–item rating matrix solves CF sparseness problem to some extent. Two computational models of trust namely profile-level trust and item level trust have been developed and incorporated into standard Collaborative Filtering frameworks (O’Donovan and Smith, 2005). Work by Massa and Bhattacharjee (2004) and Massa and Avesani (2009, 2007, 2004) focus on using the explicit trust as input along with user–item rating matrix to predict ratings. They have analyzed explicit trust from the popular Internet web site epinions.com and shown that by exploiting the web of trust, it is possible to propagate trust and infer an additional weight for other users. New users can also benefit from trust propagation as long as the users provide at least one trusted friend. Although the explicit trust based recommender system models have high rating prediction coverage and high rating prediction 1184 P. Bedi, R. Sharma / Expert Systems with Applications 39 (2012) 1183–1190
Be 85 accuracy, the explicit trust statements may not always be available discrete scale 1 to 5. We have normalized ratings of both the data- (Yuan, Guan, Lee, Lee, Hur 2010). Also there is a need sets in the range 0 to 1 as follows: ng valuable recommendations when input data is sparse and solv- ing new user problem as the following problems may persist: ( New user may or may not provide even one trusted friend in com- unity.(ii) Due to sparseness in user-item rating matrix, trusted where ray denotes rating given by ith user for jth item in the user friends may not be able to provide recommendations for some Item rating matrIx. items but a friend of friend may ( iii) It may be time consuming n denotes the total number of items in the user-item rating or expensive to get explicit trust. In addition, the selection of a peer eighborhood containing similar users is a vital function for gener Step 2 Directed trust graph creation for each user and storing ating good recommendations. In the sparse data environment, the the in predicted recommendations often depend on a small portion of the The directed trust graphG=(V, E)is created where v is the set selected neighborhood. Thus in our proposed approach TARs, we of vertices which corresponds to users and e is the set of edges have focused on such issues by creating directed trust graph and connecting users. Weight on the edge represents strength of exploiting it using pheromone strategy known from ant algorithm onnectedness i.e. trust intensity between the two recommen- to provide better recommendations. dation partners(recommender and active user)at time t Trust intensity being dynamic information, increases or decreases 3. Proposed Trust based Ant Recommender System(TARs) with the involvement or non-involvement of user as a recom- mender for active user over a period of time. It is updated using This section discusses our proposed approach for making rec- pheromone updating strategy known from ant algorithms as ommendations called Trust based Ant Recommender System discussed in next subsection. Due to its dynamic property, it (TARS)in detail. It works in two phases. Phase I is the Preproces is called Dynamic Trust Pheromone(DTP)in our approach. Ini- ing Phase which is offline. In this phase, directed trust graph ally at time t=O, dtP depends on the following factors: each user is created from user-item rating matrix and information (i Degree of similarity between the partner profiles: The sim- regarding trustworthy users is stored in the database for future larity function measures the similarity between the users recommendations Phase ll is online in which the recommendation based on their ratings on items there are a numberon sers process takes place for the active user. In this phase, a small and sible measures for computing the similarity, for example the best neighborhood is selected for active user based on biological Euclidean distance metric, cosine/vector similarity and the f ant colonies to generate recommendations. Finally. Pearson Correlation metric. Our approach uses Pearson Cor- on discusses a solution to new user(cold start) problem relation coefficient for computing similarity sim(u, v) pheromone updating strategy of ants. Igorithm is briefly outlined as follows: uD=∑(n-hj if Pu>0 Phase I: Preprocessing Phase(Offline process 0 otherwise Step 1 Input data normalization Step 2. Directed trust graph creation for each user based on where rui and rui denote the ratings of users u and v for ith similarity measure and partners' rating profile overlap and item respectively Tu and rr denote the average ratings of storing the information in the database users u and v respectively u and y denote the standard Phase l1: Recommendation process for the active user (online deviation of the ratings of users u and v respectively Pearson Correlation coefficient Pu. p is computed between Step 1. Initialize source node in directed trust graph as active the overlapping part of the rating profiles i.e. on the rat ings of the items that are rated by both the users. The va- Step 2. Select best neighborhood for the active user based on lue of Pu, lies in between -1 to 1 indicating degree of ant colony metaphor imilarity ranging in between 0 to 1. Since Pui <=0 indi- Step 3. Aggregate the ratings of top U trustworthy friends for cates that u and v are not correlated therefore zero and unrated items of active user negative correlations are not considered and all such out Step 5. Update dynamic trust pheromone(DTP)of users (ii) Confidence in a partner profile: It determines the linked to active user in the directed trust graph amount of interest (confidence)a user u should have in (on)user v and viceversa. Amount of confidence a user u should have on user v is given as The following subsections explain TARS in detail. no of items rated by u and v in common 3.1. Phase 1: Preprocessing Phase This probability captures the intuition that user v should have rated many of the items that user u has rated As seen Step 1. Input data normalization. from the equation (3). conf(yu )is large if rating overlap be- Input data is stored in the form of user-item rating matrix in tween the two partners u and vis high and less otherwise. which users represent the rows, the items represent the columns DTP initialization: At time t=0, DTP denoted as tu dt)is nd the values in the cells represent the rating expressed by a computed by combining similarity and confidence mea- user about an item. Since ratings may be real or discrete value sures as follows ranging in different scales, therefore there is a need to normalize hemin the scale O to 1. For example, in our experiments, we have sism upaconfeay if sim(u, v)=0 and conf( wlu) taken two datasets available online namely jester dataset which Tu,D(t=0)=kx conf(vlu) if sim(u, v)=0 and conf(u/u)M=0 has numeric ratings ranging on real value scale from -10 to +10 and MovieLens dataset consisting of ratings ranging in the
accuracy, the explicit trust statements may not always be available (Yuan, Guan, Lee, Lee, & Hur 2010). Also there is a need for producing valuable recommendations when input data is sparse and solving new user problem as the following problems may persist: (i) New user may or may not provide even one trusted friend in community. (ii) Due to sparseness in user–item rating matrix, trusted friends may not be able to provide recommendations for some items but a friend of friend may. (iii) It may be time consuming or expensive to get explicit trust. In addition, the selection of a peer neighborhood containing similar users is a vital function for generating good recommendations. In the sparse data environment, the predicted recommendations often depend on a small portion of the selected neighborhood. Thus in our proposed approach TARS, we have focused on such issues by creating directed trust graph and exploiting it using pheromone strategy known from ant algorithms to provide better recommendations. 3. Proposed Trust based Ant Recommender System (TARS) This section discusses our proposed approach for making recommendations called Trust based Ant Recommender System (TARS) in detail. It works in two phases. Phase I is the Preprocessing Phase which is offline. In this phase, directed trust graph for each user is created from user–item rating matrix and information regarding trustworthy users is stored in the database for future recommendations. Phase II is online in which the recommendation process takes place for the active user. In this phase, a small and best neighborhood is selected for active user based on biological metaphor of ant colonies to generate recommendations. Finally, this section discusses a solution to new user (cold start) problem based on pheromone updating strategy of ants. TARS algorithm is briefly outlined as follows: Phase I: Preprocessing Phase (Offline process) Step 1. Input data normalization Step 2. Directed trust graph creation for each user based on similarity measure and partners’ rating profile overlap and storing the information in the database Phase II: Recommendation process for the active user (online process) Step 1. Initialize source node in directed trust graph as active user node. Step 2. Select best neighborhood for the active user based on ant colony metaphor Step 3. Aggregate the ratings of top U trustworthy friends for unrated items of active user Step 4. Generate recommendations for active user Step 5. Update dynamic trust pheromone (DTP) of users linked to active user in the directed trust graph The following subsections explain TARS in detail. 3.1. Phase I: Preprocessing Phase Step 1. Input data normalization. Input data is stored in the form of user–item rating matrix in which users represent the rows, the items represent the columns and the values in the cells represent the rating expressed by a user about an item. Since ratings may be real or discrete values ranging in different scales, therefore there is a need to normalize them in the scale 0 to 1. For example, in our experiments, we have taken two datasets available online namely Jester dataset which has numeric ratings ranging on real value scale from 10 to +10 and MovieLens dataset consisting of ratings ranging in the discrete scale 1 to 5.We have normalized ratings of both the datasets in the range 0 to 1 as follows: rij ¼ P rij n j¼1rij ð1Þ where rij denotes rating given by ith user for jth item in the user– item rating matrix. n denotes the total number of items in the user–item rating matrix. Step 2. Directed trust graph creation for each user and storing the information in the database. The directed trust graph G = (V, E) is created where V is the set of vertices which corresponds to users and E is the set of edges connecting users. Weight on the edge represents strength of connectedness i.e. trust intensity between the two recommendation partners (recommender and active user) at time t. Trust intensity being dynamic information, increases or decreases with the involvement or non-involvement of user as a recommender for active user over a period of time. It is updated using pheromone updating strategy known from ant algorithms as discussed in next subsection. Due to its dynamic property, it is called Dynamic Trust Pheromone (DTP) in our approach. Initially at time t = 0, DTP depends on the following factors: (i) Degree of similarity between the partner profiles: The similarity function measures the similarity between the users based on their ratings on items. There are a number of possiblemeasures for computing the similarity, for example the Euclidean distance metric, cosine/vector similarity and the Pearson Correlation metric. Our approach uses Pearson Correlation coefficient for computing similarity sim(u, v) between the two users u and v given as: simðu; vÞ ¼ Pu;v ¼ Pðru;iruÞðrv;irv Þ rurv if Pu;v > 0 0 otherwise; ( ð2Þ where ru,i and rv,i denote the ratings of users u and v for ith item respectively ru and rv denote the average ratings of users u and v respectively ru and rv denote the standard deviation of the ratings of users u and v respectively. Pearson Correlation coefficient Pu,v is computed between the overlapping part of the rating profiles i.e. on the ratings of the items that are rated by both the users. The value of Pu,v lies in between 1 to 1 indicating degree of similarity ranging in between 0 to 1. Since Pu,i : ð4Þ P. Bedi, R. Sharma / Expert Systems with Applications 39 (2012) 1183–1190 1185
P Bedi, R Sharma/Expert Systems with Applications 39(2012)1183-1190 where k is a small constant value. Combining sim(u, v)with con- allowed=N-tabuk) denotes the set of nodes not ye f(du)results in two advantages. Firstly, tu.(t) may not be same as tuu(t)which is true in real life scenario and secondly, since n denotes the nodes in the directed trust graph he sparse user-item rating matrix results in sparseness in user (v) Arrange TF(S) in descending order of milarity matrix, therefore tut)=k x conf(iu) when si- Step 3. Aggregating ratings of top U trustworthy friends of m(u, v)=0 but conf(yu)=0 reduces the sparseness problem. active user conf(Mu)+0 indicates that at least u and v are comparable. At Recommendation to an active user for an item is generated by time t=O, Tu,it) may be negligible but later on as the time aggregating the ratings of top U trustworthy users for that passes, user vcan be a trustworthy friend of user u if recommen tem. If top_U=l, then recommendations will be generated dations are continuously generated by him. The advantage of from one most trustworthy user otherwise using the harmonic mean is that it is robust to large differences recommendations will be generated from aggregated inputs so that a high weighting will only be calculated ratings of top_U trustworthy user if sim(u, v) and conf(du)are high. (i)If top_U= l then TF(S)with highest probs(t) is selected otherwise TF(S)with top_U highest probs(t)are selected Once the directed trust graph is created, the database contains (ii) For each unrated item of s do Store top_UTF(S)and their the following information corresponding to each user: users in his ratings in Tabuk(S) trust network, trust intensity(DTP) linked to each user in his trust (iii) The following cases may arise graph and items rated by trustworthy users along with their ratings (a)If top_U=l and Tf(S)with maximum probs(t) has not rated the item i then select next tF(S)with next highest 3. 2. Phase lI: Recommendation process for the active user probs(t) To understand this step consider directed trust subg Here we assume that the directed trust graph of the active user al- as shown in Fig. 1. Let the active user be U,, tFU) in the ready exists. Given a connected directed trust graph, a source node rep- descending order of probi()be U7 and U6. Let the number esenting active user node and a destination node representing of items unrated by Ui be 6. If Top-U= l, then initially U7 ustworthy partner whose location is unknown, a source node gener will be selected If U, has not rated all 6 items then us will es m ants that try to find the path to the destination node based on be selected next for remaining items previously laid pheromones. Each edge of the trust graph contains (b)If ratings for some unrated items of S are not found DIP information which is combined with level of connectedness from and tf(S)nodes of s are exhausted then the active user node to the other node chosen by ants for all the gen- erated ants, there is time to live parameter associated which specifies S=TF(S)with maximum probs(t) the maximum number of iterations that the ant should explore. If the goto step 3(ii) destination node is not found within time to live limit the ant termi- ferring Fig. 1, if few items are not rated nates. since the destination node is not known or in the worst case it then level becomes 2 and child nodes of u will be selected may not exist, therefore a stop point for an ant is essential to prevent (iv) Generate recommendations using Resnick,'s prediction it from running indefinitely. Since node i and node represent informa- formula(resnick et al., 1994), reproduced as follor tion associated to user u and user v respectively, therefore, in this sec- ion, node i and node j are used in place of user u and user v. Recommendation process is described in detail as follows Algorithm for recommendation process Step 1. Initialization where (i)s= active user node Tiit and r, it denote the ratings of node i and j for item it (ii)Level=1 respectively Step 2. Best neighborhood selection for the active user Ti and ri denote the average ratings of node (i Create m ants(m= no. of outgoing links from s) (ii) Place m ants on S ty(t) denotes the trust that node i holds about node j at (iii) Place starting node s of kth ant in tabu(S), where time t k=1...m. Tabuk list is a data structure associated with kth top_u denotes the number of trustworthy users ant which keeps track of the nodes already visited by ant. (v)Update DTP(ti(t))such that it increases for the to forbid it from visiting the same nodes again. trustworthy friends of s i.e. (tf(s) who are involved in (iv)Compute probability probs(t)from directed trust graph generating recommendations and decreases for other users of S and store all trustworthy friends in TF(S). The who are not involved probability of an ant k located at node i selecting node jat time t depends on the amount of dTP(tif(t))and level of connectedness(ni)from source node S. The equation is The aim of pheromone updating strategy in ant algorithms is to in- crease the pheromone values associated with good solutions and to de prob; (C)=max(tg(t))(y)jE allowed crease those that are associated with bad ones. Usually, this is achieved by decreasing all the pheromone values through pheromone evap where tion, and by increasing the pheromone levels associated with a chosen ti(t)denotes trust that node i holds about node j at time t set of good solutions. As time passes, the edges or paths marked by ny-1/ds denotes the heuristic (level)degree of stronger amount of pheromone are chosen with higher probability ansferring trust from node i to node j than those that have weaker amount of pheromone deposit Based dsj indicates the level of connectness from the active user on this strategy, at time t, trust intensity decreases by a small constant node S to node j p=0.01 on all the edges connecting active user and its trustworthy
where k is a small constant value. Combining sim(u, v) with conf(v|u) results in two advantages. Firstly, su,v(t) may not be same as sv,u(t) which is true in real life scenario and secondly, since the sparse user–item rating matrix results in sparseness in user similarity matrix, therefore su,v(t) = k conf(v|u) when sim(u, v) = 0 but conf(v|u) = 0 reduces the sparseness problem. conf(v|u) – 0 indicates that at least u and v are comparable. At time t = 0, su,v(t) may be negligible but later on as the time passes, user v can be a trustworthy friend of user u if recommendations are continuously generated by him. The advantage of using the harmonic mean is that it is robust to large differences between inputs so that a high weighting will only be calculated if sim(u, v) and conf(v|u) are high. Once the directed trust graph is created, the database contains the following information corresponding to each user: users in his trust network, trust intensity (DTP) linked to each user in his trust graph and items rated by trustworthy users along with their ratings. 3.2. Phase II: Recommendation process for the active user Here we assume that the directed trust graph of the active user already exists. Given a connected directed trust graph, a source node representing active user node and a destination node representing trustworthy partner whose location is unknown, a source node generates m ants that try to find the path to the destination node based on previously laid pheromones. Each edge of the trust graph contains DTP information which is combined with level of connectedness from the active user node to the other node chosen by ants. For all the generated ants, there is time to live parameter associated which specifies the maximum number of iterations that the ant should explore. If the destination node is not found within time to live limit, the ant terminates. Since the destination node is not known or in the worst case it may not exist, therefore a stop point for an ant is essential to prevent it from running indefinitely. Since node i and node j represent information associated to user u and user v respectively, therefore, in this section, node i and node j are used in place of user u and user v. Recommendation process is described in detail as follows: Algorithm for recommendation process Step 1. Initialization (i) S = active user node (ii) Level = 1 Step 2. Best neighborhood selection for the active user (i) Create m ants (m = no. of outgoing links from S) (ii) Place m ants on S (iii) Place starting node S of kth ant in tabuk(S), where k = 1 ... m. Tabuk list is a data structure associated with kth ant which keeps track of the nodes already visited by antk to forbid it from visiting the same nodes again. (iv) Compute probability probSi(t) from directed trust graph of S and store all trustworthy friends in TF(S). The probability of an ant k located at node i selecting node j at time t depends on the amount of DTP (sij(t)) and level of connectedness (gij) from source node S. The equation is given as probk ijðtÞ ¼ maxððsijðtÞÞðgijÞÞj 2 allowedk ð5Þ where sij(t) denotes trust that node i holds about node j at time t gij = 1/dsj denotes the heuristic (level) degree of transferring trust from node i to node j dsj indicates the level of connectness from the active user node S to node j allowedk = {N tabuk} denotes the set of nodes not yet visited by antk N denotes the nodes in the directed trust graph (v) Arrange TF(S) in descending order of probSi(t) Step 3. Aggregating ratings of top U trustworthy friends of active user Recommendation to an active user for an item is generated by aggregating the ratings of top U trustworthy users for that item. If top_U = 1, then recommendations will be generated from one most trustworthy user otherwise recommendations will be generated from aggregated ratings of top_U trustworthy users (i) If top_U = 1 then TF(S) with highest probSi(t) is selected otherwise TF(S) with top_U highest probSi(t) are selected (ii) For each unrated item of S do Store top_U TF(S) and their ratings in Tabuk(S) (iii) The following cases may arise: (a) If top_U = 1 and TF(S) with maximum probSi(t) has not rated the item i then select next TF(S) with next highest probSi(t) To understand this step, consider directed trust subgraph as shown in Fig. 1. Let the active user be U1, TF(U1) in the descending order of prob1i(t) be U7 and U6. Let the number of items unrated by U1 be 6. If Top U ¼ 1, then initially U7 will be selected. If U7 has not rated all 6 items then U6 will be selected next for remaining items (b) If ratings for some unrated items of S are not found and TF(S) nodes of S are exhausted then level = level + 1 S = TF(S) with maximum probsi(t) goto step 3(ii) Referring Fig. 1, if few items are not rated by U6 and U7, then level becomes 2 and child nodes of U7 will be selected (iv) Generate recommendations using Resnick’s prediction formula (Resnick et al., 1994), reproduced as follows: ri;it ¼ ri þ Ptop U j¼1 si;jðtÞðrj;it rjÞ Ptop U j¼1 si;jðtÞ ð6Þ where ri,it and rj,it denote the ratings of node i and j for item it respectively ri and rj denote the average ratings of nodes i and j respectively si,j(t) denotes the trust that node i holds about node j at time t top_U denotes the number of trustworthy users (v) Update DTP (sij(t)) such that it increases for the trustworthy friends of S i.e. (TF(S)) who are involved in generating recommendations and decreases for other users who are not involved The aim of pheromone updating strategy in ant algorithms is to increase the pheromone values associated with good solutions and to decrease those that are associated with bad ones. Usually, this is achieved by decreasing all the pheromone values through pheromone evaporation, and by increasing the pheromone levels associated with a chosen set of good solutions. As time passes, the edges or paths marked by stronger amount of pheromone are chosen with higher probability than those that have weaker amount of pheromone deposit. Based on this strategy, at time t, trust intensity decreases by a small constant q = 0.01 on all the edges connecting active user and its trustworthy 1186 P. Bedi, R. Sharma / Expert Systems with Applications 39 (2012) 1183–1190
P. Bedi, R Sharma/ Expert Systems with Applications 39(2012)1183-1190 utation of△Q Path from node s to node j mv(-1) 比;二 0.52 .72 U1→Ux→U3→U 08*09*0.59=0424 0424/3)*(1/6)=0.023 The level of connectedness(dsi)indicates the distance of recom- mender j from active user S ie farther the recommender from active user. the less reliable is the inferred value of II, T, (t-1)/ds. As ds increases. II, Ty(t-1)/dsydecreasesAlso U since the number of items traced by trustworthy users varies. therefore the weight T-traced,/T-unrateds is assigned accordingly This effect is depicted in Table 1 To understand the computation of AQ, consider directed trust subgraph of active user s= Ui as shown in Fig. 1. Let tunrateds be6,t17=0.8,t16=0.52,t73=0.9andt32=0.59. Table1 shows U the computation of△Q Referring to Fig. 1. Tables 2 and 3 show the effect of DTP while generating recommendations computed using equation(7). Although U6 and U, are at the same level and have same DtPva- Fig. 1. Trustworthy friends of active user U lue initially, since number of items traced by U7 is more than that of U6, therefore DtP associated to U7 is more and TF(U7)are se- lected at next level. Also DTP(U1)-DTP(U)=1.0 if i DTP on the edges linking UI with other users at time [=0, DTP evaporation DTP associated to U3, U4. Us and Ug has been increased and edges linking U, with other users at level= I when 4 out of 6 it amount by which they are increased varies depending on number e rated by Us and U. of items traced by them UU U3 U4 Us U. Us Ug U10 U1(t=0)1.000000.16 0.1667000 3.3. A solution to new user(cold start) problem DTPe)1.000000.16500.1650000 DTPd)1000000.226902475000 In the directed trust graph, dTP is aggregated on each edge con- necting trustworthy users and active user. When recommenda- friends and increases by a small quantity AQon theedges connecting tions are generated for an active user, local DTP is computed.The active user and its trustworthy friends involved in generating rec- of a user and number of incoming links to a user results in compu- summation of aggregated DTP corresponding to all incoming links ommendations. dtP update rule is given as tation of global DTP. Users benefit from this wisdom of crowds be- t()=(1-p)t(t-1)+△Q (7) cause global DTP acts as positive feedback reflecting behavior that is universally considered good or bad and defines"popularity"of a user as recommender over a period of time. List of"popular"users p is a constant that represents the evaporation rate of DTP be-(say 2 or 3 users)with high DTP can act as default list of friends at tween time t-1 and t to avoid its unlimited accumulation AQ is a small quantity computed as follows time t and be added as friends of new user at initial stage (t-1) 4. Experimental study T-traced The experimental study was conducted on two different types of datasets viz. the jester dataset and MovieLens dataset available denotesthetransferofusers'trust-pheromonefromonlineonwebsiteswww.ieor.berkeleyedu/-goldberg/jester-data activeusernodestonodej.Ifdsj2thenitisdefinedastu2(t)=andwww.grouplens.org/node/73,respectivelyMovielensdataset t+(t)xt+1.+2() is relatively much sparser as compared to Jester dataset. Jester dsj denotes the level of connectedness from the active user node dataset has 73, 421 user entered numeric ratings for 100 jokes S to nod L2. traced, denotes the number of items traced by user at node j set consists of 100,000 ratings ranging in the discrete scale 1 to 5 hich are unrated by active user node s rom 943 users on 1682 movies. We restricted the number of T_unrateds denotes the total number of items unrated by active users to first 1500 users in Jester dataset and 500 users in Movie- Lens dataset Since Jester dataset contains ratings of 100 jokes. DTP on the edges linking U7 with other users at time t=0, DTP evaporation and deposition on the edges linking U, with other users at level 2, when remaining 2 items are also rated by tFU). 00294 00690 0690 00883 THe) 0.0291 00683 0683 0029 0.0683 0986 2814 0068 00768 00768 00874 0.1109 0.2814
friends and increases by a small quantityDQ on the edges connecting active user and its trustworthy friends involved in generating recommendations. DTP update rule is given as: sijðtÞ¼ð1 qÞsijðt 1Þ þ DQ ð7Þ where q is a constant that represents the evaporation rate of DTP between time t 1 and t to avoid its unlimited accumulation. DQ is a small quantity computed as follows: DQ ¼ QdSj i¼1 sijðt 1Þ dSj T tracedj T unratedS whereQdSj i¼1sij denotes the transfer of users’ trust-pheromone from active user node S to node j. If dSj = 2 then it is defined as si,i+2(t) = si,i+1(t) si+1, i+2(t). dSj denotes the level of connectedness from the active user node S to node j. T tracedj denotes the number of items traced by user at node j which are unrated by active user node S. T unratedS denotes the total number of items unrated by active user node S. The level of connectedness (dSj) indicates the distance of recommender j from active user S i.e. farther the recommender from active user, the less reliable is the inferred value of QdSj i¼1sijðt 1Þ=dSj. As dSj increases, QdSj i¼1sijðt 1Þ=dSj decreases. Also, since the number of items traced by trustworthy users varies, therefore the weight T tracedj=T unratedS is assigned accordingly. This effect is depicted in Table 1. To understand the computation of DQ, consider directed trust subgraph of active user S = U1 as shown in Fig. 1. Let T unratedS be 6, s17 = 0.8, s16 = 0.52, s73 = 0.9 and s32 = 0.59. Table 1 shows the computation of DQ. Referring to Fig. 1, Tables 2 and 3 show the effect of DTP while generating recommendations computed using equation (7). Although U6 and U7 are at the same level and have same DTP value initially, since number of items traced by U7 is more than that of U6, therefore DTP associated to U7 is more and TF(U7) are selected at next level. Also DTP(Ui) = DTP(Uj) = 1.0 if i = j. DTP associated to U3, U4, U5 and U9 has been increased and amount by which they are increased varies depending on number of items traced by them. 3.3. A solution to new user (cold start) problem In the directed trust graph, DTP is aggregated on each edge connecting trustworthy users and active user. When recommendations are generated for an active user, local DTP is computed. The summation of aggregated DTP corresponding to all incoming links of a user and number of incoming links to a user results in computation of global DTP. Users benefit from this wisdom of crowds because global DTP acts as positive feedback reflecting behavior that is universally considered good or bad and defines ‘‘popularity’’ of a user as recommender over a period of time. List of ‘‘popular’’ users (say 2 or 3 users) with high DTP can act as default list of friends at time t and be added as friends of new user at initial stage. 4. Experimental study The experimental study was conducted on two different types of datasets viz. the Jester dataset and MovieLens dataset available online on websites www.ieor.berkeley.edu/~goldberg/jester-data and www.grouplens.org/node/73, respectively. MovieLens dataset is relatively much sparser as compared to Jester dataset. Jester dataset has 73,421 user entered numeric ratings for 100 jokes ranging on real value scale from 10 to +10. The MovieLens dataset consists of 100,000 ratings ranging in the discrete scale 1 to 5 from 943 users on 1682 movies. We restricted the number of users to first 1500 users in Jester dataset and 500 users in MovieLens dataset. Since Jester dataset contains ratings of 100 jokes, Table 1 Computation of DQ. Path from node S to node j QdSj i¼1sijðt 1Þ T tracedj DQ U1 ? U7 0.8 3 (0.8/1) (3/6) = 0.4 U1 ? U6 0.52 1 (0.52/1) (1/6) = 0.086 U1 ? U7 ? U3 0.8 0.9 = 0.72 1 (0.72/2) (1/6) = 0.06 U1 ? U7 ? U3 ? U2 0.8 0.9 0.59 = 0.424 1 (0.424/3) (1/6) = 0.023 U1 U7 U6 U9 U5 U4 U3 U2 Fig. 1. Trustworthy friends of active user U1. Table 2 DTP on the edges linking U1 with other users at time t = 0, DTP evaporation and deposition on the edges linking U1 with other users at level = 1 when 4 out of 6 items are rated by U6 and U7. U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U1(t = 0) 1.0 0 0 0 0 0.1667 0.1667 0 0 0 DTP(e) 1.0 0 0 0 0 0.1650 0.1650 0 0 0 DTP(d) 1.0 0 0 0 0 0.2269 0.2475 0 0 0 Table 3 DTP on the edges linking U7 with other users at time t = 0, DTP evaporation and deposition on the edges linking U7 with other users at level = 2, when remaining 2 items are also rated by TF(U7). U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U7 (t = 0) 0.0294 0.0690 0.0690 0.0294 0.0690 0.0883 1.0 0.0294 0.0996 0.2814 DTP(e) 0.0291 0.0683 0.0683 0.0291 0.0683 0.0874 1.0 0.0291 0.0986 0.2814 DTP(d) 0.0291 0.0683 0.0768 0.0328 0.0768 0.0874 1.0 0.0291 0.1109 0.2814 P. Bedi, R. Sharma / Expert Systems with Applications 39 (2012) 1183–1190 1187
P Bedi, R Sharma/ Expert Systems with Applications 39(2012)1183-1190 therefore we restricted the number of movies to 100 in Movie- Table Lens dataset Sample output obtained from Jester dataset and MovieLens hen test Set=25, Trust_Users =10, Top_N= 10 on user-item rating matr (Here P stands for Precision in % R stands for Recall in g and F denotes FI metric 4.1. Evaluation metric 500x100 000x1001500×100 Precision and recall are the most popular metrics for evaluating lens Jester MovieLens Jester information retrieval systems. For the evaluation of recommender systems, they have been used by various researchers( Basu, Hirsh, 29.72262 Cohen, 1998: Billsus Pazzani, 1998: Sarwar, Karypis, Konstan F142453742434838.51 4356 45.34 reidl, 2000a, 2000b). Precision is a measure of exactness or fidel- ty and recall is a measure of completeness. Precision score of 100% indicates that every recommendation retrieved was relevant. Re- Test Set=25. Trust Users=10 call score of 100% indicates that all relevant recommendations Top_ N=10 Jester Dataset) were retrieved. Several ways to evaluate precision and recall exists and the most appropriate way is to predict the top N items for which the user's ratings already exists In this method, a users rat ings are taken and divided into a training set and a test set. algo- 口 Recall rithm is then trained on the training set and top N items are predicted from that user's test set. Items that appear in both sets, become members of a special set, called the hit set(Herlocker, Konstan, Terveen, Reidl, 2004). Recall and precision for top-N rec- ommendations can be defined as follows: Recall is a global measure for the whole dataset. When referring to recommender systems, it can be defined as the ratio of the hit set size to the test set size User-Item Rating Matrix Recall size of hit set [test ntop-NI Fig. 2. Partial sample output depicting influence of ant (user colony size. Precision, when referring to recommender systems, can be defined or trustworthy users(Trust_Users)was taken as 1, 10, 20 and 30. as the ratio of hit set size to the top-N set size. It gives the average Parameter p(evaporation rate)was initialized with small constant quality of an individual recommendation. value 0.01, as the small value of p indicates slow evaporation and large value indicates fast evaporation Parameter k for computing (9) DTP was initialized to 0. 2. Traditional Collaborative Filtering based recommendation approach was also implemented to test the These two measures are clearly conflicting in nature. If the numbe performance of our system TARS of recommendations(N) produced increases, then the value of reca The following observations were made from the results increases, while at the same time precision is decreased. But since btained. both recall and precision are important in evaluating the perfor mance of a system that generates top-N recommendations, they (a) Influence of ant colony size(i.e number of users involved in can be combined with equal weights to get a single metric, the FI forming directed trust graph) on recommendations: As metric. It consists of weighted combination of precision and recall. shown in Table 4, with the increase in colony size from The general formula for F-measure( for non-negative real a)is 100 to 1500, precision and recall also increases. The same effect is depicted in Fig. 2. F(1+a)x Precision x Recall (b)As Top_Increases, precision decreases and Recall increases a2 x Precision +Recall It can be seen in Table 5 and Fig. 3 that precision dropped smoothly as the number of recommendations (Top_n) when a= 1, it is known as Fi measure and represents the weighted ncreased. This is expected as the average quality of the rec- harmonic mean of precision and recall giving equal weights to ommendations made decreases as the number of recom- mendation to be made increases on the other hand. recall F,、2× Precision x Recall increased as the value of Top_n increased from 2 to 10. F1 and recall is achieved for high values of Top_n Higher values of F, indicate a more balanced combination between (c) Comparison of TARS with traditional CF approach recall and precision. Precision, Recall and Fi measures are used as evaluation metrics for our approach TARS Traditional CF approach was implemented by computing sim- ilarity among users using Pearson Correlation Coefficient and pre 4. 2. Experimental results dicting ratings using Resnick's prediction formula(Resnick et al 1994). At time t=0, if conf(u) is not combined with sim(u, D) TARS was implemented in MATLAB version 7.2 on Microsoft then CF and tArs produce similar results as they have no differ Windows Operating System. The analysis was done for different ence, but if conf(u v) is combined with sim(u, D), tArS produces viz. 100 x 100, 500x 100, 1000 x 100 and 1500 x 100 in Jester friends' list of an active user might change due to increap hy est sets=5. 15 and 25 er-item rating matrix of different sizes better results. As the time passes (i.e. at time t>O), trustor dataset and 100 x 100 and 500 x 100 in MovieLens dataset by decrease in DTP. This results in better recommendations. As the varying the values of Top_n and number of trustworthy users detailed results on all the user-item rating submatrices with all (Trust_Users). For test set=5, Top_N=1,2, 3: for test set=15, varying parameters can not be shown, partial result is shown in Top_N=2. 5. 10: for test set= 25, Top_N= 5, 10, 15. The number the Table 6 and Fig 4
therefore, we restricted the number of movies to 100 in MovieLens dataset. 4.1. Evaluation metric Precision and recall are the most popular metrics for evaluating information retrieval systems. For the evaluation of recommender systems, they have been used by various researchers (Basu, Hirsh, & Cohen, 1998; Billsus & Pazzani, 1998; Sarwar, Karypis, Konstan, & Reidl, 2000a, 2000b). Precision is a measure of exactness or fidelity and recall is a measure of completeness. Precision score of 100% indicates that every recommendation retrieved was relevant. Recall score of 100% indicates that all relevant recommendations were retrieved. Several ways to evaluate precision and recall exists and the most appropriate way is to predict the top N items for which the user’s ratings already exists In this method, a user’s ratings are taken and divided into a training set and a test set. Algorithm is then trained on the training set and top N items are predicted from that user’s test set. Items that appear in both sets, become members of a special set, called the hit set (Herlocker, Konstan, Terveen, & Reidl, 2004). Recall and precision for top-N recommendations can be defined as follows: Recall is a global measure for the whole dataset. When referring to recommender systems, it can be defined as the ratio of the hit set size to the test set size. Recall ¼ size of hit set size of test set ¼ jtest \ top Nj jtestj ð8Þ Precision, when referring to recommender systems, can be defined as the ratio of hit set size to the top-N set size. It gives the average quality of an individual recommendation. Precision ¼ size of hit set size of top N set ¼ jtest \ top Nj top N ð9Þ These two measures are clearly conflicting in nature. If the number of recommendations (N) produced increases, then the value of recall increases, while at the same time precision is decreased. But since both recall and precision are important in evaluating the performance of a system that generates top-N recommendations, they can be combined with equal weights to get a single metric, the F1 metric. It consists of weighted combination of precision and recall. The general formula for F-measure (for non-negative real a) is Fa ¼ ð1 þ a2Þ Precision Recall a2 Precision þ Recall ð10Þ when a = 1, it is known as F1 measure and represents the weighted harmonic mean of precision and recall giving equal weights to them. F1 ¼ 2 Precision Recall Precision þ Recall ð11Þ Higher values of F1 indicate a more balanced combination between recall and precision. Precision, Recall and F1 measures are used as evaluation metrics for our approach TARS. 4.2. Experimental results TARS was implemented in MATLAB version 7.2 on Microsoft Windows Operating System. The analysis was done for different test sets = 5, 15 and 25 on user–item rating matrix of different sizes viz. 100 100, 500 100, 1000 100 and 1500 100 in Jester dataset and 100 100 and 500 100 in MovieLens dataset by varying the values of Top_N and number of trustworthy users (Trust_Users). For test set = 5, Top_N = 1, 2 ,3; for test set = 15, Top_N = 2, 5, 10; for test set = 25, Top_N = 5, 10, 15. The number of trustworthy users (Trust_Users) was taken as 1, 10, 20 and 30. Parameter q (evaporation rate) was initialized with small constant value 0.01, as the small value of q indicates slow evaporation and large value indicates fast evaporation. Parameter k for computing DTP was initialized to 0.2. Traditional Collaborative Filtering based recommendation approach was also implemented to test the performance of our system TARS. The following observations were made from the results obtained: (a) Influence of ant colony size (i.e. number of users involved in forming directed trust graph) on recommendations: As shown in Table 4, with the increase in colony size from 100 to 1500, precision and recall also increases. The same effect is depicted in Fig. 2. (b) As Top_N increases, precision decreases and Recall increases. It can be seen in Table 5 and Fig. 3 that precision dropped smoothly as the number of recommendations (Top_N) increased. This is expected as the average quality of the recommendations made decreases as the number of recommendation to be made increases. On the other hand, recall increased as the value of Top_N increased from 2 to 10. F1 measure indicates that the best combination of precision and recall is achieved for high values of Top_N. (c) Comparison of TARS with traditional CF approach Traditional CF approach was implemented by computing similarity among users using Pearson Correlation Coefficient and predicting ratings using Resnick’s prediction formula (Resnick et al. 1994). At time t = 0, if conf(v|u) is not combined with sim(u, v) then CF and TARS produce similar results as they have no difference, but if conf(u|v) is combined with sim(u, v), TARS produces better results. As the time passes (i.e. at time t > 0), trustworthy friends’ list of an active user might change due to increase or decrease in DTP. This results in better recommendations. As the detailed results on all the user–item rating submatrices with all varying parameters can not be shown, partial result is shown in the Table 6 and Fig. 4. Table 4 Sample output obtained from Jester dataset and MovieLens dataset when Test Set = 25, Trust_Users = 10, Top_N = 10 on user–item rating matrix of varying sizes. (Here P stands for Precision in %, R stands for Recall in % and F1 denotes F1 metric.) 100 100 500 100 1000 100 1500 100 Jester MovieLens Jester MovieLens Jester Jester P 74.3 65.5 76.1 67.4 76.23 79.35 R 29.72 26.2 30.44 26.94 30.49 31.74 F1 42.45 37.42 43.48 38.51 43.56 45.34 Test Set=25, Trust_Users=10, Top_N=10 (Jester Dataset) 0 10 20 30 40 50 60 70 80 100x100 500x100 1000x100 1500x100 User-Item Rating Matrix Precision, Recall, F1 Precision Recall F1 Fig. 2. Partial sample output depicting influence of ant (user) colony size. 1188 P. Bedi, R. Sharma / Expert Systems with Applications 39 (2012) 1183–1190
P. Bedi, R Sharma/ Expert Systems with Applications 39(2012)1183-1190 89 for the system to compare him / her with other users and find ed from Jester dataset and MovieLens dataset when Test possible neighborhood. This problem can be solved through stands for Precision in % R stands for Recall in and Fi denotes FI metric) he application of pheromone strategy known from ant alge rithms. Since the dynamic trust pheromone(DTP) value Top_N=2 ⊥N=5 Te ssociated to the users is always updated whether they pro- Jester MovieLens Jester MovieLens Jester Movielens uce recommendations or not, therefore, as the time passes, the set of users who have produced recommendations for maximum users, will have high associated DTP value. This F1225621.74 419 379 44.01379 list of default trusted friends can be captured and automat ically added to the new users list at initial stage. Test Set=15, User-item Rating Matrix (ii The data sparsity in user-item rating matrix results in 500x100, Trust_ Users=20( MovieLens arseness of user similarity matrix which is reduced in Dataset our proposed approach tars by combining sim(u, v) with nf(du) while creating directed trust graph of each user at time t=O As the time passes, valuable recommendations by continuously updating dynamic trust Top N=2 between users and selecting a small and best neighborhood 口 Top N=10 Further, our approach can be used as part of a more broad rec ommendation explanation which not only improves user satisfac- tion, but also helps users make better decisions. Along with the predicted rating if the active user is displayed additional informa tion regarding the level of connectedness in trust graph from where recommendations are generated items and number of Fig. 3. Effect of Top_N on Precision and RecalL neighbors involved in predicting rating then this transparency Table 6 might increase the faith in user about the recommendations. This esults obtained using traditional CF algorithm, our approach TARS at time t= 0(Le. explanation reveal why an active user might like an item as well when dtP is initialized and DTP as an indication of confidence of the predicted rating then DTP updation takes place)on jester dataset an As an example consider directed trust subgraph shown in Fig dataset when Test Set=25, Trust_Users=30 and Top_N= 10 on user matrix of size 100 x 100. (Here P stands for Precision in %, R stands for Recall in an For an active user U1, if 4 out of 6 items are rated by U6, U7 at level Fn denotes Fi mett I and by child nodes of U, at level 2. Remaining 2 items are rated by child nodes of u7(as they are not rated by U6 U7 at level 1)then TARS (ester) TARS (MovieLens) the explanation is as follows 73.2776 Item number: 3. 5. 6. 10 24.33 Predicted rating: 0.6. 0.78, 0.59, 0.92 F137084586 No. of neighbors involved in predicting rating: 6. Level of connectedness in trust graph(from U1): 1 and 2. 43. Discussion Item number: 2. 8 Predicted rating: 0.43, 0.75 Our proposed approach TARS focuses on two main weaknesses No of neighbors involved in predicting rating: 4. which CF based recommender systems suffer from viz. new user Level of connectedness in trust graph(from U1: 2. problem and generating good recommendations from the user tem rating matrix even in the case of sparseness as follows: Results from table 6 depict that while generating recommenda- tions on two datasets viz. Jester dataset and MovieLens dataset. (i)New User(cold start)problem: This problem occurs when precision is increased by approximately 8% and 3% respectively recommendations are to be generated for user who has not using our approach tars at time t=0 and approximately by 12% lted any item or rated very few items since it is difficult and 8% respectively at time t>0 as compared to traditional Test Set=25, Top N=10, User-Item Rating Matrix 100x 100, Trust Users=30 80 口 Precision MoMieLens Dataset Fig 4. Results obtained from CF and TARS approach on MovieLens and Jester Datasets
4.3. Discussion Our proposed approach TARS focuses on two main weaknesses which CF based recommender systems suffer from viz. new user problem and generating good recommendations from the user– item rating matrix even in the case of sparseness as follows: (i) New User (cold start) problem: This problem occurs when recommendations are to be generated for user who has not rated any item or rated very few items since it is difficult for the system to compare him/her with other users and find possible neighborhood. This problem can be solved through the application of pheromone strategy known from ant algorithms. Since the dynamic trust pheromone (DTP) value associated to the users is always updated whether they produce recommendations or not, therefore, as the time passes, the set of users who have produced recommendations for maximum users, will have high associated DTP value. This list of default trusted friends can be captured and automatically added to the new user’s list at initial stage. (ii) The data sparsity in user–item rating matrix results in sparseness of user similarity matrix which is reduced in our proposed approach TARS by combining sim(u,v) with conf(v|u) while creating directed trust graph of each user at time t = 0. As the time passes, valuable recommendations are produced by continuously updating dynamic trust between users and selecting a small and best neighborhood using ant colony metaphor. Further, our approach can be used as part of a more broad recommendation explanation which not only improves user satisfaction, but also helps users make better decisions. Along with the predicted rating if the active user is displayed additional information regarding the level of connectedness in trust graph from where recommendations are generated, items and number of neighbors involved in predicting rating then this transparency might increase the faith in user about the recommendations. This explanation reveal why an active user might like an item as well as an indication of confidence of the predicted rating. As an example consider directed trust subgraph shown in Fig. 1. For an active user U1, if 4 out of 6 items are rated by U6, U7 at level 1 and by child nodes of U7 at level 2. Remaining 2 items are rated by child nodes of U7 (as they are not rated by U6, U7 at level 1) then the explanation is as follows: Item number: 3, 5, 6, 10. Predicted rating: 0.6, 0.78, 0.59, 0.92. No. of neighbors involved in predicting rating: 6. Level of connectedness in trust graph (from U1): 1 and 2. Item number: 2, 8. Predicted rating: 0.43, 0.75. No. of neighbors involved in predicting rating: 4. Level of connectedness in trust graph (from U1): 2. Results from table 6 depict that while generating recommendations on two datasets viz. Jester dataset and MovieLens dataset, precision is increased by approximately 8% and 3% respectively using our approach TARS at time t = 0 and approximately by 12% and 8% respectively at time t > 0 as compared to traditional Table 5 Sample output obtained from Jester dataset and MovieLens dataset when Test Set = 15, Trust_Users = 20 on user–item rating matrix of size 500 100. (Here P stands for Precision in %, R stands for Recall in % and F1 denotes F1 metric.) Top_N = 2 Top_N = 5 Top_N = 10 Jester MovieLens Jester MovieLens Jester MovieLens P 95.9 92.4 83.8 75.8 55.02 47.38 R 12.78 12.32 27.93 25.26 36.68 31.58 F1 22.56 21.74 41.9 37.9 44.01 37.9 Test Set=15, User-Item Rating Matrix 500x100, Trust_Users=20 (MovieLens Dataset) 0 10 20 30 40 50 60 70 80 90 100 Precision Recall F1 Top_N=2 Top_N=5 Top_N=10 Fig. 3. Effect of Top_N on Precision and Recall. Table 6 Results obtained using traditional CF algorithm, our approach TARS at time t = 0 (i.e. when DTP is initialized and DTP updation does not take place) and at time t > 0 i.e. after 100 iterations (when DTP updation takes place) on Jester dataset and MovieLens dataset when Test Set = 25, Trust_Users = 30 and Top_N = 10 on user–item rating matrix of size 100 100. (Here P stands for Precision in %, R stands for Recall in % and F1 denotes F1 metric). CF TARS (Jester) TARS (MovieLens) Jester MovieLens t = 0 t > 0 t = 0 t > 0 P 64.9 61.15 73.2 77.6 67.4 73 R 25.96 36.69 24.4 31.04 26.96 24.33 F1 37.08 45.86 36.6 44.34 38.51 36.5 Test Set=25, Top_N=10, User-Item Rating Matrix 100x100, Trust_Users=30 0 10 20 30 40 50 60 70 80 t=0 t>0 t=0 t>0 CF TARS CF TARS Jester Dataset MovieLens Dataset Precision, Recall, F1 Precision Recall F1 Fig. 4. Results obtained from CF and TARS approach on MovieLens and Jester Datasets. P. Bedi, R. Sharma / Expert Systems with Applications 39 (2012) 1183–1190 1189
P Bedi, R Sharma/ Expert Systems with Applications 39(2012)1183-1190 Collaborative Filtering based recommender system. Also, compar- Goldberg, K, Roeder, T- Gupta, D& Perkins, C(2001).Eigentaste: A constant time ing the performance of TARS on both the datasets taking different collaborative filtering algorithm. Information Retrieval Jourmal. 4(2). 133-151 sparseness levels into account, precision using jester dataset is in- Herlocker, ). L, Konstan, J. A, Terveen, L G, Reidl, ].(2004). Evaluating ased approximately by 5.8% at time t=O and by 3.6% at time t>0 as compared to MovieLens dataset. Hill, w,Stead, L Rosenstein, M.& Furnas, G (1995). Recommending and evaluatin 5 Conclusions Addison-wesley p crisping systems. Denver Colorado, United States, ACM Press/ The success of Collaborative Filtering technology depends on Konstan, J.A., Miller, B N, Maltz, D, Herlocker, J. L Gordon, LR,& Riedl,]. (1997). r ne f a peer neighborhood containing similar users is a vital function Lorenzi. F. Santos. DSdo azzan, ALC(2005). Case-based recommender for generating valuable recommendations. In the sparse data envi- Congresso da Sociedade Braseilera de Computacao, Sao Leopolda, pp. 752-76 ronment, the predicted recommendations often depend on a small Massa, P& Avesani, P(2004). Trust-aware collaborative filtering for recommender portion of the selected neighborhood. In our proposed system TARS, sparseness in user similarity due to data sparsity of input Massa). P. Avesani. P: (2007), Prust-aware recommender systems Dynamic trust pheromone updation for each user in the directed esra sys s bhattacharjee B, (2004) Using trust in recommender systers: a- gement. Oxford, England, pp. 221-235. his recommendation partner. It indicates that trustw iness of a Massa, P. Avesani, P( 2009) Trust metrics in recommender systems. computing partner is the function of the time and inter-operation between the ith Social Trust. London: Springer, pp. 259-285, doi: 10. 1007/ 978-1-84800- 56-9 graph, the optimal trust path is searched effectively resulting in the 10th International Conference on Intelligent User Interfaces(IUr05), San Diego, for recommendation by providing addition information along with Resnick, P, Lakoya pp 167-12k ak, M, Bergstrom, P& Riedl, J. (1994). GroupLens: An open architecture for collaborative filtering of Netnews, in Proceedings of the the predicted rating regarding the level of connectedness in trust cooperative work, Chapel Hil, North graph from where recommendations are generated, items and number of neighbors involved in predicting rating. This not only es user satisfaction, but also helps users make better deci- Rich, E(1979). User modeling via stereotypes. Cognitive Science Journal. Elsevier. ions as it acts as an indication of confidence of the predicted rat ng. Also, new users highly benefit from pheromone updating J,& MuhIhauser, M.(2006). A Classification of trust systems. 06. Berlin: Springer, pp S strategy known from ant algorithms. The Many are smarter than Sarwar, B M, Karypis, G, Konstan, J. A& Reidl, J.(2000a). Analysis of the Few and users benefit from this wisdom of crowds as positive feedback in the form of aggregated dynamic trust pheromone de- tion generation application which has input in the form of r-item rating matrix. The performance of TARS is evaluated Sarw度MKm0mm账mr毁 nstan,.A& Riedl, ]. (2001) Item-based collaborative using Jester dataset and MovieLens dataset available online and compared with traditional Collaborative Filtering based approach Schafer. J. B, Konstan, J.A,& Reidl, J(1999) Recommender systems in E- for generating recommendations. It is found that our approach generates better results as compared to traditional CF based Schafer, J.B. Frankowski locker, -& Sen, S (2007) Collaborative filtering Springer,pp.291-324SBN:9783-540-72078-2 on Human Factors in Computing Systems, Denver, Colorado, United Basu, C, Hirsh, H,& Cohen social and content-based information in recommendation, in Proceedings of the Sharma, R, Singh, M, Makkar, R, Kaur, H, Bedi, P (2007). Ant Recommender: Artificial Intelligence (AAAl-98) Madison, ecommender system inspired by ant colony, in Proceedings of international nference on Advances in Computer Vision and Information Technology(ACVI- R, Kaur, H(2009). Recommender System based on collaborativ n using ant 998) Learning collaborative information filters, in Proceedings of the Fifteenth International Conference on Machine Learning, Terveer en L. Hill. w. Amento. B D. er,J (1997). PHOAKS: A system sharingrecommendationsCommunicationsoftheAcm,40(3),59-62.http:// Blum, C(2005) Ant Colony Optimization: Introduction and recent trends. Physics Bonjplrev. 2005 10.00, Journal, Elsevier, 2(4). pp. 353-373. doi: 10.1016/ Terveen, L,& Hill, W(2001). Human-Computer collaboration in recommender puter 487-509) neraulaz, rom natural mplexity ew York). ISBN: 0-19-51315s Burke, R(2002). Hybrid rec 31.doi:10.1109/s1s2003.1202257 ng and User-Adapted Interaction Journal 12(4). L ge. D Procedintley P3.(2003). Particle Swarm Optimization recommender system. or E-Co A:1008286413827 Dorigo, M, Maniezzo, v,& Colorni, A (1996) Ant System: Optimization by a colony hengdu,pp.14,lSBN:1-4244-0885-7,doi:10.1109 ICSSSM20074280307 nsactions on Systems, Man, and Cybernetics-PartB, Yuan, w Guan, D, Lee, Y. K Lee, S,& Hur, SI(2010). Improved trust-aware oldness of trust networks. Knowledge- Dorigo, M, Stutzle, T (2004). Ant Colony Optimization. Cambridge, MA: MIT Press. BN0-262-04219 Ziegler, C N.& Nicolas, G..(2007). Investigating correlations of trust and interest Goldberg, D, Nicholas, D, Oki, B. M,& Terry, D.(1992). Using collaborative similarity- Do birds of a feather really flock together? Decision Support Systems, fltering to weave an informatio try. Co cations of the ACM, 35(12) 43(2).460-475 61-70
Collaborative Filtering based recommender system. Also, comparing the performance of TARS on both the datasets taking different sparseness levels into account, precision using Jester dataset is increased approximately by 5.8% at time t = 0 and by 3.6% at time t > 0 as compared to MovieLens dataset. 5. Conclusions The success of Collaborative Filtering technology depends on the process of locating people with similar neighbors. The selection of a peer neighborhood containing similar users is a vital function for generating valuable recommendations. In the sparse data environment, the predicted recommendations often depend on a small portion of the selected neighborhood. In our proposed system TARS, sparseness in user similarity due to data sparsity of input matrix is reduced while creating directed trust graph for each user. Dynamic trust pheromone updation for each user in the directed trust graph reflects the degree to which an active user might trust his recommendation partner. It indicates that trustworthiness of a partner is the function of the time and inter-operation between the two partners. By applying ant colony algorithm on directed trust graph, the optimal trust path is searched effectively resulting in best neighborhood. Further our approach is used as an explanation for recommendation by providing addition information along with the predicted rating regarding the level of connectedness in trust graph from where recommendations are generated, items and number of neighbors involved in predicting rating. This not only improves user satisfaction, but also helps users make better decisions as it acts as an indication of confidence of the predicted rating. Also, new users highly benefit from pheromone updating strategy known from ant algorithms. The Many are smarter than the Few and users benefit from this wisdom of crowds as positive feedback in the form of aggregated dynamic trust pheromone de- fines ‘‘popularity’’ of a user as recommender over a period of time. Our proposed approach can be implemented for any recommendation generation application which has input in the form of user–item rating matrix. The performance of TARS is evaluated using Jester dataset and MovieLens dataset available online and compared with traditional Collaborative Filtering based approach for generating recommendations. It is found that our approach generates better results as compared to traditional CF based approach. References Basu, C., Hirsh, H., & Cohen, W.W. (1998). Recommendation as classification: using social and content-based information in recommendation, in Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI-98). Madison, Wisconsin, AAAI Press, pp. 714–720. Bedi, P., Sharma, R., & Kaur, H. (2009). Recommender System based on collaborative behavior of ants, Journal of Artificial Intelligence 2009, Asian Network for Scientific Information, ISSN 1994–5450, pp. 40–55. Billsus, D. &. Pazzani, M. J. (1998). Learning collaborative information filters, in Proceedings of the Fifteenth International Conference on Machine Learning, Madison, Morgan Kaufman San Francisco, CA, pp. 46–54. Blum, C. (2005). Ant Colony Optimization: Introduction and recent trends. Physics of Life Reviews Journal, Elsevier, 2(4), pp. 353–373. doi:10.1016/ j.plrev.2005.10.001. Bonabeau, E., Dorigo, M. & Theraulaz, G. (1999). Swarm Intelligence: From natural to artificial systems. Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press (New York). ISBN: 0-19-513158-4, Kindle Edition. Burke, R. (2002). Hybrid recommender systems: Survey and experiments. User Modeling and User-Adapted Interaction Journal, 12(4), 331–370. doi:10.1023/ A:1008286413827. Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 29–41. Dorigo, M., & Stutzle, T. (2004). Ant Colony Optimization. Cambridge, MA: MIT Press. ISBN 0-262-04219-3. Goldberg, D., Nicholas, D., Oki, B. M., & Terry, D. (1992). Using collaborative filtering to weave an information tapestry. Communications of the ACM, 35(12), 61–70. Goldberg, K., Roeder, T., Gupta, D., & Perkins, C. (2001). Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval Journal, 4(2), 133–151. doi:10.1.1.37.8212. Herlocker, J. L., Konstan, J. A., Terveen, L. G., & Reidl, J. (2004). Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems, 22(1), 5–53. doi:10.1145/963770.963772. Hill, W., Stead, L., Rosenstein, M. & Furnas, G. (1995). Recommending and evaluating choices in a virtual community of use, in Proceedings of the SIGCHI conference on Human factors in computing systems, Denver, Colorado, United States, ACM Press/ Addison-Wesley Publishing Co., pp. 194–201. Konstan, J. A., Miller, B. N., Maltz, D., Herlocker, J. L., Gordon, L. R., & Riedl, J. (1997). GroupLens: Applying collaborative filtering to UseNet news. Communications of the ACM, 40(3), 77–87. http://doi.acm.org/10.1145/245108.245126. Lorenzi, F., Santos, D.S.dos & Bazzan, A.L.C. (2005). Case-based recommender systems inspired by social insects, in Proceedings of XXV Congresso da Sociedate Braseilera de Computacao, Sao Leopolda, pp. 752–760. Massa, P., & Avesani, P. (2004). Trust-aware collaborative filtering for recommender systems, in Proceedings of International Conference on Cooperative Information Systems, Agia Napa, Cyprus, pp. 492–508. Massa, P., & Avesani, P. (2007). Trust-aware recommender systems, Proceedings of RecSys, ACM, New York, NY, USA, pp. 17–24. Massa, P. & Bhattacharjee, B. (2004). Using trust in recommender systems: an experimental analysis. in Proceedings of 2nd International Conference on trust management, Oxford, England, pp. 221–235. Massa, P., & Avesani, P. (2009). Trust metrics in recommender systems. Computing with Social Trust. London: Springer, pp. 259–285, doi:10.1007/978-1-84800- 356-9. O’Donovan, J., & Smith, B. (2005). Trust in recommender systems, in Proceedings of the 10th International Conference on Intelligent User Interfaces (IUI’05), San Diego, California, USA, pp. 167–174. Resnick, P., Lakovou, N., Sushak, M., Bergstrom, P. & Riedl, J. (1994). GroupLens: An open architecture for collaborative filtering of Netnews, in Proceedings of the 1994 ACM conference on Computer supported cooperative work, Chapel Hill, North Carolina, United States, ACM Press, pp. 175–186. Resnick, P., & Varian, H. R. (1997). Recommender systems. Communications of the ACM, 40(3), 56–58. doi:10.1145/245108.245121. Rich, E. (1979). User modeling via stereotypes. Cognitive Science Journal, Elsevier, 3(4), 329–354. doi:10.1207/s15516709cog0304_3. Ries, S., Kangasharju, J., & Muhlhauser, M. (2006). A Classification of trust systems, LNCS 4277/2006. Berlin: Springer, pp. 894–903. Sarwar, B. M., Karypis, G., Konstan, J. A. & Reidl, J. (2000a). Analysis of recommendation algorithms for E-Commerce. in Proceedings of the 2nd ACM conference on electronic commerce (EC’00), Minneapolis, Minnesota, United States, pp. 158–167. doi:10.1145/352871.352887. Sarwar, B. M., Karypis, G., Konstan, J. A. & Reidl, J. (2000b). Application of dimensionality reduction in recommender system – A case study. ACM WebKDD 2000 Web mining for E-commerce workshop. Sarwar, B. M., Karypis, G., Konstan, J. A. & Riedl, J. (2001). Item-based collaborative filtering recommendation algorithms, in Proceedings of the 10th international conference on World Wide Web, Hong Kong, ACM Press, pp. 285–295. Schafer, J. B., Konstan, J. A., & Reidl, J. (1999). Recommender systems in ECommerce, in Proceedings of the first ACM conference on electronic commerce 99, Denver, United States, ACM Press, pp.158–166. Schafer, J. B., Frankowski, D., Herlocker, J., & Sen, S. (2007). Collaborative filtering recommender systems. The Adaptive Web LNCS 4321/2007. Berlin/Heidelberg: Springer, pp. 291-324ISBN: 978-3-540-72078-2. Shardanand, U., & Maes, P. (1995). Social information filtering: Algorithms for automating ‘Word of Mouth’, in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, Denver, Colorado, United States, pp. 210–217. Sharma, R., Singh, M., Makkar, R., Kaur, H., & Bedi, P. (2007). Ant Recommender: Recommender system inspired by ant colony, in Proceedings of International Conference on Advances in Computer Vision and Information Technology (ACVIT- 07), pp. 361–369. Sobecki, J. (2007). Web-based system user interface hybrid recommendation using ant colony metaphor. LNCS 4694/2008. Berlin/Heidelberg: Springer, pp.1033–1040, ISBN: 978-3-540-74828-1. Terveen, L., Hill, W., Amento, B., McDonald, D., & Creter, J. (1997). PHOAKS: A system for sharing recommendations. Communications of the ACM, 40(3), 59–62. http:// doi.acm.org/10.1145/245108.245122. Terveen, L., & Hill, W. (2001). Human–Computer collaboration in recommender systems. In Human computer interaction in the new millenium (pp. 487–509). New York: Addision-Wesley. Ujjin, S., & Bentley, P.J. (2003). Particle Swarm Optimization recommender system, in Proceedings of the 2003 IEEE Swarm Intelligence Symposium-SIS‘03, pp. 124– 131. doi:10.1109/SIS.2003.1202257. Wei, Z. (2007). A novel trust model based on recommendation for E-Commerce, in International Conference on Service Systems and Service Management 2007, Chengdu, pp. 1-4, ISBN: 1-4244-0885-7, doi:10.1109/ICSSSM.2007.4280307. Yuan, W., Guan, D., Lee, Y. K., Lee, S., & Hur, S. J. (2010). Improved trust-aware recommender system using small-worldness of trust networks. KnowledgeBased Systems, 23(3), 232–238. doi:10.1016/j.knosys.2009.12.004. Ziegler, C. N., & Nilcolas, G. J. (2007). Investigating correlations of trust and interest similarity- Do birds of a feather really flock together? Decision Support Systems, 43(2), 460–475. 1190 P. Bedi, R. Sharma / Expert Systems with Applications 39 (2012) 1183–1190
