Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
машинное обучение сегодняСтатья 15, В предыдущей статье говорилось о связанной оптимизации Kmeans, а также рассказывалось о знаменитом алгоритме EM. Некоторые друзья сказали, что им нравится смотреть на эти хардкоры, поэтому сегодня я закажу хардкоры Давайте посмотрим на структуру данных, часто используемую в области машинного обучения——KD-Tree.
От дерева сегментов к дереву KD
Прежде чем говорить о дереве KD, давайте посмотримдерево сегментовКонцепция чего-либо. Деревья отрезков не очень распространены в области машинного обучения, но как высокопроизводительная структура данных обслуживания они часто фигурируют в различных соревнованиях по алгоритмам. Суть дерева отрезков — это сбалансированное бинарное дерево, сохраняющее интервал.
Например, следующий рисунок представляет собой классическое дерево отрезков:
На рисунке ниже нетрудно увидеть, что это дерево отрезков поддерживаетмаксимальное значение в интервале. Например, если корень дерева равен 8, сохраняется максимальное значение всего интервала, а значение каждого промежуточного узла является максимальным значением всех элементов в поддереве с ним в качестве корня дерева.
Через дерево отрезков мы можем
время для расчета определенногоМаксимальное значение непрерывного интервала. Например, давайте посмотрим на следующий рисунок:
Когда мы запрашиваем максимальное значение в ограниченном интервале, нам просто нужноНайдите промежуточные узлы, которые могут покрыть этот интервалПросто сделай это. Мы можем обнаружить, что поддеревья двух узлов, обрамленные красной рамкой, как раз покрывают этот интервал, поэтому максимальное значение всего интервала является максимальным значением этих двух элементов. Таким образом, мы ставим потребность
Задача поиска сводится к
, мало того, мы также можемсделай это
Обновление в пределах сложности, что означает, что мы можем не только быстро запрашивать, но и обновлять элементы в сегменте линии.
Конечно, область применения деревьев отрезков очень обширна, и существуют такжемного вариантов, Мы не будем здесь слишком углубляться. Заинтересованные студенты могут с нетерпением ждать темы среды об алгоритмах и структурах данных и поделятся для вас соответствующим содержанием деревьев отрезков в следующих статьях. Здесь нам нужно только иметь общее представление о том, что делает дерево отрезков.
Дерево отрезков поддерживает линейный отрезок, то есть элементы в интервале, то есть поддерживает одномерную последовательность. Что, если мы расширим измерение данных до многомерного?
Да, вы угадали, в каком-то смысле мы можем думать о KD-Tree как о дереве сегментов.Расширение в многомерное пространствоситуация в нем.
Определение KD-дерева
Давайте посмотрим на конкретное определение KD-Tree, где K относится кK-мерное пространство, D, естественно, размерность, то есть размерность, то есть KD-Tree означает K-мерное дерево.
Когда мы строим дерево отрезков, это на самом деле рекурсивный процесс построения дерева.Мы каждый раз делим текущий отрезок на два, а затем используем данные, разделенные на две половины, для построения левого и правого поддеревьев соответственно. Мы можем просто написать псевдокод, чтобы получить более интуитивное представление:
class Node:
def __init__(self, value, lchild, rchild):
self.value = value
self.lchild = lchild
self.rchild = rchild
def build(arr):
n = len(arr):
left, right = arr[: n//2], arr[n//2:]
lchild, rchild = self.build(left), self.build(right)
return Node(max(lchild.value, rchild.value), lchild, rchild)
Давайте рассмотрим двумерный пример, где несколько точек распределены в двумерной плоскости.
Сначала мы выбираем размерРазделите данные на два, например, мы выбираем ось x. Мы сортируем все данные в соответствии со значением оси x и выбираем среднюю точку, чтобы разделить ее на две части.
Точки слева и справа от прямой разбиваются на два поддерева, для данных этих двух частейизменить размер, то есть выберите ось Y для деления. Опять же, сначала сортируем, потом находим среднюю точку, а потом снова делим на два. Мы можем получить:
мыПовторите описанный выше процесс, и делим точки до тех пор, пока их нельзя разделить.Чтобы было лучше видно, мы помечаем все данные координатами (неточно).
Если мы думаем о пространстве как об обобщенном интервале, то оно работает так же, как дерево отрезков. Наконец-то получилидеальное бинарное дерево, поскольку мы выбираем среднюю точку набора данных для деления каждый раз, мы можем гарантировать, что длина от корня до конечного узла не будет превышать
.
После того, как мы подставим вышеуказанные координаты, KD-дерево, которое мы в итоге получим, вероятно, будет следующим:
Строительство KD-дерева
В процессе построения дерева каждый раз, когда глубина нашего дерева расширяется на один уровень вниз, мы меняем измерение в качестве эталона измерения. Причина также очень проста, потому что мы надеемся, что это дерево обладает хорошей выразительной способностью для этого K-мерного пространства, так что мы можем быстро выполнять запросы по различным измерениям.
В некоторых реализациях мы вычисляем дисперсию каждого измерения, а затем выбираем измерение с большей дисперсией для разделения. Это естественно, потому что измерение с большой дисперсией указывает на то, что данные относительно разбросаны, и после сегментации данные можно более четко различить. Но я лично не думаю, что это имеет смысл делать, в конце концов, вычисление дисперсии — это тоже накладные расходы. Так что здесь мы выбираем самый простой способ - по очереди выбирать.
То есть мы начинаем с корня дерева и выбираем 0-е измерение в качестве основы для сортировки и разделения данных, а затем к слою, где глубина дерева равна 1, мы выбираем первое измерение и слой, где глубина дерева равна 2, мы выбираем Второе измерение и так далее. Когда глубина дерева превышает K, мы определяем глубину дерева по модулю.
После выяснения этого момента мы можем написать код построения дерева KD-Tree, который очень похож на код двоичного дерева выше, но с большей обработкой измерений.
# 外部暴露接口
def build_model(self, dataset):
self.root = self._build_model(dataset)
# 先忽略，容后再讲
self.set_father(self.root, None)
# 内部实现的接口
def _build_model(self, dataset, depth=0):
if len(dataset) == 0:
return None
# 通过树深对K取模来获得当前对哪一维切分
axis = depth % self.K
m = len(dataset) // 2
# 根据axis这一维排序
dataset = sorted(dataset, key=lambda x: x[axis])
# 将数据一分为二
left, mid, right = dataset[:m], dataset[m], dataset[m+1:]
# 递归建树
return KDTree.Node(
mid[axis],
mid,
axis,
depth,
len(dataset),
self._build_model(left, depth+1),
self._build_model(right, depth+1)
)
Таким образом, мы построили дерево, но в последующем запросе нам нужно получить доступ к родительскому узлу узла, поэтому нам нужно назначить указатель на родительский узел для каждого узла. Мы можем прописать это значение в коде построения дерева, но это будет немного сложнее, поэтому я выделю его отдельно и назначу каждому узлу как отдельную функцию. Для корневого узла, поскольку у него нет родительского узла, значение равно None.
Давайте взглянем на содержимое set_father, которое на самом деле очень простое и представляет собой рекурсивный обход дерева:
def set_father(self, node, father):
if node is None:
return
# 赋值
node.father = father
# 递归左右
self.set_father(node.lchild, node)
self.set_father(node.rchild, node)
Быстрый пакетный запрос
После того, как KD-дерево построено, его необходимо использовать.Получите несколько образцов, ближайших к образцу, в одном запросе. В равномерно распределенном наборе данных мы можем
Запрос выполняется вовремя, но может быть дольше для особых случаев, но и намного быстрее, чем наш запрос через наивный метод.
Мы можем легко обнаружить, что широкий сценарий использования KD-Tree используется дляОптимизируйте алгоритм KNN. В предыдущей статье об алгоритме KNN мы упоминали, что алгоритму KNN необходимо пройти весь набор данных при прогнозировании, затем вычислить расстояние между каждой выборкой в наборе данных и текущей выборкой и выбрать ближайшее K, что требует много s расходы. С помощью KD-Tree мы можем запроситьНайдите сразу до K ближайших образцов, что значительно повышает эффективность алгоритма KNN.
Итак, как же реализована эта операция запроса?
Этот запрос реализован на основе рекурсии, поэтому для тех, кто не знаком с рекурсией, он может показаться сложным на первый взгляд, вы можете сначала прочитать предыдущую статью о рекурсии.
Сначала мы проходимРекурсивно найти листовые узлы на KD-Tree, то есть найти подпространство, в котором находится образец. Этот поиск должен быть довольно простым, по сути, мы постоянно сравниваем текущий образец с линией разделения, чтобы увидеть, находится ли он слева или справа от линии разделения. Это то же самое, что и поиск элементов в бинарном дереве поиска:
def iter_down(self, node, data):
# 如果是叶子节点，则返回
if node.lchild is None and node.rchild is None:
return node
# 如果左节点为空，则递归右节点
if node.lchild is None:
return self.iter_down(node.rchild, data)
# 同理，递归左节点
if node.rchild is None:
return self.iter_down(node.rchild, data)
# 都不为空则和分割线判断是左还是右
axis = node.axis
next_node = node.lchild if data[axis] <= node.boundray else node.rchild
return self.iter_down(next_node, data)
Мы нашли листовой узел, на самом делепредставляет небольшую часть пространства выборки.
Давайте на самом деле пройдемся по процессу, допустим, мы хотим найти 3 точки. Сначала мы создадим набор кандидатов для хранения ответов. Когда мы находим листовой узел, в этой области есть только одна точка, и мы добавляем ее в набор кандидатов.
На приведенном выше рисунке фиолетовый x представляет собой образец, который мы ищем.После того, как мы найдем конечный узел, мы добавим текущую точку в набор кандидатов в двух случаях. Первый случайНабор кандидатов все еще доступен, то есть еще не полное K, где K — количество запросов, которые мы запрашиваем, равное 3. Второй случайРасстояние от текущей точки до выборки меньше наибольшего в наборе кандидатов, то нам нужно обновить набор кандидатов.
После того, как мы посетим эту точку, мыотметка, указывая на то, что точка уже была посещена. В это время нам нужно судить, закончился ли поиск по всему дереву.Если текущий узел уже является корневым узлом, это означает, что наш обход закончился, то возвращаем набор кандидатов, иначе это означает, что он еще не , и нам нужно продолжить поиск. На приведенном выше рисунке мы используемЗеленый цвет указывает на то, что образец помещен в набор кандидатов, а желтый цвет указывает на то, что он был посещен.
Поскольку наши поиски еще не закончены, нам нужно продолжать поиски. Продолжение поиска требует сужденияРасстояние между образцом и текущей линией разделенияЧтобы судить и разделить другую сторону линии, может ли быть ответ. Поскольку у листового узла нет другой стороны, мы сдаемся, поднимаемся на один вверх и прыгаем к его родительскому узлу.
Мы вычисляем расстояние и смотрим на набор кандидатов.Когда набор кандидатов не заполнен, мы присоединяемся к набору кандидатов и помечаем его как посещенный. Хотя есть разделительная линия, она такженет узла с другой стороны, так что пропускайте тоже.
Мы поднимаемся и переходим к его родительскому узлу.Мы выполняем то же самое суждение и обнаруживаем, что в это время все еще есть место для набора кандидатов, поэтому мы продолжаем добавлять его к ответу:
Но когда мы оценили расстояние до разделительной линии, то обнаружили, что на этот разПример выборки до разделительной линии меньше, чем максимальное расстояние в предыдущем наборе кандидатов, так что есть большая вероятность, что ответ находится по ту сторону разделительной линии:
Здесь d1 — расстояние от образца до разделительной линии, а d2 — расстояние от образца до самой дальней точки в наборе кандидатов. Поскольку он находится ближе к разделительной линии, вполне вероятно, что по ту сторону разделительной линии есть ответ.Поиск поддерева по другую сторону разделительной линиии выполните поиск до конечного узла.
Мы нашли листовой узел, вычислили расстояние и обнаружили, что в это времяНабор кандидатов заполнен, и его расстояние больше, чем любой ответ в наборе кандидатов, поэтому он не может составлять новый ответ. Поэтому мы просто отмечаем его как посещенный и не добавляем в набор кандидатов. Точно так же мы продолжаем переход к его родительскому узлу:
После сравнения обнаруживается, что данные к егоРасстояние меньше, чем наибольшее в наборе кандидатов, поэтому мы обновляем набор кандидатов, чтобы удалить ответ, расстояние которого больше, чем это. Затем мы повторяем описанный выше процесс до корневого узла.
Поскольку позади нет ближайшей точки, набор кандидатов не обновлялся Наконец, три точки, отмеченные зеленым цветом на рисунке выше, являются ответом.
Разобравшись с вышеописанным процессом, мы получаем логику в рекурсивной функции, которая практически совпадает с кодом, когда мы пишем ее на Python:
def query(node, data, answers, K):
# 判断node是否已经访问过
if node.visited:
# 标记访问
node.visited = True
# 计算data到node中点的距离
dis = cal_dis(data, node.point)
# 如果小于答案中最大值则更新答案
if dis < max(answers):
answers.update(node.point)
# 计算data到分割线的距离
dis = cal_dis(data, node.split)
# 如果小于最长距离，说明另一侧还可能有答案
if dis < max(answers):
# 获取当前节点的兄弟节点
brother = self.get_brother(node)
if brother is not None:
# 往下搜索到叶子节点，从叶子节点开始寻找
leaf = self.iter_down(brother, data)
if leaf is not None:
return self.query(leaf, data, answers, K)
# 如果已经到了根节点了，退出
if node is root:
return answers
# 递归父亲节点
return self.query(node.father, data, answers, K)
else:
if node is root:
return answers
return self.query(node.father, data, answers, K)
Окончательный код мало чем отличается от абзаца выше.После получения расстояния и сравнения максимального расстояния в ответе мы использовалиприоритетная очередь. В других местах почти то же самое, я тоже выложил на всеобщее обозрение:
def _query_nearest_k(self, node, path, data, topK, K):
# 我们用set记录访问过的路径，而不是直接在节点上标记
if node not in path:
path.add(node)
# 计算欧氏距离
dis = KDTree.distance(node.value, data)
if (len(topK) < K or dis < topK[-1]['distance']):
topK.append({'node': node, 'distance': dis})
# 使用优先队列获取topK
topK = heapq.nsmallest(K, topK, key=lambda x: x['distance'])
axis = node.axis
# 分割线都是直线，直接计算坐标差
dis = abs(data[axis] - node.boundray)
if len(topK) < K or dis <= topK[-1]['distance']:
brother = self.get_brother(node, path)
if brother is not None:
next_node = self.iter_down(brother, data)
if next_node is not None:
return self._query_nearest_k(next_node, path, data, topK, K)
if node == self.root:
return topK
return self._query_nearest_k(node.father, path, data, topK, K)
else:
if node == self.root:
return topK
return self._query_nearest_k(node.father, path, data, topK, K)
Эту логику должен уметь понять каждый, но есть сомнение, что мыПочему бы не добавить посещенное поле к узлу, но сохранить посещенный узел, передав набор?? Эту логику трудно понять, просто взглянув на код, и ее нужно понять путем практических экспериментов. Конечно, можно добавить поле к узлу.Если это сделано, после того, как мы выполним поиск, мы должны вручную выполнить еще одну рекурсию и установить для всех узлов в дереве значение false, иначе следующий запрос будет Некоторые узлы имеют был помечен как True, что, очевидно, влияет на результат. Ручное восстановление этих значений после запроса приведет к накладным расходам, поэтому идея состоит в том, чтобы использовать set для оценки доступа.
Функция iter_down здесь такая же, как функция, которую мы разместили выше, для поиска конечных узлов, то есть для поиска конечных узлов текущего поддерева. Если я правильно помню, это тоже есть в нашей статьеПервое вхождение рекурсии вызывает другую рекурсиюСлучай. Для новичков это может быть относительно сложно понять. Я лично предлагаю вам попробовать это самостоятельно, нарисовав kd-дерево на бумаге, чтобы смоделировать его вручную, и вы, естественно, будете знать операционную логику. Это также очень полезный способ думать и учиться.
оптимизация
Когда мы поймем логику построения и поиска по всему kd-дереву, давайтеПодумайте об оптимизации.
Глядя на этот код, мы можем изначально найти два места, которые можно оптимизировать: Первое место — это когда мы строим дерево. Каждый раз, когда мы рекурсивно, потому что мы хотим разделить данные на две части, мыб/у сортировкаметод достижения, и каждая сортировка
Сложность на самом деле не маленькая. На самом деле подумайте об этом, нам не нужно сортировать, мыПросто выберите первые n/2 числа, отсортированные по оси. Другими словами, это проблема выбора, а не проблема сортировки, поэтому вполне возможно, что мы можем использовать метод быстрого выбора, упомянутый ранее, для оптимизации. Используя быстрый выбор, мы можем
Завершите разделение данных в течение времени.
В другом месте, когда мы запрашиваем K соседей, мы используемприоритетная очередьОтветы в поддерживаемом наборе кандидатов, чтобы мы могли обновить ответы. Точно так же приоритетная очередь для получения topK также
сложность. Это также может быть оптимизировано, лучшая идеявместо этого используйте кучу. сможет сделать
По сравнению с методом heapq nsmallest вставка и извлечение более эффективны.
Суммировать
На этом мы почти закончили говорить о принципе KD-дерева.После того, как у нас есть функции построения дерева и запроса, мы можем использовать его для оптимизации алгоритма KNN. Но наше текущее KD-дерево поддерживает только построение дерева и запросы, если мыЧто делать, если я хочу вставить или удалить данные в коллекции? Вам нужно перестраивать дерево каждый раз, когда вы его изменяете? Это, очевидно, невозможно, но вставка и удаление узлов вызовут изменения в структуре дерева, что, вероятно, приведет к тому, что дерево перестанет быть сбалансированным Что нам делать в это время?
Давайте сначала ее продадим, а соответствующий контент будет в следующей статье, заинтересованные студенты не должны ее пропустить.
Наконец, я разместил полный код KD-дерева на ubuntu.paste Студенты, которые хотят просмотреть полный исходный код, пожалуйста, ответьте в официальном аккаунте.kd-treeсмотреть.
На сегодняшней статье все. Если вы чувствуете, что что-то приобрели, пожалуйста, нажмитеПодпишитесь или сделайте ретвитЧто ж, твое маленькое усилие много значит для меня.