Ulam Distance for Ordinal Variables

< Previous | Next | Content >

Ulam Distance

Ulam distance measure disorder of ordinal variables by counting the minimum number of Delete-Shift-Insert operations.

The algorithm to compute Ulam distance is to count the minimum number of operation Delete-Shift-Insert :

1. Take or delete any single digit on disorder-vector that does not match to the corresponding digit in pattern-vector.
2. Shift the remaining digit on disorder-vector to remove the empty space
3. Shift an empty space on disorder-vector that match to the corresponding digit in pattern-vector.
4. Put or Insert back the deleted digit the empty space

Example:

We have ask two persons, A and B about their preference on public transport and here is their ordering vector A = [Bus, Van, Train] and B =[Van, Bus, Train]

Suppose we use vector A = [Bus, Van, Train] as pattern-vector and vector B=[Van, Bus, Train] as disorder-vector. Diagram below shows only single interchange operation is needed to transform disorder-vector into pattern-vector. Thus, the Ulam distance of preference between A and B is 1

Example:

Suppose we have two judges (A and B) who give rank of importance over 6 products. The ranking vector is given as follow A=[1, 2, 3, 4, 5, 6] and B = [2, 5, 3, 1, 4, 6]. We want to measure Ulam distance between A and B

We set rank vector A as pattern-vector and vector B as disorder-vector. Our goal is to count the minimum number of steps of operation Interchange of any pair to make disorder-vector into pattern-vector. Diagram below show the steps. Since we count two number of the operation Delete-Shift-Insert , thus the Ulam distance between A and B is 2.

< Previous | Next | Content >

Rate this tutorial

This tutorial is copyrighted.

Preferable reference for this tutorial is

Teknomo, Kardi (2015) Similarity Measurement. http:\people.revoledu.comkardi tutorialSimilarity