[ML] Clustering의 Distance Function의 종류

이번 포스팅에서는 저번 시간에 배웠던 Clustering 내용에 대한 추가적인 컨텐츠이다. 바로 Clustering을 실행할 때 데이터 간의 거리를 계산해야 하는데 '어떤 방법' 으로 계산을 할지에 대한 내용이다. 이번에는 하나의 주제에 대한 것이므로 별다른 목차 없이 바로 본론으로 들어가겠다. 앞으로 나올 내용들은 모두 거리는 계산하는 방법 중 하나인 Distance Function의 종류들이다.

 

1. Euclidian Distance 

중, 고등학교 시절 문과, 이과를 불문하고 수학을 공부했던 사람들에겐 모두 친숙한 공식일 것이다. 바로 유클리디안 거리 공식이다. 이름만 듣고 잘 모르겠는가? 그렇다면 공식을 보면 "아~!" 라고 나올지도 모른다. 유클리디안 거리 공식을 살펴보자.

 

유클리디안 거리 공식

하지만 이 유클리디안 거리 공식은 NLP(자연어 처리) 문제에서 큰 힘을 발휘하지 못한다. 왜냐하면 NLP 분야에서는 단어의 빈도수를 계산하게 되는데 예를 들어 'A'라는 문서에 'economic'이라는 단어가 10번 등장했고 'B'라는 문서에 'economic'이라는 단어가 100개가 등장했다고 하자. 이 때 'economic'이라는 단어가 10번 등장했던 100번, 1000번 등장했던 어찌됐든 해당 문서 A,B 두개 모두 주제가 경제와 관련된 주제임을 알 수 있을 것이다. 이 때 유클리디안 거리는 단순히 단어의 빈도수만들 계산하게 되어 비효율적인 방법으로 취급된다. 이를 극복하기 위해서 Cosine Similarity가 등장하게 된다. 

 

2. Cosine Similarity

이제 중, 고등학교 시절 들어보지 못했던 개념들이 등장한다. 긴장은 하되 쫄지는 말자! Cosine Similarity는 기본적으로 두 벡터들 사이의 각도를 계산하게 된다. 그래서 벡터의 크기(Magnitude)는 무시하되 벡터의 방향의 차이만 계산을 하게 된다. 따라서 위 1번의 유클리디안 거리가 NLP 분야에서  해결하지 못하는 문제를 해결하게 된다. 다음은 Cosine Similarity의 공식이다.

 

Cosine Similarity의 공식

 

하지만 Cosine Similarity는 상호상관 관계를 갖는 Feature들을 지니고 있는 데이터들간의 유사도는 계산을 잘 하지 못하는 단점을 갖고 있다.

 

그리고 Cosine Similarity와 관계가 있는 Cosine Distance라는 개념이 존재하는데 이는 간단하다. 바로 1에서 Cosine Similarity를 빼준 값이 Cosine Distance가 된다.

 

Cosine Distance = 1 - Cosine Similarity

 

이에 대한 쉬운 설명은 박지호님의 Weekly NLP 포스팅을 참고하길 바란다.

https://jiho-ml.com/weekly-nlp-5/

Week 5 - 얘랑 나랑 얼마나 비슷해?

 

3. KL(Kullback-Leibler) Divergence

Relative entropy 또는 Information Gain 또는 Information Divergence 라고도 부른다. KL Divergence는 두 확률분포의 차이를 계산하는 방식으로 여기서 차이는 실제 거리를 의미하는 것은 아님을 알아두자. KL Divergence 개념을 이해하기 위해서는 entropy라는 개념을 이해해야 수월한데 이는 머신러닝 포스팅 초반에서 Decision Tree를 다룰 때에 등장했던 개념이다.(Information Gain개념에 대해서도!)

 

어찌됬든 KL divergence는 예측확률의 entropy에서 실제확률의 entropy를 빼주어 구하게 된다. 따라서 KL divergence의 값은 0이상의 값이 나오게 되며, 예측확률이 실제와 가까울수록 0에 가까워지게 된다. 따라서 0에 가까워지게 함으로써 loss를 측정하는 기준으로도 사용이 가능하다. 

 

필자가 해당 개념을 이해할 때 유용하게 사용했던 참고 블로그 링크를 공유한다.

https://blog.naver.com/PostView.nhn?blogId=gyrbsdl18&logNo=221013188633

Cross Entropy 란 무엇인가 (information theory)

3. Mahalanobis Distance(마할라노비스 거리)

이 개념은 다변량 데이터에서 분포의 형태를 고려하여 거리를 재겠다는 아이디어에서 기원되었다. 다음 수식을 잠깐 살펴보자.

 

마할라노비스 거리의 공식

위 수식에서 노란색으로 칠해진 부분은 Covariance Matrix(공분산 행렬)을 의미한다. 이를 inverse matrix(역행렬)로 변형시킨 형태이다. 즉, 변수들간의 Correlation을 고려하겠다는 의미이다. 만약 변수들간에 모두 독립적이고 Variance(분산)가 1로 정규화된다면 그 때 공분산 행렬은 항등원 행렬이 되며 이 때 마할라노비스 거리는 유클리디안 거리와 같아진다.

 

변수들 간에 독립적일 때는 유클리디안 거리공식으로 변하게 된다.

 

다음의 그림을 보면서 마할라노비스 거리가 어떤 것인지 시각적으로 확인해보자.

 

어떤 별들이 더 가까운걸까?

 

위 그림은 변수들간에 Correlation이 있는 상태이며 위 두개의 별 중 어떤 것이 원점 (0,0)과 거리가 더 가까울까?

정답은 x축위에 놓여있는 별이다. 왜냐하면 동그라미로 그려진 등고선 같은 부분을 고려했을 때 x축에 놓여있는 별표가 y축에 놓여있는 별표보다 원점에 더 가까운 등고선에 위치하기 때문이다.

 

이 개념도 이해하기에 좋은 포스팅이 있어 공유한다.

https://godongyoung.github.io/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D/2019/02/11/Mahalanobis-and-MCD.html

[데이터분석 정리] Mahalanobis거리와 MCD 개인적 정리 · Go's BLOG

 

4. Hamming Distance

해밍 거리란 같은 길이를 가진 2개의 문자열에서 같은 위치에 있지만 서로 다른 문자의 개수 즉, 한 문자열을 다른 문자열로 바꾸기 위해 몇개의 글자를 바꿔주어야 하는지에 대한 계산 방식이다. 주로 컴퓨터 통신에서 문자열을 전송 할 때 몇 글자가 오류가 났는지 측정하는 방법으로 사용된다. 해밍 거리의 정의를 말로만 들어선 이해가 안될 것 같아 간단하게 예시를 들어 보겠다.

 

ex1) '123456' 과 '124466' 의 해밍 거리는 2이다.

ex2) 'toned' 와 'roses'의 해밍 거리는 3이다.