Criteria for Polynomial Time (Conceptual) Clustering (Preprint)

Abstract

Research in cluster analysis has 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 which have "good" descriptions in some language. We investigate the general properties which 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1987
Accession Number
ADA638205

Entities

People

  • Leonard Pitt
  • Robert E. Reinke

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Autonomy

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Clustering
  • Information Operations
  • Language
  • Learning
  • Machine Learning
  • Mathematics
  • Polynomials
  • Three Dimensional

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Artificial Intelligence
  • Regression Analysis.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms