Programmable clustering

ABSTRACT

We initiate a novel study of clustering problems. Rather than specifying an explicit objective function to optimize, our framework allows the user of clustering algorithm to specify, via a first-order formula, what constitutes an acceptable clustering to them. While the resulting genre of problems includes, in general, NP-complete problems, we highlight three specific first-order formulae, and provide efficient algorithms for the resulting clustering problems.

REFERENCES

• 1: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 2: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 3: R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. Karp, editor, Complexity of COmputation, SIAM-AMS Proceedings 7, pages 43--73, 1974.
• 4: Aristides Gionis , Heikki Mannila , Panayiotis Tsaparas, Clustering Aggregation, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.341-352, April 05-08, 2005 [doi>10.1109/ICDE.2005.34]
• 5: N. Immerman. Descriptive Complexity. Springer, 1998.
• 6: N. Jardine and R. Sibson. Mathematical Taxonomy. Wiley, 1971.
• 7: J. Kleinberg. An impossibility theorem for clustering. In Advances in Neural Information Processing Systems 15, pages 446--453, 2002.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Algorithms

General Terms:
Algorithms, Theory

Keywords:
clustering, first-order formula