두 대상이 얼마나 다른지를 수 하나로 적은 것이 거리이고, 얼마나 닮았는지를 적은 것이 유사도다. 지도 위 두 도시 사이의 길이처럼 거리는 작을수록 가깝고, 유사도는 그 눈금을 뒤집어 클수록 닮았다. 다만 아무 수나 거리라 부를 수는 없고, 자기 자신과만 0이고, 재는 방향을 바꿔도 같고, 다른 곳을 들러 가는 길이 곧장 가는 길보다 짧지 않아야 한다. 이 조건이 깨진 값은 “가까운 것의 가까운 것은 가깝다”는 추론에 쓸 수 없다.
예시로 보기
수는 크다·작다, 많다·적다를 비교할 수 있다. 사진, 문장, 장바구니는 그대로는 비교할 수 없다. “이 사진과 가장 닮은 사진”을 찾으려면 두 대상을 받아 수 하나를 내놓는 규칙이 있어야 한다. 그 수끼리 대소를 비교하면 가깝다·멀다가 나온다.
예를 들어 바다사자 사진과 다른 세 사진의 유사도가 표범 0.81, 물범 0.88, 너구리 0.81이라고 하자. 물범이 가장 닮았다. 유사도를 “1에서 뺀 값”으로 거리로 바꾸면 0.19, 0.12, 0.19이고, 물범이 가장 가깝다. 순서가 뒤집힌 채로 같은 말을 한다.
거리라 부르려면 지켜야 할 조건이 있다. 좌표 위의 세 점 0, 1, 2에서 “차이의 제곱”을 거리로 쓰면 이렇게 된다.
- 0에서 2까지: \((0 - 2)^2 = 4\)
- 0에서 1을 들러 2까지: \((0 - 1)^2 + (1 - 2)^2 = 2\)
들러 가는 길이 곧장 가는 길보다 짧다. 지도에서는 있을 수 없는 일이다. 차이의 제곱은 순서를 매기는 데는 쓸 수 있지만 거리의 조건은 지키지 못한다1.
정의
대상들의 모음을 \(\mathcal{S}\)라 하자. 사진 전체, 문장 전체, 좌표 평면 위의 점 전체 같은 것이다.
거리 함수. 대상 둘을 받아 0 이상의 실수를 내놓는 함수 \(d : \mathcal{S} \times \mathcal{S} \to \mathbb{R}^+ \cup \{0\}\)이다. \(\mathbf x, \mathbf y, \mathbf z \in \mathcal{S}\)에 대해,
- \(d(\mathbf x, \mathbf y)\)가 작으면 \(\mathbf x\)와 \(\mathbf y\)는 가깝다. 곧 비슷하다.
- \(d(\mathbf x, \mathbf y) < d(\mathbf x, \mathbf z)\)이면 \(\mathbf x\)는 \(\mathbf z\)보다 \(\mathbf y\)에 더 가깝다.
유사도 함수. 대상 둘을 받아 실수를 내놓는 함수 \(s : \mathcal{S} \times \mathcal{S} \to \mathbb{R}\)이다. \(\mathbf x\)와 \(\mathbf y\)가 비슷하면 \(s(\mathbf x, \mathbf y)\)가 크다. 흔히 0부터 1까지로 맞춘다.
서로 바꾸기.
| 가진 것 | 바꾸는 식 | 쓰는 때 |
|---|---|---|
| 0~1의 유사도 \(s\) | \(d_s = 1 - s\) | 유사도에서 거리로 |
| 0~1의 거리 \(d\) | \(s_d = 1 - d\) | 거리에서 유사도로 |
| 가장 큰 값이 \(D\)인 거리 | \(s_d = 1 - \dfrac{d}{D}\) | 거리가 1을 넘을 때 |
| 끝없이 커질 수 있는 거리 | \(s_d = \dfrac{1}{1 + d}\) | 가장 큰 값을 모를 때 |
모두 거리가 0이면 유사도가 1이고, 거리가 클수록 유사도가 작다. 예: \(d = 3\)이면 \(\frac{1}{1 + 3} = 0.25\)다.
거리의 척도. 거리 함수가 다음 네 조건을 모두 지키면 거리의 척도(metric)라 한다.
- 0 이상: \(d(\mathbf x, \mathbf y) \ge 0\).
- 같을 때만 0: \(d(\mathbf x, \mathbf y) = 0 \iff \mathbf x = \mathbf y\).
- 대칭: \(d(\mathbf x, \mathbf y) = d(\mathbf y, \mathbf x)\).
- 삼각부등식: \(d(\mathbf x, \mathbf z) \le d(\mathbf x, \mathbf y) + d(\mathbf y, \mathbf z)\).
4번은 삼각형의 한 변이 나머지 두 변의 합보다 길 수 없다는 말이다. 삼각형을 점점 납작하게 눌러 \(\mathbf y\)가 \(\mathbf x\)와 \(\mathbf z\)를 잇는 선 위에 오면 양쪽이 같아진다.
각 조건이 왜 필요한지는 깨지는 예로 본다1.
| 깨지는 조건 | 예 | 무슨 일이 생기나 |
|---|---|---|
| 2 (같을 때만 0) | 첫 좌표만 비교: \((1, 2)\)와 \((1, 9)\)가 0 | 다른 대상을 같다고 본다 |
| 3 (대칭) | 일방통행 길의 주행 시간 | “A에서 가까운 B”가 “B에서 가까운 A”가 아니다 |
| 4 (삼각부등식) | 차이의 제곱: \(4 > 1 + 1\) | 가까운 것의 가까운 것이 멀 수 있다 |
어떤 자료에 어떤 척도를 쓰나. 관계를 재야 할 자료는 아홉 가지로 나눌 수 있다. 숫자, 범주, 둘이 섞인 것, 집합, 이진, 문자열, 글, 그래프, 시계열이다. 이 문서 모음에서 다루는 척도는 자료에 따라 이렇게 나뉜다.
| 자료 | 척도 | 문서 |
|---|---|---|
| 숫자 벡터 | 민코프스키 거리 | 민코프스키 거리 |
| 숫자 벡터(퍼진 모양까지) | 마할라노비스 거리 | 마할라노비스 거리 |
| 숫자 벡터(방향만) | 코사인 유사도 | 내적과 노름 |
| 범주, 이진 부호 | 겹침 유사도, 해밍 거리, 자카드 | 범주형 속성의 비유사도, 해밍 거리와 부호 거리 |
| 문자열 | 토큰 기반 유사도, 편집 거리 | 문자열 유사도, 편집 거리 |
예제
코사인 거리는 척도가 아니다. 코사인 유사도를 1에서 뺀 \(1 - \cos(\mathbf x, \mathbf y)\)를 코사인 거리라 부른다. 이름은 거리지만 조건 2와 4를 어긴다1.
- 같을 때만 0인가: \((1, 2)\)와 \((2, 4)\)는 방향이 같아 코사인이 1, 거리가 0이다. 다른 점인데 0이다.
- 삼각부등식: \(\mathbf a = (1, 0)\), \(\mathbf b = (1, 1)\), \(\mathbf c = (0, 1)\)로 잰다. \(\mathbf a\)와 \(\mathbf c\)는 직각이라 거리 1이다. \(\mathbf a\)–\(\mathbf b\)와 \(\mathbf b\)–\(\mathbf c\)는 45도라 각각 \(1 - \frac{1}{\sqrt2} \approx 0.293\)이다.
- 비교: 들러 가는 길 \(0.293 + 0.293 = 0.586\)이 곧장 가는 길 1보다 짧다. 삼각부등식이 깨진다.
코사인 거리는 “닮은 순서”를 매기는 데는 쓸 수 있다. 하지만 삼각부등식에 기대는 계산에는 넣을 수 없다.
활용
- 가까운 것 찾기. 최근접 이웃 찾기, 군집화, 추천, 중복 찾기가 모두 거리나 유사도의 대소 비교다1.
- 삼각부등식으로 계산 아끼기. \(d(\mathbf x, \mathbf y)\)가 크고 \(d(\mathbf y, \mathbf z)\)가 작으면 \(d(\mathbf x, \mathbf z) \ge d(\mathbf x, \mathbf y) - d(\mathbf y, \mathbf z)\)라서 \(\mathbf z\)도 멀다는 것을 재지 않고 안다. 척도가 아니면 이 지름길을 쓸 수 없다1.
- 오류 정정. 부호 거리가 \(2t + 1\)이면 \(t\)개를 고친다는 증명이 해밍 거리의 삼각부등식을 쓴다.
- 흔한 실수: 유사도와 거리를 섞어 “값이 큰 쪽이 가깝다”와 “값이 작은 쪽이 가깝다”를 뒤바꾸는 것. 정렬 방향을 먼저 확인한다.
연결
확인 문제
C1 거리 함수가 거리의 척도가 되기 위한 네 조건을 쓰라.
답: ① \(d(\mathbf x, \mathbf y) \ge 0\) ② \(d(\mathbf x, \mathbf y) = 0\)인 것은 \(\mathbf x = \mathbf y\)일 때뿐 ③ \(d(\mathbf x, \mathbf y) = d(\mathbf y, \mathbf x)\) ④ \(d(\mathbf x, \mathbf z) \le d(\mathbf x, \mathbf y) + d(\mathbf y, \mathbf z)\).
흔한 오답: ②를 “같으면 0”으로만 쓰는 것. “0이면 같다”까지 있어야 한다.
C2 두 대상의 거리가 3이다. 가장 큰 거리가 10인 경우의 유사도와, 가장 큰 거리를 모르는 경우의 유사도를 구하라.
답: \(1 - \frac{3}{10} = 0.7\). 모르면 \(\frac{1}{1 + 3} = 0.25\).
이유: 두 값이 달라도 괜찮다. 같은 식으로 바꾼 값끼리만 비교하면 순서는 같다.
C3 “차이의 제곱” \(d(a, b) = (a - b)^2\)이 거리의 척도가 아님을 보여라. 어느 조건이 깨지는가?
답: 삼각부등식. \(a = 0, b = 1, c = 2\)에서 \(d(a, c) = 4\)인데 \(d(a, b) + d(b, c) = 1 + 1 = 2\)다. 조건 1~3은 지킨다.