용어
- LSH : 지역성 기반 해싱 / 가장 유사해 보이는 쌍들만을 검색하는 기법
- 슁글링 : 문서들을 문자단위의 집합으로 변화하는 기법
- 민해싱 : 대형 집합을 압축하는 기법
현실문제:
서로 다른 두 집합이 얼마나 유사해야 충분히 유사한 그룹이라고 말할 수 있나?
- 유사도를 측정하는 방법이 정해져야 한다.
- 유사하다고 판단하는 기준이 정해져야 한다.
Step1.
원본 데이터는 집합형태가 아니다. 따라서 유사도를 계산하기 전에 가장 먼저 집합형태로 데이터를 가공해야 한다.
--> white space( blank, tab, newline )을 어떻게 처리할 것인가? 2개 이상의 white space를 1개로 치환한다.
--> stopwords(의미가 없는 전치사,접속사, 대명사)들은 어떻게 처리할 것인가? 삭제..
--> 문장의 문자들을 어떻게 잘라내야 하나? 즉 말뭉치의 크기를 선택하는 일이다. 이를 슁글이라 하고, 보통 5이상으로 잡음.
--> 싱글(문자열)을 압축하고 수치값으로 변환할 수 있나? 해시함수를 적용해 "버킷번호(해쉬값)"을 얻을 수 있다.
--> 싱글로 구성된 집합을 압축할 수 없나? "대표값(시그니처)을 모은 집합"을 만들 수 있다.
Step.2
싱글집합을 상대적으로 작은 크기이면서 "고유속성"을 그대로 지닌 집합(시그니처 행렬)로 압축변환해야 빠른 연산/저장이 가능하다.
--> MinHash()를 사용해서 슁글(단어)와 집합(문서)들로 구성된 Sparse Matrix를 Dense Matrix로 변환함.
* MinHash란 무엇인가? 슁글(행)에 대한 해시값 만들어 놓고 그 순서를 무작위로 반환하는 해시함수.
--> 왜 MinHash()를 사용하는가? 민해시함수값이 같을 확률은 자카드 유사도와 같다.
Step3.
이제야 본론이다. 유사도를 어떻게 측정할 것인가? 클러스터링을 생각해보자.
가장 유명한 KNN이 무엇인가? 가장 가까운 거리에 있는 k개 데이터를 통해 나의 그룹을 찾아낸다.
--> "가장 유사해 보이는 쌍들만 집중적으로 계산한다"
--> 이를 지역성 기반 해싱 / 근접이웃탐색 이라고 함.
Step4.
정해야 할 것이 있다. 거리를 측정하는 방법을 정해야 한다.
1) 유클리드 거리
2) 자카드 거리** : 교집합/합집합 (이거 선택하겠다..)
*밴드분할기법
(발상) 해시값1개만으로 유사하다고 할 수 없다면? 해시값 1개 말고 여러개가 일치해야 교집합이라고 하자!
--> 시그니처 해시값(각 고유집합/문서의 해시값)을 n개 그룹(밴드)으로 나누고, 밴드단위로 해시값이 같으면 후보쌍이다.
--> 한 개의 해시값보다 연속적인 해시값이 일치할 때, Context를 담은 정보의 유사성이 있다고 판단되니까~
--> 자카드 유사도에 따른 후보가 될 확률은 "sigmoid함수" 형태이다.
3) 코사인 거리
4) 편집 거리
5) 해밍 거리
Step5.
두개 항목이 "유사한 후보쌍"인지 판단(기준을 가진)하는 함수를 정해야 한다.
Local Sensitive Hashing 의 공통점
: 두가지 기준을 만든다.
- 거리가 d1 미만인 경우, 유사할 확률은 p1 미만이다.
- 거리가 d2 초과인 경우, 유사할 확률은 p2 초과다.
1) 자카드 거리 기반 함수
2) 코사인 거리 기반 함수
3) 해밍 거리 기반 함수
4) 유클리드 거리 기반 함수