첨언 : 글을 쓰다 보니 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가 같을 확률이 높다고 할수 있다.
조금더 정확히 하려면 키워드를 좀더 많이 선택해서 비교하면 된다
- universal hash : 유사한 hash값은 동일한 bucket이나 인접한 bucket에 들어가는 것을 보장
- min hash : 두집합 사이의 유사도를 빠르게 계산하는 알고리즘( jaccard similarity 기반 )
minhash.pdf
위 그림을 간단히 설명하면 다음과 같다.
왼쪽처럼 세개의 문서( c1, c2, c2 )가 있다.
이 문서를 3가지 permutation 방법으로 읽는다.
perm1은 1,2,3,4,5 로 순서대로 읽으면 되는데
S1, S2, S3이 각각 1, 2, 1이 나온 이유는 다음과 같다.
0은 skip을 하고 1이 나온 ROW의 숫자를 기록한다.
그러면 c2만 첫번째 행에 0이 있기 때문에 2(R2)가 되고
C1과 C3는 1(R1)이 된다.
그러면 perm2를 가지고 다시 해보면 이번에는 역순으로 읽는다
C1 C2 C3
R5 0 1 0
R4 1 0 1
R3 1 0 0
R2 0 1 1
R1 1 0 1
위와 같이 데이터가 있다고 생각하고
다시 첫줄부터 1이 나타나는 위치를 보면
C1의 첫번째줄 R5는 0이므로 아래로 이동한다. R4는 1이므로 S1은 4(R4)가 되고 C2의 첫번째줄은 1이므로 5(R5) C3의 첫번째줄은 0이므로 아래로 이동한다. R4는 1이므로 4(R4) 가 된다.
perm3도 마찬가지로 (3,4,5,1,2)순으로 읽게 되면
C1 C2 C3
R3 1 0 0
R4 1 0 1
R5 0 1 0
R1 1 0 1
R2 0 1 1
처럼 테이블이 되고
첫번째 줄부터 1이 나타나는 위치를 아래줄로 이동하면서 확인한다
C1은 첫번째 줄에서 1이 나타난다 즉 R3 그래서 S1은 3이 되고
C2는 첫번째 줄, 두번째 줄은 0이고 세번째 줄에서 1이 나타나서 R5 그래서 S1은 5
C3은 첫번째 줄은 0 두번째 줄은 1이 되서 R4 그래서 S3은 4가 된다.
값들이 ROW INDEX로 바뀌어 해석이 되서 조금 헷갈리는 부분이 없지 않아 있지만 위 그림을 이해할수는 있을 것이다.
https://www.pinecone.io/learn/series/faiss/locality-sensitive-hashing/
'알고리즘' 카테고리의 다른 글
| NMF 테스트 결과 (0) | 2009.05.28 |
|---|---|
| Non negative Matrix Factorization ( NMF ) (0) | 2009.05.20 |
| Expectation Maximization (0) | 2008.09.15 |
| index-compression( relative-10 ) (0) | 2007.12.14 |
| gamma code (0) | 2007.11.23 |