Criteria for Polynomial-Time (Conceptual) Clustering

Leonard Pitt, Robert E. Reinke

Research output: Contribution to journalArticlepeer-review


Research in cluster analysishas resulted in a large number of algorithms and similarity measurements for clustering scientific data. Machine learning researchers have published a number of methods for conceptual clustering, in which observations are grouped into clusters that have “good” descriptions in some language. In this paper we investigate the general properties that similarity metrics, objective functions, and concept description languages must have to guarantee that a (conceptual) clustering problem is polynomial-time solvable by a simple and widely used clustering technique, the agglomerative-hierarchical algorithm. We show that under fairly general conditions, the agglomerative-hierarchical method may be used to find an optimal solution in polynomial time.

Original languageEnglish (US)
Pages (from-to)371-396
Number of pages26
JournalMachine Learning
Issue number4
StatePublished - Apr 1988
Externally publishedYes


  • Cluster analysis
  • analysis of algorithms
  • conceptual clustering

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence


Dive into the research topics of 'Criteria for Polynomial-Time (Conceptual) Clustering'. Together they form a unique fingerprint.

Cite this