2016-11-14 16:00  596人阅读  评论(0)  收藏  举报   分类： 机器学习（24） 

目录(?)[+]

一、决策树分类算法概述

    决策树算法是从数据的属性（或者特征）出发，以属性作为基础，划分不同的类。例如对于如下数据集 （数据集） 其中，第一列和第二列为属性（特征），最后一列为类别标签，1表示是，0表示否。决策树算法的思想是基于属性对数据分类，对于以上的数据我们可以得到以下的决策树模型 （决策树模型） 先是根据第一个属性将一部份数据区分开，再根据第二个属性将剩余的区分开。     实现决策树的算法有很多种，有ID3、C4.5和CART等算法。下面我们介绍ID3算法。

二、ID3算法的概述

    ID3算法是由Quinlan首先提出的，该算法是以信息论为基础，以信息熵和信息增益为衡量标准，从而实现对数据的归纳分类。     首先，ID3算法需要解决的问题是如何选择特征作为划分数据集的标准。在ID3算法中，选择信息增益最大的属性作为当前的特征对数据集分类。信息增益的概念将在下面介绍，通过不断的选择特征对数据集不断划分；     其次，ID3算法需要解决的问题是如何判断划分的结束。分为两种情况，第一种为划分出来的类属于同一个类，如上图中的最左端的“非鱼类”，即为数据集中的第5行和第6行数据；最右边的“鱼类”，即为数据集中的第2行和第3行数据。第二种为已经没有属性可供再分了。此时就结束了。     通过迭代的方式，我们就可以得到这样的决策树模型。 （ID3算法基本流程）

三、划分数据的依据

    ID3算法是以信息熵和信息增益作为衡量标准的分类算法。

1、信息熵(Entropy)

   熵的概念主要是指信息的混乱程度，变量的不确定性越大，熵的值也就越大，熵的公式可以表示为： 其中，，为类别在样本中出现的概率。

2、信息增益(Information gain)

   信息增益指的是划分前后熵的变化，可以用下面的公式表示： 其中，表示样本的属性，value（A)是属性所有的取值集合。是的其中一个属性值，是中的值为的样例集合。

四、实验仿真

1、数据预处理

    我们以下面的数据为例，来实现ID3算法： 摘自 http://blog.sina.com.cn/s/blog_6e85bf420100ohma.html 我们首先需要对数据处理，例如age属性，我们用0表示youth，1表示middle_aged，2表示senior等等。 （将表格数据化）

2、实验结果

（原始的数据 ） （划分1） （划分2） （划分3） （最终的决策树） MATLAB代码 主程序 [plain]  view plain  copy   %% Decision Tree   % ID3      %导入数据