Identifying clusters from positive data

Abstract

The relationship between natural topological properties and clusterability has been investigated. The clusterability of a class does not depend on the decision which numbering of the class is used as a hypothesis space for the clusterer. The Turing degrees of maximal oracles which permit to solve all computationally interactable aspects of clustering are determined. It is shown that some oracles are trivial in the sense that they do not provide any useful information for clustering at all.