اعتماد مبتنی بر سیستم توصیه با استفاده از کلونی مورچه ها برای محاسبات قابل اعتماد

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.

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 and Varian, 1997, Schafer et al., 1999 and Terveen and 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 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 et al., 1999, Dorigo et al., 1996 and Dorigo and 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.

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 defines “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.