Statistical analysis of \(k\)-nearest neighbor collaborative recommendation. (English) Zbl 1189.62190

Summary: Collaborative recommendation is an information-filtering technique that attempts to present information items that are likely of interest to an Internet user. Traditionally, collaborative systems deal with situations with two types of variables, users and items. In its most common form, the problem is framed as trying to estimate ratings for items that have not yet been consumed by a user. Despite the wide-ranging literature, little is known about the statistical properties of recommendation systems. In fact, no clear probabilistic model even exists which would allow us to precisely describe the mathematical forces driving collaborative filtering. To provide an initial contribution to this, we propose to set out a general sequential stochastic model for collaborative recommendation. We offer an in-depth analysis of the so-called cosine-type nearest neighbor collaborative method, which is one of the most widely used algorithms in collaborative filtering, and analyze its asymptotic performance as the number of users grows. We establish consistency of the procedure under mild assumptions on the model. Rates of convergence and examples are also provided.


62P99 Applications of statistics
62G08 Nonparametric regression and quantile regression
90B18 Communication networks in operations research
62G05 Nonparametric estimation
62G20 Asymptotic properties of nonparametric inference
62L99 Sequential statistical methods
65C60 Computational problems in statistics (MSC2010)
Full Text: DOI arXiv


[1] Abernethy, J., Bach, F., Evgeniou, T. and Vert, J.-P. (2009). A new approach to collaborative filtering: Operator estimation with spectral regularization. J. Mach. Learn. Res. 10 803-826. · Zbl 1235.68122
[2] Adomavicius, G., Sankaranarayanan, R., Sen, S. and Tuzhilin, A. (2005). Incorporating contextual information in recommender systems using a multidimensional approach. ACM Trans. Inform. Syst. 23 103-145.
[3] Adomavicius, G. and Tuzhilin, A. (2005). Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. Knowl. Data Eng. 17 734-749.
[4] Breese, J., Heckerman, D. and Kadie, C. (1998). Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of 14th Conference on Uncertainty in Artificial Intelligence 43-52. Morgan Kaufman, San Francisco, CA.
[5] Candès, E. and Plan, Y. (2009). Matrix completion with noise. Submitted. Available at http://www.acm.caltech.edu/ emmanuel/papers/NoisyCompletion.pdf.
[6] Candès, E. and Recht, B. (2009). Exact matrix completion via convex optimization. Found. Comput. Math. 9 717-772. · Zbl 1219.90124
[7] Choi, S., Kang, S. and Jeon, Y. (2006). Personalized recommendation system based on product specification values. Expert Systems with Applications 31 607-616.
[8] Devroye, L., Györfi, L. and Lugosi, G. (1996). A Probabilistic Theory of Pattern Recognition . Springer, New York. · Zbl 0853.68150
[9] Györfi, L., Kohler, M., Krzyżak, A. and Walk, H. (2002). A Distribution Free Theory of Nonparametric Regression . Springer, Berlin. · Zbl 1021.62024
[10] Heckerman, D., Chickering, D., Meek, C., Rounthwaite, R. and Kadie, C. (2000). Dependency networks for density estimation, collaborative filtering, and data visualization. J. Mach. Learn. Res. 1 49-75. · Zbl 1008.68132
[11] Hill, W., Stead, L., Rosenstein, M. and Furnas, G. (1995). Recommending and evaluating choices in a virtual community of use. In Proceedings of ACM CHI’95 Conference on Human Factors in Computing Systems 194-201. ACM Press, New York.
[12] Montaner, M., Lopez, B. and Rosa, J. (2003). A taxonomy of recommender agents on the Internet. Artificial Intelligence Review 19 285-330.
[13] Resnick, P., Iakovou, N., Sushak, M., Bergstrom, P. and Riedl, J. (1994). Grouplens: An open architecture for collaborative filtering of netnews. In Proceedings of the 1994 Computer Supported Cooperative Work Conference 175-186. ACM Press, New York.
[14] Salakhutdinov, R., Mnih, A. and Hinton, G. (2007). Restricted Boltzmann machines for collaborative filtering. In Proceedings of the 24th International Conference on Machine Learning 791-798. ACM Press, New York.
[15] Sarwar, B., Karypis, G., Konstan, J. and Riedl, J. (2001). Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th International WWW Conference 285-295. ACM Press, New York.
[16] Shardanand, U. and Maes, P. (1995). Social information filtering: Algorithms for automating “Word of mouth.” In Proceedings of the Conference on Human Factors in Computing Systems 210-217. ACM Press, New York.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.