种植决策树

与所有监督式机器学习模型一样,训练过的树也经过训练,可以更好地解释一组训练样本。决策树的最佳训练是 NP 困难问题。因此,通常使用启发法来完成训练。启发法是一种易于创建的学习算法,可提供非最佳但最优的决策树。

用于训练决策树的大多数算法都适用于贪欲分裂和征服策略。该算法首先创建一个节点(根),然后以递归方式一味地扩大决策树。

在每个节点,评估所有可能的条件并进行评分。该算法会选择“最佳”条件,即得分最高的条件。目前,您只需要知道得分就是与任务相关的指标,并且系统会选择条件来最大限度地提升该指标。

例如,在 Palmer 企鹅数据集(用于本课程后面的代码示例)中,大多数 Adelie 和 Chinstrap 企鹅的帐单长度大于 16 毫米,而大多数巴布亚企鹅的帐单金额都更小。因此,条件 bill_length_mm ≥ 16 可完美预测根特企鹅,但无法区分 Adelies 和 Chintraps。算法可能会选择此条件。

一个条件指向两个叶子。条件为 'bill_length_mm >= 16'。
如果是,表示绿叶是 Adelie 或 Chinstrap。如果不是,请以叶子显示“Gentoo”。

图 7. 发展树的第一步。

 

然后,该算法以递归方式独立地在这两个子节点上重复。如果未找到满足条件,节点就会变成一片叶子。叶预测被确定为示例中最具代表性的标签值。

算法如下:

def train_decision_tree(training_examples):
  root = create_root() # Create a decision tree with a single empty root.
  grow_tree(root, training_examples) # Grow the root node.
  return root

def grow_tree(node, examples):
  condition = find_best_condition(examples) # Find the best condition.

  if condition is None:
    # No satisfying conditions were found, therefore the grow of the branch stops.
    set_leaf_prediction(node, examples)
    return

  # Create two childrens for the node.
  positive_child, negative_child = split_node(node, condition)

  # List the training examples used by each children.
  negative_examples = [example for example in examples if not condition(example)]
  positive_examples = [example for example in examples if condition(example)]

  # Continue the growth of the children.
  grow_tree(negative_child, negative_examples)
  grow_tree(positive_child, positive_examples)

我们来更详细地了解一下训练特定决策树的步骤。

第 1 步:创建根目录:

一个带问号的节点。

第 2 步:生长节点 1。找到了条件“x1 ≥ 1”。 创建了两个子节点:

指向两个未定义节点的根节点。

第 3 步:生长节点 #2。未找到满足条件。因此,请将节点变成一片叶子:

指向两个未定义节点的根节点。

第 4 步:成长节点 3。发现条件“x2 ≥ 0.5”。系统会创建两个子节点。

一个根节点、一个条件和三个叶子。

还有一些方法可以扩大决策树的规模。一种常用的替代方案是在全球范围内优化节点,而不是使用分而治之策略。

在 TF-DF 中,默认情况下,系统会使用上文所述的“贪潮分治法”扩展决策树。或者,您也可以使用 growing_strategy=BEST_FIRST_GLOBAL 启用全局增长。

根据输入特征的数量和类型,给定节点的可能条件数量可能非常庞大,通常是无限的。例如,给定阈值 $\mathrm{feature}_i \geq t$,$t \in \mathbb{R}$ 的所有可能的阈值值的组合是无限的。

负责查找最佳条件的例程称为“拆分器”。因为拆分器需要测试许多可能的条件,所以拆分器是训练决策树时的瓶颈。

分配器最大限度提高的得分取决于任务。例如:

  • 信息增益Gini(稍后介绍)通常用于分类。
  • 均方误差通常用于回归。

有许多分路器算法,每种算法对以下各项的支持各不相同:

  • 特征的类型;例如,数值、分类、文本
  • 任务;例如二元分类、多类别分类、回归
  • 条件的类型;例如阈值条件、边衬区条件、倾斜条件
  • 正则化标准;例如,适用于阈值条件的精确或拆分器

此外,在内存用量、CPU 使用率、计算分布情况等方面,也有对应的不同拆分器变体。

在 TF-DF 中,从自动检测(或手动指定)的功能类型、超参数和每个分路器的估算速度(在训练期间,TF-DF 会运行一个小型模型来预测每个候选分路器的速度)隐式选择分路器。