[search]k-nearest neighor (kNN) search

250x250

Notice

Recent Posts

Recent Comments

Link

« 2024/12 »
일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

Tags more

Archives

Today

Total

관리 메뉴

아빠는 개발자

[search]k-nearest neighor (kNN) search 본문

Search/kNN Search

[search]k-nearest neighor (kNN) search

father6019 2023. 9. 1. 23:34

728x90

k-nearest neighor (kNN) search

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

kNN의 일반적인 사용 사례는 다음과 같습니다.

자연어 처리(NLP) 알고리즘 기반 관련성 순위
제품 추천 및 추천 엔진
이미지 또는 비디오에 대한 유사성 검색

전제 조건

kNN 검색을 실행하려면 데이터를 의미 있는 벡터 값으로 변환할 수 있어야 합니다. Elasticsearch 외부에서 이러한 벡터를 생성하고 dense_vector 필드 값으로 문서에 추가합니다. 쿼리는 동일한 차원의 벡터로 표시됩니다.
유사성 메트릭을 기반으로 문서의 벡터가 쿼리 벡터에 가까울수록 더 잘 일치하도록 벡터를 디자인합니다.
이 가이드의 단계를 완료하려면 다음 인덱스 권한이 있어야 합니다 .
- create_index또는 필드가 manage있는 인덱스를 만들려면 dense_vector
- create, index, 또는 write생성한 인덱스에 데이터 추가
- read색인을 검색하려면

kNN 방법

Elasticsearch는 kNN 검색을 위한 두 가지 방법을 지원합니다.

script_score벡터 함수가 있는 쿼리를 사용하는 정확한 무차별 대입 kNN
knn검색 옵션을 사용한 대략적인 kNN

대부분의 경우 대략적인 kNN을 사용하는 것이 좋습니다. 대략적인 kNN은 더 느린 인덱싱과 불완전한 정확도를 희생시키면서 더 짧은 대기 시간을 제공합니다.

정확하고 무차별적인 kNN은 정확한 결과를 보장하지만 대규모 데이터 세트로 잘 확장되지 않습니다. 이 접근 방식을 사용하면 script_score쿼리가 일치하는 각 문서를 스캔하여 벡터 함수를 계산해야 하므로 검색 속도가 느려질 수 있습니다. 그러나 쿼리를 사용하여 함수에 전달되는 일치하는 문서의 수를 제한함으로써 대기 시간을 개선할 수 있습니다. 데이터를 문서의 작은 하위 집합으로 필터링하는 경우 이 접근 방식을 사용하여 좋은 검색 성능을 얻을 수 있습니다.

정확한 kNN

정확한 kNN 검색을 실행하려면 script_score벡터 함수와 함께 쿼리를 사용하십시오.

하나 이상의 dense_vector필드를 명시적으로 매핑합니다. 대략적인 kNN에 필드를 사용하지 않으려면 index매핑 옵션을 생략하거나 로 설정합니다 false. 이렇게 하면 인덱싱 속도가 크게 향상될 수 있습니다.

PUT product-index
{
  "mappings": {
    "properties": {
      "product-vector": {
        "type": "dense_vector",
        "dims": 5,
        "index": false
      },
      "price": {
        "type": "long"
      }
    }
  }
}

데이터를 인덱싱합니다.

POST product-index/_bulk?refresh=true
{ "index": { "_id": "1" } }
{ "product-vector": [230.0, 300.33, -34.8988, 15.555, -200.0], "price": 1599 }
{ "index": { "_id": "2" } }
{ "product-vector": [-0.5, 100.0, -13.0, 14.8, -156.0], "price": 799 }
{ "index": { "_id": "3" } }
{ "product-vector": [0.5, 111.3, -13.0, 14.8, -156.0], "price": 1099 }
...

검색 API를 사용하여 벡터 함수가 script_score 포함된 쿼리를 실행합니다 .

POST product-index/_search
{
  "query": {
    "script_score": {
      "query" : {
        "bool" : {
          "filter" : {
            "range" : {
              "price" : {
                "gte": 1000
              }
            }
          }
        }
      },
      "script": {
        "source": "cosineSimilarity(params.queryVector, 'product-vector') + 1.0",
        "params": {
          "queryVector": [-0.5, 90.0, -10, 14.8, -156.0]
        }
      }
    }
  }
}

벡터 함수에 전달되는 일치 문서의 수를 제한하려면 매개변수에 필터 쿼리를 지정하는 것이 좋습니다 script_score.query. match_all필요한 경우 이 매개변수의 쿼리를 사용하여 모든 문서를 일치시킬 수 있습니다 . 그러나 모든 문서를 일치시키면 검색 대기 시간이 크게 늘어날 수 있습니다.

대략적인 kNN

다른 유형의 검색과 비교할 때 근사 kNN 검색에는 특정 리소스 요구 사항이 있습니다. 특히 모든 벡터 데이터는 노드의 페이지 캐시에 맞아야 효율적입니다. 구성 및 크기 조정에 대한 중요한 참고 사항은 대략적인 kNN 검색 튜닝 가이드를 참조하십시오 .

대략적인 kNN 검색을 실행하려면 인덱싱이 활성화된 하나 이상의 필드를 검색하는 knn옵션을dense_vector 사용하십시오 .

하나 이상의 dense_vector필드를 명시적으로 매핑합니다. 대략적인 kNN 검색에는 다음 매핑 옵션이 필요합니다.
```
PUT image-index
{
  "mappings": {
    "properties": {
      "image-vector": {
        "type": "dense_vector",
        "dims": 3,
        "index": true,
        "similarity": "l2_norm"
      },
      "title": {
        "type": "text"
      },
      "file-type": {
        "type": "keyword"
      }
    }
  }
}
```
- 값 . index_true
- 값 similarity. 이 값은 쿼리와 문서 벡터 간의 유사성을 기반으로 문서 점수를 매기는 데 사용되는 유사성 메트릭을 결정합니다. 사용 가능한 측정항목 목록은 similarity 매개변수 문서를 참조하세요.
데이터를 인덱싱합니다.

컬로 복사 콘솔에서 보기

POST image-index/_bulk?refresh=true
{ "index": { "_id": "1" } }
{ "image-vector": [1, 5, -20], "title": "moose family", "file-type": "jpg" }
{ "index": { "_id": "2" } }
{ "image-vector": [42, 8, -15], "title": "alpine lake", "file-type": "png" }
{ "index": { "_id": "3" } }
{ "image-vector": [15, 11, 23], "title": "full moon", "file-type": "jpg" }

knn옵션을 사용하여 검색을 실행합니다 .

POST image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [-5, 9, -12],
    "k": 10,
    "num_candidates": 100
  },
  "fields": [ "title", "file-type" ]
}

문서 는_score 쿼리와 문서 벡터 간의 유사성에 의해 결정됩니다. similarity. kNN 검색 점수 계산 방법에 대한 자세한 내용은 를 참조하십시오 .

대략적인 kNN 검색에 대한 지원이 버전 8.0에 추가되었습니다. 이전에는 필드가 매핑에서 dense_vector활성화를 지원하지 않았습니다 . index필드 를 포함하는 8.0 이전의 인덱스를 만든 경우 dense_vector대략적인 kNN 검색을 지원하려면 를 설정하는 새 필드 매핑을 사용하여 데이터를 다시 인덱싱해야 합니다 index: true.

속도 또는 정확도를 위해 대략적인 kNN 조정

결과를 수집하기 위해 kNN 검색 API는 num_candidates각 샤드에서 가장 가까운 이웃 후보를 찾습니다. 검색은 이러한 후보 벡터와 쿼리 벡터의 유사성을 계산하여 k 각 샤드에서 가장 유사한 결과를 선택합니다. 그런 다음 검색은 각 샤드의 결과를 병합하여 전역에서 가장 k가까운 이웃을 반환합니다.

num_candidates더 느린 검색 속도를 희생시키면서 더 정확한 결과를 얻기 위해 증가시킬 수 있습니다 . 값이 높은 검색은 num_candidates 각 샤드에서 더 많은 후보를 고려합니다. 이 작업은 시간이 더 걸리지만 검색에서 진정한 k최상위 최근접 이웃을 찾을 확률이 더 높습니다.

num_candidates마찬가지로 잠재적으로 덜 정확한 결과로 더 빠른 검색을 위해 줄일 수 있습니다 .

바이트 벡터를 사용한 대략적인 kNN

근사 kNN 검색 API는 값 byte벡터 외에도 float값 벡터를 지원합니다. 이 knn옵션을 사용하여 로 설정되고 인덱싱이 활성화된 dense_vector필드를 검색합니다 .element_typebyte

로 설정되고 인덱싱이 활성화된 하나 이상의 dense_vector필드를 명시적으로 매핑합니다 .element_type byte

PUT byte-image-index
{
  "mappings": {
    "properties": {
      "byte-image-vector": {
        "type": "dense_vector",
        "element_type": "byte",
        "dims": 2,
        "index": true,
        "similarity": "cosine"
      },
      "title": {
        "type": "text"
      }
    }
  }
}

모든 벡터 값이 [-128, 127] 범위 내의 정수인지 확인하여 데이터를 인덱싱합니다.

POST byte-image-index/_bulk?refresh=true
{ "index": { "_id": "1" } }
{ "byte-image-vector": [5, -20], "title": "moose family" }
{ "index": { "_id": "2" } }
{ "byte-image-vector": [8, -15], "title": "alpine lake" }
{ "index": { "_id": "3" } }
{ "byte-image-vector": [11, 23], "title": "full moon" }

query_vector 값이 [-128, 127] 범위 내의 정수인지 확인하는 knn옵션을 사용하여 검색을 실행합니다 .

POST byte-image-index/_search
{
  "knn": {
    "field": "byte-image-vector",
    "query_vector": [-5, 9],
    "k": 10,
    "num_candidates": 100
  },
  "fields": [ "title" ]
}

필터링된 kNN 검색

kNN 검색 API는 필터를 사용한 검색 제한을 지원합니다. k검색은 필터 쿼리와도 일치하는 상위 문서를 반환합니다 .

다음 요청은 file-type필드로 필터링된 대략적인 kNN 검색을 수행합니다.

POST image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [54, 10, -2],
    "k": 5,
    "num_candidates": 50,
    "filter": {
      "term": {
        "file-type": "png"
      }
    }
  },
  "fields": ["title"],
  "_source": false
}

일치하는 문서가 반환 되도록 대략적인 kNN 검색 중에 필터가 적용됩니다 k. 이는 대략적인 kNN 검색이 완료된 후 필터가 적용되는 사후 필터링 접근 방식과 대조됩니다 . 사후 필터링에는 일치하는 문서가 충분히 있는 경우에도 k개 미만의 결과를 반환하는 경우가 있다는 단점이 있습니다.

대략적인 kNN을 다른 기능과 결합편집하다

옵션 과 다음을 모두 제공하여 하이브리드 검색을 수행할 수 있습니다 .knn query

POST image-index/_search
{
  "query": {
    "match": {
      "title": {
        "query": "mountain lake",
        "boost": 0.9
      }
    }
  },
  "knn": {
    "field": "image-vector",
    "query_vector": [54, 10, -2],
    "k": 5,
    "num_candidates": 50,
    "boost": 0.1
  },
  "size": 10
}

이 검색은 전역 상위 k = 5벡터 일치 항목을 찾아 쿼리의 일치 항목과 결합 match하고 마지막으로 상위 점수 결과 10개를 반환합니다. knn및 일치 항목 query은 마치 부울 또는 둘 사이에 있는 것처럼 분리를 통해 결합됩니다. 상위 k벡터 결과는 모든 인덱스 샤드에서 전역 최근접 이웃을 나타냅니다.

knn각 안타의 점수는 와 점수 의 합입니다 query. boost합계의 각 점수에 가중치를 부여할 값을 지정할 수 있습니다 . 위의 예에서 점수는 다음과 같이 계산됩니다.

점수 = 0.9 * match_score + 0.1 * knn_score

이 knn옵션은 와 함께 사용할 수도 있습니다 aggregations. 일반적으로 Elasticsearch는 검색과 일치하는 모든 문서에 대한 집계를 계산합니다. 따라서 대략적인 kNN 검색의 경우 가장 k 가까운 상위 문서에서 집계가 계산됩니다. 검색에 가 포함된 경우 집계는 및 일치 query의 결합된 집합에서 계산됩니다 .knnquery

시맨틱 검색 수행

이 기능은 기술 미리 보기 상태이며 향후 릴리스에서 변경되거나 제거될 수 있습니다. Elastic은 모든 문제를 해결하기 위해 최선의 노력을 다할 것이지만, 기술 미리 보기의 기능은 공식 GA 기능의 지원 SLA가 적용되지 않습니다.

kNN 검색을 사용하면 이전에 배포된 텍스트 임베딩 모델을 사용하여 시맨틱 검색을 수행할 수 있습니다 . 검색어에 대한 리터럴 매칭 대신 시맨틱 검색은 검색 쿼리의 의도와 문맥적 의미를 기반으로 결과를 검색합니다.

후드 아래에서 NLP 모델을 포함하는 텍스트는 model_text사용자가 제공하는 입력 쿼리 문자열에서 조밀한 벡터를 생성합니다. 그런 다음 동일한 텍스트 임베딩 기계 학습 모델로 생성된 조밀한 벡터를 포함하는 인덱스에 대해 검색됩니다. 검색 결과는 모델에서 학습한 것과 의미론적으로 유사합니다.

시맨틱 검색을 수행하려면 다음을 수행하십시오.

검색할 입력 데이터의 조밀한 벡터 표현을 포함하는 인덱스가 필요합니다.
입력 데이터에서 조밀한 벡터를 만드는 데 사용한 것과 동일한 텍스트 임베딩 모델을 검색에 사용해야 합니다.
텍스트 포함 NLP 모델 배포를 시작해야 합니다.

개체 에서 배포된 텍스트 임베딩 모델을 참조 query_vector_builder하고 검색 쿼리를 다음과 같이 제공합니다 model_text.

(...)
{
  "knn": {
    "field": "dense-vector-field",
    "k": 10,
    "num_candidates": 100,
    "query_vector_builder": {
      "text_embedding": { 
        "model_id": "my-text-embedding-model", 
        "model_text": "The opposite of blue" 
      }
    }
  }
}
(...)

	수행할 자연어 처리 작업입니다. . text_embedding_
	쿼리 문자열에서 고밀도 벡터를 생성하는 데 사용할 텍스트 임베딩 모델의 ID입니다. 검색하는 인덱스의 입력 텍스트에서 임베딩을 생성한 동일한 모델을 사용합니다.
	모델이 조밀한 벡터 표현을 생성하는 쿼리 문자열입니다.

학습된 모델을 배포하고 이를 사용하여 텍스트 임베딩을 만드는 방법에 대한 자세한 내용은 이 종단 간 예 를 참조하십시오 .

여러 kNN 필드 검색

하이브리드 검색 외에도 한 번에 둘 이상의 kNN 벡터 필드를 검색할 수 있습니다.

POST image-index/_search
{
  "query": {
    "match": {
      "title": {
        "query": "mountain lake",
        "boost": 0.9
      }
    }
  },
  "knn": [ {
    "field": "image-vector",
    "query_vector": [54, 10, -2],
    "k": 5,
    "num_candidates": 50,
    "boost": 0.1
  },
  {
    "field": "title-vector",
    "query_vector": [1, 20, -52, 23, 10],
    "k": 10,
    "num_candidates": 10,
    "boost": 0.5
  }],
  "size": 10
}

이 검색은 에 대한 전역 상위 k = 5벡터 일치 및 에 대한 image-vector전역을 찾습니다 . 그런 다음 이러한 상위 값이 쿼리의 일치 항목과 결합되고 상위 10개 문서가 반환됩니다. 여러 항목과 일치 항목은 마치 부울을 사용하는 것처럼 분리를 통해 결합 됩니다 . 상위 벡터 결과는 모든 인덱스 샤드에서 전역 최근접 이웃을 나타냅니다.k = 10 title-vector match knn query k

위의 부스트가 구성된 문서의 점수는 다음과 같습니다.

점수 = 0.9 * match_score + 0.1 * knn_score_image-벡터 + 0.5 * knn_score_title-벡터

유사성이 예상되는 kNN 검색편집하다

kNN은 강력한 도구이지만 항상 k가장 가까운 이웃을 반환하려고 시도합니다. knn따라서 with a 를 사용하면 filter모든 관련 문서를 필터링하고 관련 없는 문서만 검색할 수 있습니다. 이 상황에서 이웃이 벡터 공간에서 멀리 떨어져 있을 수 있더라도 가장 가까운 이웃을 knn반환하기 위해 최선을 다할 것입니다 .k

similarity이러한 걱정을 덜기 위해 절 에서 사용할 수 있는 매개변수가 있습니다 knn. 이 값은 벡터가 일치하는 것으로 간주되는 데 필요한 최소 유사성입니다. 이 매개변수를 사용한 검색 knn흐름은 다음과 같습니다.

사용자 제공 filter쿼리 적용
벡터 공간을 탐색하여 k벡터를 얻습니다.
구성된 것보다 더 멀리 있는 벡터를 반환하지 마십시오.similarity

다음은 예입니다. query_vector이 예에서는 가장 가까운 이웃 에 대해 주어진 것을 검색합니다 k. 그러나 filter발견된 벡터가 적어도 similarity그들 사이에 제공되는 것을 적용하고 요구합니다.

POST image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [1, 5, -20],
    "k": 5,
    "num_candidates": 50,
    "similarity": 36,
    "filter": {
      "term": {
        "file-type": "png"
      }
    }
  },
  "fields": ["title"],
  "_source": false
}

데이터 세트에서 파일 유형이 인 유일한 문서에는 png벡터가 있습니다 [42, 8, -15]. 와 l2_norm사이의 거리는 이며 의 구성된 유사성보다 큽니다 . 즉, 이 검색은 적중을 반환하지 않습니다.[42, 8, -15][1, 5, -20]41.41236

인덱싱 고려 사항

대략적인 kNN 검색을 위해 Elasticsearch는 각 세그먼트의 밀집 벡터 값을 HNSW 그래프 로 저장합니다 . 대략적인 kNN 검색을 위한 인덱싱 벡터는 이러한 그래프를 구축하는 데 비용이 많이 들기 때문에 상당한 시간이 걸릴 수 있습니다. 인덱스 및 대량 요청에 대한 클라이언트 요청 제한 시간을 늘려야 할 수 있습니다. 대략 적인 kNN 튜닝 가이드에는 인덱싱 성능에 대한 중요한 지침과 인덱스 구성이 검색 성능에 미치는 영향이 포함되어 있습니다.

검색 시간 조정 매개변수 외에도 HNSW 알고리즘에는 그래프 작성 비용, 검색 속도 및 정확도 간에 절충되는 인덱스 시간 매개변수가 있습니다. 매핑 을 설정할 때 인수를 사용하여 다음 매개변수를 조정할 dense_vector수 있습니다 .index_options

PUT image-index
{
  "mappings": {
    "properties": {
      "image-vector": {
        "type": "dense_vector",
        "dims": 3,
        "index": true,
        "similarity": "l2_norm",
        "index_options": {
          "type": "hnsw",
          "m": 32,
          "ef_construction": 100
        }
      }
    }
  }
}

대략적인 kNN 검색의 제한 사항

nested 매핑 필드에서는 dense_vector 필드 에서 kNN 검색을 실행할 수 없습니다.
클러스터 간 검색 에서 kNN 검색을 사용하는 경우 옵션 ccs_minimize_roundtrips 이 지원되지 않습니다.
Elasticsearch는 HNSW 알고리즘을 사용하여 효율적인 kNN 검색을 지원합니다. 대부분의 kNN 알고리즘과 마찬가지로 HNSW는 검색 속도 향상을 위해 결과 정확도를 희생하는 근사 방법입니다. 이것은 반환된 결과가 항상 진정한 k개의 가장 가까운 이웃이 아니라는 것을 의미합니다.

dfs_query_then_fetch 대략적인 kNN 검색은 샤드 전체에서 전역 상위 일치 항목을 수집하기 위해 항상 검색 유형을 사용합니다 k. search_typekNN 검색을 실행할 때 명시적으로 설정할 수 없습니다 .

knn (필수) - 실행시킬 knn 쿼리

field (필수) - 검색할 필드 이름 반드시 dense_vector 타입으로 색인되어야 함.

query_vector (필수, float 타입의 배열 ) - 검색하려는 쿼리의 백터와 색인된 필드의 백터의 차원수가 동일 해야 함

k (필수, integer) - 상위 적중 항목으로 반환할 최근접 이웃의 수. 이 값은 num_candidates보다 작아야 함

num_candidates (필수, integer) -

샤드당 고려할 가장 가까운 이웃 후보의 수입니다. 10,000을 초과할 수 없습니다. Elasticsearch는 각 샤드에서 num_candidates개의 결과를 수집한 다음 이를 병합하여 상위 k개 결과를 찾습니다. num_candidates를 늘리면 최종 k개 결과의 정확도가 향상되는 경향이 있습니다.

728x90

아빠는 개발자

[search]k-nearest neighor (kNN) search 본문

[search]k-nearest neighor (kNN) search

k-nearest neighor (kNN) search

전제 조건

kNN 방법

정확한 kNN

대략적인 kNN

속도 또는 정확도를 위해 대략적인 kNN 조정

바이트 벡터를 사용한 대략적인 kNN

필터링된 kNN 검색

대략적인 kNN을 다른 기능과 결합편집하다

시맨틱 검색 수행

여러 kNN 필드 검색

유사성이 예상되는 kNN 검색편집하다

인덱싱 고려 사항

대략적인 kNN 검색의 제한 사항

티스토리툴바