### 机器学习代写|决策树作业代写decision tree代考|Cost-Complexity Pruning

statistics-lab™ 为您的留学生涯保驾护航 在代写决策树decision tree方面已经树立了自己的口碑, 保证靠谱, 高质且原创的统计Statistics代写服务。我们的专家在代写决策树decision tree代写方面经验极为丰富，各种代写决策树decision tree相关的作业也就用不着说。

• Statistical Inference 统计推断
• Statistical Computing 统计计算
• (Generalized) Linear Models 广义线性模型
• Statistical Machine Learning 统计机器学习
• Longitudinal Data Analysis 纵向数据分析
• Foundations of Data Science 数据科学基础

## 机器学习代写|决策树作业代写decision tree代考|Cost-Complexity Pruning

Cost-complexity pruning is the post-pruning strategy of the CART system, detailed in [12]. It consists of two steps:

1. Generate a sequence of increasingly smaller trees, beginning with $T$ and ending with the root node of $T$, by successively pruning the subtree yielding the lowest cost complexity, in a bottom-up fashion;
2. Choose the best tree among the sequence based on its relative size and accuracy (either on a pruning set, or provided by a cross-validation procedure in the training set).

The idea within step 1 is that pruned tree $T_{i+1}$ is obtained by pruning the subtrees that show the lowest increase in the apparent error (error in the training set) per pruned leaf. Since the apparent error of pruned node $t$ increases by the amount $r^{(t)}-r^{T^{(r)}}$, whereas its number of leaves decreases by $\left|\lambda_{T^{(t)}}\right|-1$ units, the following ratio measures the increase in apparent error rate per pruned leaf:
$$\alpha=\frac{r^{(r)}-r^{T^{(t)}}}{\left|\lambda_{T^{(t)}}\right|-1}$$
Therefore, $T_{i+1}$ is obtained by pruning all nodes in $T_{i}$ with the lowest value of $\alpha$. $T_{0}$ is obtained by pruning all nodes in $T$ whose $\alpha$ value is 0 . It is possible to show that each tree $T_{i}$ is associated to a distinct value $\alpha_{i}$, such that $\alpha_{i}<\alpha_{i+1}$. Building the sequence of trees in step 1 takes quadratic time with respect to the number of internal nodes.

Regarding step 2, CCP chooses the smallest tree whose error (either on the pruning set or on cross-validation) is not more than one standard error (SE) greater than the lowest error observed in the sequence of trees. This strategy is known as “1-SE” variant since the work of Esposito et al. [33], which proposes ignoring the standard error constraint, calling the strategy of selecting trees based only on accuracy of “0-SE”. It is argued that 1-SE has a tendency of overpruning trees, since its selection is based on a conservative constraint $[32,33]$.

## 机器学习代写|决策树作业代写decision tree代考|Error-Based Pruning

This strategy was proposed by Quinlan and it is implemented as the default pruning strategy of C4.5 [89]. It is an improvement over PEP, based on a far more pessimistic estimate of the expected error. Unlike PEP, EBP performs a bottom-up search, and it performs not only the replacement of non-terminal nodes by leaves but also the grafting $g^{4}$ of subtree $T^{(t)}$ onto the place of parent $t$. Grafting is exemplified in Fig. $2.2$.
Since grafting is potentially a time-consuming task, only the child subtree $T^{\left(t^{\prime}\right)}$ of $t$ with the greatest number of instances is considered to be grafted onto the place of $t$.

For deciding whether to replace a non-terminal node by a leaf (subtree replacement), to graft a subtree onto the place of its parent (subtree raising) or not to prune at all, a pessimistic estimate of the expected error is calculated by using an upper confidence bound. Assuming that errors in the training set are binomially distributed with a given probability $p$ in $N_{x}^{(t)}$ trials, it is possible to compute the exact value of the upper confidence bound as the value of $p$ for which a binomially distributed random variable $P$ shows $E^{(t)}$ successes in $N_{x}^{(t)}$ trials with probability $C F$. In other words, given a particular confidence $C F$ (C4.5 default value is $C F=25 \%$ ), we can find the upper bound of the expected error $\left(E E_{U B}\right)$ as follows:
$$E E_{U B}=\frac{f+\frac{z^{2}}{2 N_{x}}+z \sqrt{\frac{f}{N_{x}}-\frac{f^{2}}{N_{x}}+\frac{z^{2}}{4 N_{x}^{2}}}}{1+\frac{z^{2}}{N_{x}}}$$
where $f=E^{(t)} / N_{x}$ and $z$ is the number of standard deviations corresponding to the confidence $C F$ (e.g., for $C F=25 \%, z=0.69$ ).

In order to calculate the expected error of node $t\left(E E^{(t)}\right)$, one must simply compute $N_{x}^{(t)} \times E E_{U B}$. For evaluating a subtree $T^{(t)}$, one must sum the expected error of every leaf of that subtree, i.e., $\sum_{s \in \lambda_{T}(t)} E E^{(s)}$. Hence, given a non-terminal node $t$, it is possible to decide whether one should perform subtree replacement (when condition $E E^{(t)} \leq E E^{T^{(t)}}$ holds), subtree raising (when conditions $\exists j \in \zeta_{t}, E E^{(j)}<E E^{(t)} \wedge$ $\forall i \in \zeta_{I}, N_{x}^{(i)}<N_{x}^{(j)}$ hold), or not to prune $t$ otherwise.

An advantage of EBP is the new grafting operation that allows pruning useless branches without ignoring interesting lower branches (an elegant solution to the horizon effect problem). A drawback of the method is the parameter $C F$, even though it represents a confidence level. Smaller values of $C F$ result in more pruning.

## 机器学习代写|决策树作业代写decision tree代考|Empirical Evaluations

Some studies in the literature performed empirical analyses for evaluating pruning strategies. For instance, Quinlan [94] compared four methods of tree pruning (three of them presented in the previous sections-REP, PEP and CCP 1-SE). He argued that those methods in which a pruning set is needed (REP and CCP) did not perform noticeably better than the other methods, and thus their requirement for additional data is a weakness.

Mingers [71] compared five pruning methods, all of them presented in the previous sections (CCP, CVP, MEP, REP and PEP), and related them to different splitting measures. He states that pruning can improve the accuracy of induced decision trees by up to $25 \%$ in domains with noise and residual variation. In addition, he highlights the following findings: (i) MEP (the original version by Niblett and Bratko [82]) is the least accurate method due to its sensitivity to the number of classes in the data; (ii) PEP is the most “crude” strategy, though the fastest one-due to some bad results,

it should be used with caution; (iii) CVP, CCP and REP performed well, providing consistently low error-rates for all data sets used; and (iv) there is no evidence of an interaction between the splitting measure and the pruning method used for inducing a decision tree.

Buntine [16], in his PhD thesis, also reports experiments on pruning methods (PEP, MEP, CCP 0-SE and 1-SE for both pruning set and cross-validation). Some of his findings were: (i) CCP $0-S E$ versions were marginally superior than the $1-S E$ versions; (ii) CCP 1-SE versions were superior in data sets with little apparent structure, where more severe pruning was inherently better; (iii) CCP 0-SE with crossvalidation was marginally better than the other methods, though not in all data sets; and (iv) PEP performed reasonably well in all data sets, and was significantly superior in well-structured data sets (mushroom, glass and LED, all from UCI [36]);

Esposito et al. [32] compare the six post-pruning methods presented in the previous sections within an extended C4.5 system. Their findings were the following: (i) MEP, CVP, and EBP tend to underprune, whereas 1-SE (both cross-validation and pruning set versions) and REP have a propensity for overpruning; (ii) using a pruning-set is not usually a good option; (iii) PEP and EBP behave similarly, despite the difference in their formulation; (iv) pruning does not generally decrease the accuracy of a decision tree (only one of the domains tested was deemed as “pruning-averse”); and (v) data sets not prone to pruning are usually the ones with the highest base error whereas data sets with a low base error tend to benefit of any pruning strategy.

For a comprehensive survey of strategies for simplifying decision trees, please refer to [13]. For more details on post-pruning techniques in decision trees for regression, we recommend $[12,54,85,97,113-115]$.

## 机器学习代写|决策树作业代写decision tree代考|Cost-Complexity Pruning

1. 生成一系列越来越小的树，从吨并以根节点结束吨，通过以自下而上的方式连续修剪产生最低成本复杂度的子树；
2. 根据其相对大小和准确性（在修剪集上，或由训练集中的交叉验证程序提供）在序列中选择最佳树。

## 机器学习代写|决策树作业代写decision tree代考|Error-Based Pruning

EBP 的一个优点是新的嫁接操作，它允许修剪无用的分支而不会忽略有趣的较低分支（对地平线效应问题的优雅解决方案）。该方法的一个缺点是参数CF，即使它代表一个置信水平。较小的值CF导致更多的修剪。

## 机器学习代写|决策树作业代写decision tree代考|Empirical Evaluations

Mingers [71] 比较了五种修剪方法，所有这些方法都在前面的章节中介绍过（CCP、CVP、MEP、REP 和 PEP），并将它们与不同的分裂措施相关联。他指出，剪枝可以将诱导决策树的准确性提高多达25%在具有噪声和残余变化的域中。此外，他强调了以下发现：（i）MEP（Niblett 和 Bratko [82] 的原始版本）是最不准确的方法，因为它对数据中的类数很敏感；(ii) PEP 是最“粗鲁”的策略，虽然是最快的策略——由于一些糟糕的结果，

Buntine [16] 在他的博士论文中还报告了剪枝方法的实验（PEP、MEP、CCP 0-SE 和 1-SE 用于剪枝集和交叉验证）。他的一些发现是：(i) CCP0−小号和版本略优于1−小号和版本；(ii) CCP 1-SE 版本在几乎没有明显结构的数据集中表现出色，其中更严格的修剪本质上更好；(iii) 具有交叉验证的 CCP 0-SE 略好于其他方法，尽管并非在所有数据集中；(iv) PEP 在所有数据集中表现相当不错，并且在结构良好的数据集中（蘑菇、玻璃和 LED，均来自 UCI [36]）显着优于；

## 有限元方法代写

tatistics-lab作为专业的留学生服务机构，多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于Essay代写，Assignment代写，Dissertation代写，Report代写，小组作业代写，Proposal代写，Paper代写，Presentation代写，计算机作业代写，论文修改和润色，网课代做，exam代考等等。写作范围涵盖高中，本科，研究生等海外留学全阶段，辐射金融，经济学，会计学，审计学，管理学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。

## MATLAB代写

MATLAB 是一种用于技术计算的高性能语言。它将计算、可视化和编程集成在一个易于使用的环境中，其中问题和解决方案以熟悉的数学符号表示。典型用途包括：数学和计算算法开发建模、仿真和原型制作数据分析、探索和可视化科学和工程图形应用程序开发，包括图形用户界面构建MATLAB 是一个交互式系统，其基本数据元素是一个不需要维度的数组。这使您可以解决许多技术计算问题，尤其是那些具有矩阵和向量公式的问题，而只需用 C 或 Fortran 等标量非交互式语言编写程序所需的时间的一小部分。MATLAB 名称代表矩阵实验室。MATLAB 最初的编写目的是提供对由 LINPACK 和 EISPACK 项目开发的矩阵软件的轻松访问，这两个项目共同代表了矩阵计算软件的最新技术。MATLAB 经过多年的发展，得到了许多用户的投入。在大学环境中，它是数学、工程和科学入门和高级课程的标准教学工具。在工业领域，MATLAB 是高效研究、开发和分析的首选工具。MATLAB 具有一系列称为工具箱的特定于应用程序的解决方案。对于大多数 MATLAB 用户来说非常重要，工具箱允许您学习应用专业技术。工具箱是 MATLAB 函数（M 文件）的综合集合，可扩展 MATLAB 环境以解决特定类别的问题。可用工具箱的领域包括信号处理、控制系统、神经网络、模糊逻辑、小波、仿真等。