数据挖掘课上面老师介绍了下决策树ID3算法,我抽空余时间把这个算法用C++实现了一遍。
决策树算法是非常常用的分类算法,是逼近离散目标函数的方法,学习得到的函数以决策树的形式表示。其基本思路是不断选取产生信息增益最大的属性来划分样例集和,构造决策树。信息增益定义为结点与其子结点的信息熵之差。信息熵是香农提出的,用于描述信息不纯度(不稳定性),其计算公式是
Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望,可以区分训练样本中正负样本的能力,其计算公司是
我实现该算法针对的样例集合如下
该表记录了在不同气候条件下是否去打球的情况,要求根据该表用程序输出决策树
C++代码如下,程序中有详细注释
输入的训练数据如下
程序输出决策树如下
可以用图形表示为
有了决策树后,就可以根据气候条件做预测了
例如如果气候数据是{Sunny,Cool,Normal,Strong} ,根据决策树到左侧的yes叶节点,可以判定会去游泳。
另外在编写这个程序时在数据结构的设计上面走了弯路,多叉树的实现有很多方法,本算法采用每个结点的所有孩子用vector保存比较合适,同时注意维护剩余样例和剩余属性信息,建树时横向遍历靠循环属性的值,纵向遍历靠递归调用 ,总体是DFS,树和图的遍历在编程时经常遇到,得熟练掌握。程序有些地方的效率还得优化,有不足的点地方还望大家拍砖。
分享到:
相关推荐
数据挖掘决策树ID3算法C++实现 数据挖掘入门程序
数据挖掘技术决策树分类算法(ID3算法)研究.pdf
决策树ID3算法描述与实现 使用MFC做的,有界面有算法,还有详细的word报告与描述
用Java写的决策树ID3算法,训练集和测试数据都是用的米歇尔的《机器学习》中的例子。
大学 ppt 数据挖掘 决策树 原理 算法 id3 迭代二元树 3代
决策树ID3算法的实现,里面有很详细的注释
本程序为VS2010编写,其中源程序中包含测试数据。
数据挖掘技术决策树分类算法分析、比较与实验.pdf
资源中包括决策树分类算法、朴素贝叶斯分类算法、人工神经网络分类算法的代码(.ipynb,.py)和案例股票价格波动分析的数据(.csv),建议使用jupyter notebook打开.ipynb文件,体验更佳 1、资源配合博文《【python...
c++编写的决策树分类算法,能够对文本进行决策树分类,算法中包括了决策树算法的全部步骤,是决策树学习的不错例子,下载后用VS2008打开就可以执行
主要利用了网上的决策树ID3算法,添加了调用决策树的模块,输出决策树调用最终产生的结果
机器学习C++源码解析-决策树cart算法-源码+数据
描述了数据挖掘的概况以及决策树算法的实现,主要是ID3算法的不足之处所引的优化过程是本资源的重点,里面配有图解和文字说明
此程序主要实现对数据的加载和处理,首先加载数据,本算法选择的数据集是鸢尾花数据集,加载的数据形式是元胞数组,本程序先把其转换成字符串数组,后对字符串数组进行处理,将数据部分和标签部分分隔开,数据部分...
分类算法与决策树 1 1 分类的概念 3 2 预备知识 3 2.1 目的 3 2.2 辨别 3 2.3 分类VS预测 3 2.3.1 分类 3 ...4.3 决策树算法 6 4.4 决策树修剪 6 4.5 决策树应用 6 5 MATLAB实现 7 5.1 加载数据集 7 5.2 分类 7
首先讲解了信息量的概念,隐身出信息熵的概念,举经典例子。
一个使用C++对决策树的算法实现。