在R中创建随机树

Question

在R中创建随机树

3

假设我想在 R 中创建一个二叉树，其间隔为 (0,1)，最大深度为 3，步骤如下：

1. 首先有一个潜在的二叉树切割点池： 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)。

2. 开始时有整个区间(0,1) 3. 从t中随机选择一个切割点t_1 4. 根据所选的切割点将区间(0,1)分割成子区间(0,t_1)和(t_1,1) 5. 随机选择其中一个子区间(0,t_1)或(t_1,1)，并从切割点中随机抽取一个合适的点t_2，使得该点不在区间之外

6. 继续执行该过程，直到达到最大深度

我不知道从何处开始。这是发布此类问题的正确论坛吗？

- Jonathan1234

2个回答

2

也许我们可以使用 Reduce 以二叉树的方式生成区间。

Reduce(
  function(interval, k) {
    lb <- min(interval)
    ub <- max(interval)
    x <- v[v > lb & v < ub]
    if (!length(x)) {
      return(c(NA, NA))
    }
    p <- sample(x, 1)
    list(c(lb, p), c(p, ub))[[sample(1:2, 1)]]
  },
  1:3,
  init = c(0, 1),
  accumulate = TRUE
)

您将看到以下结果：

[[1]]
[1] 0 1

[[2]]
[1] 0.0 0.6

[[3]]
[1] 0.0 0.2

[[4]]
[1] 0.0 0.1

该指示了从上到下每次迭代中所选择的时间间隔。

- ThomasIsCoding

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Allan Cameron · Accepted Answer

创建这样的树形结构需要一个递归函数（即调用自身的函数）。以下函数创建了一个节点列表，其中每个分支节点包含一个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()

为了获取初始分割值，我们执行：

tree$split
#> [1] 0.2655087

因此，右侧分支处理介于0.2655087和1之间的所有值。为了查看它在哪里分裂这个范围，我们执行

tree$right$split
#> [1] 0.4136423

因此，该分支在左侧和右侧之间分成值的范围为[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组成的向量，或者你可能希望它绘制树形结构，后者更加复杂，但仍然可行。

创建于2022-03-09，使用reprex包（v2.0.1）。