문서 유사도 측정
20 Apr 2017 | Document Similarity
이번 글에서는 문서 유사도를 측정하는 몇 가지 지표에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
유사도?
유사도(similarity)란 비슷한 정도를 나타내는 지표를 뜻합니다. 하지만 ‘비슷하다’는 단어의 어감에서도 알 수 있듯 굉장히 주관적인 지표입니다. 이를 정량화하는 노력이 필요한데요. 자연언어처리(Natural Language Processing) 분야에서 정의하는 유사도 지표의 속성 몇 가지를 나열해 보도록 하겠습니다.
(1) 두 객체간 유사성은 둘이 공유하는 속성이 많을 수록 증가한다.
(2) 개별 속성은 서로 독립(independent)이며, 추가가 가능하다.
(3) 각 속성이 갖는 추상화 레벨이 동일해야 한다.
(4) 유사성은 개념구조(conceptual structure)를 설명하는 데 충분해야 한다.
(1)은 직관적으로 이해가 가능할 것 같고요. (2)의 경우 예컨대 한 문서가 하나의 객체이고 이 문서가 5개 변수로 이뤄져 있다면 각 변수는 서로 무상관(uncorrelated)이라는 뜻이 됩니다. 이 문서를 벡터공간(vector space)에 표현했을 때 각 변수에 대응하는 기저(basis)는 서로 수직이라는 말로도 이해할 수 있을 것 같습니다. 아울러 변수를 6개, 7개… 이렇게 추가도 가능합니다.
(3)의 경우 각 변수가 커버하는 개념 영역이 비슷해야 한다는 취지로 받아들이면 될 것 같습니다. 예컨대 첫번째 변수가 ‘자동차’인데, 두번째 변수가 ‘아반떼’라면 해당 변수들로부터 추출한 유사도가 정확성을 갖기 어려울 것입니다. (4)는 유사도가 높은 객체들은 의미적으로도 비슷하다는 뜻으로 해석됩니다.
문서 간 유사도를 측정하는 지표는 여럿 제안되었습니다만, 대체로 단어(word, term) 수준의 방법론들입니다. 두 문서에 겹치는 단어가 많을수록 유사도가 높다는 결과를 내놓는 식입니다. 단어 수준의 유사도 측정은 (1) 문서 길이 (2) 동시 등장 단어 (3) 흔한/희귀한 단어 (4) 출현 빈도 등을 어떻게 처리하는지에 따라 다양한 방법론이 있습니다. 이번 글은 이와 관련한 여섯가지 측정 지표에 대해 살필 예정입니다.
Notation
앞으로 설명해드릴 여섯가지 지표를 계산하는 데 쓰이는 표현들에 대해 정리해보도록 하겠습니다.
- $x_{ik}$는 $i$번째 문서에 $k$번째 단어가 몇번 등장했는지 빈도를 나타냅니다.
- $t_{ik}$는 $x_{ik}$가 0 이상이면 1, 그렇지 않으면 0의 값을 갖습니다.
- $a_{ij}$, $b_{ij}$, $c_{ij}$, $d_{ij}$는 $t$를 바탕으로 구하는데요. 각각 아래 표와 같습니다. 아래 표에서 Y는 어떤 단어가 해당 문서에 쓰인 경우를, N은 쓰이지 않은 경우를 뜻합니다. $a_{ij}$, $b_{ij}$, $c_{ij}$, $d_{ij}$는 각각에 해당하는 단어 수를 나타냅니다.
$Doc_i$||$Doc_j$
Y
N
Y
$a_{ij}$
$b_{ij}$
N
$c_{ij}$
$d_{ij}$
예시 table
아래 표는 앞으로 설명드릴 지표에 대한 이해를 돕기 위한 예시입니다.
$x_{ik}$(빈도)
$Doc_1$
$Doc_2$
$Doc_3$
$Term_1$
3(=$x_{11}$)
0(=$x_{21}$)
2(=$x_{31}$)
$Term_2$
0(=$x_{12}$)
0(=$x_{22}$)
1(=$x_{32}$)
$Term_3$
5(=$x_{13}$)
3(=$x_{23}$)
0(=$x_{33}$)
$Term_4$
0(=$x_{14}$)
2(=$x_{24}$)
1(=$x_{34}$)
$Term_5$
0(=$x_{15}$)
1(=$x_{25}$)
2(=$x_{35}$)
아래 표는 등장여부를 binary로 표시한 결과입니다. 같은 말뭉치에서 도출된 표입니다.
$t_{ik}$(binary)
$Doc_1$
$Doc_2$
$Doc_3$
$Term_1$
1(=$t_{11}$)
0(=$t_{21}$)
1(=$t_{31}$)
$Term_2$
0(=$t_{12}$)
0(=$t_{22}$)
1(=$t_{32}$)
$Term_3$
1(=$t_{13}$)
1(=$t_{23}$)
0(=$t_{33}$)
$Term_4$
0(=$t_{14}$)
1(=$t_{24}$)
1(=$t_{34}$)
$Term_5$
0(=$t_{15}$)
1(=$t_{25}$)
1(=$t_{35}$)
Doc1과 Doc2에 대해 $a_{12},b_{12},c_{12},d_{12}$를 각각 구해보겠습니다. Doc1에는 등장했는데 Doc2에는 등장하지 않은 단어는 Term1 하나뿐이므로 $b_{12}$은 1입니다. Doc1에는 등장하지 않았는데 Doc2에 나온 단어는 Term4와 Term5 두 개이므로 $c_{12}$는 2입니다. 두 문서 모두 등장한 단어는 Term3 하나, 두 문서에 모두 나오지 않은 단어는 Term2 하나이므로 $a_{12}$, $d_{12}$는 각각 1입니다.
$Doc_1$||$Doc_2$
Y
N
Y
1(=$a_{12}$)
1(=$b_{12}$)
N
2(=$c_{12}$)
1(=$d_{22}$)
common features model
$i$번째 문서와 $j$번째 문서에 동시에 등장한 단어수를 전체 단어수로 나누어 구합니다. 보통 전체 말뭉치에 등장하는 단어수가 10만개에 육박하기 때문에 $d_{ij}$가 매우 큽니다. 따라서 이처럼 계산하는 유사도는 대체로 0에 가까운 작은 값을 지닙니다. 계산방법과 예시는 아래와 같습니다.
\[{ s }_{ ij }^{ common }=\frac { { a }_{ ij } }{ { a }_{ ij }+{ b }_{ ij }+{ c }_{ ij }+{ d }_{ ij } }\]
common
Doc1
Doc2
Doc3
Doc1
-
1/5
1/5
Doc2
-
2/5
Doc3
-
ratio model
common features model에서 $d_{ij}$를 빼고 계산한 유사도입니다.
\[{ s }_{ ij }^{ ratio }=\frac { { a }_{ ij } }{ { a }_{ ij }+{ b }_{ ij }+{ c }_{ ij } }\]
ratio
Doc1
Doc2
Doc3
Doc1
-
1/4
1/5
Doc2
-
2/5
Doc3
-
simple matching coefficient
common features model의 식에서 분자와 분모에 $d_{ij}$를 반영해 구한 유사도입니다. common features model보다는 값이 큰 경향이 있습니다.
\[{ s }_{ ij }^{ smc }=\frac { { a }_{ ij }+{ d }_{ ij } }{ { a }_{ ij }+{ b }_{ ij }+{ c }_{ ij }+{ d }_{ ij } }\]
SMC
Doc1
Doc2
Doc3
Doc1
-
2/5
1/5
Doc2
-
2/5
Doc3
-
jaccard similarity
jaccard similarity는 아래와 같이 구합니다. ratio model과 본질적으로 유사하다고 합니다.
\[{ s }_{ ij }^{ jaccard }=\frac { \sum _{ k }^{ }{ min({ x }_{ ik },{ x }_{ jk }) } }{ \sum _{ k }^{ }{ max({ x }_{ ik },{ x }_{ jk }) } }\]
jaccard
Doc1
Doc2
Doc3
Doc1
-
3/11
2/12
Doc2
-
2/9
Doc3
-
overlap similarity
overlap simliarity는 아래와 같이 구합니다.
\[{ s }_{ ij }^{ overlap }=\frac { \sum _{ k }^{ }{ min({ x }_{ ik },{ x }_{ jk }) } }{ min(\sum _{ k }^{ }{ { x }_{ ik } } ,\sum _{ k }^{ }{ { x }_{ jk } } ) }\]
overlap
Doc1
Doc2
Doc3
Doc1
-
3/6
2/6
Doc2
-
2/6
Doc3
-
cosine similarity
cosine similarity는 아래와 같이 구합니다. 예시로 제시된 table을 행렬로, 각각의 문서에 해당하는 열을 벡터로 놓고 두 벡터를 아래와 같이 내적하게 되면 두 벡터가 이루는 각도(유사도)가 됩니다. 일반적으로 문서 유사도 계산시 가장 많이 쓰이는 방법입니다.
\[{ s }_{ ij }^{ cosine }=\frac { \sum _{ k }^{ }{ ({ x }_{ ik }\times { x }_{ jk }) } }{ \sqrt { (\sum _{ k }^{ }{ { x }_{ ik }^{ 2 } } )(\sum _{ k }^{ }{ { x }_{ jk }^{ 2 } } ) } }\]
common
Doc1
Doc2
Doc3
Doc1
-
0.6875
0.3254
Doc2
-
0.3380
Doc3
-
이번 글에서는 문서 유사도를 측정하는 몇 가지 지표에 대해 살펴보도록 하겠습니다. 이번 글 역시 고려대 강필성 교수님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
유사도?
유사도(similarity)란 비슷한 정도를 나타내는 지표를 뜻합니다. 하지만 ‘비슷하다’는 단어의 어감에서도 알 수 있듯 굉장히 주관적인 지표입니다. 이를 정량화하는 노력이 필요한데요. 자연언어처리(Natural Language Processing) 분야에서 정의하는 유사도 지표의 속성 몇 가지를 나열해 보도록 하겠습니다.
(1) 두 객체간 유사성은 둘이 공유하는 속성이 많을 수록 증가한다.
(2) 개별 속성은 서로 독립(independent)이며, 추가가 가능하다.
(3) 각 속성이 갖는 추상화 레벨이 동일해야 한다.
(4) 유사성은 개념구조(conceptual structure)를 설명하는 데 충분해야 한다.
(1)은 직관적으로 이해가 가능할 것 같고요. (2)의 경우 예컨대 한 문서가 하나의 객체이고 이 문서가 5개 변수로 이뤄져 있다면 각 변수는 서로 무상관(uncorrelated)이라는 뜻이 됩니다. 이 문서를 벡터공간(vector space)에 표현했을 때 각 변수에 대응하는 기저(basis)는 서로 수직이라는 말로도 이해할 수 있을 것 같습니다. 아울러 변수를 6개, 7개… 이렇게 추가도 가능합니다.
(3)의 경우 각 변수가 커버하는 개념 영역이 비슷해야 한다는 취지로 받아들이면 될 것 같습니다. 예컨대 첫번째 변수가 ‘자동차’인데, 두번째 변수가 ‘아반떼’라면 해당 변수들로부터 추출한 유사도가 정확성을 갖기 어려울 것입니다. (4)는 유사도가 높은 객체들은 의미적으로도 비슷하다는 뜻으로 해석됩니다.
문서 간 유사도를 측정하는 지표는 여럿 제안되었습니다만, 대체로 단어(word, term) 수준의 방법론들입니다. 두 문서에 겹치는 단어가 많을수록 유사도가 높다는 결과를 내놓는 식입니다. 단어 수준의 유사도 측정은 (1) 문서 길이 (2) 동시 등장 단어 (3) 흔한/희귀한 단어 (4) 출현 빈도 등을 어떻게 처리하는지에 따라 다양한 방법론이 있습니다. 이번 글은 이와 관련한 여섯가지 측정 지표에 대해 살필 예정입니다.
Notation
앞으로 설명해드릴 여섯가지 지표를 계산하는 데 쓰이는 표현들에 대해 정리해보도록 하겠습니다.
- $x_{ik}$는 $i$번째 문서에 $k$번째 단어가 몇번 등장했는지 빈도를 나타냅니다.
- $t_{ik}$는 $x_{ik}$가 0 이상이면 1, 그렇지 않으면 0의 값을 갖습니다.
- $a_{ij}$, $b_{ij}$, $c_{ij}$, $d_{ij}$는 $t$를 바탕으로 구하는데요. 각각 아래 표와 같습니다. 아래 표에서 Y는 어떤 단어가 해당 문서에 쓰인 경우를, N은 쓰이지 않은 경우를 뜻합니다. $a_{ij}$, $b_{ij}$, $c_{ij}$, $d_{ij}$는 각각에 해당하는 단어 수를 나타냅니다.
| $Doc_i$||$Doc_j$ | Y | N |
|---|---|---|
| Y | $a_{ij}$ | $b_{ij}$ |
| N | $c_{ij}$ | $d_{ij}$ |
예시 table
아래 표는 앞으로 설명드릴 지표에 대한 이해를 돕기 위한 예시입니다.
| $x_{ik}$(빈도) | $Doc_1$ | $Doc_2$ | $Doc_3$ |
|---|---|---|---|
| $Term_1$ | 3(=$x_{11}$) | 0(=$x_{21}$) | 2(=$x_{31}$) |
| $Term_2$ | 0(=$x_{12}$) | 0(=$x_{22}$) | 1(=$x_{32}$) |
| $Term_3$ | 5(=$x_{13}$) | 3(=$x_{23}$) | 0(=$x_{33}$) |
| $Term_4$ | 0(=$x_{14}$) | 2(=$x_{24}$) | 1(=$x_{34}$) |
| $Term_5$ | 0(=$x_{15}$) | 1(=$x_{25}$) | 2(=$x_{35}$) |
아래 표는 등장여부를 binary로 표시한 결과입니다. 같은 말뭉치에서 도출된 표입니다.
| $t_{ik}$(binary) | $Doc_1$ | $Doc_2$ | $Doc_3$ |
|---|---|---|---|
| $Term_1$ | 1(=$t_{11}$) | 0(=$t_{21}$) | 1(=$t_{31}$) |
| $Term_2$ | 0(=$t_{12}$) | 0(=$t_{22}$) | 1(=$t_{32}$) |
| $Term_3$ | 1(=$t_{13}$) | 1(=$t_{23}$) | 0(=$t_{33}$) |
| $Term_4$ | 0(=$t_{14}$) | 1(=$t_{24}$) | 1(=$t_{34}$) |
| $Term_5$ | 0(=$t_{15}$) | 1(=$t_{25}$) | 1(=$t_{35}$) |
Doc1과 Doc2에 대해 $a_{12},b_{12},c_{12},d_{12}$를 각각 구해보겠습니다. Doc1에는 등장했는데 Doc2에는 등장하지 않은 단어는 Term1 하나뿐이므로 $b_{12}$은 1입니다. Doc1에는 등장하지 않았는데 Doc2에 나온 단어는 Term4와 Term5 두 개이므로 $c_{12}$는 2입니다. 두 문서 모두 등장한 단어는 Term3 하나, 두 문서에 모두 나오지 않은 단어는 Term2 하나이므로 $a_{12}$, $d_{12}$는 각각 1입니다.
| $Doc_1$||$Doc_2$ | Y | N |
|---|---|---|
| Y | 1(=$a_{12}$) | 1(=$b_{12}$) |
| N | 2(=$c_{12}$) | 1(=$d_{22}$) |
common features model
$i$번째 문서와 $j$번째 문서에 동시에 등장한 단어수를 전체 단어수로 나누어 구합니다. 보통 전체 말뭉치에 등장하는 단어수가 10만개에 육박하기 때문에 $d_{ij}$가 매우 큽니다. 따라서 이처럼 계산하는 유사도는 대체로 0에 가까운 작은 값을 지닙니다. 계산방법과 예시는 아래와 같습니다.
\[{ s }_{ ij }^{ common }=\frac { { a }_{ ij } }{ { a }_{ ij }+{ b }_{ ij }+{ c }_{ ij }+{ d }_{ ij } }\]| common | Doc1 | Doc2 | Doc3 |
|---|---|---|---|
| Doc1 | - | 1/5 | 1/5 |
| Doc2 | - | 2/5 | |
| Doc3 | - |
ratio model
common features model에서 $d_{ij}$를 빼고 계산한 유사도입니다.
\[{ s }_{ ij }^{ ratio }=\frac { { a }_{ ij } }{ { a }_{ ij }+{ b }_{ ij }+{ c }_{ ij } }\]| ratio | Doc1 | Doc2 | Doc3 |
|---|---|---|---|
| Doc1 | - | 1/4 | 1/5 |
| Doc2 | - | 2/5 | |
| Doc3 | - |
simple matching coefficient
common features model의 식에서 분자와 분모에 $d_{ij}$를 반영해 구한 유사도입니다. common features model보다는 값이 큰 경향이 있습니다.
\[{ s }_{ ij }^{ smc }=\frac { { a }_{ ij }+{ d }_{ ij } }{ { a }_{ ij }+{ b }_{ ij }+{ c }_{ ij }+{ d }_{ ij } }\]| SMC | Doc1 | Doc2 | Doc3 |
|---|---|---|---|
| Doc1 | - | 2/5 | 1/5 |
| Doc2 | - | 2/5 | |
| Doc3 | - |
jaccard similarity
jaccard similarity는 아래와 같이 구합니다. ratio model과 본질적으로 유사하다고 합니다.
\[{ s }_{ ij }^{ jaccard }=\frac { \sum _{ k }^{ }{ min({ x }_{ ik },{ x }_{ jk }) } }{ \sum _{ k }^{ }{ max({ x }_{ ik },{ x }_{ jk }) } }\]| jaccard | Doc1 | Doc2 | Doc3 |
|---|---|---|---|
| Doc1 | - | 3/11 | 2/12 |
| Doc2 | - | 2/9 | |
| Doc3 | - |
overlap similarity
overlap simliarity는 아래와 같이 구합니다.
\[{ s }_{ ij }^{ overlap }=\frac { \sum _{ k }^{ }{ min({ x }_{ ik },{ x }_{ jk }) } }{ min(\sum _{ k }^{ }{ { x }_{ ik } } ,\sum _{ k }^{ }{ { x }_{ jk } } ) }\]| overlap | Doc1 | Doc2 | Doc3 |
|---|---|---|---|
| Doc1 | - | 3/6 | 2/6 |
| Doc2 | - | 2/6 | |
| Doc3 | - |
cosine similarity
cosine similarity는 아래와 같이 구합니다. 예시로 제시된 table을 행렬로, 각각의 문서에 해당하는 열을 벡터로 놓고 두 벡터를 아래와 같이 내적하게 되면 두 벡터가 이루는 각도(유사도)가 됩니다. 일반적으로 문서 유사도 계산시 가장 많이 쓰이는 방법입니다.
\[{ s }_{ ij }^{ cosine }=\frac { \sum _{ k }^{ }{ ({ x }_{ ik }\times { x }_{ jk }) } }{ \sqrt { (\sum _{ k }^{ }{ { x }_{ ik }^{ 2 } } )(\sum _{ k }^{ }{ { x }_{ jk }^{ 2 } } ) } }\]| common | Doc1 | Doc2 | Doc3 |
|---|---|---|---|
| Doc1 | - | 0.6875 | 0.3254 |
| Doc2 | - | 0.3380 | |
| Doc3 | - |
Comments