« 読了：Wright & Ziegler (2017) ランダム・フォレストのRパッケージranger | メイン | 覚え書き：教師あり学習モデルの評価方法 »
2018年5月 1日 (火)
Choi, S.S., Cha, S.H., Tappert, C.C. (2010) A survey of binary similarity and distance measures. Journal of Systemics, Cybernetics and Informatics, 8(1), 43-48.
6頁の短い論文。掲載誌についてはよくわからない。
何の気になしに印刷し、帰宅する電車で眺めていたらこれが妙に面白く、図を「へぇぇぇ...」と感心して眺めていたら乗り過ごしてしまった。仕方がないので次の駅で降り、駅前の深夜スーパーでうろうろして安売りのワインを買った。
どういう話かというと、長さが等しいふたつの二値ベクトルの類似性を測ることがありますわね。値が一致する個数を調べるとか、値が異なる個数を調べるとか。そういうときに使う指標が山のようにある。そこで、どの指標とどの指標が似ているかというデンドログラムを作りましたという話である。類似性指標の類似性を調べているわけです。
要するに、なんらかのランダムデータを使って、二値ベクトル間の類似性をいろんなやり方で測ったところ、いつも似た値になる指標とそうでない指標があった、これをデンドログラムで表現しました、と。
面白いのは、検討する類似性指標のコレクションである。集めも集め、実に76種類もの指標について調べている。各指標の発表年表もついていたりして、眺めているだけで飽きない。いやあ、いろんな指標があるものだ...
著者らはデンドログラムに基づき、いくつかの指標のグループを指摘しているので、メモしておく。以下、2x2のクロス表について、両方presenceを$a$, 両方absenceを$d$, 片方だけpresenceを$b, c$とする。合計を$n=a+b+c+d$とする。
- Pearsonのファイ係数$(ad-bc)/((a+b)(a+c)(c+d)(b+d))$、ハミング距離$b+c$、Hamannの類似性指標$((a+d)-(b+c))/n$など。ネガティブマッチ($d$)を含むタイプの指標群である。これが最大勢力。
- Lance&Williams距離$(b+c)/(2a+b+c)$、Jaccard類似性$a/(a+b+c)$、コサイン類似性$a/\sqrt{(a+b)(a+c)}$など。ネガティブマッチ($d$)を除外するタイプの指標が多い。
- 内積$a+d$とその仲間たち。Russel&Rao類似性$a/n$もここに入る。
- カイ二乗類似性$n(ad-bc)^2/((a+b)(a+c)(c+d)(b+d))$とその仲間たち。
- Goodman&Kruskal類似性(メンドクサイので式は省略)など、確率的な類似性。
ほかにも一匹狼的な指標がある。Yuleのw $(\sqrt{ad}-\sqrt{bc})/(\sqrt{ad}+\sqrt{bc})$ とか。
... いやー、週末にできちゃうような実験だけど(すいません)、面白かった。
一番面白かったのは指標の年表である。Jaccard類似性は1901年発表だが、これより古い(つまり19世紀の)指標として、二値ユークリッド距離、Peirceの類似性$(ab+bc)/(ab+2bc+cd)$、Yuleの類似性(YuleのQ$(ad-bc)/(ad+bc)$のことかな？)が挙げられるのだそうだ。ハミング距離なんていったらえらく古めかしい印象があるけど(情報理論っていうんでしょうか？)、発表は1950年、統計学の長い歴史の中では中堅どころに過ぎないのであった。恐れ入りました。
仕事に役立つ学びは、というと...正直あんまりないけれど、ネガティブ・マッチを抜くか抜かないかというのが重要な対立軸なのね、というのが勉強になった点である。
いちおうメモしておくけど、この論文、細かい点は良くわからないことが多くて...
76個の指標をよく見ると、定義が全く同じ奴が散見されるんだけど、これはどういうことなんだろうか。
実験手続きもよくわからない。該当箇所を逐語訳すると「ランダムな二値データセットをデータセットとして用いる。参照セットは30個の二値事例からなり、それぞれが100の二値特徴を持つ。この参照セットを使った一回のテスト・クエリで、距離ないし類似性の値が100個、それぞれの指標について生成される。2つの指標の間の相関係数を使ってデンドログラムを作る」「30回の独立な試行を平均してデンドログラムを作る」とのこと。どういうこと？ 長さ100のランダム二値特徴ベクトルを1本作り、それとは別に100本作り、1本と100本の類似性をk種類の指標で測り、100行k列の行列からk行k列の相関行列をつくり、以上を30回繰り返して平均し、できあがったk行k列の相関行列を使ってk種類の指標を階層クラスタリングした、ってこと？ というか、ランダム二値データって母比率はなんなの？ ま、細けぇこたぁいいんだよ、って気もするけど。
論文：データ解析(2018-) - 読了：Choi, Cha, & Tappert (2010) 二値類似性指標はたくさんあるので、その類似性を調べてみた