Применение суффиксных кодов в модульной метрике для решения задачи кластеризации и задачи поиска k-соседей
https://doi.org/10.15514/ISPRAS-2025-37(5)-2
Аннотация
Данная работа посвящена применению суффиксных кодов в модульной метрике для решения задач кластеризации и поиска ближайших соседей (k-nearest neighbors, kNN). Рассматриваются преимущества использования модульной метрики перед евклидовой метрикой, особенно в пространствах высокой размерности. Основной акцент сделан на разработку эффективных алгоритмов кластеризации и поиска ближайших соседей с использованием кодов, позволяющих исправить ошибки в модульной метрике. Предложенный подход обеспечивает полиномиальную сложность относительно размерности обучающей выборки, что делает его перспективным для приложений машинного обучения с большими наборами данных и высокими требованиями к производительности.
При поддержке: Статья подготовлена в ходе проведения исследования в рамках Программы фундаментальных исследований Национального исследовательского университета «Высшая школа экономики» (НИУ ВШЭ).
Об авторах
Александр Рауилович ШАРАПОВ
Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Является аспирантом московского института электроники и математики им. А.Н. Тихонова, департамент электронной инженерии. Темой исследования является «Разработка метода анализа данных с использованием кодов, исправляющих ошибки в метрике l1». Сфера научных интересов: статистика, анализ данных, кодирование информации, сети и телекоммуникации.
Вячеслав Анатольевич ДАВЫДОВ
Национальный исследовательский университет «Высшая школа экономики»
Россия
Россия
Кандидат технических и экономических наук. Он является приглашенным преподавателем московского института электроники и математики им. А.Н. Тихонова, кафедра информационной безопасности киберфизических систем. Сфера научных интересов: алгебраическая и комбинаторная теория кодирования, теория активных систем, технология блокчейн.
Список литературы
1. В. А. Давыдов. Использование кодов в модульной метрике для решения задачи KNN. (в публикации).
2. В. А. Давыдов. Коды, исправляющие ошибки в модульной метрике, метрике Ли и ошибки оператора // Пробл. передачи информ. 1993. Глава 29:3. С. 209–217
3. V. Davydov, N. Zeulin, I. Pastushok, A. Turlikov. Coding Scheme for High-Order QAM Modulations in the Manhattan Metric // IEEE Communications Letters. 2020. Vol. 24. N. 11. P. 2387–2391.
4. T. Cover, P. Hart. Nearest neighbor pattern classification // IEEE Transactions on Information Theory. 1967. Vol. 13. N. 1. P. 21–27.
5. Fix. E, Hodges, J.L. Discriminatory analysis. Nonparametric discrimination; consistency properties // USAF School of Aviation Medicine. 1951. Technical Report 4.
6. P. Indyk, R. Motwani. Approximate nearest neighbor: towards removing the curse of dimensionality // Proceedings of the Symposium on Theory of Computing. 1998.
7. E. Kushilevitz, R. Ostrovsky, Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces // Proceedings of the Thirtieth ACM Symposium on Theory of Computing. 1998. P. 614– 623.
8. J. Buhler, M. Tompa. Finding motifs using random projections // Proceedings of the Annual International Conference on Computational Molecular Biology. 2001.
9. J. Buhler. Provably sensitive indexing strategies for biosequence similarity search // Proceedings of the Annual International Conference on Computational Molecular Biology. 2002.
10. N. C. Jones, P. A. Pevzner. An Introduction to Bioinformatics Algorithms // The MIT Press Cambridge. 2004.
11. M. Namratha. IOSR Journal of Computer Engineering. 2012. Vol. 4(6). P 23–30.
12. A. V. Kumar, J. C. Selvaraj. Journal of Recent Research and Applied Studies. 2016. Vo_103.
13. M. Omran, A. Engelbrecht, A. A. Salman. Intelligent Data Analysis. 2007. Vol. 11(6). P. 583–605.
14. M. Wegmann, D. Zipperling, J. Hillenbrand, J. Fleischer. A review of systematic selection of clustering algorithms and their evaluation. 2021.
15. J. Gu. Journal of Physics: Conference Series. 2021. Vol. 1.
16. T. W. Liao. Pattern Recognition. 2005. Vol. 38(11). P. 1857–1874.
17. Τ. Gupta, S. Panda. International Journal of Engineering & Technology. 2018. Vol. 7(4). P. 4766–4768.
Рецензия
Для цитирования:
ШАРАПОВ А.Р., ДАВЫДОВ В.А. Применение суффиксных кодов в модульной метрике для решения задачи кластеризации и задачи поиска k-соседей. Труды Института системного программирования РАН. 2025;37(5):33-42. https://doi.org/10.15514/ISPRAS-2025-37(5)-2
For citation:
SHARAPOV A.R., DAVYDOV V.A. Application of Codes in Modular Metrics for Searching k-neighbors. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(5):33-42. (In Russ.) https://doi.org/10.15514/ISPRAS-2025-37(5)-2
Послать статью по эл. почте 