banner

机器学习系列(5):决策树——非线性回归与分类

作者: afenxi来源: afenxi时间:2017-05-14 12:36:470

摘要:本章我们要讨论一种简单的非线性模型,用来解决回归与分类问题,称为决策树(decision tree)。

决策树——非线性回归与分类

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

决策树简介

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

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

机器学习系列(5):决策树——非线性回归与分类-数据分析网

训练决策树

我们用Ross Quinlan发明的ID3(Iterative Dichotomiser 3,迭代二叉树3代)算法创建决策树,ID3是最早用于决策树的算法之一。假设你有一些猫和狗的分类数据。但是不允许直接观察,你只能通过动物特征的描述去做决策。对每个动物,你都会获得关于“是否喜欢玩球(play fetch)”和“是否经常发脾气”,以及它最喜欢的食物三个问题的答案。

要正确分出新动物的种类,决策树需要对每条边的解释变量进行检查。每条边的下一个节点由测试结果决定。例如,第一关节点可能问“是否喜欢玩球”,如果回答“YES”,则进入左节点,否则,如果回答“NO”,则进入右节点。以此类推,最后一条边会指向一个叶子节点,那就是答案。下表是14个节点的训练数据:

训练数据 是否喜欢玩球 是否经常发脾气 最喜欢的食物 种类 1 Yes No Bacon Dog 2 No Yes Dog Food Dog 3 No Yes Cat food Cat 4 No Yes Bacon Cat 5 No No Cat food Cat 6 No Yes Bacon Cat 7 No Yes Cat Food Cat 8 No No Dog Food Dog 9 No Yes Cat food Cat 10 Yes No Dog Food Dog 11 Yes No Bacon Dog 12 No No Cat food Cat 13 Yes Yes Cat food Cat 14 Yes Yes Bacon Dog

从数据中我们发现,猫比狗更容易发脾气。大多数狗玩球,而猫不爱玩。狗更喜欢狗粮和培根,而猫喜欢猫粮和培根。解释变量是否喜欢玩球和是否经常发脾气可以转换成二元特征值。解释变量最喜欢的食物可以转换成一个具有三个可能值的分类变量,可以用热独编码[1,0,0],[0,1,0],[0,0,1]表示,具体方法在第三章已经介绍过。通过上面的分析,我们可以构建模型的规则。例如,一个动物如果经常发脾气且喜欢吃猫粮那就是猫,如果喜欢玩球且爱吃培根就是狗。在这么小的训练集里,想手工逐条构建规则也是非常麻烦的事情。因此,下面我们来构建决策树。

问题选择

和猜猜看一样,决策树也是通过对解释变量序列的逐条测试获取响应变量结果的。那么,哪个解释变量应该先测试?直觉观察会发现,解释变量集合包含所有猫或者所有狗的测试,比既包含猫又包含狗的解释变量集合的测试要好。如果子集成员种类不同,我们还是不能确定种类。我们还需要避免创建那种测试,把单独的一只猫或一条狗分离出去,这种做法类似于猜猜看问题中前几轮就问非常具体的问题。更一般的情形是,这些测试极少可以分出一个样本的种类,也不能降低分类不确定性。能够降低分类不确定性的测试通常都是最好的测试。我们通常用熵(entropy)来度量信息的不确定性。

以比特(bits)为计量单位,熵量化了一个变量的不确定性。熵计算公式如下所示:

机器学习系列(5):决策树——非线性回归与分类-数据分析网

其中,n是样本的数量,P(xi)是第i个样本的概率。b一般取2,e或10。因为对数函数中真数小于1则对数值为0,因此,公式前面加符号使熵为正数。

例如,一个硬币投掷一次事件发生后一般有两种可能:正面或反面。正面朝上的概率是0.5,反面朝上的概率也是0.5。那么一个硬币投掷一次的结果这个变量的熵:

机器学习系列(5):决策树——非线性回归与分类-数据分析网

也就是说,两个等概率的可能值,正面和反面,只需要一个比特。如果是两个硬币投掷一次事件发生后一般有四种可能:正面正面,正面反面,反面反面,反面正面,每种可能的概率是0.25。其熵为:

H(X)=−(0.25log20.25×4)=2.0

如果硬币的两面相同,那么表示其可能值的变量熵为0比特,也就是说,结果是确定的,变量再也不会产生新信息量了。熵还可以用小数值表示。比如,一个不正常的硬币,其正反面的材质不同,一边重一边轻。导致其投掷后正面朝上的概率0.8,反面朝上概率0.2。那么其熵为:

H(X)=−(0.8log20.8+0.2log20.2)=0.721928095

一个不正常的硬币投掷后其结果的熵是一个小数。虽然两种结果都有可能,但是因为其中一种可能性更大,所有不确定性减小了。

下面让我们计算动物分类的熵。如果训练集数据中猫和狗数量是相等的,而且我们不知道动物的任何其他信息,那么决策的熵是1。这就像普通硬币的结果一样,非猫即狗,两种可能概率一样。但是,我们的训练数据里面,6条狗8只猫。如果我们不考虑其他信息,那么决策的熵就是:

H(X)=−(614log2614+814log2814)=0.985228136

由于猫更多,所以不确定性要小一些。现在让我们找出对分类最有用的解释变量,也就是找出对熵降幅最大的解释变量。我们可以测试是否喜欢玩球这个解释变量,把测试分成两支,喜欢玩和不喜欢玩,其结果如下图所示:

机器学习系列(5):决策树——非线性回归与分类-数据分析网

决策树通常都是用流程图显示决策过程的。最上面的方框是根节点,包括所有要测试的解释变量。在根节点里我们还没有开始测试,所以变量的熵设为0.985228136。前面我们介绍过,将解释变量是否喜欢玩球转换成二元变量,左子节点用0表示,右子节点用1表示。左子节点包括7只猫和2条狗都是不喜欢玩球的数据。计算这时解释变量的熵:

H(X)=−(79log279+29log229)=0.764204507

右子节点包括1只猫和4条狗都是喜欢玩球的数据。计算这时解释变量的熵:

H(X)=−(15log215+45log245)=0.721928095

同理,我们也可以测试解释变量是否经常发脾气。不经常发脾气为左子节点,用0表示,经常发脾气为右子节点,用1表示。

机器学习系列(5):决策树——非线性回归与分类-数据分析网

也可以对解释变量最喜欢的食物。对每一种食物都可以按照前面的思路进行测试:

机器学习系列(5):决策树——非线性回归与分类-数据分析网

信息增益

对解释变量最喜欢的食物的值是猫粮进行测试的结果是,右节点喜欢猫粮的动物中6只猫没有狗,其熵为0,而做节点2只猫6条狗,其熵为0.8113比特。我们如何评估哪一个变量最大程度的降低了分类的不确定性?子集熵的均值看起来像是一个合理的度量指标。本例中,猫粮测试这个子集熵的均值最小。直观上看,这条测试也更有效,因为我们可以用它识别出几乎是一半样本。但是,实际上这么做可能做导致决策局部最优值。例如,假设有一个子集的结果是两条狗没有猫,另一个子集的结果是4条狗8只猫。第一个子集的熵是0,而第二个子集的熵0.918。那么平均熵是0.459,但是第二个子集包含了绝大多数样本,而其熵接近1比特。

这就好像在猜猜看游戏中过早的问了太具体的问题,而我们的问题并没有消除许多可能性。因此,我们要用一种方法来合理度量熵的降幅,这个方法称为信息增益(information gain)。信息增益是父节点熵,用H(T)表示与其子节点熵的加权均值的差,计算公式如下:

机器学习系列(5):决策树——非线性回归与分类-数据分析网

其中,机器学习系列(5):决策树——非线性回归与分类-数据分析网表示解释变量a的样本x。机器学习系列(5):决策树——非线性回归与分类-数据分析网表示解释变量a的值等于v样本数量。H( grid_search = GridSearchCV(pipeline, parameters, n_jobs=-1, verbose=1, scoring=f1) grid_search.fit(X_train, y_train) print(最佳效果:%0.3f % grid_search.best_score_) print(最优参数:) best_parameters = grid_search.best_estimator_.get_params() for param_name in sorted(parameters.keys()): print(t%s: %r % (param_name, best_parameters[param_name])) predictions = grid_search.predict(X_test) print(classification_report(y_test, predictions))

[Parallel(n_jobs=-1)]: Done 1 jobs | elapsed: 3.4s [Parallel(n_jobs=-1)]: Done 50 jobs | elapsed: 24.0s [Parallel(n_jobs=-1)]: Done 200 jobs | elapsed: 1.3min [Parallel(n_jobs=-1)]: Done 318 out of 324 | elapsed: 2.0min remaining: 2.1s [Parallel(n_jobs=-1)]: Done 324 out of 324 | elapsed: 2.0min finished

Fitting 3 folds for each of 108 candidates, totalling 324 fits 最佳效果:0.914 最优参数: clf__max_depth: 50 clf__min_samples_leaf: 1 clf__min_samples_split: 1 clf__n_estimators: 20 precision recall f1-score support 0 0.98 0.99 0.99 712 1 0.94 0.90 0.92 108 avg / total 0.98 0.98 0.98 820

这个分类器发现了测试集中91%的广告,各类指标相比单一决策树都有明显改善。精确率和召回率都提升到98%。

决策树的优劣势

和前面几章介绍过的模型相比,决策树的用法更简单。首先,决策树对数据没有零均值,均方差的要求。而且可以容忍解释变量值的缺失,虽然现在的scikit-learn还没实现这一特点。决策树在训练的时候可以忽略与任务无关的解释变量。

小型决策树很容易理解,而且可以通过scikit-learn的tree模块里的export_graphviz函数生成图形,可视化效果好。决策树的分支都有着逻辑上的联接关系,很容易通过流程图画出来。另外,决策树支持多输出任务,单一决策树可以用于多类分类,不需要使用one-versus-all策略。

和前面介绍过的模型一样,决策树是一种积极学习方法(eager learner),必须在它们可以用于预测测试集任务时,先从训练集建立一个与后面的需求无关的模型,但是模型一旦建好它们可以很快的预测出结果。相反,有些算法是消极学习方法(lazy learners),像K最近邻(K-Nearest Neighbor,KNN)分类算法,它们必须等到有了训练集数据的预测需求,才会开始学习整个数据的特征。消极学习方法不需要花时间训练预测能力,但是比积极学习方法预测速度慢。

决策树比我们之前介绍的算法更容易拟合过度,因为它们可以通过精确的描述每个训练样本的特征,构建出复杂的决策树,从而忽略了一般性的真实关联关系。有一些技术可以修正决策树的拟合过度。修剪就是一个常用的策略,将决策树里一些最高的子节点和叶子节点剪掉,但是目前scikit-learn还没有相应的实现。但是,类似的效果可以通过设置决策树最大深度,或者限定只有当决策树包含的训练样本数量超过限定值时才创建子节点。DecisionTreeClassifier和DecisionTreeRegressor类都有这样的参数可以设置。另外,随机森林决策树也可以消除拟合过度。

像ID3这样的决策树学习算法是贪婪的(greedy)。它们充分的学习有时会深陷于局部最优的美梦,但是不能保证生成最优决策树。ID3通过选择解释变量序列进行测试。一个解释变量被选中是因为它比其他解释变量更大幅度的降低了不确定性。但是,有可能全局最优的决策并非局部最优。

在我们的例子中,决策树的规模并不重要,因为我们可以获取所有节点。但是,在现实应用中,决策树的规模被修剪以及其他技术限制。而决策树经过修剪后的不同形状会产生不同的效果。实际上,由信息增益和基尼不纯度启发式方法计算出的局部最优决策通常都会生成一个可行的决策树。

总结

本章我们介绍了一个非线性模型——决策树,用来解决分类和回归问题。就像猜猜看游戏一样,决策树也是由一些了问题构成一个测试实例。决策树的一个分支在遇到显示响应变量值的叶子节点时停止。我们介绍了ID3算法,用来训练决策树,通过递归分割训练集,形成子集以减低响应变量的不确定性。我们还介绍了集成学习方法,通过将一系列模型组合起来达到更好的学习效果。最后,我们用随机森林方法对图片是广告还是网页正文进行了预测。下一章,我们将介绍第一种非监督学习方法:K-Means聚类。

banner
看过还想看
可能还想看
热点推荐

永洪BI
更敏捷、更快速、更强大

申请试用
Copyright © 2012-2024开发者:北京永洪商智科技有限公司版本:V10.1
京ICP备12050607号-1京公网安备110110802011451号 隐私政策应用权限