100만개(10^6)의 문서에 대해 중복 검사한다고 해보자.
이때 두 문서간 80%정도만 같으면 중복문서라고 가정한다.
가장 쉬우면서도 정확한 방법(Naive)으로는 두 문서를 뽑아서 Jaccard Similarity를 구하면 되는데, 두 문서의 비교작업만 5*10^11번 필요하고, 한 문서를 shingling한 dimention도 무시할 수 없으므로 time and space complexity 모두 어마어마한 작업이 된다.
참고로 Jaccard Similarity(Jaccard Index) 두셋(set)의 유사성을 표현하는 방법으로 (A,B의 교집합/A,B의 합집합) 으로 표현할 수 있다.
A={1,2,3,4,5}
B={1,3,5,7,9}
교집합={1,3,5}
합집합={1,2,3,4,5,7,9}
J(A,B)=3/7
먼저, 다음과 같이 문서를 shingling(우리말로 번역하면 기왓장?)하여 다차원의 키워드 vector로 변환해보자.
문서 c1에 'my name is jack', 문서 c2에 'your name is heidi'이란 문장이 있다면
2-gram shingling한 결과로 다음과 같은 셋을 얻게된다.
c1: 'my name','name is','is jack'
c2: 'your name','name is','is heidi'
이런식으로 2-gram단위의 연속된 단어로 묶어 쪼갠후 중복을 제거한 상태를 말한다.
shingling한 단어들로 다음과 같은 bit vector를 생성할 수 있다.
| 'my name' | 'your name' | 'name is' | 'is jack' | 'is heidi' |
c1 | 1 | 0 | 1 | 1 | 0 |
c2 | 0 | 1 | 1 | 0 | 1 |
XOR, AND의 bit연산만으로 쉽게 jaccard계수(1/5)를 구할 수 있지만, 아직 dimension이 줄어든 상태는 아니다.
min-hashing을 적용하여 5-dimension 문서에서 3-dimension signature를 구하는 과정은 다음과 같다.
| A | B | C | D | E |
c1 | 1 | 0 | 1 | 1 | 0 |
c2 | 0 | 1 | 1 | 0 | 1 |
| h1 | h2 | h3 |
c1 | A | D | C |
c2 | B | E | C |
c1 | 1 | 4 | 3 |
c2 | 2 | 5 | 3 |
'개발 > 빅데이타' 카테고리의 다른 글
Indexing Strategy (0) | 2013.04.03 |
---|---|
Association Rule (0) | 2013.01.22 |
composite key, chain map reduce예제 (0) | 2013.01.16 |
Hadoop - Chaining Multiple MapReduce (0) | 2013.01.16 |
Using composite key in Hadoop MapReduce (0) | 2013.01.16 |