常见面试算法:决策树、随机森林和AdaBoost

  • 2019 年 10 月 28 日
  • 筆記

决策树 概述

决策树(Decision Tree)算法是一种基本的分类与回归方法,是最经常使用的数据挖掘算法之一。我们这章节只讨论用于分类的决策树。

决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。它可以认为是 if-then 规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。

决策树学习通常包括 3 个步骤:特征选择、决策树的生成和决策树的修剪。

决策树 场景

一个叫做 "二十个问题" 的游戏,游戏的规则很简单:参与游戏的一方在脑海中想某个事物,其他参与者向他提问,只允许提 20 个问题,问题的答案也只能用对或错回答。问问题的人通过推断分解,逐步缩小待猜测事物的范围,最后得到游戏的答案。

一个邮件分类系统,大致工作流程如下:

首先检测发送邮件域名地址。如果地址为 myEmployer.com, 则将其放在分类  "无聊时需要阅读的邮件"中。  如果邮件不是来自这个域名,则检测邮件内容里是否包含单词 "曲棍球" ,  如果包含则将邮件归类到 "需要及时处理的朋友邮件",  如果不包含则将邮件归类到 "无需阅读的垃圾邮件" 。

决策树的定义:

分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点(node)和有向边(directed edge)组成。结点有两种类型:内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或属性(features),叶结点表示一个类(labels)。

用决策树对需要测试的实例进行分类:从根节点开始,对实例的某一特征进行测试,根据测试结果,将实例分配到其子结点;这时,每一个子结点对应着该特征的一个取值。如此递归地对实例进行测试并分配,直至达到叶结点。最后将实例分配到叶结点的类中。

决策树 原理

决策树 须知概念

信息熵 & 信息增益

熵(entropy): 熵指的是体系的混乱的程度,在不同的学科中也有引申出的更为具体的定义,是各领域十分重要的参量。

信息论(information theory)中的熵(香农熵): 是一种信息的度量方式,表示信息的混乱程度,也就是说:信息越有序,信息熵越低。例如:火柴有序放在火柴盒里,熵值很低,相反,熵值很高。

信息增益(information gain): 在划分数据集前后信息发生的变化称为信息增益。

决策树 工作原理

如何构造一个决策树? 我们使用 createBranch() 方法,如下所示:

决策树 开发流程

收集数据:可以使用任何方法。

准备数据:树构造算法 (这里使用的是ID3算法,只适用于标称型数据,这就是为什么数值型数据必须离散化。 还有其他的树构造算法,比如CART)

分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期。

训练算法:构造树的数据结构。

测试算法:使用训练好的树计算错误率。

使用算法:此步骤可以适用于任何监督学习任务,而使用决策树可以更好地理解数据的内在含义。

决策树 算法特点

优点:计算复杂度不高,输出结果易于理解,数据有缺失也能跑,可以处理不相关特征。

缺点:容易过拟合。

适用数据类型:数值型和标称型。

决策树 项目案例

项目案例1: 判定鱼类和非鱼类

项目概述

根据以下 2 个特征,将动物分成两类:鱼类和非鱼类。

特征:

  1. 不浮出水面是否可以生存
  2. 是否有脚蹼

开发流程

完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/3.DecisionTree/DecisionTree.py

收集数据:可以使用任何方法

准备数据:树构造算法(这里使用的是ID3算法,因此数值型数据必须离散化。)

分析数据:可以使用任何方法,构造树完成之后,我们可以将树画出来。

训练算法:构造树结构

测试算法:使用习得的决策树执行分类

使用算法:此步骤可以适用于任何监督学习任务,而使用决策树可以更好地理解数据的内在含义

收集数据:可以使用任何方法

我们利用 createDataSet() 函数输入数据

使用算法:此步骤可以适用于任何监督学习任务,而使用决策树可以更好地理解数据的内在含义。

项目案例2: 使用决策树预测隐形眼镜类型

完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/3.DecisionTree/DecisionTree.py

项目概述

隐形眼镜类型包括硬材质、软材质以及不适合佩戴隐形眼镜。我们需要使用决策树预测患者需要佩戴的隐形眼镜类型。

开发流程

  1. 收集数据: 提供的文本文件。
  2. 解析数据: 解析 tab 键分隔的数据行
  3. 分析数据: 快速检查数据,确保正确地解析数据内容,使用 createPlot() 函数绘制最终的树形图。
  4. 训练算法: 使用 createTree() 函数。
  5. 测试算法: 编写测试函数验证决策树可以正确分类给定的数据实例。
  6. 使用算法: 存储树的数据结构,以便下次使用时无需重新构造树。

收集数据:提供的文本文件

文本文件数据格式如下:

解析数据:解析 tab 键分隔的数据行

lecses = [inst.strip().split('t') for inst in fr.readlines()]  lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']

分析数据:快速检查数据,确保正确地解析数据内容,使用 createPlot() 函数绘制最终的树形图。

>>> treePlotter.createPlot(lensesTree)

训练算法:使用 createTree() 函数

https://github.com/apachecn/AiLearning/blob/master/docs/3.%E5%86%B3%E7%AD%96%E6%A0%91.md

集成方法-随机森林和AdaBoost

集成方法: ensemble method(元算法: meta algorithm) 概述

  • 概念:是对其他算法进行组合的一种形式。
  • 通俗来说: 当做重要决定时,大家可能都会考虑吸取多个专家而不只是一个人的意见。 机器学习处理问题时又何尝不是如此? 这就是集成方法背后的思想。
  • 集成方法:
    1. 投票选举(bagging: 自举汇聚法 bootstrap aggregating): 是基于数据随机重抽样分类器构造的方法
    2. 再学习(boosting): 是基于所有分类器的加权求和的方法

集成方法 场景

目前 bagging 方法最流行的版本是: 随机森林(random forest) 选男友:美女选择择偶对象的时候,会问几个闺蜜的建议,最后选择一个综合得分最高的一个作为男朋友

目前 boosting 方法最流行的版本是: AdaBoost 追女友:3个帅哥追同一个美女,第1个帅哥失败->(传授经验:姓名、家庭情况) 第2个帅哥失败->(传授经验:兴趣爱好、性格特点) 第3个帅哥成功

bagging 和 boosting 区别是什么?

  1. bagging 是一种与 boosting 很类似的技术, 所使用的多个分类器的类型(数据量和特征量)都是一致的。
  2. bagging 是由不同的分类器(1.数据随机化 2.特征随机化)经过训练,综合得出的出现最多分类结果;boosting 是通过调整已有分类器错分的那些数据来获得新的分类器,得出目前最优的结果。
  3. bagging 中的分类器权重是相等的;而 boosting 中的分类器加权求和,所以权重并不相等,每个权重代表的是其对应分类器在上一轮迭代中的成功度。

随机森林

随机森林 概述

  • 随机森林指的是利用多棵树对样本进行训练并预测的一种分类器。
  • 决策树相当于一个大师,通过自己在数据集中学到的知识用于新数据的分类。但是俗话说得好,一个诸葛亮,玩不过三个臭皮匠。随机森林就是希望构建多个臭皮匠,希望最终的分类效果能够超过单个大师的一种算法。

随机森林 原理

那随机森林具体如何构建呢? 有两个方面:

  1. 数据的随机性化
  2. 待选特征的随机化

使得随机森林中的决策树都能够彼此不同,提升系统的多样性,从而提升分类性能。

数据的随机化:使得随机森林中的决策树更普遍化一点,适合更多的场景。

(有放回的准确率在:70% 以上, 无放回的准确率在:60% 以上)

  1. 采取有放回的抽样方式 构造子数据集,保证不同子集之间的数量级一样(不同子集/同一子集 之间的元素可以重复)
  2. 利用子数据集来构建子决策树,将这个数据放到每个子决策树中,每个子决策树输出一个结果。
  3. 然后统计子决策树的投票结果,得到最终的分类 就是 随机森林的输出结果。
  4. 如下图,假设随机森林中有3棵子决策树,2棵子树的分类结果是A类,1棵子树的分类结果是B类,那么随机森林的分类结果就是A类。

待选特征的随机化

  1. 子树从所有的待选特征中随机选取一定的特征。
  2. 在选取的特征中选取最优的特征。

下图中,蓝色的方块代表所有可以被选择的特征,也就是目前的待选特征;黄色的方块是分裂特征。

左边是一棵决策树的特征选取过程,通过在待选特征中选取最优的分裂特征(别忘了前文提到的ID3算法,C4.5算法,CART算法等等),完成分裂。 右边是一个随机森林中的子树的特征选取过程。

随机森林 开发流程

收集数据:任何方法  准备数据:转换样本集  分析数据:任何方法  训练算法:通过数据随机化和特征随机化,进行多实例的分类评估  测试算法:计算错误率  使用算法:输入样本数据,然后运行 随机森林 算法判断输入数据分类属于哪个分类,  最后对计算出的分类执行后续处理

随机森林 算法特点

优点:几乎不需要输入准备、可实现隐式特征选择、训练速度非常快、其他模型很难超越、  很难建立一个糟糕的随机森林模型、大量优秀、免费以及开源的实现。  缺点:劣势在于模型大小、是个很难去解释的黑盒子。  适用数据范围:数值型和标称型

项目案例: 声纳信号分类

项目概述

这是 Gorman 和 Sejnowski 在研究使用神经网络的声纳信号分类中使用的数据集。任务是训练一个模型来区分声纳信号。

开发流程

收集数据:提供的文本文件  准备数据:转换样本集  分析数据:手工检查数据  训练算法:在数据上,利用 random_forest() 函数进行优化评估,返回模型的综合分类结果  测试算法:在采用自定义 n_folds 份随机重抽样 进行测试评估,得出综合的预测评分  使用算法:若你感兴趣可以构建完整的应用程序,从案例进行封装,也可以参考我们的代码

收集数据:提供的文本文件

样本数据:sonar-all-data.txt

使用算法:若你感兴趣可以构建完整的应用程序,从案例进行封装,也可以参考我们的代码

完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/7.RandomForest/randomForest.py

AdaBoost

AdaBoost (adaptive boosting: 自适应 boosting) 概述

能否使用弱分类器和多个实例来构建一个强分类器? 这是一个非常有趣的理论问题。

AdaBoost 原理

AdaBoost 工作原理

AdaBoost 开发流程

收集数据:可以使用任意方法  准备数据:依赖于所使用的弱分类器类型,本章使用的是单层决策树,这种分类器可以处理任  何数据类型。     当然也可以使用任意分类器作为弱分类器,第2章到第6章中的任一分类器都可以充  当弱分类器。     作为弱分类器,简单分类器的效果更好。  分析数据:可以使用任意方法。  训练算法:AdaBoost 的大部分时间都用在训练上,分类器将多次在同一数据集上  训练弱分类器。  测试算法:计算分类的错误率。  使用算法:通SVM一样,AdaBoost 预测两个类别中的一个。如果想把它应用到多个类别的  场景,那么就要像多类 SVM 中的做法一样对 AdaBoost 进行修改。

AdaBoost 算法特点

* 优点:泛化(由具体的、个别的扩大为一般的)错误率低,易编码,可以应用在大部分分  类器上,无参数调节。  * 缺点:对离群点敏感。  * 适用数据类型:数值型和标称型数据。

项目案例: 马疝病的预测

项目流程图

基于单层决策树构建弱分类器

  • 单层决策树(decision stump, 也称决策树桩)是一种简单的决策树。

项目概述

预测患有疝气病的马的存活问题,这里的数据包括368个样本和28个特征,疝气病是描述马胃肠痛的术语,然而,这种病并不一定源自马的胃肠问题,其他问题也可能引发疝气病,该数据集中包含了医院检测马疝气病的一些指标,有的指标比较主观,有的指标难以测量,例如马的疼痛级别。另外,除了部分指标主观和难以测量之外,该数据还存在一个问题,数据集中有30%的值是缺失的。

完整代码地址: https://github.com/apachecn/MachineLearning/blob/master/src/py2.x/ML/7.AdaBoost/adaboost.py

开发流程

收集数据:提供的文本文件  准备数据:确保类别标签是+1和-1,而非1和0  分析数据:统计分析  训练算法:在数据上,利用 adaBoostTrainDS() 函数训练出一系列的分类器  测试算法:我们拥有两个数据集。在不采用随机抽样的方法下,我们就会对 AdaBoost 和  Logistic 回归的结果进行完全对等的比较  使用算法:观察该例子上的错误率。不过,也可以构建一个 Web 网站,让驯马师输入马的  症状然后预测马是否会死去

收集数据:提供的文本文件

训练数据:horseColicTraining.txt 测试数据:horseColicTest.txt

分析数据:统计分析

过拟合(overfitting, 也称为过学习)

  • 发现测试错误率在达到一个最小值之后有开始上升,这种现象称为过拟合。

通俗来说:就是把一些噪音数据也拟合进去的,如下图。

训练算法:在数据上,利用 adaBoostTrainDS() 函数训练出一系列的分类器。

要点补充

非均衡现象:

在分类器训练时,正例数目和反例数目不相等(相差很大)。或者发生在正负例分类错误的成本不同的时候。

  • 判断马是否能继续生存(不可误杀)
  • 过滤垃圾邮件(不可漏判)
  • 不能放过传染病的人
  • 不能随便认为别人犯罪

我们有多种方法来处理这个问题: 具体可参考此链接

8 Tactics to Combat Imbalanced Classes in Your Machine Learning Dataset

再结合书中的方法,可以归为八大类:

1.能否收集到更多的数据?

这个措施往往被人们所忽略,被认为很蠢。但是更大的数据集更能体现样本的分布,多样性。

2.尝试使用其他的评价指标

Accuracy 或者error rate 不能用于非均衡的数据集。这会误导人。这时候可以尝试其他的评价指标。

Confusion Matrix 混淆矩阵:使用一个表格对分类器所预测的类别与其真实的类别的样本统计,分别为:TP、FN、FP与TN。

Precision:精确度

Recall: 召回率

F1 Score (or F-Score): 精确度和召回率的加权平均

或者使用

Kappa (Cohen's kappa)

ROC Curves

ROC 评估方法

  • ROC 曲线: 最佳的分类器应该尽可能地处于左上角
  • 对不同的 ROC 曲线进行比较的一个指标是曲线下的面积(Area Unser the Curve, AUC).
  • AUC 给出的是分类器的平均性能值,当然它并不能完全代替对整条曲线的观察。
  • 一个完美分类器的 AUC 为1,而随机猜测的 AUC 则为0.5。

3.尝试对样本重抽样

欠抽样(undersampling)或者过抽样(oversampling)

- 欠抽样: 意味着删除样例  - 过抽样: 意味着复制样例(重复使用)

对大类进行欠抽样

对小类进行过抽样

或者结合上述两种方法进行抽样

一些经验法则:

  • 考虑样本(超过1万、十万甚至更多)进行欠采样,即删除部分样本;
  • 考虑样本(不足1为甚至更少)进行过采样,即添加部分样本的副本;
  • 考虑尝试随机采样与非随机采样两种采样方法;
  • 考虑对各类别尝试不同的采样比例,不一定是1:1
  • 考虑同时使用过采样与欠采样

4.尝试产生人工生成的样本

一种简单的方法就是随机抽样小类样本的属性(特征)来组成新的样本即属性值随机采样。你可以根据经验进行抽样,可以使用其他方式比如朴素贝叶斯方法假设各属性之间互相独立进行采样,这样便可得到更多的数据,但是无法保证属性之间的非线性关系。

当然也有系统性的算法。最常用的SMOTE(Synthetic Minority Over-Sampling Technique)。 顾名思义,这是一种over sampling(过抽样)的方式。它是产生人为的样本而不是制造样本副本。这个算法是选取2个或者2个以上相似的样本(根据距离度量 distance measure),然后每次选择其中一个样本,并随机选择一定数量的邻居样本对选择的那个样本的一个属性增加噪声(每次只处理一个属性)。这样就构造了更多的新生数据。具体可以参见原始论文。

http://www.jair.org/papers/paper953.html

python实现可以查阅UnbalancedDataset

https://github.com/scikit-learn-contrib/imbalanced-learn

5.尝试不同的算法

强烈建议不要在每个问题上使用你最喜欢的算法。虽然这个算法带来较好的效果,但是它也会蒙蔽你观察数据内蕴含的其他的信息。至少你得在同一个问题上试试各种算法。具体可以参阅Why you should be Spot-Checking Algorithms on your Machine Learning Problems

Why you should be Spot-Checking Algorithms on your Machine Learning Problems

比如说,决策树经常在非均衡数据集上表现良好。创建分类树时候使用基于类变量的划分规则强制使类别表达出来。如果有疑惑,可以尝试一些流行的决策树,比如, C4.5, C5.0, CART 和 Random Forrest。

6.尝试使用惩罚的模型

你可以使用同种算法但是以不同的角度对待这个问题。

惩罚的模型就是对于不同的分类错误给予不同的代价(惩罚)。比如对于错分的小类给予更高的代价。这种方式会使模型偏差,更加关注小类。

通常来说这种代价/惩罚或者比重在学习中算法是特定的。比如使用代价函数来实现:

代价函数

  • 基于代价函数的分类器决策控制:TP*(-5)+FN*1+FP*50+TN*0

这种方式叫做 cost sensitive learning,Weka 中相应的框架可以实现叫CostSensitiveClassifier

http://weka.sourceforge.net/doc.dev/weka/classifiers/meta/CostSensitiveClassifier.html

如果当你只能使用特定算法而且无法重抽样,或者模型效果不行,这时候使用惩罚(penalization)是可行的方法。这提供另外一种方式来“平衡”类别。但是设定惩罚函数/代价函数是比较复杂的。最好还是尝试不同的代价函数组合来得到最优效果。

7.尝试使用不同的角度

其实有很多研究关于非均衡数据。他们有自己的算法,度量,术语。

从它们的角度看看你的问题,思考你的问题,说不定会有新的想法。

两个领域您可以考虑: anomaly detection(异常值检测) 和 change detection(变化趋势检测)。

Anomaly dectection 就是检测稀有事件。 比如通过机器震动来识别机器谷中或者根据一系列系统的调用来检测恶意操作。与常规操作相比,这些事件是罕见的。

把小类想成异常类这种转变可能会帮助你想到新办法来分类数据样本。

change detection 变化趋势检测类似于异常值检测。但是他不是寻找异常值而是寻找变化或区别。比如通过使用模式或者银行交易记录来观察用户行为转变。

这些两种转变可能会给你新的方式去思考你的问题和新的技术去尝试。

8.尝试去创新

仔细思考你的问题然后想想看如何将这问题细分为几个更切实际的小问题。

比如:

将你的大类分解成多个较小的类;

使用One Class分类器(看待成异常点检测);

对数据集进行抽样成多个数据集,使用集成方式,训练多个分类器,然后联合这些分类器进行分类;

这只是一个例子。更多的可以参阅In classification, how do you handle an unbalanced training set? 和Classification when 80% of my training set is of one class

http://www.quora.com/In-classification-how-do-you-handle-an-unbalanced-training-set

https://github.com/apachecn/AiLearning/blob/master/docs/7.%E9%9B%86%E6%88%90%E6%96%B9%E6%B3%95-%E9%9A%8F%E6%9C%BA%E6%A3%AE%E6%9E%97%E5%92%8CAdaBoost.md