Distance Measures

해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.

이번 포스팅에서는 데이터의 거리 라는 개념에 대해 다룹니다.

데이터 관점에서는 유사한 정도를 거리로 표현합니다. 유사한 데이터끼리는 가까운 거리에 있고, 데이터 간 차이가 많을수록 긴 거리를 갖습니다.

이전 LSH 포스팅에서는 집합 간 유사도를 파악하기 위해 Jaccard Similarity 를 사용했습니다.

이를 거리라고 하진 않지만 ‘$d(x,y)= 1 - SIM(x,y)$’ 형식으로 정의하여 거리 개념을 도입할 수 있습니다.

거리라는 개념은 여러 관점으로 해석될 수 있고, 이 관점과 데이터의 형태에 따라 여러가지 거리 측도(=Distance measure)가 제시되었습니다.

여기서는 거리 측도의 정의에 대해 이야기하고,

이 정의에 부합하는 여러가지 거리측도에 대해 다룹니다.

Definition of a Distance Measure

점(point)들의 집합(set) 인 공간(=space) 이 있습니다.

그리고 이 공간안에서 하나의 함수 d(x,y) 를 정의합니다.

이 함수는 공간안의 임의의 점 2개 x,y 를 인자로 받고,

실수(real number)를 출력합니다.

이 함수가 다음의 공리들을 만족하면 거리 측도(Distance Measure) 라고 합니다.

1. $d(x,y) \geq 0$ (non-negative)
2. $d(x,y) = 0$ if and only if $x = y$
3. $d(x,y) = d(y,x)$ (symmetric)
4. $d(x,y)\leq d(x,z)+d(z,y) $ (triangle inequality)

직관적으로 보았을 때 우리가 생각하는 거리의 개념과 일치할 것입니다.

4번의 삼각부등식 같은 경우, ‘거리란 한점에서 다른 점으로의 최단 경로의 길이이다’ 라고 이해할 수 있습니다.

이제 여러 거리측도에 대해 설명하고, 위의 공리를 만족하는지에 대해 살펴보겠습니다.

Euclidean Distances

유클리드 거리(Euclidean Distance) 은 사람들이 일반적으로 생각하는 개념입니다.

n 차원의 유클리드 공간에서, n개의 실수들로 구성된 벡터를 입력받아 실수를 출력해 줍니다.

\[d([x_1,x_2,\dots,x_n],[y_1,y_2,\dots,y_n] = \begin{equation} \sqrt{\sum_{i=1}^{n}(x_i-y_i)^2} \end{equation})\]

각 차원에서의 차이를 제곱하고, 모든 차원에서의 차이 제곱값을 더한다음 루트를 씌웁니다.

여기서 제곱($^2$) 을 사용하기 때문에 $L_r$-norm 이라고도 불립니다.

공리를 만족하는지 확인해 봅시다.

1. 실수의 제곱은 음수가 아니기 때문에, $x_i \neq y_i$ 인 어떤 $i$ 도 양수 항이 나옵니다. 이 항들의 합의(양의) 제곱근이고, 두 점 사이의 거리는 음수가 될 수 없습니다.
2. $x_i = y_i$ 인 모든 $i$ 인 경우에 거리는 0 이 됩니다.
3. $(x_i - y_i)^2 = (y_i - x_i)^2$ 이므로 성립합니다.
4. 유클리드 공간의 속성을 생각해보면, 삼각형의 두변의 길이의 합은 나머지 한 변의 길이보다 크고, 직선이 될 때 같습니다.

유클리드 거리는 $L_2$-norm 외 에도 상수 r 을 조정해 $L_r$-norm 을 정의할 수 있습니다.

\[d([x_1,x_2,\dots,x_n],[y_1,y_2,\dots,y_n] = (\sum_{i=1}^{n}|x_i-y_i|^r)^{1/r}\]

$L_r$-norm 중에 대표적인 것은

$L_1$-norm, 인 Manhattan distance 가 있습니다.

여기서 두 점 사이의 거리는, 각 차원에서의 magnitude 의 합입니다.

이것이 Manhattan distance 라 불리는 이유는 실제 맨허튼의 거리 처럼

점 사이를 이동할 때 그리드를 따라가야 하는 특징을 갖고 있기 때문입니다.

이 외에도 $L_\infty$-norm 도 잘 사용됩니다.

r 이 커질 수록 두 점에서 각 벡터의 차이 중 가장 큰 차원에서의 차이만 중요해지게 됩니다.

즉, 전체 차원 중 $

x_i-y_i

$ 가 최대인 i 에 대해 정의 됩니다.

$max(

x_1-y_1

,\cdots,

x_n-y_n

)$ 으로 볼 수 잇습니다.

example

2차원 유클리드 공간에서 두 점 x =(2,7), y =(6,4) 인 경우

$L_1$-norm

\[|2-6| + |7-4| = 4+3 = 7\]

$L_2$-norm

\[\sqrt{(2-6)^2 + (7-4)^2 } = \sqrt{4^2 + 3^2} = 5\]

$L_\infty$-norm

\[max(|2-6|,|7-4|) = max(4,3) = 4)\]

Jaccard Distance

자카드 거리를 1 - sim(x,y) 로 정의했습니다.

이 함수가 거리측도인지 확인을 해봅시다.

1. d(x,y) 는 음수가 될 수 없습니다. intersection의 크기는 union을 넘길 수 없습니다.

2. d(x,y) = 0 이면 x=y 입니다. $x\cup x = x \cap x = x$ 이기 때문입니다. 그러나 $x\neq y$ 이면 $x\cap y$ 는 무조건 $x\cup y$ 보다 작아야합니다. 그래서 d(x,y)는 확실히 양수 입니다.

3. d(x,y) = d(y,x), $x\cup y = y \cup x$ , $x\cap y = y \cap x$ 입니다.

4. 자카드 유사도 SIM(x,y) 는 minhash 함수의 x, y 의 값이 같은 값일 확률입니다. 그러므로 자카드 거리 d(x,y) 는 minhash 함수의 x, y 의 값이 같지 않을 확률입니다. $d(x,y)\leq d(x,z)+d(z,y) $ 는 무작위 minhash 함수 h 가 있을 때, $h(x)\neq h(y)$ 가 $h(x)\neq h(z)$ 와 $h(y)\neq h(z)$ 의 합보다 크지 않을 확률이 됩니다.

   확률보다는 경우의 수로 생각하면 이해가 좀 더 쉽습니다. 여기서 $h(x)\neq h(z)$ 인 경우와 $h(y)\neq h(z)$ 인 경우의 합은 $h(x)\neq h(y)$ 인 경우보다 많고, x=y 일 때만 경우의 수가 동일합니다.

Cosine Distance

Cosine distance 는 그 점들이 만드는 벡터의 각도입니다.

이 각도는 0부터 180도가 될 수 있습니다.

첫번째 각의 cosine 을 계산하고 0부터 180 범위 안에 있는 각으로 변환하기 위해 arccos을 적용합니다.

두개의 백터 x,y 가 주어진다면, 그것들 사이의 cosine 은 x 와 y의 내적에 $L_2$-norm 으로 나눈 값 입니다.

$d(x,y) = 1 - \frac{\Sigma x_iy_i}{

x

_{2}

y

_2}$

example

x= [1,2,-1] y=[2,1,1] 일때

내적은 $1\times 2 + 2 \times 1 + (-1) \times 1 = 3$ 이고,

L2는 x,y 둘다 $\sqrt{6}$ 입니다.

x,y 사이 각의 cosine 은 $\frac{1}{2}$ 이되고,

cosine이 $\frac{1}{2}$ 인 각은 60도 입니다.

그리고 이 60이 x,y 사이의 코사인 거리입니다.

코사인 거리가 거리 측도인지를 확인해봅시다.

1. 코사인 거리 값은 0에서 180으로 정의를 했습니다. 그래서 음수값이 불가능합니다.
2. 두개의 백터 사이 각이 0 이면 필요충분조건으로 같은 방향을 갖습니다.
3. x,y 사이 각은 y,x 사이 각 입니다.
4. x에서 y로 회전하는 방법은 z로 회전하고나서 y로 회전하는 방법이 있습니다. 이 두 회전의 합은 x에서 y로 바로 회전하는 것보다 작을 수 없습니다.

Edit Distance

Edit Distance는 점이 문자열일 때 적합합니다.

두 문자열 $X=x1x2\dots$ $Y = y1y2\dots$ 사이의 거리는

문자열 X를 Y로 바꾸기 위해 문자를 삽입 및 삭제 하는 최소 횟수 입니다.

예시를 먼저 살펴보겠습니다.

example

x= abcde 이고 y = acfdeg 일 때

x에서 y로 변환하는 edit distance 는 3입니다.

다음과 같은 작업이 필요합니다.

1. b를 지운다
2. c 뒤에 f 를 삽입한다.
3. e 뒤에 g 를 삽입한다.

작업을 더 줄일 수 없으므로 d(x,y)= 3 입니다.

이 edit distance를 정의, 계산하는 다른 방식은 LSC(=longest common subsequence)를 계산하는 것입니다.

x와 y에서 특정 문자를 삭제하여 만든 공통된 문자열은 LCS이며

이는 x에서 y로 바꾸는 데 수행할 작업의 수를 줄입니다. (작업할 필요가 없는 문자열)

그래서 edit distance d(x,y)는 x의 길이 더하기 y길이에서 LCS 의 길이의 2배를 뺀 값으로 계산할 수 있습니다.

x=aba, y =bab 인 경우, LCS = ab 혹은 ba 가 되고

각 문자열의 길이

x

= 3,

y

=3,

LCS(X,Y)

= 2 이므로

Edit distance 는 $3+3 -(2\times2) =2$ 가 됩니다.

edit distance가 거리측도인지 확인을 해봅시다.

1. 횟수를 계산하는 것이기 때문에 음수가 될 수 없습니다.
2. 두 문자열이 같은 경우 0 이 됩니다
3. 문자열을 바꿔도 삽입과 삭제의 순서를 반대로 수행하면 동일하게 만들어 집니다.
4. 문자열 s 가 문자열 t 로 바뀌는 방법은 s가 u 로 된 다음 u에서 t 가되는 방법이 있습니다. s 에서 u 로 갈 때 수정의 횟수와 u에서 t로 가는 수정의 횟수는 s서 t로 수정하는 가장 작은 수보다 작을 수 없습니다.

Hamming Distance

벡터들의 공간이 주어졌을 때 해밍 거리를 정의 할 수 있습니다.

해밍 거리는 두 벡터의 차이가 있는 컴포넌트의 수로 정의합니다.

example

10101 과 11110 의 거리는 3 입니다.

여기서 2,4,5번째 컴포넌트가 차이를 갖습니다.

해밍 거리는 거리 측도입니다.

1. 차이의 수를 세는 것이기 때문에 음수가 될 수 없습니다.
2. 벡터가 동일한 경우 0이 됩니다.
3. 벡터가 다른지를 보는 것 이므로 순서와는 무관합니다.
4. x, z가 m개의 컴포넌트에서 차이가 있고, z, y가 n개의 컴포넌트에서 차이가 있습니다. 그러면 x와 y는 m+n 보다 더 크게 차이날 수 없습니다.

일반적으로 해밍거리는 boolean을 사용합니다. 그러나, 원리 상, 벡터의 컴포넌트는 어떤 집합이든 사용할 수 있습니다.

Nod-Eucliden Spaces

이 포스팅에서 소개된 몇개의 거리측도는 유클리드 공간안에서 사용하는 것이 아닙니다.

유클리드 공간의 속성은 유클리드 공간안의 점들의 평균은 항상 존재하고 그 점은 공간안에 있다는 것 입니다.

그러나 자카드 거리에서 사용한 집합의 공간의 경우, 두 집합의 평균이란 개념을 사용할 수 없습니다.

edit 거리를 사용하는 문자열들의 공간도 마찬가지로, 문자열의 평균을 사용할 수 없습니다.

일부 거리 측도들은 벡터들의 자료형에 따라 유클리드 공간에 포함 여부가 달라집니다.

예를 들어 [1,2],[3,1] 의 벡터가 있을 때,

실수형 인 경우 [2.0,1.5] 로 평균을 구할 수 있지만

정수형 갖는 벡터 공간에서는 평균을 구할 수없습니다.

이런식으로 자료형에 따라 유클리드 공간인지 아닌지가 갈릴 수 있습니다.