Экспериментальное исследование эффективности алгоритмов поиска ближайших соседей в метрических пространствах при кластеризации объектов

С развитием технологий и экспоненциальным ростом объёмов данных возникает острая проблема кластеризации информации. Ряд алгоритмов кластеризации использует принцип поиска ближайшего соседа, чтобы определить принадлежность элемента к какому-либо кластеру. В работе рассматриваются эффективные по времени алгоритмы поиска ближайших соседей в различных метрических пространствах, их влияние на качество и время кластеризации, а также представлены экспериментальные результаты сравнительного анализа. Исследование проводилось с использованием алгоритма иерархической агломеративной кластеризации, который использует для поиска ближайших соседей алгоритмы, основанные на деревьях и хешировании, совместно с метрическими пространствами Евклида, Кларка, Лоренца и размера Пенроуза. Для экспериментов используется два вида входных данных: сгенерированных случайным образом (обобщенные характеристики временных рядов) и взятых из реальной жизни (показания электромиографа). Работа содержит 57 страниц, 4 главы, 33 рисунка, 4 таблицы, 49 источников, 2 приложения. Ключевые слова: кластеризация, иерархическая кластеризация, поиск ближайших соседей, kd дерево, vp дерево, locality-sensitive hashing, best bin first.