5-nonlinear-classification-and-regression-with-decision-trees

《5-nonlinear-classification-and-regression-with-decision-trees》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、决策树——非线性回归与分类前面几章，我们介绍的模型都是广义线性模型，基本方法都是通过联接方程构建解释变量与若干响应变量的关联关系。我们用多元线性回归解决回归问题，逻辑回归解决分类问题。本章我们要讨论一种简单的非线性模型，用来解决回归与分类问题，称为决策树（decisiontree）。首先，我们将用决策树做一个广告屏蔽器，可以将网页中的广告内容屏蔽掉。之后，我们介绍集成学习（lensemblelearning）方法，通过将一系列学习方法集成使用，以取得更好的训练效果。决策树简介决策树就是做出一个树状

2、决策，就像猜猜看(TwentyQuestions)的游戏。一个玩家（先知）选择一种常见物品，但是事先不能透露给其他玩家（提问者）。提问者最多问20个问题，而先知只能回答：是，否，可能三种答案。提问者的提问会根据先知的回答越来越具体，多个问题问完后，提问者的决策就形成了一颗决策树。决策树的分支由可以猜出响应变量值的最短的解释变量序列构成。因此，在猜猜看游戏中，提问者和先知对训练集的解释变量和响应变量都很了解，但是只有先知知道测试集的响应变量值。决策树通常是重复的将训练集解释变量分割成子集的过程，如下

3、图所示。决策树的节点用方块表示，用来测试解释变量。每个节点向下的边表示不同决策产生结果。训练集的样本由决策结果分成不同的子集。例如，一个节点测试解释变量的值是否超过的限定值。如果没有超过，则进入该节点的右侧子节点；如果超过，则进入左侧子节点。子节点的运行原理和前面的一样，直到终止条件（stoppingcriterion）满足才停止。在分类任务中，包含在叶子节点中的样本响应变量的值的平均值作为响应变量的估计值。决策树建立之后，做决策的过程就是把测试样本放进决策树沿着边不断前进，直到一个叶子被触及才停

4、止前进。训练决策树我们用RossQuinlan发明的ID3（IterativeDichotomiser3，迭代二叉树3代）算法创建决策树，ID3是最早用于决策树的算法之一。假设你有一些猫和狗的分类数据。但是不允许直接观察，你只能通过动物特征的描述去做决策。对每个动物，你都会获得关于“是否喜欢玩球（playfetch）”和“是否经常发脾气”，以及它最喜欢的食物三个问题的答案。要正确分出新动物的种类，决策树需要对每条边的解释变量进行检查。每条边的下一个节点由测试结果决定。例如，第一关节点可能问“是否喜

5、欢玩球”，如果回答“YES”，则进入左节点，否则，如果回答“NO”，则进入右节点。以此类推，最后一条边会指向一个叶子节点，那就是答案。下表是14个节点的训练数据：训练数据是否喜欢玩球是否经常发脾气最喜欢的食物种类1YesNoBaconDog2NoYesDogFoodDog3NoYesCatfoodCat4NoYesBaconCat5NoNoCatfoodCat6NoYesBaconCat7NoYesCatFoodCat8NoNoDogFoodDog9NoYesCatfoodCat10YesNoDo

6、gFoodDog11YesNoBaconDog12NoNoCatfoodCat13YesYesCatfoodCat14YesYesBaconDog从数据中我们发现，猫比狗更容易发脾气。大多数狗玩球，而猫不爱玩。狗更喜欢狗粮和培根，而猫喜欢猫粮和培根。解释变量是否喜欢玩球和是否经常发脾气可以转换成二元特征值。解释变量最喜欢的食物可以转换成一个具有三个可能值的分类变量，可以用热独编码[1,0,0]，[0,1,0]，[0,0,1]表示，具体方法在第三章已经介绍过。通过上面的分析，我们可以构建模型的规则。

7、例如，一个动物如果经常发脾气且喜欢吃猫粮那就是猫，如果喜欢玩球且爱吃培根就是狗。在这么小的训练集里，想手工逐条构建规则也是非常麻烦的事情。因此，下面我们来构建决策树。问题选择和猜猜看一样，决策树也是通过对解释变量序列的逐条测试获取响应变量结果的。那么，哪个解释变量应该先测试？直觉观察会发现，解释变量集合包含所有猫或者所有狗的测试，比既包含猫又包含狗的解释变量集合的测试要好。如果子集成员种类不同，我们还是不能确定种类。我们还需要避免创建那种测试，把单独的一只猫或一条狗分离出去，这种做法类似于猜猜看问

8、题中前几轮就问非常具体的问题。更一般的情形是，这些测试极少可以分出一个样本的种类，也不能降低分类不确定性。能够降低分类不确定性的测试通常都是最好的测试。我们通常用熵（entropy）来度量信息的不确定性。以比特（bits）为计量单位，熵量化了一个变量的不确定性。熵计算公式如下所示：nH(X)=−∑P(xi)logbP(xi)i=1其中，n是样本的数量，P(xi)是第i个样本的概率。b一般取2，e或10。因为对数函数中真数小于1则对数值为0，因此，公式前面加符号使熵为正数。例如，一个