Selective Markov models for predicting Web page accesses

ABSTRACT

The problem of predicting a user's behavior on a Web site has gained importance due to the rapid growth of the World Wide Web and the need to personalize and influence a user's browsing experience. Markov models and their variations have been found to be well suited for addressing this problem. Of the different variations of Markov models, it is generally found that higher-order Markov models display high predictive accuracies on Web sessions that they can predict. However, higher-order models are also extremely complex due to their large number of states, which increases their space and run-time requirements. In this article, we present different techniques for intelligently selecting parts of different order Markov models so that the resulting model has a reduced state complexity, while maintaining a high predictive accuracy.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Azer Bestavros, Using speculation to reduce server load and service time on the WWW, Proceedings of the fourth international conference on Information and knowledge management, p.403-410, November 29-December 02, 1995, Baltimore, Maryland, United States [doi>10.1145/221270.221653]
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 4: Ed H. Chi , Peter Pirolli , James Pitkow, The scent of a site: a system for analyzing and predicting information scent, usage, and usability of a Web site, Proceedings of the SIGCHI conference on Human factors in computing systems, p.161-168, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332423]
• 5: Ed H. Chi , James Pitkow , Jock Mackinlay , Peter Pirolli , Rich Gossweiler , Stuart K. Card, Visualizing the evolution of Web ecologies, Proceedings of the SIGCHI conference on Human factors in computing systems, p.400-407, April 18-23, 1998, Los Angeles, California, United States [doi>10.1145/274644.274699]
• 6: Cooley, R., Tan, P.-N., and Srivastava, J. 1999. Websift: The web site information filter system. In Proceedings of the Web Usage Analysis and User Profiling Workshop.
• 7: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceeding of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
• 8: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 9: Durbin, R., Eddy, S., Krogh, A., and G., M. 1998. Biological sequence analysis. Cambridge University Press.
• 10: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 11: Kohavi, R. and Brodley, C. 2000. Knowledge discovery and data mining cup SIGKDD 2000. http://www.ecn.purdue.edu/KDDCUP/.
• 12: Ron Kohavi , Carla E. Brodley , Brian Frasca , Llew Mason , Zijian Zheng, KDD-Cup 2000 organizers' report: peeling the onion, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.86-93, Dec. 2000 [doi>10.1145/380995.381033]
• 13: Linton, F. 2000. Owl: A recommender system for organization-wide learning. J. Inter. Forum Educat. Tech. Soc.
• 14: Venkata N. Padmanabhan , Jeffrey C. Mogul, Using predictive prefetching to improve World Wide Web latency, ACM SIGCOMM Computer Communication Review, v.26 n.3, p.22-36, July 1996 [doi>10.1145/235160.235164]
• 15: Papoulis, A. 1991. Probability, Random Variables, and Stochastic Processes. McGraw Hill.
• 16: Peter Pirolli , James Pitkow , Ramana Rao, Silk from a sow's ear: extracting usable structures from the Web, Proceedings of the SIGCHI conference on Human factors in computing systems: common ground, p.118-125, April 13-18, 1996, Vancouver, British Columbia, Canada [doi>10.1145/238386.238450]
• 17: Pitkow, J. and Pirolli, P. 1999. Mining longest repeating subsequence to predict world wide web surfing. In 2nd USENIX Symposium on Internet Technologies and Systems. Boulder, CO.
• 18: Dana Ron , Yoram Singer , Naftali Tishby, The power of amnesia: learning probabilistic automata with variable memory length, Machine Learning, v.25 n.2-3, p.117-149, Nov./Dec. 1996 [doi>10.1007/BF00114008]
• 19: Salzberg, S. L., Delcher, A. L., Kasif, S., and White, O. 1998. Microbial gene identification using interpolated markov models. Nucleic Acids Research.
• 20: Ramesh R. Sarukkai, Link prediction and path analysis using Markov chains, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.377-386, June 2000, Amsterdam, The Netherlands
• 21: Stuart Schechter , Murali Krishnan , Michael D. Smith, Using path profiles to predict HTTP requests, Proceedings of the seventh international conference on World Wide Web 7, p.457-467, April 1998, Brisbane, Australia
• 22: Siu, M. and Ostendorf, M. 2000. Variable n-grams and extensions for conversational speech language modeling. IEEE Trans. Speech Audio Process. 8, 1 (Jan), 63--75.
• 23: Jaideep Srivastava , Robert Cooley , Mukund Deshpande , Pang-Ning Tan, Web usage mining: discovery and applications of usage patterns from Web data, ACM SIGKDD Explorations Newsletter, v.1 n.2, January 2000 [doi>10.1145/846183.846188]
• 24: Theusinger, C. and Huber, K.-P. 2000. Analyzing the footsteps of your customers. In WebKDD 2000.
• 25: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms

Keywords:
Markov models, World wide web, predicting user behavior, web mining