龙空技术网

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

java程序媛 243

前言:

此时姐妹们对“id3算法java源码”大约比较关注,小伙伴们都需要了解一些“id3算法java源码”的相关内容。那么小编在网上收集了一些对于“id3算法java源码””的相关知识,希望朋友们能喜欢,看官们一起来学习一下吧!

小编花了很长的时间,把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、第二个问题是当程序划分到最后一个属性时,出现了数据的类标识并不是同一个类的时候,小编的处理操作时直接不处理,直接返回,造成节点没有数据属性,也没有数据索引。

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

标签: #id3算法java源码