[Data Mining] 2. Finding Similar Items
1. 개요 (motivation)
데이터마이닝에서, item들의 유사성을 계산하는 것은 중요하다. 한 예로, 20,000개의 이미지 중 주어진 이미지와 가장 비슷한 10개의 이미지를 찾는 경우를 생각하자. 각 이미지는 수많은 픽셀로 이루어져 있으므로, 이 문제는 high-dimensional space에서 가까운 점을 찾는 문제와 같다. 이외에도, 구매자가 구매한 상품과 비슷한 상품을 띄워야 할 때, 특정 사이트의 미러 사이트를 찾을 때, 특정 기사와 유사한 기사를 찾을 때 비슷한 문제에 직면한다.
2. 목표 (goal)
고차원 데이터 \(x_1, x_2, ...\)와 거리함수 \(d\), 특정 역치 \(s\)에 대하여, 거리가 특정 역치보다 짧은, 즉 \(d(x_i, x_j)\leq s\)을 만족하는 데이터 쌍을 구하려고 한다. Naïve한 구현은 \(O(N^2)\)의 시간복잡도를 가지므로 비효율적이다. 따라서 \(O(N)\)에 구현 가능한 확률론적 알고리즘을 소개한다.
3. Jaccard similarity, Jaccard distance
Jaccard similarity는 두 집합의 교집합의 기수를 합집합의 기수로 나눈 값이다. 분모가 두 집합의 기수를 합한 것이 아니라 합집합의 기수임에 유의하라. \[sim(C_1, C_2)=\frac{|C_1 \cap C_2|}{| C_1 \cup C_2|}\]
Jaccard distance는 Jaccard similarity를 1에서 뺀 값이다.\[d(C_1, C_2)=1-\frac{|C_1 \cap C_2|}{| C_1 \cup C_2|}\]
4. 알고리즘 (algorithm)
이 알고리즘은 shingling, min-hashing, locality-sensitive hashing의 세 단계를 거쳐 진행된다.
4.1. Shingling
Shingling은 document를 set으로 바꾼다. 이는 Jaccard similarity를 적용하기 위해서이다. 이때, 고려해야 할 점은 두 가지이다. 먼저, 일반적인 중요도 정렬 알고리즘은 많은 비용이 들기 때문에 사용하기 어렵다. 또한, 문서에 등장하는 단어 하나하나뿐만 아니라 그들의 순서도 중요하다. 따라서 연속한 \(k\)개의 단어의 모음인 \(k\)-shingle (또는 \(k\)-gram)을 도입한다. 이때 \(k\)는 문서의 크기에 따라서 \(5\)에서 \(10\) 정도로 설정한다.
문서 \(D\)에서 \(k\)-shingle들의 모임을 \(S(D)\)라 한다. 예를 들어 단어열 \(D=abcab\)에서 \(2\)-shingle은 \(S(D)=\{ab, bc, ca\}\)이다. 이때, \(S(D)\)는 일반적으로 set이므로 중복을 허용하지 않는다. 그러나 multiset이라는 언급이 있다면 중복을 허용한다. 또한, 특정 전치사나 짧은 단어를 stop words로 정의한 뒤 그 단어들로 시작하는 \(k\)-shingle들만 모으는 경우도 있다. (예: 3글자 이하의 단어로 시작하며 뒤에 두 단어가 더 붙은 \(3\)-shingle)
이 이후에는 문자열로 이루어져 있는 각 shingle에 해시함수를 적용한다. 이는 shingle이 문자열로 있는 경우보다 (예를 들어) 4Byte 정수로 있는 경우가 이후 과정에서 더 편리하기 때문이다.
이제 우리는 각 문서에 대하여 \(2^{32}\)개의 (해시함수를 적용한) 가능한 shingle들 중 toggle up되어 있는 shingle이 어떤 것인지 알 수 있다. 즉, 각 문서는 \(0\) 또는 \(1\)로 이루어진 길이 \(2^{32}\)의 열벡터로 표현된다.
4.2. Min-hashing
Min-hashing 과정의 목표는 길이 \(2^{32}\)의 열벡터의 크기를 (\(100\) 정도로) 줄이는 것이다. 이때, 고려해야 할 점은 similarity를 유지해야 한다는 점이다. 즉, min-hashing 이전에 similarity가 높은 두 문서는 열벡터의 크기가 줄어들어도 similarity가 높을 확률이 커야 한다. 또한, 사용할 수 있는 점은 문서의 길이가 \(2^{32}\)에 비해서는 매우 짧으므로 shingling을 통해 구한 길이 \(2^{32}\)의 열벡터가 사실은 매우 sparce한 벡터라는 점이다.
이 조건을 만족하도록 선택된 방법은 확률론적 방법으로, shingle들의 순열 \(\pi\)를 사용하는 것이다. \(0\)부터 \(2^{32}-1\)까지의 정수들의 순열을 통해 각 shingle에 번호를 부여하고, 각 열벡터 \(C\)마다 toggle up된 shingle들 중 가장 작은 번호 \(h_\pi(C)\)를 찾는다. 순열을 랜덤하게 정했을 때, 두 열벡터 \(C_1, C_2\)가 같은 최소 번호를 가질 확률은 \(C_1, C_2\) 중 적어도 하나에 toggle up된 shingle들 중 \(C_1, C_2\)에 모두 toggle up된 shingle이 가장 앞에 위치할 확률이므로 Jaccard similarity와 일치한다. 이제 이러한 순열들을 \(K=100\)개 정도 준비하면 각 열벡터는 \(h_{\pi_i}(C)\)로 이루어진 (길이 \(100\) 정도의) signature 벡터로 바뀐다.
그러나 사실은 이러한 방법으로 구현하지는 않는다. 실제로는 길이 \(2^{32}\)인 배열의 랜덤한 순열을 한 번 계산하는 것만으로도 많은 비용이 필요하기 때문이다. 따라서 유사순열로 행 번호에 해시함수를 취한 값, 특히 universal hash function이라고 불리는 \(h(x)=ax+b \mod p\)를 사용한다. 즉, 각 shingle의 행 번호에 대한 해시함수 값을 계산해 놓고 toggle up된 열이 있으면 원래 저장된 값과 해시함수 값을 비교하여 갱신하는 과정을 \(K\)개의 해시함수에 대하여 반복하는 것이다. 이것이 이 과정이 min-hashing이라 불리는 이유이다.
4.3. Locality sensitive hashing (LSH)
우리는 지금까지 shingling과 min-hashing을 통하여, 문서 \(\rightarrow\) 열벡터 \(\rightarrow\) signature 벡터 순서대로 similarity를 유지하면서 dimension을 낮추었다. 그러나 아직도 Naïve한 구현은 \(O(N^2)\)이다. 따라서 확률론적 방법을 다시 사용할 것이다.
먼저, signature 열벡터들을 모아 놓은 행렬을 \(M\)이라 하자. 이제, 이 행렬을 \(r\)개의 행을 가지는 \(b\)개의 밴드로 나눌 것이다. (단, \(r \times b\)는 \(M\)의 행 개수) 그리고, 각각의 (작은) 밴드의 열에 (bucket이 충분히 많은) 해시함수를 취한다. Bucket의 수를 충분히 크게 했으므로, 여러 개의 밴드 중에서 한 밴드라도 같은 해시값을 갖는 두 열이 있다면 유사하다고 판단한다. 이를 candidate pair라고 하며, 실제로는 유사할 수도, 아닐 수도 있지만 결과적으로 유사하다고 판단되는 문서 쌍이다. candidate pair가 실제로 reasonable한지 추가로 판단할 수도 있으나 이는 선택적이므로 다루지 않는다.
5. 예시 (Example)
나머지 과정은 직관적이므로, LSH의 예시만 확인하고자 한다. 100,000개의 문서 \(\rightarrow\) 열벡터와 100개의 해시함수에 대하여 min-hashing을 진행하여 행의 개수가 100, 열의 개수가 100,000이 된 행렬 \(M\)을 생각하자. 이 행렬을 가로로 20개의 밴드로 나누면 각 밴드는 5개의 행을 갖는다. 이제, similarity의 역치를 \(s=0.8\) (2. 목표 의 역치와는 반대임에 유의하라.)이라고 하자.
먼저, 실제로 Jaccard similarity가 \(0.8\)인 두 문서 \(C_1, C_2\)를 생각하자. Min-hashing 과정에 의하여 각 해시함수에 의한 signature가 같을 확률은 \(0.8\)이다. 각 밴드는 5개의 행으로 이루어져 있으므로 \(0.8^5=0.328\)의 확률로 완전히 일치한다. 반대로, 20개의 밴드가 모두 완전히 같지는 않을 확률은 \((1-0.8^5)^{20}=0.00035\)이다. 즉, 99.965%의 확률로는 맞게 판단하지만, 0.035%의 확률로는 \(C_1\)과 \(C_2\)가 유사하지 않다고 나온다. (false negative, 제2종 오류)
다음으로, 실제로 Jaccard similarity가 \(0.3\)인 두 문서 \(C_1, C_2\)를 생각하자. 각 해시함수에 의한 signature가 같을 확률이 \(0.3\)이므로 20개의 밴드가 모두 완전히 같지는 않을 확률은 \((1-0.3^5)^{20}=0.9526\)이다. 즉, 95.26%의 확률로는 맞게 판단하지만, 4.74%의 확률로는 \(C_1\)과 \(C_2\)가 유사하다고 나온다. (false positive, 제1종 오류)
6. 밴드 조정
LSH에서, \(r\)과 \(b\)의 값을 적절히 조절하면 제1종 오류와 제2종 오류의 확률을 바꿀 수 있다. \(p(x)=1-(1-x^r)^b\)와 similarity의 역치 \(s\)에 대하여, \(x<s\)인 범위에서 \(y=p(x)\) 아래 부분의 넓이가 제1종 오류의 확률, \(x>s\)인 범위에서 \(y=p(x)\) 위쪽 부분의 넓이가 제2종 오류의 확률이다.
직관적으로, \(r\)을 키우고 \(b\)를 줄이면 각 밴드가 완전히 일치할 확률도 줄어드는데 밴드 개수 자체도 적기 때문에 유사하다고 판단할 확률이 전체적으로 내려간다. 즉, 제2종 오류가 늘어나고 제1종 오류(false positive)가 줄어든다. 반대로, \(r\)을 줄이고 \(b\)를 키우면 각 밴드가 완전히 일치할 확률도 높아지고 밴드 개수도 많아지므로 (실제로 유사하지 않음에도) 유사하다고 판단할 확률이 전체적으로 높아진다. 즉, 제1종 오류가 늘어나고 제2종 오류(false negative)가 줄어든다.
실생활에서는 제1종 오류를 줄이는 것이 중요한 경우와, 제2종 오류를 줄이는 것이 중요한 경우가 모두 존재한다. 전염병 진단의 경우 제2종 오류를 줄이는 것이 중요할 것이고, 무죄 추정의 원칙의 경우 제1종 오류를 줄이는 것이 중요할 것이다. 이 경우도 마찬가지이다. 상황에 맞게 오류의 확률을 조절하는 것이 필요하다.