ON ORDER EQUIVALENCES BETWEEN DISTANCE AND SIMILARITY MEASURES ON SEQUENCES AND TREES

Martin Emms, Hector-Hugo Franco-Penya

2012

Abstract

Both ’distance’ and ’similarity’ measures have been proposed for the comparison of sequences and for the comparison of trees, based on scoring mappings, and the paper concerns the equivalence or otherwise of these. These measures are usually parameterised by an atomic ’cost’ table, defining label-dependent values for swaps, deletions and insertions. We look at the question of whether orderings induced by a ’distance’ measure, with some cost-table, can be dualized by a ’similarity’ measure, with some other cost-table, and vice-versa. Three kinds of orderings are considered: alignment-orderings, for fixed source S and target T, neighbour-orderings, where for a fixed S, varying candidate neighbours Ti are ranked, and pair-orderings, where for varying Si, and varying Tj , the pairings hSi,Tji are ranked. We show that (1) alignment-orderings by distance can be dualized by similarity, and vice-versa; (2) neigbour-ordering and pair-ordering by distance can be dualized by similarity; (3) neighbour-ordering and pair-ordering by similarity can sometimes not be dualized by distance. A consequence if this is that there are categorisation and hierarchical clustering outcomes which can be achieved via similarity but not via distance.

Paper Citation

in Harvard Style

Emms M. and Franco-Penya H. (2012). ON ORDER EQUIVALENCES BETWEEN DISTANCE AND SIMILARITY MEASURES ON SEQUENCES AND TREES . In Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM, ISBN 978-989-8425-98-0, pages 15-24. DOI: 10.5220/0003712500150024

in Bibtex Style

@conference{icpram12,
author={Martin Emms and Hector-Hugo Franco-Penya},
title={ON ORDER EQUIVALENCES BETWEEN DISTANCE AND SIMILARITY MEASURES ON SEQUENCES AND TREES},
booktitle={Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,},
year={2012},
pages={15-24},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003712500150024},
isbn={978-989-8425-98-0},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 1st International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,
TI - ON ORDER EQUIVALENCES BETWEEN DISTANCE AND SIMILARITY MEASURES ON SEQUENCES AND TREES
SN - 978-989-8425-98-0
AU - Emms M.
AU - Franco-Penya H.
PY - 2012
SP - 15
EP - 24
DO - 10.5220/0003712500150024