决策树生成——ID3算法的java实现
2016-12-15 19:53阅读：
前言：之前自己试着写了一下ID3
，发现自己逻辑不够清晰。所以决定仔细研读前人的代码，努力弥补一下差距。
源代码见：华夏35度，Data
Mining，归纳决策树ID3（Java实现）
- ID3简介
算法核心：在决策树各节点应用信息增益准则选择特征，递归地构建决策树。
输入：训练数据集D，特征集A，阈值ε
输出：决策树T
- 输入数据集
数据集描述气候的指标（天色outlook、温度temperature、湿度humidity、风速windy），以及分类能否出去玩（yes,no）
@relation weather.symbolic
@attribute outlook {sunny, overcast, rainy}
//天色
@attribute temperature {hot, mild, cool}
//温度
@attribute humidity {high, normal}
//湿度
@attribute windy {TRUE, FALSE}
//风速
@attribute play {yes, no} //
能否出去玩
@data
sunny,hot,high,FALSE,no
sunny,hot,high,TRUE,no
overcast,hot,high,FALSE,yes
rainy,mild,high,FALSE,yes
rainy,cool,normal,FALSE,yes
rainy,cool,normal,TRUE,no
overcast,cool,normal,TRUE,yes
sunny,mild,high,FALSE,no
sunny,cool,normal,FALSE,yes
rainy,mild,normal,FALSE,yes
sunny,mild,normal,TRUE,yes
overcast,mild,high,TRUE,yes
overcast,hot,normal,FALSE,yes
rainy,mild,high,TRUE,no
因此输入数据可以用下图表示：
则ID3
的属性为：
为了方便，创建一个索引，指向类别在A
ttribute集中的索引
- 树的结构
主要是一个Element类型（此类是用来构建xml中节点的）的root
- 建树buildDT
由于要频繁取属性，所以用
Sellatt
|
存下除了类别之外的attribute的索引
|
Subset
|
存下数据集的索引
|
调用buildDT
函数开始建树
下面重点分析buildDT
方法
-
寻找各特征对数据集的信息增益，选择信息增益最大的特征。（tips:信息增益最大的，就是H(D|A)最小的）
求得当前信息增益最大的特征索引是minIndex，
根据索引，获取此特征的特征名称，并从特征列表中剔除
- 将这个特征作为节点，构建叶子节点
根据索引，获取此特征的各取值。
遍历此特征的各取值，在每个取值val下，遍历数据集。选出本取值下的数据集al,并递归调用buildDT
- 总结
自己写的时候，屡不清数据的表示方式，复杂了逻辑。要仔细吸收别人的思想，简洁代码。
