新規
編集
添付
一覧
最終更新
差分
バックアップ
凍結
複製
名前変更
ヘルプ２つのデータが似ている度合いを，類似度の大きさや距離の近さといった数値にしてあらわすことで，クラスタ分析や，k-近傍法，多次元尺度構成法(MDS)をはじめとするいろいろな分析を行うことが可能となる．
ここでは，よく知られている類似度や距離について述べる．
類似度という概念は，２つの集合の要素がまさにどれだけ似ているかを数量化したものであり，距離とは，要素同士の離れ具合，従って非類似度とちかい概念と考えてもよい．
参考までに数学における距離の概念の定義を示すと，
距離空間の定義 Sを１つの空でない集合とし，dをSで定義された2変数の実数値関数 d(SxS) → R が，以下の４条件（距離の公理） D1 ： （非負性） 任意のx,y∈Sに対して d(x,y)≧0． D2 ： （非退化性） x,y∈Sに対し d(x,y)=0 ⇔ x=y． D3 ： （対称性） 任意のx,y∈Sに対して d(x,y)=d(y,x)． D4 ： （三角不等式） 任意のx,y,z∈Sに対して d(x,y)+d(y,z)≧d(x,z)． を満たすとき，dをS上の距離関数(metric)といい，概念(S,d)を距離空間という．
この距離の公理は，実世界での自然な距離の概念によく整合しているが，実際にデータ分析で使われる距離や類似度の中には，負の値をもつ類似度や，非対称な距離といったものもある．
n次元ベクトルの距離 
距離をはかる対象要素x,yを，n次元の行ベクトル
x=(x1,x2,..,xn) y=(y1,y2,..,yn)
とし，n次元空間での距離を考える．なお，記号として以下のものを使う．
t(x)=転置行列 inv(x)=逆行列 x*y=スカラー積または行列の積 x・y=ベクトルの内積 =Σxi*yi |x|=ベクトルの長さ（ノルム）= sqrt(x・x)
- ユークリッド距離
n次元ユークリッド空間上でのベクトルx,yであらわされる２点の幾何学的な直線距離であるユークリッド距離dは，もっともなじみのある距離であり，d=sqrt((x1-y1)**2 + (x2-y2)**2 + .. + (xn-yn)**2) = sqrt( (x-y) * t(x-y) ) t()は，行列の転置
であらわされる．
- 標準ユークリッド距離
ユークリッド距離は，実世界の３次元空間のアナロジーであるので，どの方向についても距離は均質と考えられた．しかし，データ分析の場合，ある項目，すなわちある次元のデータは，他の次元のデータに比べて取りうる値が非常に大きいときがある．その場合，距離の違いは，ほぼその次元の違いになってしまい，他の次元のデータの差異が距離にほとんど反映されなくなる．そこで，各次元をその次元の取りうる値の標準偏差で割り，値の分散を標準化した上でのユークリッド距離を標準ユークリッド距離という．d=sqrt(((x1-y1)/std1)**2 + ((x2-y2)/std2)**2 + .. + ((xn-yn)/stdn)**2) =sqrt( (x-y) * inv(v) * t(x-y) ) where stdnは，第n次元の標準偏差，vは，各次元の分散を対角成分にもつ行列，inv()は逆行列
であらわされる．
- マハラノビス距離
さらに，ある次元と別の次元の取りうる値に相関がある場合，相関のある方向に対して平行にデータが散らばりやすいのだから，ユークリッド距離や標準ユークリッド距離だと，その方向の差異が距離を大きく支配してしまう．このような場合，相関のある方向に平行な距離を相対的に短く，相関のある方向に垂直な距離を相対的に長くしたマハラノビス距離のほうが理に適っている．d=sqrt( (x-y) * inv(cov) * t(x-y) ) where covは，分散共分散行列
であらわされる．
共分散=0とすれば，標準ユークリッド距離に，さらに，分散＝１とすれば，ユークリッド距離に一致する．
- マンハッタン距離
２点を直線で結ぶのではなく，各時点では，必ず１つの次元の移動だけを許した移動距離であらわしたものをマンハッタン距離という．ニューヨークのマンハッタン島のようなマス目状の路上を縦横にタクシーで移動する場合の距離を概念化したものである．d=|x1-y1| + |x2-y2| + .. + |xn-yn|．
であらわされる．
- チェビシェフ距離
マス目状の路上において，縦に１ブロック移動するのも，横に１ブロック移動するのも，斜め対角線上に１ブロック移動するのも，いずれも同じ１単位分の移動であると考えた場合の距離である．この場合，各次元毎の差異のもっとも大きいものがチェビシェフ距離の値となる．d=max(|x1-y1| , |x2-y2| , .. , |xn-yn|)．
であらわされる．
- ミンコフスキー距離
ユークリッド距離が，各次元の差の平方和の平方根であったが，それをある種の一般化として，a乗和のb乗根としたのが，ミンコフスキー距離である．なお，a=bとして扱う定義もある．aが大きいほど，次元軸にとらわれない移動（斜め方向のショートカット）を重視する距離である．d=( |x1-y1|**a + |x2-y2|**a + .. + |xn-yn|**a )**(1/b)．
であらわされる．
a=b=1がマンハッタン距離に，a=b=2がユークリッド距離に，a=b=∞がチェビシェフ距離に一致する．
n次元ベクトルの類似度
今度はn次元空間での類似度について述べる．
- コサイン類似度
ベクトルx,yのなす角θの余弦cosθをコサイン類似度といい，ベクトルの向きの近さを類似性の指標としたものである．ベクトルの向きが一致している時，最大値の１をとり，直交ならば0，向きが逆ならば最小値の-1をとる．sim= x・y /(|x|*|y|) x・y=ベクトルx,yの内積 =(x1*y1 + x2*y2 + .. + xn*yn) |x|=ベクトルxの長さ（ノルム）= sqrt(x・x) =原点からベクトルxの終点までのユークリッド距離 =sqrt((x1-0)**2 + (x2-0)**2 + .. + (xn-0)**2) = sqrt( (x-0) * t(x-0) )
であらわされる．
- ピアソンの相関係数
２つの確率変数の相関関係をあらわすピアソンの相関係数も，類似度の尺度として使うことができる．xとyを２つの変数と考え，次元ごとの値の組(xi,yi) (i=1,2,..,n) の相関係数として算出する．1が，完全に一致，0が無相関，-1が，完全に不一致となる．
ベクトルxの次元要素xi (i=1,2,..,n)の平均をmxとし，ベクトルv=x-mx = (x1-mx, x2-mx, .., xn-mx)とおく．
同様にベクトルyに対して，w=y-my=(y1-my, y2-my, .., yn-my)とおくと，sim=vとwのコサイン類似度 =v・w /(|v|*|w|)
であらわされる．
- 偏差パターン類似度
ピアソンの相関係数では，各ベクトルの次元要素の値の平均からの偏差ベクトルを考えたが，偏差パターン類似度では，全ベクトルの平均ベクトルからの偏差ベクトルを使う．第i次元要素xi の平均をmiとし平均ベクトルをm=(m1,m2,..,mn)とする．
x,yの偏差ベクトルをv=x-m = (x1-m1, x2-m2, .., xn-mn)，w=y-m=(y1-m1, y2-m2, .., yn-m3)とするとsim=vとwのコサイン類似度 =v・w /(|v|*|w|)
であらわされる．
集合の類似度
次に示す３つの類似性指標は，もともと２つの集合の要素の一致度を示すものであるが，コサイン類似度に似た定義式をもっており，ある種のベクトルの類似度としても使うことができる．
- ジャッカード係数
集合XとYの共通要素数を少なくとも１方にある要素の総数で割ったものsim=|X∩Y|/|X∪Y|
を，ジャッカード係数という．
今，X∪Yの要素をz1,z2,..,znとして，ベクトルx=(x1,x2,..,xn)を，xi=1 (if zi∈X), xi=0 (otherwise)として定める．
ベクトルyも同様に定めると，ジャッカード係数は，sim= x・y /(Σxi+Σyi-x*y)
とあらわされる．
- ダイス係数
集合XとYの共通要素数を各集合の要素数の平均で割ったものsim=2*|X∩Y|/(|X|＋|Y|)
を，ダイス係数という．
X,Yに対応するベクトルx,yを使えば，sim= 2*x・y /(Σxi+Σyi)
とあらわされる．
- シンプソン係数
集合XとYの共通要素数を各集合の要素数の最小値で割ったものsim=|X∩Y|/min(|X|, |Y|)
を，シンプソン係数という．
X,Yに対応するベクトルx,yを使えば，sim= x・y /min(Σxi, Σyi)
とあらわされる．
文字列の距離
２つの文字列の非類似度をあらわすハミング距離，編集距離について述べる.
- ハミング距離
２つの文字列の同じ位置の文字の不一致数をハミング距離という．
たとえば，01010 と 01111では，3番目と5番目の2箇所が異なるので，ハミング距離は２となる．
この場合，ベクトル(0,1,0,1,0）と(0,1,1,1,1）のマンハッタン距離と同じになる．
なお，文字は３種類以上でもかまわない．
- 編集距離
ハミング距離は．原則として同じ長さの文字列の距離であったが，異なる長さの文字列に対しては，文字の挿入や削除の操作もひとつの間隔とした編集距離が用いられる．
レーベンシュタイン編集距離は，一方の文字列を他方の文字列に変換するのに必要となる，文字の置換，文字の挿入，文字の削除の3種類の操作の最小回数としてあらわされる．
たとえば，special→speciral（挿入)→speiral（削除)→spiral（削除) であるから，specialとspiralのレーベンシュタイン編集距離は，3である．さらに，操作ごとに対応する重みを変えたり，操作の種類（たとえば，同じ文字の並びを１文字に置き換える，前後の文字を入れ替えるなど）を増やすなどのバリエーションが存在する．
see also関数・コールルーチンのspedis関数,compged関数,complev関数
外部情報を使った距離
最後に，近さの関係を示す情報が，外部情報として与えられる場合について述べる．
- グラフ距離
要素を頂点としたグラフが与えられており，２頂点間の距離を，その２頂点をつなぐ最短のグラフの辺の数として表現する．これは，要素の隣接関係をグラフとして外部から規定しているわけで，空間内にグラフが位相として入っていると考えればよい．マンハッタン距離も，縦横の道路（アベニューとストリート）をグラフと考えればグラフ距離とも考えられる．
２つほど例をあげると
1) 人（頂点）同士を家系図（グラフ）で血縁の距離ではかる（親等数）．
2) 単語（頂点）の距離を，ワードネットのような言語概念のつながりを記述した意味辞書（グラフ）上での距離としてはかる．
がある．
基本的には，１つの辺を１つの間隔の単位として数え上げるが，各辺に固有の重みや向きを与えることもできる．
計算例
*********************************************************
similarity.sas
081019 翔
*********************************************************;
options nocenter;
data similarity;
/*計算例用のベクトルデータx,y*/
array x(3) x1-x3 (2 3 1);
array y(3) y1-y3 (4 6 1);
**********************************
ユークリッド距離
**********************************;
euclid=((x1-y1)**2 + (x2-y2)**2 + (x3-y3)**2)**0.5;
put euclid=; /*euclid=3.6055512755*/
**********************************
標準ユークリッド距離
**********************************;
std1=2;/*第1要素の標準偏差*/
std2=1;/*第2要素の標準偏差*/
std3=1;/*第3要素の標準偏差*/
stdeuclid=(((x1-y1)/std1)**2 + ((x2-y2)/std2)**2 + ((x3-y3)/std3)**2)**0.5;
put stdeuclid=; /*stdeuclid=3.1622776602*/
**********************************
マハラノビス距離
**********************************;
r=0.5;/*第1,第2要素間の相関*/
/* 分散共分散行列Covを
{ 1 r 0,
Cov= r 1 0,
0 0 1 }
とすると逆行列を求めて，．．
*/
inv11=1/(1-r**2);
inv12=-r/(1-r**2);
inv21=-r/(1-r**2);
inv22=1/(1-r**2);
mahalanobis
=( inv11*(x1-y1)**2
+ inv12*(x1-y1)*(x2-y2)
+ inv21*(x2-y2)*(x1-y1)
+ inv22*(x2-y2) **2
+ (x3-y3)**2
)**0.5;
put mahalanobis=; /*mahalanobis=3.0550504633*/
/*
上では少々無理をして，datastepの四則演算で例示したが，
行列演算を使えば，次のように簡単に書ける．
proc iml;
x={2 3 1};
y={4 6 1};
cov={ 1 0.5 0,
0.5 1 0,
0 0 1};
mahalanobis=sqrt((x-y)*inv(cov)*t(x-y));
print mahalanobis;
run;
なお，マハラノビス距離の分散共分散行列が，単位行列であれば，ユークリッド距
離に一致し，
対角行列（相関がない）であれば，標準ユークリッド距離に一致する．
*/
**********************************
マンハッタン距離
**********************************;
manhattan=abs(x1-y1) + abs(x2-y2) + abs(x3-y3);
put manhattan=; /*manhattan=5*/
**********************************
チェビシェフ距離
**********************************;
chebyshev=max(abs(x1-y1) , abs(x2-y2) , abs(x3-y3));
put chebyshev=; /*chebyshev=3*/
**********************************
ミンコフスキー距離
**********************************;
a=2;b=2;
minkowski=(abs(x1-y1)**a + abs(x2-y2)**a + abs(x3-y3)**a)**(1/b);
put minkowski=; /*minkowski=3.6055512755*/
**********************************
コサイン類似度
**********************************;
cos=(x1*y1+x2*y2+x3*y3)
/ (sqrt(x1**2+x2**2+x3**2)*sqrt(y1**2+y2**2+y3**2));
put cos=; /*cos=0.9912011826*/
**********************************
ピアソンの相関係数
**********************************;
mx=mean(of x1-x3);my=mean(of y1-y3);
v1=x1-mx;v2=x2-mx;v3=x3-mx;
w1=y1-my;w2=y2-my;w3=y3-my;
r=(v1*w1+v2*w2+v3*w3)
/ (sqrt(v1**2+v2**2+v3**2)*sqrt(w1**2+w2**2+w3**2));
put r=; /*r=0.9933992678*/
**********************************
偏差パターン類似度
**********************************;
m1=1;m2=2;m3=1;
v1=x1-m1;v2=x2-m2;v3=x3-m3;
w1=y1-m1;w2=y2-m2;w3=y3-m3;
cosd=(v1*w1+v2*w2+v3*w3)
/ (sqrt(v1**2+v2**2+v3**2)*sqrt(w1**2+w2**2+w3**2));
put cosd=; /*cosd=0.9899494937*/
**********************************
ジャッカード係数
**********************************;
jaccard=(x1*y1+x2*y2+x3*y3)/(sum(of x1-x3) + sum(of y1-y3) - (x1*y1+x2*y2+x3*y3));
put jaccard=; /*jaccard=-2.7*/
**********************************
ダイス係数
**********************************;
dice=(x1*y1+x2*y2+x3*y3)/(sum(of x1-x3) + sum(of y1-y3))*2;
put dice=; /*dice=3.1764705882*/
**********************************
シンプソン係数
**********************************;
simpson=(x1*y1+x2*y2+x3*y3)/min(sum(of x1-x3),sum(of y1-y3));
put simpson=; /*simpson=4.5*/
**********************************
ハミング距離
**********************************;
hamming=(x1 ne y1) + (x2 ne y2) + (x3 ne y3);
put hamming=; /*hamming=2*/
**********************************
編集距離
**********************************;
spedis=spedis("special","spiral"); /* 編集距離（非対称）*/
put spedis=; /*spedis=35*/
compged=compged("special","spiral"); /*一般化編集距離*/
put compged=; /*compged=300*/
complev=complev("special","spiral"); /*レーベンシュタイン編集距離*/
put complev=; /*complev=3*/
run;集合の類似性指標についての補足
- 集合の特性ベクトル
集合同士の類似性を測るために，集合をベクトル化してその距離や類似度をはかることはよく行われる．
今，有限な全体集合Sの部分集合X,Yの距離（または類似度）を考える．Sの要素の数をnとし，S={s1,s2,...,sn}とする．部分集合Xの特性ベクトルx=(x1,x2,...,xn)を
xi=1 (if si∈X)
xi=0 (otherwise)
と定めると，集合X,Yに対応する特性ベクトルx,yの類似性指標を使って，集合X,Yの類似性をあらわすことができる．
たとえば，X={s2,s4,s5,s8},Y={s1,s2,s5}ならば，x=(0,1,0,1,1,0,0,1,0,...,0)，y=(1,1,0,0,1,0,...,0)で，このコサイン類似度は，cos=x・y/(|x||y|)=2/(2*sqrt(3))=1/√3 となる． - よく使われる類似性指標
上にあげた距離や類似度は，編集距離とグラフ距離を除くと，いずれも，n次元ベクトルに対して形式的な計算は可能である．しかし集合間の類似性を，「共通要素が多く非共通要素が少ない」という観点でとらえるならば，適した指標はいくつかに限られる．まず，ユークリッド距離に代表されるn次元空間上でのベクトル間の幾何学的距離をあらわす指標については，次の式からわかるように，集合X,Yの要素数が２倍になると，共通要素の比率が同じでも，距離を２倍にしてしまうので適切ではない．euclid**2= (x-y) * t(x-y) = |x|**2 + |y|**2 -2x・y
標準ユークリッド距離，マハラノビス距離，マンハッタン距離，チェビシェフ距離，ミンコフスキー距離についても同様な問題がある．
ピアソンの相関係数や偏差パターン類似度も，属する，属さないを意味するベクトルの0,1の値が，壊れてしまい，期待する指標にはならない．
また，ハミング距離については，非共通要素のみを数える事になるので，共通要素の大きさを反映できず集合の類似性指標には適さない．
残るコサイン類似度，ジャッカード係数，ダイス係数，シンプソン係数は，集合の類似性指標として使える．これらは，いずれも分子は共通で，分母のとり方に特徴がある．
なお，ベクトルx,yを単位ベクトル化 x/|x|, y/|y|したユークリッド距離dは，コサイン類似度cosに対して，d=√(2-2*cos)
という単調な関係があり，これも類似性指標として使う事ができる． - 重み付き特性ベクトル
先に述べた特性ベクトルは，要素が属する，属さないを意味する0,1からなるベクトルであったが，1ではなく，帰属度，重要度などで重み付けしたベクトルを扱うこともできる．コサイン類似度などの分子がベクトルの内積になっている指標は，ベクトルのなす角で類似度をはかるため，重みが比例関係にあるものは，大きさによらず，同じ類似度になることに留意すること．すなわち，ベクトル(w1,w2)に対して，(v1,v2)と(k*v1,k*v2)の類似度は，同じである． - スパースなベクトルの処理
言語情報の集合を扱う場合などにおいては，全体集合Sが数万語以上からなる単語の集合となり，個々の集合Xの特性ベクトルは，数万次元からなるほとんどが0のスパースなベクトルとなることが多い．（スパースとは「疎」，ほとんどが値の入っていない情報格納領域のことをいう）
このような場合，実際に数万次元を記憶域に確保する必要はなく，連想配列（ハッシュ）に属する要素名と重みを記録すればよい．x=(s2:w2,s4:w4,s5:w5,s8,w8) y=(s1:v1,s2:v2,s5:v5)
また，コサイン類似度などを,計算する場合も，全次元の要素から内積を計算する必要はなく，両方のベクトルに存在する要素のみを取り出して積和をもとめればよい．片方しかないまたは両方にない次元の要素の積は，０になってしまうからである．
関連事項
- 関数・コールルーチンspedis関数,compged関数,complev関数
- DISTANCEプロシジャ
- CLUSTERプロシジャ?
- FASCLUSプロシジャ?
- MDSプロシジャ?
- CORRESPプロシジャ?
- CORRプロシジャ?
