机器学习算法-决策树C4.5练习

决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象,而每个分叉路径则代表的某个可能的属性值,而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出,若欲有复数输出,可以建立独立的决策树以处理不同输出。 数据挖掘中决策树是一种经常要用到的技术,可以用于分析数据,同样也可以用来作预测(就像上面的银行官员用他来预测贷款风险)。从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

  1986年Quinlan提出了著名的ID3算法。在ID3算法的基础上,1993年Quinlan又提出了C4.5算法。为了适应处理大规模数据集的需要,后来又提出了若干改进的算法,其中SLIQ (super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比较有代表性的两个算法,此处暂且略过。

  本文实现了C4.5的算法,在ID3的基础上计算信息增益,从而更加准确的反应信息量。其实通俗的说就是构建一棵加权的最短路径Haffman树,让权值最大的节点为父节点。

  下面简要介绍一下ID3算法:

  ID3算法的核心是:在决策树各级结点上选择属性时,用信息增益(information gain)作为属性的选择标准,以使得在每一个非叶结点进行测试时,能获得关于被测试记录最大的类别信息。

  其具体方法是:检测所有的属性,选择信息增益最大的属性产生决策树结点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树结点的分支,直到所有子集仅包含同一类别的数据为止。最后得到一棵决策树,它可以用来对新的样本进行分类。

  某属性的信息增益按下列方法计算:

  信息熵是香农提出的,用于描述信息不纯度(不稳定性),其计算公式是Info(D)。

  其中:Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例;j是属性A中的索引,D是集合样本,Dj是D中属性A上值等于j的样本集合。

这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望,可以区分训练样本中正负样本的能力。信息增益定义为结点与其子结点的信息熵之差,公式为Gain(A)。

  ID3算法的优点是:算法的理论清晰,方法简单,学习能力较强。其缺点是:只对比较小的数据集有效,且对噪声比较敏感,当训练数据集加大时,决策树可能会随之改变。

  C4.5算法继承了ID3算法的优点,并在以下几方面对ID3算法进行了改进:

  1) 用信息增益率来选择属性,克服了用信息增益选择属性时偏向选择取值多的属性的不足,公式为GainRatio(A);

  2) 在树构造过程中进行剪枝;

  3) 能够完成对连续属性的离散化处理;

  4) 能够对不完整数据进行处理。

  C4.5算法与其它分类算法如统计方法、神经网络等比较起来有如下优点:产生的分类规则易于理解,准确率较高。其缺点是:在构造树的过程中,需要对数据集进行多次的顺序扫描和排序,因而导致算法的低效。此外,C4.5只适合于能够驻留于内存的数据集,当训练集大得无法在内存容纳时程序无法运行。

  实现的C4.5数据集合如下:

  它记录了再不同的天气状况下,是否出去觅食的数据。

  程序引入状态树作为统计和计算属性的数据结构,它记录了每次计算后,各个属性的统计数据,其定义如下:

1 struct attrItem
2 {
3    std::vector<int>  itemNum;  //itemNum[0] = itemLine.size()
4                                //itemNum[1] = decision num
5    set<int>          itemLine;
6 };
7
8 struct attributes
9 {
10    string attriName;
11    vector<double> statResult;
12    map<string, attrItem*> attriItem;
13 };
14
15 vector<attributes*> statTree;

程序输出结果为:

以图形表示为:

小结:

  1、在设计程序时,对程序逻辑有时会发生混乱,后者在纸上仔细画了些草图才解决这些问题,画一个好图可以有效的帮助你理解程序的流程以及逻辑脉络,是需求分析时最为关键的基本功。

  2、在编写程序之初,一直在纠结用什么样的数据结构,后来经过几次在编程实现推敲,才确定最佳的数据结构,可见数据结构在程序中的重要性。

  3、决策树的编写,其实就是理论与实践的相结合,虽然理论上比较简单,但是实践中却会遇到这样那样的问题,而这些问题就是考验一个程序员对最基本的数据结构、算法的理解和熟练程度,所以,勤学勤练基本功依然是关键。

原文发布于微信公众号 - 大数据挖掘DT数据分析(datadw)

原文发表时间:2015-07-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习之旅

应用:数据预处理-异常值识别

上四分位数Q3,又叫做升序数列的75%位点 下四分位数Q1,又叫做升序数列的25%位点 箱式图检验就是摘除大于Q3+3/2*(Q3-Q1),小于Q1-3/2...

743
来自专栏算法channel

深度学习|循环神经网络之LSTM(后篇)

01 — 回顾 昨天推送了循环神经网络LSTM的前半部分,说到构成其网络模型:输入层包含一系列时序:x0, x1, ..., xt,隐含层是实现 Long-te...

3928
来自专栏AI科技评论

学界 | 百度联合英伟达发布最新论文:使深度学习效率事半功倍的混合精度训练

AI科技评论消息: 在10月10日-11日在加拿大蒙特利尔召开的Rework Deep Learning Summit会议上,百度高级研究员Greg Diamo...

3388
来自专栏人工智能

计算图的微积分:反向传播

后向传播是训练深度模型在计算上易于处理的关键算法。对于现代神经网络,相对于单纯的实现,它可以使梯度下降的训练速度提高一千万倍。这相当于模型训练时间...

2327
来自专栏机器学习算法全栈工程师

不懂word2vec,还敢说自己是做NLP?

如今,深度学习炙手可热,deep learning在图像处理领域已经取得了长足的进展。随着Google发布word2vec,深度学习在自然语言处理领域也掀起了一...

965
来自专栏PPV课数据科学社区

【V课堂】R语言十八讲(十五)—-置换检验和自助法

不知道看到这里,读者有么有发现,前面讲了那么多方法,几大检验,回归分析,方差分析“都有一个共同的特点,那就是有一定的前提假设,只有满足这个假设时,模型才有较好的...

2546
来自专栏机器之心

专栏 | 递归卷积神经网络在解析和实体识别中的应用

35013
来自专栏IT派

资源 | textgenrnn:只需几行代码即可训练文本生成网络

通过简简单单的几行代码,使用预训练神经网络生成文本,或者在任意文本数据集上训练你自己的任意规模和复杂度的文本生成神经网络。

883
来自专栏ATYUN订阅号

解决机器学习中不平衡类的问题

大多数实际的分类问题都显示了一定程度的类不平衡,也就是当每个类不构成你的数据集的相同部分时。适当调整你的度量和方法以适应你的目标是很重要的。如果没有这样做,你可...

3486
来自专栏数据结构与算法

超几何分布与二项分布及其期望

惊奇的发现选修2-3上有期望的介绍,不过我没有课本啊qwq。只能去网上找资料了。。

392

扫描关注云+社区