기존 문헌 간 유사도 계산방식의 한계와 TS-SS 공식

이 글은 A Heidarian, 2016, A Hybrid Geometric Approach for Measuring Similarity Level Among Documents and Document Clustering 논문의 내용과 이를 정리하고 구현한 깃헙의 코드(https://github.com/taki0112/Vector_Similarity)를 바탕으로 작성되었습니다.

문헌들 사이의 유사도를 계산하기 위해서 흔히 사용되는 방법은 문헌에 등장하는 색인어(단어)의 빈도를 파악하여 TF-IDF 등의 가중치를 반영하여 벡터화하는 것입니다. 일단 문헌이 벡터로 표현되게 되면 여러가지 수학적 기법을 통해 벡터 간 유사도를 계산할 수 있죠. 그 중 대표적으로 사용되는 것에는 코사인 유사도와 유클리드 유사도 등이 있습니다. 앞으로의 예시에서 A, B는 각각의 문헌을 나타내는 N차원의 벡터라고 가정할게요.

코사인 유사도(내적 계수)

코사인 유사도는 두 벡터를 단위벡터화 시킨뒤 내적하여 계산합니다. 두 문헌이 이루는 각도가 작을수록 코사인 유사도는 커지므로, 문헌의 크기와 상관없이 특정 단어가 등장한 비율만을 유사도 계산에 반영한다는 특징이 있습니다. 범위는 0~1이며 1이면 완전 일치, 0이면 두 문헌이 완전 수직인 경우겠죠.

널리 쓰이는 유사도 척도이지만 A Heidarian는 이 척도가 몇 가지 부분에서 약점이 있다고 지적했습니다.

 

1. 유일성 문제: 문헌 A가 주어져있고, 방향은 같지만 등장하는 색인어의 규모가 다른 문헌들 B,C,D가 있다고 할때 A-B, A-C, A-D의 유사도는 모두 같게 나오게 됩니다. 두 문헌이 이루는 각도가 같기때문에 발생하는것이지요.
2. 이진 값 문제: 위와 마찬가지로 같은 각도에 있고 색인어의 규모만 다른 문헌들을 비교할 경우 두 문헌이 완전히 일치한다는 결과를 얻게 됩니다. 즉 '밥'이 1번 나오고, '급식'이 2번 나온 문헌과 '밥'이 10번 나오고, '급식'이 20번 나온 문헌을 같은것으로 보게된다는 거죠. 두 문헌이 완전히 같다고 볼 순 없다고 저자는 주장합니다.

유클리드 유사도

반면 유클리드 계수는 전통적인 좌표 평면 상의 거리 계산 공식을 이용합니다. 두 문헌을 좌표 상에 찍었을때 실제로 얼마나 가까이 위치하는지를 보는것이죠. 이 경우는 두 문헌이 이루는 각도는 무시되고 거리만 유사도 계산에 반영됩니다. 이 경우 거리가 0인경우 완전 일치하고, 그 값이 커질수록 유사하지 않아집니다.

이 척도의 경우 코사인 유사도가 반영하지 못하는 색인어의 규모가 다른 경우를 식별해 낼 수 있다는 특징이 있으나, 반대로 두 문헌이 이루는 각도를 무시하기 때문에 등장하는 색인어 비율이 달라도 그 숫자가 유사하면 유사한 문헌이라고 판단해 버리는 단점이 있습니다.

A와 B,C,D는 같은 거리만큼 떨어져 있으므로 유클리드 방법으로는 유사도가 같게 측정됩니다. 하지만 A와 D보다는 A와 B가 방향 차원에서 더 유사한게 맞지 않을까요?

맨하튼 유사도

유클리드 거리가 대각선으로 최단 거리를 재는 방법이라면 맨하튼 거리의 경우 군인이 직각보행하는것 마냥 대각선 없이 축 방향으로만 직각직각으로 이동하여 재는 방법입니다. 대체적으로 유클리도 거리척도와 유사한 성질을 가지나 더 품질이 낮은 경향이 있습니다.(이론적으로만 다루고 실제로는 거의 안 쓰인답니다) 이 경우 역시 거리가 0인경우 완전 일치하고, 그 값이 커질수록 유사하지 않아집니다.

유클리드 거리나 맨하탄 거리를 일반화하여 P-norm거리를 다루기도 합니다.

P-norm 유사도

P-norm 유사도는 p값에 따라 그 성질이 변하는데 p가 1일 경우 맨하튼 유사도와 같고, 2일 경우 유클리드 유사도와 같습니다. 즉 유클리드/맨하탄 유사도를 임의의 p값에 대해 확장한 경우라고 할 수 있습니다. 거리 계수를 바탕으로 하는것이다 보니 서로서로 대체로 유사한 성질을 갖는다고 볼 수 있어요.

P-norm 유사도 척도들은 유클리드 유사도가 가지고 있는 단점들을 공유하고 있습니다. 즉, 이 거리기반 유사도 척도는 같은 계통이라고 보시면 되겠습니다. 

저자는 기존 유사도 척도들이 가지는 한계를 지적하며 아래와 같은 새로운 척도를 제시했는데요, 어떤 방법으로 유사도 척도를 제시했는지 살펴보죠.

삼각형 면적 유사도(Triangle's Area Similarity; TS)

저자가 제시한 TS척도는 두 문헌 A,B와 원점이 이루는 삼각형의 넓이를 통해 유사도를 계산합니다. 당연히 삼각형 면적은 0 이상의 값일 것이고, 0일때가 가장 유사한 것이겠죠. 두 선분의 길이와 그 끼인각을 알때 삼각형 넓이는 다음과 같이 계산됩니다.

다만 이 공식을 그대로 이용할 경우 A,B가 같은 각도를 이룰경우 항상 넓이가 0이 되므로 θ값을 10도 늘려서 사용한다고 합니다. 즉 정리하면 다음과 같이되겠죠. (여기서 α = 10도)

cosθ 값은 위의 코사인 유사도에서 구한값과 같으므로, 그것을 그대로 대입하여 계산하면 되겠습니다.

하지만 이 척도는 코사인 유사도에서 들었던 예시 그림에서 A-B가 보다 A-D가 더 유사하다고 측정하게 됩니다. 따라서 이것만으로는 부족하다는 것이죠.

부채꼴 면적 유사도(Sector's Area Similarity; SS)

그래서 저자는 SS척도를 함께 제시하고 있습니다. SS척도는 두 문헌 간의 유클리드 거리에 문헌 벡터의 크기 차이를 합한 값을 반지름으로 하는 부채꼴을 그려서 그 넓이를 유사도로 사용합니다. 그때 부채꼴의 각으로는 위의 TS공식에서 사용하는 끼인각과 같이 θ+α를 사용하구요. 반지름과 그 각을 알 때 부채꼴의 넓이는 다음과 같이 계산됩니다.

이때 반지름은 다음과 같구요,

각은 θ+α이니 결론적으로 SS유사도는 다음과 같습니다.

이 척도의 경우에는 두 문헌 벡터가 나타내는 각이 유사하고, 그 거리와 크기 차이가 작을수록 유사도가 강하게 나타납니다.

TS-SS 유사도

최종적으로 저자는 TS유사도와 SS유사도의 곱을 유사도 척도로 사용할 것을 제안했습니다. 둘을 곱해서 사용하면 서로의 약점을 보완하면서 높은 성능을 얻을수 있다고 하는군요. 계산 과정이 조금 까다롭긴 하지만 성능을 향상시킬수만 있다면야!

실제로 테스트 셋을 대상으로 실험한 결과 다음과 같이 purity 점수에서 높은 성능을 보였다고 저자는 밝히고 있습니다. 작은 규모의 데이터에서는 잘 안드러나지만 그 규모가 커질수록 높은 성능을 보인다고 합니다.

Dataset	Cosine	EucDist	TS-SS
20NewsGroup	0.46	0.45	0.86
7sector	0.73	0.69	0.75
WebKB	0.83	0.74	0.85
Classic4	0.92	0.80	0.95

소폭 상승한 것을 볼 수 있죠. 다음 번에 문헌 유사도 실험할 때는 TS-SS 척도를 사용해봐야겠네요.