机器学习实验报告

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