【データ分析】2つのランキングの類似度を測る Part.1
そもそもの問題意識は次のとおり。
複数の人々に、「リンゴ」「マンゴー」「バナナ」「イチゴ」「オレンジ」「ブドウ」のようなアイテム群からランキングを作ってもらうとする。この際ルールとして、同じ順位を付けないこととする。各人が作成したランキングを比較して、どの２つのランキングが最も似ているのか、または最も似ていないのかを定量的に評価する手法が知りたい。
つまり、タイトルにもあるとおり「２つのランキングの類似度を測りたい」ということです。
この方法について仕事で調べる機会があったので、頭の中の整理も兼ねてメモしました。できるだけ数学の前提知識が無くても理解できるように書くことを心がけています。
ランキングの類似度を測る方法
用語の確認：「順序」と「距離」
まず「ランキング」は専門的には「順序」というらしい。そして「どの２つのランキングが最も似ている（似ていない）のか」という「類似度」を測る問いは、専門的には「どの２つの順序の距離が最も近しい（離れている）のか」という「距離」を測る問いに言い換えられるとのこと。
「距離」とは
日常生活で何の気なしに使うことが多い「距離」という言葉ですが、実は数学的には次の４つの条件を満たすものを言うのだそう。
マイナスの値を取らない。（非負性）
同じ場所から同じ場所への距離は0である。（同一性）
ある2点間の距離は、それらの点の順序によって変わらない。（対称性）
ある2点間の距離は、直接経路が最短となる。（三角不等式）
「ランキングの類似度」（順序の距離）が満たしてほしい性質
もし２つのランキングの類似度を定量的に測定できる方法があるとすれば、その方法はどんな性質を満たしているべきでしょうか。私は次の２つの性質が直感的に思い浮かびました。
類似度が最大（距離が最小）なのは全く同じランキング
類似度が最小（距離が最大）なのは全く逆順のランキング
具体的に考えた方が分かりやすいため、ここでは{リンゴ, バナナ, イチゴ}という３つの果物のランキングを考えてみます。
まず１つ目の性質が言っているのは、「１位：リンゴ、２位：バナナ、３位：イチゴ」というランキングと最も近いランキングはこれと全く同じ「１位：リンゴ、２位：バナナ、３位：イチゴ」というランキングになるということです。これは分かりやすいですね。
２つ目の性質は、逆に最も離れているのが「１位：イチゴ、２位：バナナ、３位：リンゴ」という逆順のランキングであるということを言っています。
４つの測定方法
「ランキングの類似度」（順序の距離）を測定する代表的な手法は４つあるそうです。具体的に考えるため、ランキングAとランキングBを次のように仮定して、実際にAとBの距離を測定しながら紹介していきます。
ランキングA：リンゴ＞バナナ＞イチゴ＞オレンジ＞ブドウ
ランキングB：イチゴ＞バナナ＞オレンジ＞ブドウ＞リンゴ
① Spearman's Footrule（スピアマンのフットルール）
2つのランキング間の項目の順位の差の絶対値の総和を計算するという非常に分かりやすい方法。ランキングが全く同じ時に０、逆順を成す時に最大値となり、期待している性質を満たします。
ランキングAとランキングBの場合、「リンゴ」はランキングAでは１位だが、ランキングBでは５位なので順位の差は４です。「バナナ」はランキングAでもランキングBでも２位なので順位の差は０。こうした順位の差を「イチゴ」「オレンジ」「ブドウ」についても同様に考えて合計してやるとランキングAとランキングBの距離が計算できます。以下のとおり、この場合の距離は８と分かります。
$$
4+0+2+1+1=8
$$
② Kendall distance（ケンドール距離）
２つのランキングの中で順序が不一致なものの対の数を数える方法。ランキングが全く同じ時に０、逆順を成す時に最大値となり、期待している性質を満たします。
ランキングAの場合、「リンゴ＞バナナ＞イチゴ＞オレンジ＞ブドウ」という順序は次の10個の順序を含んでいます。
リンゴ＞バナナ
リンゴ＞イチゴ
リンゴ＞オレンジ
リンゴ＞ブドウ
バナナ＞イチゴ
バナナ＞オレンジ
バナナ＞ブドウ
イチゴ＞オレンジ
イチゴ＞ブドウ
オレンジ＞ブドウ
一方、ランキングBの場合は次の10個の順序を含んでいます。
イチゴ＞バナナ
イチゴ＞オレンジ
イチゴ＞ブドウ
イチゴ＞リンゴ
バナナ＞オレンジ
バナナ＞ブドウ
バナナ＞リンゴ
オレンジ＞ブドウ
オレンジ＞リンゴ
ブドウ＞リンゴ
それぞれの含んでいる順序を比較すると、一致しているのは次の５個です。
バナナ＞オレンジ
バナナ＞ブドウ
イチゴ＞オレンジ
イチゴ＞ブドウ
オレンジ＞ブドウ
逆に不一致な対の数は5個あるため、Kendall distanceは5と分かります。
③ Cayley distance（ケイリー距離）
片方のランキングについて２つの要素の位置を交換する作業を繰り返して、もう片方のランキングに一致させることを考えます。この時必要な最小の交換の数がCayley distanceです。ランキングが全く同じ時に０となりますが、逆順を成す時に最大値となるとは限らず、期待している性質とは異なります。
ランキングAの要素を交換していくことで、ランキングBに一致させてみましょう。
【交換０回】
リンゴ＞バナナ＞イチゴ＞オレンジ＞ブドウ
【交換１回】
イチゴ＞バナナ＞リンゴ＞オレンジ＞ブドウ（リンゴとイチゴを交換）
【交換２回】
イチゴ＞バナナ＞オレンジ＞リンゴ＞ブドウ（リンゴとオレンジを交換）
【交換３回】
イチゴ＞バナナ＞オレンジ＞ブドウ＞リンゴ（リンゴとブドウを交換）
→ランキングBに一致！
従ってCayley distanceは３と分かります。
④ Ulam distance（ウラム距離）
片方のランキングについてある要素を、別の場所に挿入する作業を繰り返して、もう片方のランキングに一致させることを考えます。この時必要な最小の交換の数がUlam distanceです。ランキングが全く同じ時に０、逆順を成す時に最大値となり、期待している性質を満たします。
ランキングAに作業してランキングBに一致させてみましょう。
【作業０回】
リンゴ＞バナナ＞イチゴ＞オレンジ＞ブドウ
【作業１回】
イチゴ＞リンゴ＞バナナ＞オレンジ＞ブドウ（イチゴをリンゴの前に挿入）
【作業２回】
イチゴ＞バナナ＞オレンジ＞ブドウ＞リンゴ（リンゴをブドウの後に挿入）
→ランキングBに一致！
従ってUlam distanceは２と分かります。
おまけ
おまけ①：Kendall distanceをExcel VBAで実装する
２列に並んだランキングのKendall distanceを計算するマクロをExcel VBAで実装してみました。ランキングデータが記載されているセルを範囲選択して実行すると、イミディエイトウィンドウにKendall distanceを表示します。
Sub CalculateKendallDistance()
Dim dataRange As Range
Set dataRange = Selection
Dim tmpDic As Object
Set tmpDic = CreateObject("Scripting.Dictionary")
Dim kendallDistance As Long
Dim i, j As Long
For i = 1 To dataRange.Rows.Count - 1
For j = i + 1 To dataRange.Rows.Count
For k = 1 To 2
buf = dataRange.Cells(i, k) & ">" & dataRange.Cells(j, k)
If Not tmpDic.Exists(buf) Then
tmpDic.Add buf, buf
End If
Next k
Next j
Next i
kendallDistance = tmpDic.Count - dataRange.Rows.Count * (dataRange.Rows.Count - 1) / 2
Set tmpDic = Nothing
Debug.Print "Kendall Distance: "; kendallDistance
End Subおまけ②：Rパッケージ
PearMallowsパッケージというパッケージで上記で紹介したKendall, Cayley, Ulamによる距離を求める関数が実装されているそうです。
おまけ③：参考図書
より専門的に勉強する場合は次の図書が詳しいらしいです。
この記事が気に入ったらサポートをしてみませんか？