Хотите изучить Flink и другие инструменты для работы с большими данными у ведущих специалистов по обработке данных из Кремниевой долины или Нью-Йорка? Программа Insight Data Engineering Fellows Programme - это бесплатное 7-недельное профессиональное обучение, на котором вы можете создавать передовые платформы больших данных и перейти к карьере инженера данных в таких ведущих командах, как Facebook, Uber, Slack и Squarespace.

Узнать больше о программе и подать заявку сегодня.

Этот пост является продолжением более ранней публикации о написании распределенных запросов k-ближайших соседей для библиотеки машинного обучения Apache Flink. В этом сообщении описывается приблизительный метод выполнения запроса k-ближайших соседей.

В более ранней публикации я описал работу, которую я первоначально выполнял как научный сотрудник Insight Data Engineering. Эта работа, теперь объединенная с основной веткой Flink, заключалась в выполнении эффективного запроса точных k-ближайших соседей (KNN) с использованием квадродеревьев. С тех пор я работал над приблизительной версией алгоритма KNN, и я расскажу об одном методе, который я использовал для приблизительной версии с использованием хеширования на основе Z-значения.

Для больших и многомерных наборов данных точный запрос k-ближайших соседей может стать невозможным. Существует множество алгоритмов, которые уменьшают размерность точек, хешируя их до более низких размеров. Один из распространенных подходов - LSH (хеширование с учетом местоположения). Этот метод более известен - например, см. здесь - и остановлюсь на другом методе.

Более эффективный подход к хешированию для измерений от низкого до среднего - использование Z-значений. Для размеров меньше 32 он обычно превосходит методы на основе LSH, и в этом посте мы сосредоточимся на подходе на основе Z-значения. Используя z-значения, было обнаружено увеличение производительности более чем на порядок при умеренных размерах по сравнению с точными методами.

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

Даже для малых размерностей точный поиск k-ближайших соседей часто может быть довольно сложным и неэффективным. Геопространственные древовидные структуры, такие как Quadtrees, KD-Trees или R-Trees, часто используются для уменьшения сложности путем индексации обучающего набора. Однако во всех случаях существует проблема, заключающаяся в том, что ближайшие соседи контрольной точки могут находиться в минимальном ограничивающем прямоугольнике.

Например, на рисунке ниже обучающий набор состоит из синих точек, индексированных зелеными прямоугольниками, а ближайшие соседи контрольной точки (золотая звезда) не являются двумя тренировочными точками в прямоугольнике, в котором находится контрольная точка.

Чтобы обойти это, мы сначала находим k «соседних» точек, используя метод, описанный в моем предыдущем посте - детали которого не важны для этого поста - и эти k близлежащих точек позволяют определить радиус, по которому будет выполняться поиск по всем соседним прямоугольникам. до контрольной точки.

В этом круге может быть много тренировочных точек (например, миллионы), и нужно будет вычислить все расстояния от всех точек в этом круге до тестовой точки, что увеличивает время выполнения. Та же проблема возникает при использовании Quadtree, K-D Tree или R-Tree, и в идеале нам нужен метод, который хорошо работает независимо от пространственного распределения точек.

Аналогичная идея поиска k ближайших точек и их использования для фильтрации обучающей выборки описана на стр. 5 этой статьи. Ключевой вывод заключается в том, что любой известный мне подход для выполнения точных запросов KNN требует больших вычислительных ресурсов для конкретных пространственных распределений точек обучения.

Z-значения и k-ближайшие соседи

Если мы хэшируем точки до одномерного и разрешаем приблизительный запрос KNN, запрос можно будет выполнить более эффективно. С хорошей одномерной функцией хеширования поиск KNN становится простым: хешируется обучающий набор и сортируется одномерное представление обучающего набора. Затем для каждой тестовой точки выполняется хеширование тестовой точки и поиск ближайших соседей одномерного представления точек выполняется с помощью двоичного поиска.

Как выбрать хорошую хеш-функцию? Одним из ключевых свойств для получения хорошей точности является то, что хеш-функция должна сопоставлять близлежащие точки с соседними точками, чтобы гарантировать, что поиск ближайшего соседа, выполняемый в более низких измерениях, соответствует поиску k- «ближайших» соседей в исходном измерении.

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

Z-значение точки получается путем чередования двоичных цифр ее координат. Например, Z-значение (2,5) равно 13, как показано на рисунке ниже.

Естественно, мы хотели бы, чтобы алгоритм применялся не только к целочисленным значениям, и в этом случае вам может быть интересно: как вычислить Z-значение, например, (0,12525, 0,7819)? Однозначно брать слово - не лучший подход, поскольку, если все точки лежат в единичном кубе, все точки хешируются в одно и то же ведро.

Однако нам все еще нужно взять слово, чтобы получить не слишком большое двоичное представление после объединения двоичных строк каждой координаты. Чтобы контролировать и максимизировать количество битов, присутствующих после перекрытия точек, мы нормализуем точки, чтобы они лежали в единичном кубе, и вычисляем Z-значение минимального уровня точек, масштабированных на 2 ^ n. Степень n выбирается настолько большой, насколько это возможно, чтобы битовая строка имела как можно ближе к 32 битам, то есть, поскольку мы объединяем битовые строки каждой координаты, естественным выбором будет позволить n = floor (32 / dim) биты из каждого измерения.

Псевдокод алгоритма

Из псевдокода видно, что алгоритм имеет сложность O (NTest ln (NTrain) + NTrain ln (NTrain)) - вычисляются Z-значения обучающего набора и сортируются, отсюда термин NTrain ln (NTrain), а затем для каждой тестовой точки выполняет двоичный поиск по Z-значениям обучающего набора, чтобы найти k ближайших точек.

Что касается распределения алгоритма, я использовал ту же структуру MapReduce, что и для квадродеревьев, и метод грубой силы, описанный в моем предыдущем посте, а именно разделил обучающий и тестовый набор на блоки, взял кросс-продукт, выполнил локальные запросы KNN и объединил результаты. , который представлен на диаграмме MapReduce.

Код Scala для локального поиска knn выглядит следующим образом

Представление

Производительность методов на основе точных деревьев зависит от пространственного распределения точек, что отрицательно сказывается на производительности, что не относится к методу, основанному на приближенном Z-значении. Метод Z-значения особенно хорошо работает в измерениях от низкого до среднего, и на самом деле его не следует применять к более высоким измерениям, поскольку он включает формирование битовой строки из каждой координаты - если кто-то хочет, чтобы Z-значение было типа Int, и использование каждой координаты, то нельзя использовать Z-значения для размеров выше 32, не прибегая к использованию таких типов, как BigInt.

На следующей диаграмме показана разница в производительности при использовании подхода Z-значения по сравнению с вычислением KNN для измерения 6. Точный метод либо использует метод грубой силы, либо использует дерево квадратов и делает предположение, что лучше подходит - деревья квадратов хорошо масштабируются с количество точек, но плохо с размерностью.

Резюме

Точные запросы KNN часто выполняются с использованием геопространственных древовидных структур данных для индексации точек. Хотя это имеет тенденцию к повышению производительности в малых размерностях по сравнению с точными методами грубой силы, это все же может быть довольно затратным с точки зрения вычислений, а эффективность может зависеть от пространственного распределения точек.

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

Заинтересованы в том, чтобы сделать карьеру в области инженерии данных? Узнайте больше о программе Insight Data Engineering Fellows Program в Нью-Йорке и Кремниевой долине, подайте заявку сегодня или подпишитесь на обновления программы.