与所有监督式机器学习模型一样,决策树经过训练,能够 用于解释一组训练示例。决策树的最佳训练方式是 NP 困难问题。因此,训练通常使用启发式方法完成, 一种易于创建的学习算法,可提供非最优,但接近于 最优决策树。
用于训练决策树的大多数算法都使用贪心除法和 制胜策略。该算法首先创建一个节点(根节点),然后 以递归方式贪心地增大决策树。
在每个节点上,系统会评估所有可能的条件并打分。通过 算法选出“最佳”条件,即 得分。现在,您只需要知道,得分是与 任务和条件,以最大限度地提高该指标。
例如,在 Palmer 企鹅 数据集(在本课程后面的代码示例中),大多数 Adelie 和 Chinstrap 企鹅的账单长度超过 16 毫米,而大部分企鹅 企鹅的账单比较小。因此,条件 bill_length_mm ≥ 16 能够对 巴布亚企鹅但无法分辨 Adelies 和 Chinstraps 之间的交流。算法很可能会选择此条件。
<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”已找到。两个儿童 节点数量
还有其他方法可以扩展决策树。一种常见的替代方案是 全局优化节点,而不是使用分而治之策略。
growing_strategy="BEST_FIRST_GLOBAL"
参数实现增长。
请参阅
文档了解详情。
根据输入特征的数量和类型, 可能非常庞大,通常是无限的。 例如,假设存在一个阈值条件 $\mathrm{feature}_i \geq t$, 所有参数的 可能 阈值 $t \in \mathbb{R}$ 是无限的。
负责找出最佳状况的例程称为 splitter。由于它需要测试许多可能的条件,因此分频器 是训练决策树时的瓶颈。
拆分器最大化的得分取决于具体任务。例如:
有许多拆分器算法,每种算法对以下方面的支持各不相同:
- 特征的类型;例如数字、分类、文本
- 任务;例如,二元分类、多类别 分类、回归
- 条件的类型;例如阈值条件、内嵌条件 斜面
- 正则化标准;例如精确拆分器或近似拆分器 适用于阈值条件
此外,还有等效拆分器变体,它们权衡不同 内存用量、CPU 用量、计算分布等方面的信息。