Metric Space - 거리 공간

Metric Space의 정의

 

거리 공간( metric space)은 두 점 사이의 거리가 정의된 공간이다. 거리의 정의에 따라 표준적인 위상상을 갖는다.

Metric space M =(D,d)의 정의는 다음과 같다.

M = (D,d)

- Data domain D

- Total (distance) function d: D * D -> [0,무한)

 

즉 데이터의 집합 D와, 데이터 간의 거리를 표현하는 function 'd'가 정의된 공간이라 할 수 있다.

이 거리공간은 다음과 같은 조건을 만족시켜야 한다.

 

위 조건들을 간단히 설명하자면,

- 거리공간에서 서로 다른 두 점 사이의 거리는 음수가 될 수 없고(p1)

- 임의의 점 x에서 y까지의 거리는 y에서 x까지의 거리와 같으며(p2)

- 같은 두 점 사이의 거리는 0이고(p3)

- 서로 같지 않은 두 점의 거리는 무조건 0보다 커야하며(p4)

- 삼각 부등식이 성립해야 한다(p5)

 

위의 조건들중 하나라도 생략되면 Metric Space가 아니다.

특정 조건이 생략되어 Metric Space는 아니지만 특별한 케이스들이 있다.

 

Pseudo metric space

p4의 조건이 생략되면, Pseudo metric space(유사 거리 공간)이 된다.

유사 거리 공간은 서로 다른 두 점 사이의 거리가 0이 될 수 있는 공간이다.

즉 같은 위치에 존재하는 object가 서로 다른 object로 취급 될 수 있다는 특징이 있다.

 

Quasi metric

p2의 조건이 생략되면, Quasi metric space(쿼시 거리 공간)이 된다.

이해하기 쉽게 예를 들자면, 일방통행로가 존재하는 지도를 생각해보자.

X에서 Y까지의 경로는 일방통행으로 |X - Y|가 될 수 있지만, Y에서 X로 가기 위해서는 돌아가야 하므로 symmetry의 성질이 성립하지 않는다.

 

Metric distance measures

 

이제 거리 공간에서 사용할수 있도록, 거리를 측정하는 다양한 방법들을 알아보자.

---

1. Minkowski distance

민코프스키 거리.

Lp metrics라고도 불린다.

n차원 벡터에 대해 거리를 측정할 수 있다.

p = 2인경우에는 유클리디안 distance로 우리가 흔히 아는 벡터의 내적과 같다.

민코프스키 거리 이의 확장으로 1차원부터 무한대의 차원까지의 벡터 사이의 거리를 나타낼 수 있다.

 

---

 

2. Quadratic form distance

 

서로 상관관계를 가지는 object 간의 거리를 나타낼 때 사용한다.

다음과 같이 3차원 벡터 red, orange, blue를 정의하였다고 가정해보자.

이 때 각 벡터의 거리를 계산해 본다면,

빨강-주황, 빨강-파랑 사이의 거리가 각각 루트2로 같게 된다.

하지만 사람의 관점에서 보면, 빨강과 주황이 더 가깝게 느껴진다.

이렇게 벡터간의 상관관계가 있을 경우, '보정값'을 이용하여 결과를 조정해줄 수 있다.

다음과 같이, red와 orange 사이의 상관관계를 추가해준 보정값 M 넣

를 다시 계산하게 되면, red-orange의 거리는 루트0.2, red-blue의 거리는 루트2가 된다.

이렇게 상관관계가 존재하는 data(벡터)들간의 거리를 구하기 위해 사용하는 distance measure가,

쿼드라틱 폼 디스턴스인 것이다.

 

---

 

3. Edit distance

 

Levenstein(레벤시테인) 거리라고도 불리는 edit distance는, 문자열 x을 문자열 y로 바꾸는데 필요한 최소한의 기본 변환의 수를 나타내는 거리이다.

 

문자열 간의 거리를 나타내는 기본이 되는 방식으로,

구글이나 네이버 등에서의 웹 서칭을 위한 알고리즘의 근간이 된다.

 

basic function에는 insert(삽입), delete(삭제), replace(대체)가 있다.

 

만약 삽입과 삭제의 가중치, 즉 weight가 다르다고 가정해보자.

이 경우 우리가 전에 살펴봤던 metric space의 기본 원칙 p2(대칭성)를 위반하게 되어 거리공간이 아니게 된다.

다음과 같은 경우가 그것이다.

combine에서 combination으로 변환하는데 드는 비용과

combination에서 combine으로 변환하는데 드는 비용이 다르다면,

(insert와 delete의 비용이 다른 경우)

metric space로 표현을 할 수가 없다는 얘기다.

---

4. Jaccard's coefficient

 

자카드 계수(jaccard's coefficient)는 집합 사이의 거리를 나타내는 계수이다.

집합 A와 B의 거리 d(A,B)는 다음과 같이 정의된다.

곱집합을 합집합으로 나눈 것을 1에서 빼는 형태이다.

즉 집합간에 겹치는 원소가 많을 수록 값은 0과 가까워지고, 겹치는 원소가 없을 수록 1과 가까워진다.

이와 비슷한 계수로 Tanimoto similarity가 있다.

자카드 계수가 집합 간의 거리를 나타내는데 반해 타니모토 계수는 백터 간의 거리를 표현한다.

---

5. Hausdorff distance

 

하우스도르프 거리도 집합들의 거리를 측정하기 위한 방법이다.