An effective document clustering method using user-adaptable distance metrics

ABSTRACT

Document clustering is inherently an unsupervised learning process that organizes document (or text) data into distinct groups without depending on pre-specified knowledge. However, real-world applications, such as building a topical hierarchy for a large document collection, need to perform clustering under various kinds of constraints. This paper presents a new type of supervised clustering to organize information in a way that reflects knowledge provided by a user. As a means by which external human knowledge can be incorporated into the clustering process, a quadratic form distance metric is employed that contains a weight matrix. Also, we propose a way of representing knowledge to guide the clustering process and a variant of the gradient descent search technique to find a user-specific weight matrix under the hierarchical clustering strategy.

REFERENCES

• 1: Javed Aslam , Katya Pelekhov , Daniela Rus, Static and dynamic information organization with star clusters, Proceedings of the seventh international conference on Information and knowledge management, p.208-217, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288659]
• 2: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 3: D. R. Fuhrmann, and M. I. Miller. On the Existence of Positive-Definite Maximum-Likelihood Estimates of Structured Covariance Matrices. IEEE Transaction on Information Theory, 34(4):722-729, 1988.
• 4: M. D. Gordon. User-based Document clustering by Redescribing Subject Description with a Genetic Algorithm, Journal of the American Society for Information Science, 42(5):311-322, 1991.
• 5: David A. Grossman , Ophir Frieder, Information Retrieval: Algorithms and Heuristics, Kluwer Academic Publishers, Norwell, MA, 1998
• 6: Han-Joon Kim , Sang-Goo Lee, A semi-supervised document clustering technique for information organization, Proceedings of the ninth international conference on Information and knowledge management, p.30-37, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354777]
• 7: T. Labzour, A. Bensaid, and J. Bezdek. Improved Semi-Supervised Point-Prototype Clustering Algorithms. In Proc. of Int'l Conf. on Fuzzy Systems, pp.1383-1387, 1998.
• 8: Mourad Mechkour , David J. Harper , Gheorghe Muresan, The WebCluster project. Using clustering for mediating access to the World Wide Web, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.357-358, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291047]
• 9: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 10: Yasushi Ogawa , Tetsuya Morita , Kiyohiko Kobayashi, A fuzzy document retrieval system using the keyword connection matrix and a learning method, Fuzzy Sets and Systems, v.39 n.2, p.163-179, Jan. 25, 1991 [doi>10.1016/0165-0114(91)90210-H]
• 11: Mehran Sahami , Salim Yusufali , Michelle Q. W. Baldonaldo, SONIA: a service for organizing networked information autonomously, Proceedings of the third ACM conference on Digital libraries, p.200-209, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276697]
• 12: Luis Talavera , Javier Béjar, Integrating Declarative Knowledge in Hierarchical Clustering Tasks, Proceedings of the Third International Symposium on Advances in Intelligent Data Analysis, p.211-222, August 01, 1997
• 13: http://www.research.att.com/~lewis/

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

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

Keywords:
document clustering, hierarchical clustering, information organization, quadratic form distance, user knowledge