Этот вопрос задавался несколько раз, но все они на разных языках (например, см. здесь для 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
в свой фрейм данных, но изо всех сил пытаюсь заставить код работать. Любые предложения относительно того, как я могу это сделать?
Я отредактировал вопрос, чтобы, надеюсь, прояснить логику фрейма данных.
Мне пока непонятно... Что такое переменная? Что представляет собой каждая строка?
В моем случае у меня есть модель машинного обучения, которая использует двоичные деревья для прогнозирования. Столбец var в моем примере выше представляет собой переменную разделения в двоичных деревьях модели ML. Таким образом, в df
выше каждая строка будет представлять один узел в дереве и его атрибуты (например, номеру дерева, которому он принадлежит, и т. д.).
Не похоже, что вы можете однозначно восстановить дерево на основе обхода предварительного порядка в глубину. Вам нужна дополнительная информация. baeldung.com/cs/reconstruct-tree-length-first-traversals
Я извлекаю деревья в этом порядке непосредственно из модели ML. Они упорядочены по принципу обхода «в глубину — сначала слева». Итак, при чтении df мы движемся вниз, по левой ветке. Если мы достигнем NA, это будет конечный узел и мы перейдем к следующей ветке. Поэтому мы всегда идем вниз по левой стороне, пока не достигнем конечного узла, а затем продолжаем процесс на этой ветви.
@MrFlick Может быть, я неправильно интерпретирую тот документ, на который вы ссылаетесь. Но там говорится: «Чтобы мы могли восстановить дерево из его предварительного и последующего порядка, наше дерево должно быть полным двоичным деревом. Это означает, что каждый узел в дереве должен иметь 0 или 2 узла». Все деревья в моем примере являются полными двоичными деревьями (т.е. каждый узел имеет 0 или 2 дочерних узла).
Там написано «предзаказ и постзаказ». У вас есть только один из двух. Двоичная часть не является проблемой.
@MrFlick Итак, с моим текущим порядком деревьев в фрейме данных df невозможно определить глубину каждого узла? Любые предложения о том, что я могу сделать?
Вам нужно больше информации в data.frame. Непонятно, как вы это построили. Но если бы каждый узел указывал на своего родителя, это значительно упростило бы задачу.
Структура кадра данных извлекается непосредственно из сборки модели BART с использованием пакета dbarts. Внутри они заказывают фрейм данных таким образом в своем пакете.
Я думаю, если вы явно знаете, какие узлы являются терминальными, а какие нет, то можно декодировать. Итак, вот функция, которая может рассчитать глубину с помощью этой дополнительной информации.
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(...))
Можете ли вы объяснить логику data.frame?