种植决策树

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

用于训练决策树的大多数算法都使用贪心除法和 制胜策略。该算法首先创建一个节点(根节点),然后 以递归方式贪心地增大决策树。

在每个节点上,系统会评估所有可能的条件并打分。通过 算法选出“最佳”条件,即 得分。现在,您只需要知道,得分是与 任务和条件,以最大限度地提高该指标。

例如,在 Palmer 企鹅 数据集(在本课程后面的代码示例中),大多数 Adelie 和 Chinstrap 企鹅的账单长度超过 16 毫米,而大部分企鹅 企鹅的账单比较小。因此,条件 bill_length_mm ≥ 16 能够对 巴布亚企鹅但无法分辨 Adelies 和 Chinstraps 之间的交流。算法很可能会选择此条件。

一种情况导致两片叶子。使用情况为“bill_length_mm >= 16”。
如果是,这个叶子就是“Adelie 或 Chinstrap”。如果不是,则代表叶节点。
是“Gentoo”

<ph type="x-smartling-placeholder"></ph> 图 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”已找到。两个儿童 节点数量

根节点、
有三片叶子。

还有其他方法可以扩展决策树。一种常见的替代方案是 全局优化节点,而不是使用分而治之策略。

YDF 代码
在 YDF 中,决策树是随着“贪心的分而治之”而生长的 算法。或者,您也可以 使用 growing_strategy="BEST_FIRST_GLOBAL" 参数实现增长。 请参阅 文档了解详情。

根据输入特征的数量和类型, 可能非常庞大,通常是无限的。 例如,假设存在一个阈值条件 $\mathrm{feature}_i \geq t$, 所有参数的 可能 阈值 $t \in \mathbb{R}$ 是无限的。

负责找出最佳状况的例程称为 splitter。由于它需要测试许多可能的条件,因此分频器 是训练决策树时的瓶颈。

拆分器最大化的得分取决于具体任务。例如:

  • 信息增益Gini(同时 通常用于分类。
  • 均方误差通常用于回归。

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

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

此外,还有等效拆分器变体,它们权衡不同 内存用量、CPU 用量、计算分布等方面的信息。

YDF 代码
在 YDF 中,分隔线是从自动检测的(或 特征的类型、超参数和 每个分割器的速度(在训练期间,YDF 会运行一个小型模型来预测 每个候选字词拆分器的速度)。