 

Cayley Distance for Ordinal Variables Cayley distance measure disorder of ordinal variables by counting the minimum number of transposition of any pair digits on disordervectors that at least one digit does not match to the patternvector. Unlike Kendall distance that requires adjacent pair, computation of Cayley distance can select any pair digits on the disordervector.
The algorithm to compute Cayley distance is to count the minimum number of operation “ Interchange ” or transposition of the selected pair:
Similar to Kendall distance, the problem of Cayley distance computation is to find the minimum operation rather than the operation itself. Priority must be given to a pair that its transposition will give higher matched digits between the disordervector and the patternvector. Unlike Kendall distance, any digit that has already matched does not need to be selected anymore. The matched digits will reduce the number of operation, thus .
Cayley distance is rank invariant that the distance will not change after renumbering of the rank. For example, rank 1 to 10 (best to worst) could be renumbered as rank 10 to 1 (again as the best to worst). While other ordinal distance may change due to this renumbering, Cayley distance and Hamming distance, have nice property that the distance does nit be affected by the rank renumbering.
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 patternvector and vector B=[Van, Bus, Train] as disordervector. Diagram below shows only single “interchange” operation is needed to transform disordervector into patternvector. Thus, the Cayley 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 Kendall distance between A and B We set rank vector A as patternvector and vector B as disordervector. Our goal is to count the minimum number of steps of operation “ Interchange ” of any pair to make disordervector into patternvector. Diagram below show the steps. Since we count three number of interchange, thus the Cayley distance between A and B is 3.
See also: Kendall distance, Hamming Distance for ordinal data
Preferable reference for this tutorial is Teknomo, Kardi. Similarity Measurement. http:\\people.revoledu.com\kardi\ tutorial\Similarity\




© 2006 Kardi Teknomo. All Rights Reserved. Designed by CNV Media 