K-NN

• 输入：p维实例特征向量

  • 将样本点视为p维特征空间的中点

• 输出：实例类别，可以取多类别

• 基本思想

  • 在已有数据中找到与$X_0$相似的若干个观测 $(X_1, X_2, …, X_k)$，称为$X_0$的近邻
  • 对近邻$(X_1, X_2, …, X_k)$的输出变量 $(y_1, y_2, …, y_k)$，计算诸如算术平均值 （加权平均值、中位数、众数），作为新观测$X_0$输出 变量取值$y_0$的预测值

• 特点

  • k近邻不具有显式学习过程、简单、直观
  • 不需要假设$y=f(X)$函数体形式，实际上是利用训练数据集 对特征空间进行划分

局部方法

k-NN是一种“局部”方法，仅适合特征空间维度较低的情况

• 给定k的情况下，在高维空间中，需要到更远的区域寻找近邻， 局部性逐渐丧失，近似误差变大

• 如：n个观测均匀分布在超立方体中，确定k后即确定$X_0$需要 寻找的近邻个数占总观测的比率r，即近邻覆盖的体积

  • 考虑$X_0$在原点，则近邻分布的小立方体边期望长度为

    $$Ed_p(r) = r^{1/p} \\ Ed_3(0.1) = 0.1^{1/3} = 0.46 \\ Ed_10(0.1)d = 0.1^{1/10} = 0.79 \\ Ed_10(0.01) = 0.1^{1/10} = 0.63 \\$$

  • 可以看出：减少近邻比例（数量）没有帮助，还会使得近似 误差变大，只能通过增大样本量解决

• 特征选择有必要

特征选择

• 变量本身考察

  • low variance filter：剔除标准差小于阈值数值型变量
  • missing values ratio：剔除缺失值大于阈值的变量
  • 剔除众数比率大于阈值的分类型变量

• 变量与输出变量相关性角度考察

  • high correlation filter

• 对预测误差影响角度考察

  • Wrapper方法：逐个选择使错误率、均方误差下降最快变量 ，可使用Forward Feature Elimination

k-NN模型

K-NN是使用模型：实际上对应于特征空间的划分

• 模型包括3个基本要素，据此划分特征空间，确定特征空间中 每个点所属类
  • k值选择
  • 距离度量：参见data_science/ref/functions
  • 分类决策规则

k值选择

k值选择对k-NN方法有重大影响

• 较小k值：相当于使用较小邻域中训练实例进行预测

  • 复杂模型，容易发生过拟合
  • approximation error较小：只有于输入实例近、相似的 训练实例才会对预测结果有影响
  • estimation error较大：预测结果对近邻实例点非常敏感

• 较大k值：相当于使用较大邻域中训练实例进行预测

  • 简单模型
  • 估计误差较小
  • 近似误差较大：同输如实例远、相似程度差的训练实例也会 对预测结果有影响

k=1

只使用一个近邻做预测

• 找到距离$X_0$最近的近邻$X_i$，用其取值作为预测值

• 模型简单、效果较理想

  • 尤其适合特征空间维度较低、类别边界不规则情况
  • 只根据单个近邻预测，预测结果受近邻差异影响极大，预测 波动（方差）大，稳健性低

• 预测错误的概率不高于普通贝叶斯方法的两倍

  $$\begin{align*} P_e & = (1-p(y=1|X=X_0))P(y=1|X=X_0) + (1-p(y=0|X=X_0))P(y=0|X=X_0) \\ & = 2P(y=1|X=X_0)(1-P(y=1|X=X_0)) \\ & \leq 2(1-P(y=1|X=X_0)) \\ \end{align*}$$

  • $P(y=1|X=X_0)$：普通贝叶斯方法做分类预测，预测结果 为1的概率
  • 1-NN方法犯错的概率就是$X_0$、$X_i$二者实际值不同的 概率？？？？

k=N

使用训练样本整体做预测

• 无论输入实例，预测结果完全相同

  • 对分类预测，预测结果为“众数”
  • 对回归预测，预测结果为“平均数”

• 模型过于简单、效果不好

  • 忽略训练实例中大量信息
  • “稳健性”极好：预测值基本不受近邻影响，无波动

决策规则

分类决策规则

Majority Voting Rule

多数表决规则：等价于经验风险最小化

• 分类损失函数为0-1损失函数，分类函数为 $f: \mathcal{R^n} \rightarrow {c_1, c_2, \cdots}$

• 误分类概率$P(Y \neq f(X)) = 1 - P(Y=f(X))$

• 给定实例$x \in \mathcal{X}$的误分率为

  $$\frac 1 k \sum_{x \in N_k(x)} I(y_i \neq c_j) = 1 - \frac 1 k \sum_{x \in N_k(x)} I(y_i = c_j)$$

  • $N_k(x)$：最近邻k个实例构成集合
  • $c_j$：涵盖$N_k(x)$区域的类别
  • $I$：指示函数

• 为使误分率（经验风险）最小，应选择众数

• 经验风险的构造中，前提是近邻被认为属于相同类别$c_j$，
• 当然这个假设是合理的，因为k-NN方法就是认为近邻类别相同， 并使用近邻信息预测
• $c_j$的选择、选择方法是模型选择的一部分，不同的$c_j$会 有不同的经验风险

数值决策规则

算法

• 实现k近邻法时，主要问题是对训练数据进行快速k近邻搜索， 尤在特征空间维数大、训练数据量大

• 考虑使用特殊的结构存储训练数据，减少计算距离次数，提高 k近邻搜索效率

linear scan

线性扫描：最简单的实现方法

• 需要计算输入实例与每个训练实例的距离，训练集较大时计算 非常耗时

kd树最近邻搜索

• 输入：已构造kd树
• 输出：x的最近邻

• 在kd树种找出包含目标点x的叶节点的

  • 从根节点出发，比较对应坐标，递归进行访问，直到叶节点 为止

  • 目标点在训练样本中不存在，必然能够访问到叶节点

• 以此叶节点为“当前最近点”

  • 目标点在此叶节点中点所在的区域内，且区域内只有该 叶节点中点

• 回溯，并在每个节点上检查

  • 如果当前节点保存实例点比当前最近点距离目标的更近， 更新该实例点为“当前最近点”

  • 检查该节点另一子区域是否可能具有更近距离的点

    • 即其是否同以目标点为圆心、当前最短距离为半径圆 相交
    • 只需要比较目标点和相应坐标轴距离和最短距离即可

  • 若二者相交，则将目标节点视为属于该子区域中点， 进行最近邻搜索，递归向下查找到相应叶节点，重新 开始回退

  • 若二者不相交，则继续回退

• 退回到根节点时，搜索结束，最后“当前最近点”即为最近邻点

• 这里涉及到回溯过程中，另一侧子域是否访问过问题，可以通过 标记、比较相应轴坐标等方式判断
• k>1的情况类似，不过检测时使用最远近邻，新近邻需要和所有 原近邻依次比较

加权k-NN

变量重要性

计算变量的加权距离，重要变量赋予较高权重

• 变量重要性：Backward Feature Elimination得到各变量 重要性排序

  $$FI_{(i)} = e_i + \frac {1} {p} \quad \\ w_{(i)} = \frac {FI_{(i)}} {\sum_{j=1}^p FI_{(j)}}$$

  • $e_i$：剔除变量i之后的均方误差（错误率）

• 加权距离：$dw(x,y)=\sqrt {\sum{i=1}^{p} w^{(i)}(x_i - y_i)^2}$

观测相似性

目标点的k个近邻对预测结果不应有“同等力度”的影响，与$X_0$越 相似的观测，预测时重要性（权重）越大

• 权重：用函数$K(d)$将距离d转换相似性，$K(d)$应该有特性

  • 非负：$K(d) \geqslant 0, d \in R^n$
  • 0处取极大：$max K(d) = K(0)$
  • 单调减函数，距离越远，相似性越小

  • 核函数符合上述特征
  • 且研究表明除均匀核外，其他核函数预测误差差异均不明显

步骤

• 依据函数距离函数$d(Z_{(i)}, Z_0)$找到$X_0$的k+1个近邻

  • 使用第k+1个近邻距离作为最大值，调整距离在0-1之间 $$D(Z_{(i)}, Z_0) = \frac {d(Z_{(i)}, Z_0)} {d(Z_{(k+1)}, Z_0)}, \quad i=1,2,...,k$$

• 依据函数$w_i=K(d)$确定k各近邻的权重

• 预测

  • 回归预测 $$\hat{y}_0 = \frac 1 k (\sum_{i=1}^k w_iy_i)$$
  • 分类预测：多数表决原则 $$\hat{y}_0 = max_r (\sum_{i=1}^k w_iI(y_i=r)) \\ P(\hat{y}_0=r|X_0)= \frac {\sum_{i=1}^k w_iI(y_i=r)} {\sum_{i=1}^k w_i}$$

Approximate Nearest Neighbor

相似最近邻

决策树概述

结构

• 决策树分析结论、展示方式类似一棵倒置的树

• 决策树由 node、directed edge 组成

  • internal node：内部节点，表示特征、属性
  • leaf node：叶子节点，表示一个类

• 对训练数据进行分类

  • 从根节点开始，对实例某特征进行测试，根据测试结果将实例分配到其子节点，对应该特征一个取值
  • 递归地对实例进行分配，直至到达叶子节点，将实例分到叶节点地类中

• 对新数据的预测

  • 从决策树的树根到树叶搜索，确定数所的叶子节点
  • 利用叶子节点中训练数据集预测
    • 分类型：众数
    • 数值型：均值

本质

决策树：本质上是从训练数据中归纳出一组分类规则

• 与训练数据不矛盾的分类规则（即能对训练数据正确分类）可能有多个、没有，需要找到矛盾较小、泛化能力较好的
• 决策树学习也是由训练数据集估计条件概率模型，需要寻找对训练数据有很好拟合、对未知数据有很好预测的模型

分类规则集合

• 决策树可以看作是 if-then 规则的集合：体现输入、输出变量逻辑关系

• 决策树根节点到叶节点每条路径构成一条规则
• 路径上内部节点的特征对应规则的条件，叶节点对应规则结论
• 决策树的路径或其对应的 if-then 规则集合 互斥且完备，即每个实例有且仅有一条路径覆盖

条件概率分布

• 决策树可以表示定义在特征空间、类空间上的条件概率分布

• 此条件概率分布定义在特征空间的一个划分（有限）上

  • 决策树中一条路径（叶节点）对应划分中一个单元
  • 每个单元定义的概率分布就构成一个条件概率分布

• 条件概率分布由 各单元的给定条件下，各类的条件概率分布组成

  • $P(Y|X)$：$X$ 为表示特征的随机变量（取值各个单元），$Y$ 表示类的随机变量
  • 各叶节点上的条件概率往往偏向于某类，决策树分类时将属于该节点实例分为该类

特点

• 优势

  • 能有效处理分类型输入变量
  • 能够实现非线性分割
  • 模型具有可读性，分类速度块

• 问题

  • 充分生长的决策有高方差，预测不稳定
  • 剪枝可以提高预测稳健性，但是预测精度可能会下降

决策树构建

• 从所有可能决策树中选取最优决策树是NP完全问题

  • 所以实际决策树算法通常采用 启发式 算法、贪心算法，近似求解最优化问题，得到 sub-optimal 决策树
  • 从包含所有数据的根节点开始，递归的选择 当前 最优特征、分割点对训练数据进行分割，使得各子数据集有当前最好分类
  • 此样本不断分组过程对应特征空间的划分、决策树的构建

• 原则：使节点/组内观测取值异质性下降最大，从而确定

  • 最佳划分特征
  • 特征的最佳分割点

异质性衡量：划分准则

• 信息增益
• 信息增益比：避免信息增益倾向于取值较多特征
  • 若样本类别严格服从分布，则信息增益和信息增益比选择应完全相同
  • 但由于偶然性、样本数量等原因，各特征取值的样本数量往往不完全符合分布
  • 由信息增益定义可看出，各特征取值样本数量较小时，数量变动影响更大，而特征取值较多更可能出现各取值对应样本数量较小
• GINI 指数

• 研究表明，不同决策树的划分准则对泛化性能影响有限，信息增益和 GINI 指数理念分析表明，其仅在 2% 情况下有所不同

特征变量处理

• 离散值处理

  • 全分类：各类别分别独立作为分支，构建节点
  • 切分二分：将类别分为的两组
  • 是否二分：某取值作为一个分支，其余作为另一分支

• 连续值处理

  • 二分法：选择阈值，按照阈值将连续值分为两部分
    • 精确阈值选取：检查所有可能阈值点，即所有不同取值点的中间点
    • 近似阈值选取
  • 近似分裂算法：选取一组阈值，将特征划分至不同桶内，类似分类值处理
    • 等频阈值：分位数
    • 等距阈值：linespace

缺失值处理

• 缺失值处理需要解决：异质性衡量指标计算、特征缺失样本划分问题

• 异质性衡量指标计算：使用特征未缺失样本权重对指标加权（以信息增益为例）

  $$\begin{align*} g(Y|X) &= \rho * g(\tilde Y | X) \\ & = \rho * (H(\tilde D) - \sum_v^V \tilde {r_v} H(\tilde {D^v})) \\ H(\tilde V) &= - \sum_k^K \tilde {p_k} log \tilde {p_k} \\ \rho &= \frac {\sum_{x \in \tilde D} w_x} {\sum_{x \in D} w_x}\\ \tilde {p_x} &= \frac {\sum_{x \in \tilde {D_k}} w_x} {\sum_{x \in \tilde D} w_x} \\ \tilde {r_v} &= \frac {\sum_{x \in \tilde {D^v}} w_x} {\sum_{x \in \tilde D} w_x} \end{align*}$$

  • $Y, X, w_x$：样本类别，特征，样本权重
  • $D, \tilde D, \tilde {D_k}, \tilde {D^v}$：样本全集，在特征 $X$ 上无缺失样本子集，属于 $k$ 类样本子集，在特征 $X$ 上取 $v$ 样本子集

• 特征缺失样本划分

  • 划分至所有节点，其权重设置为 $\tilde {r_v} * w_x$
    • $\tilde {r_v}$ 为节点 $v$ 的权重
    • 即将特征缺失样本节点权重比例划分至各节点

剪枝

树剪枝：在决策树的学习过程中，将已生成的树进行简化的过程

• 最小化 RSS、最大化置信目标下，会导致庞大的树

  • 对训练数据拟合好
  • 模型复杂度越高
  • 推广能力差
  • 比较难理解、解释

• 通过剪枝得到恰当的树，具备一定的预测精度、复杂程度恰当，代价（误差）和复杂度之间的权衡是必要的

• Pre-pruning 预剪枝：在决策树分裂过程中，不分裂不满足分裂条件的节点，限制决策树充分生长

  • 分裂条件
    • 最大深度
    • 叶节点数量
    • 样本量最小值
    • 异质性下降阈值
  • 预剪枝基于“贪心”的禁止划分，可能降低过拟合、减少时间开销，但也可能导致欠拟合

• Post-pruning 后剪枝：决策分裂完成后，根据一定规则剪去不具备普遍性的子树

  • 比预剪枝决策保留更多分支，欠拟合风险小、泛化性能好
  • 决策树生成局部模型，决策树剪枝学习整体模型

• 剪枝方法、程度对泛化性能影响显著，尤其是数据带有噪声

自底向上剪枝

• 自底向上剪去所有无法改善评价准则的非叶节点分支（转为叶节点）

  • 最简单后剪枝策略
  • 若已使用一定预剪策略，则该策略价值不大

• 特点

  • 须在生成完全决策树之后自底向上逐个考察非叶节点，时间开销大

Minimal Cost Complexity Pruning

$$\begin{align*} C_\alpha(T) & = C(T) + \alpha |T| \\ & = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha |T| \\ & = -\sum_{t=1}^{|T|} \sum_{k=1}^K \frac {N_{t,k}} {N_t} log \frac {N_{t,k}} {N_t} + \alpha|T| \\ H_t(T) & = -\sum_k (\frac {N_{t,k}} {N_t} log \frac {N_{t,k}} {N_t}) \end{align*}$$

• $N_t$：树 $T$ 的第 $t$ 个叶子节点中样本点数量
• $N_{t,k}$：树 $T$ 的第 $t$ 个叶子节点第 $k$ 类样本点数量
• $H_t(T)$：树 $T$ 的第 $t$ 个叶子节点熵
• $C(T)$：模型对训练数据的预测误差
• $|T|$：用叶节点数量衡量的模型复杂度
• $\alpha \geq 0$：控制模型复杂度对模型总损失影响，每个叶节点带来的复杂度

• 极小化损失复杂度剪枝
  • 损失函数：正则化的极大似然函数
  • 此策略即在给定 $\alpha$ 的情况下，选择损失函数最小树

剪枝步骤

• 输入：生成算法产生的整个树 $T$，参数 $\alpha$
• 输出：修剪后的子数 $T_\alpha$

• 计算每个节点的经验熵
• 递归的从树的叶节点向上回缩
  • 若 $C\alpha(T{before}) \geq C\alpha(T{after})$，则剪枝
  • 不断回缩直到根节点，选取损失函数最小的子树 $T_\alpha$

• 算法只需要比较节点、节点子树之间损失函数之差即可，计算可以在局部进行
• 算法可以由动态规划算法实现

超参选择

• 对给定超参 $\alpha$，存在使损失函数 $C\alpha(T)$ 最小子树 $T\alpha$，且此最优子树唯一

  • $\alpha$ 偏大时，最优子树 $T_\alpha$ 偏小
  • $\alpha=0$ 时完整树最优，$\alpha \rightarrow \infty$ 时单节点树最优

• 对决策树种每个节点 $t$，通过以下策略生成 $g(t)$

  • $C_{\alpha}(T^t) = C(T^t) + \alpha|T^t|$：以 $t$ 为根节点的子树 $T^t$ 损失
  • $C_{\alpha}(t) = C(t) + \alpha$：对 $t$ 剪枝之后，仅包含单个节点 $t$ 的正则损失
  • 则 $\alpha=g(t) = \frac {C(t)-C(T^t)} {|T^t|-1}$ 时，单节点 $t$ 和子树 $T^t$ 损失相同

• 考虑以上 $g(t)$ 序列

  • $\alpha^t=g(t)$ 表示对 $T^{(0)}$ 中每个内部节点 $t$ 剪枝后，整体损失函数值减少程度
  • 可以证明，对以上 $\alpha > 0$ 序列排序，按 $0, \alpha^{(1)}, \cdots, \alpha^{(N)}$ 依次进行剪枝，对应最优子树序列 $T^{(0)}, T^{(1)},\cdots, T^{(N)}$ 嵌套
  • 通过交叉验证法在独立的验证数据集上对子树进行测试，选择最优决策树

完整剪枝+超参选择

• 输入：CART 算法生成决策树 $T^{(0)}$
• 输出：最优决策树 $T_\alpha$

• 自下而上地计算各内部节点 $t$ 对应 $C(T^t), |T^t|, g(t)$，对 $g(t)$ 升序排列得到 $\alpha^{(1)},\cdots,\alpha^{(N)}$

• 置：$k=1, \alpha=\alpha^{(k)}, T=T^{(0)}$

• 自上而下访问内部节点，若有 $g(t)=\alpha$，剪枝并计算新叶节点 $t$ 取值，得到对应最优树 $T^{(k)}$

  • 对于节点 $t$，其子树 $T^t$ 最大有效 $\alpha$ 也只是根节点对应 $g(t)$，更大没有价值
  • 自上而下剪枝避免无效剪枝

• 置：$k+=1, \alpha=\alpha^{(k)}, T=T^{(k)}$

• 若 $T$ 不是单节点树，则重复以上

• 采用交叉验证法在子树序列中选取最优子树 $T_\alpha$

• 也可从 $\alpha \leftarrow \infty$ 开始，逐渐减少，添枝 得到子树序列

决策树构建算法

• 以下是一些经典的决策树（算法），但实际实现中往往不会严格按其构建决策树

• 决策树算法常用递归描述、构建，完全决策树中止条件如下 （往往不会应用，而是以预剪枝条件作为中止条件）

  • 节点中样本属于同一类
  • 所有特征利用完毕
  • 无法找到满足划分阈值的特征、划分点

Iterative Dichotomiser 3

步骤

• 输入：训练数据集 $D$，特征集 $A$，阈值 $\epsilon$
• 输出：决策树 $T$

• 以下情况下 $T$ 为单节点树，以 $D$ 中实例数最大的类（众数） $C_k$ 作为该节点的类标记，返回 $T$

  • $D$ 中所有实例属于同一类 $C_k$
  • $A = \varnothing$

• 计算 $A$ 中各特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$

  • 若 $A_g$ 的信息增益小于阈值 $\epsilon$，则置 $T$ 为单节点树，并将 $D$ 中实例数最大的类 $C_k$ 作为节点类标记，返回 $T$
  • 否则，对 $A_g$ 每个可能值 $a_m$，将 $D$ 分割为若干非空子集 $D_i$
    • 将 $D_i$ 中实例数最多的类作为标记，构建子节点
    • 对第 $i$ 个子节点，以 $D_i$ 为训练集，以 $A-{A_g}$ 为特征集，递归的构造子树 $T_i$ 并返回

特点

• 只允许分类型特征，且每个特征只会被用于划分一次

  • 每次所有取值都会被用于建立子节点
  • ID3 树是多叉树，各个节点的分叉个数取决于使用特征

• 只有树的生成，容易产生过拟合

• 以信息增益作为划分训练数据集的特征，倾向于选择取值较多的特征进行划分

  • 理论上若特征取值严格符合分布，取值数量多寡，对信息增益没有影响
  • 由于各种误差的存在，样本不可能严格符合总体分布，取值数量较多特征，各取值对应样本数量较少，误差会使得条件经验熵倾向于偏小 （假设误差随机，可以大概证明）

• 相当于用 极大似然法 进行概率模型的选择

C4.5

C4.5算法：ID3 算法继承者

• 与 ID3 差别

  • 用信息增益比代替信息增益用于选择特征，并且也被用于 前剪枝
    • 修正 ID3 倾向于使用取值较多的特征值分裂结点
  • 兼容数值型特征，使用二分法处理

• C4.5 算法还包含 C4.5Rules 将 C4.5 决策树转化为符号规则 - 各分支被重写为规则，并进行前件合并、删减

  • 最终规则集泛化性能可能优于原决策树

Classification and Regression Tree

CART 树：可用于分类和回归的二叉树

• 特点

  • 二叉树
  • 可以用于分类、回归
    • 分类：众数代表节点，GINI 指数选择特征
    • 回归：均值代表节点，MSE 选择特征
  • 能较好的处理缺失值

• CART 回归：平方误差最小化准则

  $$f(x) = \sum_{m=1} \hat c_m I(x \in R_m)$$

  • $R_m$：空间划分出的第 $m$ 单元
  • $\hat c_m=avg(y_i|x_i \in R_m)$：第 $m$ 个单元上所有实例输出变量均值，此时平方误差最小

• CART 分类：最小化基尼指数准则

  $$Gini(D, X=a) = \frac {|D_1|} {|D|} Gini(D_1) + \frac {|D_2|} {|D|} Gini(D_2)$$

  • $D_1 = {(x,y) \in D, X = a}$
  • $D_2 = D - D_1$
  • CART 树是二叉树，对分类变量只选择是否

CART回归步骤

• 输入：训练数据集 $D$
• 输出：回归树 $f(x)$

• 选择最优切变量 $j$、切分点 $s$，即求解

  $$\arg\min_{j,s} [\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 ]$$

  • $R_1(j,s) = {x|x^{(j)} \leq s}$
  • $R_2(j,s) = {x|x^{(j)} \geq s}$
  • $c_m = avg(y_i|x_i \in R_m)$：使得区域 $R_m$ 中平方误差最小，即其中样本点 $y_i$ 均值
  • 这里通过 遍历 得到

• 对两个子区域 $R_1(j,s), R_2(j,s)$ 继续重复以上步骤，直至满足停止条件

• 将输入空间划分为 $M$ 个区域 $R_1, R_2, \cdots, R_M$，生成决策 树

  $$f(x) = \sum_{m=1} \hat c_m I(x \in R_m)$$

CART 分类步骤

• 输入：训练数据集 $D$，停止计算条件
• 输出：CART 决策树

• 选择最优切变量 $j$、切分点 $s$

  $$Gini(D, X=a) = \frac {|D_1|} {|D|} Gini(D_1) + \frac {|D_2|} {|D|} Gini(D_2)$$
  • 对每个特征 $X$，对其所有取值 $a$ 计算条件基尼指数
  • 选择条件基尼指数最小的特征、对应的切分点，将训练数据依特征分配到两个子结点中

• 对生成两个子节点递归分裂，直至满足停止条件

• 生成 CART 决策树

Chi-squared Automatic Interaction Detector

CHAID 卡方自动交叉检验法：类似 ID3 算法，但利用卡方统计确定特征变量

• https://wenku.baidu.com/view/bdd3e60abed5b9f3f90f1cd6.html
• https://sefiks.com/2020/03/18/a-step-by-step-chaid-decision-tree-example/

特点

• 通过卡方统计量选择最显著特征变量作为划分特征

  • 分类目标变量：列联分析，卡方检验
  • 数值目标变量：回归分析，F检验

• 特征预处理

  • 分类型特征变量：根据卡方统计量显著性、组数量等考虑拆分、合并分组
  • 数值型特征变量：均分分组

• 是从相关性显著角度确定特征变量

  • 对决策树分支优化明显
  • 可用特征变量与目标相关性显著显著性作为停止分裂的标准

QUEST

Quick Unbiased Efficient Statical Tree：类似 CHAID 算法，但对选择特征、划分点依据不同，仅能处理分类目标变量

特点

• 类似 CHAID，选择最显著（p 值）的特征变量作为划分特征

  • 分类特征变量：连列分析，卡方检验
  • 数值特征变量：方差分析，F检验

• 划分点选择

  • 分类特征变量：映射为 one-hot 向量后，用判别分析求解划分向量，再映射回划分取值

• 目标变量多分类

  • 为每个类别计算特征均值，使用均值聚类将其简化为二分类
  • 只需要为节点内样本的、用待划分特征计算均值

• 运行速度快于 CART 树

• http://www.mclover.cn/blog/index.php/archives/60.html
• http://www3.stat.sinica.edu.tw/statistica/oldpdf/A7n41.pdf