决策树之ID3算法的Python实现

目录:

  1. 什么是决策树?
  2. 决策树主要算法有哪些?
  3. 信息熵与信息增益
  4. ID3算法介绍
  5. 决策树的优缺点
  6. ID3算法的Python实现

内容:

1.什么是决策树?

       决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的一种图解法。

       决策树是一种十分常用的分类方法。它是一种监督学习、所谓监督学习就是给定一堆样本,每个样本都有一组属性和一个类别,这些类别是事先确定的,那么通过学习得到一个分类器,这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

       通俗来说,决策树就是用于分类的一种算法,适用于对离散且包含同类多种属性的数据进行分类,分类的准确性取决于训练集。

2.决策树主要算法有哪些?

     常用的决策树算法有ID3,C4.5,CART等,之后会详解,这次只讲最容易的ID3算法。

3.信息熵与信息增益

      熵这个概念最早起源于物理学,在物理学中是用来度量一个热力学系统的无序程度,而在信息学里面,熵是对不确定性的度量。在1948年,香农引入了信息熵,将其定义为离散随机事件出现的概率,一个系统越是有序,信息熵就越低,反之一个系统越是混乱,它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。这是ID3的核心,一定要理解哦!

设随机变量集合ID3-1gallery.

” src=”http://www.snakehacker.me/wp-content/plugins/ckeditor-for-wordpress/plugins/wpgallery/images/spacer.gif?t=F7J8″ title=”gallery ids=”69″” />gallery.” src=”http://www.snakehacker.me/wp-content/plugins/ckeditor-for-wordpress/plugins/wpgallery/images/spacer.gif?t=F7J8″ title=”gallery size=”full” ids=”69″” />

集合中每个元素被获取的概率为ID3-2gallery.

” src=”http://www.snakehacker.me/wp-content/plugins/ckeditor-for-wordpress/plugins/wpgallery/images/spacer.gif?t=F7J8″ title=”gallery ids=”70″” />

那么,X的信息熵为ID3-3gallery.

” src=”http://www.snakehacker.me/wp-content/plugins/ckeditor-for-wordpress/plugins/wpgallery/images/spacer.gif?t=F7J8″ title=”gallery ids=”71″” />

由H(X)可以看出,当X内的元素数量越多,则H(X)的混乱程度越大,因此用信息熵来衡量X的不确定性。

       再来谈信息增益,信息增益是针对每一个特征而言的。信息增益就是看某一个特征,系统有它和没有它时的信息熵各是多少,两者的差值就是这个特征给系统带来的信息获取量,即信息增益。

4.ID3算法介绍

说了那么多概念,接下来我们来看一个算法,通过它来更现实地了解决策树算法到底是怎么一回事情。

ID3算法的核心思想就是以信息增益来度量决策树建立时每一次节点中属性的选择,选择分裂后信息增益最大的属性进行分裂,直到训练集的样本完全被分类。

接下来看个简单的例子:

ID3-4 

这是一个买电脑的训练集,第2-5列是样本的属性,最后一列代表用户是否会买电脑。我们通过训练集训练我们的决策树算法,最后可以得到我们想要的决策树模型。这样一来,只要以后有用户来商店,只要输入他的属性就可以预测该用户是否会买电脑。

首先,我们根据公式计算该样本的信息熵:

ID3-5

T为训练集集合

接着,我们随便选一个属性,假设根据它来分类,计算信息熵:

这里我们选择age

ID3-6

因此T_age的信息增益为:

Gain(T_age)=0.246

如法炮制,计算如果取另外三个属性的信息增益分别是:

Gain(T_income)=0.029

Gain(T_student)=0.151

Gain(T_credit_rating)=0.048

选取信息增益最大的属性,作为第一个节点,以此类推继续分类,直到每个类的样本标记完全一样(就是买的和不买的完全分开)

这就是ID3算法根据训练集建立样本空间的完整过程。

5.决策树的优缺点

优点:

1) 可以生成可以理解的规则。

2) 计算量相对来说不是很大。 

3) 可以处理连续和种类字段。 

4) 决策树可以清晰的显示哪些字段比较重要。

缺点:

1) 数据集很大(多属性)时产生规则会很复杂,效率下降。

2) 局部最优,无法保障全局最优。 

3) 对于训练集的选择需要尽可能的排除噪声,可以通过交叉验证后剪枝的方法来克服过拟合。 

      4) 对连续性的字段比较难预测。

6.ID3算法的Python实现

这里用到了一个scikit-learn的Python包,它可以用于分类,回归,聚类,降唯,模型选择等。我们还需要下载安装一个Python的机器学习环境—Anaconda,它集成了Python2和3两个版本,可以在IDE中导入替换原来安装的python。最后,为了让决策树可视化 还需要安装Graphviz并且在windows系统环境变量path下添加它的bin目录,这个工具用来将scikit-learn生成的决策树模型进行图形化显示,方便用户查阅。

Cmd命令:dot -Tpdf input.dot -0 output.pdf

Input.dot为输入文件名,output.pdf为输出

出来的效果如下:

ID3-7

代码已经共享到baidu云盘,欢迎下载(代码已打注释)如果有哪里没写清楚的请尽快告诉我(QQ:1256541288),我会尽快改善。

——Snake

snake

作者: snake

我们需要为这个社会做一点贡献,失去了才懂得去珍惜。

《决策树之ID3算法的Python实现》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注