[Vector Similarity Search] 3 Traditional Methods for Similarity Search - Jaccard / w-shingling / Levenshtein

Jaccard

 

Jaccard 유사도는 두 개체간의 유사성을 계산한다.
예를 들어 두 텍스트 문서의 유사성을 계산하는데 활용할 수 있다.
계산 방식은 교집합을 합집합으로 나눈 것이다.

 

def jaccard(x: str,  y: str):
  # convert to sets
  x = set(x.split())
  y = set(y.split())

  # calculate
  intersection = x.intersection(y)
  union = x.union(y)

  return len(intersection)/len(union)

 

 

다음 두 문장의 Jaccard 유사도를 계산해본다고 하자.

b와 c의 교집합은 위 하이라이트가 되어있는 단어 6개이다.
합집합은 21개의 단어이므로 6/21이 Jaccard Similarity가 될 것이다.

 

 

W-shingling

n-gram을 기준으로 토큰을 나누고 Jaccard Simialrity를 구하는 방법이다.

 

예를들어 uni-gram으로 나눈다고 한다면 위에서 했던 것과 똑같은 결과가 나올 것이다.

 

def jaccard(x: str,  y: str):
  # convert to sets
  x = set(x)
  y = set(y)

  # calculate
  intersection = x.intersection(y)
  union = x.union(y)

  return len(intersection)/len(union)

# uni-gram
b = b.split()
b_unigram = [b[i] for i in range(len(b))]

c = c.split()
c_unigram = [c[i] for i in range(len(c))]

 

 

bi-gram으로 나누는 것은 아래처럼 두 단어를 연속적으로 나열한 형태이다.

 

 

Levenshtein

단어 간 거리는 형태적 거리와 의미적 거리로 분류할 수 있다.

Word2Vec같이 단어 간 의미적 유사성을 벡터로 표현하는 경우 (도서관, 책방) 벡터 간 거리는 작을 것이다. 
그러나 두 글자 사이에 공통된 음절이 없기 때문에 형태적 거리는 크다. 
이렇게 string의 형태적 거리를 정의하는 방법을 string distance라고 한다.

String distance은 오탈자 교정에 활용할 수 있다.
해당 방법을 이용해 챗봇에서 entity 매칭을 할 때 오탈자도 어느정도 인식하여 매칭하도록 사용해본 경험이 있다.

이런 String distance metric 중 하나는 Levenshtein distance이다.

Levenshetein distance는 한 단어를 다른 단어로 변경하는데 필요한 한 문자의 편집(삽입/삭제/대체)의 최소 횟수이다.

예를 들어 dream와 dream이라는 두 단어가 주어졌다면 두 단어가 동일하므로 Levenshetein 거리는 0이다.

만약 dream와 steam이라는 두 단어가 주어졌다면 dr을 st로 변경하기 위해서는 두 번 편집해야하므로 Levenshetien 거리는 2가 된다.

따라서 Levenshtein 거리가 크면 두 문서의 유사도는 낮다는 것이고, 거리가 작으면 두 문서는 유사도가 높은 것이다.

 

 

 

hello와 kelm 두 단어의 Levenshtein 거리를 구할 경우, 아래 그림처럼 3이라는 값이 나오는데
이는 kelm을 hello로 변환시키기 위해서는 3 edist이 필요하다는 뜻이다.

1. b를 h로 substitution
2. m을 l로 substituiton
3. o를 inserting 

https://blog.paperspace.com/measuring-text-similarity-using-levenshtein-distance/

 

 

import numpy as np

def leven(a, b):
  # add an additional character at the start of each string
  a = f" {a}"
  b = f" {b}"

  # initialize empty zero array
  lev = np.zeros((len(a), len(b)))

  # begin iterating through each value, finding the best path
  for i in range(len(a)):
    for j in range(len(b)):
      if min([i, j]) == 0:
        lev[i, j] = max([i, j])
      else:
        # calculate three possible operations
        x = lev[i-1, j] # deletion
        y = lev[i, j-1] # insertion
        z = lev[i-1, j-1] # substitution
        
        # get minimum
        lev[i, j] = min([x,y,y])

        # if two current characters don't match, add 1
        if a[i] != b[j]:
          lev[i, j] += 1
  return lev, lev[-1, -1]

 

 

 

---

Reference

https://towardsdatascience.com/text-similarity-w-levenshtein-distance-in-python-2f7478986e75

https://www.youtube.com/watch?v=AY62z7HrghY&list=PLIUOU7oqGTLhlWpTz4NnuT3FekouIVlqc 

https://lovit.github.io/nlp/2018/08/28/levenshtein_hangle/

https://blog.paperspace.com/measuring-text-similarity-using-levenshtein-distance/