[Data Mining] Finding Similar Items : Locality Sensitive Hashing

Finding Similar Items

• 고차원의 데이터 공간(high-dimensional space)에서 가장 유사한 아이템(near-neighbors)을 찾는 작업은 중요한 작업들 중 하나이며, 많은 분야에서 사용되고 있습니다.
  • 페이지에서 유사한 단어 찾기
  • 유사한 상품을 구매한 사용자
  • 유사한 Feature 를 가진 이미지
• 하지만, 아이템 간 유사도 계산 과정에서는 다양한 문제들이 발생할 수 있습니다.
  • 각 아이템들의 Feature 표현 방식
  • 각 아이템들의 Feature Vector Dimension
  • 유사도 계산 시의 시간 복잡도
• 따라서, 해당 포스트에서는 여러개의 파일들(C1, C2, ..., Cn) 중 악성코드 파일을 찾는 작업이 주어졌을 때
• 해당 작업에서 발생할 수 있는 문제들과, 각각의 문제들을 해결할 수 있는 알고리즘들을 살펴보겠습니다.

1. 각 아이템들의 Feature 표현 방식

• 만약, 각 아이템들이 Text 파일이라면, 각 Text 파일들은 토큰화가 가능합니다.
  • 예를 들어, 파일의 내용이 "finding similar items" 라면
  • finding, similar, items 로 토큰화 할 수 있습니다.
• 이렇게 토큰화 된 Feature 들은 Sequence 또는 Set 형태로 표현할 수 있습니다.
  • Sequence : 순서대로 표현 (중복 허용)
    • finding, similar, items
  • Set : 집합으로 표현 (중복 비허용)
    • {finding, similar, items}
• Sequence, Set 에 따라 다양한 유사도 계산 방법을 사용할 수 있습니다.
  • Sequence
    • 예를 들어, m1 파일과 m2 파일이 아래와 같은 byte sequence 로 표현된다면
      • m1 = a, b, c, f
      • m2 = a, c, d
    • m1 과 m2 의 유사도 계산 방법 중, 가장 극단적인 방법으로는 string 유사도 계산 방법이 있습니다.
    • 또한, string 유사도 계산 알고리즘 중에서도, 가장 유명한 알고리즘 중 하나는,
    • 하나의 string 을 다른 string 으로 바꿀 때, 몇 번의 변환(추가 및 삭제)이 발생하느냐를 Count 해서 비교하는 방법입니다.
      • 예를 들어, [ m1 = a, b, c, f ] 이 [ m2 = a, c, d ] 가 되기 위해선, 3번의 변환이 필요합니다.
        • a 와 c 사이의 b 삭제
        • f 삭제
        • d 추가
    • 이처럼, 계산된 count 값을 통해, 두 개의 sequence 가 얼마나 유사한지 비교할 수 있습니다.
    • 하지만, 이렇게 sequence 를 비교하는 알고리즘은 굉장히 느리다는 단점이 있습니다.
  • Set
    • Sequence 표현을 Set 표현으로 바꿀 때는 아래와 같은 방법들을 사용할 수 있습니다.
      • 1-gram (1-shingling)
        • finding, similar, items → {finding, similar, items}
      • 2-gram (2-shingling)
        • finding, similar, items → {finding similar, similar items}
      • 3-gram (3-shingling)
        • finding, similar, items → {finding similar items}
    • 위와 같이, Feature 들을 Set 으로 표현했다면, jaccard 유사도 기법을 사용할 수 있습니다.
    • jaccard 유사도 기법은, 두 Set 이 얼마나 비슷한지 측정하는 가장 유명한 유사도 기법 중 하나이며, 아래와 같이 계산할 수 있습니다.
      • 예를 들어, A = {a, b, c} B = {a, b, d, e} 라면
      • j(A,B) 는 [ |A∩B| / |A∪B| = 2/5 = 0.4 ] 로 계산할 수 있습니다.
• 이처럼, 문서의 Feature 들을 Set 형태로 표현하는 방법을 "Shingling" 이라고 합니다.
  • 하지만, 위의 2-gram(2-shingling) 에서 "finding similar" 또는 "similar items" 와 같은 string 은, 종류에 따라 크게는 수십 byte 를 가질 수 있습니다.
  • 그렇게 되면 Set 의 Size 가 너무 커지게 됩니다.
  • 따라서, 각각의 Feature 를 Hash 함수를 통해 4 byte 정수 형태로 변환해서 사옹할 수 있습니다.
    • {1, 5}
  • 이후, 동일하게 Jaccard 유사도 등을 사용해 유사도를 비교할 수 있습니다.

2. 각 파일들의 Feature Vector Dimension

• 위처럼, 각 문서의 Feature 들은, Set 형태로 변환한 뒤, Feature Vector 로 표현할 수 있습니다.

• 하지만, 아무리 Feature 들을 중복이 제거된 Set 형태로 변환한다고 하더라도,

• 각 문서들의 Size 가 굉장히 크기 때문에,

• Feature Vector 의 dimension 이 너무 커지게 되며, 변환 시간 또한 굉장히 오래 걸리게 됩니다.

• 따라서, Set 의 Size 를 줄이는 방법으로 "Min-Hashing" 방법이 존재합니다.

• "Min-Hashing" 알고리즘의 순서는 아래와 같습니다.

• 만약, 우리가 4개의 문서를 가지고 있다면, 위 1번 과정을 통해, 각각의 문서에 대한 k-shingles Feature 를 생성할 수 있습니다.

• 이때, 만약 4가지 문서에서 추출한 k-shingles 의 합집합 개수가 총 7개라면,

• 우리는 각 문서내의 Feature 등장 여부에 따라, 아래와 같은 Matrix 를 생성할 수 있습니다.

  

• 위 Matrix 의 열(Documents)을 순서대로 C1, C2, C3, C4 라고 지정한다면

• C1 문서와 C2 문서의 jaccard 유사도는 3/6 으로 계산할 수 있습니다.

• 하지만, 만약 document 의 개수가 100만개 이상이라면,

• shingles 의 개수는 각 document 에 등장한 Feature 들의 합집합이므로, 더 많아질 것이고

• 그렇게 되면 Matrix 의 Size 는 굉장히 커지게 되며,

• 크기에 비해 매우 Sparse 하기 때문에, 계산에 많은 낭비가 발생하게 될 것 입니다.

  • 문서에서 등장한 shingle = 1
  • 문서에서 등장하지 않은 shingle = 0
  • 0 이 많은 Matrix 는 Sparse Matrix

• 따라서, 문서 간 유사도는 유지하면서, 큰 Matrix 를 압축시키기 위한 방법이 "min-hashing" 알고리즘 입니다.

  • 우리는 "min-hashing" 알고리즘의 hash 함수를 사용해,
  • Columns(Documents) 를 작은 signature 값으로 압축할 수 있습니다.

• "Min-Hashing" 알고리즘의 순서는 아래와 같습니다.

• 우선, Columns(Documents) 길이만큼의 random index 를 가지는, Permutation π 해쉬 함수를 생성합니다.

  

  • 위 예제에서 Permutation π 해쉬 함수는 3개 입니다.

• 이후, 첫 번째 갈색 permutation π 를 살펴봅니다.

  

  • 첫 번째 갈색 permutation π 에서 index 가 1 인 row 와 동일한, document 들의 row 들을 살펴봅니다.

  • document 들의 row 에, 1 이 있는지 확인합니다.

  • C2 와 C4 에, 1 이 나타났으므로,

  • 해당 permutation π 의 index 값을 signature matrix M 에 저장합니다.

  • 하지만 아직, C1 과 C3 에는, 1 이 나타나지 않았으므로,

  • permutation π 에서 index 가 2 인 row 와 동일한, document 들의 row 들을 살펴봅니다.

    

  • document 들의 row 들 중, C1 과 C3 에 1 이 나타났으므로,

  • 해당 permutation π 의 index 값을 signature matrix M 에 저장합니다.

  • 첫 번째 갈색 permutation π 를 총 4개의 문서에 적용하는 과정을 통해,

  • signature matrix 의 첫 번째 행을 완성할 수 있습니다.

• 이후에도 동일하게, 두 번째 노란색 permutation π 와 세 번째 permutation π 를 사용해,

• Columns(Documents) 에 1 이 처음으로 등장하는 permutation index 를 Signature Matrix M 에 저장하는 방식으로 진행한다면, Signature Matrix 가 완성됩니다.

  

• 위와 같은 "min-hashing" 알고리즘을 통해

• Input Matrix 의 Shingles 를 압축한 Signature Matrix M 을 생성할 수 있습니다.

• 또한, Signature Matrix M 의 Column 이 서로 유사하다면, Input Matrix 에서도 유사한 Column 을 가지는 것을 유추할 수 있습니다.

3. 유사도 계산 시의 시간 복잡도

• 2번의 과정을 통해, Input Matrix 의 Shingles 를 압축한 Signature Matrix M 을 생성했다면

• 이제, n 개의 문서들(C1, C2, ..., Cn)을 2개씩 쌍으로 묶어 유사도를 비교(pair-wise comparison) 해야합니다.

• 기본적으로는 (C1, C2), (C1, C3), ... , (Cn-1, Cn) 과 같은 방법으로 비교할 수 있으며,

• [ nC2 = n(n-1)/2 ] 횟수 만큼 비교해야합니다.

• 하지만, 해당 방법은 O(n^2) 의 시간복잡도를 가진다는 단점이 있습니다.

  • n^2 이 넘어간다는 건, 사용할 수 없다고 봐야한다.

• 따라서, 이러한 문제를 해결하기 위해, O(N) 의 시간 복잡도만으로 Column 간 유사도를 계산할 수 있는 "LSH(Locality-Sensitive Hasing)" 알고리즘이 존재합니다.

• "LSH(Locality-Sensitive Hasing)" 알고리즘의 순서는 다음과 같습니다.

• 우선, signature matrix M 의 Column 을 b 개의 band 만큼 자릅니다.

  

  • 예를 들어, 한 Column 의 길이는 100 이며, Column 을 10 개의 band 로 잘라, 각 band 별로 10개의 row 를 가진다고 가정합니다.

• 이후, 각 band 별로 band 의 값들을 concat 합니다.

  • 예를 들어, 첫 번째 band 에 2,1,4,...,8 과 같이 10 개의 row 가 있다면
  • 이를 concat 해 214..8 와 같은 하나의 숫자로 만듭니다.

• 그럼, 해당 Column 은 band 별로 1개의 숫자를 가지게 되며, band 가 10개이므로 총 10개의 숫자를 가지게 됩니다.

  • 예를 들어, 214..8, 145..6, ..., 313..5 와 같이 구성될 수 있습니다.

• 이후, band 별 해쉬 함수와 모든 band 와 document 에서 사용할 해쉬 테이블을 준비합니다.

• 우선, C1 의 첫 번째 band 숫자에 해쉬 함수를 적용한 뒤, 해쉬 테이블 bucket 에 매핑합니다.
  • h(C1.b1)
• 그리고 C1 의 두번째 band 숫자에 해쉬 함수를 적용한 뒤, 해쉬 테이블 bucket 에 매핑합니다.
  • h(C1.b2)
• C1 는 총 10개의 band 를 가지고 있으므로, 위와 같은 방법으로 10개의 해쉬값을 해쉬 테이블 bucket 에 매핑합니다.
  • h(C1.h1), h(C1.h2), ..., h(C1.h10)
• 위와 같은 방법을 모든 document(C1, C2, ..., Cn) 에 적용해 전체 해쉬 테이블을 완성합니다.
  • h(C1.h1), h(C1.h2), ..., h(C1.h10)
  • ...
  • h(C4.h1), h(C4.h2), ..., h(C4.h10)
• 그렇다면, 전체 해쉬 테이블에 각 Document 들의 band 들이 매핑될 것이며
• 동일한 bucket 에 매핑된(충돌된) band 들은 유사하다고 볼 수 있고
• 유사한 band 들이 많은 column 쌍은 유사하다고 볼 수 있습니다.

전체적인 순서

1. Document 가 주어지면,
2. 우선, 해당 Document 의 토큰들을 Shingling 을 통해 집합으로 표현합니다.
3. 이후, Min-Hashing 를 통해 집합의 사이즈를 고정된 크기로 줄입니다.
4. 마지막으로, 모든 문서들을 pair-wise 단위로 유사도 비교하는 것은 O(n^2) 의 시간복잡도를 가지므로, Locality-Sensitive Hashing 을 통해 O(N) 의 시간복잡도로 유사도를 비교합니다.

참고

• Stanford University (Mining of Massive Datasets)
  • http://www.mmds.org
• https://jeongchul.tistory.com/604?category=593875