火咖

.

.

决策树算法

一、决策树算法简介：

决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先

对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数

据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树方

法的基本思想是：利用训练集数据自动地构造决策树，然后根据这个决策树对任

意实例进行判定。其中决策树（DecisionTree）是一种简单但是广泛使用的分类

器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。决策数有两

大优点：1）决策树模型可以读性好，具有描述性，有助于人工分析；2）效率高，

决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的

深度。

决策树算法构造决策树来发现数据中蕴涵的分类规则．如何构造精度高、规

模小的决策树是决策树算法的核心内容。决策树构造可以分两步进行。第一步，

决策树的生成：由训练样本集生成决策树的过程。一般情况下，训练样本数据集

是根据实际需要有历史的、有一定综合程度的，用于数据分析处理的数据集。第

二步，决策树的剪技：决策树的剪枝是对上一阶段生成的决策树进行检验、校正

和修下的过程，主要是用新的样本数扼集（称为测试数据集）中的数据校验决策

树生成过程中产生的初步规则，将那些影响预衡准确性的分枝剪除、

决策树方法最早产生于上世纪60年代，到70年代末。由JRossQuinlan提

出了ID3算法，此算法的目的在于减少树的深度。但是忽略了叶子数目的研究。

C4.5算法在ID3算法的基础上进行了改进，对于预测变量的缺值处理、剪枝技术、

派生规则等方面作了较大改进，既适合于分类问题，又适合于回归问题。

本节将就ID3算法展开分析和实现。

ID3算法：

ID3算法最早是由罗斯昆（inlan）于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}。

RIDoutlooktemperaturehumiditywindyplay

1sunnyhothighFALS

E

no

.

.

2sunnyhothighTRUEno

3overcas

t

hothighFALS

E

yes

4rainymildhighFALS

E

yes

5rainycoolnormalFALS

E

yes

6rainycoolnormalTRUEno

7overcas

t

coolnormalTRUEyes

8sunnymildhighFALS

E

no

9sunnycoolnormalFALS

E

yes

10rainymildnormalFALS

E

yes

11sunnymildnormalTRUEyes

12overcas

t

mildhighTRUEyes

13overcas

t

hotnormalFALS

E

yes

14rainyhighhighTRUEno

输出：

图3所示为本项目最终的输出结果。项目的输出结果详细的给出了在构建决

策树的过程中候选属性的信息增益、测试属性的选取结果、测试属性的各个属性

值所对应的分支、目标属性选取结果以及目标概念buys_computer的决策树

JSON格式输出，并使用项目生成的决策树进行预测分析。

.

.

根据生成的xml文件画出决策树如图所示：

2.实现步骤：

第一步：从文件中读取测试样例的属性attribute和样例数据

data，方法voidreadARFF(Filefile)实现了数据的读取这项工作。

第二步：开始递归地创建决策树。首先为样例集中的每一个测试属性分配一

个权值，权值越小代表属性的重要性越高。创建决策树的过程中要计算样本的总

体熵，计算各个属性的信息增益，将信息增益值最大的属性定为测试属性（根结

点），然后开始从根节点开始递归地创建子结点。实现代码参考方法publicdouble

calEntropy(ArrayListsubt,intindex)。

.

.

第三步：输出目标概念weather的决策树xml格式，此项需要引入

包，编译整个项目并运行生成决策树。

关键代码：

//给定原始数据的子集(subt中存储行号),当以第index个属性为节点时计

算它的信息熵

publicdoublecalEntropy(ArrayListsubt,intindex)

{

intsum=();

doubleentropy=0.0;

int[][]info=newint[(index).size()][];

f金融风险管理 or(inti=0;i<;i++)

info[i]=newint[(decatt).size()];

int[]count=newint[(index).size()];

for(inti=0;i

{

intn=(i);

Stringnodevalue=(n)[index];

intnodeind=(index).indexOf(nodevalue);

count[nodeind]++;

Stringdecvalue=(n)[decatt];

intdecind=(decatt).indexOf武汉到丽江 (decvalue);

info[nodeind][decind]++;

}

for(inti=0;i<;i++)

{

entropy+=getEntropy(info[i])*count[i]/sum;

}

returnentropy;

}

//构建决策树

publicvoidbuildDecisionTree(Stringname,Stringvalue,

ArrayListsubt,LinkedListlatt)

{

Elementele=null;

.

.

SuppressWarnings("unchecked")

Listlist=Nodes("//"+name);

Iteratoriter=or();

while(t())

{

ele=();

if(uteValue("value").equals(value))

break;

}

if(infoPure(subt))

{

t(((0))[decatt]);

return;

}

intminIndex=-1;

doubleminEntropy=_VALUE;

for(inti=0;i<();i++){

if(i==decatt)

continue;

doubleentropy=calEntropy(subt,(i));

if(entropy

{

minIndex=(i);

minEntropy=entropy;

}

}

StringnodeName=(minIndex);

(newInteger(minIndex));

ArrayListattvalues=(minIndex);

for(Stringval:attvalues){

ment(nodeName).addAttribute("value",val);

ArrayListal=newArrayList();

for(inti=0;i<();i++)

{

.

.

if(((i))[minIndex].equals(val))

{

((i));

}

}

buildDecisionTree(nodeName,val,al,latt);

}

}

.

.

BP神经网络

一、BP神经网络简介

在人工神经网络发展历史中，很长一段时间里没有找到隐层的连接权值调整

问题的有效算法。直到误差反向传播算法（BP算法）的提出，成功地解决了求

解非线性连续函数的多层前馈神经网络权重调整问题。

BP网络是1986年由Rumelhart和McCelland为首的科学家小组提出，是一种按

误差逆传播算法训练的多层前馈网络，是目前应用最广泛的神经网络模型之一。

BP网络能学习和存贮大量的输入-输出模式映射关系，而无需事前揭示描述这种

映射关系的数学方程。它的学习规则是使用最速下降法，通过反向传播来不断调

整网络的权值和阈值，使网络的误差平方和最小。BP神经网络模型拓扑结构包

括输入层（input）、隐层(hidelayer)和输出层(outputlayer)。

二、算法原理

由于传统的感知器和线性神经网络有自身无法克服的缺陷，它们都不能解决

线性不可分问题，因此在实际应用过程中受到了限制。而BP网络却拥有良好的

繁泛化能力、容错能力以及非线性映射能力。因此成为应用最为广泛的一种神经

网络。

BP算法的基本思想是把学习过程分为两个阶段：第一阶段是信号的正向传

播过程；输入信息通过输入层、隐层逐层处理并计算每个单元的实际输出值；第

二阶段是误差的反向传递过程；若在输入层未能得到期望的输出值，则逐层递归

的计算实际输出和期望输出的差值（即误差），以便根据此差值调节权值。这种

过程不断迭代，最后使得信号误差达到允许或规定的范围之内。

.

.

基于BP算法的多层前馈型网络模型的拓扑结构如上图所示。

BP算法的数学描述：三层BP前馈网络的数学模型如上图所示。三层前馈网

中，输入向量为：T

ni

xxxxX),...,,...,,(

21

；隐层输入向量为：

T

mj

yyyyY),...,...,,(

21

；输出层输出向量为：T

lk

ooooO),...,...,,(

21

；期望输出

向量为：T

lk

ddddd),...,...,(

21

。输入层到隐层之间的权值矩阵用V表示，

Y

mj

vvvvV),...,...,(

21

，其中列向量

j

v为隐层第j个神经元对应的权向量；隐层到

输出层之间的权值矩阵用W表示，

),...,...,(

21lk

wwwwW

，其中列向量

k

w

为输出

层第k个神经元对应的权向量。

下面分析各层信号之间的数学关系。

对于输出层，有





mjxvnet

mjnetfy

iijj

jj

,...,2,1,

,...,2,1),(

对于隐层，有

.

.









m

j

ijkk

kk

lkywnet

lknetfO

0

,...,2,1,

,...,2,1),(

以上两式中，转移函数f(x)均为单极性Sigmoid函数：

xe

xf





1

1

)(

f(x)具有连续、可导的特点，且有

)](1)[()('xfxfxf

以上共同构成了三层前馈网了的数学模型。

当网络输出和期望输出不相等时，存在输出误差E如下：







m

j

kk

ododE

0

22)(

2

1

)(

2

1

将以上误差定义式展开至隐层，有

2

110

2)]([

2

1

)]([

2

1





l

k

l

k

m

j出纳是干什么的

jjkkjk

ywfdnetfdE

进一步展开至输入层，有

2

1100

2

0

]})([{

2

1

)]}([{

2

1





l

k

l

k

n

i

n

i

iijjkkj

m

j

jkk

xvfwfdnetfwfdE

由上式可以看出，网络输入误差是两层权值W和V的函数，因此调整权值

可以改变误差E。

显然，调整权值的原则是使误差不断的减小，因此应使权值的调整量与误差

的负梯度成正比，即：

mjni

v

E

v

lkmj

w

E

w

ij

ij

jk

jk

,...,2,1;,...,2,1,0,

,...,2,1;,...2,1,0,





















式中负号表示梯度下降，常数

)1,0(

表示比例系数，在训练中反映了学习

速率。

.

.

容易看出，BP学习算法中，各层权值调整公式形式上都是一样的，均有3

个因素决定，即：学习速率、本层误差信号和本层输入信号X/Y。其中输出层误

差信号同网络的期望输出与实际输出之差有关，直接反映了输出误差，而各隐层

的误差信号与前面各层的误差信号都有关，是从输出层开始逐层反传过来的。

三、实验

实验输入与输出：

本次实验做的是一个数字分类的实验，目的是对于任意的整数（int型），BPNN在经

过训练之后，能够准确地判断出它是奇数还是偶数，正数还是负数。首先对于训练的样本（是

随机生成的数字），将它转化为一个32位的向量，向量的每个分量就是其二进制形式对应

的位上的0或1。将目标输出视作一个4维的向量，[1,0,0,0]代表正奇数，[0,1,0,0]代表正偶

数，[0,0,1,0]代表负奇数，[0,0,0,1]代表负偶数。

训练样本为1000个，学习200次。

实验结果：

如图所示，BPNN在经过训练之后，能够准确地判断出它是奇数还是偶数，正数还是负

数。

关键代码：

privatevoidforward(double[]layer0,double[]layer1,double[][]weight){

//thresholdunit.

layer0[0]=1.0;

for(intj=1,len=;j!=len;++j){

doublesum=0;

for(inti=0,len2=;i!=len2;++i)

sum+=weight[i][j]*layer0[i];

.

.

layer1[j]=sigmoid(sum);

}

}

/**

*Calculateoutputerror.

*/

privatevoidoutputErr(){

doubleerrSum=0;

for(intidx=1,len=;idx!=len;++idx){

doubleo=output[idx];

optDelta[idx]=o*(1d-o春节贴对联图片 )*(target[idx]-o);

errSum+=(optDelta[idx]);

}

optErrSum=errSum;

}

/**

*Calculatehiddenerrors.

*/

privatevoidhiddenErr(){

doubleerrSum=0;

for(intj=1,len=;j!=len;++j){

doubleo=hidden[j];

doublesum=0;

for(intk=1,len2=;k!=len2;++k)

sum+=hidOptWeights[j][k]*optDelta[k];

hidDelta[j]=o*(1d-o)*sum;

errSum+=(hidDelta[j]);

}

hidErrSum=errSum;

}

.

.