LSH(Locality Sensitive Hashing), Minhash를 사용한 차원축소

석사 졸업논문을 쓸 때 OLE 기반의 여러 파일들에 대한 특징을 추출해야 할 일이 있었는데 그 때 데이터를 좀 축소시켜볼까 해서 썼던 방법 중 하나가가변 길이의 데이터를 같은 차원으로 압축?축소? 시키기 위해 사용할 적당한 알고리즘을 찾다가 LSH(Locality Sensitive Hashing)라는 것을 발견했다. 결론적으로 사용하진 않았다.

 

LSH는 고차원 데이터의 차원 확률에 기반한 차원 축소 방법론이라고 할 수 있다. 하나의 문서가 100여개의 단어로 이루어져 있다면 이를 벡터로 표현하면 100차원이다. 이것을 제한된 크기 n차원으로 줄이는 기술이다. 간략히 공부하면서 어떤 저자가 Coursera 강좌를 듣고 Minhash 알고리즘에 대해 정리해 놓은 글을 봤는데 해당 글을 다시 정리해보았다.

 

---

MinHash Tutorial with Python Code - Chris McCormick

MinHash Tutorial with Python Code · Chris McCormick

 

 

Set Similarity

유사도 측정을 위해 Jaccard similarity를 사용하는데 전체중에 겹치는 비율을 유사함으로 측정한다.

 

 

예를들어, A와 B가 각각 좋아한 상품이 A=[1,2,3,4] / B=[1,2,7] 라고 하면 A,B는 아래의 공식에 의해 Similarity는 0.4가 된다.

 

 

 

 

Documents as sets

이렇게 유사도를 측정하는 것에 의미가 있기 때문에 예를 들면, 표절 검사와 같은 곳에 사용할 수 있다. 문서를 단어 집합으로 나타내면 Jaccard Similarity를 두 문서 사이의 비슷한 정도를 나타내는 척도로 사용할 수 있기 때문이다. 여기서 실제로 문서의 어떤 의미론적 의미를 파악하지는 않는다는 것을 알아 두어야 한다. 단순히 동일한 단어가 포함되어 있는지 여부만 살펴 보는 것이다.

 

아래와 같이 두 집합이 있다. 두 집합은 3개의 항목이 같고 사이에 10개의 고유한 항목이 있다. 따라서 이 두 집합간의 Jaccard Similaritysms 3/10이 된다.

 

• Set A (32, 3, 22, 6, 15, 11)

• Set B (15, 30, 7, 11, 28, 3, 17)

 

 

Shingles

예를들어, 아래와 같은 다른 string이 3개 있다고 해보자. 각 개별 단어를 hashing하는 것이 아니라 해당 string을 hashing하여 하나의 integer로 나타내게 된다. 각 단어를 hashing하는 것보다 이렇게 하는 것이 문서의 구조를 좀더 깨뜨리지 않게된다(?)

 

• A small detail

• small detail here

• detail here is

 

이것을 shingling한다고 하고 각 고유한 string을 shingle이라고 부른다.

 

 

Problem scale

많은 문서 모음을 가지고 있고 서로 거의 중복되는 모든 문서 쌍을 찾고 싶다고 가정해 보자. 각 문서 쌍 사이의 Jaccard Similarity를 계산한 Similarity가 임계값 이상인 것을 확인할 수 있다.

 

이때, 각 문서를 다른 모든 문서와 비교하려면 상당히 많은 비교가 필요하다...

 

 

MinHash Signatures

각 데이터에 대해 MinHash signature을 생성할 것이다. 각 signature는 데이터의 사이즈에 상관없이 고정된 길이를 갖는다. 두 데이터 사이의 Jaccard Similarity을 근사하기 위해 우리는 MinHash signature를가져와 동등한 구성 요소의 수를 단순히 계산한다.이 수를 signature 길이로 나눈다면 Jaccard Similarity에 꽤 근접할 것이다.

 

평균적으로 각각 같은 주제를 갖는 10,000 개의 기사 모음이 있다고 할 때 모든 페어에 대해 Jaccard Similarity을 직접 계산하는 작업은 PC에서 20분이 걸리지만 MinHash signature을 생성하고 비교하는 데는 약 2분 45초 밖에 걸리지 않는다고 한다.

 

 

참고자료
blog.daum.net/jchern/13627840
www.slideshare.net/deview/261-52784785
github.com/chrisjmccormick/MinHash/blob/master/runMinHashExample.py