ステージ3-5: 類似度や距離の例 (情報工学実験 3 : データマイニング班)

• 想定環境
• 数学的な「距離(空間)」と「類似度(空間)」に必要な要件
• cosine類似度による特徴ベクトルの類似度
• ユークリッド距離と標準ユークリッド距離
• 参考サイト一覧

想定環境

• OS: Mac OS X 10.8.x (10.7.x以降であれば同じ方法で問題無いはず)
• Python: 2.7.x
• Mercurial: 2.2
• numpy: 1.8.0 (numpy.version)
• scipy: 0.13.0 (scipy.version)

数学的な「距離(空間)」と「類似度(空間)」に必要な要件

• 距離空間 (Wikipedia)
• 距離指数の原理

• 条件1(非負性): func(vec1, vec2) >= 0
• 条件2(対称性): func(vec1, vec2) == func(vec2, vec1)
• 条件3(反射性): func(vec1, vec1) = 0
• 条件4(三角不等式): func(vec1, vec2) + func(vec2, vec3) >= func(vec1, vec3)

  ここまで満たして「擬距離(空間)」。独自に「＊＊距離」を設計して構わないが、数学的に距離と呼ぶなら最低でも上記4条件を満足する必要がある。

• 条件5(非退化性): func(vec1, vec2) = 0 <=> vec1 = vec2

  4条件に加え、厳密な「距離(空間)」を構築するには、距離0となる2点は必ず等しくなる必要がある。（擬距離(空間)では等しくなくても構わない）

• 条件: 「func(vec1, vec2) <= func(vec1, vec1)」となるvec2はvec1のみ。
  言い換えると「最も類似している値となるベクトルは同じベクトル同士」。

  独自に「＊＊類似度」を設計して構わないが、類似度と呼ぶなら上記条件を満足する必要がある。

cosine類似度による特徴ベクトルの類似度

• Cosine similarity

#cosine類似度
def cosine_similarity(vec1, vec2):
    u'''コサイン類似度。
    vec1, vec2 は同次元の特徴ベクトル(リスト型)。
    文章の類似度を測るために使われる指標の一つ。
    vec1とvec2が似ているほど+1に近い値、似ていないほど-1に近い値を返す。
    vec1, vec2のなす角度θに対するcosθを求めるため、以下のような値を返す。
        ・ベクトルの向きが一致している時に最大値1。
        ・直行している時に0。
        ・向きが真逆の時に-1。
    >>> len(vec1) == len(vec2)
    True
    '''
    import math
    numerator = sum([vec1[x]*vec2[x] for x in range(len(vec1))])
    
    sum1 = sum([vec1[x]**2 for x in range(len(vec1))])
    sum2 = sum([vec2[x]**2 for x in range(len(vec2))])
    denominator = math.sqrt(sum1) * math.sqrt(sum2)
    
    if not denominator:
        return 0.0
    else:
        return float(numerator) / denominator

cosine_similarity([1,1,1], [1,1,1]) #同一なので1.0
cosine_similarity([1,1,1], [2,2,2]) #向きは同一なので1.0
cosine_similarity([1,1,1], [0,1,1]) #ほぼ同じ向きなので+1に近い値
cosine_similarity([1,1,1], [0,0,1]) #大分向きが異なるが反対方向ではないためまだ正の値
cosine_similarity([1,1,1], [0,0,0]) #直行しているため0.0
cosine_similarity([1,1,1], [0,0,-1]) #向きが逆方向になったため負の値
cosine_similarity([1,1,1], [0,-1,-1]) #更に向きが逆方向に向いたため-1に近い負の値
cosine_similarity([1,1,1], [-1,-1,-1]) #向きが真逆なので-1.0

#以下で使用している scipy.spatial.distance.pdist() でもコサイン類似度に似た指標
#を算出できるが、pdist('cosine')は「コサイン距離」を求めている点に注意。

ユークリッド距離と標準ユークリッド距離

• Euclidean distance

#ユークリッド距離
import scipy.spatial.distance as dist

# 以下では2ベクトル間の距離を求めるやり方を例示していますが、
# 第1引数にm個の行列を列挙し、まとめて「組み合わせ全ての距離」を求めることができます。

dist.pdist([[1,1,1], [1,1,1]], 'euclidean') #同一なので0.0
dist.pdist([[1,1,1], [1,1,1]]) #同一なので0.0
dist.pdist([[1,1,1], [2,2,2]]) #向きは同じだが大きさが異なるので正の値
dist.pdist([[1,1,1], [0,0,0]]) #上記と同じ距離にあるため同じ値を返す

dist.pdist([[1,1,1], [0,1,1]]) #距離的に近いのでより小さな正の値
dist.pdist([[1,1,1], [0,0,1]]) #上記より少し離れたのでやや大きな正の値
dist.pdist([[1,1,1], [0,0,-1]]) #更に離れた正の値
dist.pdist([[1,1,1], [0,-1,-1]]) #更に離れた正の値
dist.pdist([[1,1,1], [-1,-1,-1]]) #更に離れた正の値

dist.pdist([[1,1,1], [1,1,1000]]) #一部の属性に引きずられた値


#標準ユークリッド距離
# 一部の素性が他と比べて非常に大きいとき、その一部の素性に引きずられた距離となるのを防ぐため、
# ユークリッド距離を分散でならした（割った）値を求める。
# *デフォルトではベクトル間の分散を求めて割るため、
#  同一値となる素性が1カ所でもあると NaN (不定) になってしまう。
dist.pdist([[1,1,1], [1,1,1]], 'seuclidean') #同一だらけで NaN
dist.pdist([[1,1,1], [0,0,1]], 'seuclidean') #3番目の素性が同一のためNaN
dist.pdist([[1,1,1], [2,2,2]], 'seuclidean') #ただのユークリッド距離よりも大きな値を返す。
dist.pdist([[1,1,1], [-1,-1,-1]], 'seuclidean') #ユークリッド距離的には上記より離れているはずだが、同一距離となる。
dist.pdist([[1,1,1], [0,0,1000]], 'seuclidean') #ユークリッド距離的にかなり離れているが、同一距離。

参考サイト一覧

• 類似度と距離
• 距離空間 (Wikipedia)
• 距離指数の原理
• scipy.spatial.distance.pdist()
• Encyclopedia of Distances (Springer)