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

이전 포스팅에서 Min-hashing 알고리즘에 대해서 다루었다. 이번에는 이 개념에서 추가로 사용될 수 있는 LSH라는 방법론에 대해서 알아보겠다. 이전 포스팅은 아래에 링크가 있으니 Min-hashing에 대한 개념이 아직 없다면 확인하고 오길 바란다. 

2021/02/07 - [인공지능/데이터 마이닝] - [데이터 마이닝] Min-Hashing 란?

---

 

 

Locality-Sensitive Hashing (LSH) 란?

LSH도 Min-hashing과 마찬가지로 빅 데이터의 정보 압축을 하는 알고리즘 중 하나로, 본래는 문서를 Shingle 이라는 조각으로 쪼개어서 데이터의 차원으로 만든 다음 이것을 바탕으로 문서들 사이의 클러스터링을 통해서 어떤 문서가 서로 비슷한지를 효과적으로 확인하기 위해서 만들어졌다. 즉, 유사 문서를 확인하는 알고리즘으로 완전히 동일하진 않더라도 어느 정도 비슷한 논문이나 글을 확인하여 유사 문서로 분류 할 수 있다. 

Locality 라는 말을 통해서 부분적으로 비슷하기만 해도 어느 정도는 비슷할 가능성이 높다는 것에 착안한 알고리즘이다. 

직관적 이해

LSH는 그렇게 복잡한 방법론은 아니며, 아래와 같이 Min-hashing 포스팅에서 다루었던 인풋을 가져왔다고 해보자. 

 

 

여기서 Band 라는 것을 지정하는데, 본래 인풋 차원에서 이것을 쪼개어서 각각의 Band로 정의 한다. 하지만 이 Band의 크기는 사용자가 정하기 나름이다. 얼마나 정확하게 클러스터링 할 것인지, 얼마나 빠르게 대략적으로 클러스터링 할 것인지를 잘 조율하여 Band의 크기를 지정해야 한다. 

여하튼 이렇게 지정된 Band 들을 보자. 각 밴드 내부에서 클러스터링을 실시한다. 그래서 한번이라도 같은 클러스터링에 할당되면 여기서는 이것을 bucket 이라고 부르는 클러스터에 할당되었다고 표현한다. 이렇게 bucket에 한번이라도 두 개 또는 그 이상의 열이 할당되면 이것은 후보 유사 문서 집합에 할당된다. 여기서 문서라고 문제를 설명했지만, 이것은 사실 어떠한 차원의 데이터도 될 수 있다. 

그런데 여기서 각각의 밴드에서의 bucket은 공유하지 않고, 각 밴드에서 따로 생성되므로, Bandit 이론과는 또 구분된다고 봐야 한다. 그냥 비슷한적이 부분적으로 한번이라도 있으면 그것들은 실제로 전체를 봐도 비슷할 것이라고 보고 후보자 집합에 넣는 것이다. 

 

 

그리하여 후보자 집합에 있는 열들만 다시 모아 놓고 여기서 클러스터링을 다시 실행한다. 그래서 실제로 어떠한 클러스터가 생성되는지 보면 유사 문서들을 잘 구분할 수 있게 된다. 즉, 아웃라이어로 판명난 문서는 무시하게 된다. 위의 예제에서는 C2는 단 한번도 다른 C들과 부분적으로 비슷한적이 없었기에 무시되고, 오직 C1, C3, C4, C5 만 비교하여 구분하게 된다. 이렇게 함으로써 모든 문서들을 쌍으로 비슷한 정도를 계산할 필요 없이 유사 문서를 찾아 낼 수 있게 되는 것이 LSH의 장점이라고 볼 수 있겠다. 

그런데 왜 Min-hashing을 설명한 이후에 LSH를 설명했는가 하면, 사실 LSH는 보통 Min-hashing이 끝난 후, 만들어진 Signature 행렬에 적용하는 경우가 대부분이다. 

 

 

즉, 위와 같이 Min-hashing으로 만들어진 Signature 행렬에 LSH를 아래와 같이 적용한다. 

 

 

결국 이중으로 계산 시간과 로드를 줄여주는 셈이 되는 것이다. 이러한 데이터 마이닝 기법은 빅데이터 분석에서 아주 쓸모가 있고, 특히 계산량이 너무 큰 문제가 되는 경우에 가장 유용하게 쓰일 수 있다.