[데이터마이닝] 3. 유사항목 찾기(Finding Similar Items) - 1

주어진 많은 아이템 중에서 무엇이 input과 가장 비슷한가.?

모든 아이템을 비교해 보면 되지만. 그것은 사실상 불가능하다. 시간이 오래 걸리기 때문이다.  따라서 해싱을 이용한다

 

 

해싱이라는것은 굉장히 효율적인 방법이다. 

삽입 삭제 찾기 .. 해싱을 이용하면 O(1)이다. 

 

LSH는 해싱을 하는데 주변에 있는지(simillar)한지를 알아챌 수 있는것. 

 

모든 pair를 다 보지 않고 100*100 정도면 제곱에 비례하게 되는 이런 상황이 괜찮을수 있겠지만 더 커지면 힘들다. 

 

item을 hash bucket으로 여러 hash fuction을 써서 mapping한다. 비슷하다면 같은 bucket으로 mapping이 잘 될것이다. 

 

한번이라도 같은  bucket에 들어간 것들과 input과의 유사도를 구하면 효율적이다. 

 

너무 운이 없어서 같은 bucket으로 갔다면 어떻게 해야하는가?(false negatives가 발생한 것.) 

 

- lexically Similar documents

 - Entity resoultion : 데이터 베이스 테이블 내의 레코드들이 같은 사람,회사 를 표현하는 레코드를 찾아내는것. ex) A쇼핑몰과 B쇼핑몰이 고객들의 정보를 가지고 있는데 두 쇼핑몰이 합병된다. 그렇다면 같은 사람을 어떻게 찾아낼 것인가.  similar 한 record를 찾아서 같은 entity라고 여길 수 있다. 

-News-article similarity  :  모든 뉴스 aritcle 간의 유사도를 계산하기는 힘든 일

 

document들이 많이 있는 상황에서 text가 많이 겹치는 한 쌍의 document를 찾고 싶다. 

검색결과에  Mirror site를 반영해서 

Plagiarism(표절)

 

LSH는 same topic을 찾아낼 수 있는 것이 아니다. 같은 topic인데 전혀 다른 단어로 쓰여있으면 못찾아낸다. 

 

 

 

슁글링(Shingling)

문서를 집합으로 표현하는 과정.

민해싱(Minhashing)

민해싱을 하는 이유는 document가 set으로 변했는데 .. 커다란 set들을 size줄이는 작업이 필요했고 이것이 Minhashing이다. 시그니처라고 불린다.(lists of integers), 각 셋이 짧은 signatrue로 줄어들었다고 하더라도 similarity는 보존이 되어야한다.

지역성 기반 해싱(Locality-Sensitive Hashing)

이 signature들을 input으로 받아서 similar한 가능성이 높은 signature들을 찾아낸다. 

 

출저 : stanford University Jeffrey D. Ullman

doucument에 나타난 길이 k짜리 string의 셋

minhahing을 통해서 셋을 시그니처로 변경시킨다. 

시그니처는 짧은 int vector들이 되어야하고. 셋간 similarity를 반영해주어야한다. 

세번째 단계가 LSH인데 candidate pair를 output으로 낸다. similar한 가능성이 높은.. 

signature들이 LSH로 들어가서.. 

 

실제로 signautre값