机器学习算法-决策树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 条评论
登录 后参与评论

相关文章

来自专栏崔庆才的专栏

Learning to Rank概述

Learning to Rank,即排序学习,简称为 L2R,它是构建排序模型的机器学习方法,在信息检索、自然语言处理、数据挖掘等场景中具有重要的作用。其达到的...

3275
来自专栏SnailTyan

ResNet论文翻译——中文版

Deep Residual Learning for Image Recognition 摘要 更深的神经网络更难训练。我们提出了一种残差学习框架来减轻网络训...

3077
来自专栏有趣的Python

4- OpenCV+TensorFlow 入门人工智能图像处理-灰度化处理

图片特效及线段文字的绘制 特效1: 灰度处理 ? mark 完成彩色图片灰度化。彩色图片有三个颜色通道RGB 灰度图片也是三通道的话,RGB值相等。 单通...

4049
来自专栏AI科技评论

开发 | Keras版faster-rcnn算法详解(RPN计算)

AI科技评论按:本文首发于知乎专栏Learning Machine,作者张潇捷, AI科技评论获其授权转载。 前段时间学完Udacity的机器学习和深度学习的课...

47111
来自专栏深度学习之tensorflow实战篇

皮尔森类似度(Pearson Similiarity)计算举例与数学特性和存在问题

Pearson Similiarity image.png 计算案例 以下以还有一篇文章中的用户-物品关系为例,说明一下皮尔森类似度的计算过程。 ? ...

3445
来自专栏大数据挖掘DT机器学习

R语言与机器学习(分类算法)决策树算法

决策树定义 首先,我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 ? 观察上图,我们判决鸢尾花的思考过程可以这么...

3704
来自专栏AI科技评论

开发 | CNN中的maxpool到底是什么原理?

AI科技评论按:本文整理自知乎问题“请问 CNN 中的 maxpool 到底是什么原理,为什么要取最大值,取最大值的原理是什么?谢谢。”的下Yjango和小白菜...

3537
来自专栏瓜大三哥

基于FPGA的Canny算子设计(一)

Canny算子计算流程: 高斯滤波和Sobel算子已经在前面讲过,所以这里主要讨论非最大值抑制和滞后分割电路设计。 非最大值一直电路设计 非最大值抑制主要是对...

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

机器学习系列:(三)特征提取与处理

特征提取与处理 上一章案例中的解释变量都是数值,比如匹萨的直接。而很多机器学习问题需要研究的对象可能是分类变量、文字甚至图像。本章,我们介绍提取这些变量特征的方...

4028

特征选择(Feature Selection)引言

您应该采纳哪种特征去创建一个可预测的模型呢?

2456

扫码关注云+社区