3.1 근접 이웃 탐색의 응용
자카드 유사도 (Jaccard Similarity): 교집합의 상대적인 크기로 관찰되는 집합의 유사성
집합 S와 T가 있으면, 이 둘의 자카드 유사도는∣S∩T∣/∣S∪T∣| 로 정의한다. (둘의 자카드 유사도는 SIM(S, T)로 나타내기도 함.)
일반적으로 웹이나 기사 모음 같은 말뭉치에서 유사한 문서들을 찾는 일은 자카드 유사도로 다루기 적합한 종류의 문제인데, 이는 문자 기반 유사성 (Character-level Similarity) 임에 유의하자. 즉, 의미가 유사한 것이 아닌 문자 자체의 유사도를 비교하는 것이다.
(사용하는 예시: 표절, 미러페이지, 출처가 유사한 기사의 필터링)
단순히 글의 유사도만 걸러내는 것이 아니라, 협업 필터링 (Collaborative Filterling)이라 하여 특정 사용자와 취향이 비슷한 사용자들이 선호하는 항복을 추천하는데 사용할 수도 있다. 예를 들어 온라인 커머스에선 자카드 유사도가 특정 수준 이상인 (약 20%) 사람들을 묶어 유사 취향으로 분류하고, 추천 아이템을 제시할 수 있을 것이다.
만약 사람들이 특정 상품에 별점을 매기고, 해당 별점을 기준으로 추천 상품을 고르는 방법은 뭘까? 단순 이진 선택이 아니기에 집합에 데이터가 있다/없다로 구분하기 어렵다. 만약 특정 상품에 n개의 별을 준다면, 집합에 해당 상품을 n번 넣는다. 이후 자카드 유사도를 판단하는 과정에서 백 유사성 (Bag-similarity)를 사용한다. 교집합을 구하는 과정에선 해당 원소가 나오는 최소횟수를 구해주고, 합집합을 구할때는 나오는 전체 갯수로 구해준다.
3.2 문서의 슁글링
어휘적으로 유사한 문서들을 구별하기 위해선 문서에 등장하는 문자열들을 원소로 하는 집합을 구성하는 것이 좋다. 이렇게 하면 문장이나 구문등 일부분을 공유하는 문서들은 집합의 많은 원소를 공통으로 갖게 될 것이다. 집합을 구성하는 방법에는 여러가지가 있겠지만, 여기서는 일반적인 접근법인 슁글링(Shingling)을 알아볼 것이다.
문서 내에서 발견되는 길이가 k인 부분문자열을 활용해 해당 문서에 대한 k슁글을 정의한다. 이렇게 하면 각 문서를 해당 문서 내에 한 번 이상 등장하는 k슁글의 집합으로 간주할 수 있다.
공백이나 줄바꿈 같은 문자는 어떻게 처리할까? 일반적인 경우엔 Whitespace에 대해 1글자로 치환하여 간주한다.
k는 어떤 상수든 될 수 있으나, k가 너무 작으면 모든 문서들의 유사도가 너무 높아질 수 있다. 따라서 문서의 길이나 일반적인 문자들로 구성된 집합의 크기에 따라 결정되고, 슁글들이 겹칠 확률이 낮아지도록 충분히 크게 해주면 좋다.
예를 들어, SNS나 이메일의 경우엔 k=5를 기준으로 잡고, 연구 논문 같은 대형 문서에서는 k=9를 기준으로 잡는다.
그러나 모든 부분문자열의 슁글을 다루기엔 길이가 길어질 수 있으니, 해시함수에 밀어넣고 인덱스를 받는 방법도 있다. k글자의 슁글의 경우 당연히 k바이트가 나오겠지만, 해시함수에 넣고 (hash 인덱스가 int 선에서 커트된다는 전제하에) 인덱스를 갖고 놀면 4바이트를 넘기지 않는다! 9슁글을 사용해서 해시함수를 끼얹으면 4슁글과 동일한 바이트를 사용하지만, 구분은 훨씬 잘 될 것이다.
다만 영어에선 a, an, for, have, it, its, is, and, or, not... 같은 단어들이 있기 때문에, 적절히 잘 필터링 해줄 필요가 있는데, 저 단어 주변 단어가 유사하면 두 컨텐츠는 유사할 가능성이 매우 높기 때문에 높은 자카드 유사도를 갖도록 만들 수 있을 것이다.
3.3 집합의 유사도 보존 요약
잘 생각해보자. 위에서 4바이트로 슁글을 해싱한다고 했는데, 실제로 저걸 다 메모리에 적재하는게 가능할까? 어림도 없지! 따라서 대형 집합을 적은 수의 시그니처로 표현하는 방식을 선택하는 경우가 있다.
우선 집합들을 시각하기 위해 특성 행렬 (Characteristic Matrix)로 시각화해보자.
행렬의 열은 집합이며, 행은 전체 집합의 원소이다. 즉, (r, c)가 1이면 r에 해당하는 원소가 c에 해당하는 집합에 포함된다는 것이고, 0이면 아닐 것이다.
중요한건, 시각화라는 것이고 절대 저렇게 저장되는건 아니다! (0이 차지하는 공간을 고려하면 공간 낭비니까...)
구성하고자 하는 집합에 대한 시그니처는 계산 결과로 구성되어 있으며, 각각의 계산은 특성 행렬의 민해시 (minhash) 라고 부른다.
우선 열로 표현되는 집합을 민해싱하기 위해 행들을 치환해보자. 이때 특정 열의 민해시 값은 변경된 순서에서 첫번째로 1을 갖는 행의 번호이다.
다음과 같이 abcde → beadc로 순서를 바꿔버리면 민해시 값은 h(S1) = a, h(S2) = c, h(S3) = b, h(S4) = a이다.
이렇게 무작위 치환을 진행하는 민해시 함수가 두 집합에 대해 같은 값을 생성할 확률은 그 두 집합의 자카드 유사도와 같다!
두 집합의 경우로 좁혀야하니, S1과 S2를 골라서 봐보자.
당연히 둘다 1이거나, 하나만 1이거나, 둘다 0인 세가지 경우로 나뉠텐데, 희소 행렬의 특성상 세번째인 경우가 많을 것이다.
그런데 우리는 자카드 유사도에 대해 합집합과 교집합으로 정의를 했으니, (둘다 1인 경우) ⇒ 교집합, (둘다 1인 경우 + 하나만 1인 경우) ⇒ 합집합으로 볼 수 있을 것이다! 둘다 1인 경우의 수를 x, 하나만 1인 경우를 y라고 하면, 자카드 유사도는 x / (x + y)라고 볼 수 있다.
그럼 P(h(S1) = h(S2))는 어떨까? 둘다 0인 경우는 어차피 넘어갈테고, 첫번째로 1이 보이는 지점에서 둘다 1이여야 h(S1) = h(S2)이니, 결국 이 확률도 x / (x + y)가 된다.
이런식으로 민해시 값을 얻을 수 있는데, 이런 무작위 섞기를 n번 반복하면 하나의 집합 S에 대해 n개의 민해시 값을 얻을 수 있는데, 이걸 벡터로 묶고 S 뿐만이 아닌 전체 집합에 대해 표현해주면 하나의 시그니처 행렬 (Signature Matrix)를 생성할 수 있다.
문제는 섞는데 걸리는 시간과, 첫번째 1을 구하는 연산을 어떻게 하냐는 것이다. 다행히 행 번호를 행 수만의 버킷으로 매핑하는 해시 함수를 사용해 무작위를 어떻게든 구현할 수 있긴 하다.
무작위로 n번 순서를 바꾸는게 아니라, 임의로 선택된 해시 함수로 행을 꽉 채워주고, 주어진 순서로 각 행들을 처리하고 시그니처 행렬을 만들 수 있다.
i번째 해시 함수와 열 c에 대한 시그니처 행렬의 성분을 SIG(i, c) 라고 정의하자. 그 후 모든 i와 c에 대한 SIG(i, c)의 초기값을 INF로 설정하고, 다음 절차에 따라 행 r을 처리해보자.
- h1(r), h2(r), ... hn(r)을 계산한다.
- 각 열 c는 다음을 수행한다.
- 행 r에서 c가 0이면 아무것도 하지 않는다.
- 행 r에서 c가 1이면, i = 1, 2, ... n에 대해 SIG(i, c) = min(SIG(i, c), hi(r))이다.
앞에 사용했던 친구를 데려와서 예시를 보자.
h1(0)과 h2(0)은 모두 1이다. S1과 S4에 해당하는 열에서 0번째 값이 1이므로, 시그니처 행렬은 다음과 같이 변한다.
h1(1) = 2, h2(1) = 4이므로, SIG(1, 3) = 2, SIG(2, 3) = 4이다.
다음것도 정도껏 처리하고, 갱신해주면
다음과 같이 완성된다.
원래 집합들의 자카드 유사도를 계산해보자. 일단 1번 열과 4번 열은 동일하므로 SIM(S1, S2) = 1.0으로 추측이 가능하다. (실제 자카드 유사도는 2/3이지만...) 이런식으로 추정치는 정말 '추정'치일뿐, 결과값이 다르다. (사실, 제대로 추측하기 위해선 시그니처 행렬의 열의 수가 너무 적다...)