-
[클러스터링] 거리 혹은 비유사도 (Distance or Dissimilarity)clustering 2023. 3. 5. 17:28
0. 내용
- 클러스터링이란?
- 거리란?
- 다양한 거리
- 유클리드 거리
- 민코프스키 거리 (맨해튼 거리, 캔버라 거리, 체브셰프 거리)
- 마할라노비스 거리
- 각도 기반 거리 (코사인 유사도, 피어슨 상관계수)
- 하버사인 거리
- 자카드 거리 (가중 자카드 거리, 다이스 거리)
- 편집 거리 (해밍 거리, 레벤슈타인 거리)
- 어떤 걸 어떻게 써야 하는지?
- 참고 문헌
1. 클러스터링이란?
클러스터링(군집화)은 데이터의 내재적 특성을 이용하여 데이터 포인트들을 여러 클러스터로 묶는 방법입니다. 다른 말로는, 데이터를 클러스터에 소속시킨다..., 혹은 데이터의 소속(membership)을 추정한다...고 표현하기도 합니다. 이때 보통 서로 유사한 데이터는 같은 클러스터에, 상이한 데이터는 다른 클러스터에 소속시키는 것이 자연스럽습니다.
이렇게 있는 데이터들을... 
이렇게 묶어 주기!
2. 거리란?
그렇다면 데이터끼리 얼마나 유사한지 어떻게 수치화할까요? 가장 간단하게는 멀리 떨어져 있으면 다르고, 가깝게 붙어있으면 비슷하다고 생각해 볼 수 있습니다. 이때 두 데이터 포인트가 얼마나 떨어져 있는지를 '거리(metric)'라고 하고 다음의 성질을 만족합니다.
어떤 집합 $X$에 속하는 $ x, y, z \in X $와 어떤 함수 $d: X \times X \to [0, \infty )$를 생각합니다. 이때, 모든 $x,y,z$에 대해
1. 조건에 적혀 있듯이 $d$의 값은 음이 아닌 실수입니다.
2. $d(x,y) = 0$ iff $x=y$ 두 데이터 사이의 거리가 0이라는 것은 두 데이터가 같은 데이터라는 말과 같습니다.
3. $d(x,y) = d(y,x)$ 두 데이터 사이의 거리는 대칭입니다.
4. $d(x,y) \leq d(x,z) + d(z,y)$ 삼각 부등식을 만족합니다.엄밀하게 말하면 위와 같은 조건을 만족하는 함수 $d$를 거리라고 부를 수 있습니다. 그러나 위의 조건을 만족하지 않아도 두 데이터 사이가 얼마나 비슷한지 나타내는 방법은 많고, 심지어는 그러한 방법들을 클러스터링에 무리 없이 적용할 수 있는 경우도 많습니다. 따라서 이 글에서는 사용하는 '거리(distance)'라는 용어는 위의 조건들을 만족하는 '거리(metric)'가 아닐 수도 있으며, 사실은 '비유사도(dissimilarity)'라는 두루뭉술한 개념이라고 보는 것이 좋습니다. 아래 설명할 여러 개념들이 거리 조건을 만족하는지 여부에 대해서는 자세히 다루지 않겠습니다.
3. 다양한 거리
세상에는 엄청나게 많은 비유사도가 존재합니다. 어떤 사람들은 본인의 연구를 위한 적절한 비유사도를 새로 만들어서 사용하기도 합니다. 수많은 비유사도 중에서 두 데이터 포인트 사이의 거리를 측정하는 기초적인 몇 가지를 다뤄 보도록 하겠습니다.
3-1. 유클리드 거리 (Euclidean distance)
가장 먼저 유클리드 거리에 대해 알아보겠습니다. 유클리드 거리는 기계 학습에서 $L^2$ 거리라고도 불립니다. 정의 상 유클리드 거리는 두 데이터 포인트 $\mathbf{a}, \mathbf{b}$ 사이를 잇는 선분의 길이입니다.
$\mathbb{R}^n$에서 정의된 두 데이터 포인트 $\mathbf{a} = [a_1, \ldots ,a_n], \mathbf{b} = [b_1, \ldots ,b_n]$가 있다고 하겠습니다. 이때 둘 사이의 유클리드 거리 $d_E$는 다음과 같이 정의되는데,
$$ d_E(\mathbf{a}, \mathbf{b}) := \sqrt{(a_1-b_1)^2 + \cdots + (a_n-b_n)^2} = \sqrt{\sum_{i=1}^n {(a_i-b_i)^2}} $$
이는 의미적으로 벡터 안의 요소들의 차이를 전부 더한 것이라고도 볼 수 있습니다. 단, 그냥 더하면 양수와 음수들이 섞여 나와서 크기가 보존이 되지 않기 때문에 제곱을 해서 더해 줍니다. 제곱을 했으니, 이후에 루트를 씌워서 크기를 보정했다...고 이해할 수 있습니다 (여러 클러스터링 기법에서는 최적화 문제로 루트를 씌워 보정하는 과정을 생략하고 유클리드 거리의 제곱을 그대로 사용하는 경우도 있습니다).
벡터 형태로 수식을 적으면 다음과 같습니다.
$$ d_E(\mathbf{a}, \mathbf{b}) = \sqrt{(\mathbf{a}-\mathbf{b})^t(\mathbf{a}-\mathbf{b})} $$
유클리드 거리는 2차원에서 보면 고등학생 때 배웠던 대로 아래와 같이 피타고라스 정리로 표현할 수 있습니다. 이렇게 보면 유클리드 거리가 두 점 사이를 잇는 선분의 길이라는 것도 보다 직관적으로 알 수 있습니다.
from Wikipedia 유클리드 공간에서 벡터의 크기 또한 원점과 벡터 사이의 유클리드 거리라고 이해할 수도 있습니다.
$$ ||\mathbf{a}||_{2} = \sqrt{{a_1}^2+\cdots+{a_n}^2} = \sqrt{{(a_1-0)}^2+\cdots+{(a_n-0)}^2} = d_E(\mathbf{a}, \mathbf{0}) $$
그리고 위의 노테이션을 사용하면 유클리드 거리는 두 벡터의 차이의 길이라고 볼 수 있습니다.
$$ d_E(\mathbf{a}, \mathbf{b}) = ||\mathbf{a} - \mathbf{b}||_2 $$
3-2. 민코프스키 거리 (Minkowski distance)
유클리드 거리를 보다 보면 2제곱해서 더하고 나중에 1/2제곱을 하는 것 대신에 3제곱해서 더하고 나중에 1/3제곱을 해 보고 싶지 않나요? 혹은 2, 3 대신에 다른 값을 넣어 보면 어떨까요? 이렇게 유클리드 거리를 일반화한 것을 민코프스키 거리라고 하며 다음과 같이 정의됩니다. 위의 노테이션을 그대로 사용하면 $L^p$ 거리라고도 불리는 민코프스키 거리 $d_M$은 다음과 같이 정의됩니다.
$$d_M(\mathbf{a}, \mathbf{b}) := \sqrt[p]{|a_1-b_1|^p+\cdots+|a_n-b_n|^p} = \left(\sum_{i=1}^n {|a_i-b_i|^p}\right)^{1/p}$$
위의 식에서 $p=2$일 때가 유클리드 거리입니다. 결국 유클리드 거리는 민코프스키 거리의 특수한 경우였네요! 그리고 이외에도 몇 가지 특수한 경우에 대한 별칭이 있습니다.
첫 번째로, $L^1$ 거리라고도 불리는 $p=1$의 별칭은 맨해튼 거리 혹은 택시 거리입니다.
$$ d_{Mht}(\mathbf{a}, \mathbf{b}) := \sum_{i=1}^n {|a_i-b_i|}$$
아래의 그림에서 한 점에서 다른 점까지 가는 최단 거리는 초록 선으로 그려진 유클리드 거리입니다. 그리고 빨간 선이 바로 맨해튼 거리입니다. 한 차원을 따라 끝까지 이동하고, 다음 차원을 따라 또 끝까지 이동하고, ... 이렇게 모든 차원에서 일직선으로 이동하며 한 점에서 다른 점으로 갈 때 이동하는 거리의 총합입니다. 파란 선과 노란 선도 빨간 선과 길이는 같은데, 저런 방식으로 이동하는 것이 빌딩 사이를 이동하는 택시 같다고 해서 붙여진 이름이 택시 거리입니다.
from Wikipedia 이 거리 개념을 이용하면 벡터의 크기를 다음과 같이 표현해 볼 수 있습니다.
$$ ||\mathbf{a}||_{1} = |{a_1}|+\cdots+|{a_n}| = |a_1-0|+\cdots+|a_n-0| = d_{taxi}(\mathbf{a}, \mathbf{0}) $$
맨해튼 거리는 유클리드 거리보다 아웃라이어에 안정적이라고 알려져 있습니다만, 여전히 벡터의 크기에 크게 영향을 받을 것처럼 보입니다. 캔버라 거리 (Canberra distance)는 이러한 문제를 완화하기 위해 고안된 거리입니다 (고안한 연구자가 캔버라에 살아서 맨해튼 거리의 패러디처럼 이름을 지었다고 하네요!). 캔버라 거리 $d_{Can}$는 다음과 같이 각 element의 크기로 맨해튼 거리를 나누어 스케일링합니다.
$$ d_{Can}(\mathbf{a},\mathbf{b}) := \sum_i^n {\frac{|\mathbf{a}_i-\mathbf{b}_i|}{|\mathbf{a}_i|+|\mathbf{b}_i|}} $$
두 번째로 $p=\infty$의 별칭은 쳬비셰프 거리 (Chebyshev distance), 혹은 체스 거리입니다.
$$ d_{chess}(\mathbf{a}, \mathbf{b}) := \lim_{p \rightarrow \infty} \left(\sum_{i=1}^n {|a_i-b_i|^p}\right)^{1/p} = max_{i}^{n}(|a_i-b_i|) $$
이는 사발팔방으로 거리가 같은데, 아래 그림과 같이 체스에서 킹이 이동할 수 있는 거리와 같아서 체스 거리라는 별명이 있습니다. 킹을 중심으로 체스 거리가 적혀 있습니다.
from Wikipedia 3-3. 마할라노비스 거리 (Mahalanobis distance)
위의 민코프스키 거리 친구들은 두 데이터 포인트 사이의 절대적인 거리를 나타냅니다. 하지만 데이터의 맥락에서 보면 절대적 거리는 적절하지 않을 수 있습니다. 예컨대, 아래와 같이 어떤 분포가 있다고 하겠습니다.
10,000개의 데이터 포인트에 대한 가우시안 분포 이때 1번에서 2번 사이의 거리와 3번과 4번 사이의 거리는 모두 1로 같습니다. 하지만, 1 $\rightarrow$ 2로의 이동보다 3 $\rightarrow$ 4로의 이동이 더 어려워 보입니다. 비유적으로 말하자면, 500명이 참가한 마라톤에서 300등에서 250등으로 이동하기는 쉽지만 55등에서 5등으로 이동하기는 어려울 것입니다. 절대적인 차이는 50등으로 같지만 말이에요! 이러한 관점에서 분포 상 더욱 드문 곳에 있는 데이터 포인트가 더 멀다고 생각해 볼 수 있습니다. 정보 이론적으로 말하면 더 놀라운(!) 사건이 더 멀리 있다고 말할 수도 있겠습니다.
그렇다면 '놀랍다'는 어떻게 수치화하면 좋을까요? 한 가지 좋은 방법은 큰 표준 편차를 가지는 데이터 포인트가 더 놀라운 친구라고 할 수 있습니다. 표준 편차를 고려하여 거리를 계산하기 위해, 마할라노비스 거리에서 우리는 공간을 기울여서 (선형 변환해서) 표준 편차를 보정한 이후에 유클리드 거리를 계산할 것입니다. 그림으로 나타내면 다음과 같이 직관적으로 이해해 볼 수 있습니다.
왼쪽의 데이터를 오른쪽으로 표준화한 뒤에 유클리드 거리 계산 위의 그림에서 왼편이 우리에게 주어진 데이터입니다. 10,000개의 데이터 포인트가 있고 우리는 그 중에서 A 사이의 거리와 B 사이의 거리를 계산하고 싶습니다. 단순히 유클리드 거리를 이용해서 A 사이 선분, B 사이 선분의 길이를 구하면 B 사이 선분이 더 깁니다.
하지만 마할라노비스 거리는 가정이 다릅니다. 우리가 원래 원하는 데이터 형태는 오른편과 같이 평균이 $\mathbf{0}$이고 분산이 항등 행렬인 표준 가우시안 형태입니다. 그런데 실제 우리에게 주어진 데이터는 모종의 사건이 발생해서 맥락이 생겨 버렸고 평균과 분산이 달라진 데이터입니다. 결과적으로 그러한 맥락 때문에 거리도 왜곡되어 버렸습니다. 그럼 어떻게 해야 할까요? 선형 변환을 통해서 원래의 형태로 바꾸어 준 이후에 유클리드 거리를 구하면 됩니다. 그러면 왼편에서 더 길어 보였던 B 사이의 거리가 사실은 A의 경우와 같다는 것을 알 수 있습니다. 이런 식으로 기저에 보다 간명한 형태의 모델이 존재한다는 가정은 데이터 분석에서 자주 사용됩니다.
맥락을 보정하여 마할라노비스 거리를 구하는 구체적인 방법은 다음과 같습니다. $n$차원에서 정의된 $m$개의 데이터 포인트가 존재하는 데이터 셋 $X \in \mathbb{R}^{m \times n}$이 있다고 하겠습니다. 먼저, 이 데이터를 이용해서 분산 $\hat{\Sigma}$를 추정합니다 (분산을 추정할 때 $m-1$로 나누는 이유는 불편추정치를 구하기 위함인데, 여기서 자세히 다루지는 않겠습니다).
$$ \hat{\Sigma} = \frac{1}{m-1}X^tX \in \mathbb{R}^{n \times n} $$
바로 이 $\hat{\Sigma}$가 표준 가우시안을 기울여서 맥락을 발생시킨 원인입니다. 이를 역으로 변환하려면 분산의 역행렬을 곱해주면 됩니다. 따라서 마할라노비스 거리 $d_{Mh}$는 아래와 같이 정의됩니다.
$$ d_{Mh} := \sqrt{(\mathbf{a}-\mathbf{b})^t\hat{\Sigma}^{-1}(\mathbf{a}-\mathbf{b})} $$
이렇게 두고 보니, 유클리드 거리는 분산 $\Sigma$가 항등 행렬인 마할라노비스 거리라는 사실을 알 수 있습니다. 결국 유클리드 거리는 마할라노비스 거리의 특수한 형태입니다. 조금 복잡하게 생각하면, 유클리드 거리를 사용하다는 것은 기저에 보다 간명한 형태인 표준 가우시안이 존재한다고 생각하지 않는다..., 혹은 최소한 그런 가정이 나의 분석에는 별로 효과적이지 않을 것이다...라는 분석가의 믿음을 반영한다고 볼 수도 있습니다.
3-4. 각도 기반 거리
거리는 각도의 관점에서도 볼 수 있습니다. 두 데이터 포인트가 이루는 각도가 작으면 더 가깝고, 각도가 크면 더 멉니다. 각도와 거리가 관계있다는 개념은 아래의 그림으로 직관적으로 이해할 수 있습니다.
세 데이터 포인트와 그것들이 이루는 각도 위의 그림에 세 데이터 포인트, $\mathbf{a},\mathbf{b},\mathbf{c}$와 두 각도, $\theta, \phi$가 표현되어 있습니다. $\mathbf{a},\mathbf{c}$ 중에 $\mathbf{b}$에 더 가까운 친구는 누구일까요? 딱 봐도 $\mathbf{a}$가 더 가까워 보입니다.
그렇다면 이제 $\mathbf{a}$가 더 가깝다는 것은 알겠는데, 얼마나 가까운지 수로 나타내고 싶어집니다. 이때 사용하는 것이 각도 $\theta, \phi$입니다. $\theta$가 $\phi$보다 작은 만큼 $\mathbf{a}$가 더 가깝다...고 보는 것입니다. 하지만 단순히 각도를 그대로 사용하면 몇 가지 문제가 있습니다. 180까지는 각도와 비유사도가 같이 늘어나지만, 180 ~ 360까지는 각도가 커질수록 비유사도가 감소합니다. 그럼 180까지만 쓰면 되는 거 아닌가요?...라는 생각은 좋은 생각이지만 여전히 수가 너무 쑥쑥 커져서 스케일을 안정적으로 만들어야 할 필요가 있습니다.
그래서 보통은 코사인 유사도(cosine similarity)를 사용합니다. $\theta$각을 이루는 두 데이터 포인트 $\mathbf{a},\mathbf{b}$의 코사인 유사도 $S_{cos}$은 다음과 같이 정의됩니다. 여기서 $\bullet$은 dot product 연산자입니다.
$$ S_{cos}(\mathbf{a},\mathbf{b}) := cos(\theta) = \frac{\mathbf{a} \bullet \mathbf{b}}{||\mathbf{a}||_2||\mathbf{b}||_2} $$
where
$$ 0 \leq \theta \leq \pi $$
위의 식을 조금 더 자세히 살펴보면, 코사인 유사도는 데이터 포인트의 위치는 무시한다는 것을 알 수 있습니다. 벡터의 길이는 스칼라이기 때문에 식을 다음과 같이 다시 적을 수 있습니다.
$$ \frac{\mathbf{a} \bullet \mathbf{b}}{||\mathbf{a}||_2||\mathbf{b}||_2} =\frac{\mathbf{a}}{||\mathbf{a}||_2} \bullet \frac{\mathbf{b}}{||\mathbf{b}||_2} $$
이렇게 두고 보면 $\mathbf{a}/{||\mathbf{a}||_2}$와 $\mathbf{b}/{||\mathbf{b}||_2}$는 둘 다 유클리드 노름으로 정규화된, 길이가 1인 벡터입니다. 따라서, 코사인 유사도는 두 데이터 포인트를 비교할 때, 길이를 정규화하여 1로 만들어 데이터 포인트의 위치는 무시하고 각도로만 계산하는 방식입니다. 다른 말로, 데이터 포인트를 전부 단위 원에 올려 두고 각도를 구한다고 생각할 수도 있습니다.
마지막으로 코사인 유사도는 $( 0 \leq \theta \leq \pi )$ 조건에 따라 $[-1, 1]$ 사이의 값을 가지게 됩니다.
0 ~ $\pi$의 코사인 함수 따라서 코사인 비유사도 $d_{cos}$은 다음과 같이 정의할 수 있습니다.
$$ d_{cos}(\mathbf{a},\mathbf{b}) := 1-S_{cos}(\mathbf{a},\mathbf{b}) $$
그런데 위치를 무시하는 것이 과연 옳은 일인가...?라는 의문이 생길 수 있습니다. 하지만 위치 기반 거리들, 예컨대 유클리드 거리를 사용했을 때 발생하는 문제가 있습니다. 특히 텍스트 데이터일 경우에 그런데요. 텍스트 데이터는 각 데이터 포인트 별로 담고 있는 정보의 양이 많이 차이나고는 합니다. 예를 들어, 비슷한 내용을 담고 있지만 단어의 양에서 차이가 나는 긴 문서 $\mathbf{a}$와 짧은 문서 $\mathbf{b}$가 있다고 하겠습니다. 그리고 그 문서들에 어떤 단어가 얼마나 많이 등장하는지 적어 둔 단어-문서 행렬(term-document matrix)이 아래 표와 같다고 하겠습니다.
등장하는 단어와 단어가 등장한 빈도 표에서 볼 수 있듯이 두 데이터 포인트를 벡터로 나타내면 $\mathbf{a} = [1245, 1345, 342, \ldots], \mathbf{b} = [223, 332, 41, \ldots]$가 됩니다. 이때 두 데이터 포인트가 이루는 각도는 작을 수 있습니다. 하지만 벡터 각 요소의 절대적인 크기가 크게 차이나기 때문에 두 데이터 포인트의 위치도 크게 차이날 수 있습니다. 마치 아래 그림처럼 말이에요! 이에 더해서, 텍스트는 의미(semantic)가 방향으로 표현되는 경향이 있기 때문에 텍스트를 다룰 때에는 각도 기반 거리를 자주 사용합니다.
코사인 유사도는 크지만 유클리드 거리는 먼 예시 만약에 나는 각도, 위치 둘 다 포기하고 싶지 않다...고 하면 삼각형(또는 arc의)의 넓이를 사용할 수 있다고 합니다. 위의 그림에서 보자면 원점, $\mathbf{a}$, $\mathbf{b}$ 세 점이 이루는 삼각형의 넓이를 두 데이터 포인트 사이의 거리로 사용하는 것입니다. 그런데 대중적인 방법은 아니고, (저의 일천한 경험으로 정확한 이유는 잘 모르겠지만) 잘 안 쓰이는 데에는 다 이유가 있는 것 같으니 생략하도록 하겠습니다 :-)
코사인 유사도를 알아본 김에 그 연장선상에서 피어슨 상관계수도 알아보면 좋을 것 같습니다. 피어슨 상관계수는 두 데이터 포인트 사이의 공분산을 분산으로 교정한 계수이지만, 코사인 유사도의 관점에서도 볼 수 있습니다. 피어슨 상관계수 $corr$은 코사인 유사도 $S_{cos}$를 이용하여 다음과 같이 계산됩니다. 여기에서 $\bar{\mathbf{a}}, \bar{\mathbf{b}}$는 각각 $\mathbf{a}, \mathbf{b}$의 평균입니다.
$$ corr(\mathbf{a},\mathbf{b}) = S_{cos}(\mathbf{a} - \bar{\mathbf{a}},\mathbf{b} - \bar{\mathbf{b}}) $$
피어슨 상관계수 또한 코사인 유사도이기 때문에 $[-1, 1]$의 범위를 가집니다. 따라서 코사인 거리와 비슷하게 피어슨 상관계수 거리 $d_{corr}$도 다음과 같이 계산하고는 합니다.
$$ d_{corr}(\mathbf{a},\mathbf{b}) = 1 - corr(\mathbf{a},\mathbf{b}) $$
피어슨 상관계수는 왜 사용하는 것일까요? 가장 큰 이유는 스케일에 구애받지 않기 때문입니다. 코사인 유사도에서 하나의 벡터에 $\mathbf{1}$을 감산한 이후에 계산하면 결과값이 바뀌지만, 피어슨 상관계수는 그렇지 않습니다. 한 마디로 피어슨 상관계수는 통계 첫 시간에 배우는 스케일의 종류 (명목 척도, 서열 척도, ...) 중에서 등간 척도를 위한 통계치입니다. 즉, 피어슨 상관계수는 데이터에 절대영이 없고 스케일에 따라 의미가 바뀌지 않는다고 가정합니다. 사회 과학에서 코사인 유사도 대신에 피어슨 상관계수를 많이 활용하는 것도 이러한 가정 때문입니다. 예컨대, '세상을 사랑하는 마음' 설문지 (0 ~ 30점)에서 0점을 받은 사람은 정말 세상을 하나도 사랑하지 않는다기보다는 1점보다 덜 사랑한다는 것 뿐이고, 설문지가 측정할 수 없을 뿐이지 0점보다 아래인 사람도 존재할 수 있습니다. 비슷하게, 23점을 받은 사람도 22점보다는 더, 24점보다는 덜 사랑하는 것이지, 정말 진리값이 23이라는 이야기는 아닙니다. 마찬가지 논리로, 모든 사람들의 점수에 1씩 더해서 1 ~ 31점 척도로 바꾼다고 해서 앞의 의미들이 바뀌지는 않습니다. 반대로, 주어진 데이터가 세상을 정확하게 반영한다고 믿으면 코사인 유사도가 더 좋을 수 있습니다. 물론 이런 가정이 반드시 지켜야 하는 황금률은 아니지만, 한번쯤 생각해 보면 재밌습니다...는 장점이 있습니다.
마지막으로 코사인 유사도와 유클리드 거리 사이의 관계를 알아보겠습니다. 노테이션을 계속 이어서 사용하면, 유클리드 거리 제곱을 벡터 형태로 적으면 아래와 같습니다.
$$ d_E(\mathbf{a}, \mathbf{b})^2 = ||\mathbf{a} - \mathbf{b}||_{2}^{2} = (\mathbf{a} - \mathbf{b})^t (\mathbf{a} - \mathbf{b}) $$
$$ = \mathbf{a}^t \mathbf{a} + \mathbf{b}^t \mathbf{b} - 2\mathbf{a}^t \mathbf{b} $$
이때 두 데이터 포인트가 $L^2$ 정규화되어 있다고 가정하면 길이가 1이므로 최종적으로 다음과 같이 정리됩니다.
$$ = 1 + 1 - 2 \cdot \mathbf{a} \bullet \mathbf{b} $$
이때 코사인 유사는 $L^2$ 정규화에 의해 다음과 같습니다.
$$ S_{cos}(\mathbf{a}, \mathbf{b}) = \frac{\mathbf{a} \bullet \mathbf{b}}{||\mathbf{a}||_2||\mathbf{b}||_2} = \mathbf{a} \bullet \mathbf{b} $$
그리고 유클리드 거리, 코사인 유사도, 코사인 거리 사이의 관계를 보면, 다음과 같습니다.
$$ d_E^2 = 2 -2S_{cos} = 2(1 - S_{cos}) = 2d_{cos} $$
3-5. 하버사인 거리 (Haversine distance)
하버사인 거리는 구 위에 있는 두 지점 사이의 최단 거리를 의미합니다. 지도 앱에서 두 지점 사이의 거리를 계산할 때에도 지구를 구체라고 가정하고 하버사인 거리를 구한다고 합니다.
'Haversine'이라는 이름은 풀어 말하면 'Half versed sine'입니다. 이름 그대로 하버사인 함수 $hav$는 아래와 같이 정의됩니다. 어떤 각도 $\theta$에 대해,
$$ hav(\theta) = {sin}^2\frac{\theta}{2} = \frac{1-cos(\theta)}{2}$$
이때 각을 이루는 구 위의 두 좌표가 위도 $\phi_1, \phi_2$와 경도 $\lambda_1, \lambda_2$로 표현되어 있다고 하고 하버사인 함수를 풀면 아래와 같습니다.
$$ hav(\theta) = hav(\phi_2-\phi_1) + cos(\phi_1)cos(\phi_2)hav(\lambda_2-\lambda_1) $$
즉, 우리는 이제 각도를 좌표만으로 계산할 준비를 마친 셈입니다. 이를 이용하여 아래의 사실에서 두 좌표 간의 최단 거리인 $d_{Hav}$를 구하면 됩니다.
$$ \theta = \frac{d_{Hav}}{r} $$
이 식을 풀기 위해서 $hav$의 역함수 $archav$를 생각하면 $d_{Hav}$는 다음과 같이 정리됩니다.
$$ d_{Hav} = r \times archav(hav(\theta)) = 2r \times arcsin(\sqrt{hav(\theta)}) $$
종종 데이터를 전부 하나의 구 위에 올려두었다는 가정 아래에서 분석을 시도할 때가 있는데, 만약 그 구를 고정해 놓을 계획이라면 하버사인 거리를 사용해 보는 것도 하나의 방법입니다.
3-6. 자카드 거리 (Jaccard distance)
이번에는 순서를 보존하지 않는 집합 사이의 거리를 측정하는 자카드 거리에 대해 알아보겠습니다.
자카드 거리는 두 집합 사이의 유사도를 나타내는 자카드 지수(Jaccard index), 혹은 자카드 계수(Jaccard coefficient)를 통해 계산한 거리입니다. 먼저, 두 집합 $A, B$에 대해 자카드 지수 $J$는 다음과 같이 정의됩니다. $n(.)$은 원소의 개수를 나타내는 함수입니다.
$$ J(A, B) := \frac{n(A \cap B)}{n(A \cup B)} $$
풀어 말하자면, 자카드 지수는 합집합의 원소 중에 교집합에도 포함되는 원소들이 얼마나 존재하는지 나타낸 것입니다. 정말 자연스럽지 않나요? 그리고 당연하게도 0과 1 사이의 값을 갖습니다. 이때, 자카드 거리 $d_J$는 다음과 같이 정의됩니다.
$$ d_J(A,B) := 1 - J(A,B) $$
이런 식으로 두 책 사이의 유사도를 계산해 볼 수 있습니다. 예컨대, $A$라는 책에 나오는 단어와 $B$라는 책에 나오는 단어를 두 개의 집합으로 생각하면 말이죠! 혹은, 비전 분야에서 정답 bbox와 기계가 예측한 bbox의 일치율을 픽셀 단위로 계산하는 데에 사용할 수도 있습니다.
만약에 순서가 없는 집합이 아닌 순서가 있는 벡터에 자카드 거리를 적용하려면 어떻게 하면 될까요? 이때에는 가중 자카드 거리(weighted Jaccard distance)를 사용합니다. 먼저, 두 벡터 $\mathbf{a} = [a_1, \ldots ,a_n], \mathbf{b} = [b_1, \ldots ,b_n]$가 있다고 하겠습니다 (단, $\mathbf{a}_i,\mathbf{b}_i \geq 0, \forall i$). 이때, 가중 자카드 거리 $d_{J_{W}}$와 가중 자카드 지수 $J_W$는 다음과 같이 정의됩니다.
$$ d_{J_{W}}(\mathbf{a}, \mathbf{b}) := 1 - J_W(\mathbf{a},\mathbf{b}) $$
where
$$ J_W(\mathbf{a},\mathbf{b}) := \frac{ \sum_i {min(\mathbf{a}_i, \mathbf{b}_i}) }{ \sum_i {max(\mathbf{a}_i, \mathbf{b}_i}) } $$
그런데 솔직히 이렇게 보아서는 대관절 저 최대 최소값이 의미하는 바가 무엇인지 잘 와닿지 않습니다. 하지만 따져보면 가중 자카드 지수도 꽤나 자연스러운 지수입니다.
먼저 최대 최소값은 다음과 같이 표현할 수 있습니다. 모든 $i$에 대해서,
$$ min(\mathbf{a}_i,\mathbf{b}_i) = \frac{\mathbf{a}_i+\mathbf{b}_i-|\mathbf{a}_i-\mathbf{b}_i|}{2} $$
$$ max(\mathbf{a}_i,\mathbf{b}_i) = \frac{\mathbf{a}_i+\mathbf{b}_i+|\mathbf{a}_i-\mathbf{b}_i|}{2} $$
입니다 (숫자 몇 개 넣어서 해 보면 당연한 소리입니다).
이때, 다음과 같이 가중 자카드 지수를 새로 표현할 수 있습니다.
$$ J_W(\mathbf{a},\mathbf{b}) = \frac{||\mathbf{a}||_1+||\mathbf{b}||_1-||\mathbf{a}-\mathbf{b}||_1}{||\mathbf{a}||_1+||\mathbf{b}||_1+||\mathbf{a}-\mathbf{b}||_1} $$
상황을 단순화하기 위해 $\mathbf{a},\mathbf{b}$가 $L^1$ 정규화되어 있다고 가정하면, $||\mathbf{a}||_1$과 $||\mathbf{b}||_1$의 크기는 바뀌지 않습니다. 따라서 $\mathbf{a}$와 $\mathbf{b}$ 사이의 맨해튼 거리인 $||\mathbf{a}-\mathbf{b}||_1$가 커질수록 분모는 커지고 분자는 작아져서 결국 가중 자카드 지수는 작아집니다. 한 마디로, 맨해튼 거리에 비례해서 작아지는 유사도...라고 생각해 볼 수 있겠네요! 그리고 그러한 유사도를 1에서 감산한 것이 가중 자카드 거리입니다.
자카드 거리와 비슷하게 집합을 대상으로 하는 다이스 거리(Dice distance)가 있어서 간략하게 소개하겠습니다. 다이스 거리 $d_{D}$는 다이스 계수 $D$를 통해 계산됩니다.
$$ d_D(A, B) = 1 - D(A, B) $$
where
$$ D(A, B) = \frac{2n(A\cap B)}{n(A) + n(B)} $$
이외에도 타니모토 계수(Tanimoto coefficient), 중복 계수(overlap coefficient) 등이 집합을 대상으로 하는 유사도입니다.
3-7. 편집 거리 (Edit distance)
편집 거리는 한 데이터를 얼마나 많이 편집(수정)해야 다른 데이터를 만들어 낼 수 있는지...를 거리로 삼습니다. 다양한 편집 거리 중에 가장 많이 사용되는 해밍 거리(Hamming distance)와 레벤슈타인 거리(Levenshtein distance)에 대해 알아보겠습니다.
해밍 거리는 수식보다는 직관적으로 이해하는 편이 좋은 것 같습니다. 간단히 이야기하면, 해밍 거리는 순서가 있는 데이터가 일치하지 않는 부분의 개수...입니다. 아래 두 단어를 보겠습니다.
글자를 기준으로 구한 두 단어 사이의 해밍 거리 categorical이라는 단어와 cathedral이라는 단어는 알파벳으로 되어 있습니다. 그리고 알파벳은 4곳에서 일치하고 7곳에서 일치하지 않습니다. 그렇다면 두 단어 사이의 해밍 거리는 7입니다.
해밍 거리의 대표적인 단점은 데이터 크기가 같아야 한다는 것입니다. 위의 예시에서는 그냥 머리 글자를 일치시키는 방식을 사용했지만 엄밀하게 이야기하면 어떻게 길이를 맞출 것인지가 골치거리입니다.
이런 문제를 해결하는 편집 거리로는 레벤슈타인 거리가 있습니다. 레벤슈타인 거리는 해밍 거리처럼 단순히 다르면 1, 같으면 0이 아니라 약간 더 복잡한 방법을 따릅니다. 한 단어에서 글자를 바꾸거나, 지우거나, 추가할 때마다 비용이 1 증가하고, 한 단어를 다른 단어로 완벽하게 바꿀 때까지 소요된 최소 비용이 레벤슈타인 거리가 됩니다.
이번에도 예시를 통해 레벤슈타인 거리를 이해해 보겠습니다. 가장 유명한 예시는 'kitten'과 'sitting' 사이의 거리입니다.
k i t t e n $\rightarrow$ k i t t e n : {cost = 0} 변경하지 않으면 비용 0 발생
k i t t e n $\rightarrow$ s i t t e n : {cost = 1} k를 s로 변경해서 비용 1 발생
s i t t e n $\rightarrow$ s i t t i n : {cost = 1} e를 i로 변경해서 비용 1 발생
s i t t i n $\rightarrow$ s i t t i n g : {cost = 1} g를 추가해서 비용 1 발생
total cost = 3레벤슈타인 거리는 수식으로 계산하는 것은 아니고 알고리즘을 이용해서 구합니다. 알고리즘은 다음과 같습니다. 먼저 텍스트 맨 앞의 한 칸은 빈 칸으로 두고 표를 만듭니다. 그리고 첫 행, 첫 열에 0부터 차례대로 숫자를 씁니다.
알고리즘 실행 준비 완! 이후에는 아래의 규칙에 따라 알고리즘을 진행합니다.
1. 0에서 시작하여 오른쪽 아래 방향으로 내려가며 진행한다.
2. 비용이 발생하지 않으면 왼쪽 위의 숫자를 그대로 가져와 적는다.
3. 비용이 발생할 경우...
3-1. 변경이 필요하면 왼쪽 위의 숫자 +1을 적는다.
3-2. 삽입이 필요한 경우 위의 숫자 +1을 적는다.
3-3. 삭제가 필요한 경우 왼쪽 숫자 +1을 적는다.
4. 최우하단에 도달할 때까지 반복한다.위의 알고리즘을 완료하면 아래와 같은 결과가 나오는데, 최우하단에 있는 것이 바로 레벤슈타인 거리입니다!
알고리즘 완!
4. 어떤 걸 어떻게 써야 하는지?
이번 글에서는 두 데이터 포인트 사이의 비유사도를 측정하는 몇 가지 기초적인 방법을 알아 보았습니다. 당연하게도 두 데이터 포인트 사이의 비유사도 지수는 셀 수 없이 많고, 데이터 포인트 간이 아닌 대상(*e.g., 분포, 모델)의 비유사도 지수는 더 많을 것입니다.
그럼 클러스터링에서는 도대체 어떤 걸 어떤 상황에서 어떻게 사용해야 할까요?
결론적으로 만병통치약 비유사도 같은 건 없습니다. 물론 경험적인 가이드라인은 있습니다. 이상치 탐지에는 마할라노비스 거리를 많이 사용합니다. 텍스트 데이터에는 각도 기반 거리를 많이 사용합니다. 그런데 그렇다고 해서 텍스트 데이터에 마할라노비스 거리를 사용하면 무조건 망하느냐...그건 아닙니다. 주어진 데이터와 분석 목적, 그리고 각 비유사도의 성격을 잘 알고 상황에 맞추어 대처하는 것이 좋습니다. 그리고 뭔가 뭔가... 뭔가 중요한 것(!)을 심각하게 위배하지 않는다면 자기 나름의 비유사도를 고안해 보는 것도 방법입니다. 예를 들어서, 이 글에서는 1에서 유사도를 감산해서 비유사도를 구하는 방식을 많이 사용했지만 역수를 취해볼 수도 있습니다. 혹은 비유사도를 적절히 스케일링하거나, 여러 개의 비유사도를 앙상블 해 볼 수 있습니다.
다음 글부터는 본격적으로 클러스터링은 어떻게끄름 하면 되는지 공부해 보도록 하겠습니다.
5. 참고 문헌
http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/36928.pdf
'clustering' 카테고리의 다른 글
[클러스터링] K-means의 다양한 확장 (0) 2023.03.08