Shingling

해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.

이번 모듈에서 다루는 데이터는 집합(=Set)으로 표현됩니다.

때문에 이번 포스팅에서는,

Document 데이터를 집합의 형태로 표현하는 방법 중 하나인 Shingling 에 대해 설명하고,

집합 간 유사도를 나타내는 측도인 Jaccard Similarity 에 대해 설명하겠습니다.

Shingling

Shingling 이란 텍스트 데이터(문서, 이메일 등)를 집합으로 표현하기 위한 방법입니다.

텍스트 데이터를 변환하는 방법은 여러가지가 있습니다.

이 중 Shingling 은 문서 데이터의 어휘 단위 (lexically) 특성을 집합으로 표현하는데 효과적인 방법입니다.

k-Shingles

k-shingle 은 문서(=document)에서 나타나는 k 개의 토큰의 시퀀스 입니다. 이 토큰은 문자나 단어 등이 될 수 있습니다.

문서는 문자열로 구성 되어 있습니다. 이번 모듈에서는 k-shingle 을 문서에 있는 k 길이의 부분 문자열(=substring) 으로 사용합니다.

그리고 각 문서는 문서에서 등장한 부분문자열, k-shingle 의 집합으로 표현할 수 있습니다.

예를 들어 문서 D 가 ‘abcdaba’ 의 문자열로 구성되어 있는 경우,

k=2 일 때, D는 집합 {‘ab’, ‘bc’, ‘cd’, ‘da’, ‘ba’} 로 표현합니다.

그림@@

여기서 유의해야 할 점은, 집합(=Set) 이라는 점입니다. 위 예시에서는 ‘ab’ 가 2번 나왔지만 집합에서는 한번만 표시됩니다.

shingle 의 변형에서는 set 대신 bag 을 사용하여 출현 빈도까지 고려하기도 합니다. 여기서는 집합을 사용합니다.

Choosing the Shingle Size

k-shingle 에서 k는 성능에 큰 영향을 미칩니다.

k가 작은 경우, k 길이의 문자 시퀀스는 대부분의 문서에서 나타나게됩니다.

이런 경우, 문장이나 구 단위에서 동일한 것이 없더라도 높은 자카드 유사도나 산출됩니다.

극단적으로 k=1 인 경우, 거의 모든 문서에 대해 1에 가까운 유사도를 갖게 될 것입니다. 문자에 대한 유사도만 파악할 수 있을 뿐, 문장이나 구, 단어 단위 유사도를 나타낼 수 없게 됩니다.

k가 너무 높은 경우에는 교집합 크기가 적어 유사성 있는 문서를 찾기가 어렵게 됩니다.

그래서 k 를 몇으로 설정하는냐는 중요한 이슈입니다.

k의 크기는 사용되는 일반적인 문서의 크기와, 문자 집합의 크기에 따라 조정합니다.

k는 문서에서 주어진 shingling 이 있을 확률이 충분히 낮은 것으로 선택되어야 합니다.

이메일을 처리하는 경우, k=5 가 적당합니다.

영문 수(26) 과 공백 문자(1) 가 이메일에서 나타난다고 보면, $27^5 = 14,348,907$ 개의 shingle 을 생성 가능합니다.

그리고 일반적으로 이메일은 문자 수가 14백만개보다 적으므로 k=5 을 사용하기 적합합니다.

Hashing Shingles

구현을 할 때, shingle 을 문자열 그대로 사용하게 되면 많은 용량을 차지합니다.

예를들어 9-shingle을 사용한다면, 전체 shingle 집합, 경우의 수를 표현하기 위해 $27^9$ 개의 문자를 사용하게 됩니다. 문자 자료형 하나당 1byte 이므로, 전체 shingle 을 표현하기 위해서는 약 7TB($\approx 27^9$) 의 용량이 필요합니다.

이것이 데이터 자체를 의미하는 것도 아니고, 인덱스일 뿐인데 7TB 를 사용하는 것은 너무 비효율적입니다.

때문에 문자열을 그대로 사용하지 않고,

문자열을 해시하여 만들어진 버켓을 사용합니다.

예를 들어 4byte 로 표현을 하고자 한다면,

0부터 $2^{32} -1$ 사이의 값이 나오는 해시 함수를 사용하여 문자열을 변환합니다.

앞선 9-shingle 같은 경우는 6byte ($2^{48}$) 만 사용하더라도 7TB 의 문자열을 대신할 수 있게됩니다.

Jaccard Similarity of Sets

자카드 유사도(=Jaccard Similarity)는 다음과 같이 정의됩니다.

집합 S 와 집합 T의 자카드 유사도 $SIM(S,T)$ 는

\[SIM(S,T) = \frac{|S \cap T| }{ |S\cup T|}\]

입니다.

그림@@

집합 S와 T의 합집합(=Union Set) 의 크기 분에

집합 S와 T의 교집합(=Intersection) 의 크기 입니다.

두 집합이 유사 할수록 1에 가까워집니다.

CV 분야에서 사용하는 IoU 와 동일한 원리입니다.

문서의 문자열로 만들어진 shingle 집합은 두 문서 간 유사도 비교를 위해 사용됩니다.

두 문서에서 출현한 전체 shingle 의 수를 분모로,

두 문서에서 모두에서 출현한 shingle의 수를 분자로 계산하여

자카드 유사도를 구할 수 있습니다.

이렇게 직접 비교하는 것은 시간이 오래걸리므로

이후 포스팅에서 몇가지 작업들을 수행하여 효율적으로 유사한 쌍을 찾습니다.