Please use this identifier to cite or link to this item:
https://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 |
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.