Distance Measures

 jaccard distance

: 1- jaccard similarity

 

Euclidean Distance

L2 norm

• 유클리드 거리: 대각선으로도 이동가능한 최단거리
  (피타고라스 공식 사용)

L1 norm

• 맨해튼 거리: 대각선으로 이동불가한 최단거리

 

 

Non-Euclidean Distance

Edit Distance

: 한 문자를 다른 문자로 변형하는데 삽입하거나 삭제해야 하는 문자의 개수

 

d(x, y) = |x| + |y| - 2|LCS(x, y)|

* LCS: 두 문자가 공통으로 가지는 가장 긴  sub문자열

 

예) x=abcde, y=bcduve

x를 y로 바꾸려면 a를 삭제하고, d와 e사이에 u, v를 삽입해야 함

-> Edit distance=3

이걸 식으로 계산해 보면, LCS(x, y)=bcde=4

-> d(x, y) = |x| + |y| - 2|LCS(x, y)|

               = 5 + 6 - 2*4

               = 3

 

만약 x=ab, y=ba라면 

LCS를 a로 봐도 되고, b로 봐도 된다.