Kendall距离与Kendall tau距离的区别、符号解析及落地实现问询

Hey there! Let’s break down your questions one by one to get you sorted with your ranking optimization task using Borda count and Kendall distance.

1. Difference Between Kendall Distance and Kendall Tau #

The confusion often comes from overlapping naming conventions, so let’s anchor this to your project’s documentation:

• Kendall Distance (as defined in your docs)：
  • Counts the total number of pairwise "inconsistencies" between two rankings. For any pair of items, if their relative order is reversed across the two rankings, that’s one inconsistency.
  • The normalized version divides this raw inconsistency count by the maximum possible inconsistencies, calculated via the combination formula C(n,2) = n(n-1)/2 (where n is the number of items). This normalized value ranges from 0 (perfectly identical rankings) to 1 (completely reversed rankings) — smaller values mean higher similarity.
• Kendall Tau：
  • A similarity metric derived from the normalized Kendall distance. The most common variant (tau-a) is calculated as:
    tau_a = (number of consistent pairs - number of inconsistent pairs) / C(n,2)
  • This simplifies to 1 - 2 * (normalized Kendall distance), and ranges from -1 (completely reversed rankings) to 1 (perfectly identical rankings) — larger values mean higher similarity.
• The key mix-up point: Sometimes people refer to the raw inconsistency count as "Kendall tau distance", which overlaps with your project’s "Kendall distance" term. Just remember your task uses the normalized Kendall distance (smaller = more similar), not the tau metric (which uses the opposite scale).

2. What Does (j,s), j≠s Mean in the Summation? #

This notation tells you to iterate over all unique pairs of distinct items in your ranking set. For n items, there are exactly C(n,2) such pairs (since we only need to check each pair once, regardless of the order of j and s).

• In Kendall distance calculations, this summation is used to count every inconsistent pair: For each pair (j,s) where j isn’t the same as s, you check if their relative order is reversed between the two rankings. Each reversal adds 1 to the total distance.
• Example with your 4 items (x1, x2, x3, x4): The pairs are (x1,x2), (x1,x3), (x1,x4), (x2,x3), (x2,x4), (x3,x4) — exactly 6 pairs, matching C(4,2) = 4*3/2 = 6.

3. Calculating Kendall Distance for Your Given Rankings #

First, let’s clarify your data: Each row A_i shows the position rank of each item (1 = highest priority, 4 = lowest). So for A1, the actual ranking order is x2 (1) > x4 (2) > x3 (3) > x1 (4).

Let’s walk through calculating the normalized Kendall distance between A1 and A3 as an example:

1. Convert position ranks to item order:
   • A1 order: [x2, x4, x3, x1]
   • A3 order: [x4, x3, x2, x1] (since A3 assigns x4 to position 1, x3 to 2, x2 to 3, x1 to 4)
2. List all unique item pairs (6 total, as noted earlier)
3. Count inconsistent pairs:
   • (x1,x2): A1 has x2 before x1; A3 has x2 before x1 → consistent (0)
   • (x1,x3): A1 has x3 before x1; A3 has x3 before x1 → consistent (0)
   • (x1,x4): A1 has x4 before x1; A3 has x4 before x1 → consistent (0)
   • (x2,x3): A1 has x2 before x3; A3 has x3 before x2 → inconsistent (1)
   • (x2,x4): A1 has x2 before x4; A3 has x4 before x2 → inconsistent (1)
   • (x3,x4): A1 has x4 before x3; A3 has x4 before x3 → consistent (0)
4. Compute raw and normalized distance:
   • Raw Kendall distance (inconsistency count): 2
   • Normalized distance: 2 / C(4,2) = 2/6 ≈ 0.333

To compute distances between all pairs of your rankings (A1-A5), just repeat this process for every combination. If you’re optimizing a combined ranking (using Borda count + Kendall distance minimization), generate candidate combined rankings, calculate their total normalized Kendall distance to all A_i rankings, and pick the one with the smallest total.

内容的提问来源于stack exchange，提问作者Jerry Chen