隨著網路的發達，日常生活中人們在線上網站進行購物己成為非常普遍的行為；一個大型的線上購物網站往往會提供各式各樣的商品供使用者選購，因而產生了大量的交易記錄及使用者對商品的評價資料，推薦系統藉由分析這些過去的交易記錄、評價資料等可產生個人化的推薦項目。在眾多的推薦方法中，矩陣分解法 (例如：奇異值分解法) 因有較佳的準確度，所以常被應用來產生推薦預測；然而，傳統的矩陣分解法面臨一個嚴重的問題，即重新對整個評分矩陣進行分解動作的計算複雜度非常高。在線上購物環境中，為了讓推薦系統能適用於擁有如此大量及快速變動的使用者與啇品資訊，我們設計了一個漸進式奇異值分解法之機制，當系統有新的評價資料時能立即為使用者產生最即時的評分預測及個人化的推薦項目；透過此漸進式機制，系統能利用已知的分解結果直接地更新評分矩陣，不需要再重新建立整個評分矩陣並進行分解動作。除了相關的理論分析外，實驗結果也顯示我們設計之漸進式機制在實際應用環境中對於系統整體效能有顯著的改善。

With the Internet emerging as a necessity today, online shopping is becoming a common activity for more and more people in their daily lives. In an online store, numerous types of items are provided for users that result in large amounts of transaction and rating data. Recommendation systems analyze these past transaction patterns or rating data to provide personalized recommendations for users. Among several alternatives, matrix factorization algorithms such as singular value decomposition (SVD) can potentially be used for generating predictions in a more precise way. However, conventional SVD-based approaches suffer one serious limitation in that recomputing the SVD of a rating matrix is computationally very expensive. To adapt to the huge amount of both user and item information in an online e-commerce environment, and rapid changes in that information, we aim to develop an incremental SVD scheme for generating up-to-date user-item rating predictions when streams of new rating data come in. With our incremental scheme, the user-item rating matrix is directly updated by making use of the existing result of SVD. In addition to theoretical analyses of relevant issues, empirical studies show that our approach is efficient and feasible for use in practical applications.

[1] D. Agarwal and B.-C. Chen, “Regression-based Latent Factor Models,” Proceedings of the 15th International ACM Conference on Knowledge Discovery and Data Mining, pages 19-28, June 2009.

[2] G. Adomavicius and A. Tuzhilin, “Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-art and Possible Extensions,” IEEE Transactions on Knowledge and Data Engineering, 17(6):734-749, January 2005.

[3] A. Ansari, S. Essegaier, and R. Kohli, “Internet Recommendation Systems,” Journal of Marketing Research, 37(3):363-375, August 2000.

[4] J. Bennet and S. Lanning, “The Netflix Prize,” KDD Cup and Workshop, 2007.

[5] C. Basu, H. Hirsh, and W. Cohen, “Recommendation as Classification: Using Social and Content-based Information in Recommendation,” Proceedings of the 15th National Conference on Artificial Intelligence, pages 714-720, July 1998.

[6] M. E. Brand, “Incremental Singular Value Decomposition of Uncertain Data with Missing Values,” Proceedings of the 7th European Conference on Computer Vision, pages 707-720, May 2002.

[7] M. W. Berry, S. T. Dumais, and G. W. O’Brien, “Using Linear Algebra for Intelligent Information Retrieval,” SIAM Review, 37(4):573-595, December 1995.

[8] M. Balabanovic and Y. Shoham “Fab: Content-based, Collaborative Recommendation,” Communications of the ACM, 40(3):66-72, March 1997.

[9] R. M. Bell and Y. Koren, “Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights,” IEEE Conference on Data Mining, pages43-52, October 2007.

[10] L. M. D. Campos, J. M. Fernandez-Luna, J. F. Huete, and M. A. Rueda-Morales “Combining Content-based and Collaborative Recommendations: A Hybrid Approach Based on Bayesian Networks,” International Journal of Approximate Reasoning, 51(7):785-799, September 2010.

[11] R. G. Crespo, O. S. Martinez, J. M. C. Lovelle, B. C. P. Garcia-Bustelo, J. E. L. Gayo, and P. O. D. Pablos, “Recommendation System based on User Interaction Data Applied to Intelligent Electronic Books,” Computers in Human Behavior (2010), doi: 10.1016/j.chb.2010.09.012.

[12] S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman, “Indexing by Latent Semantic Analysis,” Journal of the American Society for Information Science, 41(6):391-407, September 1990.

[13] N. Good, J. B. Schafer, J. A. Konstan, A. Borchers, B. Sarwar, J. Herlocker, and J. Riedl, “Combining Collaborative Filtering with Personal Agents for Better Recommendations,” Proceedings of the 16th National Conference on Artificial Intelligence, pages 439-446, July 1999.

[14] G. Golub and C. Van Loan, “Matrix Computations,” Johns Hopkins University Press, 1996.

[15] J. L. Herlocker, J. A. Konstan, A. Borchers, and J. Riedl, “An Algorithmic Framework for Performing Collaborative Filtering,” Proceedings of the 22nd Annual International ACM Conference on Research and Development in Information Retrieval, pages 230-237, August 1999.

[16] J. L. Herlocker, J. A. Konstan, and J. Riedl, “Explaining Collaborative Filtering Recommendations,” Proceedings of the ACM Conference on Computer Supported Cooperative Work, pages 241-250, December 2000.

[17] M. Khoshneshin and W. N. Street, “Collaborative Filtering via Euclidean Embedding,” Proceedings of the 4th ACM Conference on Recommender Systems, pages 87-94, September 2010.

[18] Y. Koren, R. Bell, and C. Volinsky, “Matrix Factorization Techniques for Recommender Systems,” IEEE Computer, 42(8):30-37, August 2009.

[19] Y. Koren, “Factor in the Neighbors: Scalable and Accurate Collaborative Filtering,” ACM Transactions on Knowledge Discovery from Data, 4(1):1-24, January 2010.

[20] Y. Koren, “Collaborative Filtering with Temporal Dynamics,” Communications of the ACM, 53(4):89-97, April 2010.

[21] Y. Koren, “Factorization Meets the Neighborhood: A Multifaceted Collaborative Filtering Model,” Proceedings of the 14th International ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 426-434, August 2008.

[22] J.-W. Lee, H.-J. Kim, and S.-G. Lee, “Conceptual Collaborative Filtering Recommendation: A Probabilistic Learning Approach,” Neurocomputing, 73(13-15):2793-2796, August 2010.

[23] Z. Liu, W. Qu, H. Li, and C. Xie, “A Hybrid Collaborative Filtering Recommendation Mechanism for P2P Networks,” Future Generation Computer Systems, 26(8):1409-1417, October 2010.

[24] F. Liu and H. J. Lee, “Use of Social Network Information to Enhance Collaborative Filtering Performance,” Expert Systems with Applications, 37(7):4772-4778, July 2010.

[25] R. J. Mooney and L. Roy, “Content-based Book Recommending Using Learning for Text Categorization,” Proceedings of the 5th ACM Conference on Digital Libraries, pages 195-204, June 2000.

[26] R. V. Meteren and M. V. Someren, “Using Content-based Filtering for Recommendation,” Proceedings of the MLnetECML Workshop, pages 312-321, 2000.

[27] MovieLens Data Sets, http://www.grouplens.org/node/73.

[28] N. T. Nguyen, M. Rakowski, M. Rusin, J. Sobecki, and L. C. Jain, “Hybrid Filtering Methods Applied in Web-based Movie Recommendation System,” Lecture Notes in Computer Science, 4692:206-213, 2007.

[29] M. J. Pazzani and D. Billsus, “Content-based Recommendation Systems,” Lecture Notes in Computer Science, 4321:325-341, 2007.

[30] P. Stange, “On the Efficient Update of the Singular Value Decomposition,” International Association of Applied Mathematics and Mechanics, 8(1):10827-10828, December 2008.

[31] B. Sarwar, G. Karypis, J. Konstan, and J. Riedl, “Incremental Singular Value Decomposition Algorithms for Highly Scalable Recommender Systems,” Proceedings of the 5th International Conference on Computer and Information Technology, pages 27-28, December 2002.

[32] B. Sarwar, G. Karypis, J. Konstan, and J. Riedl, “Application of Dimensionality Reduction in Recommender System -- A Case Study,” ACM WebKDD Workshop, August 2000.

[33] J. B. Schafer, J. Konstan, and J. Riedl, “Recommender Systems in E-Commerce,” Proceedings of the 1st ACM conference on Electronic Commerce, pages 158-166, November 1999.

[34] G. Salton, “Automatic Text Processing,” Addison-Wesley, 1988.

[35] C. Shahabi, F. B. Kashani, Y.-S. Chen and D. McLeod, “Yoda: An Accurate and Scalable Web-based Recommendation System,” Proceedings of the 6th International Conference on Cooperative Information Systems, pages 418-432, September 2001.

[36] A. Toscher, M. Jahrer, and R. Legenstein, “Improved Neighborhood-based Algorithms for Large-scale Recommendation Systems,” SIGKDD Workshop on Large-scale Recommendation Systems and the Netflix Prize Competition, 2008.

[37] K. Yoshii, M. Goto, K. Komatani, T. Ogata, and H. G. Okuno, “Hybrid Collaborative and Content-based Music Recommendation Using Probabilistic Model with Latent User Preferences,” Proceedings of the 7th International Conference on Music Information Retrieval, pages 296-301, October 2006.

[38] H. Zha and H. D. Simon, “On Updating Problems in Latent Semantic Indexing,” SIAM Journal on Scientific Computing, 21(2):782-791, September 1999.