Document clustering: an optimization problem

ABSTRACT

Clustering algorithms have been widely used in information retrieval applications. However, it is difficult to define an objective "best" result. This article analyzes some document clustering algorithms and illustrates that they are equivalent to the optimization problem of some global functions. Experiments show their good performance, but there are still counter-examples where they fail to return the optimal solution. We argue that Monte-Carlo algorithms in the global optimization framework have the potential to find better solutions than traditional clustering, and they are able to handle more complex structures.

REFERENCES

• 1: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 2: C. J. van Rijsbergen and K. S. Jones. A test for the separation of relevant and non-relevant documents in experimental retrieval collections. Journal of Documentation}, 29(3):251--257, 1973.

INDEX TERMS

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

General Terms:
Algorithms, Performance, Theory

Keywords:
clustering algorithm, global optimization, simulated annealing