Найти глубину каждого узла двоичного дерева в R?

Этот вопрос задавался несколько раз, но все они на разных языках (например, см. здесь для Java и здесь для Python, но я пытаюсь добиться этого в R.

У меня есть фрейм данных деревьев. Мои деревья упорядочены по принципу обхода в глубину сначала левой стороны, как в приведенном ниже коде:

df <- data.frame(
  var = c("x2", NA, NA, "x1", NA, "x2", "x2", NA, NA, NA, "x2", NA, "x10", NA, NA, NA, "x1", NA, NA, "x5", NA, NA),
  node = c(1, 2, 3, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 1, 1, 2, 3, 1, 2, 3),
  terminal = c(FALSE, TRUE, TRUE, FALSE, TRUE, FALSE, FALSE, TRUE, TRUE, TRUE, FALSE, TRUE, FALSE, TRUE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE),
  iteration = c(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2),
  treeNum = c(1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 1, 2, 2, 2, 3, 3, 3),
  stringsAsFactors = FALSE 
)

Структура фрейма данных следующая:

var = имя переменной (если терминальный узел или пень, то это просто NA)

узел = номер узла

терминал = является ли узел терминальным узлом или нет.

итерация = номер итерации

TreeNum = номер дерева

Как видите, мой фрейм данных содержит 3 дерева за 2 итерации.

Для ясности, если мы посмотрим на одно дерево (например, дерево номер 2 в итерации 1), оно будет выглядеть следующим образом (где узлы пронумерованы в соответствии с методом обхода):

И глубина этого дерева (упорядоченная методом «глубина-сначала-левая сторона») будет: 0,1,1,2,3,3,2.

В конечном итоге я хочу добавить столбец depth в свой фрейм данных, но изо всех сил пытаюсь заставить код работать. Любые предложения относительно того, как я могу это сделать?

Можете ли вы объяснить логику data.frame?

s_baldur 13.03.2024 14:29

Я отредактировал вопрос, чтобы, надеюсь, прояснить логику фрейма данных.

Electrino 13.03.2024 14:41

Мне пока непонятно... Что такое переменная? Что представляет собой каждая строка?

s_baldur 13.03.2024 14:44

В моем случае у меня есть модель машинного обучения, которая использует двоичные деревья для прогнозирования. Столбец var в моем примере выше представляет собой переменную разделения в двоичных деревьях модели ML. Таким образом, в df выше каждая строка будет представлять один узел в дереве и его атрибуты (например, номеру дерева, которому он принадлежит, и т. д.).

Electrino 13.03.2024 14:50

Не похоже, что вы можете однозначно восстановить дерево на основе обхода предварительного порядка в глубину. Вам нужна дополнительная информация. baeldung.com/cs/reconstruct-tree-length-first-traversals

MrFlick 13.03.2024 15:22

Я извлекаю деревья в этом порядке непосредственно из модели ML. Они упорядочены по принципу обхода «в глубину — сначала слева». Итак, при чтении df мы движемся вниз, по левой ветке. Если мы достигнем NA, это будет конечный узел и мы перейдем к следующей ветке. Поэтому мы всегда идем вниз по левой стороне, пока не достигнем конечного узла, а затем продолжаем процесс на этой ветви.

Electrino 13.03.2024 16:03

@MrFlick Может быть, я неправильно интерпретирую тот документ, на который вы ссылаетесь. Но там говорится: «Чтобы мы могли восстановить дерево из его предварительного и последующего порядка, наше дерево должно быть полным двоичным деревом. Это означает, что каждый узел в дереве должен иметь 0 или 2 узла». Все деревья в моем примере являются полными двоичными деревьями (т.е. каждый узел имеет 0 или 2 дочерних узла).

Electrino 13.03.2024 16:17

Там написано «предзаказ и постзаказ». У вас есть только один из двух. Двоичная часть не является проблемой.

MrFlick 13.03.2024 16:24

@MrFlick Итак, с моим текущим порядком деревьев в фрейме данных df невозможно определить глубину каждого узла? Любые предложения о том, что я могу сделать?

Electrino 13.03.2024 17:08

Вам нужно больше информации в data.frame. Непонятно, как вы это построили. Но если бы каждый узел указывал на своего родителя, это значительно упростило бы задачу.

MrFlick 13.03.2024 18:00

Структура кадра данных извлекается непосредственно из сборки модели BART с использованием пакета dbarts. Внутри они заказывают фрейм данных таким образом в своем пакете.

Electrino 13.03.2024 18:09
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
11
89
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Я думаю, если вы явно знаете, какие узлы являются терминальными, а какие нет, то можно декодировать. Итак, вот функция, которая может рассчитать глубину с помощью этой дополнительной информации.

node_depth <- function(tree) {
  stopifnot(is.data.frame(tree))
  stopifnot("terminal" %in% names(tree))
  depths <- rep(0, nrow(tree))
  recurse <- function(idx, current_depth) {
    if (idx > nrow(tree)) {
      return(idx)
    }
    depths[idx] <<- current_depth
    if (tree$terminal[idx]) {
      return(idx+1)
    }
    step <- recurse(idx+1, current_depth + 1)
    step <- recurse(step, current_depth + 1)
    step
  }
  recurse(1, 1)
  depths
}

Похоже, что вы нарисовали дерево TreeNum==2 на итерации==1. Мы можем запустить функцию на этом дереве с помощью

node_depth(subset(df, iteration==1 & treeNum==2))
# [1] 1 2 2 3 4 4 3

(вы можете вычесть 1 из вектора, если предпочитаете начинать с 0).

Мы можем запустить это на всех деревьях с помощью

lapply(split(df, ~treeNum + iteration), 
  function(x) cbind(x, depth=node_depth(x)))

который возвращает

$`1.1`
   var node terminal iteration treeNum depth
1   x2    1    FALSE         1       1     1
2 <NA>    2     TRUE         1       1     2
3 <NA>    3     TRUE         1       1     2

$`2.1`
    var node terminal iteration treeNum depth
4    x1    1    FALSE         1       2     1
5  <NA>    2     TRUE         1       2     2
6    x2    3    FALSE         1       2     2
7    x2    4    FALSE         1       2     3
8  <NA>    5     TRUE         1       2     4
9  <NA>    6     TRUE         1       2     4
10 <NA>    7     TRUE         1       2     3

$`3.1`
    var node terminal iteration treeNum depth
11   x2    1    FALSE         1       3     1
12 <NA>    2     TRUE         1       3     2
13  x10    3    FALSE         1       3     2
14 <NA>    4     TRUE         1       3     3
15 <NA>    5     TRUE         1       3     3

$`1.2`
    var node terminal iteration treeNum depth
16 <NA>    1     TRUE         2       1     1

$`2.2`
    var node terminal iteration treeNum depth
17   x1    1    FALSE         2       2     1
18 <NA>    2     TRUE         2       2     2
19 <NA>    3     TRUE         2       2     2

$`3.2`
    var node terminal iteration treeNum depth
20   x5    1    FALSE         2       3     1
21 <NA>    2     TRUE         2       3     2
22 <NA>    3     TRUE         2       3     2

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

Использование обхода по предварительному порядку и тот факт, что каждый узел либо является терминальным, либо имеет двух дочерних узлов.

lapply(
  split(df$terminal, df[c("treeNum", "iteration")]),
  \(term) {
    i <- 0L
    depth <- vector("integer", length(term))
    helper <- \(d) {
      i        <<- i + 1L
      depth[i] <<- d
      if (!term[i]) {
        helper(d+1L)
        helper(d+1L)
      }
    }
    helper(0L)
    return(depth)
  }
)

$`1.1`
[1] 0 1 1

$`2.1`
[1] 0 1 1 2 3 3 2

$`3.1`
[1] 0 1 1 2 2

$`1.2`
[1] 0

$`2.2`
[1] 0 1 1

$`3.2`
[1] 0 1 1

Вы можете добавить результаты в data.frame с помощью

df$depth <- unlist(lapply(...))

Другие вопросы по теме