Меню
Публикации
2025
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
doi: 10.17586/2226-1494-2025-25-2-339-344
УДК 004.021
Векторный поиск методом кластеризации с помощью ансамбля небрежных решающих деревьев
Читать статью полностью

Язык статьи - английский
Ссылка для цитирования:
Аннотация
Ссылка для цитирования:
Томилов Н.А., Туров В.П., Бабаянц А.А., Платонов А.В. Векторный поиск методом кластеризации с помощью ансамбля небрежных решающих деревьев // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 2. С. 339–344 (на англ. яз.). doi: 10.17586/2226-1494-2025-25-2-339-344
Аннотация
Введение. Информационный поиск с использованием алгоритмов машинного обучения основывается на преобразовании исходных мультимодальных документов в векторные представления, далее строится индекс векторных представлений и производится поиск внутри индекса. Популярным способом построения индекса является кластеризация векторных представлений, например с помощью 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