走在架构师路上之决策分类树算法之ID3，C4.5算法系列

小编花了很长的时间，把18大数据挖掘的经典算法进行了学习而且进行了代码实现，涉及到了很多算法比如：决策分类，聚类，链接挖掘，关联挖掘，模式挖掘等等方面。也算是对数据挖掘领域的入门。之后小编的文章都会介绍算法。直到18个介绍完毕，另外想要代码的可以私聊我。

一、引言

刚开始的时候，小编本来是要学习C4.5算法，最后发现C4.5算法的核心是ID3算法，所以又辗转回到学习ID3算法，因为C4.5是它的一个改进。具体是什么改进，在后面的描述中小编会提到。

二、ID3算法

ID3算法是分类决策树算法的一种。通过系列的规则，将数据最后分类成决策树的形式。分类根据的是熵这个概念。熵在物理这门课程中就出现过，它表示是一个物质的稳定度，在这里就是分类的纯度的一个概念。公式为：

在ID3中，采用的是Gain信息增益来作为一个分类的判定标准的。定义公式为：

每次选择属性中信息增益大的作为划分属性，在这里小编实现一个Java版本的ID3算法，为了模拟数据的可观的操作性，就把数据写到一个input.txt文件中，作为数据源，格式如下：

PalyTennis为结构属性，作为类标识用的，中间的OutLool,Temperature,Humidity,Wind才是划分属性，通过将源数据与执行程序分类，这样可以模拟巨大的数据量了。下面要讲的是ID3的主程序类，小编将ID3的算法进行包装，对外只是开放了一个构建决策树的方法，在构造函数时候，只需传入一个数据路径文件就行：

场景实现的方式为：

结果为：

三、C4.5算法

如果你看懂上面ID3算法的实现，理解C4.5也很容易了，C4.5与ID3在核心的算法是一样的，但有一点是不同的，C4.5采用了信息增益率作为划分的根据，克服了ID3算法中采用信息增益划分导致属性选择偏向取值多的属性。信息增益率的公式为:

分母的位置是分裂因子，他的计算公式为：

和熵的计算公式比较像，具体的信息增益率的算法也在上面的代码中了，请关注着2个方法：

补充一下C4.5在其他方面对ID3的补充和改进：

1、在构造决策树的过程中能对树进行剪枝。

2、能对连续性的值进行离散化的操作。

四、编码时遇到的一些问题

实现ID3算法，从阅读和理解它的原理就花掉了很多时间，再尝试着阅读其他人写的C++版本的代码，又是花了几天时间，费了好大的劲实现了2个算法，最后在构造树的过程中遇到了很大麻烦，用到了递归构造树，对于其中节点的设计就显得更重要了，或许我目前的设计也不是最优秀。下面是小编的程序遇到的一些问题。

1、在构建决策树的时候，出现remainAttr值缺少的情况，是递归的时候remainAttr的属性划分移除掉之后，对于上次的递归操作的属性时受到影响了，后来才发现是因为小编remainAttr采用的是ArrayList，他是一个引用对象，通过引用传入的方式，对象用的还是同一个，所以果断重新建了一个ArrayList对象，问题就OK了。

2、第二个问题是当程序划分到最后一个属性时，出现了数据的类标识并不是同一个类的时候，小编的处理操作时直接不处理，直接返回，造成节点没有数据属性，也没有数据索引。

我的妈呀 总于写完了 好累啊 喜欢和小编交流的 私信我 需要技术支持私信我哦！