Non-Euclidean or non-metric measures can be informative

Elzbieta Pekalska, Elzbieta Pȩkalska, Artsiom Harol, Robert P W Duin, Barbara Spillmann, Horst Bunke

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    Statistical learning algorithms often rely on the Euclidean distance. In practice, non-Euclidean or non-metric dissimilarity measures may arise when contours, spectra or shapes are compared by edit distances or as a consequence of robust object matching [1,2]. It is an open issue whether such measures are advantageous for statistical learning or whether they should be constrained to obey the metric axioms. The k-nearest neighbor (NN) rule is widely applied to general dissimilarity data as the most natural approach. Alternative methods exist that embed such data into suitable representation spaces in which statistical classifiers are constructed [3]. In this paper, we investigate the relation between non-Euclidean aspects of dissimilarity data and the classification performance of the direct NN rule and some classifiers trained in representation spaces. This is evaluated on a parameterized family of edit distances, in which parameter values control the strength of non-Euclidean behavior. Our finding is that the discriminative power of this measure increases with increasing non-Euclidean and non-metric aspects until a certain optimum is reached. The conclusion is that statistical classifiers perform well and the optimal values of the parameters characterize a non-Euclidean and somewhat non-metric measure. © Springer-Verlag Berlin Heidelberg 2006.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|Lect. Notes Comput. Sci.
    PublisherSpringer Nature
    Number of pages9
    ISBN (Print)3540372369, 9783540372363
    Publication statusPublished - 2006
    EventJoint IAPR International Workshops on Structural, Syntactic, and Statistical Pattern Recognition, SSPR 2006 and SPR 2006 - Hong Kong
    Duration: 1 Jul 2006 → …

    Publication series

    NameLecture Notes in Computer Science


    ConferenceJoint IAPR International Workshops on Structural, Syntactic, and Statistical Pattern Recognition, SSPR 2006 and SPR 2006
    CityHong Kong
    Period1/07/06 → …
    Internet address


    Dive into the research topics of 'Non-Euclidean or non-metric measures can be informative'. Together they form a unique fingerprint.

    Cite this