고요한 하늘

첨언 : 글을 쓰다 보니 LSH를 어디에 사용하는지 쓰지 않은것 같다.

LSH는 문서를 몇개의 signature( 고유값 )으로 표현하는 방법이다. 일반적으로 문서 하나가 100여개의 단어로 구성되어 있다면 이를 벡터로 표현했을때 100차원이라고 볼수 있다. 이것은 제한된 크기 n차원으로 줄이는 기술이다.

n이 크면 클수록 원본 데이터에 유사해지지만 속도가 느려지고 작아지면 속도가 빨리진다.
물론 차원을 줄여 속도가 빨라진다고 퀄리티까지 형편 없어지면 알고리즘이고 불리지도 않았을 것이다.

차원이 줄어들면 문서의 중복 제거나 클러스터링이 가능할것 같다.

구글에서는 이기술을 map & reduce와 접목시켜 개인화된 뉴스 클러스터링을 한다고 한다.

Locality sensitive hashing : 고차원 데이터의 차원 확률에 기반한 차원 축소 방법론

Basic idea : 해시 함수에서 같은 데이터는 같은 buket에 들어간다.

간단한게 LSH를 설명하면 다음과 같다

두개의 문서가 있을때

문서에 나타나는 모든 키워드에 ID를 부여한다.( ID는 unique 해야 하고, 두번째 출연한 키워드에 대해서는 이미 부여된 ID가 주어진다 )
id가 부여되면

문서1 = 1,2,3,4,5

문서2  = 1,2,3,4,6,7,8

이런 모습이 될것이다.

여기에 1차원 함수를 n 개 만든다.

예를 들면

각각의 문서에서 일정한 간격  k개 마다  term id  n개를 추출한다.

간격(k)은 임의대로 설정해서 4로 설정하고 첫번째는 5, 두번째는 7, 세번째는 15, 네번째는 20

추출된 n개의 ID에서 가장 작은 값을 선택한다.( get the signature )

그러면 결과적으로

첫번째 문서에서 추출한 id가 4개

두번재 문서에서 추출한 id가 4개가 된다.

이렇게 추출한 ID가 같으면 두개의 문서는 유사할 가능성이 높은 문서로 판단한다.

간격 k를 더 많이 설정하여 추출하면 더 많은 id가 추출될 것이고 신뢰성도 높아질 것이다.( 물론 계산량은 많이지고 속도는 떨어질 것이다 )

실제 알고리즘은 여기에 prime number와  universal hash, random permutation 과 같은 개념들이 추가된다.

 BOOL prime_number (int x)
  {
  for ( int i = 2; i<=sqrt(double(x)); i++)

     if( x % i == 0 )
        return FALSE;

   return TRUE;
}

약 240,000개 문서에 대해서

문서당 signature를 추출하는 과정까지 테스트 했을때 1분 30초 정도가 소요되었다.

속도가 중요한 경우에는 사용해 볼만한 알고리즘이다.

LINK :

http://people.csail.mit.edu/indyk/mmds.pdf

KNN : http://sj21.wo.to/tt/320?category=4

MIN HASH : http://www.stanford.edu/class/cs276b/handouts/minhash.pdf

 위 내용이 이해가 어렵다면

문서 A, B가 있고

우선 문서 A에서 다음 규칙에 의해서 키워드를 선택한다.

3, 6, 9 12.. 번째 키워드를 가져와 정렬한 후에 최상위에 오는 키워드를 선택한다.( 선택된 키워드는 k1 )

5, 10, 15 ...번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k2)

7, 14, 21... 번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k3)

그럼 A문서는 { k1, k2, k3 }가 되고  A`으로 표현

다음 문서 B에서 다음 규칙에 의해서 키워드를 선택한다.

3, 6, 9 12.. 번째 키워드를 가져와 정렬한 후에 최상위에 오는 키워드를 선택한다.( 선택된 키워드는 k1 )

5, 10, 15 ...번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k2)

7, 14, 21... 번째 키워드를 가져와서 정렬한 후에 최상에 오는 키워드를 선택한다.( 선택된 키워드는 k3)

그럼 B문서는 { k1, k2, k3 }가 되고 B`으로 표현

만약 A` = B`이라면 문서 A와 문서 B가 같을 확률이 높다고 할수 있다.

조금더 정확히 하려면 키워드를 좀더 많이 선택해서 비교하면 된다

이 글은 스프링노트에서 작성되었습니다.