Locality preserving indexing for document representation

ABSTRACT

Document representation and indexing is a key problem for document analysis and processing, such as clustering, classification and retrieval. Conventionally, Latent Semantic Indexing (LSI) is considered effective in deriving such an indexing. LSI essentially detects the most representative features for document representation rather than the most discriminative features. Therefore, LSI might not be optimal in discriminating documents with different semantics. In this paper, a novel algorithm called Locality Preserving Indexing (LPI) is proposed for document indexing. Each document is represented by a vector with low dimensionality. In contrast to LSI which discovers the global structure of the document space, LPI discovers the local structure and obtains a compact document representation subspace that best detects the essential semantic structure. We compare the proposed LPI approach with LSI on two standard databases. Experimental results show that LPI provides better representation in the sense of semantic structure.

REFERENCES

• 1: Rie Kubota Ando, Latent semantic space: iterative scaling improves precision of inter-document similarity measurement, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.216-223, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345579]
• 2: Rie Kubota Ando , Lillian Lee, Iterative residual rescaling, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.154-162, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383981]
• 3: Brian T. Bartell , Garrison W. Cottrell , Richard K. Belew, Latent semantic indexing is an optimal special case of multidimensional scaling, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.161-167, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133191]
• 4: M. Belkin and P. Niyogi, "Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering", Advances in Neural Information Processing Systems 14, Vancouver, Canada, 2001.
• 5: Ella Bingham , Heikki Mannila, Random projection in dimensionality reduction: applications to image and text data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.245-250, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502546]
• 6: Fan R. K. Chung, Spectral Graph Theory, Regional Conferences Series in Mathematics, number 92, 1997.
• 7: S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. harshman, "Indexing by Latent Semantic Analysis", Journal of the American Society of Information Science, 41(6):391--407, 1990.
• 8: L. Devroye, L. Gyorfi, and G. Lugosi, A Probabilistic Theory of Pattern Recognition. Springer-Verlag New York, Inc., 1996.
• 9: Chris H. Q. Ding, A similarity-based probability model for latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.58-65, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312652]
• 10: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 11: Susan T. Dumais , Jakob Nielsen, Automating the assignment of submitted manuscripts to reviewers, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.233-244, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133205]
• 12: Peter W. Foltz , Susan T. Dumais, Personalized information delivery: an analysis of information filtering methods, Communications of the ACM, v.35 n.12, p.51-60, Dec. 1992 [doi>10.1145/138859.138866]
• 13: Xiaofei He and Partha Niyogi, "Locality Preserving Projections", in Advances in Neural Information Processing Systems 16, Vancouver, Canada, 2003.
• 14: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 15: Charles Lee Isbell, Jr. , Paul Viola, Restructuring sparse high dimensional data for effective retrieval, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.480-486, July 1999
• 16: Tamara G. Kolda , Dianne P. O'Leary, A semidiscrete matrix decomposition for latent semantic indexing information retrieval, ACM Transactions on Information Systems (TOIS), v.16 n.4, p.322-346, Oct. 1998 [doi>10.1145/291128.291131]
• 17: K. Lang, "Learning to filter netnews", Proc. Of the 12th Int. Conf. on Machine Learning, 1995.
• 18: Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275505]
• 19: S. T. Roweis, L. K. Saul, "Nonlinear Dimensionality Reduction by Locally Linear Embedding", Science, vol 290, 22 December 2000.
• 20: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 21: J. B. Tenenbaum, Vin De Silva, and J. C. Langford, "A Global Geometric Framework for Nonlinear Dimensionality Reduction", Science, Vol 290, 22 December 2000.
• 22: Wei Xu , Xin Liu , Yihong Gong, Document clustering based on non-negative matrix factorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860485]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory

Keywords:
dimensionality reduction, document representation and indexing, latent semantic indexing, locality preserving indexing, similarity measure, vector space model