Deriving distance metrics from generality relations

Many pattern recognition and machine learning approaches employ a distance metric on patterns, or a generality relation to partially order the patterns. We investigate the relationship amongst them and prove a theorem that shows how a distance metric can be derived from a partial order (and a corresponding size on patterns) under mild conditions. We then discuss the use of the theorem. More specifically, we show how well-known distance metrics for sets, strings, trees and graphs can be derived from their generality relation.