Golden Path Analyzer: using divide-and-conquer to cluster Web clickstreams

ABSTRACT

This paper describes a novel algorithm and deployed system Golden Path Analyzer (GPA) that analyzes clickstreams of people trying to complete the same task on a website. It finds the shortest, successful paths taken by users - 'golden paths' - and uses these as seeds for clickstream clusters. Other users are assigned to a cluster if their clickstream is a supersequence of the golden path. The advantages of this approach are that the resulting clusters are easily comprehended, they are few in number, correspond to semantically different strategies used by the users, and jointly partition all the clickstreams. GPA's key contribution over prior work in process funnels is that by not excluding users that make diversions from the golden path, GPA is able to assign more users to fewer clusters. Another key contribution is to use actual full clickstreams as cluster seeds to which supersequences of other users are added. Golden paths correspond to complete clickstreams that are based on actual user page transitions. GPA is particularly useful for site designers to improve processes such as shopping, returns and registration. Its analyses identify which web pages cause many users to deviate from a golden path, which links distract users and the percentage of users taking each golden path. GPA has demonstrated value on more than twenty client projects in diverse industries.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: Banerjee, A. and Ghosh, J. Clickstream Clustering using Weighted Longest Common Subsequences, in Proc. of the Workshop on Web Mining, SIAM Conference on Data Mining (Chicago IL, April 2001), 33--40.
• 3: Barron A., Rissanen J. and Yu B. The minimum description length principle in coding and modeling. IEEE Trans. Information Theory, vol 44 (1998), 2743--2760.
• 4: Bettina Berendt, Detail and Context in Web Usage Mining: Coarsening and Visualizing Sequences, Revised Papers from the Third International Workshop on Mining Web Log Data Across All Customers Touch Points, p.1-14, August 26, 2001
• 5: Igor Cadez , David Heckerman , Christopher Meek , Padhraic Smyth , Steven White, Visualization of navigation patterns on a Web site using model-based clustering, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.280-284, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347151]
• 6: Ming-Syan Chen , Jong Soo Park , Philip S. Yu, Efficient Data Mining for Path Traversal Patterns, IEEE Transactions on Knowledge and Data Engineering, v.10 n.2, p.209-221, March 1998 [doi>10.1109/69.683753]
• 7: Robert Cooley , Pang-Ning Tan , Jaideep Srivastava, Discovery of Interesting Usage Patterns from Web Data, Revised Papers from the International Workshop on Web Usage Analysis and User Profiling, p.163-182, August 15, 1999
• 8: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 9: Masand B. and Spiliopoulou M. (eds.). Advances in Web Usage Mining and User Profiling: Proceedings of the WEBKDD'99 Workshop, LNAI 1836. Springer Verlag, July 2000.
• 10: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 11: C. Shahabi , A. M. Zarkesh , J. Adibi , V. Shah, Knowledge discovery from users Web-page navigation, Proceedings of the 7th International Workshop on Research Issues in Data Engineering (RIDE '97) High Performance Database Management for Large-Scale Applications, p.20, April 07-08, 1997
• 12: Spiliopoulou M., Faulstich L. C. and Winkler K. A Data Miner analyzing the Navigational Behaviour of Web Users. In Proc. of the Workshop on Machine Learning in User Modelling of the ACAI'99 Int. Conf., Creta, Greece, July '99.
• 13: Spiliopoulou, M., Pohle, C. and Faulstich, L. C. Improving the effectiveness of a web site with web usage mining. In {Masand and Spiliopoulou, 2000}, pages 139--159. 2000.
• 14: Spiliopoulou M. and Faulstich L. C. WUM: A Web Utilization Miner. In Workshop on the Web and Data Bases (WebDB98) (1998), 109--115.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms

Keywords:
Web-mining, clustering, divide-and-conquer