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

相关文章

来自专栏机器之心

教程 | 5种快速易用的Python Matplotlib数据可视化方法

选自towardsdatascience 作者:George Seif 机器之心编译 参与:刘晓坤、思源 数据可视化是数据科学家工作的重要部分。在项目的早期...

3676
来自专栏机器之心

教程 | 深度学习:自动编码器基础和类型

36216
来自专栏人工智能LeadAI

TensorFlow从0到1 | 第十一章 74行Python实现手写体数字识别

到目前为止,我们已经研究了梯度下降算法、人工神经网络以及反向传播算法,他们各自肩负重任: 梯度下降算法:机器自学习的算法框架; 人工神经网络:“万能函数”的形式...

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

深度学习word2vec笔记(算法篇)

一. CBOW加层次的网络结构与使用说明 Word2vec总共有两种类型,每种类型有两个策略,总共4种。这里先说最常用的一种。这种的网络结构如下图。 ? 其中第...

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

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

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

5308
来自专栏UAI人工智能

连载 | 深度学习入门第六讲

1276
来自专栏AI科技大本营的专栏

一文看尽深度学习RNN:为啥就它适合语音识别、NLP与机器翻译?

本文是机器学习大牛Jason Brownlee系统介绍RNN的文章,他在文中详细对比了LSTM、GRU与NTM三大主流架构在深度学习上的工作原理及各自特性。读过...

3529
来自专栏机器之心

教程 | 用人工蜂群算法求解k-分区聚类问题

我之前的文章介绍了如何利用名为人工蜂群算法(ABC)的集群智能(SI)算法来解决现实世界的优化问题:https://medium.com/cesar-updat...

1010
来自专栏量化投资与机器学习

【Python机器学习】系列之特征提取与处理篇(深度详细附源码)

第1章 机器学习基础 将机器学习定义成一种通过学习经验改善工作效果的程序研究与设计过程。其他章节都以这个定义为基础,后面每一章里介绍的机器学习模型都是按照这个...

1.2K7
来自专栏机器之心

教程 | 从头开始了解PyTorch的简单实现

选自GitHub 机器之心编译 参与:路 本教程展示了如何从了解张量开始到使用 PyTorch 训练简单的神经网络,是非常基础的 PyTorch 入门资源。Py...

5255

扫码关注云+社区