Data mining for hypertext: a tutorial survey

ABSTRACT

With over 800 million pages covering most areas of human endeavor, the World-wide Web is a fertile ground for data mining research to make a difference to the effectiveness of information search. Today, Web surfers access the Web through two dominant interfaces: clicking on hyperlinks and searching via keyword queries. This process is often tentative and unsatisfactory. Better support is needed for expressing one's information need and dealing with a search result in more structured ways than available now. Data mining and machine learning have significant roles to play towards this end.In this paper we will survey recent advances in learning and mining problems related to hypertext in general and the Web in particular. We will review the continuum of supervised to semi-supervised to unsupervised learning problems, highlight the specific challenges which distinguish data mining in the hypertext domain from data mining in the context of data warehouses, and summarize the key areas of recent and ongoing research.

REFERENCES

• 1: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 2: James Allan, Automatic hypertext link typing, Proceedings of the the seventh ACM conference on Hypertext, p.42-52, March 16-20, 1996, Bethesda, Maryland, United States [doi>10.1145/234828.234833]
• 3: J. Allen. Natural Language Understanding. Benjamin/Cummings, 1987.
• 4: D. J. Arnold, L. Balkan, R. L. Humphreys, S. Meijer, and L. Sadler. Machine translation: An introductory guide, 1995. Online at http://clwww.essex.ac.uk/~doug/book/book.html.
• 5: Babelfish Language Translation Service. http://www.altavista.com, 1998.
• 6: Krishna Bharat , Andrei Broder, A technique for measuring the relative size and overlap of public Web search engines, Proceedings of the seventh international conference on World Wide Web 7, p.379-388, April 1998, Brisbane, Australia
• 7: Krishna Bharat , Andrei Broder , Monika Henzinger , Puneet Kumar , Suresh Venkatasubramanian, The connectivity server: fast access to linkage information on the Web, Proceedings of the seventh international conference on World Wide Web 7, p.469-477, April 1998, Brisbane, Australia
• 8: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 9: William James Blustein , Sylvia Osborn, Hypertext versions of journal articles: computer-aided linking and realistic human-based evaluation, 1999
• 10: 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
• 11: Claire Cardie , David Pierce, The role of lexicalization and pruning for base noun phrase grammars, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.423-430, July 18-22, 1999, Orlando, Florida, United States
• 12: N. Catenazzi and F. Gibb. The publishing process: the hyperbook approach. Journal of Information Science, 21(3):161--172, 1995.
• 13: Soumen Chakrabarti , Byron Dom , Rakesh Agrawal , Prabhakar Raghavan, Using Taxonomy, Discriminants, and Signatures for Navigating in Text Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.446-455, August 25-29, 1997
• 14: Soumen Chakrabarti , Byron Dom , Rakesh Agrawal , Prabhakar Raghavan, Scalable feature selection, classification and signature generation for organizing large text databases into hierarchical topic taxonomies, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.3, p.163-178, August 1998 [doi>10.1007/s007780050061]
• 15: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
• 16: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 17: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636]
• 18: Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Proceeding of the eighth international conference on World Wide Web, p.1623-1640, May 1999, Toronto, Canada
• 19: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 20: Douglass R. Cutting , David R. Karger , Jan O. Pedersen, Constant interaction-time scatter/gather browsing of very large document collections, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.126-134, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160706]
• 21: Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133214]
• 22: 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
• 23: S. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the Society for Information Science, 41(6):391--407, 1990. Online at http://superbook.telcordia.com/~remde/isi/papers/JASIS90.ps.
• 24: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, B(39):1--38, 1977.
• 25: Steven J. DeRose, What Do Those Weird XML Types Want, Anyway?, Proceedings of the 25th International Conference on Very Large Data Bases, p.721-724, September 07-10, 1999
• 26: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 27: R. Dude and P. Hart. Pattern Classification and Scene Analysis. Wiley, New York, 1973.
• 28: S. Fong and R. Berwick. Parsing with Principles and Parameters. MIT Press, 1992.
• 29: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 30: P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
• 31: Jerome H. Friedman, On Bias, Variance, 0/1—Loss, and the Curse-of-Dimensionality, Data Mining and Knowledge Discovery, v.1 n.1, p.55-77, 1997 [doi>10.1023/A:1009778005914]
• 32: Gerard Gazdar , Chris Mellish, Natural Language Processing in LISP: An Introduction to Computational Linguistics, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 33: R. Goldman, J. McHugh, and J. Widom. From semistructured data to XML: Migrating the Lore data model and query language. In Proceedings of the 2nd International Workshop on the Web and Databases (WebDB '99), pages 25--30, Philadelphia, June 1999. Online at http://www-db.stanford.edu/pub/papers/xml.ps.
• 34: G. H. Golub and C. F. van Loan. Matrix Computations. Johns Hopkins University Press, London, 1989.
• 35: S. G. Green. Building newspaper links in newspaper articles using semantic similarity. In Natural Language and Data Bases Conference, Vancouver, NLDB'97, 1997.
• 36: L. Haegeman. Introduction to Government and Binding Theory. Basil Blackwell Ltd., Oxford, 1991.
• 37: Marti A. Hearst , Chandu Karadi, Cat-a-Cone: an interactive interface for specifying searches and viewing retrieval results using a large category hierarchy, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.246-255, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 38: David Heckerman, Bayesian Networks for Data Mining, Data Mining and Knowledge Discovery, v.1 n.1, p.79-119, 1997 [doi>10.1023/A:1009730122752]
• 39: W. J. Hutchins and H. L. Somers. An Introduction to Machine Translation. Academic Press, 1992.
• 40: U. N. U. Institute of Advanced Studies. The universal networking language: Specification document. In Internal Technical Document, 1999.
• 41: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 42: Thorsten Joachims, Making large-scale support vector machine learning practical, Advances in kernel methods: support vector learning, MIT Press, Cambridge, MA, 1999
• 43: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 44: D. Koller and M. Sahami. Toward optimal feature selection. In L. Saitta, editor, International Conference on Machine Learning, volume 13. Morgan-Kaufmann, 1996.
• 45: Daphne Koller , Mehran Sahami, Hierarchically Classifying Documents Using Very Few Words, Proceedings of the Fourteenth International Conference on Machine Learning, p.170-178, July 08-12, 1997
• 46: K. S. Kumarvel. Automatic hypertext creation. M. Tech Thesis, Computer Science and Engineering Department, IIT Bombay, 1997.
• 47: P.-S. Laplace. Philosophical Essays on Probabilities. Springer-Verlag, New York, 1995. Translated by A. I. Dale from the 5th French edition of 1825.
• 48: R. Larson. Bibliometrics of the world wide web: An exploratory analysis of the intellectual structure of cyberspace. In Annual Meeting of the American Society for Information Science, 1996. Online at http://sherlock.berkeley.edu/asis96/asis96.html.
• 49: S. Lawrence and C. Lee Giles. Accessibility of information on the web. Nature, 400:107--109, July 1999.
• 50: Mark Craven , Seán Slattery , Kamal Nigam, First-Order Learning for Web Mining, Proceedings of the 10th European Conference on Machine Learning, p.250-255, April 21-23, 1998
• 51: A. McCallum and K. Nigam. A comparison of event models for naive Bayes text classification. In AAAI/ICML-98 Workshop on Learning for Text Categorization, pages 41--48. AAAI Press, 1998. Also technical report WS-98-05, CMU; online at http://www.cs.cmu.edu/~knigam/papers/multinomial-aaaiws98.pdf.
• 52: Andrew McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, A Machine Learning Approach to Building Domain-Specific Search Engines, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.662-667, July 31-August 06, 1999
• 53: Andrew McCallum , Ronald Rosenfeld , Tom M. Mitchell , Andrew Y. Ng, Improving Text Classification by Shrinkage in a Hierarchy of Classes, Proceedings of the Fifteenth International Conference on Machine Learning, p.359-367, July 24-27, 1998
• 54: Jason McHugh , Serge Abiteboul , Roy Goldman , Dallas Quass , Jennifer Widom, Lore: a database management system for semistructured data, ACM SIGMOD Record, v.26 n.3, p.54-66, Sept. 1997 [doi>10.1145/262762.262770]
• 55: M. S. Mizruchi, P. Mariolis, M. Schwartz, and B. Mintz. Techniques for disaggregating centrality scores in social networks. In N. B. Tuma, editor, Sociological Methodology, pages 26--48. Jossey-Bass, San Francisco, 1986.
• 56: T. K. Moon and W. C. Sterling. Mathematical Methods and Algorithms for Signal Processing. Prentice Hall, 1 edition, Aug. 1999.
• 57: K. Nigam, J. Lafferty, and A. McCallum. Using maximum entropy for text classification. In IJCAI'99 Workshop on Information Filtering, 1999. Online at http://www.cs.cmu.edu/~mccallum/papers/maxent-ijcaiws99.ps.gz.
• 58: C. Papadimitriou, P. Raghavan, H. Tamaki, and S. Vempala. Latent sematic indexing: A probabilistic analysis. Submitted for publication.
• 59: J. Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. Technical Report MSR-TR-98-14, Microsoft Research, 1998. Online at http://www.research.microsoft.com/users/jplatt/smoTR.pdf.
• 60: Jason Rennie , Andrew McCallum, Using Reinforcement Learning to Spider the Web Efficiently, Proceedings of the Sixteenth International Conference on Machine Learning, p.335-343, June 27-30, 1999
• 61: E. S. Ristad. A natural law of succession. Research report CS-TR-495-95, Princeton University, July 1995.
• 62: Gerald Salton, Automatic text processing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 63: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 64: Jacques Savoy, An extended vector-processing scheme for searching information in hypertext systems, Information Processing and Management: an International Journal, v.32 n.2, p.155-170, March 1996 [doi>10.1016/S0306-4573(96)85003-5]
• 65: R. G. Schank and C. J. Rieger. Inference and computer understanding of natural language. In in Readings in Knowledge Representation, R. J. Brachman and H. J. Levesque (ed.), Morgan Kaufmann Publishers, 1985.
• 66: Hinrich Schütze , Craig Silverstein, Projections for efficient document clustering, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.74-81, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 67: J. F. Sowa, Conceptual structures: information processing in mind and machine, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 68: D. Temperley. An introduction to link grammar parser. Technical report, Apr. 1999. Online at http://www.link.cs.cmu.edu/link/dict/introduction.html.
• 69: V. Vapnik, S. Golowich, and A. J. Smola. Support vector method for function approximation, regression estimation, and signal processing. In Advances in Neural Information Processing Systems. MIT Press, 1996.
• 70: S. Wasserman and K. Faust. Social Network Analysis. Cambridge University Press, 1994.
• 71: Terry Winograd, Language As a Cognitive Process: Syntax, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1982
• 72: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997