MinHash와 LSH(Locality Sensitive Hashing)

LSH는 두 문서(오디오, 비디오)의 유사도를 측정할 때 활용할 수 있습니다.

 

LSH는 3단계로 나눌 수 있습니다.

 

1. Shingling

2. MinHashing

3. LSH(Locality-Sensitive Hashing)

 

1. Shingling

이 단계는 각 문서를 길이가 k인 문자 집합(k-shingles 또는 k-gram이라고도 한다.)으로 변환합니다.

예를 들어 한 문서(D)에 "Casper"이라는 문자열 있을 경우 k가 2라면 다음과 같은 set가 나옵니다.

k가 2인 경우 -> {"Ca", "as", "sp", "pe", "er"}

k가 3인 경우 -> {"Cas", "asp", "spe", "per"}

 

이때 유사한 문서의 경우 더 많은 shingle을 공유할 가능성이 높습니다.

또한 만들어진 집합들의 유사도를 구하기 위해 자카드 유사도를 사용합니다.

 

Jacard Similarity

자카드 유사도는 두 집합의 유사도를 측정할 때 사용하는 방법 중 하나입니다.

IOU(Intersection Over Union) 라고도 합니다.

$J(A,B) = \frac{|A\bigcap B|}{|A\bigcup B|}$

 

예) A={1, 2, 3, 4}, B={1, 2, 3, 5}

위 두 집합 A, B의 자카드 유사도는 $\frac{3}{5}$ 입니다.

 

이를 IOU(Intersection Over Union)라고도 합니다. 일반적으로 shingles의 수가 많을수록 자카드 유사도가 커지므로 문서가 유사할 가능성이 높아집니다.

 

 

2. MinHashing

 

좌측의 무작위 순열의 순서대로 중앙의 Input Matrix를 참고하여 우측의 Signature Matrix를 완성합니다.

Input Matrix의 C1, C2, C3, C4를 각 문서라고 생각합니다.

 

 

Signature Matrix의 C'만 보자면 다음과 같습니다.

 

[그림1] C' 생성 (1)

[그림 2] C' 생성 (2)

[그림 3] C' 생성 (3)

C'에 들어가는 값은 무작위 순열에서의 인덱스 값이며 들어가는 규칙은 무작위 순열에 따릅니다.

[그림 1]에서 무작위 순열 1에서 열C1과 열C3에 대한 값이 존재하므로 C'의 열C1, 열C3자리에 인덱스 값 '1'을 넣어줍니다.

[그림 2]에서는 열C1,열 C3, 열C4에 대한 값이 존재하지만 열C1과  열C3에 대한 값은 이미 존재하므로 C'의 열C4자리에 인덱스 값'2'를 넣어줍니다.

[그림 3]에서는 무작위 순열에서 인덱스 값 '3'과 '4'에서는 열C2에 대한 값이 없고 인덱스 '5'부터 존재하기 때문에 C'의 열C2자리에 인덱스 값 5를 넣어줍니다.

 

이제 Input Matrix의 Jaccard 유사도와 Signature로 구한 유사도를 비교해 보겠습니다.

 

각 각의 유사성을 비교해보았을 때 시그니처의 길이가 3이라 어느정도 차이가 존재합니다. 하지만 시그니처의 길이를 늘린다면 둘의 유사도는 서로 근사해질 것입니다.

※ 해당 내용의 오류와 문제점에 대한 부분을 알려주시면 감사하겠습니다.

 

따라서 MinHashing을 사용하여 희소성을 제거하고 유사성을 유지함으로써 공간복잡성 문제를 해결하였습니다.

 

 

3. LSH(Locality-Sensitive Hashing)

LSH는 Minhash를 통해 구한 signature matrix의 한 컬럼을 가지고 어떻게 비슷한 다른 컬럼을 찾을 수 있을지에 대해 다룹니다.

 

길이가(행이) n인 Signature matrix를 행으로 b 등분합니다. 이들을 b bands라고 부릅니다.

또한 각 각의 b bands들은 r개의 행을 가지고 있습니다.

그러므로 b * r = n이 됩니다.

예) n = 100, b = 20, r = 5

 

각 밴드는 k개의 버킷을 가지고 있고, 밴드별로 할당된 시그니처의 열을 k개의 버킷에 해싱합니다.

 

이때 두개의 컬럼을 해싱할 때 하나의 밴드라도 동일한 버킷에 들어간다면 두 컬럼은 비슷하다고 봅니다.

 

이때 b와 r을 결정해야 하는데 다음을 먼저 살펴보겠습니다.

1. b가 커지면 similarity threshold가 낮습니다. 이는 FP가 높다는 것을 의미합니다.

2. b가 작아지면 similarity threshold가 높습니다. 이는 FN가 높다는 것을 의미합니다.

FP : False Positive = 비슷하지 않은데 비슷하다고 판단하는 오류

FN : False Negative = 비슷한데 비슷하지 않다고 판단하는 오류

 

위 설명을 참고하자면 n은 고정이기 때문에 b가 커지면 r은 작아집니다.

알고리즘에서는 하나의 band에 들어있는 모든 row를 해시한 값이 일치하면 비슷한 문서라고 판단한다고 했습니다.

그러므로 r이 낮을 수록 문서를 비슷하다고 판단할 확률이 높아진다고 볼 수 있습니다.

 

 

 

 

 

 

 

참고 : https://towardsdatascience.com/understanding-locality-sensitive-hashing-49f6d1f6134

Locality Sensitive Hashing

https://haandol.github.io/2019/05/28/lsh-minhash-explained.html

쉽게 설명한 LSH-Minhash 알고리즘 (LSH Minhash concept and implementation), Haandol

https://medium.com/@hubert_46043/locality-sensitive-hashing-explained-304eb39291e4

Locality sensitive hashing — LSH explained

https://lifemath.tistory.com/8?category=919393 

[데이터 마이닝] Locality-Sensitive Hashing (LSH) 란?

https://jisung0920.github.io/data%20mining/lsh/d011/

Shingling