요약

숫자로 된 두 점이 얼마나 떨어져 있는지 재는 방법을 하나로 묶은 공식이다. 지도에서 곧장 날아가는 거리(유클리드)와 바둑판 같은 도로를 따라 걷는 거리(맨해튼)가 모두 이 공식의 특별한 경우다. 공식 속 지수 하나만 바꾸면 어느 쪽인지 정해진다. 다만 지수가 1보다 작으면 “돌아가는 길이 더 짧아지는” 이상한 값이 나와 거리라고 부를 수 없고, 속성마다 단위가 다르면 큰 단위의 속성이 거리를 독차지한다.

예시로 보기

점 \(x_1 = (1, 2)\)에서 \(x_2 = (3, 5)\)까지 가로로 2, 세로로 3 떨어져 있다.

  • 대각선으로 곧장 가면 피타고라스 정리로 \(\sqrt{2^2 + 3^2} = \sqrt{13} \approx 3.61\)이다. 유클리드 거리다.
  • 바둑판 도로처럼 가로세로로만 갈 수 있으면 \(2 + 3 = 5\)다. 맨해튼 거리(시가지 거리)다. 뉴욕 맨해튼의 격자 도로에서 택시가 가는 거리라는 뜻이다.

두 식은 “각 좌표의 차이를 몇 제곱 해서 더하고, 다시 그만큼 제곱근을 씌운다”는 같은 모양이다. 유클리드는 2제곱, 맨해튼은 1제곱이다. 이 지수를 \(h\)로 두면 하나의 식이 된다.

검증: \((1, 2)\)–\((3, 5)\)의 3.61과 5, 무작위 점 2,000쌍에서 세 성질, \(h\)가 커지면 3으로 줄어듦, \(h = \frac12\)의 반례, 카드 C3 — 04_minkowski-distance_verify.py

정의

수치 속성 \(p\)개로 적은 두 대상 \(i = (x_{i1}, \dots, x_{ip})\)와 \(j = (x_{j1}, \dots, x_{jp})\)의 민코프스키 거리는, 좌표 차이의 \(h\)제곱을 모두 더해 \(h\)제곱근을 씌운 것이다. 여기서 \(h \ge 1\)인 실수다.

\[d(i, j) = \sqrt[h]{\vert x_{i1} - x_{j1}\vert ^h + \vert x_{i2} - x_{j2}\vert ^h + \cdots + \vert x_{ip} - x_{jp}\vert ^h}\]
\(h\) 이름 식
1 맨해튼 거리 \(\sum_f \lvert x_{if} - x_{jf}\rvert\)
2 유클리드 거리 \(\sqrt{\sum_f (x_{if} - x_{jf})^2}\)
\(\infty\) 최대 거리 \(\max_f \lvert x_{if} - x_{jf}\rvert\)1

\(h\)가 커질수록 가장 큰 좌표 차이가 합을 좌우한다. 예시 두 점은 \(h = 1, 2, 4, 10\)에서 5, 3.61, 3.14, 3.005로 줄어 가장 큰 차이인 3에 다가간다1.

그림

원점에서 거리가 정확히 1인 점들을 \(h\)마다 이었다. \(h = 1\)은 마름모, \(h = 2\)는 원이고, \(h\)가 커질수록 정사각형(\(h = \infty\))에 다가간다. 점선 \(h = \frac12\)는 안쪽으로 오목하다. 그래서 곧장 가는 길이 꺾어 가는 길보다 길어진다2.

거리는 다음 세 성질을 지킨다.

  • 0 이상: \(d(i, j) \ge 0\).
  • 대칭: \(d(i, j) = d(j, i)\).
  • 삼각부등식: \(d(i, j) \le d(i, k) + d(k, j)\). 다른 점 \(k\)를 들렀다 가는 길이 곧장 가는 길보다 짧을 수 없다.

예제

\(h < 1\)이면 거리가 아니다. \(h = \frac12\)로 \((0, 0)\), \((1, 0)\), \((1, 1)\)을 잰다1.

  • 곧장: \(d((0,0), (1,1)) = (\sqrt1 + \sqrt1)^2 = 4\).
  • \((1, 0)\)을 들러서: \(d((0,0), (1,0)) + d((1,0), (1,1)) = 1 + 1 = 2\).

들러 가는 길(2)이 곧장 가는 길(4)보다 짧아 삼각부등식이 깨진다. 그래서 정의에서 \(h \ge 1\)로 제한한다.

활용

  • 군집화(k-평균 등)와 최근접 이웃 찾기의 기본 거리다.
  • 맨해튼 거리는 한 좌표의 큰 차이를 제곱으로 키우지 않아, 튀는 값 하나에 유클리드보다 덜 흔들린다1.
  • 흔한 실수: 단위가 다른 속성을 그대로 넣는 것. 키를 cm로 적으면 몸무게 차이가 묻히고, m로 적으면 키 차이가 묻힌다. 먼저 정규화한다.

연결

과목별 관점

자료와 정보 (2-1학기). 같은 식을 지수 \(p\)로 쓰고 \(L_p\) 노름이라 부른다. 속성 수는 \(k\)다.

\[L_p(\mathbf x, \mathbf y) = \left(\sum_{i=1}^{k} \vert x_i - y_i\vert ^p\right)^{\frac1p}\]

위 정의의 \(h\)가 \(p\)이고, \(p \ge 1\)일 때만 거리의 척도라는 조건도 같다. \(p \to \infty\)인 최대 거리를 체비셰프 거리라 부르고 \(L_\infty(\mathbf x, \mathbf y) = \max_i \vert x_i - y_i\vert\)로 적는다. 가로 4, 세로 3인 직사각형의 마주 보는 두 꼭짓점 사이는 유클리드 거리로 5, 맨해튼 거리로 7, 체비셰프 거리로 4다. 맨해튼 거리는 격자 도로 지도 위에서 꺾어 가는 길로 그린다.

두 가지가 이 문서와 다르다.

  • 조건의 수. 자료와 정보에서는 거리의 척도가 되려면 네 조건을 지켜야 한다고 본다. 위의 세 성질에 “거리가 0인 것은 두 점이 같을 때뿐”이 더 있다: 거리와 유사도. 민코프스키 거리는 \(p \ge 1\)이면 이 조건도 지킨다. 좌표가 하나라도 다르면 합이 0보다 크기 때문이다3.
  • 자료의 퍼진 모양. 민코프스키 거리는 모든 방향을 똑같이 본다. 자료가 한쪽으로 길게 퍼져 있을 때 그 모양까지 넣어 재는 것이 마할라노비스 거리다. 모든 속성이 0 또는 1이면 맨해튼 거리는 다른 자리의 수가 되어 해밍 거리와 같다.

확인 문제

C1 \((0, 0)\)과 \((4, 3)\) 사이의 맨해튼, 유클리드, 최대 거리를 구하라.

답: 맨해튼 \(4 + 3 = 7\), 유클리드 \(\sqrt{16 + 9} = 5\), 최대 \(\max(4, 3) = 4\). 늘 맨해튼 ≥ 유클리드 ≥ 최대다.

C2 민코프스키 공식에서 \(h\)를 1보다 작게 잡으면 안 되는 이유를 반례로 보여라.

답: \(h = \frac12\)에서 \((0,0)\)–\((1,1)\)은 4인데, \((1, 0)\)을 들러 가면 \(1 + 1 = 2\)로 더 짧다. 삼각부등식이 깨져 거리가 아니다.

C3 세 사람 A(170 cm, 60 kg), B(180 cm, 61 kg), C(171 cm, 62 kg)에서 A와 가장 가까운 사람을 유클리드 거리로 찾으라. 키를 m로 바꿔 적으면 어떻게 되는가? 무엇을 해야 하는가?

답: cm로 적으면 \(d(A, B) \approx 10.05\), \(d(A, C) \approx 2.24\)라 C가 가깝다. m로 적으면 \(d(A, B) \approx 1.005\), \(d(A, C) \approx 2.0\)이라 B가 가깝다. 단위만 바꿨는데 답이 뒤집힌다. 속성마다 크기를 맞추는 정규화를 먼저 해야 한다1.

C4 어떤 자료는 거리의 성질을 셋(0 이상, 대칭, 삼각부등식)으로, 다른 자료는 넷으로 적는다. 넷째는 무엇인가? “첫 좌표의 차이만 재는” \(d(\mathbf x, \mathbf y) = \vert x_1 - y_1\vert\)은 셋과 넷 가운데 어디까지 지키는가?

답: 넷째는 “\(d(\mathbf x, \mathbf y) = 0\)인 것은 \(\mathbf x = \mathbf y\)일 때뿐”이다. 첫 좌표만 재는 값은 0 이상, 대칭, 삼각부등식은 지키지만 \((1, 2)\)와 \((1, 9)\)가 0이 되어 넷째를 어긴다.
이유: 세 성질만으로는 서로 다른 두 대상을 “거리 0”으로 뭉개는 값을 막지 못한다. 민코프스키 거리는 모든 좌표의 차이를 더하므로 넷째도 지킨다3.

  1. Han, Kamber, Pei, Data Mining: Concepts and Techniques 3판, 2.4.4절이 최대 거리를 다룬다. 수치는 검증 코드로 확인했다. ↩ ↩2 ↩3 ↩4 ↩5

  2. 04_minkowski-distance_plot.py로 그렸고, 곡선 위 점들의 거리가 1인지, 예시 두 점의 5, 3.61, 3.14, 3.005, \(h = \frac12\)의 반례를 같은 코드로 확인했다. ↩

  3. 08_distance-similarity_verify.py로 확인했다. ↩ ↩2