文系プログラマが数式アレルギーを治す為に、中学〜高校レベルの知識でもわかる数式を、プログラムのコードに直す作業を黙々と続ける企画。
ソースコードはJuliaを利用。徐々に改善はされているけどまだまだPythonに勝てる日は遠いJulia。
今回のテーマはJaccard距離。「あなたにピッタリの異性を紹介します」みたいなサービスでも使えそうなJaccard距離。
式はWikipediaのJaccard indexを参考にした。
https://en.wikipedia.org/wiki/Jaccard_index
Jaccard similarity（類似）の式はこんな感じ。
# 自分用メモ
$ J( A, B ) = \frac { \mid A \cap B \mid } { \mid A \cup B \mid } $
上の式では同一であれば1に、似ていないものであれば0に近づく。
これに対してJaccard距離ということになると、似ているほど0に近くなって欲しいので、1-類似度ということになる。
その式がこんな感じになるらしい。
# 自分用メモ
$ 1 - J( A, B ) = \frac { \mid A \cup B \mid - \mid A \cap B \mid } { \mid A \cup B \mid } $
なんかよくわからないけど、感じ的にbitをandしてorすればいいのかな。
名前はUnionとIntercsection。日本語だと和集合と交差？
1001101101と0101010101という2つの2進数があったとする。この2つの距離を求めてみる。
# 2つの2進数があったとさ
a = parseint("1001101101",2)
b = parseint("0101010101",2)
この2つの単純なAND/ORならこうなる。
sim(x, y) = count_ones(x & y) / count_ones(x | y) sim(a, b ) #=> 0.375
こんな感じでsimilarityが計算された。
distanceを出す場合もやってみる。
dist(x, y) = ( count_ones( x | y ) - count_ones(x & y) ) / count_ones(x | y) dist(a, b) #=> 0.625
ちゃんと 1 - sim(a, b) の値が出た。
上の例はbinary numberをただAND/ORしたけど、普通はSet同士の距離とか測ったりするらしい。
試しに下記3つのSetで距離を取ってみる。
# 奇数のSet odd = Set( 1, 3, 5, 7, 9 ) # 偶数のSet even = Set( 2, 4, 6, 8, 10 ) # 両方混じったSet each = Set( 1, 2, 3, 4, 5 )
当然ながら奇数と偶数では距離が遠い（1）, 奇数と奇偶双方混じったSetでは距離が中間になることになる。
Setにはunion, intersectなどの関数が用意されているけど、Juliaさんなので ∪ と ∩ にもaliasが貼ってある。
というわけで、こんな風に書ける。
dist( x, y ) = (length(x ∪ y) - length(x ∩ y)) / length(x ∪ y) dist( odd, even ) #=> 1.0 dist( odd, each ) #=> 0.5714285714285714 dist( even, each ) #=> 0.75
oddとevenは1に、odd, even, each（eachは奇数の方が多い）では、odd-each間の方が近くなっている。
自前で書いただけだと合ってるかどうか怪しいので、scipy先生で答え合わせする。
from scipy.spatial.distance import jaccard # odd - each距離 jaccard( [ 1, 0, 3, 0, 5, 0, 7, 0, 9 ], [ 1, 2, 3, 4, 5, 0, 0, 0, 0 ] ) #=> 0.5714285714285714 # even - each距離 jaccard( [ 0, 2, 0, 4, 0, 6, 0, 8, 0, 10 ], [ 1, 2, 3, 4, 5, 0, 0, 0, 0, 0 ] ) #=> 0.75
同じ答えになった。