一、引言

在最开始的时候，我本来准备学习的是C4.5算法，后来发现C4.5算法的核心还是ID3算法，所以又辗转回到学习ID3算法了，因为C4.5是他的一个改进。至于是什么改进，在后面的描述中我会提到。

二、ID3算法

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

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

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

Day OutLook Temperature Humidity Wind PlayTennis
1 Sunny Hot High Weak No
2 Sunny Hot High Strong No
3 Overcast Hot High Weak Yes
4 Rainy Mild High Weak Yes
5 Rainy Cool Normal Weak Yes
6 Rainy Cool Normal Strong No
7 Overcast Cool Normal Strong Yes
8 Sunny Mild High Weak No
9 Sunny Cool Normal Weak Yes
10 Rainy Mild Normal Weak Yes
11 Sunny Mild Normal Strong Yes
12 Overcast Mild High Strong Yes
13 Overcast Hot Normal Weak Yes
14 Rainy Mild High Strong No

package DataMing_ID3;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * ID3算法实现类
 * 
 * @author lyq
 * 
 */
public class ID3Tool {
	// 类标号的值类型
	private final String YES = "Yes";
	private final String NO = "No";

	// 所有属性的类型总数,在这里就是data源数据的列数
	private int attrNum;
	private String filePath;
	// 初始源数据，用一个二维字符数组存放模仿表格数据
	private String[][] data;
	// 数据的属性行的名字
	private String[] attrNames;
	// 每个属性的值所有类型
	private HashMap<String, ArrayList<String>> attrValue;

	public ID3Tool(String filePath) {
		this.filePath = filePath;
		attrValue = http://www.mamicode.com/new HashMap<>();>他的场景调用实现的方式为：
/**
 * ID3决策树分类算法测试场景类
 * @author lyq
 *
 */
public class Client {
	public static void main(String[] args){
		String filePath = "C:\\Users\\lyq\\Desktop\\icon\\input.txt";
		
		ID3Tool tool = new ID3Tool(filePath);
		tool.startBuildingTree(true);
	}
}
最终的结果为：
	------【OutLook】
		--Sunny--【Humidity】
				--High--类别:No[1, 2, 8, ]
				--Normal--类别:Yes[9, 11, ]
		--Overcast--类别:Yes[3, 7, 12, 13, ]
		--Rainy--【Wind】
				--Weak--类别:Yes[4, 5, 10, ]
				--Strong--类别:No[6, 14, ]

请从左往右观察这棵决策树，【】里面的是分类属性，---XXX----，XXX为属性的值，在叶子节点处为类标记。
对应的分类结果图：

这里的构造决策树和显示决策树采用的DFS的方法，所以可能会比较难懂，希望读者能细细体会，可以调试一下代码，一步步的跟踪会更加容易理解的。
三、C4.5算法
如果你已经理解了上面ID3算法的实现，那么理解C4.5也很容易了，C4.5与ID3在核心的算法是一样的，但是有一点所采用的办法是不同的，C4.5采用了信息增益率作为划分的根据，克服了ID3算法中采用信息增益划分导致属性选择偏向取值多的属性。信息增益率的公式为:

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

和熵的计算公式比较像，具体的信息增益率的算法也在上面的代码中了，请关注着2个方法：
		// 选择剩余属性中信息增益最大的作为下一个分类的属性
		for (int i = 0; i < remainAttr.size(); i++) {
			// 判断是否用ID3算法还是C4.5算法
			if (isID3) {
				// ID3算法采用的是按照信息增益的值来比
				tempValue = http://www.mamicode.com/computeGain(remainData, remainAttr.get(i));>在补充一下C4.5在其他方面对ID3的补充和改进：
1、在构造决策树的过程中能对树进行剪枝。
2、能对连续性的值进行离散化的操作。
四、编码时遇到的一些问题
为了实现ID3算法，从理解阅读他的原理就已经用掉了比较多的时间，然后再尝试阅读别人写的C++版本的代码，又是看了几天，好不容易实现了2个算法，最后在构造树的过程中遇到了最大了麻烦，因为用到了递归构造树，对于其中节点的设计就显得至关重要了，也许我自己目前的设计也不是最优秀的。下面盘点一下我的程序的遇到的一些问题和存在的潜在的问题:
1、在构建决策树的时候，出现了remainAttr值缺少的情况，就是递归的时候remainAttr的属性划分移除掉之后，对于上次的递归操作的属性时受到影响了，后来发现是因为我remainAttr采用的是ArrayList，他是一个引用对象，通过引用传入的方式，对象用的还是同一个，所以果断重新建了一个ArrayList对象，问题就OK了。
				// 创建新的对象属性，对象的同个引用会出错
				ArrayList<String> rAttr = new ArrayList<>();
				for (String str : remainAttr) {
					rAttr.add(str);
				}

				buildDecisionTree(childNode[i], valueTypes.get(i), rData,
						rAttr, isID3);
2、第二个问题是当程序划分到最后一个属性时，如果出现了数据的类标识并不是同一个类的时候，我的处理操作时直接不处理，直接返回，会造成节点没有数据属性，也没有数据索引。
	private void buildDecisionTree(AttrNode node, String parentAttrValue,
			String[][] remainData, ArrayList<String> remainAttr, boolean isID3) {
		node.setParentAttrValue(parentAttrValue);

		String attrName = "";
		double gainValue = http://www.mamicode.com/0;>在这种情况下的处理不是很恰当个人觉得是这样。

决策分类树算法之ID3，C4.5算法系列