机器学习经典算法详解及Python实现,机器学习

作者: 冶金矿产  发布:2019-10-24

本文对决策树算法进行简单的总结和梳理,并对著名的决策树算法ID3(Iterative Dichotomiser 迭代二分器)进行实现,实现采用Python语言,一句老梗,“人生苦短,我用Python”,Python确实能够省很多语言方面的事,从而可以让我们专注于问题和解决问题的逻辑。

4.1 决策树(Decision Tree)的定义:

(一)认识决策树

根据不同的数据,我实现了三个版本的ID3算法,复杂度逐步提升:

是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干,故称决策树。在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。Entropy

系统的凌乱程度,使用算法ID3,C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

4.2 划分选择的要点:

4.2.1 信息增益:是特征选择中的一个重要指标,它定义为一个特征能够为分类系统带来多少信息,带来的信息越多,该特征越重要。

图片 1

4.2.2熵:那么如何衡量一个特征为分类系统带来的信息多少呢:对一个特征而言,系统有它和没它时信息量将发生变化,而前后信息量的差值就是这个特征给系统带来的信息量。所谓信息量,其实就是熵。信息熵可以衡量事物的不确定性,这个事物不确定性越大,信息熵也越大

【补充】知乎上有一个对信息熵的解释比较好https://www.zhihu.com/question/22178202/answer/49929786一个事件的信息量就是这个事件发生的概率的负对数

【信息增益熵之间关系】信息增益=熵-条件熵https://www.zhihu.com/question/22104055

【信息增益信息增益率之间关系】一些变种决策树的算法对划分的要点略有不同,如ID3使用信息增益,c4.5使用信息增益比,他们的之间的区别,如下:

https://www.zhihu.com/question/22928442

andy:离散数据使用信息增益ID3与C4.5的区别并不大。但如果面对连续的数据(如体重、身高、年龄、距离等),或者每列数据没有明显的类别之分(最极端的例子的该列所有数据都独一无二),在这种情况下,信息增益率减轻了划分行为本身的影响

4.2.3 基尼指数

Gini是从数据集随机抽两个样本,不一致的概率。如果Gini越小,则数据集纯度越高。

4.3 剪枝处理:解决 “过拟合”的主要手段

有关“过拟合”(数据集匹配的太好)和“欠拟合”(数据集匹配的不好)之间的关系:http://www.cnblogs.com/nxld/p/6058782.html

分为: 预剪枝和 后剪枝

4.3.1 预剪枝

解释剪枝前,需要解释什么是泛化

泛化即是,机器学习模型学习到的概念在它处于学习的过程中时模型没有遇见过的样本时候的表现。

好的机器学习模型的模板目标是从问题领域内的训练数据到任意的数据上泛化性能良好。这让我们可以在未来对模型没有见过的数据进行预测。

预剪枝:树还没有训练成,但是用判断节点,要不要继续划分。这样的操作会提高分类的准度,但是会带来欠拟合的风险。

4.3.1 后剪枝

后剪枝,是树已经形成了,然后剪枝的策略和预剪枝差不多,也是一个个去尝试,在西瓜的例子中,就是判断这个节点是否替换后,是否好瓜还是坏瓜。比较他们剪枝前和剪枝后的精度。从书上的图可以看出,后剪枝分支更多,欠拟合的风险小。但训练时间大很多。

4.4 连续与缺失值

目前取值的都是离散的。在连续的数据上,要将“连续数学离散化技术”-二分法对连续属性进行处理。

以下这个论文对决策树的二分处理解释比较好。

http://www.docin.com/p-490493786.html

核心内容:

图片 2

4.4.1 连续值处理:西瓜数据上添加了“密度”和“含糖率”。

【注意】以前的数据是离散,如:青色、浑浊、卷曲、是、否等。但是密度和含糖率,都是连续的数据,如0.456、0.258等。

然后根据二分法结合信息增溢来计算新的树。

4.4.2 如何数据集有缺失怎么办?

关心2个问题:

1.如何在属性值缺失情况下进行属性选择?(简单的说 表头没有怎么办)

比如该节点是根据a属性划分,但是待分类样本a属性缺失,怎么办呢?假设a属性离散,有1,2两种取值,那么就把该样本分配到两个子节点中去,但是权重由1变为相应离散值个数占样本的比例。然后计算错误率的时候,注意,不是每个样本都是权重为1,存在分数。

2.给定划分的属性,若样本缺失,如何划分?(简单的说 表头有了,表头里面的数据没有怎么办)

假如你使用ID3算法,那么选择分类属性时,就要计算所有属性的熵增(信息增益,Gain)。假设10个样本,属性是a,b,c。在计算a属性熵时发现,第10个样本的a属性缺失,那么就把第10个样本去掉,前9个样本组成新的样本集,在新样本集上按正常方法计算a属性的熵增。然后结果乘0.9(新样本占raw样本的比例),就是a属性最终的熵。

4.5 多变量决策树

相比于ID3、C4.5、CART这种单变量决策树(分支时只用一个属性),多变量决策树在分支时用的是多个属性的加权组合,来个直观的图(以下),这个是单变量决策树学习出来的划分边界,这些边界都是与坐标轴平行的,多变量决策树的划分边界是倾斜于坐标轴的。

算法分支(详情参见

ID3

选取能够得到最大信息增益(information gain)的特征为数据划分归类,直到全部划分结束而不对树的规模进行任何控制。

等树生成之后,执行后剪枝。

信息增益的潜在问题是,比如有一个数据集含有一个特征是日期或者ID,则该特征会得到最大的信息增益,但是显然在验证数据中不会得到任何的结果。C45的信息增益比就是解决这个问题的。

C45

选取能够得到最大信息增益率(information gain ratio)的特征来划分数据,并且像ID3一样执行后剪枝。

是ID3的后续版本并扩展了IDC的功能,比如特征数值允许连续,在分类的时候进行离散化。

信息增益率:

“Gain ratio takes number and size of branches into account when choosing an attribute, and corrects the information gain by taking the intrinsic information of a split into account (i.e. how much info do we need to tell which branch an instance belongs to).”

C50

这是最新的一个版本,是有许可的(proprietary license)。比之C45,减少了内存,使用更少的规则集,并且准确率更高。

CART

CART(Classification and Regression Trees)分类回归树,它使用基尼不纯度(Gini Impurity)来决定划分。Gini Impurity和information gain ratio的理解和区分在这里:

它和C45基本上是类似的算法,主要区别:1)它的叶节点不是具体的分类,而是是一个函数f(),该函数定义了在该条件下的回归函数。2)CART是二叉树,而不是多叉树。

总结表

图片 3

图片 4

xgboost

最后以下文章对以上内容总结挺好的 http://www.cnblogs.com/bourneli/archive/2013/03/15/2961568.html

1,决策树分类原理

决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种,分类树对离散变量做决策树,回归树对连续变量做决策树。

近来的调查表明决策树也是最经常使用的数据挖掘算法,它的概念非常简单。决策树算法之所以如此流行,一个很重要的原因就是使用者基本上不用了解机器学习算法,也不用深究它是如何工作的。直观看上去,决策树分类器就像判断模块和终止块组成的流程图,终止块表示分类结果(也就是树的叶子)。判断模块表示对一个特征取值的判断(该特征有几个值,判断模块就有几个分支)。

如果不考虑效率等,那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上,样本所有特征中有一些特征在分类时起到决定性作用,决策树的构造过程就是找到这些具有决定性作用的特征,根据其决定性程度来构造一个倒立的树--决定性作用最大的那个特征作为根节点,然后递归找到各分支下子数据集中次大的决定性特征,直至子数据集中所有数据都属于同一类。所以,构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程,我们需要解决的第一个问题就是,当前数据集上哪个特征在划分数据分类时起决定性作用。

为了找到决定性的特征、划分出最好的结果,我们必须评估数据集中蕴含的每个特征,寻找分类数据集的最好特征。完成评估之后,原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型,则则该分支处理完成,称为一个叶子节点,即确定了分类。如果数据子集内的数据不属于同一类型,则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集的方法相同,直到所有具有相同类型的数据均在一个数据子集内(叶子节点)。如下图就是一个决策树实例(目标是两类--见或者不见,每个样本有年龄、长相、收入、是否公务员四个特征):

图片 5

图片 6

1.纯标称值无缺失数据集

2, 决策树的学习过程

一棵决策树的生成过程主要分为以下3个部分:

特征选择:特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准,如何选择特征有着很多不同量化评估标准标准,从而衍生出不同的决策树算法。

决策树生成: 根据选择的特征评估标准,从上至下递归地生成子节点,直到数据集不可分则停止决策树停止生长。 树结构来说,递归结构是最容易理解的方式。

剪枝:决策树容易过拟合,一般来需要剪枝,缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

2.连续值和标称值混合且无缺失数据集

3,基于信息论的三种决策树算法

划分数据集的最大原则是:使无序的数据变的有序。如果一个训练数据中有20个特征,那么选取哪个做划分依据?这就必须采用量化的方法来判断,量化划分方法有多重,其中一项就是“信息论度量信息分类”。基于信息论的决策树算法有ID3、CART和C4.5等算法,其中C4.5和CART两种算法从ID3算法中衍生而来。

CART和C4.5支持数据特征为连续分布时的处理,主要通过使用二元切分来处理连续型变量,即求一个特定的值-分裂值:特征值大于分裂值就走左子树,或者就走右子树。这个分裂值的选取的原则是使得划分后的子树中的“混乱程度”降低,具体到C4.5和CART算法则有不同的定义方式。

ID3算法由Ross Quinlan发明,建立在“奥卡姆剃刀”的基础上:越是小型的决策树越优于大的决策树(be simple简单理论)。ID3算法中根据信息论的信息增益评估和选择特征,每次选择信息增益最大的特征做判断模块。ID3算法可用于划分标称型数据集,没有剪枝的过程,为了去除过度数据匹配的问题,可通过裁剪合并相邻的无法产生大量信息增益的叶子节点(例如设置信息增益阀值)。使用信息增益的话其实是有一个缺点,那就是它偏向于具有大量值的属性--就是说在训练集中,某个属性所取的不同值的个数越多,那么越有可能拿它来作为分裂属性,而这样做有时候是没有意义的,另外ID3不能处理连续分布的数据特征,于是就有了C4.5算法。CART算法也支持连续分布的数据特征。

C4.5是ID3的一个改进算法,继承了ID3算法的优点。C4.5算法用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝;能够完成对连续属性的离散化处理;能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高;但效率低,因树构造过程中,需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描,C4.5只适合于能够驻留于内存的数据集。

CART算法的全称是Classification And Regression Tree,采用的是Gini指数(选Gini指数最小的特征s)作为分裂标准,同时它也是包含后剪枝操作。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息,但其生成的决策树分支较大,规模较大。为了简化决策树的规模,提高生成决策树的效率,就出现了根据GINI系数来选择测试属性的决策树算法CART。

3.连续值和标称值混合,有缺失数据集

4,决策树优缺点

决策树适用于数值型和标称型(离散型数据,变量的结果只在有限目标集中取值),能够读取数据集合,提取一些列数据中蕴含的规则。在分类问题中使用决策树模型有很多的优点,决策树计算复杂度不高、便于使用、而且高效,决策树可处理具有不相关特征的数据、可很容易地构造出易于理解的规则,而规则通常易于解释和理解。决策树模型也有一些缺点,比如处理缺失数据时的困难、过度拟合以及忽略数据集中属性之间的相关性等。

第一个算法参考了《机器学习实战》的大部分代码,第二、三个算法基于前面的实现进行模块的增加。

(二)ID3算法的数学原理

前面已经提到C4.5和CART都是由ID3演化而来,这里就先详细阐述ID3算法,奠下基础。

本文由88必发手机版发布于冶金矿产,转载请注明出处:机器学习经典算法详解及Python实现,机器学习

关键词:

上一篇:没有了
下一篇:没有了