ケンドールタウ距離

Kendallタウ ランク距離は、2 つのランキング リスト間のペアごとの不一致の数をカウントするメトリック (距離関数)です。距離が大きいほど、2 つのリストは類似していないことになります。Kendall タウ距離は、バブル ソートアルゴリズムが 1 つのリストを他のリストと同じ順序に配置するために実行するスワップの数に相当するため、バブル ソート距離とも呼ばれます。Kendall タウ距離は、 Maurice Kendallによって作成されました。

2 つのリストと間の Kendall タウ順位距離は、とがそれぞれ との要素の順位である 場合です 。 ${\displaystyle \tau_{1}}$${\displaystyle \tau_{2}}$$${\displaystyle K_{d}(\tau _{1},\tau _{2})=|\{(i,j):i<j,[\tau _{1}(i)<\tau _ {1}(j)\wedge \tau _{2}(i)>\tau _{2}(j)]\vee [\tau _{1}(i)>\tau _{1}(j)\wedge \tau _{2}(i)<\tau _{2}(j)]\}|.}$$${\displaystyle \tau_{1}(i)}$${\displaystyle \tau_{2}(i)}$${\displaystyle i}$${\displaystyle \tau_{1}}$${\displaystyle \tau_{2}}$

${\displaystyle K_{d}(\tau _{1},\tau _{2})}$2 つのリストが同一の場合は 0 になり、一方のリストが他方のリストの逆の場合は (リストのサイズ)になります。${\textstyle {\frac {1}{2}}n(n-1)}$${\displaystyle n}$

ケンドールタウ距離は次のように定義されることもある。 $${\displaystyle K_{d}(\tau _{1},\tau _{2})=\sum _{\{i,j\}\in P,i<j}{\bar {K}}_{i,j}(\tau _{1},\tau _{2})}$$

どこ

• Pは、および内の異なる要素の順序付けられていないペアの集合である。${\displaystyle \tau_{1}}$${\displaystyle \tau_{2}}$
• ${\displaystyle {\bar {K}}_{i,j}(\tau _{1},\tau _{2})}$= 0、iとjが同じ順序である場合、${\displaystyle \tau_{1}}$${\displaystyle \tau_{2}}$
• ${\displaystyle {\bar {K}}_{i,j}(\tau _{1},\tau _{2})}$= 1、iとjが逆の順序である場合${\displaystyle \tau_{1}}$${\displaystyle \tau_{2}.}$

ケンドールのタウ距離は、不一致なペアの合計数として定義することもできます。

ランキングにおけるケンドールのタウ距離: 順列 (またはランキング) は、0 から N-1 までの各整数が 1 回ずつ出現する N 個の整数の配列です。

2つのランキング間のケンドールタウ距離は、2つのランキングで異なる順序になっているペアの数です。たとえば、0 3 1 6 2 5 4と1 0 3 6 4 2 5の間のケンドールタウ距離は4です。これは、0-1、3-1、2-4、5-4のペアが2つのランキングで異なる順序になっているが、他のすべてのペアは同じ順序になっているためです。^[1]

正規化されたケンドールタウ距離 は、したがって区間[0,1]内にあります。 ${\displaystyle K_{n}}$${\displaystyle {\frac {K_{d}}{{\frac {1}{2}}n(n-1)}}={\frac {2K_{d}}{n(n-1)}}}$

Kendall タウ距離関数が(ここで、 と はそれぞれと の要素の順位)の代わりに として実行される場合、三角不等式は保証されません。リストに繰り返しがある場合にも、三角不等式が失敗することがあります。そのため、メトリックを扱っているわけではありません。 ${\displaystyle K(L1,L2)}$${\displaystyle K(\tau _{1},\tau _{2})}$${\displaystyle \tau_{1}}$${\displaystyle \tau_{2}}$${\displaystyle L1}$${\displaystyle L2}$

ケンドールタウ距離の一般化バージョンは、さまざまな項目やランキングのさまざまな位置に重みを与えるために提案されています。^[2]

ケンドールのタウ距離（）は、統計で使用されるケンドールのタウ順位相関係数（）と混同しないでください。 ${\displaystyle K_{d}}$${\displaystyle K_{c}}$

これらは  、${\displaystyle K_{c}=1-4K_{d}/(n(n-1))}$${\displaystyle K_{d}=(1-K_{c})(n(n-1))/4}$

または、より簡単に言うと  、正規化された距離は上記を参照) ${\displaystyle K_{c}=1-2K_{n},K_{n}=(1-K_{c})/2}$${\displaystyle K_{n}}$${\displaystyle 2K_{d}/(n(n-1))}$

距離は 0 から までの値です。(正規化された距離は 0 から 1 までです) ${\displaystyle n(n-1)/2}$

相関関係は -1 から 1 の間です。

等しいものの間の距離は 0 で、等しいものの間の相関は 1 です。

反転間の距離は、反転間の相関は-1です。 ${\displaystyle n(n-1)/2}$

たとえば、ランキング A>B>C>D と A>B>C>D を比較すると、距離は 0、相関は 1 になります。

ランキングA>B>C>DとD>C>B>Aを比較すると、距離は6、相関は-1です。

順位を比較すると、A>B>C>DとB>D>A>Cの距離は3、相関は0です。

5 人のグループを身長と体重で順位付けするとします。

ここで、人 A は最も背が高く、3 番目に重い、人 B は 2 番目に背が高く、4 番目に重い、というようになります。

これら 2 つのランキング間のケンドール タウ距離を計算するには、各人を他のすべての人とペアにして、リスト 1 の値がリスト 2 の値と逆の順序になっている回数を数えます。

値が逆の順序になっているペアが4つあるので、ケンドールタウ距離は4です。正規化されたケンドールタウ距離は

${\displaystyle {\frac {4}{5(5-1)/2}}=0.4.}$

値が 0.4 の場合、2 つのリスト間でペアの 40% の順序が異なることを示します。

Python での単純な実装 ( NumPyを使用) は次のとおりです。

 numpyを npとして インポートする

def  normalised_kendall_tau_distance ( values1 ,  values2 ): 
"""ケンドールのタウ距離を計算します。""" n = len ( values1 ) assert len ( values2 ) == n , "両方のリストの長さは同じである必要があります" i , j = np . meshgrid ( np . arange ( n ), np . arange ( n )) a = np . argsort ( values1 ) b = np . argsort ( values2 ) ndisordered = np . logical_or ( np . logical_and ( a [ i ] < a [ j ], b [ i ] > b [ j ]), np . logical_and ( a [ i ] > a [ j ], b [ i ] < b [ j ])) . sum () return ndisordered / ( n * ( n - 1 ))    
      
        
        
      
      
                 
           

ただし、これにはメモリが必要となり、大規模な配列では非効率的です。 ${\displaystyle n^{2}}$

2 つのランキング が与えられた場合、 となるように項目の名前を変更することができます。すると、ケンドールのタウ距離を計算する問題は、における反転の数、つまりとなるようなインデックス ペアの数を計算することに簡略化されます。この数を計算するアルゴリズムはいくつかあります。 ${\displaystyle \tau _{1},\tau _{2}}$${\displaystyle \tau _{1}=(1,2,3,...)}$${\displaystyle \tau_{2}}$${\displaystyle i,j}$${\displaystyle i<j}$${\displaystyle \tau _{2}(i)>\tau _{2}(j)}$

• マージソートに基づく単純なアルゴリズムには時間がかかる。^[3]${\displaystyle O(n\log n)}$
• より高度なアルゴリズムには時間が必要である。^[4]${\displaystyle O(n{\sqrt {\log {n}}})}$

以下は基本的な C 実装です。

#include <stdbool.h> 

int kendallTau ( short x [], short y [], int len ) { int i , j , v = 0 ; bool a , b ;       
         
      

    ( i = 0 ; i < len ; i ++ ) { ( j = i + 1 ; j < len ; j ++ ) {​​        
                  

            a = x [ i ] < x [ j ] && y [ i ] > y [ j ]; b = x [ i ] > x [ j ] && y [ i ] < y [ j ];        
                    

            もし( a || b ) v ++であれば;   
                

        } 
}    

    戻り値: abs ( v ); } 


float normalize ( int kt 、int len ) { return kt / ( len * ( len - 1 ) / 2.0 ); }     
             

• ケンドールタウ順位相関係数
• スピアマンの順位相関係数
• ケメニー・ヤングの最大尤度投票ルール

• Fagin, R.; Kumar, R.; Sivakumar, D. (2003). 「上位 k リストの比較」. SIAM Journal on Discrete Mathematics . 17 (1): 134–160. CiteSeerX  10.1.1.86.3234 . doi :10.1137/S0895480102412856. S2CID  6249357.
• Kendall, M. (1948)。順位相関法。Charles Griffin & Company Limited。
• Kendall, M. (1938). 「順位相関の新しい尺度」Biometrika . 30 (1/2): 81–89. doi :10.2307/2332226. JSTOR  2332226.

• オンラインソフトウェア: ケンドールのタウ順位相関を計算する
• QuickVote — 2 つのインタラクティブなランキング リスト間の Kendall タウ距離を計算し、リスト間のペアごとの不一致を表示する Web サイト。