Во-первых, предварительно обработайте ваш список векторов, чтобы сделать каждый вектор нормализованным ... единичная величина.
Теперь обратите внимание, что ваша функция сравнения T () теперь имеет значения величин, которые становятся постоянными, и формулу можно упростить, чтобы найти наибольшее произведение точек между вашим тестовым вектором и значениями в базе данных.
Теперь подумайте о новой функции D = расстояние между двумя точками в 60D пространстве. Это классическое L2 расстояние , взять разность каждого компонента, возвести в квадрат каждый, сложить все квадраты и взять квадратный корень из суммы. D (A, B) = sqrt ((A-B) ^ 2) где A и B - каждый из 60 размерных векторов.
Это может быть расширено до D (A, B) = sqrt (A * A -2 * точка (A, B) + B * B).
А и В - единичная величина, то. И функция D является монотонной, поэтому она не изменит порядок сортировки, если мы удалим sqrt () и посмотрим на квадратные расстояния. Это оставляет нам только -2 * точка (A, B). Таким образом, расстояние минимизации точно эквивалентно максимизации точечного произведения.
Таким образом, исходную метрику классификации T () можно упростить, чтобы найти произведение высшей точки между нормированными векторами. И это сравнение показано эквивалентным нахождению ближайших точек к точке выборки в пространстве 60-D.
Так что теперь все, что вам нужно сделать, - это решить эквивалентную проблему «заданной нормализованной точки в пространстве 60D, перечислить 20 точек в базе данных нормализованных векторов выборок, которые находятся ближе всего к ней».
Эта проблема хорошо понятна .. это K Ближайшие соседи.
Есть много алгоритмов для решения этой проблемы. Наиболее распространенными являются классические KD деревья
.
Но есть проблема. Деревья KD имеют O (e ^ D) поведение. Высокая размерность быстро становится болезненной. И 60 измерений определенно в этой чрезвычайно болезненной категории. Даже не пытайтесь.
Однако существует несколько альтернативных общих методов для ближайшего соседа с высоким D.
Эта статья дает четкий метод.
Но на практике есть отличное решение, включающее еще одно преобразование. Если у вас есть метрическое пространство (что вы делаете, или вы не будете использовать сравнение Tanimoto), вы можете уменьшить размерность задачи на 60-мерное вращение. Это звучит сложно и страшно, но это очень часто ... это форма разложения по сингулярным значениям или разложения по собственным значениям. В статистике он известен как Анализ основных компонентов.
В основном это использует простое линейное вычисление, чтобы найти, в каких направлениях ваша база данных действительно охватывает. Вы можете свернуть 60 измерений до меньшего числа, возможно, до 3 или 4, и все же сможете точно определить ближайших соседей.
Существуют тонны программных библиотек для этого на любом языке, см., Например, здесь .
Наконец, вы сделаете классическое K ближайших соседей, вероятно, только в 3-10 измерениях ... вы можете экспериментировать для лучшего поведения. Для этого есть потрясающая библиотека под названием Ranger , но вы можете использовать и другие библиотеки. Большим дополнительным преимуществом является то, что вам даже больше не нужно хранить все 60 компонентов данных образца!
Возмущающий вопрос: действительно ли ваши данные могут быть свернуты в более низкие измерения, не влияя на точность результатов. На практике декомпозиция PCA может сообщить вам максимальную остаточную ошибку для любого выбранного вами предела D, так что вы можете быть уверены, что он работает. Поскольку точки сравнения основаны на метрике расстояния, весьма вероятно, что они сильно коррелируют, в отличие от значений, скажем, хеш-таблиц.
Итак, краткое изложение выше:
- Нормализуйте свои векторы, превратив вашу проблему в задачу K-ближайшего соседа в 60 измерениях
- Использование анализа основных компонентов для уменьшения размерности до приемлемого предела, скажем, 5 измерений
- Используйте алгоритм K Nearest Neighbor, например, библиотеку KD-дерева Ranger, чтобы найти соседние сэмплы.