k-NN расшифровывается как k-nearest neighbors и используется для поиска близких документов на основе размерности вектора.
Эта стратегия широко используется для рекомендаций. На основе многих параметров (размерности вектора) пользователи классифицируются и группируются, затем, когда появляется новый пользователь, вы можете использовать k-NN для сравнения его векторов с остальными пользователями и дать соответствующие рекомендации.
Еще один интересный вариант использования - "встраивание слов", или преобразование слов в векторы. В этом сценарии вы хотите искать слово "кошка" и находить такие вещи, как "товары для животных", "песок для кошек" и "усы", а не "автомобиль" или "катапульта".
Чтобы добиться этого, модель обучается присваивать векторы каждому слову на основе контекста. Затем, используя k-NN, мы можем узнать, что "кот" и "зоотовары" являются соседями, несмотря на то, что это совершенно разные слова.
Плагин k-NN Opensearch
Opensearch приходит на помощь с плагином, который обрабатывает этот поиск по расстоянию. Единственное, что вам нужно сделать, это загрузить документы с их векторами в качестве типа поля k-NN.
Установка
Версия Opensearch с полной установкой включает в себя плагин, поэтому вам не нужно его устанавливать.
Если вы не уверены, вы можете проверить свои плагины и поискать opensearch-knn:
| 1 | sudo bin/opensearch-plugin list |
Если вы не видите opensearch-knn в списке, вы можете легко установить его:
| 1 | sudo bin/opensearch-plugin install opensearch-knn |
Использование
Плагин k-NN поддерживает 3 метода получения соседей. Ниже приведено краткое описание этих методов. Если вы хотите получить более подробное объяснение, обратитесь к официальной документации.
| Название | Метод | Особенности | Пример использования |
| Приблизительный k-NN | Алгоритм HNSW (Hierarchical Navigable Small World) | Низкая задержка, масштабируемость | Большие индексы (много векторов), без предварительных фильтров |
| Сценарная оценка k-NN | Грубая сила | Поддержка двоичного представления полей | Меньшие тела или предварительная фильтрация |
| Безболезненные расширения | Пользовательский | Поддержка функций расстояния | Более сложные сценарии |
Вы должны использовать Approximate k-NN для больших индексов без предварительной фильтрации запросов, Script Score для небольших индексов/предварительно отфильтрованных запросов, и Painless extensions в случае, если вам нужно использовать пользовательскую функцию расстояния для вычисления баллов.
k-NN маппинг
Плагин представляет новый тип поля под названием "knn_vector", который имеет множество опций настройки, с которыми вы можете ознакомиться здесь.
Тип поля knn_vector выглядит следующим образом:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | { "my_vector_field": { "type": "knn_vector", "dimension": 4, "method": { "name": "hnsw", "space_type": "l2", "engine": "nmslib", "parameters": { "ef_construction": 128, "m": 24 } } } } |
Наиболее важные свойства:
- dimension: Количество размеров, которые будет иметь ваш вектор.
- space_type: Пространственная функция, которая будет использоваться для вычисления расстояния между векторами. Доступные варианты.
- ef_construction: Размер динамического списка, используемого для k-NN. Чем больше значение, тем выше точность, но ниже скорость индексации.
- m: Количество двунаправленных ссылок, которые будет создавать плагин. Влияет на использование памяти, держите значение между 2 и 100.
Приближенный k-NN
Создание k-nn индекса
Давайте создадим несколько документов для поиска по ним с помощью метода приближенного k-NN. Мы будем использовать пример Word Embedding. Значения векторного массива должны быть сгенерированы с помощью библиотеки встраивания слов, в данном примере они придуманы.
| 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 | PUT test-knn { "settings": { "index": { "knn": true, "knn.algo_param.ef_search": 100 } }, "mappings": { "properties": { "product_vector": { "type": "knn_vector", "dimension": 4, "method": { "name": "hnsw", "space_type": "l2", "engine": "nmslib", "parameters": { "ef_construction": 128, "m": 24 } } } } } } |
Теперь давайте загрузим несколько примеров документов.
| 1 2 3 4 5 6 7 8 9 | POST _bulk { "index": { "_index": "test-knn", "_id": "1" } } { "product_vector": [1, 5, 5, 4], "price": 10.00,"name": "Hygienic sand" } { "index": { "_index": "test-knn", "_id": "2" } } { "product_vector": [5, 4, 4, 4], "price": 25.00,"name": "Pet supplies pack" } { "index": { "_index": "test-knn", "_id": "3" } } { "product_vector": [7, 9, 9, 9], "price": 500,"name": "Catapult" } { "index": { "_index": "test-knn", "_id": "4" } } { "product_vector": [1, 1, 2, 1], "price": 5,"name": "Hot Wheels Car" } |
Каждый элемент векторного массива - это измерение, которое представляет собой характеристику документа. Алгоритмы машинного обучения могут вычислять тысячи различных измерений. Свойство dimension в отображениях поддерживает до 10 000.
Запрос
Допустим, векторное представление для "кошки" после обучения нашей модели составляет: [2,3,5,6].
| 1 2 3 4 5 6 7 8 9 10 11 12 | GET test-knn/_search { "size": 2, "query": { "knn": { "product_vector": { "vector": [2, 3, 5, 6], "k": 2 } } } } |
- size: Количество возвращаемых результатов.
- k: Количество соседей для каждого графа.
- vector (вектор): Векторное представление искомого документа.
Ответ может выглядеть следующим образом:
| 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | { "took" : 2, "timed_out" : false, "_shards" : { "total" : 1, "successful" : 1, "skipped" : 0, "failed" : 0 }, "hits" : { "total" : { "value" : 2, "relation" : "eq" }, "max_score" : 0.1, "hits" : [ { "_index" : "test-knn", "_type" : "_doc", "_id" : "1", "_score" : 0.1, "_source" : { "product_vector" : [ 1, 5, 5, 4 ], "price" : 10.0, "name" : "Hygienic sand" } }, { "_index" : "test-knn", "_type" : "_doc", "_id" : "2", "_score" : 0.0625, "_source" : { "product_vector" : [ 5, 4, 4, 4 ], "price" : 25.0, "name" : "Pet supplies pack" } } ] } } |
Посмотрите, как Catapult и car не возвращаются, а Pet Supply и Sand возвращаются (или релевантны/более релевантны).
Интересно то, что критерии, используемые для определения расстояния между k элементами, могут быть разными. Модели вкрапления слов обучаются на тоннах текста, например книгах или газетах, но измерения могут быть такими, как предпочтения категорий фильмов, рейтинги, возраст людей, город, продолжительность фильма и т. д.
Использование с фильтрами
Как мы уже говорили, Approximate k-NN не может быть предварительно отфильтрован, поэтому, если, например, мы хотим отфильтровать товары по цене после выполнения k-NN, мы можем использовать условие post_filter.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | GET test-knn/_search { "size": 2, "query": { "knn": { "product_vector": { "vector": [2, 3, 5, 6], "k": 2 } } }, "post_filter": { "range": { "price": { "lte": 20 } } } } |
При таком запросе пакет "Зоотовары" не будет возвращен из-за его цены.
| 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 32 33 34 35 | { "took" : 1, "timed_out" : false, "_shards" : { "total" : 1, "successful" : 1, "skipped" : 0, "failed" : 0 }, "hits" : { "total" : { "value" : 1, "relation" : "eq" }, "max_score" : 0.1, "hits" : [ { "_index" : "test-knn", "_type" : "_doc", "_id" : "1", "_score" : 0.1, "_source" : { "product_vector" : [ 1, 5, 5, 4 ], "price" : 10.0, "name" : "Hygienic sand" } } ] } } |
Сценарий скоринга k-NN
С помощью этого подхода мы можем применить фильтр перед выполнением поиска ближайших соседей. По этой причине он не очень хорошо масштабируется, но полезен для случаев динамического поиска, когда тело индекса может меняться в зависимости от других условий.
Маппинг
| 1 2 3 4 5 6 7 8 9 10 11 | PUT my-knn-index-1 { "mappings": { "properties": { "product_vector": { "type": "knn_vector", "dimension": 4 } } } } |
Как видите, это более короткая версия приближенного поиска, поскольку многие параметры конфигурации относятся исключительно к этому подходу.
Если вы хотите использовать этот индекс как для сценарного, так и для аппроксимационного поиска, вам нужно установить knn.index: true и задать knn.space_type.
Если вы хотите использовать только возможности скриптовых оценок, рекомендуется установить knn.index: false. Вы выиграете от меньшего использования памяти и более быстрого индексирования, но не сможете выполнять стандартные kNN-запросы к индексу.
Запрос
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | GET my-knn-index-1/_search { "size": 4, "query": { "script_score": { "query": { "match_all": {} }, "script": { "source": "knn_score", "lang": "knn", "params": { "field": "product_vector", "query_value": [2.0, 3.0, 5.0, 6.0], "space_type": "cosinesimil" } } } } } |
Все параметры являются обязательными.
Наиболее важными являются:
- lang: knn вместо painless.
- source: имя скрипта.
- query_value: Точка, для которой необходимо найти соседей, представленная в виде массива плавающих значений, которые должны совпадать с размерами маппинга.
- space_type: Функция, используемая для вычисления расстояния между точками.
Бинарные данные в скрипте Score
Скрипт k-NN Score также поддерживает запрос query_value не в виде массива, а в двоичном виде. В этом случае необходимо использовать пространство расстояний Хэмминга и прикрепить строку в виде данных base64. Вы также можете представить это значение в виде типа long.
Создание индекса
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | PUT my-index { "mappings": { "properties": { "my_binary": { "type": "binary", "doc_values": true }, "color": { "type": "keyword" } } } } |
Индексирование документов
| 1 2 3 4 5 | POST _bulk { "index": { "_index": "my-index", "_id": "1" } } { "my_binary": "SGVsbG8gV29ybGQh", "color" : "RED" } { "index": { "_index": "my-index", "_id": "2" } } { "my_binary": "ay1OTiBjdXN0b20gc2NvcmluZyE=", "color" : "RED" } |
Выполните запрос
| 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 | GET my-index/_search { "size": 2, "query": { "script_score": { "query": { "bool": { "filter": { "term": { "color": "RED" } } } }, "script": { "lang": "knn", "source": "knn_score", "params": { "field": "my_binary", "query_value": "U29tZXRoaW5nIEltIGxvb2tpbmcgZm9y", "space_type": "hammingbit" } } } } } |
Обратите внимание, что вы ищете соседей только красного цвета (RED), поэтому любой другой цвет будет проигнорирован.
Скрипт Painless Script
Этот метод позволяет манипулировать значениями функции расстояния и баллом. Вы можете выбирать из списка доступных функций и, например, умножать значение оценки или вовлекать в уравнение другие поля документа. Все функции получают в качестве параметров имя поля и значение вектора.
Смотрите пример ниже.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | GET my-knn-index-1/_search { "query": { "script_score": { "query": { "match_all": {} }, "script": { "source": "1.0 + cosineSimilarity(params.query_value, doc[params.field])", "params": { "field": "product_vector", "query_value": [ 7.9, 2.9, 4.9, 4.9 ] } } } } } |
Этот скрипт выполнит функцию косинусного сходства для подсчета баллов, а затем подставит 1.0 в итоговое значение.
Ограничения
- Вы можете выбирать между функциями расстояния l2Squared, l1Norm и cosineSimilarity (более подробная информация здесь).
- Размерность query_value должна совпадать с размером, определенным в маппинге, иначе запрос не будет выполнен.
- Если в документе отсутствует векторное значение, запрос будет выполнен неудачно. Это можно исправить, проверив это значение перед запуском функции расстояния с помощью этого кода: "source": "doc[params.field].size() == 0 ? 0 : 1 / (1 + l2Squared(params.query_value, doc[params.field]))".
- Баллы могут быть только положительными, поэтому документы с векторными полями будут иметь более высокие баллы.