[CS246] Finding Similar Items (1) - Introduction

Big Picture

naive하게 similar item을 찾는다고 하면 이중 루프를 통해 유사도를 계산하는 것을 생각할 수 있다. 

해싱(hashing)을 이용하여 제곱의 시간복잡도 없이 유사한 아이템을 빠르게 찾을 수 있다.

대표적인 알고리즘으로 Locality-Sensitive Hashing (LSH)에 대하여 공부할 것이다.

LSH의 장점으로 매우 적은 pair만으로도 계산이 가능하다는 것이고, 단점으로 false negative가 존재할 수 있다는 것이다.

 

Applications

Finding Similar Documents

web, 뉴스 기사 등의 매우 큰 스케일에서 문자 그대로(textually) 유사한 문서를 찾는 것이다. 

의미가 비슷한(similar meaning, topic) 것을 찾는 것이 아니라 문자 수준(character-level)으로 유사한 것을 찾는것이다.

많은 문서들은 거의 비슷하지만, 완전히 같지는 않다. 

표절, 미러 사이트(mirror site), similar article 등을 찾는데 응용된다.

 

Collaborative Filtering

비슷한 취향을 갖는 사람들에게 아이템을 추천해줄 수 있다.

Amazon과 같은 웹 스케일의 전자상거래, Netflix와 같은 영화 추천 등에 응용된다.

 

Three Essential Techniques

Shingling

document, email 등의 문자열 데이터를 집합으로 매핑하는 작업이다.

Minhashing

크기가 큰 집합을 signature(정수 리스트)로 매핑하는 작업이다. 

그러나 유사한 집합끼리는 signature의 유사도 역시 보존되어야 한다.

일반적으로 유사도는 jaccard similarity를 이용한다. (다음 포스팅에서 설명)

Locality-sensitivity hashing (LSH)

signature pair가 유사하도록 하는데 중점을 둔다.

Big picture of LSH Algorithm