پینو: یک سامانه توصیه‌گر با استفاده از کاوش در سیاهه‌های وب

نویسندگان

دانشگاه یزد - گروه مهندسی کامپیوتر

چکیده

سامانه‌های توصیه‌گر در وبگاه‌ها شخصی‌سازی وب را به‌صورت هوشمند و برخط با ارائه پیشنهادهایی به کاربران انجام می‌دهند. این سامانه‌ها را می‌توان با مدل‌سازی شیوه‌های دسترسی کاربران با استفاده از کاوش در سیاهه‌های وب ایجاد نمود. به بیانی دیگر می‌توان الگوهای دسترسی کاربران را با روش‌های داده‌کاوی از سیاهه‌های وب استخراج کرد؛ سپس به کاربران بر پایه این الگوها پیشنهاد داد. سامانه‌های توصیه‌گر گوناگونی مبتنی بر کاوش در سیاهه‌های وب ایجاد شده‌اند اما هنوز بهبود کارایی و پیچیدگی آن‌ها موضوعی چالش‌برانگیز است. در این مقاله، سامانه توصیه‌گری بنام پینو مبتنی بر کاوش در سیاهه‌های وب به همراه رویکرد جدیدی برای استخراج الگوهای دسترسی در آن ارائه شده است. در این رویکرد ابتدا شیوه‌های دسترسی کاربران با گرافی جهت‌دار و وزن‌دار مدل می‌شوند. صفحات، رأس‌های این گراف و یال‌ها نشان‌دهنده ارتباط بین آن‌ها بر اساس تکرارهای با هم صفحات هستند. وزن یال‌ها بر اساس معکوس احتمال شرطی مشاهده صفحات با در نظر گرفتن ترتیب آن‌ها محاسبه می‌شود سپس صفحات با بخش‌بندی گراف شیوه‌های دسترسی کاربران بر پایه کوتاه‌ترین مسیرها خوشه‌بندی می‌شوند. پیشنهاددهی بر پایه این الگوها با پیچیدگی زمانی ثابت و سازگار با فراموش‌کاری پروتکل HTTP انجام می‌گیرد. سامانه پینو بر روی سیاهه‌های یک سرور مورد ارزیابی قرار گرفته است. اثربخشی پیشنهاددهی با معیارهای قابلیت پیشنهاددهی، پیشنهادهای درست، دقت و پوشش ارزیابی شده است. نتایج ارزیابی نشان‌دهنده توانایی سامانه پینو در بهبود کیفیت پیشنهادها است به‌گونه‌ای که میانگین همساز بین این معیارها در سامانه پینو به 57% رسیده که نسبت به سامانه‌های پیشین 12% بهبود یافته است.

کلیدواژه‌ها


عنوان مقاله [English]

Pino: A Recommender System using Web Usage Mining

نویسندگان [English]

  • M. R. Abbasnezhad
  • A. Jahangard Rafsanjani
  • M. R. Pajoohan
Department of Computer Engineering, Yazd University, Yazd, Iran
چکیده [English]

Recommender systems for websites do web personalization online and intelligently using recommendations to the users. These systems can be developed by web usage mining techniques which model user navigation patterns. In other words, data mining methods can be used to discover user access patterns from web logs. Then, recommendations to the users are provided based on these patterns. A variety of recommender systems based on web usage mining have been proposed, although improving the efficiency and complexity of them is still a challenging issue. In this paper, a recommender system called Pino has been proposed. A new approach for mining access patterns is proposed in Pino. In this approach, users' navigation patterns are modeled with a directed and weighted graph. Its vertices are webpages and the edges indicate their correlation based on co-occurrence frequencies between webpages. The weight of edges is calculated on the basis of the inverse conditional probability of viewing the webpages by considering their order. Then, webpages are clustered by partitioning this graph based on shortest paths. Recommendations will be generated based on discovered patterns with constant time complexity and with consistency to the statelessness property of HTTP protocol. Pino has been evaluated on web server logs. The effectiveness of recommendations has been evaluated by criteria applicability recommendation, correct recommendations, accuracy and coverage. Evaluation results indicate the ability of the system to improve quality of recommendations so that the harmony mean of these criteria in Pino system has reached 57% improved by 12% compared to previous systems.

کلیدواژه‌ها [English]

  • Recommender system
  • web usage mining
  • access pattern mining
  • graph shortest path
[1] B. Mobasher, R. Cooley, and J. Srivastava, “Automatic Personalization Based on Web Usage Mining,” Commun. ACM, vol. 43, no. 8, pp. 142–151, Aug. 2000.
[2] J. Srivastava, R. Cooley, M. Deshpande, and P.-N. Tan, “Web Usage Mining: Discovery and Applications of Usage Patterns from Web Data,” ACM SIGKDD Explorations Newsletter, vol. 1, no. 2, pp. 12–23, Jan. 2000.
[3] R. Cooley, B. Mobasher, and J. Srivastava, “Data Preparation for Mining World Wide Web Browsing Patterns,” Knowledge and Information Systems, vol. 1, no. 1, pp. 5–32, 1999.
[4] T. W. Yan, M. Jacobsen, H. Garcia-Molina, and U. Dayal, “From user access patterns to dynamic hypertext linking,” Computer Networks and ISDN Systems, vol. 28, no. 7, pp. 1007–1014, 1996.
[5] J. A. Hartigan, Clustering Algorithms, 99th ed. New York, NY, USA: John Wiley & Sons, Inc., 1975.
[6] R. C. Agarwal, C. C. Aggarwal, and V. V. V Prasad, “A Tree Projection Algorithm for Generation of Frequent Item Sets,” Journal of Parallel and Distributed Computing, vol. 61, no. 3, pp. 350–371, 2001.
[7] E.-H. Han, G. Karypis, V. Kumar, and B. Mobasher, “Clustering based on association rule hypergraphs,” in Proccedings of SIGMOD’97 Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD’97), 1997.
[8] B. Mobasher, R. Cooley, and J. Srivastava, “Creating adaptive Web sites through usage-based clustering of URLs,” in Proceedings of Workshop on Knowledge and Data Engineering Exchange, 1999, pp. 19–25.
[9] M. Perkowitz and O. Etzioni, “Towards adaptive Web sites: Conceptual framework and case study,” Artificial Intelligence, vol. 118, no. 1, pp. 245–275, 2000.
[10 C. Shahabi, F. Banaei-Kashani, Y.-S. Chen, and D. McLeod, “Yoda: An Accurate and Scalable Web-Based Recommendation System,” in Proceedings of the 9th International Conference on Cooperative Information Systems, Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 418–432.
[11] C. Shahabi, F. Banaei-Kashani, J. Faruque, and A. Faisal, “Feature Matrices: A Model for Efficient and Anonymous Web Usage Mining,” in Proceedings of the Second International Conference on Electronic Commerce and Web Technologies, Berlin, Heidelberg: Springer Berlin Heidelberg, 2001, pp. 280–294.
[12] M. Nakagawa and B. Mobasher, “A hybrid web personalization model based on site connectivity,” in Proceedings of WebKDD, 2003, pp. 59–70.
[13] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules in Large Databases,” in Proceedings of the 20th International Conference on Very Large Data Bases, 1994, pp. 487–499.
[14] D. E. Knuth, The Art of Computer Programming : Seminumerical Algorithms. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1997.
[15] M. Nakagawa and B. Mobasher, “Impact of Site Characteristics on Recommendation Models Based On Association Rules and Sequential Patterns,” in Proceedings of the IJCAI’03 Workshop on Intelligent Techniques for Web Personalization, 2003.
[16] B. Zhou, S. C. Hui, and K. Chang, “An intelligent recommender system using sequential Web access patterns,” in IEEE Conference on Cybernetics and Intelligent Systems, 2004, vol. 1, pp. 393–398.
[17] B. Zhou, S. C. Hui, and A. C. M. Fong, “CS-Mine: An Efficient WAP-Tree Mining for Web Access Patterns,” in Proceedings of the 6th Asia-Pacific Web Conference, Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 523–532.
[18] R. Baraglia and F. Silvestri, “Dynamic Personalization of Web Sites Without User Intervention,” Commun. ACM, vol. 50, no. 2, pp. 63–67, Feb. 2007.
[19] A. Silberschatz, P. B. Galvin, and G. Gagne, Operating System Concepts, 8th ed. Wiley Publishing, 2008.
[20] M. Jalali, N. Mustapha, M. N. Sulaiman, and A. Mamat, “WebPUM: A Web-based recommendation system to predict user future movements,” Expert Systems with Applications, vol. 37, no. 9, pp. 6201–6212, 2010.
[21] D. S. Hirschberg, “Algorithms for the Longest Common Subsequence Problem,” J. ACM, vol. 24, no. 4, pp. 664–675, Oct. 1977.
[22] R. Forsati, H. M. Doustdar, M. Shamsfard, A. Keikha, and M. R. Meybodi, “A fuzzy co-clustering approach for hybrid recommender systems,” International Journal of Hybrid Intelligent Systems, vol. 10, no. 2, pp. 71–81, 2013.
[23] سیامک عبداله‌زاده،  محمدعلی بالافر و لیلی محمدخانی، «استفاده از خوشه‌بندی و مدل مارکوف جهت پیش‌بینی درخواست آتی کاربر در وب»، مجله مهندسی برق دانشگاه تبریز، جلد 45، شماره 3، صفحات 96-89، 1394.
[24] جواد حمیدزاده و مریم صادق‌زاده، «فیلترکننده مشارکتی فازی ناهموار مبتنی بر کاربر در سیستم‌های پیشنهاددهنده»، مجله مهندسی برق دانشگاه تبریز، جلد 47، شماره 2، صفحات 500-491، 1396.
[25] R. Forsati, A. Moayedikia, and M. Shamsfard, “An effective Web page recommender using binary data clustering,” Information Retrieval Journal, vol. 18, no. 3, pp. 167–214, 2015.
[26] H. Liu and V. Kešelj, “Combined mining of Web server logs and web contents for classifying user navigation patterns and predicting users’ future requests,” Data & Knowledge Engineering, vol. 61, no. 2, pp. 304–330, 2007.
[27] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson, Introduction to Algorithms, 2nd ed. McGraw-Hill Higher Education, 2001.