在 R 中创建随机树

发布于03月10日

假设我想在R中创建一个间隔为(0,1)、最大深度为3的二叉树，方法如下:

首先，我们有一个树t=c(0.1,0.2,0.3,0.4,0.5,0.6,0.7)的潜在截止值池，截止值意味着如果我们随机 Select 值0.4，那么我们将区间(0,1)拆分为(0,0.4)和(0.4,1).

我想做的步骤是:

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

2) 从t中随机 Select 一个截止值，表示为t_1

3) 根据 Select 的截止线，将间隔(0,1)拆分为子间隔(0,t_1)和(t_1,1)

4) 然后随机 Select (0,t_1)和(t_1,1)之间的间隔

5) 对于所选间隔，从截止点随机抽取一个有意义的点t_2，即不在间隔之外的点

6) 继续这个过程直到达到最大深度.

我完全不知道从哪里开始.这是发布这样一个问题的合适论坛吗？

推荐答案

创建这样的树 struct 需要一个递归函数(即调用自身的函数).下面的函数创建一个 node 列表，其中每个分支 node 包含一个split值，以及两个子 node left和right.叶 node 包含叶中包含的最终范围.

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()

要获得初始拆分值，我们需要:

tree$split
#> [1] 0.2655087

所以右边的分支处理0.2655087到1之间的所有值.要想知道它把这个范围分成了什么样，我们需要

tree$right$split
#> [1] 0.4136423

所以这个分支分裂成左边[0.2655087,0.4136423]和右边[0.4136423,1]之间的值.让我们判断一下左侧 node :

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

这将[0.2655087,0.4136423]分支拆分为左[0.2655087,0.3985904]分支和右[0.3985904,0.4136423]分支.

如果我们取这根右边的 twig ，现在已经达到深度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(v2.0.1)于2022-03-09创建}