Finding Similar Items

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

이번 모듈에서는 주어진 데이터셋에서 유사한 아이템 쌍을 찾는 기술에 대해 다룹니다.

이 기술은 표절된 문서를 찾거나 미러링 페이지 찾기, 추천시스템에서 유사한 취향을 가진 사용자를 찾는 등 여러 분야에서 활용될 수 있습니다.

데이터의 규모가 작은 경우에는, 유사한 아이템을 찾는 작업을 쉽게 수행할 수 있습니다.

단순하게 한 아이템과 나머지 아이템들을 순차적으로 비교해보고, 모든 아이템에 대해 비교를 하면 됩니다.

중복을 제외한다면 $\frac{n(n-1)}{2}$ 의 아이템 비교 작업이 필요합니다.

데이터의 규모가 큰 경우 이런 계산을 하기 어렵습니다.

예를들어, 백만개 정도의 아이템이 주어지면 조 단위의 비교가 필요합니다.

이러한 상황에서 계산을 줄이기 위해 고안된 기술이 Locality Sensitive Hashing, LSH 입니다.

Locality Sensitive Hashing

LSH 는 데이터 셋을 전체 탐색하지 않고도 유사한 쌍을 찾아줍니다.

물론, 전체에 대한 비교가 안되므로, 추정(estimate) 작업입니다.

모든 아이템 쌍을 다 보지 않고, 유사하다고 추정되는 쌍만 비교하여 계산시간을 단축하는 원리입니다.

LSH에서는 해시함수(=hash function)를 사용합니다.

단순하게 해시함수를 사용하는 것이 아니라, 유사한 아이템끼리 동일한 버켓(=bucket) 에 들어가도록 속성을 잘 설계합니다.

그리고 동일한 버켓에 있는 쌍들, 후보 쌍들(=Candidate pairs)에 대해서만 유사도 검사를 하여 유사한 아이템 쌍을 찾아냅니다.

LSH는 다양한 형태가 있지만,

이번 포스팅에선

유사한 문서(=Document) 쌍을 찾는 문제 위주로 설명하겠습니다.

유사한 아이템(문서) 쌍을 찾는 전체 프로세스는 다음과 같습니다.

그림@@

문자열로 구성된 데이터 같은 경우,

Shingling 을 수행하여 각 데이터 항목 마다 하나의 집합으로 표현해줍니다.

특정 집합에 대한 표현을 행, 각 데이터 항목이 열인 행렬을 입력으로 받아 Minhashing 을 수행합니다.

Minhashing 작업으로 입력 행렬보다 행의 수가 적은 Signature Matrix 을 얻습니다.

이 행렬에 LSH 를 적용하여 키 별로 후보쌍을 얻어냅니다.

이번 포스팅에서는

우선, 텍스트 데이터를 어떻게 집합으로 표현하는지에 대해 다루고,

집합의 유사도를 측정하는 방식인 Jaccard Simliarity 에 대해 설명합니다.

그리고 기존 데이터 셋을 signature 라고 불리는 더 작은 데이터,

representation 으로 변환하는 minhash 에 대해 다룹니다.

이렇게 만들어진 signature matrix 에 LSH를 어떻게 적용하는지에 대해 설명하겠습니다.