Play，是否适合打球，属性值为{yes, no}。 RID 1 2 3 4 5 6 7 8 9 10 11 12 13 14 输出： 图 3 所示为本项目最终的输出结果。 项目的输出结果详细的给出了在构建决 策树的过程中候选属性的信息增益、测试属性的选取结果、测试属性的各个属性 值所对应的分支、 目标属性选取结果以及目标概念 buys_computer 的决策树 JSON 格式输出，并使用项目生成的决策树进行预测分析。 outlook sunny sunny overcast rainy rainy rainy overcast sunny sunny rainy sunny overcast overcast rainy temperature hot hot hot mild cool cool cool mild cool mild mild mild hot high humidity high high high high normal normal normal high normal normal normal high normal high windy FALSE TRUE FALSE FALSE FALSE TRUE TRUE FALSE FALSE FALSE TRUE TRUE FALSE TRUE play no no yes yes yes no yes no yes yes yes yes yes no
ele.setText(data.get(subset.get(0))[decatt]); return; } int minIndex = -1; double minEntropy = Double.MAX_VALUE; for (int i = 0; i < selatt.size(); i++) { if (i == decatt) continue; double entropy = calEntropy(subset, selatt.get(i)); if (entropy < minEntropy) { minIndex = selatt.get(i); minEntropy = entropy; } } String nodeName = attribute.get(minIndex); selatt.remove(new Integer(minIndex)); ArrayList<String> attvalues = attributevalue.get(minIndex); for (String val : attvalues) { ele.addElement(nodeName).addAttribute("value", val); ArrayList<Integer> al = new ArrayList<Integer>(); for (int i = 0; i < subset.size(); i++) { if (data.get(subset.get(i))[minIndex].equals(val)) { al.add(subset.get(i)); } } buildDecisionTree(nodeName, val, al, selatt); } }
根据生成的 xml 文件画出决策树如图所示：
2.实现步骤：
第一步：从文件 weather.arff 中读取测试样例的属性 attribute 和样例数据 data，方法 void readARFF(File file)实现了数据的读取这项工作。 第二步： 开始递归地创建决策树。首先为样例集中的每一个测试属性分配一 个权值， 权值越小代表属性的重要性越高。创建决策树的过程中要计算样本的总 体熵，计算各个属性的信息增益，将信息增益值最大的属性定为测试属性（根结 点） ， 然后开始从根节点开始递归地创建子结点。 实现代码参考方法 public double calEntropy(ArrayList<Integer> subset, int index)。 第 三 步 ： 输 出 目 标 概 念 weather 的 决 策 树 xml 格 式 ， 此 项 需 要 引 入 jaxen-1.1.1.jar 包，编译整个项目并运行生成决策树。 关键代码： // 给定原始数据的子集(subset 中存储行号),当以第 index 个属性为节点时计 算它的信息熵 public double calEntropy(ArrayList<Integer> subset, int ine entropy = 0.0; int[][] info = new int[attributevalue.get(index).size()][]; for (int i = 0; i < info.length; i++)
BP 神经网络
一、BP 神经网络简介 在人工神经网络发展历史中， 很长一段时间里没有找到隐层的连接权值调整 问题的有效算法。直到误差反向传播算法（BP 算法）的提出，成功地解决了求 解非线性连续函数的多层前馈神经网络权重调整问题。 BP 网络是 1986 年由 Rumelhart 和 McCelland 为首的科学家小组提出，是一种按 误差逆传播算法训练的多层前馈网络，是目前应用最广泛的神经网络模型之一。 BP 网络能学习和存贮大量的输入-输出模式映射关系，而无需事前揭示描述这种 映射关系的数学方程。 它的学习规则是使用最速下降法，通过反向传播来不断调 整网络的权值和阈值，使网络的误差平方和最小。BP 神经网络模型拓扑结构包 括输入层（input）、隐层(hide layer)和输出层(output layer)。 二、算法原理 由于传统的感知器和线性神经网络有自身无法克服的缺陷， 它们都不能解决 线性不可分问题，因此在实际应用过程中受到了限制。而 BP 网络却拥有良好的 繁泛化能力、 容错能力以及非线性映射能力。因此成为应用最为广泛的一种神经 网络。 BP 算法的基本思想是把学习过程分为两个阶段：第一阶段是信号的正向传 播过程；输入信息通过输入层、隐层逐层处理并计算每个单元的实际输出值；第 二阶段是误差的反向传递过程； 若在输入层未能得到期望的输出值，则逐层递归 的计算实际输出和期望输出的差值（即误差），以便根据此差值调节权值。这种 过程不断迭代，最后使得信号误差达到允许或规定的范围之内。
决策树算法
一、决策树算法简介：
决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先 对数据进行处理， 利用归纳算法生成可读的规则和决策树，然后使用决策对新数 据进行分析。 本质上决策树是通过一系列规则对数据进行分类的过程。决策树方 法的基本思想是： 利用训练集数据自动地构造决策树，然后根据这个决策树对任 意实例进行判定。其中决策树（Decision Tree）是一种简单但是广泛使用的分类 器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。决策数有两 大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高， 决策树只需要一次构建， 反复使用，每一次预测的最大计算次数不超过决策树的 深度。 决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规 模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步， 决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集 是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第 二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正 和修下的过程，主要是用新的样本数扼集（称为测试数据集）中的数据校验决策 树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除、 决策树方法最早产生于上世纪 60 年代，到 70 年代末。由 J Ross Quinlan 提 出了 ID3 算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。 C4.5 算法在 ID3 算法的基础上进行了改进， 对于预测变量的缺值处理、 剪枝技术、 派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。 本节将就 ID3 算法展开分析和实现。 ID3 算法： ID3 算法最早是由罗斯昆（J. Ross Quinlan）于 1975 年在悉尼大学提出的一 种分类预测算法，算法的核心是“信息熵”。ID3 算法通过计算每个属性的信息 增益， 认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标 准，重复这个过程，直至生成一个能完美分类训练样例的决策树。 在 ID3 算法中， 决策节点属性的选择运用了信息论中的熵概念作为启发式函 数。 在这种属性选择方法中，选择具有最大信息增益（information gain）的属性
作为当前划分节点。 通过这种方式选择的节点属性可以保证决策树具有最小的分 枝数量，使得到的决策树冗余最小。 伪代码：
二、实验过程 1.实验数据集
这个样例集中，每个属性都是离散值的，连续的属性已经被离散化。将图中 的样例集转换成图 2 中所示的格式并保存到文件中以供项目程序读取数据。图 2 中“@attribute”行所对应的是样例集中的测试属性和目标属性，以及它们属性 值。而“@data”行后面的每一行数据则对应了样例集中的一条样例。 测试属性： outlook，天气情况，属性值为{sunny, overcast, rainy}； temperature，气温，属性值为{hot, mild, cool}； humidity，湿度，属性值为{high, normal}； Windy，是否有风，属性值为{TRUE, FALSE}。 目标属性：
info[i] = new int[attributevalue.get(decatt).size()]; int[] count = new int[attributevalue.get(index).size()]; for (int i = 0; i < sum; i++) { int n = subset.get(i); String nodevalue = data.get(n)[index]; int nodeind = attributevalue.get(index).indexOf(nodevalue); count[nodeind]++; String decvalue = data.get(n)[decatt]; int decind = attributevalue.get(decatt).indexOf(decvalue); info[nodeind][decind]++; } for (int i = 0; i < info.length; i++) { entropy += getEntropy(info[i]) * count[i] / sum; } return entropy; } // 构建决策树 public void buildDecisionTree(String name, String value, ArrayList<Integer> subset, LinkedList<Integer> selatt) { Element ele = null; @SuppressWarnings("unchecked") List<Element> list = root.selectNodes("//" + name); Iterator<Element> iter = list.iterator(); while (iter.hasNext()) { ele = iter.next(); if (ele.attributeValue("value").equals(value)) break; } if (infoPure(subset)) {