动机
知识获取问观察及专家判断怎样变成可支持决策的表示。引擎可以完美应用规则,但规则太广、互相矛盾或漏了变量,仍不可靠。决策树提供透明的提议方法:每条路记所问问题,每叶记结果。
透明不把归纳变成演绎。从四例学的树也会决定未见例,纯训练叶不证普遍物理定律。我们因此完整规范有限工具的格式、分割、终止、编译及解释,再分开工具正确与所获领域策略正确。
定义
定义 27.1.1
(训练表、节点与二元熵)
有限表每行 对 个具名布尔(Boole)属性给零或一,标记 亦二元,重复行照计。非空节点的正标比例 ,二元熵为 ,端点零乘对数零定为零。
定义 27.1.2
(信息增益与叶预测)
属性 分成大小 的孩子,节点大小 ,信息增益为:
空孩子项权重零,无须定 。叶预测多数,平手取零;空孩子取父多数作明订后备,不是假称该孩子有观察证据。
定义 27.1.3
(有限学习器)
有限学习器在节点纯或无剩余属性时停;否则选最大增益,按固定属性顺序破同分,两支递归并移除所选属性。它不会只因最大增益零就停,每路同属性最多测一次。这个完整策略让定理与可选剪枝启发分开。
定义 27.1.4
(编译规则与解释)
叶路径给属性值的合取,编译规则以此为条件、叶标记为结论。完整输入只循一条路,解释就是实际测试值序列与叶,不必声称物理因果。部分观察则需另订策略,例如所有完整填法都同标才答,否则未知。
定理/命题
定理 27.1.5
(有限决策树的熵账目)
固定非空表经有限树分割, 是全部行到节点 v 的比例, 是其局部增益,则
每个增益非负,总减幅不超根熵,且恰在所有非空叶纯时等于根熵。这是该表的经验恒等式,不是总体泛化界。
定理 27.1.6
(有限学习与精确规则编译)
上述学习器会终止,深度至多 m。叶规则对完整布尔输入互斥且穷尽,评估结果与树在所有完整输入一致。若相同特征向量从无矛盾标记,不剪枝学习器会拟合每行,即使中途增益为零。若同向量有相反标记,任何依这些属性的确定函数都不能同时拟合。
证明思路
证明
(凹性与逐层相消)
熵在内部的二阶导数为 ,连续延伸保凹。父比例是孩子比例加权平均,凹性证父熵不小于加权子熵,即增益非负,空支以零权重处理。
每内节点增益乘全局到达比例,再对树相加。内孩子的负熵项,恰与该孩子作内节点时的正熵项同权相消。只剩根正项与叶负项,得账目。叶熵非负,恰在非空叶纯时为零,证余下结论。
证明透视
局部增益只是全局账目一项
下一问可以零增益,条件化后再问却有用。账目把各节点增益乘到达比例,不要求根立即说明所有标记差异。零增益即停是额外建模策略,不是熵非负推出的结论。
证明
(终止、互斥规则与拟合)
终止因每个非叶调用少一属性,深度最多 m,分支有限。完整输入每测一次只走一边,必到一叶并满足其条件。两叶有首次分岔,对同一属性要求相反值,不能同时满足,证互斥与穷尽,也证树规则等价。
深度 m 后仍同组的行,全部特征相同;标记一致时必纯,较早纯叶也拟合,所以全表正确。有矛盾时,确定输出对同向量只有一值,至少一行错。叶多数最小化该叶错误数,因两种输出分别错另一类的行数;它不判断哪个原标记才符合真实领域。
证明透视
每项保证用到哪个假设
终止性只用到每次递归调用都消耗一个属性,所以深度至多为 。互斥性来自两条叶路径第一次分岔之处:该处测试同一个属性,却取相反的值。拟合性才是假设起作用的地方:只有在深度 时,仍被分在一组的数据行才必定有相同的特征向量,而标签一致使这样的组成为纯的。若去掉一致性,同一论证只能得到一片多数叶,至少有一个错误。熵在这个证明中不起作用;增益规则决定建出哪一棵树,而不决定这三项性质是否成立。
例题详解
例题 27.1.7
(学 OR 并核对每个 bit)
四行 为 。根熵 ,分 A 得两等大孩子,熵一与零,增益约 。B 同分,固定顺序选 A。A 零支再问 B,局部增益一,权重一半,账目 ,叶纯、训练错零。根增益不是整份解释。
概念视角分析
信息增益就是互信息
把一个节点的数据行看作属性值与标签的数对 上的经验分布,则
即联合分布相对于其边缘分布之积的散度。在 OR 表中,、,得 ,与上面算出的增益相同。增益为零,恰好表示该属性与标签在这个节点内经验上独立。
例题 27.1.8
(编译并解释所得策略)
规则为 A 一则标一;A 零且 B 一则标一;A 零且 B 零则标零。 的实际路是 A 零、B 一、叶一。只知 A 一时,两个 B 填法都标一;只知 A 零却未定,因 B 改答案。正规则析取可化成 ,但原路径仍保留工具真正问过什么。
例题 27.1.9
(矛盾案例暴露表示限制)
列为 。零零两例不论怎分仍同叶却标相反,平手取零错一,经验错误 。任何 A,B 确定规则至少错其中一行。应检查错标、时间变化或遗漏的测量;不增加信息只加深树,不能分开同向量。
配套可执行工具实现此策略,输出 OR 树、叶规则、预测及路径;核心递归如下:
function grow(rows, attributes, fallback = 0) {
if (rows.length === 0) return { label: fallback };
const majority = rows.filter(row => row.y === 1).length > rows.length / 2 ? 1 : 0;
if (rows.every(row => row.y === rows[0].y) || attributes.length === 0)
return { label: majority };
const test = attributes.reduce((best, name) =>
gain(rows, name) > gain(rows, best) ? name : best);
const rest = attributes.filter(name => name !== test);
return { test,
zero: grow(rows.filter(row => row[test] === 0), rest, majority),
one: grow(rows.filter(row => row[test] === 1), rest, majority) };
}
配套另提供熵、增益、格式检查、预测与规则抽取,这段不是声称未定义 helper 自己能执行的独立程序。属性序处理计算结果同分,浮点熵可影响极接近比较,但终止与等价性对任何剩余属性选择都成立。工具应记数据、格式、同分策略与实际输出,而不只报一句“智能建议”。
空分支尤其能区分工具策略与证据。如果训练表从未出现某属性组合,递归仍须定义完整输入到达该分支时怎样作答;沿用父多数令函数完整,却没有创造新的观察。解释接口应能指出这是后备叶,让用户知道结论来自策略延伸,而不是该分支已有很多相同案例。
知识获取还应保存数据版本与标记依据。专家改一行标记后,树的分割顺序可能连根节点都改变,所以不能只修改屏幕上某条规则而假装仍是原训练结果。应重新执行同一已记录策略,比较新旧规则与案例,再让领域审核决定是否接受改动。可重放的工具把这些决策变得可查,不代替决策本身。
常见错误
反例模式
零即时增益可藏有交互作用
完整 XOR 表上 A、B 根增益都零,每孩子仍各半。但先分 A,再各问 B,全部叶纯,总熵减一 bit。零增益即停会输出常数多数,错过完全可表示的交互作用。本学习器到纯或属性尽才停;剪枝另论。
常见错误
(把树的规则当作领域定律)
工具规则是构造树的演绎后果,不是有限观察在无限制世界的逻辑后果。很多函数在未完整表上同意,表外却不同。专家要检查条件、混杂因素及错建议成本,再用独立、符合使用场景的案例测预测。解释清楚也不能代替外部验证。
常见错误
(以零代替缺失值、以频率当作概率)
不要默认把缺失的测量值当零,零在格式中是真正观察值;完整输入格式错则工具拒绝,部分输入要另一语义。叶标记比例也不自动校准为概率,尤其树本身由同数据挑出。训练错小、路径有说服力及外部可靠性是不同问题。每个后备决定都应可追溯,尤其不能把没有案例的空叶说成已由数据验证的专家结论。
总结
有限树学习可完全规范与核对:熵减逐层相消,属性耗用令终止,叶规则精确保留函数与路径。这些是工具的演绎保证;所学函数是否反映领域,仍需充分特征、可信标记及新证据。
练习
练习 27.1.10
(对完整的四行 XOR 表,求根熵、两个根增益、先分 后的两个条件增益,以及加权熵账目。)
核心
四行 为 。
解答(3)
- 1
计算根熵与根增益
两行标零、两行标一,所以 bit。以 分割得两个孩子,每个孩子各有一行零标与一行一标,熵都是一,故 ; 同样。
- 2
计算先分 后的条件增益
关键一步
的每个孩子有两行、标记不同,再以 分割便得纯叶。每个孩子熵为一,其两个子节点熵为零,所以每个条件增益是 。
依据: 根增益为零不代表下一问没有用。
- 3
合成加权账目
每个孩子的全局权重为二分之一,账目为 ,等于根熵,而且所有叶都纯、熵为零。第一问增益为零,并不排除两步分割有效。
练习 27.1.11
(某节点有八行,两种标记各四行。一次分割得类别数 与 。求信息增益及分割后的多数类训练错误。这两个数量可以互换吗?)
基础
解答(3)
- 1
计算增益
父熵为 。每个孩子有四行,标记比例为 或 ,熵为 bit。两个孩子权重都是二分之一,所以 bit。
- 2
计算训练错误
每个孩子预测其多数标记,各错一行,所以错误为 。
- 3
比较两个量
前者是以 bit 计的熵减,后者是错分比例,公式与单位都不同;两者也都不是对未来错误率的保证。
练习 27.1.12
(某树先测 : 时返回零; 时再测 , 返回一, 返回零。写出全部叶规则,化简正条件,并评估“ 而 未知”的部分观察。)
核心
解答(3)
- 1
写出叶规则
三片叶给出: 则标零; 且 则标一; 且 则标零。
- 2
化简正条件
只有一片叶预测一,所以正条件是 且 ,即 。
- 3
对 应用所有完整填法策略
且 时标记为零, 且 时标记为一。两种填法不一致,所以策略返回未定。把未知的 当作假,是在回答另一个问题。
依据: 只有未知属性的每个填法都给同一标记,才返回标记。
练习 27.1.13
(两行训练数据有完全相同的完整特征向量,但标记相反。证明任何依这些特征的确定树或规则函数都不能同时拟合两行。再多重复其中一种标记,能消除这个表示冲突吗?)
综合证明
解答(3)
- 1
利用确定函数对每个向量只有一个输出
设 为任何依特征的确定函数, 为共同的向量,则 只是一个标记。
- 2
与两个标记比较
关键一步
的一次出现标零,另一次标一,所以 至少与其中一个不同。因此 在这两行上至少错一行,不存在能同时拟合两行的 。
- 3
检视重复副本
∎增加同一标记的副本会改变多数及错误比例,但两个冲突标记仍然同时存在,一个输出仍不可能等于两者。要处理冲突本身,需要新的信息特征,或修订对数据的解读。