我们概念讲解是在这里，下面便是成员变量。我们一点一点看，最后拉通走一遍。整个程序我是顺序运行的，给一个标题方便大家去找对应的方法
public class ID3 {
Instances dataset;
boolean pure;
int numClasses;
int[] availableInstances;
int[] availableAttributes;
int splitAttribute;
ID3[] children;
int label;
int[] predicts;
static int smallBlockThreshold = 3;
OK，人员已就位，旅途出发！进入main函数
二、主函数main public static void main(String[] args) {
id3Test();
}// Of main
main函数里面只有一个方法，ID3算法测试，进去看看：
ID3算法入口 public static void id3Test() {
ID3 tempID3 = new ID3("D:/data/weather.arff");
// ID3 tempID3 = new ID3("D:/data/mushroom.arff");
ID3.smallBlockThreshold = 3;
tempID3.buildTree();
System.out.println("The tree is: rn" + tempID3);
double tempAccuracy = tempID3.selfTest();
System.out.println("The accuracy is: " + tempAccuracy);
}// Of id3Test
首先是数据导入。然后把一个块的最小数目设置为 3 ，什么意思？就是当我这个块中只有三个数据的时候，尽管它不纯，你也别分了。第 5 行便是建立决策树，后面的输出结果和精度评定我们最后来说。我们先来看看与以往数据导入不同的部分。
导入数据集children = null; // 通过投票选择标签 label = getMajorityClass(availableInstances); // 判断它是否为纯的方法 pure = pureJudge(availableInstances);
在数据导入的时候，我们把孩子结点设置为 null,根节点都没找到，孩子不能从石头里蹦出来吧！getMajorityClass() 方法选出最多的哪一类。
getMajorityClass() public int getMajorityClass(int[] paraBlock) {
int[] tempClassCounts = new int[dataset.numClasses()]; // 决策类的个数
for (int i = 0; i < paraBlock.length; i++) {// 这个块元素对应的决策类统计
tempClassCounts[(int) dataset.instance(paraBlock[i]).classValue()]++;
} // Of for i
int resultMajorityClass = -1;
int tempMaxCount = -1;
for (int i = 0; i < tempClassCounts.length; i++) { // 这个循环可以找出最多的票数种类以及它的票数
if (tempMaxCount < tempClassCounts[i]) {
resultMajorityClass = i;
tempMaxCount = tempClassCounts[i];
} // Of if
} // Of for i
return resultMajorityClass;
}// Of getMajorityClass
我们是怎么来找出这个最主要的类呢？假设我们的狗分为 拉布拉多、二哈、金毛三种类型，我们给他编号 0,1,2 。对应生成三个空间的数组tempClassCounts [],之后我们就去遍历狗的数据集，是金毛我就在数组下标为2的地方+1，二哈就在tempClassCounts [1] ++;然后我们就去比较这三个空间中三个数字比较大，就返回它作为主要的类。
pureJudge（） public boolean pureJudge(int[] paraBlock) {
pure = true;
for (int i = 1; i < paraBlock.length; i++) {// 从第一个开始，0是哨兵？
if (dataset.instance(paraBlock[i]).classValue() != dataset.instance(paraBlock[0])
.classValue()) {
pure = false;
break;
} // Of if
} // Of for i
return pure;
}// Of pureJudge
这里我们把第一个元素作为老大，他代表了所有数据。比如这里的位置 paraBlock[0] 存放的是金毛，我们就去遍历后面的狗，如果全部是金毛那么我们就说这个狗群（Block）是纯净的返回ture，如果出现别的狗，那么就不纯净返回false。
bulidTree()数据导入就结束了，我们该进入建树环节了，这可是一个大工程啊。高山起微尘，千里始足下。我们继续出发咯！
public void buildTree() {
if (pureJudge(availableInstances)) { // 如果树纯就返回
return;
} // Of if
if (availableInstances.length <= smallBlockThreshold) { // 块个数不够也返回
return;
} // Of if
selectBestAttribute(); // 最优条件属性选择
int[][] tempSubBlocks = splitData(splitAttribute); // 子块
children = new ID3[tempSubBlocks.length];
// 构造剩余的属性集。
int[] tempRemainingAttributes = new int[availableAttributes.length - 1]; // 长度-1
for (int i = 0; i < availableAttributes.length; i++) {
if (availableAttributes[i] < splitAttribute) {
tempRemainingAttributes[i] = availableAttributes[i];
} else if (availableAttributes[i] > splitAttribute) {
tempRemainingAttributes[i - 1] = availableAttributes[i];
} // Of if
} // Of for i
// 构造子树
for (int i = 0; i < children.length; i++) {
if ((tempSubBlocks[i] == null) || (tempSubBlocks[i].length == 0)) {
children[i] = null;
continue;
} else {
// System.out.println("Building children #" + i + " with
// instances " + Arrays.toString(tempSubBlocks[i]));
children[i] = new ID3(dataset, tempSubBlocks[i], tempRemainingAttributes);
// Important code: do this recursively
children[i].buildTree();
} // Of if
} // Of for i
}// Of buildTree
建立树是一个递归的过程，开始的连个 if 语句便是建树的出口：子树纯洁，或者子树中的实例不足三个我们停止建树，往上级返回。在决策树概念的时候我就说过了，如果我们选择属性特点选的好，那么树形简单很容易出答案，决策属性选的不好那树就很复杂而且容易过拟合。我们来看看第 9 行的 selectBestAttribute() 选择最优属性方法。
selectBestAttribute() public int selectBestAttribute() {
splitAttribute = -1; // 被选择属性开始没有，为-1
double tempMinimalEntropy = 10000; // 最小熵
double tempEntropy; // 熵
for (int i = 0; i < availableAttributes.length; i++) { // 从可以使用的条件属性中去选，称为根节点的不用了
tempEntropy = conditionalEntropy(availableAttributes[i]); // 这个方法去计算这个条件的熵
if (tempMinimalEntropy > tempEntropy) {
tempMinimalEntropy = tempEntropy;
splitAttribute = availableAttributes[i]; // 把最优标记传给splitAttribute
} // Of if
} // Of for i
return splitAttribute;
}// Of selectBestAttribute
注意啊这里面还有一个非常重要的方法那便是条件熵的计算方法
conditionalEntropy（） public double conditionalEntropy(int paraAttribute) { // 这个条件是固定的
// Step 1. 统计
int tempNumClasses = dataset.numClasses(); // 决策类的个数
int tempNumValues = dataset.attribute(paraAttribute).numValues(); // 这个条件属性的值有几个：outlook 有三个
int tempNumInstances = availableInstances.length; // 建立树没使用的实例
double[] tempValueCounts = new double[tempNumValues]; // 统计这个条件属性在不同的值下的实例数
double[][] tempCountMatrix = new double[tempNumValues][tempNumClasses]; // 你想想这个矩阵可以装的是晴天打篮球的人数。
int tempClass, tempValue;
for (int i = 0; i < tempNumInstances; i++) { //从没有使用的实例开始统计
tempClass = (int) dataset.instance(availableInstances[i]).classValue(); // 记录这个实例的决策类
tempValue = (int) dataset.instance(availableInstances[i]).value(paraAttribute); // 记录这个实例的条件属性天气是什么。晴天
tempValueCounts[tempValue]++;// 对应的晴天++
tempCountMatrix[tempValue][tempClass]++; // 晴天打球情况++
} // Of for i
// Step 2.
double resultEntropy = 0; // 结果熵（经验熵）
double tempEntropy, tempFraction; // 熵，分数
for (int i = 0; i < tempNumValues; i++) {
if (tempValueCounts[i] == 0) {
continue;
} // Of if
tempEntropy = 0;
for (int j = 0; j < tempNumClasses; j++) {
tempFraction = tempCountMatrix[i][j] / tempValueCounts[i]; // 打球 9/14 ,不打 6/14
if (tempFraction == 0) {
continue;
} // Of if
tempEntropy += -tempFraction * Math.log(tempFraction);
} // Of for j
resultEntropy += tempValueCounts[i] / tempNumInstances * tempEntropy;
} // Of for i
return resultEntropy;
}// Of conditionalEntropy
信息增益 = 信息熵 - 条件熵 我们在决策树概念中推导过了，主要变化是在条件熵，所以我们要让信息增益最大，条件熵应该最小。所以我们在编程的情况下通常不去计算信息熵，我们只比较大小的话不用去关心信息熵。第一个 for 循环就是初始化条件熵二维数组，记录了可以使用的数据中不同条件值的数量。具体化一下 tempCountMatrix 数组：
我们用上面的表来计算一下年龄的条件熵，方便理解。tempCountMatrix 数组在第一个 for 循环之后存储的数据是：
第三个 for 循环就是说如果我们老年人的类型全部为是，那么就跳过不用计算了，条件熵为 0 。外层的 for 循环就是针对每一个具体的决策属性：青年，中年，老年。第二个 for 循环我们就去计算条件熵。先计算分数部分，比如青年有 5 个人，其中的类别为是： 2 5 frac{2}{5} 52，类别为否： 3 5 frac{3}{5} 53 然后根据公式计算就可以了。返回回去，我们通过selectBestAttribute() 方法一比较，选择最小的条件熵即可以啦。
我们已经获得了最优条件该分割数据建树了，注意啊此时我们回到了buildTree 方法中了。
selectBestAttribute(); // 最优条件属性选择 int[][] tempSubBlocks = splitData(splitAttribute); // 子块 children = new ID3[tempSubBlocks.length];
下面这一站沿途的风景是根据我们的最优属性对剩下数据集的分割，来仔细欣赏一下吧！
splitDatapublic int[][] splitData(int paraAttribute) { // outlook为例
int tempNumValues = dataset.attribute(paraAttribute).numValues(); // 晴，阴，雨天 3 种
// System.out.println("Dataset " + dataset + "rn");
// System.out.println("Attribute " + paraAttribute + " has " +
// tempNumValues + " values.rn");
int[][] resultBlocks = new int[tempNumValues][]; // 结果块[晴，阴，雨][]
int[] tempSizes = new int[tempNumValues];// 大小为条件属性的具体值的种类，阴天晴天雨天
// 遍历每一个块的尺寸，为下面分配空间
int tempValue;
for (int i = 0; i < availableInstances.length; i++) {
tempValue = (int) dataset.instance(availableInstances[i]).value(paraAttribute);
tempSizes[tempValue]++;// 对应的天气++
} // Of for i
// 分配空间
for (int i = 0; i < tempNumValues; i++) {
resultBlocks[i] = new int[tempSizes[i]];
} // Of for i
// 遍历填充
Arrays.fill(tempSizes, 0);
for (int i = 0; i < availableInstances.length; i++) {
tempValue = (int) dataset.instance(availableInstances[i]).value(paraAttribute);//这是晴天
// 赋值数据
resultBlocks[tempValue][tempSizes[tempValue]] = availableInstances[i];
tempSizes[tempValue]++;
} // Of for i
return resultBlocks;
}// Of splitData
这里非常简单，resultBlock是这么存储的，就是把剩下的实例分配到这三个块中然后我们在建立子树。
我们分完数据块又回到了 buildTree 这趟车，下面便是生成孩子，我们这图有三个孩子喽。下面的代码就是减去我们使用过的属性。在这里我们已经使用过年龄这一个属性了，那么下次在细分子树的时候就不用它，在剩余属性中选择最优属性。下面来看看是如何构建子树的。
public ID3(Instances paraDataset, int[] paraAvailableInstances, int[] paraAvailableAttributes) {
// 复制其引用，而不是克隆可用的实例。
dataset = paraDataset;
availableInstances = paraAvailableInstances;
availableAttributes = paraAvailableAttributes;
// 初始化
children = null;
// 简单投票贴标签
label = getMajorityClass(availableInstances);
//判断它是否是纯的
pure = pureJudge(availableInstances);
}// Of the second constructor
我们是通过一个 for 循环依次调用这个方法，dataset 这个数据集是没有改变的，我们把剩余的实例不是分成几个块了吗，然后就把这些数据分给第二个参数 paraAvailableInstance[],后面的 paraAvailableAttributes [] 就是剩下的条件属性性：有工作，有房子，信贷情况。然后便是获得主要标签，pure判断这个块纯不纯了。到这里我们树就已经建成了。旅途快要到终点站了，大家要准备出站了哟。
精度预测 public double test(Instances paraDataset) {
double tempCorrect = 0;
for (int i = 0; i < paraDataset.numInstances(); i++) {
if (classify(paraDataset.instance(i)) == (int) paraDataset.instance(i).classValue()) {
tempCorrect++;
} // Of i
} // Of for i
return tempCorrect / paraDataset.numInstances();
}// Of test
返回的个数就是你 判断正确 t / 总数n。
public int classify(Instance paraInstance) {
if (children == null) {
return label;
} // Of if
ID3 tempChild = children[(int) paraInstance.value(splitAttribute)];
if (tempChild == null) {
return label;
} // Of if
return tempChild.classify(paraInstance);
}// Of classify
这个就是分类的浏览过程了，我们开始从头出发，然后一个一个往下面去找孩子，我们只希望找到叶子结点，只有在叶子结点我们分类才算结束，获得标签。程序就基本分析完了，不懂请你留言。
