User:Lethe90/Item-Based Top- N Recommendation

Algorithm description

Recommender systems apply statistical and knowledge discovery techniques to the problem of making product recommendations during a live customer interaction and they are achieving widespread success in E-Commerce nowadays. To recommend products to users according to their interests, research on recommended algorithm was carried on widely.

Particular classes of model-based top-N recommendation algorithms that build the recommendation model by analyzing the similarities between the various items and then use these similar items to identify the set of items to be recommended. These algorithms, referred to the topic here as item-based top- N recommendation algorithms, have been used in various forms since the early days of CF-based recommender systems [Shardanand and Maes 1995; Kitts et al. 2000] and were shown to be computationally scalable (both in terms of model construction and model application) but tended to produce lowerquality recommendations when compared to user-based schemes.

Algorithm

Define symbols n and m to denote the number of distinct users and the number of distinct items in a particular dataset, respectively. And here we will use the symbol N to denote the number of recommendations that needs to be computed for a particular user.

Represent each dataset by an n × m binary matrix R that will be referred to as the user-item matrix, such that R(i,j) is one if the i-th customer has purchased the j-th item, and zero otherwise. The main idea of the algorithm is as below:

Given a user–item matrix R and a set of items U that have been purchased by a user, identify an ordered set of items X such that | X |≤ N and X ∩ U =∅.

Pseudocode

The Algorithm consists two core step:

<1>BuildModel(R,k)

Here Cosine-Based Similarity is one of selections able to compute similarity.

<2>ApplyModel(M,U,N)

Finally, in the third step, the algorithm sets to zero all the entries of x that have a value smaller than the N largest values of x.

Complexity

The computational complexity of the item-based top-N recommendation algorithm depends on the amount of time required to build the model M (i.e., for each item identify the other k most similar items), and the amount required to compute the recommendation using this model. During the model building phase we need to compute the similarity between each item j and the other items in R and then select the k most similar items. The upper bound on the complexity of this step is O (m^2n) as we need to compute m (m − 1) similarities, each potentially requiring n operations. However, the actual complexity is significantly smaller because the resulting item to item similarity matrix is extremely sparse. In our datasets, the item to item similarity matrix was generally more than 99% sparse. The reason for these sparsity levels is that each customer purchases a relatively small number of items and the items they purchase tend to be clustered. Consequently, by using sparse data structures to store R and only computing the similarities between pairs of items that are purchased by at least one customer we can substantially reduce the computational complexity.

Finally, the time required to compute the top-N recommendations for an active user that has purchased q items is given by O (kq) because we need to access the k most similar items for each one of the items that the user has already purchased and identify the overall N most similar items.

Performance Measures

Evaluation is important in assessing the effectiveness of recommendation algorithms. The commonly used metrics are the Mean Squared Error and Root Mean Squared Error. The latter was used in the Netflix Prize. The information retrieval metrics such as Precision, Recall, or DCG are useful to assess the quality of a recommendation method. Recently, the diversity, novelty and coverage are also considered as an important aspects in evaluation.Lathia, N., Hailes, S., Capra, L., Amatriain, X.: Temporal diversity in recommender systems. In: Proceeding of the 33rd International ACMSIGIR Conference on Research and Development in Information Retrieval, SIGIR 2010, pp. 210–217. ACM, New York

Related algorithms

There are several others ways to make recommendation. According to the recommendation algorithm, recommendation system can be divided into the different categories: collaborative filtering system; content based recommendation system; hybrid recommendation system, and other structure recommendation system.

References

Item-based top-N recommendation algorithms

By George Karypis ACM Transactions on Information Systems (TOIS)

Item-based collaborative filtering recommendation algorithms

by Sarwar, Badrul; Karypis, George; Konstan, Joseph; Riedl, John Proceedings of the 10th international conference on world wide web, 04/2001

analysis of recommendation algorithms for e-commerce.

By B Sarwar, G Karypis, J Konstan, J Riedl. Proceedings of the 2nd ACM conference on Electronic commerce, 2000:158-167

External links

Recommender Systems Wiki
Robert M. Bell, Jim Bennett, Yehuda Koren, and Chris Volinsky (May 2009). "The Million Dollar Programming Prize". IEEE Spectrum.{{cite web}}: CS1 maint: multiple names: authors list (link)
Hangartner, Rick, "What is the Recommender Industry?", MSearchGroove, December 17, 2007.
Recommender Systems Website
seethisnext – Film Similarity Search
ACM Conference on Recommender Systems
Coursebooks on Recommender Systems