[데이터마이닝] 3. 유사항목 찾기(Finding Similar Items) -2 슁글링 shingling

싱글링

uni-gram,

bi-gram 

tri-gram

example : k= 2; doc = abcab. set of 2-shingles = {ab,bc,ca}

combi(a,b,c,d)?

 

silding 기반의 k-shingle을 이용할 경우에  distance k-1정도만 영향을 받는다. 

2문단 3문단.. 순서가 바뀌면?

이렇다고 해도 similarity가 크게 바뀌지 않는다. 

출저: 스탠포드 제프리 디 울만

딱 핑크 네모 부분만 영향을 받는다. 

 

k-shingle을 compression을 해야한다.(공간을 너무 많이 차지하므로)

슁글의 개수가 너무 작으면 ...극단적으로 1이라고하면. 모든 doucment가 a-z까지 결국 모든 문서가 유사하다 라는 결론이 난다. 

k=10이면 26^10 1 bite짜리 10개 사용하면 256^10 -->너무 차이가 난다. 낭비가 심하다.

실제로 등장하는 슁글은 26^10보다 더 적다. 

 

4bytes정도 크기로 hash를 해보자 이것을 token이라고 한다. 

 

경우의 수 문제.. 이 부분에 대해서 다시 한번 생각해 보자.

 

슁글의 종류 자체가 많았으면 좋겠다. 너무 적으면 문서가 차별화되지 않는다.  다양한 슁글들을 가지게 해 주어야한다. 실제적으로 k는 8,9,10을 많이 쓴다.

26^10개의 슁글이 나올 수 있다. 그런데 컴퓨터에서는 문자 하나당 1byte를 할당하므로 1byte가 2^8= 256개를 표현할 수 있다.   실제로 256^10 = 1.208926e+24 을 표현할 수 있는공간을 잡아먹는 것. 

그래서 hahing하여 k=10이라고 했을대 아무 생각없이 10byte쓰지 말고  4byte로 줄인다. 256^4 =  4294967296 이는 26^10 = 1.411671e+14 보다 작다.  k =10이라고 해서 모든 문서에서  모든 경우의 수 인 26^10 이 다 나오진않는다. 실제로는 훨씬 덜 나오므로 256^4만큼만 써도 무방하다/