r - 在 R 中创建随机树

Question

假设我想在 R 中创建一个区间 (0,1) 上最大深度 3 的二叉树，如下所示方式:

首先，我们有树 t=c(0.1,0.2,0.3,0.4,0.5,0.6,0.7) 的潜在截止池，截止意味着如果我们随机选择值 0.4 然后我们将区间 (0,1) 拆分为 (0,0.4) 和 (0.4,1 )。

我想做的步骤是:

1)从整个区间(0,1)开始

2)从t中随机选择一个cut-off，表示为t_1

3)根据选择的截止值分割区间 (0,1)，即分成子区间 (0,t_1) 和 (t_1,1 )

4)然后随机选择区间(0,t_1)和(t_1,1)

5) 对于选定的区间，从截止点随机采样一个有意义的点 t_2，即不在区间之外的点

6) 继续这个过程，直到我们达到最大深度。

我完全不知道从哪里开始。这是发布此类问题的正确论坛吗？

Answer 1

创建这样的树结构需要递归函数(即调用自身的函数)。以下函数创建一个节点列表，其中每个分支节点包含一个 split 值，以及两个名为 left 和 right 的子节点。叶节点包含叶内包含的最终范围。

make_node <- function(min = 0, max = 1, desired_depth = 3, depth = 0) {
  
  if (depth < desired_depth) {
    split <- runif(1, min, max)
  list(split = split, 
       left = make_node(min, split, desired_depth, depth + 1),
       right = make_node(split, max, desired_depth, depth + 1))
  } else {
    list(range = c(min, max))
  }
}

它是这样工作的。让我们创建一个可复制的树:

set.seed(1)

tree <- make_node()

为了得到初始 split 值，我们做:

tree$split
#> [1] 0.2655087

因此右分支处理 0.2655087 和 1 之间的所有值。要查看它在何处拆分此范围，我们执行

tree$right$split
#> [1] 0.4136423

所以这个分支 split 成左边 [0.2655087, 0.4136423] 和右边 [0.4136423, 1] 之间的值。让我们检查一下左节点:

tree$right$left$split
#> [1] 0.3985904

现在已将 [0.2655087, 0.4136423] 分支拆分为左 [0.2655087, 0.3985904] 分支和右 [0.3985904, 0.4136423] 分支。

如果我们采取这个正确的分支，现在已经达到深度 3，那么我们得到这个叶子的最终范围并确认它的范围:

tree$right$left$right
#> $range
#> [1] 0.3985904 0.4136423

当然，为了让这一切变得更容易，您可能需要某种函数来遍历树以对特定数字进行分类。

walk_tree <- function(value, tree) {
  result <- paste("Value:", value, "\n")
  while(is.null(tree$range)) {
    if(value >= tree$split) {
      result <- paste(result, "\nGreater than split of", tree$split)
      tree <- tree$right
    } else {
      result <- paste(result, "\nLess than split of", tree$split)
      tree <- tree$left
    }
  }
  result <- paste0(result, "\nValue falls into leaf node with range [",
                  tree$range[1], ",", tree$range[2], "]\n")
  cat(result)
}

所以，例如，我们得到

walk_tree(value = 0.4, tree)
#> Value: 0.4 
#>  
#> Greater than split of 0.2655086631421 
#> Less than split of 0.413642294289884 
#> Greater than split of 0.398590389362078
#> Value falls into leaf node with range [0.398590389362078,0.413642294289884]

您可能更喜欢此函数返回一个由 0 和 1 组成的向量，或者您可能正在寻找它来绘制树，这虽然比较棘手，但却是可能的。

^{由 reprex package 创建于 2022-03-09 (v2.0.1)}