CART算法 CART算法(C&R算法)采用一种二分递归分割的方法,每次都把当前样 本集分割为两个子样本集,使生成的决策树的非叶结点都有两个分枝, 因此ART算法生成的决策树是结构简单的二叉树。这种算法选择分枝属 性A判别函数如下 p(A)=2piPR2IP(i)-p(is 式中和g分别是属性A的左有分枝的样本数占总体的比例,以和 分别表示属性A的左右分枝中样本子集属于类别的比例,m为分类类别数 使Φ(A)最大的属性A作为分枝的属性,因为这需要满足下面的条件 左右分枝样本的数量差不多。 左右分枝的样本集尽量不要属于同一类 CART算法也使用后剪枝。在决策树生成过程中,考虑到多展开一层就 会有更多信息被发现,CART算法运行到不能再长出分枝为止,从而得 到一棵最大的决策树。然后CART对生成的决策树进行剪枝。剪枝算法 使用独立于训练样本集的测试样本集对子树的分类错误进行计算,找出 分类错误最小的子树作为最终的分类模型。 31
31 CART算法 ◼ CART算法（C&R算法）采用一种二分递归分割的方法，每次都把当前样 本集分割为两个子样本集，使生成的决策树的非叶结点都有两个分枝， 因此CART算法生成的决策树是结构简单的二叉树。这种算法选择分枝属 性A的判别函数如下： 式中pL和pR分别是属性A的左右分枝的样本数占总体的比例，p(iL )和p(iR ) 分别表示属性A的左右分枝中样本子集属于类别i的比例，m为分类类别数。 使Ф（A）最大的属性A作为分枝的属性，因为这需要满足下面的条件： ◼ 左右分枝样本的数量差不多。 ◼ 左右分枝的样本集尽量不要属于同一类。 ◼ CART 算法也使用后剪枝。在决策树生成过程中，考虑到多展开一层就 会有更多信息被发现，CART 算法运行到不能再长出分枝为止，从而得 到一棵最大的决策树。然后CART 对生成的决策树进行剪枝。剪枝算法 使用独立于训练样本集的测试样本集对子树的分类错误进行计算，找出 分类错误最小的子树作为最终的分类模型。 1 ( ) 2 | ( ) ( ) | m L R L R i A p p p i p i = = −
QUEST算法 QUEST( quick unbiased efficient statistical tree)算法是1997 年Loh等提出的二元决策树分类方法 QUEST算法也需要确定分支属性和分割值等问题,但是以不同 的策略处理分支属性选择和分隔值的确定,运算过程比CART 算法简单有效。 QUEST算法的输入变量可以使分类型变量和数值型变量,但目 标变量(输出变量)是二值型(多值的变量要通过聚类转化为 二值的) QUEST算法中确定分支属性时,需要检验属性对目标变量的独 立性,以便确定分支属性
QUEST算法 ◼ QUEST（quick unbiased efficient statistical tree）算法是1997 年Loh等提出的二元决策树分类方法。 ◼ QUEST算法也需要确定分支属性和分割值等问题，但是以不同 的策略处理分支属性选择和分隔值的确定，运算过程比CART 算法简单有效。 ◼ QUEST算法的输入变量可以使分类型变量和数值型变量，但目 标变量（输出变量）是二值型（多值的变量要通过聚类转化为 二值的）。 ◼ QUEST算法中确定分支属性时，需要检验属性对目标变量的独 立性，以便确定分支属性。 32
样本集的划分 训练集、验证集和测试集。训练数据用来训练模型;验证集用 于在每一步测试模型;测试集用于最后评估模型。 通常数据集以80:10:10或70:20:10的比例分配
样本集的划分 ◼ 训练集、验证集和测试集。训练数据用来训练模型；验证集用 于在每一步测试模型；测试集用于最后评估模型。 ◼ 通常数据集以 80:10:10 或 70:20:10 的比例分配。 33
评估分类算法的准确性—K折交叉校验(1) 交叉验证是防止过拟合的方法 K折交叉校验(k- fold cross validation:把数据集分为k 子集,用k-1个子集为训练集,1个子集作为测试集,然 后k次交叉验证 如何提高分类算法的准确率? Tralning tolds Test fold Literation = 2- iteration Ex Et E 10 eration
34 评估分类算法的准确性——K折交叉校验（1） ◼ 交叉验证是防止过拟合的方法。 ◼ K折交叉校验（k-fold cross validation: 把数据集分为k 子集，用k-1个子集为训练集，1个子集作为测试集，然 后k次交叉验证。 ◼ 如何提高分类算法的准确率？
评估分类算法的准确性K折交叉校验(2) 嵌套交叉验证(η ested cross validatioη)算法(外循环通过k折等进行模型训练, 内循环使用交叉验证),对特定数据集进行模型选择。 嵌套交叉验证外部有一个k折交叉验证将数据分为训练集和测试集,内部交叉 验证用于选择模型算法。 Training folds Test fold Outer loo Train with of parameters I Training fod validation fold Inner loop Tune parameters
35 评估分类算法的准确性——K折交叉校验（2） ◼ 嵌套交叉验证(nested cross validation)算法（外循环通过k折等进行模型训练， 内循环使用交叉验证），对特定数据集进行模型选择。 ◼ 嵌套交叉验证外部有一个k折交叉验证将数据分为训练集和测试集，内部交叉 验证用于选择模型算法