[es] kNN vs ANN test

kNN ( k-nearest neighbor ) 검색은 유사성 메트릭으로 측정된 쿼리 벡터에 가장 가까운 k 개의 벡터를 찾습니다 .

 

ANN ( approximate nearest neighbor search )

KD-트리와 같은 저차원 벡터에는 kNN에 대한 잘 확립된 데이터 구조가 있습니다. 실제로 Elasticsearch는 KD-트리를 통합하여 지리 공간 및 숫자 데이터에 대한 검색을 지원합니다. 그러나 텍스트 및 이미지에 대한 최신 임베딩 모델은 일반적으로 100 - 1000개 또는 그 이상의 요소로 구성된 고차원 벡터를 생성합니다. 이러한 벡터 표현은 고차원에서 가장 가까운 이웃을 효율적으로 찾는 것이 매우 어렵기 때문에 고유한 문제를 제시합니다.

이러한 어려움에 직면한 가장 가까운 이웃 알고리즘은 일반적으로 속도를 향상시키기 위해 완벽한 정확도를 희생합니다. 이러한 근사 최근접 이웃(ANN) 알고리즘은 항상 진정한 k개의 최근접 벡터를 반환하지 않을 수 있습니다. 그러나 효율적으로 실행되어 우수한 성능을 유지하면서 대규모 데이터 세트로 확장됩니다.

 

kNN,  ANN 하고 그냥 match 쿼리의 성능을 비교 해봐야 하는데...

project path : /Users/doo/project/tf-embeddings

 

#가상환경  목록확인
conda info --envs 

#가상환경 생성
conda create --name "text" python="3.7"

#가상환경 실행
conda activate text

kNN

• 검색 대상 벡터와 모든 벡터와의 거리를 계산 
• 가장 거리가 가까운 K개를 리턴 
• 256차원 벡터 150~200만 개, K가 1000쯤 되면 응답 시간이 느려지기 시작

ANN

• 특정 방식으로 검색 대상 벡터와 가까운 벡터를 찾아내는 기법
• Spotify의 Annoy 알고리즘
• 데이터를 추가하기 힘들다

 

HNSW

Hierarchical Navigable Small Worlds

---

선행작업 900gle 에서 사용중인 DB 데이터를 추출하여 파일로 생성 

conda activate doo

#conda deactivate 는 가상환경 종료

python db/db_select_extract_json.py 

#하면 json_data.json 이 생성됨
#일단 가상환경 종료 하고
#아래 put_data.py를 실행하면 인덱스가 생성되고 조금전 생성한 json 파일을 색인한다. 

(900gle) ➜  tf-embeddings git:(main) ✗ python ann/abc/put_data.py

 

인덱스 생성 및 색인 

 

 

 

ANN 은 가이드에서 나온 대로 ..  kNN 은 dense_vector 512 차원

match 는 knn 과 같지만 name에 match 쿼리만 실행할 예정  

    INDEX_NAME_A = "ann-index"
    INDEX_FILE_A = "./data/products/ann-index.json"

    INDEX_NAME_B = "knn-index"
    INDEX_FILE_B = "./data/products/knn-index.json"

    INDEX_NAME_C = "match-index"
    INDEX_FILE_C = "./data/products/knn-index.json"

 

put_data.py 실행

인덱스 생성 

 

이부분 수정  doc['name_vector'] 에서 'name_vector'

"source": "cosineSimilarity(params.query_vector, 'name_vector') + 1.0",

 

테스트 케이스를 추가해야겠다. 

name_vector : 상품명 embedding

category_vector : 카테고리 embedding

feature_vector : 상품명 + 카테고리 embedding

 

# -*- coding: utf-8 -*-
import time
import json

from elasticsearch import Elasticsearch
from elasticsearch.helpers import bulk

import tensorflow_hub as hub
import tensorflow_text
import matplotlib.pyplot as plt
import kss, numpy

##### SEARCHING #####

def run_query_loop():
    while True:
        try:
            handle_query()
        except KeyboardInterrupt:
            return

def handle_query():
    query = input("Enter query: ")

    embedding_start = time.time()
    query_vector = embed_text([query])[0]
    embedding_time = time.time() - embedding_start

    with open(ANN) as index_file:
        script_query_a = index_file.read().strip()
        script_query_a = script_query_a.replace("${query_vector}", str(query_vector))
        script_query_a = script_query_a.replace("${SEARCH_SIZE}", str(SEARCH_SIZE))

    with open(KNN) as index_file:
        script_query_b = index_file.read().strip()
        script_query_b = script_query_b.replace("${query_vector}", str(query_vector))
        script_query_b = script_query_b.replace("${SEARCH_SIZE}", str(SEARCH_SIZE))

    with open(MATCH) as index_file:
        script_query_c = index_file.read().strip()
        script_query_c = script_query_c.replace("${query}", str(query))
        script_query_c = script_query_c.replace("${SEARCH_SIZE}", str(SEARCH_SIZE))

    search_start = time.time()
    response_a = client.search(
        index=INDEX_NAME_A,
        body=script_query_a
    )
    response_b = client.search(
        index=INDEX_NAME_B,
        body=script_query_b
    )

    print(script_query_c)
    response_c = client.search(
        index=INDEX_NAME_C,
        body=script_query_c
    )

    search_time = time.time() - search_start
    score_a =[]
    score_b =[]
    score_c =[]

    print("검색어 :", query)
    print("CASE A : ")
    for hit in response_a["hits"]["hits"]:
        score_a.append(hit["_score"])
        print("name: {}, category: {}, score: {}".format(hit["_source"]["name"], hit["_source"]["category"], hit["_score"]))

    print("CASE B : ")
    for hit in response_b["hits"]["hits"]:
        score_b.append(hit["_score"])
        print("name: {}, category: {}, score: {}".format(hit["_source"]["name"], hit["_source"]["category"], hit["_score"]))

    print("CASE C : ")
    for hit in response_c["hits"]["hits"]:
        score_c.append(hit["_score"])
        print("name: {}, category: {}, score: {}".format(hit["_source"]["name"], hit["_source"]["category"], hit["_score"]))

    t= range(0, SEARCH_SIZE)
    plt.rcParams['font.family'] = 'AppleGothic'

    fig, ax = plt.subplots()
    ax.set_title('ANN vs kNN vs match')
    line1, = ax.plot(t, score_a, lw=2, label='ANN')
    line2, = ax.plot(t, score_b, lw=2, label='kNN')
    line3, = ax.plot(t, score_c, lw=2, label='match')
    leg = ax.legend(fancybox=True, shadow=True)

    ax.set_ylabel('score')
    ax.set_xlabel('top' + str(SEARCH_SIZE))

    lines = [line1, line2, line3]
    lined = {}  # Will map legend lines to original lines.
    for legline, origline in zip(leg.get_lines(), lines):
        legline.set_picker(True)  # Enable picking on the legend line.
        lined[legline] = origline


    def on_pick(event):
        legline = event.artist
        origline = lined[legline]
        visible = not origline.get_visible()
        origline.set_visible(visible)
        legline.set_alpha(1.0 if visible else 0.2)
        fig.canvas.draw()

    fig.canvas.mpl_connect('pick_event', on_pick)
    plt.show()




##### EMBEDDING #####

def embed_text(input):
    vectors = embed(input)
    return [vector.numpy().tolist() for vector in vectors]

##### MAIN SCRIPT #####

if __name__ == '__main__':
    INDEX_NAME_A = "ann-index"
    INDEX_NAME_B = "knn-index"
    INDEX_NAME_C = "match-index"

    ANN = "ann/query/ann_query.json"
    KNN = "ann/query/knn_query.json"
    MATCH = "ann/query/match_query.json"

    SEARCH_SIZE = 5

    print("Downloading pre-trained embeddings from tensorflow hub...")
    embed = hub.load("https://tfhub.dev/google/universal-sentence-encoder-multilingual-large/3")
    client = Elasticsearch(http_auth=('elastic', 'dlengus'))
    run_query_loop()
    print("Done.")

 

ann_query.json

{
  "query": {
    "match_all": {}
  },
  "knn": {
    "field": "name_vector",
    "query_vector": ${query_vector},
    "k": 5,
    "num_candidates": 50,
    "boost": 0.1
  },
  "size": ${SEARCH_SIZE}
}

knn_query.json

{
  "query": {
    "script_score": {
      "query": {
        "match_all": {}
      },
      "script": {
        "source": "cosineSimilarity(params.query_vector, 'name_vector') + 1.0",
        "params": {
          "query_vector": ${query_vector}
        }
      }
    }
  },
  "size": ${SEARCH_SIZE}
}

match_query.json

{
  "query": {
    "match": {
      "name": {
        "query": "${query}",
        "boost": 0.9
      }
    }
  },
  "size": ${SEARCH_SIZE}
}

kNN ,ANN, match 쿼리 의 결과는 개발잡부에서 다루었으므로.. 

multi ANN 의 테스트를 해봐야겠음

https://ldh-6019.tistory.com/379

[es8] kNN vs ANN 성능비교