Evaluating the markov assumption for web usage mining

ABSTRACT

Web usage mining concerns the discovery of common browsing patterns, i.e., pages requested in sequence, from web logs. To cope with the enormous amounts of data, several aggregated structures based on statistical models of web surfing have appeared, e.g., the Hypertext Probabilistic Gramma(HPG) model [2]. These techniques typically rely on the Markov assumption with history depth n, i.e., it is assumed that the next requested page is only dependent on the last n pages visited. This is not always valid, i.e. false browsing patterns may be discovered. However, to our knowledge there has been no systematic study of the validity of the Markov assumption wrt. web usage mining and the resulting quality of the mined browsing patterns.In this paper we systematically investigate the quality of browsing patterns mined from structures based on the Markov assumption. Formal measures of quality, based on the closeness of the mined patterns to the true traversal patterns, are defined and an extensive experimental evaluation is performed, based on two substantial real-world data sets. The results indicate that a large number of rules must be considered to achieve high quality, that long rules are generally more distorted than shorter rules and that the model yield knowledge of a higher quality when applied to more random usage patterns. Thus we conclude that Markov-based structures for web usage mining are best suited for tasks demanding less accuracy such as pre-fetching, personalization, and targeted ads.

REFERENCES

• 1: Jesper Andersen , Anders Giversen , Allan H. Jensen , Rune S. Larsen , Torben Bach Pedersen , Janne Skyt, Analyzing clickstreams using subsessions, Proceedings of the 3rd ACM international workshop on Data warehousing and OLAP, p.25-32, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/355068.355312]
• 2: José Borges , Mark Levene, Data Mining of User Navigation Patterns, Revised Papers from the International Workshop on Web Usage Analysis and User Profiling, p.92-111, August 15, 1999
• 3: José Borges , Mark Levene, An Heuristic to Capture Longer User Web Navigation Patterns, Proceedings of the First International Conference on Electronic Commerce and Web Technologies, p.155-164, September 04-06, 2000
• 4: José Borges , Mark Levene, A fine grained heuristic to capture web navigation patterns, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.40-50, June, 2000 [doi>10.1145/360402.360416]
• 5: Eugene Charniak, Statistical Language Learning, MIT Press, Cambridge, MA, 1996
• 6: Xin Chen , Xiaodong Zhang, A Popularity-Based Prediction Model for Web Prefetching, Computer, v.36 n.3, p.63-70, March 2003 [doi>10.1109/MC.2003.1185219 ]
• 7: Web Mining: Information and Pattern Discovery on the World Wide Web, Proceedings of the 9th International Conference on Tools with Artificial Intelligence, p.558, November 03-08, 1997
• 8: R. Cooley, P. Tan, and J. Srivastava. Websift: the web site information filter system. In Proc. of WebKDD, pp. 163--182, 1999.
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 10: Søren E. Jespersen , Jesper Thorhauge , Torben Bach Pedersen, A Hybrid Approach to Web Usage Mining, Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery, p.73-82, September 04-06, 2002
• 11: R. Kimball and R. Merz. The Data Webhouse Toolkit. Wiley, 2000.
• 12: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Hua Zhu, Mining Access Patterns Efficiently from Web Logs, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.396-407, April 18-20, 2000
• 13: S. Ross. A First Course in Probability. Prentice Hall, 1998.
• 14: M. Spiliopoulou and L. C. Faulstich. WUM: a Web Utilization Miner. In Proc. of WebDB, pp. 184--203, 1998.
• 15: 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]

INDEX TERMS

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

General Terms:
Experimentation, Measurement

Keywords:
information quality, markov models, web usage mining