毕业论文final-金雨欢

上海大学硕士学位论文 2008年5月

第二章 机器学习算法

机器学习是人工智能研究较为年轻的分支,它的发展过程大体上分为四个时期。第一阶段是20世纪50年代中叶到60年代中叶,属于热烈时期。在这个时期,所研究的是“没有知识”的学习,即“无知”学习。其研究目标是各类自组织系统和自适应系统,其主要研究方法是不断修改系统的控制参数和改进系统的执行能力,不涉及与具体任务有关的知识。本阶段的代表性工作是:塞缪尔(Samuel)的下棋程序。但这种学习的结果远不能满足人们对机器学习系统的期望。第二阶段是在60年代中叶到70年代中叶,被称为机器学习的冷静时期。本阶段的研究目标是模拟人类的概念学习过程,并采用逻辑结构或图结构作为机器内部描述。本阶段的代表性工作有温斯顿(Winston)的结构学习系统和海斯罗思(Hayes-Roth)等的基本逻辑的归纳学习系统。第三阶段从20世纪70年代中叶到80年代中叶,称为复兴时期。在此期间,人们从学习单个概念扩展到学习多个概念,探索不同的学习策略和方法,且在本阶段已开始把学习系统与各种应用结合起来,并取得很大的成功,促进机器学习的发展。1980年,在美国的卡内基—梅隆(CMU)召开了第一届机器学习国际研讨会,标志着机器学习研究已在全世界兴起。[8]

2.1 决策树算法

决策树学习是一种逼近离散值函数的算法，对噪声数据有很好的健壮性，且能够学习析取表达式，是最流行的归纳推理算法之一，已经成功应用到医疗诊断、评估贷款申请的信用风险、雷达目标识别、字符识别、医学诊断和语音识别等广阔领域[36,37]。

决策树分类算法使用训练样本集合构造出一棵决策树，从而实现了对样本空间的划分。当使用决策树对未知样本进行分类时，由根结点开始对该样本的属性逐渐测试其值，并且顺着分枝向下走，直到到达某个叶结点，此叶结点代表的类即为该样本的类。例如，图2.1即为一棵决策树，它将整个样本空间分为三类。如果一个样本属性A的取值为a2,属性B的取值为b2，属性C的取值为c1那么

6

上海大学硕士学位论文 2008年5月

它属于类1[38]。

图2.1 一颗决策树实例

为了避免过度拟和现象的出现，在决策树的生成阶段要对决策树进行必要修剪。常用的修剪技术有预修剪(pre-pruning)和后修剪(post-pruning)两种。决策树的质量更加依靠好的停止规则而不是划分规则。[39]获取大小合适的树常用的方法是后剪枝。后剪枝法主要有①训练和验证集法，②使用统计的方法，③最小描述长度准则。其它的剪枝方法有：①限制最小结点规模，②两阶段研究，③不纯度的阀值，④将树转变为规则，⑤Tree reduction。没有一种剪枝方法明显优于其它方法。

寻找一棵最优决策树主要解决以下三个最优化问题:①生成最少数目的叶子，②生成的每个叶子的深度最小，③生成的决策树叶子最少且每个叶子的深度最小。以上三个问题均已被证明为NP难题，所以,决策树算法一般只能找到一棵近似最优决策树[40]。

常用的决策树算法由CART，ID3，C4.5算法，随机树算法，在下面，对本文中用到的决策树算法进行了详细介绍。

2.1.1 C4.5算法[41]

设S为训练集样本总数，共有m类样本Ci,(i?1,2,3...,m)，Si为类Ci中的样本数，计算公式为：

7

上海大学硕士学位论文 2008年5月

mI(s1,s2,...sm)???pilog2(pi)i?1 (2.1.1.1)

其中，其中pi是任意样本属于Ci的概率，可用Si/S来估计。

设属性X具有v个值{x1,x2,...,xv}，它将S分成v个子集{s1,s2,...,sv}，其中

Sj包含S中这样的一些样本，它们在属性X上具有值Xj(j?1,2,...,v)。以属性X为分类所需的期望熵（条件熵）是：

vE(X)??j?1s1j?...?smjsI(s1j,...,smj)

m (2.1.1.2)

其中sij是子集Sj中属于类Ci的样本数，I(s1j,...,smj)???pijlog2(pij)

i?1，

pij?sijsj是sj中的样本属于Ci的概率。

属性X的信息增益函数为：

Gain(X)?I(s1,s2,...,sm)?E(X) (2.1.1.3)

信息增益函数对于那些可能产生多分枝的测试倾向于生产大的函数值，但是输出分枝多，并不表示该测试对末知的对象具有更好的预测效果，信息增益率函数可以弥补这个缺陷“信息增益率”是为了去除多分枝属性的影响而对信息增益的一种改进。使用“信息增益率函数”，它同时考虑了每一次划分所产生的子结点的个数和每个子结点的大小（包含的数据实例的个数），考虑的对象主要是一个个地划分，而不再考虑分类所蕴涵的信息量，属性X的信息增益函数为：

A(X)?Gain(X)I(s1,s2,...,sv) (2.1.1.4)

其中v为该节点的分枝数，si为第i个分枝下的记录个数。

依次计算每个属性的信息增益Gain(X)以及信息增益率A(X)，选取信息增益率最大的，但同时获取的信息增益又不低于所有属性平均值的属性作为测试属性，以该属性作为结点，属性的每一个分布引出一个分枝，据此划分样本。要是节点中所有样本都在同一个类，则该节点成为树叶，以该客户类别标记该树叶。如此类推，直到子集中的数据记录在主属性上取值都相同，或没有属性可再供划

8

上海大学硕士学位论文 2008年5月

分使用，递归地形成初始决策树。另外，在节点处记下符合条件的统计数据：该分枝总数、有效数、中止数和失效数。

之所以选取信息增益率大而信息增益不低于平均值的属性，是因为高信息增益率保证了高分枝属性不会被选取，从而决策树的树型不会因某节点分枝太多而过于松散。过多的分枝会使得决策树过分地依赖某一属性，而信息增益不低于平均值保证了该属性的信息量，使得有利于分类的属性更早地出现。

得到了完全生长的初始决策树后，为了除去噪声数据和孤立点引起的分枝异常，可采用后剪枝算法对生成的初始决策树进行剪枝，并在剪枝过程中使用一种悲观估计来补偿树生成时的乐观偏差。对决策树上的每个非叶子结点，计算该分枝节点上的子树被剪枝可能出现的期望错误率。然后，使用每个分枝的错误率，结合沿每个分枝观察的权重评估，计算不对该节点剪枝的期望错误率。如果剪去该节点导致较高的期望错误率，则保留该子树；否则剪去该子树，最后得到具有最小期望错误率的决策树。

2.1.2 随机决策树算法[42]

设属性集X?{F1,...,Fk,D}为建树提供结构，其中Fi(i?1,2,...,k)是非决策属性，决

策属性D(d1,d2,...,dm)是一列有效的类别。Fi(x)表示记录x的属性Fi的值,具体结构描述如下：树中的每个结点表示一个问题;每个分支对应结点分裂属性Fi的可能取值Fi(x)。随机决策树的构造过程:对根结点和分支结点随机的从属性集合中选择分裂属性,在一条分支路径上离散属性仅出现一次,连续属性可以出现多次。且在以下3种情况下停止树的构造：树的高度满足预先设定的阈值;分支结点的事例数太小以至于不能给出一个有统计意义的测试;其它任何一个属性测试都不能更好地分类。在后2种情况下,分类结果标记为训练数据集中最普通的类,或是出现概率最高的类。当对事例X进行分类时,以各随机树输出的后验概率均值最大的类di(i?1,2,...,m)为预测类。下面详细介绍随机决策树的深度选择和数目的选择及其分类。

(1)选择树的深度。使用多个随机树的主要特色是多样性导致较高的分类准确率,多样性不与深度成正比关系。研究表明,当i=k/2时得到最大路径数,随机决策

9