[CS246] Finding Similar Items (2) - Shingling

Shinglings

$k$-Shinglings

document를 길이가 $k$인 문자열 집합으로 표현한다.

예를 들어 "abcdabd"에 대해 $k=2$인 2-shingling 집합은 {ab, bc, cd, da, ab, bd} 이다.

공백과 관련하여 몇까지 옵션이 가능하다. (blank, tab, newline 등)

일반적으로 $k=9,\ 9,\ 10$ 정도로 한다.

 

textually similar한 문서들은 많은 수의 shingling이 겹칠 것이다. 단순히 한단어를 바꾸는 것으로는  $k-1$ 거리만큼만 바뀐다. 

 

예를 들어 "The dog which chased the cat" 과 "The dog that chased the cat"을 비교해보자.

두 문장의 차이점은 오직 "g_which_c"에서만 발생한다. 

$k=2$라면, 3-shinglings은 g_w, _wh, whi, hic, ich, ch_, h_c 로 바뀔것이다. 

 

Choosing the Shingle Size

$k$ should be picked large enough that the probability of any given shingle appearing in any given document is low.

shingle size는 document의 성격에 따라 달라질 수 있다. 예를 들어 email의 경우라면 $k=5$ 여도 충분할 것이다. 이 경우 가능한 shingle은 (알파벳+공백=27개) $27^k = 27^5 = 14,348,907$ (약 1400만개) 이다. 하나의 이메일의 크기가 1400만개보다는 훨씬 적으므로, $k=5$는 적절한 크기일 것이다.

 

좀 더 자세히 계산을 해보자. 이메일에는 27개의 알파벳만 있는 것이 아니다. 그리고 모든 문자(알파벳과 특수문자 등)들은 동일한 확률로 등장하지 않는다. 대부분의 이메일은 공백이 대부분이고, z와 같은 문자는 덜 등장한다. 따라서 길이가 짧은 이메일이라도 5-shings는 공통 문자를 많이 포함하게 되고, 서로 관련 없는 이메일끼리도 비슷해보이는 (원하지 않는) 효과가 발생한다. 

 

연구에 따르면, 크기가 큰 문서에 대하여 $k=9$가 좋다고 한다. (출처: MMDS textbook)

 

Hashing Shingles as Tokens

위에서 설명한 것은 shinge로 substring을 이용한 것이다. 문자열을 그대로 이용하는 대신에 해시함수를 이용하여 길이가 $k$인 문자열을 정수로 매핑하여 document를 set으로 만들것이다. set은 document를 의미하고, 집합의 정수원소는 문서에 등장하는 $k$-shingle을 의미한다. 

예를 들어, 4바이트 정수를 이용할 경우, 9-shingle은 $0 \~ 2^{32}-1$ 의 정수로 표현된다. 이렇게 표현하면 데이터가 compact해지는 것 뿐만아니라 (hashed) shinge을 이용하여 조작(machine operation)이 가능하다. 9-shingle을 4바이트로 표현하면 $2^{32}$개의 sequence를 표현할 수 있다.

 

 

Characteristic Matrix

shingle set은 매우 크다. 우리가 해싱을 이용해 4바이트로 표현한다 하더라도, 약 4배의 공간이 더 필요하다. 그리고 문서의 개수가 매우 많다면, 이 set of shingle을 어떻게 저장할 것인가?

이런 문제는 후술할 signature라는 개념을 이용하여 해결할 수 있고 signature는 characteristic matrix를 이용하여 구한다.

 

전체집합 $\{ a,b,c,d,e \}$의 4개의 집합 $S_1 = \{ a,d \}, \ S_2 = \{ c \}, \ S_3 = \{ b,d,e \} ,\ S_4 \{ a,c,d \}$에 대하여 행렬로 표현하면 다음과 같다.

A matrix representing four sets (MMDS textbook)

characteristic matrix의 column은 집합을, row는 전체집합의 원소를 의미한다. 집합 $c$가 원소 $r$을 갖는다면 행렬의 $(r, c)=1$이고, 포함하지 않는다면 $(r, c)=0$이다.

 

주목할 점은 characteristic matrix는 데이터를 표현하기에 적절하지 않다. 이 행렬은 0과 1로만 표현되는데 너무 희소해지기(sparse) 때문이다.

 

Minhashing은 이러한 문제를 해결한다.