< Probability and statistics definitions < Spearman footrule distance
The Spearman footrule distance is a non-negative measure of the difference, or disagreement of two ordered lists, each of which is a full permutation of a set. This nonparametric metric is sometimes used in the Mallows distribution for selecting the optimal model among a set of potential models.
Spearman distances are bi-invariant, which means that they remain unchanged to both permutations — rearrangements of elements — and monotonic transformations — which preserve the order of elements. This means that the Spearman distance between two rankings will be the same if the rankings are permuted or if the rankings are monotonically transformed.
Spearman’s Footrule Distance uses the sum of absolute deviations. A similar measure, Kendall’s Tau, uses the sum of squared deviations.
Spearman footrule distance formula
Spearman’s footrule distance evaluates the distance between two permutations by accumulating the mismatches and summing the distances of the positions of each candidate. It is given by [1]
where i and σ(i) are the two ranks assigned to an object.
The formula measures the total element-wise displacement from the identity permutation. The identity permutation is the permutation that orders the items from 1 to n in increasing order. For example, the identity permutation for 4 items is (1, 2, 3, 4). If the two rankings are the same, the Spearman footrule distance is zero.
Example
Suppose we ask two people P and Q about their cereal preferences and they respond with:
- P = [Oatmeal, Wheat Flakes, Rice Puffs]
- Q = [Wheat Flakes, Oatmeal, Rice Puffs].
We can set these as rank vectors
- P = [1, 2, 3]
- Q = [2, 1, 3].
Summing the absolute differences gives us
[1 – 2] + [2 – 1] + [3 – 3] = 1 + 1 + 0 = 2.
Spearman footrule distance history
Spearman footrule was first introduced by the British psychologist Charles Spearman as an alternative to the correlation in pairs of ranks associated with a random sample from a continuous bivariate distribution.
Kendall [2] examined the footrule as a measure of association but dismissed its utility due to its lack of statistical properties. The footrule gained renewed interest thanks to Diaconis and Graham [1], who emphasized its intuitive interpretation in terms of the Manhattan distance between two sets of ranks.
Due to its robustness, simplicity and natural interpretation, the footrule has been rediscovered and applied in many different contexts [3].
References
- Diaconis, P. & Graham, R. (1977). Spearman’s footrule as a measure of disarray. Journal of the royal statistical society series b-methodological.
- Kendall, M. (1970), Rank Correlation Methods (4th ed.), London: Griffin.
- Genest, C. et al. Spearman’s footrule and Gini’s gamma: a review with complements. Journal of Nonparametric Statistics. Vol. 22, No. 8, November 2010, 937–954.