Exploiting asymmetry in hierarchical topic extraction

ABSTRACT

Topic or feature extraction is often used as an important step in document classification and text mining. Topics are succinct representation of content in a document collection and hence are very effective when used as content identifiers in peer-to-peer systems and other large scale distributed content management systems. Effective topic extraction is dependent on the accuracy of term clustering that often has to deal with problems like synonymy and polysemy. Retrieval techniques based on spectral analysis like Latent Semantic Indexing (LSI) are often used to effectively solve these problems. Most of the spectral retrieval schemes produce term similarity measures that are symmetric and often, not an accurate characterization of term relationships. Another drawback of LSI is its running time that is polynomial in the dimensions of the m x n matrix, A. This can get prohibitively large for some IR applications. In this paper, we present efficient algorithms using the technique of Locality-Sensitive Hashing (LSH) to extract topics from a document collection based on the asymmetric relationships between terms in a collection. The relationship is characterized by the term co-occurrences and other higher-order similarity measures. Our LSH based scheme can be viewed as a simple alternative to LSI. We show the efficacy of our algorithms via experiments on a set of large documents. An interesting feature of our algorithms is that it produces a natural hierarchical decomposition of the topic space instead of a flat clustering.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 3: A. Budanitsky and G. Hirst. Semantic distance in wordnet: An experimental, application-oriented evaluation of five measures. In Proc. of the North American Chapter of the Association for Computational Linguistics (NAACL-2001), Pittsburgh, PA, June 2001., 2001.
• 4: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 5: 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.
• 6: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 7: Inderjit S. Dhillon , Subramanyam Mallela , Rahul Kumar, Enhanced word clustering for hierarchical text classification, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775076]
• 8: P. Drineas , A. Frieze , R. Kannan , S. Vempala , V. Vinay, Clustering Large Graphs via the Singular Value Decomposition, Machine Learning, v.56 n.1-3, p.9-33 [doi>10.1023/B:MACH.0000033113.59016.96]
• 9: Douglas H. Fisher, Knowledge Acquisition Via Incremental Conceptual Clustering, Machine Learning, v.2 n.2, p.139-172, September 1987 [doi>10.1023/A:1022852608280]
• 10: G. W. Flake, R. E. Tarjan, and K. Tsioutsiouliklis. Graph clustering and minimum-cut trees. Internet Mathematics, 1(4):385--408, 2004.
• 11: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 12: T. H. Haveliwala, A. Gionis, and P. Indyk. Scalable techniques for clustering the web. In WebDB (Informal Proceedings), pages 129--134, 2000.
• 13: http://www.dmoz.org.
• 14: Piotr Indyk , Rajeev Motwani , Prabhakar Raghavan , Santosh Vempala, Locality-preserving hashing in multidimensional spaces, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.618-625, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258656]
• 15: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775126]
• 16: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 17: Jon Kleinberg , Andrew Tomkins, Applications of linear algebra in information retrieval and hypertext analysis, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.185-193, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303995]
• 18: A. Kontostathis and W. Pottenger. Detecting patterns in the LSIterm-term matrix. In Proc. Workshop on the Foundation of Data Mining and Discovery, IEEE International Conference on Data Mining (ICDM'02), 2002.
• 19: T. K. Landauer and S. T. Dumais. A solution to plato's problem: The latent semantic analysis theory of acquisition, induction and representation of knowledge. Psychological Review, 104:211--240, 1997.
• 20: F. McSherry, Spectral Partitioning of Random Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.529, October 14-17, 2001
• 21: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 22: Luis Talavera, Feature Selection as a Preprocessing Step for Hierarchical Clustering, Proceedings of the Sixteenth International Conference on Machine Learning, p.389-397, June 27-30, 1999

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
latent semantic indexing, locality-sensitive hashing