On metric spaces arising during formalization of recognition and classification problems. Part 1: Properties of compactness

• Published in: Pattern recognition and image analysis 2016-04, Vol.26 (2), p.274-284
• Main Authors: Torshin, I. Yu, Rudakov, K. V.
• Format: Article
• Language: English
• Subjects: Algebra; Algorithms; Classification; Cluster analysis; Clustering; Combinatorics; Computer Science; Data analysis; Descriptions; Estimates; Image Processing and Computer Vision; Lattices; Machine learning; Mathematical analysis; Mathematical Method in Pattern Recognition; Metric space; Pattern Recognition; Recognition; Studies; Typological analysis
• ISSN: 1054-6618; 1555-6212
• DOI: 10.1134/S1054661816020255

In the context of the algebraic approach to recognition of Yu.I. Zhuravlev’s scientific school, metric analysis of feature descriptions is necessary to obtain adequate formulations for poorly formalized recognition/classification problems. Formalization of recognition problems is a cross-disciplinary issue between supervised machine learning and unsupervised machine learning. This work presents the results of the analysis of compact metric spaces arising during the formalization of recognition problems. Necessary and sufficient conditions of compactness of metric spaces over lattices of the sets of feature descriptions are analyzed, and approaches to the completion of the discrete metric spaces (completion by lattice expansion or completion by variation of estimate) are formulated. It is shown that the analysis of compactness of metric spaces may lead to some heuristic cluster criteria commonly used in cluster analysis. During the analysis of the properties of compactness, a key concept of a ρ-network arises as a subset of points that allows one to estimate an arbitrary distance in an arbitrary metric configuration. The analysis of compactness properties and the conceptual apparatus introduced (ρ-networks, their quality functionals, the metric range condition, i - and ρ-spectra, ε-neighborhood in a metric cone, ε-isomorphism of complete weighted graphs, etc.) allow one to apply the methods of functional analysis, probability theory, metric geometry, and graph theory to the analysis of poorly formalized problems of recognition and classification.