Векторный поиск методом кластеризации с помощью ансамбля небрежных решающих деревьев

Введение. Информационный поиск с использованием алгоритмов машинного обучения основывается на преобразовании исходных мультимодальных документов в векторные представления, далее строится индекс векторных представлений и производится поиск внутри индекса. Популярным способом построения индекса является кластеризация векторных представлений, например с помощью k-ближайших соседей. В работе предложен метод кластеризации с помощью ансамбля небрежных решающих деревьев, а также алгоритм векторного поиска на основе этого метода. Разработанный метод кластеризации является детерминированным и предоставляет возможность сериализации параметров ансамбля.

Метод. Сущность метода состоит в обучении ансамбля двоичных или троичных небрежных решающих деревьев. Этот ансамбль используется для вычисления хэша для каждого из исходных векторных представлений. Векторные представления, имеющие одинаковый хэш, считаются принадлежащими к одному кластеру. Для поиска выбирается несколько кластеров, центроиды которых наиболее приближены к векторному представлению поискового запроса, после чего производится полный перебор векторных представлений выбранных кластеров. Основные результаты. Представленный метод показывает качество поиска, сравнимое с широко используемыми в индустрии библиотеками векторного поиска Faiss, Annoy и HNSWlib. Для протестированного набора данных с евклидовой метрикой расстояния предложенный метод поиска медленнее, чем существующие решения, но для протестированного набора данных с угловой метрикой расстояния результат сравним или лучше.

Обсуждение. Разработанный метод может быть применен для улучшения качества поиска при создании мультимодальных поисковых систем. Возможность сериализации позволяет кластеризовать данные на одном вычислительном узле и передавать параметры ансамбля на другой вычислительный узел, что дает возможность использовать предложенный алгоритм в распределенных системах.

1. Grbovic M., Cheng H. Real-time personalization using embeddings for search ranking at airbnb // Proc. of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018. P. 311–320. https://doi.org/10.1145/3219819.3219885

2. Berry M.W., Drmac Z., Jessup E.R. Matrices, vector spaces, and information retrieval //sIAM Review. 1999. V. 41. N 2. P. 335–362. https://doi.org/10.1137/S0036144598347035

3. Korn F., Sidiropoulos N., Faloutsos C., Siegel E., Protopapas Z Fast nearest neighbor search in medical image databases // Proc. of the 22th International Conference on Very Large Data Bases (VLDB ‘96). 1996. P. 215–226. https://doi.org/10.5555/645922.673493

4. Seidl T., Kriegel H.-P. Optimal multi-step k-nearest neighbor search // ACM SIGMOD Record. 1998. V. 27. N 2. P. 154–165. https://doi.org/10.1145/276305.276319

5. Lou Y., Obukhov M. BDT: Gradient Boosted Decision Tables for high accuracy and scoring efficiency // Proc. of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ‘17). 2017. P. 1893–1901. https://doi.org/10.1145/3097983.3098175

6. Chakrabarti S. Efficient image retrieval using multi neural hash codes and bloom filters // Proc. of the IEEE International Conference for Innovation in Technology (INOCON). 2020. P. 1–6. https://doi.org/10.1109/INOCON50539.2020.9298228

7. Rokach L., Maimon O. Data Mining with Decision Trees: Theory and Applications / 2nd ed. World Scientific Publishing, 2014. 328 p.

8. Fumero J., Papadimitriou M., Zakkak F.S., Xekalaki M., Clarkson J., Kotselidis C. Dynamic application reconfiguration on heterogeneous hardware // Proc. of the 15th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments. 2019. P. 165–178. https://doi.org/10.1145/3313808.3313819

9. Xiao H., Rasul K., Vollgraf R. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms // arXiv. 2017. arXiv:1708.07747. https://doi.org/10.48550/arXiv.1708.07747

10. Aumüller M., Bernhardsson E., Faithfull A. Ann-benchmarks: A benchmarking tool for approximate nearest neighbor algorithms // Lecture Notes in Computer Science. 2017. V. 10609. P. 34–49. https://doi.org/10.1007/978-3-319-68474-1_3

11. Томилов Н.А., Туров В.П., Бабаянц А.А., Платонов А.В. Метод хранения векторных представлений в сжатом виде с применением кластеризации // Научно-технический вестник информационных технологий, механики и оптики. 2024. Т. 24, № 1. С. 112–117. https://doi.org/10.17586/2226-1494-2024-24-1-112-117

12. Douze M., Guzhva A., Deng C., Johnson J., Szilvasy G., Mazaré P.-E., Lomeli M., Hosseini L., Jégou H. The Faiss library // arXiv. 2024. arXiv.2401.08281. https://doi.org/10.48550/arXiv.2401.08281

13. Malkov Y., Yashunin D. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2020. V. 42. N 4. P. 824–836. https://doi.org/10.1109/TPAMI.2018.2889473

14. Туров В.П., Томилов Н.А., Бабаянц А.А. Разработка инструмента сравнения алгоритмов векторного поиска // XI Конгресс молодых учёных: Cборник научных трудов. СПб.: Национальный исследовательский университет ИТМО, 2022. Т. 1. С. 446–450.

15. Laaber C., Leitner P. An evaluation of open-source software microbenchmark suites for continuous performance assessment // Proc. of the 15th International Conference on Mining Software Repositories (MSR ‘18). 2018. P. 119–130. https://doi.org/10.1145/3196398.3196407