Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/70813
Type: Conference paper
Title: Metric structures on datasets: stability and classification of algorithms
Author: Memoli, Facundo
Citation: Proceedings of the 14th International Conference on Computer Analysis of Images and Patterns (CAIP), 29-31 August, 2011, Seville, Spain: pp.1-33
Publisher: Springer-Verlag
Issue Date: 2011
ISBN: 9783642236778
Conference Name: International Conference on Computer Analysis of Images and Patterns (CAIP) (2011 : Seville, Spain)
CAIP 2011
School/Discipline: School of Computer Science
Statement of
Responsibility: 
Facundo Mémoli
Abstract: Several methods in data and shape analysis can be regarded as transformations between metric spaces. Examples are hierarchical clustering methods, the higher order constructions of computational persistent topology, and several computational techniques that operate within the context of data/shape matching under invariances. Metric geometry, and in particular different variants of the Gromov-Hausdorff distance provide a point of view which is applicable in different scenarios. The underlying idea is to regard datasets as metric spaces, or metric measure spaces (a.k.a. mm-spaces, which are metric spaces enriched with probability measures), and then, crucially, at the same time regard the collection of all datasets as a metric space in itself. Variations of this point of view give rise to different taxonomies that include several methods for extracting information from datasets. Imposing metric structures on the collection of all datasets could be regarded as a "soft" construction. The classification of algorithms, or the axiomatic characterization of them, could be achieved by imposing the more "rigid" category structures on the collection of all finite metric spaces and demanding functoriality of the algorithms. In this case, one would hope to single out all the algorithms that satisfy certain natural conditions, which would clarify the landscape of available methods. We describe how using this formalism leads to an axiomatic description of many clustering algorithms, both flat and hierarchical.
Rights: Springer-Verlag Berlin, Heidelberg © 2011
RMID: 0020115448
Published version: http://dl.acm.org/citation.cfm?id=2044577
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.