두점 사이 거리계산 알고리즘

https://hleecaster.com/ml-distance-formula/

두 점 사이의 거리 공식(Distance Formula) 쉽게 이해하기 - 아무튼 워라밸

1. 유클리드 거리 (Euclidean Distance)

‘유클리디안 거리’라고 영어 단어를 그대로 읽기도 하는데, 아무튼 가장 널리 쓰이는 거리 계산 방법이다.

예를 들어 아래와 같이 2차원에 있는 점 a와 b의 거리를 구한다면 이렇게 나타낼 수 있다.

피타고라스의 정리가 떠오를 거다. 중학교 때 다 배웠던 거다.

그리고 위 예제는 2차원이지만 만약 n차원에서 두 점 사이의 거리를 구한다면 이렇게 나타낼 수 있겠다. 각 차원의 차를 제곱해서 모두 더한 값의 제곱근이다.

이걸 파이썬 함수로 구현하면 아래와 같다.

def euclidean_distance(pt1, pt2):
distance = 0
for i in range(len(pt1)):
distance += (pt1[i] - pt2[i]) ** 2
return distance ** 0.5

# print(euclidean_distance([5, 4, 3], [1, 7, 9]))

2. 맨하탄 거리(Manhattan Distance)

맨하탄 거리도 유클리드 거리와 유사하긴 한데, 각 차원의 차를 제곱해서 사용하는 게 아니라 그냥 절대값을 바로 합산하는 거다.

아래 그림과 같은 개념으로 이해하면 쉽다. 실제로 맨하탄 거리라는 이름도 도시의 골목길(블록)을 걸을 때의 모습과 유사하기 때문에 붙은 거라고 한다. (a에서 b로 이동할 때 몇 블록 이동하는지 상상해보자.)

그림에서도 알 수 있듯이 맨하탄 거리는 항상 유클리드 거리보다 크거나 같다.

만약 n차원에서 두 점 사이의 거리를 구한다면 이렇게 나타낼 수 있겠다.

이걸 파이썬 함수로 구현하면 아래와 같다.

def manhattan_distance(pt1, pt2):
distance = 0
for i in range(len(pt1)):
distance += abs(pt1[i] - pt2[i])
return distance

# print(manhattan_distance([5, 4, 3], [1, 7, 9]))

3. 해밍 거리 (Hamming Distance)

해밍 거리는 앞서 설명한 유클리드 거리, 맨하탄 거리와는 좀 다른 개념이다.

해밍 거리에서는 각 차원마다 차이를 찾는 게 아니라 ‘정확히 같은지’ 여부만 고려한다. 그래서 주로 맞춤법 검사와 같은 알고리즘에 많이 사용된다.

예를 들어, 단어 “there”와 오타 “thete”사이의 해밍 거리는 1인 셈이다. 각 문자가 차원이며 이 예시에서 각 차원은 네 번째 문자 “r”과 “t”를 제외하고 동일한 값을 갖고 있기 때문이다.

 

예를 들어, 단어 “there”와 오타 “thete”사이의 해밍 거리는 1이다. 각 문자가 곧 차원이고, 이 예시에서는 네 번째 문자 “r”과 “t”가 다르기 때문이다. 결국 서로 다른 글자 개수만 세주는 셈이다.

해밍 거리 구하는 방법을 파이썬 함수로 구현하면 아래와 같다.

def hamming_distance(pt1, pt2):
distance = 0
for i in range(len(pt1)):
if pt1[i] != pt2[i]:
distance += 1
return distance

# print(hamming_distance([5, 4, 3], [1, 7, 9]))

---

SciPy를 통해 거리 구하기

파이썬의 라이브러리 Scipy를 사용하면 위에서 소개한 거리를 매우 쉽게 구할 수 있다.

• 유클리드 거리: .euclidean()
• 맨하탄 거리: .cityblock()
• 해밍 거리: .hamming()

(맨하탄 거리는 city block처럼 몇 블록 떨어져 있는지 구하는 꼴이기 때문에 아예 그렇게 이름이 붙어 있는 걸 볼 수 있다.)

그리고 위에서 소개한 해밍 거리를 Scipy에서는 0과 1사이의 값으로 돌려준다. 몇 개 차원에서 차이가 나는지 합산한 다음에 총 차원의 개수로 나누기 때문이다. 그래서 만약 위에서 직접 작성한 함수에서 [1, 2, 3]과 [7, 2, -10] 사이의 해밍 거리를 구하면 2이지만, scipy에서는 2/3으로 나온다.

아무튼 scipy에서는 이렇게 거리를 바로 구할 수 있다.

from scipy.spatial import distance

print(distance.euclidean([1, 2], [4, 0]))
print(distance.cityblock([1, 2], [4, 0]))
print(distance.hamming([5, 4, 9], [1, 7, 9]))