Similarity & Dimensionality Reduction (kd-tree, Fingerprint, Random Projection, JL Transform, MinHash)

출처 : http://timroughgarden.org/notes.html

Similarity Search

• Applications

  • Similar documents, web pages, etc.
  • Collaborative filtering : 비슷한 제품 찾거나 비슷한 구매자 찾아주기
  • Machine learning / classification : 비슷한 두 datapoint -> same label
  • Combining datasets : 천문학에서 사진들 추가/분류

Similarity Metrics

• Jaccard Similarity

  • Given S, T \in U, J(S, T) = |intersection(S, T)| / |union(S, T)|

• L_p Distance

  • ||x - y||_p = ( \sum{1 <= i <= d}(|x_i - y_i|^p) )^(1/p)
  • p=1이면 manhattan distance, p=2면 Euclidean distance, p=\inf면 max_i distance.
  • p=2일 때에만 rotationally invariant.
    • 즉, 각 coordinate가 특별한 무언가를 뜻하는 게 아니라면 p!=2를 사용하는 건 권장되지 않음.

kd-tree

• Algorithm

  • kd-tree는 기본적으로 binary search tree.

  • Insertion

    • 현재 노드 v에 set S가 주어졌다고 하자. x_i \in S는 R^d의 elt.
    • n = 1이면 v에 x_1을 넣고 종료
    • Otherwise, 1 <= i <= d인 i를 하나 고르자. (suggested heuristic이 다양하게 있음.)
    • m = median(x_1(i), x_2(i), ..., x_n(i))으로 잡고, i와 m을 v에 저장한다.
    • i-th coordinate가 m 미만이면 S_<, m 이상이면 S_>= 로 보내서 재귀적으로 알고리즘을 수행한다.

  • Find

    • x가 들어갔을 leaf node를 찾는다.
    • 거기서부터 위로 올라오면서, "closest point to x가 반대쪽 child subtree에 있을 수 있겠는가?"를 생각한다.
      • If yes, 거기도 탐색한다.
      • ex) d=1이면 항상 no.

• 한계

  • high dimensional data에서는 잘 작동하지 않는다.
    • d <= 20 or n >= 2^d 여야지 잘 작동한다.

Fingerprint

• Preserves what?

  • distinctness

• Algorithm

  • hash func h를 고른 다음, f(x) = h(x) / Z_2 로 고르자.
  • 그러면 P[f(x) = f(y)] <= 1/2
  • hash func의 수를 늘려서 원하는 probability까지 낮춘다.

Random Projection

• Preserves what?

  • L_2 distance

• Algorithm

  • R^k를 R^d로 project한다고 가정하자.
  • 각 coord.를 N(0, 1)에서 뽑은 random vector r \in R^k를 만들자.
  • E[ (<r, x> - <r, y>)^2 ] = d(x, y)^2
  • R^k의 n points의 nC2개의 interpoint L_2 distance를 1±ε factor로 유지하고 싶다면, d = Θ(ε^(-2) log n) 으로 잡으면 된다.
    • Θ의 factor는 2 미만이라 보면 된다.

Johnson-Lindenstrauss Transform

• Preserves what?
  • L_2 distance
• Algorithm
  • d x k matrix A의 각 coord.를 N(0, 1)에서 뽑은 다음에, JL(A, x) = (1/sqrt(d))Ax 로 transform하자.
  • 그러면 ||JL(A, x)||^2 은 d개의 random projection에서 나온 'squared L_2 distance estimation'의 mean이 된다.
• 개선점
  • A의 각 coord.를 {-1, +1}에서 random하게 뽑아도 된다. (경험적/이론적으로 모두 증명됨.)
  • Ax를 계산할 때 FFT를 쓰면 빨라진다.
  • d는 수 백 정도가 된다. 더 줄이고 싶으면 locality sensitive hashing을 사용할 수 있다.
    • x와 x'가 비슷하면 h(x)와 h(x')가 같은 bucket에 들어갈 가능성이 높은 hashing이다.

MinHash

• Preserves what?

  • Jaccard similarity

• Algorithm

  • Permutation π : U -> U 를 random하게 고른다.
  • S \in U에 대해, MinHash(S) = argmin{x in \S} π(x) 라고 하자.
  • 그러면 A, B \in U에 대해 P[ MinHash(A) = MinHash(B) ] = J(A, B)
    • 왜? π가 random하게 골라지기 때문에, MinHash(A) = MinHash(B) iff union(A, B)의 min elt가 intersection(A, B)의 elt.