机器学习实验报告67446

1、精选文档决策树算法、决策树算法简介:决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先 对数据进行处理，利用归纳算法生成可读的规则和决策树， 然后使用决策对新数 据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任 意实例进行判定。其中决策树(Decision Tree)是一种简单但是广泛使用的分类 器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。决策数有两大优点：1)决策树模型可以读性好，具有描述性，有助于人工分析；2)效率高， 决策树只需要一次构建，反复使用，每一次预测的最大

2、计算次数不超过决策树的 深度。决策树算法构造决策树来发现数据中蕴涵的分类规则.如何构造精度高、规模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步， 决策树的生成：由训练样本集生成决策树的过程。 一般情况下，训练样本数据集 是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第 二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正和修下的过程，主要是用新的样本数扼集(称为测试数据集)中的数据校验决策 树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除、决策树方法最早产生于上世纪 60年代，到70年代末。由J Ross Quinian提

3、 出了 ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。 C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、 派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。本节将就ID3算法展开分析和实现。ID3算法：ID3算法最早是由罗斯昆(J. Ross Quinian)于1975年在悉尼大学提出的一 种分类预测算法，算法的核心是“信息熵”。ID3算法通过计算每个属性的信息 增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标 准，重复这个过程，直至生成一个能完美分类训练样例的决策树。在ID3算法中，决策节点属性的选择运用

4、了信息论中的熵概念作为启发式函 数。在这种属性选择方法中，选择具有最大信息增益(in formation gain)的属性作为当前划分节点。通过这种方式选择的节点属性可以保证决策树具有最小的分 枝数量，使得到的决策树冗余最小。伪代码：Exatnpies即训练样例集“帀啓刃_口估话W已是这棵W要预测的冃标属#:. A曲话M伽 杲除a标属性外学习到的策皿测试的属性列表.返回能匝确分类给宦 Examples的决策树匕创建W的结点如果Examples都为正，那么返回label =+的单结点W Root如果Examples都为反，那么返回label二 的单结点树Rcof如果Atnibutes为空*那么返

5、回单箱点W Rgh l3iM=Exawpi&s中最普遍的 沧谿口7伽iw搐值否则A Ami bn res中分类Examples能力最好卓的属件J2qqf的决筆属性.4对TH的毎个可隹值片*iRoof下加一个新的分支对应测试J=片令El伽川弧,対Eng 中满足川属性值为儿的子集 如渠Eatnpl&s,为空庄这个新分支下加一个叶子结点，绪点的lab亡匸&洒戸?创 中最普遍的Fa評ftrib唤值否则圧这个新分支下加一个子W ID3 ( Examples ,Artfibnt&s-A li t结束返回Root二、实验过程1.实验数据集这个样例集中，每个属性都是离散值的，连续的属性已经被离散化。将图中 的

6、样例集转换成图2中所示的格式并保存到文件中以供项目程序读取数据。图2中“ attribute ”行所对应的是样例集中的测试属性和目标属性，以及它们属性 值。而“ data”行后面的每一行数据则对应了样例集中的一条样例。测试属性：outlook，天气情况，属性值为sunny, overcast, rainytemperature，气温，属性值为hot, mild, cool；humidity，湿度，属性值为high, normal；Windy,是否有风，属性值为TRUE, FALSE目标属性：Play,是否适合打球，属性值为yes, no。RIDoutlooktemp eraturehumidi

7、tywi ndyplay1sunnyhothighFALSEno2sunnyhothighTRUEno3overcasthothighFALSEyes4rai nymildhighFALSEyes5rai nycoolno rmalFALSEyes6rai nycoolno rmalTRUEno7overcastcoolno rmalTRUEyes8sunnymildhighFALSEno9sunnycoolno rmalFALSEyes10rai nymildno rmalFALSEyes11sunnymildno rmalTRUEyes12overcastmildhighTRUEyes13

8、overcasthotno rmalFALSEyes14rai nyhighhighTRUEno输出：图3所示为本项目最终的输出结果。项目的输出结果详细的给出了在构建决 策树的过程中候选属性的信息增益、测试属性的选取结果、测试属性的各个属性 值所对应的分支、目标属性选取结果以及目标概念 buys_computer的决策树JSON 格式输出，并使用项目生成的决策树进行预测分析。 oot4567g91011121415humidity value二highnoyes yes noyes 根据生成的xml文件画出决策树如图所示:2.实现步骤:weather.arff中读取测试样例的属性attribu

9、te和样例数据第一步：从文件data，方法void readARFF（File file实现了数据的读取这项工作。第二步：开始递归地创建决策树。首先为样例集中的每一个测试属性分配一 个权值，权值越小代表属性的重要性越高。创建决策树的过程中要计算样本的总 体熵，计算各个属性的信息增益，将信息增益值最大的属性定为测试属性（根结 点），然后开始从根节点开始递归地创建子结点。实现代码参考方法Public doublecalE ntro py （ArrayListvl nteger subset, i nt in dex。第三步：输出目标概念 weather的决策树 xml格式，此项需要引入 jaxe

10、n-1.1.1.jar包，编译整个项目并运行生成决策树。关键代码：/给定原始数据的子集（subset中存储行号），当以第index个属性为节点时计 算它的信息熵P ublic double calE ntropy (ArrayListvl nteger subset, int in dex) int sum = subset.size();double entropy = 0.0;in t info = new in tattributevalue.get(i ndex).size();for (int i = 0; i in fo.le ngth; i+)in foi = new in ta

11、ttnbutevalue.get(decatt).size();in t count = new in tattributevalue.get(i ndex).size();for (int i = 0; i sum; i+)int n = subset.get(i);String no devalue = data.get (n )i ndex;int nodeind = attributevalue.get(i ndex).i ndexOf( no devalue); countnodein d+;Stri ng decvalue = data.get (n )decatt;int dec

12、 ind = attributevalue.get(decatt).i ndexOf(decvalue); infonodein ddec in d+;for (int i = 0; i subset, Lin kedListv In teger selatt)Eleme nt ele = n ull;Supp ressWar nin gs( un checked)ListvEleme nt list = root.selectNodes( + n ame);IteratorvEleme nt iter = list.iterator();while (iter.hasNextO)ele =

13、iter. next();if (ele.attnbuteValue(value).equals(value)break;if (infoPu re(subset)ele.setText(data.get(subset.get(O)decatt); return;int mi nin dex = -1;double minEn tro py = Double.MAX_VALUE;for (i nt i = 0; i selatt.size(); i+) if (i = decatt)con ti nue;double entropy = calE ntropy (subset, selatt.

14、get(i);if (entropy attvalues = attributevalue.get(mi nin dex); for (Stri ng val : attvalues) ele.addEleme nt(no deName).addAttribute(value, val);ArrayListvI nteger al = new ArrayListvI nteger(); for (int i = 0; i subset.size(); i+)if (data.get(subset.get(i) minin dex.equals(val)al.add(subset.get(i);

15、buildDecisi on Tree( no deName, val, al, selatt);BP神经网络一、BP神经网络简介在人工神经网络发展历史中，很长一段时间里没有找到隐层的连接权值调整 问题的有效算法。直到误差反向传播算法（BP算法）的提出，成功地解决了求 解非线性连续函数的多层前馈神经网络权重调整问题。BP网络是1986年由Rumelhart和McCelland为首的科学家小组提出，是一种按 误差逆传播算法训练的多层前馈网络，是目前应用最广泛的神经网络模型之一。它的学习规则是使用最速下降法，通过反向传播来不断调 使网络的误差平方和最小。BP神经网络模型拓扑结构包隐层（hide l

16、ayer） 和输出层（output layer） 。BP网络能学习和存贮大量的输入-输出模式映射关系，而无需事前揭示描述这种 映射关系的数学方程。 整网络的权值和阈值， 括输入层（input ）、二、算法原理由于传统的感知器和线性神经网络有自身无法克服的缺陷，它们都不能解决线性不可分问题，因此在实际应用过程中受到了限制。而BP网络却拥有良好的繁泛化能力、容错能力以及非线性映射能力。因此成为应用最为广泛的一种神经 网络。BP算法的基本思想是把学习过程分为两个阶段：第一阶段是信号的正向传播过程；输入信息通过输入层、隐层逐层处理并计算每个单元的实际输出值;二阶段是误差的反向传递过程；若在输入层未能得

17、到期望的输出值，则逐层递归 的计算实际输出和期望输出的差值（即误差），以便根据此差值调节权值。这种 过程不断迭代，最后使得信号误差达到允许或规定的范围之内。IA12基于BP算法的多层前馈型网络模型的拓扑结构如上图所示。0(Ot * O|.厶4h、仝y “7-4= Q片丄宀r-矣ISO几T X九JX,XiSiBP算法的数学描述:三层BP前馈网络的数学模型如上图所示。 三层前馈网中，输入向量为：X(X1 ,X2,., Xi ,.,Xn)T ；隐层 输入向 量为：丫 (,y2,.,yj,.ym)T ；输出层输出向量为：。(01,02,.,0k,.0i )T ；期望输出向量为：d(d1,d2,.dk,

18、.di )T。输入层到隐层之间的权值矩阵用表示,V (v1,v2,.vj ,.vm)Y，其中列向量Vj为隐层第j个神经元对应的权向量;隐层到输出层之间的权值矩阵用W表示，W (w1,w2,.wk,.W|)，其中列向量Wk为输出层第k个神经元对应的权向量。F面分析各层信号之间的数学关系。对于输出层，有Vjf(netj), jnetjVij Xi, j1,2,., m1,2,.,m对于隐层，有Okf (netk),kmnetkWjk Vi, k 1,2,.,lj 01,2,.,l1以上两式中，转移函数f(x)均为单极性Sigmoid函数：f(x) 一1 ef(x)具有连续、可导的特点，且有f(x)

19、f(x)1f(x)以上共同构成了三层前馈网了的数学模型。当网络输出和期望输出不相等时，存在输出误差 E如下:1 1 mE 2(d o)2 2j0(dk Ok)2将以上误差定义式展开至隐层，有E 2 dk f(netj)22 k 1m2f ( WjkyJj 0进一步展开至输入层，有E 2 dk fwjkf(netj)22 k 1j 0ldkk 1nn2fWjkf ( VjXi)i 0i 0由上式可以看出，网络输入误差是两层权值W和V的函数，因此调整权值可以改变误差E。显然，调整权值的原则是使误差不断的减小,因此应使权值的调整量与误差的负梯度成正比，即:WjkVj, j 0,1,2,.m;k1,2

20、,.,lWjk,i 0,1,2,., n; j 1,2,.,mVj式中负号表示梯度下降，常数（0,1）表示比例系数，在训练中反映了学习速率。容易看出，BP学习算法中，各层权值调整公式形式上都是一样的，均有3个因素决定，即：学习速率、本层误差信号和本层输入信号X/Y。其中输出层误差信号同网络的期望输出与实际输出之差有关， 直接反映了输出误差，而各隐层的误差信号与前面各层的误差信号都有关，是从输出层开始逐层反传过来的。三、实验 实验输入与输出：本次实验做的是一个数字分类的实验，目的是对于任意的整数（int型），BPNN在经过训练之后，能够准确地判断出它是奇数还是偶数，正数还是负数。首先对于训练的样

21、本（是随机生成的数字），将它转化为一个32位的向量，向量的每个分量就是其二进制形式对应的位上的0或1。将目标输出视作一个 4维的向量，1,0,0,0代表正奇数，0,1,0,0代表正 偶数，0,0,1,0代表负奇数，0,0,0,1代表负偶数。训练样本为1000个，学习200次。实验结果：如图所示，BPNN在经过训练之后，能够准确地判断出它是奇数还是偶数，正数还是负 数。TciL ( L 卩avfl Applicatonj t:Pf03fQi1n FlciJflYQ/e8、binjvflw.e泌=01=1月 1：日 下*=9:1器2 ) 训荡完申.下面请输入T、任蔦緻字，W经网络将自动判断它杲正数还杲貝S,奇数还皋翩。1212 是1J是一卜致奇歎3333是一平正奇散9b9&是一HE腳关键代码:p rivate void forward(double layerO, double layer1, double weight)/ threshold un it.layer00 = 1.0;for (int j = 1, le n = Iayer1.le ngth; j != len; +j) double