Automated construction of web accessibility models from transaction click-streams

ABSTRACT

Screen readers, the dominant assistive technology used by visually impaired people to access the Web, function by speaking out the content of the screen serially. Using screen readers for conducting online transactions can cause considerable information overload, because transactions, such as shopping and paying bills, typically involve a number of steps spanning several web pages. One can combat this overload by using a transaction model for web accessibility that presents only fragments of web pages that are needed for doing transactions. We can realize such a model by coupling a process automaton, encoding states of a transaction, with concept classifiers that identify page fragments "relevant" to a particular state of the transaction. In this paper we present a fully automated process that synergistically combines several techniques for transforming unlabeled click-stream data generated by transactions into a transactionmodel. These techniques include web content analysis to partition a web page into segments consisting of semantically related content, contextual analysis of data surrounding clickable objects in a page, and machine learning methods, such as clustering of page segments based on contextual analysis, statistical classification, and automata learning. The use of unlabeled click streams in building transaction models has important benefits: (i) visually impaired users do not have to depend on sighted users for creating manually labeled training data to construct the models; (ii) it is possible to mine personalized models from unlabeled transaction click-streams associated with sites that visually impaired users visit regularly; (iii) since unlabeled data is relatively easy to obtain, it is feasible to scale up the construction of domain-specific transaction models (e.g., separate models for shopping, airline reservations, bill payments, etc.); (iv) adjusting the performance of deployed models over timtime with new training data is also doable. We provide preliminary experimental evidence of the practical effectiveness of both domain-specific, as well as personalized accessibility transaction models built using our approach. Finally, this approach is applicable for building transaction models for mobile devices with limited-size displays, as well as for creating wrappers for information extraction from web sites.

REFERENCES

• 1: JAWS Screen Reader. http://www.freedomscientific.com.
• 2: James Allan, Topic Detection and Tracking: Event-Based Information Organization, Kluwer Academic Publishers, Norwell, MA, 2002
• 3: J. F. Allen, N. Chambers, G. Ferguson, L. Galescu, H. Jung,M. D. Swift, and W. Taysom. Plow: A collaborative task learning agent. In Proc. of AAAI, 2007.
• 4: Einat Amitay , Cécile Paris, Automatically summarising Web sites: is there a way around it?, Proceedings of the ninth international conference on Information and knowledge management, p.173-179, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354816]
• 5: Chieko Asakawa , Takashi Itoh, User interface of a Home Page Reader, Proceedings of the third international ACM conference on Assistive technologies, p.149-156, April 15-17, 1998, Marina del Rey, California, United States [doi>10.1145/274497.274526]
• 6: A. Banerjee and J. Ghosh. Click-stream clustering using weighted longest common subsequences. In Proc. of the Web Mining Workshop at the 1st SIAM Conference on Data Mining, pages 33--40, 2001.
• 7: Huanhuan Cao , Daxin Jiang , Jian Pei , Qi He , Zhen Liao , Enhong Chen , Hang Li, Context-aware query suggestion by mining click-through and session data, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401995]
• 8: Valter Crescenzi , Giansalvatore Mecca, Automatic information extraction from large websites, Journal of the ACM (JACM), v.51 n.5, p.731-779, September 2004 [doi>10.1145/1017460.1017462]
• 9: Allen Cypher , Daniel C. Halbert , David Kurlander , Henry Lieberman , David Maulsby , Brad A. Myers , Alan Turransky, Watch what I do: programming by demonstration, MIT Press, Cambridge, MA, 1993
• 10: Xin Dong , Alon Halevy , Jayant Madhavan , Ema Nemes , Jun Zhang, Similarity search for web services, Proceedings of the Thirtieth international conference on Very large data bases, p.372-383, August 31-September 03, 2004, Toronto, Canada
• 11: D. Geoffray. The internet through the eyes of windows-eyes. In Proc. of Tech. and Persons with Disabilities Conf., 1999.
• 12: G. Greco, A. Guzzo, L. Pontieri, and D. Sacca. Mining expressive process models by clustering workflow traces. 2004.
• 13: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 14: J.-Y. Delort , B. Bouchon-Meunier , M. Rifqi, Enhanced web document summarization using hyperlinks, Proceedings of the fourteenth ACM conference on Hypertext and hypermedia, August 26-30, 2003, Nottingham, UK [doi>10.1145/900051.900097]
• 15: P. Jaccard. Bulletin del la soci?t? vaudoisedes sciences naturelles 37. pages 241--272, 1901.
• 16: Tessa Ann Lau , Daniel S. Weld , Pedro Domingos, Programming by demonstration: a machine learning approach, University of Washington, 2001
• 17: Juhnyoung Lee , Mark Podlaseck , Edith Schonberg , Robert Hoch, Visualization and Analysis of Clickstream Data of Online Stores for Understanding Web Merchandising, Data Mining and Knowledge Discovery, v.5 n.1-2, p.59-84, January-April 2001 [doi>10.1023/A:1009843912662]
• 18: K. Lerman, A. Plangprasopchok, and C. A. Knoblock. Automatically labeling the inputs and outputs of web services. In Proc. of AAAI, 2006.
• 19: Gilly Leshed , Eben M. Haber , Tara Matthews , Tessa Lau, CoScripter: automating & sharing how-to knowledge in the enterprise, Proceeding of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, April 05-10, 2008, Florence, Italy [doi>10.1145/1357054.1357323]
• 20: Jalal U. Mahmud , Yevgen Borodin , I. V. Ramakrishnan, Csurf: a context-driven non-visual web-browser, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242578]
• 21: Jalal Mahmud , Yevgen Borodin , I. V. Ramakrishnan, Assistive browser for conducting web transactions, Proceedings of the 13th international conference on Intelligent user interfaces, January 13-16, 2008, Gran Canaria, Spain [doi>10.1145/1378773.1378831]
• 22: Saikat Mukherjee , Guizhen Yang , Wenfang Tan , I. V. Ramakrishnan, Automatic Discovery of Semantic Structures in HTML Documents, Proceedings of the Seventh International Conference on Document Analysis and Recognition, p.245, August 03-06, 2003
• 23: K. Murphy. Passively learning finite automata, 1996.
• 24: O. Nasraoui, C. Cardona, and C. Rojas. Mining of evolving web click-streams with explicit retrieval similarity measures. In Proc. of "International Web Dynamics Workshop", International World Wide Web Conference, 2004.
• 25: Şule Gündüz , M. Tamer Özsu, A Web page prediction model based on click-stream tree representation of user behavior, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956815]
• 26: M. F. Porter, An algorithm for suffix stripping, Readings in information retrieval, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1997
• 27: R. Silva, J. Zhang, and J. Shanahan. Probabilistic workflow mining. 2005.
• 28: Ricardo Silva , Jiji Zhang , James G. Shanahan, Probabilistic workflow mining, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081903]
• 29: Alexander Strehl , Joydeep Ghosh, Relationship-based clustering and cluster ensembles for high-dimensional data mining, The University of Texas at Austin, 2002
• 30: Zan Sun , Jalal Mahmud , Saikat Mukherjee , I. V. Ramakrishnan, Model-directed web transactions under constrained modalities, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135843]
• 31: Rattapoom Tuchinda , Pedro Szekely , Craig A. Knoblock, Building data integration queries by demonstration, Proceedings of the 12th international conference on Intelligent user interfaces, January 28-31, 2007, Honolulu, Hawaii, USA [doi>10.1145/1216295.1216328]
• 32: W. M. P. van der Aalst , A. J. M. M. Weijters, Process mining: a research agenda, Computers in Industry, v.53 n.3, p.231-244, April 2004 [doi>10.1016/j.compind.2003.10.001]
• 33: V. Vapnik. Principles of risk minimization for learning theory. In D. S. Lippman, J. E. Moody, and D. S. Touretzky, editors, Advances in Neural Information Processing Systems 3, 1992.
• 34: Shipeng Yu , Deng Cai , Ji-Rong Wen , Wei-Ying Ma, Improving pseudo-relevance feedback in web information retrieval using web page segmentation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775155]
• 35: M. Zajicek, C. Powell, and C. Reeves. Web search and orientation with brookestalk. In Proc. of Tech. and Persons with Disabilities Conf., 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: User interface management systems (UIMS)

General Terms:
Algorithms, Design, Experimentation, Human Factors

Keywords:
context, machine learning, process models, web transaction