Concepts and effectiveness of the cover-coefficient-based clustering methodology for text databases

ABSTRACT

A new algorithm for document clustering is introduced. The base concept of the algorithm, the cover coefficient (CC) concept, provides a means of estimating the number of clusters within a document database and related indexing and clustering analytically. The CC concept is used also to identify the cluster seeds and to form clusters with these seeds. It is shown that the complexity of the clustering process is very low. The retrieval experiments show that the information-retrieval effectiveness of the algorithm is compatible with a very demanding complete linkage clustering method that is known to have good retrieval performance. The experiments also show that the algorithm is 15.1 to 63.5 (with an average of 47.5) percent better than four other clustering algorithms in cluster-based information retrieval. The experiments have validated the indexing-clustering relationships and the complexity of the algorithm and have shown improvements in retrieval effectiveness. In the experiments two document databases are used: TODS214 and INSPEC. The latter is a common database with 12,684 documents.

REFERENCES

• 1: ANDERBERG, M.R. Cluster Analysis for Applications. Academic Press, New York, 1973.
• 2: CAN, F. A new clustering scheme and its use in an information retrieval system incorporating the support of a database machine. Ph.D. dissertation, Dept. of Computer Engineering, Middle East Technical Univ., Ankara, Turkey, 1985.
• 3: Fazli Can , Esen A. Ozkarahan, A clustering scheme, Proceedings of the 6th annual international ACM SIGIR conference on Research and development in information retrieval, June 06-08, 1983, Bethesda, Maryland
• 4: CAN, F., AND OZKARAHAN, E.A. A clustering scheme, In Proceedings of the 6th Annual Sci. 35, 5 (Sept. 1984), 268-276.
• 5: Fazli Can , Esen A. Ozkarahan, Concepts of the cover coefficient-based clustering methodology, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.204-211, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253526]
• 6: F. Can , E. A. Ozkarahan, Dynamic cluster maintenance, Information Processing and Management: an International Journal, v.25 n.3, p.275-291, May 1989 [doi>10.1016/0306-4573(89)90045-9]
• 7: CAN, F., AND OZKARAHAN, E. A. Effectiveness assessment of the cover coefficient based clustering methodology. Working Paper 89-002, Dept. of Systems Analysis, Miami Univ., Oxford, Ohio, Oct. 1989.
• 8: CROUCH, D.B. A file organization and maintenance procedure for dynamic document collections. Inf. Process. Manage. 11, 1 {1975), 11-21.
• 9: Abdelmoula El-Hamdouchi , Peter Willett, Techniques for the measurement of clustering tendency in document retrieval systems, Journal of Information Science, v.13 n.6, p.361-365, December 1, 1987 [doi>10.1177/016555158701300607]
• 10: P. Willett , A. El-Hamdouchi, Comparison of hierarchic agglomerative clustering methods for document retrieval, The Computer Journal, v.32 n.3, p.220-227, June 1989 [doi>10.1093/comjnl/32.3.220]
• 11: GRIFFITHS, A , LUCKHURST, C. AND WILLETT, P. Using interdocument similarity information in document retrieval systems. J. Am. Soc. Inf. Sci. 37, 1 (Jan. 1986), 3-11.
• 12: GRIFFITHS, A., ROBINSON, L. A., AND WILLETT, P. Hierarchical agglomerative clustering methods for automatic document classification. J. Doc. 40, 3 (Sept. 1984), 175-205.
• 13: HODGES, J. L., AND LEHMANN, E.L. Basic Concepts of Probability and Statistics. Holden-Day, San Francisco, Calif., 1964.
• 14: IBM. IBM 3083 processor complex. IBM Doc. G221-2417-0, IBM Corp., Armonk, N.Y., Mar. 1982.
• 15: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 16: KUSIAK, A., AND CHOW, W. ~. An efficient cluster identification algorithm. 11~'EE "l'rans. Syst. Man Cybern. SMC-17, 4 (July-Aug. 1987), 696-699.
• 17: KUTLUAY, M.S. A validity analysis of the cover coefficient concept on cluster analysis. M.S. thesis, Dept. of Electrical and Electronics Engineering, Middle East Technical Univ., Ankara Turkey, 1986.
• 18: Esen Ozkarahan, Database machines and database management, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 19: Esen Ozkarahan , Fazli Can, An automatic and tunable document indexing system, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.234-243, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253218]
• 20: E. Rasmussen , P. Willett, Non-hierarchical document clustering using the ICL distribution array processor, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.132-139, June 03-05, 1987, New Orleans, Louisiana, United States [doi>10.1145/42005.42020]
• 21: SALTON, G. Cluster search strategies and the optimization of retrieval effectiveness. In The Smart Retrieval System--Experiments in Automatic Document Processing, G. Salton, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1971, pp. 223-242.
• 22: Gerard Salton, Dynamic information and library processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1975
• 23: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 24: Gerard Salton , Christopher Buckley, Term-weighting approaches in automatic text retrieval, Information Processing and Management: an International Journal, v.24 n.5, p.513-523, 1988 [doi>10.1016/0306-4573(88)90021-0]
• 25: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 26: G. Salton , A. Wong, Generation and search of clustered files, ACM Transactions on Database Systems (TODS), v.3 n.4, p.321-346, Dec. 1978 [doi>10.1145/320289.320291]
• 27: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 28: Ellen M. Voorhees, The cluster hypothesis revisited, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.188-196, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253524]
• 29: Ellen Marie Voorhees, The effectiveness and efficiency of agglomerative hierarchic clustering in document retrieval, Cornell University, Ithaca, NY, 1986
• 30: Ellen M Voorhees, Implementing agglomerative hierarchic clustering algorithms for use in document retrieval, Information Processing and Management: an International Journal, v.22 n.6, p.465-476, Dec. 1986 [doi>10.1016/0306-4573(86)90097-X]
• 31: Ellen M. Voorhees, The efficiency of inverted index and cluster searches, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.164-174, September 1986, Palazzo dei Congressi, Pisa, Italy [doi>10.1145/253168.253203]
• 32: Peter Willett, Recent trends in hierarchic document clustering: a critical review, Information Processing and Management: an International Journal, v.24 n.5, p.577-597, 1988 [doi>10.1016/0306-4573(88)90027-1]
• 33: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]

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.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.6 Library Automation
          Subjects: Large text archives

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING

General Terms:
Algorithms, Design, Experimentation

Keywords:
cluster validity, clustering-indexing relationships, cover coefficient, decoupling coefficient, document retrieval, retrieval effectiveness