
数据挖掘原理算法及应用第4章分类和预测ppt课件.ppt
215页第第4章章 分类和预测分类和预测第第4 4章章 分分 类类 和和 预预 测测4.1 分类和预测的基本概念和步骤4.2 基于相似性的分类算法4.3 决策树分类算法4.4 贝叶斯分类算法4.5 人工神经网络(ANN)4.6 支持向量机4.7 预测4.8 预测和分类中的准确率、误差的度量4.9 评估分类器或预测器的准确率4.10 小结.第第4章章 分类和预测分类和预测 4.1 分类和预测的基本概念和步骤 银行贷款员需要分析数据,搞清楚哪些贷款申请者是“安全的”,银行的“风险〞是什么AllElectronics的市场经理需要数据分析,以便帮助他猜测具有某些特征的顾客是否会购买一台新的计算机医学研究者希望分析乳腺癌数据,预测病人应当接受三种具体治疗方案中的哪一种 .第第4章章 分类和预测分类和预测 数据分类是一个两步过程,如图4-1所示的贷款应用数据,第一步,建立描述预先定义的数据类或概念集的分类器 .第第4章章 分类和预测分类和预测图4-1 数据分类过程.第第4章章 分类和预测分类和预测 由于提供了每个训练元组的类标号,这一步也称做监督学习(Supervised Learning),即分类器的学习在被告知每个训练元组属于哪个类的“监视〞下进行。
它不同于无监督学习(Unsupervised Learning)(或称聚类),每个训练元组的类标号是未知的,并且要学习的类的个数或集合也可能事先不知道 .第第4章章 分类和预测分类和预测 在第二步(如图4-1(b)所示),使用模型进行分类首先评估分类器的预测准确率如果使用训练集来测量分类器的准确率,则评估可能是乐观的,因为分类器趋向于过分拟合(overfit)该数据(即在学习期间,它可能并入了训练数据中的某些特殊的异常点,这些异常点不在一般数据集中出现) .第第4章章 分类和预测分类和预测 4.2 基于相似性的分类算法 基于相似性的分类算法的思路比较简单直观假定数据库中的每个元组ti为数值向量,每个类用一个典型数值向量来表示,则能通过分配每个元组到它最相似的类来实现分类第第4章章 分类和预测分类和预测 定义4.1 给定一个数据库D={t1,t2,…,tn}和一组类C={C1,C2,…,Cm}对于任意的元组ti={ti1,ti2,…,tik}∈ 如果存在一个Ci∈C,使得: (4.1)则ti被分配到类Ci中,其中sim(ti,Ci)称为相似性度量函数。
.第第4章章 分类和预测分类和预测 算法4.1 基于相似性的分类算法(每个类Ci对应一个中心点) 输入:每个类的中心C1, C2, …, Cm;待分类的元组t 输出:输出类别c .第第4章章 分类和预测分类和预测 算法4.2 基于相似性的分类算法(每个类Ci对应多个中心点) 输入:训练样本数据D={t1,t2,…,tn}和训练样本对应类属性值C={C1,C2,…,Cm};待分类的元组t 输出:输出类别c第第4章章 分类和预测分类和预测 算法4.3 k-最临近算法 输入:训练数据T;最临近数目k;待分类的元组t 输出:输出类别c.第第4章章 分类和预测分类和预测 4.3 决策树分类算法 从数据中生成分类器的一个特别有效的方法是生成一个决策树(Decision Tree)决策树表示方法是应用最广泛的逻辑方法之一,它从一组无次序、无规则的事例中推理出决策树表示形式的分类规则决策树分类方法采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较,根据不同的属性值判断从该结点向下的分支,在决策树的叶结点得到结论所以,从决策树的根到叶结点的一条路径就对应着一条合取规则,整棵决策树就对应着一组析取表达式规则。
第第4章章 分类和预测分类和预测图4-2 buys_computer的决策树示意图.第第4章章 分类和预测分类和预测4.3.1 决策树基本算法概述 1. 决策树生成算法 决策树生成算法的输入是一组带有类别标记的例子,决策树是一棵二叉树或多叉树二叉树的内部结点(非叶子结点)一般表示为一个逻辑判断,如形式为(ai=vi)的逻辑判断,其中ai是属性,vi是该属性的某个属性值树的边是逻辑判断的分支结果多叉树的内部结点是属性,边是该属性的所有取值,有几个属性值,就有几条边树的叶子结点都是类别标记第第4章章 分类和预测分类和预测 算法4.4 Generate_decision_tree(决策树生成算法) 输入:训练样本samples,由离散值属性表示;候选属性的集合attribute_list 输出:一棵决策树(由给定的训练数据产生一棵决策树) (1) 创建结点N; (2) IF samples 都在同一个类C THEN 返回N作为叶结点,以类C标记,并且Return; (3) IF attribute_list为空 THEN 返回N作为叶结点,标记为samples中最普通的类,并且Return;//多数表决.第第4章章 分类和预测分类和预测 (4) 选择attribute_list中具有最高信息增益的属性test_attribute; (5) 标记结点N为test_attribute; (6) FOR each test_attribute中的已知值ai,由结点N长出一个条件为test_attribute=ai的分枝; (7) 设si是samples 中test_attribute =ai的样本的集合;//一个划分 (8) IF si 为空 THEN 加上一个树叶,标记为samples中最普通的类; (9) ELSE 加上一个由Generate_decision_tree(si,attribute_listtest_attribute)返回的结点。
第第4章章 分类和预测分类和预测 2. 决策树修剪算法 现实世界的数据一般不可能是完美的,可能某些属性字段上缺值(Missing Values);可能缺少必须的数据而造成数据不完整;可能数据不准确、含有噪声甚至是错误的 .第第4章章 分类和预测分类和预测 有两种基本的剪枝策略: (1) 预先剪枝(Pre-Pruning):在生成树的同时决定是继续对不纯的训练子集进行划分还是停机 (2) 后剪枝(Post-Pruning):一种拟合-化简(Fitting-and-simplifying)的两阶段方法首先生成与训练数据完全拟合的一棵决策树,然后从树的叶子开始剪枝,逐步向根的方向剪剪枝时要用到一个测试数据集合(Tuning Set或Adjusting Set),如果存在某个叶子剪去后测试集上的准确度或其他测度不降低(不变得更坏),则剪去该叶子;否则停机第第4章章 分类和预测分类和预测4.3.2 ID3算法 1. 信息论简介 1948年Shannon提出并发展了信息论,以数学的方法度量并研究信息,通过通信后对信源中各种符号出现的不确定程度的消除来度量信息量的大小。
他提出了自信息量、信息熵、条件熵及平均互信息量等一系列概念第第4章章 分类和预测分类和预测 条件熵及平均互信息量等一系列概念 (1) 自信息量在收到ai之前,收信者对信源发出ai的不确定性定义为信息符号ai的自信息量I(ai),即I(ai)=-lbp(ai),其中p(ai)为信源发出ai的概率 (2) 信息熵自信息量只能反映符号的不确定性,而信息熵可以用来度量整个信源X整体的不确定性,定义如下: (4.2).第第4章章 分类和预测分类和预测 (3) 条件熵如果信源X与随机变量Y不是相互独立的,收信者收到信息Y,那么,用条件熵H(X∣Y)来度量收信者在收到随机变量Y之后,对随机变量X仍然存在的不确定性设X对应信源符号ai,Y对应信源符号bj,p(ai|bj)为当Y为bj时,X为ai的概率,则有: (4.3).第第4章章 分类和预测分类和预测 (4) 平均互信息量平均互信息量表示信号Y所能提供的关于X的信息量的大小,用I(X,Y)表示: (4.4) .第第4章章 分类和预测分类和预测 2. 信息增益计算 在学习开始的时候只有一棵空的决策树,并不知道如何根据属性将实例进行分类,所要做的就是根据训练实例集构造决策树来预测如何根据属性对整个实例空间进行划分。
设此时训练实例集为X,目的是将训练实例分为n类设属于第i类的训练实例为Ci,X中总的训练实例个数为||X||,若记一个实例属于第i类的概率为P(Ci),那么: (4.5) .第第4章章 分类和预测分类和预测 此时,决策树对划分C的不确定程度为 (4.6) .第第4章章 分类和预测分类和预测 以后在无混淆的情况下将H(X,C)简记为H(X)4.7) .第第4章章 分类和预测分类和预测 决策树学习过程就是使得决策树对划分的不确定程度逐渐减小的过程若选择测试属性a进行测试,在得知a=aj的情况下属于第i类的实例为Cij记 (4.8).第第4章章 分类和预测分类和预测即p(Ci;a=aj)为在测试属性a的取值为aj时,它属于第i类的概率此时,决策树对分类的不确定程度就是训练实例集对属性X的条件熵 (4.9).第第4章章 分类和预测分类和预测 又因为在选择测试属性a后伸出的每个a=aj分支Xj对于分类信息的信息熵为(4.10) 属性a对于分类提供的信息增益I(X;a)为: (4.11).第第4章章 分类和预测分类和预测 3. ITD3算法 算法4.5 ID3算法。
第第4章章 分类和预测分类和预测.第第4章章 分类和预测分类和预测.第第4章章 分类和预测分类和预测.第第4章章 分类和预测分类和预测 4. ID3算法应用举例 【例4.1】 表4-1给出了一个可能带有噪音的数据集合它有四个属性:Outlook、Temperature、H umidity和Windy它被分为No和Yes两类通过ID3算法构造决策树将数据进行分类第第4章章 分类和预测分类和预测.第第4章章 分类和预测分类和预测 因为初始时刻属于P类和N类的实例个数均为12个,所以初始时刻的熵值为 如果选取Outlook属性作为测试属性,根据式(4.10),此时的条件熵为.第第4章章 分类和预测分类和预测 如果选取Temperature属性作为测试属性,则有: 如果选取Humidity属性作为测试属性,则有:.第第4章章 分类和预测分类和预测 如果选取Windy属性作为测试属性,则有:.第第4章章 分类和预测分类和预测 可以看出H(X|Outlook)最小,即有关Outlook的信息对于分类有最大的帮助,提供最大的信息量,即I(X,Outlook)最大。
所以应该选择Outlook属性作为测试属性还可以看出H(X)=H(X|Windy),即I(X,Windy)=0,有关Windy的信息不能提供任何分类信息选择Outlook作为测试属性之后将训练实例集分为三个子集,生成三个叶结点,对每个叶结点依次利用上面过程则生成如图4-3所示的决策树第第4章章 分类和预测分类和预测图4-3 表4-1所训练生成的决策树.第第4章章 分类和预测分类和预测 5. ID3算法性能分析 ID3算法可以描述成从一个假设空间中搜索一个拟合训练样例的假设被ID3算法搜索的假设空间就是可能的决策树的集合ID3算法以一种从简单到复杂的爬山算法遍历这个假设空间,从空的树开始,然后逐步考虑更加复杂的假设,目的是搜索到一个正确分类训练数据的决策树引导这种爬山搜索的评估函数是信息增益度量第第4章章 分类和预测分类和预测 有几种途径可被用来避免决策树学习中的过度拟合,它们分为两类: (1) 预先剪枝,及早停止树增长,在ID3算法完美分类训练数据之前就停止树增长 (2) 后剪枝,即允许树过度拟合数据,然后对这个树进行后修剪 .第第4章章 分类和预测分类和预测 无论是通过及早停止还是后剪枝来得到正确规模的树,一个关键的问题是使用什么样的准则来确定最终正确树的规模。
解决这个问题的方法包括: (1) 使用与训练样例截然不同的一套分离的样例来评估后修剪的决策树的分类效果 (2) 使用所有可用数据进行训练,但进行统计测试来估计扩展(或修剪)一个特定的结点是否有可能改善在训练集合外的实例上的性能例如,Quinlan(1986)使用一种卡方法(Chi_square)测试来估计进一步扩展结点是否能改善在整个实例分布上的性能,还是仅仅改善了当前的训练数据上的性能第第4章章 分类和预测分类和预测4.3.3 C4.5算法 C4.5克服了ID3在应用中存在的不足,主要体现在以下几个方面: (1) 用信息增益率来选择属性,它克服了用信息增益选择属性时偏向选择取值多的属性的不足 (2) 在树构造过程中或者构造完成之后,进行剪枝 (3) 能够完成对连续属性的离散化处理 (4) 能够对于不完整数据进行处理,例如能对未知的属性值进行处理 (5) C4.5采用的知识表示形式为决策树,并最终可以形成产生式规则第第4章章 分类和预测分类和预测 1. 构造决策树 设T为数据集,类别集合为{C1,C2,…,Ck},选择一个属性V把T分为多个子集设V有互不重合的n个取值{v1,v2,…,vn},则T被分为n个子集T1,T2,…,Tn,这里Ti中的所有实例的取值均为vi。
令||T||为数据集T的例子数,||Ti||为V=vi的例子数,||Cj||=freq(Cj,T)为Cj类的例子数,||Cjv||是V=vi例子中,具有Cj类别例子数则有:.第第4章章 分类和预测分类和预测 ① 类别Cj发生概率为 (4.12) ② 属性V=vi的发生概率为 (4.13) .第第4章章 分类和预测分类和预测 ③ 属性V=vi的例子中,具有类别Cj的条件概率为 (4.14) Quinlan在ID3中使用信息论中的信息增益(gain)来选择属性,而C4.5采用属性的信息增益率(gainratio)来选择属性第第4章章 分类和预测分类和预测 1) 类别的信息熵 (4.15).第第4章章 分类和预测分类和预测 2) 类别条件熵 按照属性V把集合T分割,分割后的类别条件熵为 (4.16).第第4章章 分类和预测分类和预测 3) 信息增益(gain) 信息增益,即互信息可表示为 (4.17).第第4章章 分类和预测分类和预测 4) 属性V的信息熵 (4.18).第第4章章 分类和预测分类和预测 5) 信息增益率 (4.19) .第第4章章 分类和预测分类和预测 2. 连续属性的处理 在ID3中没有处理连续属性的功能。
在C4.5中,设在集合T中,连续属性A的取值为{v1,v2,…,vm},则任何在vi和vi+1之间的任意取值都可以把实例集合分为两部分,即 (4.20).第第4章章 分类和预测分类和预测 可以看到一共有m-1种分割情况 对属性A的m-1种分割的任意一种情况,作为该属性的两个离散取值,重新构造该属性的离散值,再按照上述公式计算每种分割所对应的信息增益率gain_ratio(vi),在m-1 种分割中,选择最大增益率的分割作为属性A的分枝,即 (4.21).第第4章章 分类和预测分类和预测图4-4 连续属性分割示意图.第第4章章 分类和预测分类和预测 3. 决策树剪枝 由于噪声和随机因素的影响,决策树一般会很复杂,因此需要进行剪枝操作 1) 剪枝策略 有两种剪枝策略: ① 在树生成过程中判断是否还继续扩展决策树,若停止扩展,则相当于剪去该结点以下的分枝; ② 对于生成好的树剪去某些结点和分枝第第4章章 分类和预测分类和预测 2) 基于误差的剪枝 决策树的剪枝通常是用叶结点替代一个或者多个子树,然后选择出现概率最高的类作为该结点的类别在C4.5中,还允许用其中的树枝来替代子树。
如果使用叶结点或者树枝代替原来的子树之后,误差率若能够下降,则使用此叶结点或者树枝代替原来的子树图4-5所示为用一个叶子节点替换子树示意图第第4章章 分类和预测分类和预测图4-5 用一个叶子节点替换子树示意图.第第4章章 分类和预测分类和预测 3) 误差率的判断 设一个叶结点覆盖N个实例,其中E个为错误的对于具有信任CF的实例,计算一个二项分布UCF(E,N),该二项分布即实例的误判概率,那么N个实例判断错误的数目为N×UCF(E,N)子树的错误数目为所有叶结点的总和例如: 上例中:括号中为覆盖的实例第第4章章 分类和预测分类和预测 设CF=0.25,则该子树的实例判断错误数目为 若以一个叶结点C1代替该子树,则16个实例中有一个错误(C3),误判实例数目为 由于判断错误数目小于上述子树,则以该叶结点代替子树第第4章章 分类和预测分类和预测 4.4 贝叶斯分类算法 贝叶斯分类是统计分类方法在贝叶斯学习方法中实用性很高的一种称为朴素贝叶斯分类方法在某些领域,其性能与神经网络、决策树相当 .第第4章章 分类和预测分类和预测4.4.1 贝叶斯定理 定义4.2 设X是类标号未知的数据样本,设H为某种假定,如数据样本X属于某特定的类C。
对于分类问题,希望确定P(H|X),即给定观测数据样本X,假定H成立的概率贝叶斯定理给出了如下计算P(H|X)的简单有效的方法:(4.22).第第4章章 分类和预测分类和预测4.4.2 朴素贝叶斯分类 朴素贝叶斯分类的工作过程如下: (1) 每个数据样本用一个n维特征向量X={x1,x2,…,xn}表示,分别描述具有n个属性A1,A2,…,An的样本的n个度量第第4章章 分类和预测分类和预测 (2) 假定有m个类C1,C2,…,Cm,给定一个未知的数据样本X(即没有类标号),分类器将预测X属于具有最高后验概率(条件X下)的类也就是说,朴素贝叶斯分类将未知的样本分配给类Ci(1≤i≤m),当且仅当P(Ci|X)>P(Cj|X),j=1,2,…,m,j≠i这样,最大的P(Ci|X)对应的类Ci称为最大后验假定,而P(Ci|X)可以根据下面的贝叶斯定理来确定: (4.23).第第4章章 分类和预测分类和预测 (3) 由于P(X)对于所有类为常数,只需要P(X|Ci)P(Ci)最大即可如果Ci类的先验概率未知,则通常假定这些类是等概率的,即P(C1)=P(C2)=…=P(Cm),因此问题就转换为对P(X|Ci)的最大化。
P(X|Ci)常被称为给定Ci时数据X的似然度,而使P(X|Ci)最大的假设Ci称为最大似然假设否则,需要最大化P(X|Ci)P(Ci)注意,假设不是等概率,那么类的先验概率可以用P(Ci)=si/s计算,其中si是类Ci中的训练样本数,而s是训练样本总数第第4章章 分类和预测分类和预测 (4) 给定具有许多属性的数据集,计算P(X|Ci)的开销可能非常大为降低计算P(X|Ci)的开销,可以做类条件独立的朴素假定给定样本的类标号,假定属性值相互条件独立,即在属性间不存在依赖关系这样 (4.24).第第4章章 分类和预测分类和预测 如果Ak是离散属性,则P(xk|Ci)=sik/si,其中sik是在属性Ak上具有值xk的类Ci的训练样本数,而si是Ci中的训练样本数 如果Ak是连续值属性,则通常假定该属性服从高斯分布,即 (4.25).第第4章章 分类和预测分类和预测 【例4.2】 对于表4-2给出的训练数据,使用朴素贝叶斯方法进行分类学习第第4章章 分类和预测分类和预测.第第4章章 分类和预测分类和预测 解 数据样本用属性age,income,student和credit_rating描述。
类标号属性buys_computer具有两个不同值(即{yes,no}) 设C1对应于类buys_computer=“Yes”,而C2对应于类buys_computer=“No”希望分类的未知样本为 X=(age=“ ≤30”,income=“medium”,student =“Yes”,credit_rating=“fair”) .第第4章章 分类和预测分类和预测 需要最大化P(X|Ci)P(Ci),i=1,2每个类的先验概P(Ci)可以根据训练样本计算: · P(buys_computer=“Yes”)=9/14= 0.643 · P(buys_computer=“No”)=5/1 4=0.357 .第第4章章 分类和预测分类和预测 为计算P(P(X|Ci)),i=1、2,计算下面的条件概率.第第4章章 分类和预测分类和预测 假设条件独立性,使用以上概率,得到:.第第4章章 分类和预测分类和预测 因而,对于样本X,朴素贝叶斯分类预测buys_computer=“yes” 至此,通过在全部时间基础上观察某事件出现的比例来估计概率。
例如,在上例中,估计P(age≤30| buys_computer=“yes”)使用的是比值行nc/n,其中n=9为所有buys_computer=“yes〞的训练样本数目,而nc=2是在其中age≤30的数目第第4章章 分类和预测分类和预测 显然,在多数情况下,观察到的比例是对概率的一个良好估计,但当nc很小时估计较差设想P(age≤30| buys_computer=“yes”)的值为0.08,而样本中只有9个样本为buys_computer=“yes”,那么对于nc最有可能的值只有0这产生了两个难题: (1) nc/n产生了一个有偏的过低估计(Underestimate)概率 (2) 当此概率估计为0时,如果将来的查询包括age≤30,此概率项会在贝叶斯分类器中占有统治地位原因在于,其他概率项乘以0值后得到的最终结果为0第第4章章 分类和预测分类和预测 为避免这些难题,可以采用一种估计概率的贝叶斯方法,即如下定义的m-估计: (4.26).第第4章章 分类和预测分类和预测4.4.3 贝叶斯信念网 1. 模型表示 贝叶斯信念网络(Bayesian Belief Networks,BBN),简称贝叶斯网络,用图形表示一组随机变量之间的概率关系。
贝叶斯网络有两个主要成分: (1) 一个有向无环图(dag),表示变量之间的依赖关系 (2) 一个概率表,把各结点和它的直接父结点关联起来第第4章章 分类和预测分类和预测 贝叶斯网络的重要性质表述如下: 性质1 条件独立 贝叶斯网络中的一个结点,如果它的父母结点已知,则它条件独立于它的所有非后代结点 图4-6(b)中,给定C,A条件独立于B和D,因为B和D都是A的非后代结点朴素贝叶斯分类器中的条件独立假设也可以用贝叶斯网络来表示如图4-5(c)所示,其中y是目标类,{X1,X2,…,Xd}是属性集第第4章章 分类和预测分类和预测图4-6 使用有向无环图表示概率关系.第第4章章 分类和预测分类和预测 图4-7所示是贝叶斯网络的一个例子,对心脏病或心口痛患者建模假设图中每个变量都是二值的心脏病结点(HD)的父母结点对应于影响该疾病的危险因素,例如锻炼(E)和饮食(D)等心脏病结点的子结点对应于该病的症状,如胸痛(CP)和高血压(BP)等如图4-7所示,心口痛(Hb)可能源于不健康的饮食,同时又可能导致胸痛第第4章章 分类和预测分类和预测图4-7 发现心脏病和心口痛病人的贝叶斯网.第第4章章 分类和预测分类和预测 影响疾病的危险因素对应的结点只包含先验概率,而心脏病、心口痛以及它们的相应症状所对应的结点都包含条件概率。
为了节省空间,图中省略了一些概率注意P(X= x )=1-P(X=x),P(X= x |Y)=1-P(X=x|Y),其中 x 表示与x相反的结果因而,省略的概率可以很易求得例如,条件概率:P(心脏病=No|锻炼=No,饮食=安康) =1-P(心脏病=Yes|锻炼=No,饮食=安康) =1-0.55 =0.45.第第4章章 分类和预测分类和预测 2. 建立模型 贝叶斯网络的建模包括两个步骤:创建网络结构;估计每一个结点的概率表中的概率值网络拓扑结构可以通过对主观的领域专家知识编码获得算法4.5给出了归纳贝叶斯网络拓扑结构的一个系统的过程第第4章章 分类和预测分类和预测 算法4.5 贝叶斯网络拓扑结构的生成算法第第4章章 分类和预测分类和预测 例4.3 考虑图4-7中的变量执行步骤1后,设变量次序为(E,D,HD,Hb,CP,BP)从变量D开始,经过步骤2到7,得到如下条件概率:.第第4章章 分类和预测分类和预测 3. 使用BBN进行推理举例 情况一:没有先验信息 在没有任何先验信息的情况下,可以通过计算先验概率P(HD=Yes)和P(HD=No)来确定一个病人是否可能患心脏病。
为了表述方便,设α∈{Yes,No}表示锻炼的两个值,β∈{安康,不健康}表示饮食的两个值第第4章章 分类和预测分类和预测.第第4章章 分类和预测分类和预测 情况二:高血压 如果一个人有高血压,可以通过比较后验概率P(HD=Yes|BP=高)和P(HD=No|BP=高)来诊断他是否患有心脏病为此,必须先计算P(BP=高):.第第4章章 分类和预测分类和预测 其中γ∈{Yes,No}因而,此人患心脏病的后验概率是:.第第4章章 分类和预测分类和预测 情况三:高血压、饮食健康、经常锻炼身体 假设得知此人经常锻炼身体并且饮食健康加上这些新信息,此人患心脏病的后验概率为.第第4章章 分类和预测分类和预测 而此人不患心脏病的概率是: 因此模型暗示健康的饮食和有规律的体育锻炼可以降低患心脏病的危险第第4章章 分类和预测分类和预测 4. BBN的特点 下面是BBN模型的一般特点: (1) BBN提供了一种用图形模型来捕获特定领域的先验知识的方法网络还可以用来对变量间的因果依赖关系进行编码 (2) 构造网络可能既费时又费力然而,一旦网络结构确定下来,添加新变量就十分容易。
第第4章章 分类和预测分类和预测 (3) 贝叶斯网络很适合处理不完整的数据对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理 (4) 因为数据和先验知识以概率的方式结合起来了,所以该方法对模型的过分拟合问题是非常鲁棒的第第4章章 分类和预测分类和预测 4.5 人工神经网络(ANN)4.5.1 人工神经网络的基本概念 大脑的一个重要成分是神经网络神经网络由相互关联的神经元组成每一个神经元由内核(Body)、轴突(Axon)和晶枝(Dendrite)组成晶枝形成一个非常精密的“毛刷〞环绕在内核周围轴突可以想象为一根又长又细的管道,其终点分为众多细小分支,将内核的信息传递给其他内核的晶枝这些细小分支的头,即那些又长又细管道的终点,称为突触(synapse),它们的主要功能是接触其他内核的晶枝第第4章章 分类和预测分类和预测图4-8 生物学中神经网络的简图.第第4章章 分类和预测分类和预测 一个神经元根据晶枝接收到的信息,通过内核进行信息处理,再通过它所控制的突触送给其他的神经元神经元可分为两种:“抑制〞性的或“兴奋〞性的。
当一个神经元的晶枝接收的兴奋性信息累计超出某一值时,神经元被激活并传递出一个信息给其他神经元,这个值称为阈值(Threshold)这种传递信息的神经元为“兴奋〞性的第二种情况是神经元虽然接收到其他神经元传递的信息,但没有向外传递信息,此时,称这个神经元为“抑制〞性的第第4章章 分类和预测分类和预测图4-9 McCulloch-Pitts认知网络.第第4章章 分类和预测分类和预测 在图4-9中,wi为关联权,表示神经元对第i个晶枝接收到信息的感知能力f称为输出函数或激活函数(Activation Function),y=f(z-θ)为输出神经元的输出值McCulloch-Pitts 输出函数定义为(4.27)其中, (4.28).第第4章章 分类和预测分类和预测 人工神经网络的建立和应用可以归结为三个步骤: (1) 网络结构的确定 激活函数的类型比较多,主要有线性函数(式(4.29))和Sigmoid函数(式(4.30)) f(x)=ax+b (4.29)其中,a和b是实常数 (4.30) .第第4章章 分类和预测分类和预测 识别和归类问题中,如果采用阶跃函数,当输出值为1时,可以肯定地说出输入的归类。
阶跃函数的缺点是数学性质较差,如在x=0点不光滑Sigmoid函数弥补了这一方面的不足,使得函数值在(0,1)区间连续变化Sigmoid函数又称S形函数,如图4-10所示第第4章章 分类和预测分类和预测图4-10 Sigmoid函数.第第4章章 分类和预测分类和预测 (2) 关联权和θ的确定关联权和θ是通过学习(训练,train)得到的,学习分为有指导学习和无指导学习两类在一组正确的输入输出结果的条件下,人工神经网络依据这些数据,调整并确定权数wi和θ,使得网络输出同理想输出偏差尽量小的方法称为有指导学习在只有输入数据而不知输出结果的前提下,确定权数wi和θ的方法称无指导学习在学习过程中,不同的目标函数得到不同的学习规则 .第第4章章 分类和预测分类和预测 (3) 工作阶段(Simulate)在权数wi和θ确定的基础上,用带有确定权数的神经网络去解决实际问题的过程称为工作 图4-11是前向型人工神经网络的计算流程 .第第4章章 分类和预测分类和预测图4-11 前向型人工神经网络的计算流.第第4章章 分类和预测分类和预测4.5.2 感知器 考虑图4-12中的图和表。
图(a)所示的表显示一个数据集,包含三个布尔变量(x1,x2,x3)和一个输出变量y,当三个输入中至少有两个是0时,y取-1,而至少有两个大于0时,y取1第第4章章 分类和预测分类和预测图4-12 使用感知器模拟一个布尔函数.第第4章章 分类和预测分类和预测 模型的输出计算公式如下: (4.31) .第第4章章 分类和预测分类和预测 注意感知器的输入结点和输出结点之间的区别输入结点简单地把接收到的值传送给输出链,而不作任何转换输出结点则是一个数学装置,计算输入的加权和,减去偏置项,然后根据结果的符号产生输出更具体地,感知器模型的输出可以用如下数学方式表示:(4.32).第第4章章 分类和预测分类和预测其中,w1,w2,…,wd是输入链的权值,而x1, x2,…, xd是输入属性值符号函数作为输出神经元的激活函数(Activation Function),当参数为正时输出+1,参数为负时输出-1感知器模型可以写成下面更简洁的形式: (4.33).第第4章章 分类和预测分类和预测 算法4.6 感知器学习算法 (10) until 满足终止条件.第第4章章 分类和预测分类和预测 算法的主要计算是第(7)步中的权值更新公式:(4.34)其中,wj(k)是第k次循环后第i个输入链上的权值,参数λ为学习率(Learning Rate),xij是训练样本xi的第j个属性值。
第第4章章 分类和预测分类和预测 从公式(4.34)可以看出,新权值W(k+1)等于旧权值W(k)加上一个正比于预测误差(y- )的项如果预测正确,那么权值保持不变否则,按照如下方法更新: (1) 如果y=+1, =-1,那么预测误差(y- )=2为了补偿这个误差,需要通过提高所有正输入链的权值、降低所有负输入链的权值来提高预测输出值 (2) 如果y=-1, =+1,那么预测误差(y- )=-2为了补偿这个误差,需要通过降低所有正输入链的权值、提高所有负输入链的权值来减少预测输出值第第4章章 分类和预测分类和预测图4-13 图4-12中的数据的感知器决策边界.第第4章章 分类和预测分类和预测图4-14 XOR.第第4章章 分类和预测分类和预测4.5.3 多层人工神经网络 人工神经网络结构比感知器模型更复杂这些额外的复杂性来源于多个方面: (1) 网络的输入层和输出层之间可能包含多个中间层,这些中间层叫做隐藏层(Hidden Layer),隐藏层中的结点称为隐藏结点(Hidden Node)这种结构称为多层神经网络(见图4-15)。
.第第4章章 分类和预测分类和预测图4-15 多层前馈人工神经网络(ANN)举例.第第4章章 分类和预测分类和预测 (2) 除了符号函数外,网络还可以使用其他激活函数,如图4-16所示的线性函数、S型(逻辑斯缔)函数、双曲正切函数等这些激活函数允许隐藏结点和输出结点的输出值与输入参数呈非线性关系第第4章章 分类和预测分类和预测图4-16 人工神经网络激活函数的类型.第第4章章 分类和预测分类和预测 这些附加的复杂性使得多层神经网络可以对输入和输出变量间更复杂的关系建模例如,考虑上一节中描述的XOR问题实例可以用两个超平面进行分类,这两个超平面把输入空间划分到各自的类,如图4-17(a)所示因为感知器只能构造一个超平面,所以它无法找到最优解该问题可以使用两层前馈神经网络加以解决,见图4-17(b) .第第4章章 分类和预测分类和预测图4-17 XOR问题的两层前馈神经网络.第第4章章 分类和预测分类和预测 1. 学习ANN模型 ANN学习算法的目的是确定一组权值W,最小化误差的平方和: (4.35) .第第4章章 分类和预测分类和预测图4-18 两个参数模型的误差曲面E(W1,W2).第第4章章 分类和预测分类和预测 大多数情况下,由于激活函数的选择(如S型或双曲正切函数),ANN的输出是参数的非线性函数。
这样,推导出W的全局最优解变得不那么直接了像基于梯度下降的方法等贪心算法可以很有效地求解优化问题梯度下降方法使用的权值更新公式可以写成:(4.36).第第4章章 分类和预测分类和预测 2. ANN学习中的设计问题 在训练神经网络来学习分类任务之前,应该先考虑以下设计问题: (1) 确定输入层的结点数目 (2) 确定输出层的结点数目 (3) 选择网络拓扑结构,例如,隐藏层数和隐藏结点数,前馈还是递归网络结构 (4) 初始化权值和偏置随机赋值常常是可取的 (5) 去掉有遗漏值的训练样例,或者用最合理的值来代替第第4章章 分类和预测分类和预测 3. 人工神经网络的特点 人工神经网络的一般特点概括如下: (1) 至少含有一个隐藏层的多层神经网络是一种普适近似(Universal Approximator),即可以用来近似任何目标函数由于ANN具有丰富的假设空间,因此对于给定的问题,选择合适的拓扑结构来防止模型的过分拟合是很重要的 (2) ANN可以处理冗余特征,因为权值在训练过程中自动学习冗余特征的权值非常小 (3) 神经网络对训练数据中的噪声非常敏感。
处理噪声问题的一种方法是使用确认集来确定模型的泛化误差;另一种方法是每次迭代把权值减少一个因子第第4章章 分类和预测分类和预测 (4) ANN权值学习使用的梯度下降方法经常会收敛到局部最小值避免局部最小值的方法是式中加上一个动量项(Momentum Term) (5) 训练ANN是一个很耗时的过程,特别是当隐藏结点数量很大时然而,测试样例分类时非常快第第4章章 分类和预测分类和预测 4.6 支 持 向 量 机 支持向量机(Support Vector Machine,SVM)已经成为一种备受关注的分类技术这种技术具有坚实的统计学理论基础,并在许多实际应用(如手写数字的识别、文本分类等)中展示了大有可为的实践效用此外,SVM可以很好地应用于高维数据,避免了维灾难问题这种方法具有一个独特的特点:它使用训练实例的一个子集来表示决策边界该子集称做支持向量(Support Vector)第第4章章 分类和预测分类和预测4.6.1 最大边缘超平面 图4-19显示了一个数据集,包含属于两个不同类的样本,分别用方块和圆圈表示 .第第4章章 分类和预测分类和预测图4-19 一个线性可分数据集上的可能决策边界.第第4章章 分类和预测分类和预测 为了更好地理解不同的超平面对泛化误差的影响,考虑两个决策边界B1和B2,如图4-20所示。
.第第4章章 分类和预测分类和预测图4-20 决策边界的边缘.第第4章章 分类和预测分类和预测 统计学习理论给出了线性分类器边缘与其泛化误差之间关系的形式化解释,称这种理论为结构风险最小化(Structural Risk Minimization,SRM)理论该理论根据分类器的训练误差Re、训练样本数N和模型的复杂度(即它的能力(Capacity))h,给出了分类器的泛化误差的一个上界R更明确地,在概率1-η下,分类器的泛化误差j在最坏情况下满足下列公式: (4.37).第第4章章 分类和预测分类和预测4.6.2 线性支持向量机:可分情况 一个线性SVM是这样一个分类器,它寻找具有最大边缘的超平面,因此它也经常被称为最大边缘分类器(Maximal Margin Classifier) .第第4章章 分类和预测分类和预测 1. 线性决策边界 考虑一个包含N个训练样本的二元分类问题每个样本表示为一个二元组(xi,yi)(i=1,2,…,N),其中xi=(xi1,xi2,…,xid)T,对应于第i个样本的属性集为方便计,令yi∈{-1,1}表示它的类标号。
一个线性分类器的决策边界可以写成如下形式: (4.38).第第4章章 分类和预测分类和预测 图4-21显示了包含圆圈和方块的二维训练集图中的实线表示决策边界,它将训练样本一分为二,划入各自的类中任何位于决策边界上的样本都必须满足公式(4.37)例如,如果xa和xb是两个位于决策边界上的点,那么两个方程相减便得到:.第第4章章 分类和预测分类和预测图4-21 SVM的决策边界和边缘.第第4章章 分类和预测分类和预测 对于任何位于决策边界上方的方块xs,可以证明: ω·xs+b=k (4.39)其中,k>0类似地,对于任何位于决策边界下方的圆圈xc,可以证明: ω·xc+b=k′(4.40)其中,k′<0如果标记所有的方块的类标号为+1,标记所有的圆圈的类标号为-1,则可以用以下的方式预测任何测试样本z的类标号y: (4.41).第第4章章 分类和预测分类和预测 2. 线性分类器的边缘 考虑那些离决策边界最近的方块和圆圈由于该方块位于决策边界的上方,因此对于某个正值k,它必然满足公式(4.38);而对于某个负值k,圆圈必须满足公式(4.40)调整决策边界的参数ω和b,两个平行的超平面bi1和bi2可以表示如下:bi1:ω·x+b=+1 (4.42)bi2:ω·x+b=-1 (4.43) .第第4章章 分类和预测分类和预测 决策边界的边缘由这两个超平面之间的距离给定。
为了计算边缘,令x1是bi1上的一个数据点,x2是bi2上的一个数据点,如图4-21所示将x1和x2分别代入公式(4.42)和(4.43)中,则边缘d可以通过两式相减得到: (4.44).第第4章章 分类和预测分类和预测 3. 学习线性SVM模型 SVM的训练阶段包括从训练数据中估计决策边界的参数ω和b选择的参数必须满足下面两个条件: (4.45).第第4章章 分类和预测分类和预测 这些条件要求所有类标号为1的训练实例(即方块)都必须位于超平面ω·x+b=+1上或位于它的上方,而那些类标号为-1的训练实例(即圆圈)都必须位于超平面ω·x+b=-1上或位于它的下方这两个不等式可以概括为如下更紧凑的形式: (4.46) .第第4章章 分类和预测分类和预测 尽管前面的条件也可以用于其他线性分类器(包括感知器),但是SVM增加了一个要求:其决策边界的边缘必须是最大的然而,最大化边缘等价于最小化下面的目标函数: (4.47) .第第4章章 分类和预测分类和预测 定义4.3 线性SVM(可分情况):SVM的学习任务可以形式化地描述为以下被约束的优化问题:.第第4章章 分类和预测分类和预测 首先,必须改写目标函数,考虑施加在解上的约束。
新目标函数称为该优化问题的拉格朗日算子:(4.48).第第4章章 分类和预测分类和预测 为了最小化拉格朗日算子,必须对Lp关于ω和b求偏导,并令它们等于零: (4.49) (4.50) .第第4章章 分类和预测分类和预测 处理不等式约束的一种方法就是把它变换成一组等式约束只要限制拉格朗日乘子非负,这种变换便是可行的这种变换导致如下拉格朗日乘子约束,称做Karuch-Kuhn-Tucher(KKT)条件: (4.51) (4.52) .第第4章章 分类和预测分类和预测 对前面的优化问题求解仍是一项十分棘手的任务,因为它涉及大量参数:ω、b和λi通过将拉格朗日算子变换成仅包含拉格朗日乘子的函数(称做对偶问题),可以简化该问题为了变换成对偶问题,首先将公式(4.49)和(4.50)代入到公式(4.48)中这将导致该优化问题的如下对偶公式:(4.53) .第第4章章 分类和预测分类和预测 对偶拉格朗日算子和原拉格朗日算子的主要区别如下: (1) 对偶拉格朗日算子仅涉及拉格朗日乘子和训练数据,而原拉格朗日算子除涉及拉格朗日乘子外,还涉及决策边界的参数尽管如此,这两个优化问题的解是等价的。
(2) 公式(4.53)中的二次项前有个负号,这说明原来涉及拉格朗日算子LP的最小化问题已经变换成了涉及对偶拉格朗日算子LD的最大化问题第第4章章 分类和预测分类和预测 对于大型数据集,对偶优化问题可以使用数值计算技术来求解,如使用二次规划一旦找到一组λi就可以通过公式(4.49)和(4.52)来求得ω和b的可行解 决策边界可以表示成:(4.54) .第第4章章 分类和预测分类和预测 【例4.4】 考虑图4-22给出的二维数据集,它包含8个训练实例使用二次规划方法,可以求解公式(4.53)给出的优化问题,得到每一个训练实例的拉格朗日乘子λi,如图4-22(a)的表的最后一列所示第第4章章 分类和预测分类和预测图4-22 一个线性可分数据集的例子.第第4章章 分类和预测分类和预测 令ω=(ω1,ω2),b为决策边界的参数使用公式(4.48),可以按如下方法求解ω1和ω2: .第第4章章 分类和预测分类和预测 偏倚项b可以使用公式(4.51)对每个支持向量进行计算: 对b取平均值,得到b=7.93对应于这些参数的决策边界显示在图4-22中。
第第4章章 分类和预测分类和预测 一旦确定了决策边界的参数,检验实例z可以按以下的公式来分类: 如果f(z)=1,则检验实例被分为到正类,否则分到负类第第4章章 分类和预测分类和预测4.6.3 线性支持向量机:不可分情况 图4-23给出了一个和图4-20相似的数据集,不同处在于它包含了两个新样本P和Q尽管决策边界B1误分类了新样本,而B2正确分类了它们,但是这并不意味着B2是一个比B1好的决策边界,因为这些新样本可能只是训练数据集中的噪声B1可能仍然比B2更可取,因为它具有较宽的边缘,从而对过分拟合不太敏感然而,上一节给出的SVM公式只能构造没有错误的决策边界 .第第4章章 分类和预测分类和预测图4-23 不可分情况下SVW的决策边界.第第4章章 分类和预测分类和预测 尽管公式(4.46)给定的原目标函数仍然是可用的,但是决策边界B1不再满足公式(4.45)给定的所有约束因而,必须放松不等式约束,以适应非线性可分数据,可以通过在优化问题的约束中引入正值的松弛变量(Slack Variable)ξ实现,如下式所示: (4.55).第第4章章 分类和预测分类和预测 图4-24可以帮助理解松弛变量ξi的意义。
圆圈P是一个实例,它违反公式(4.45)给定的约束设ω·x+b=+1-ξ是一条经过点P,且平行于决策边界的直线可以证明它与超平面ω·x+b=+1之间的距离为多ξ/||ω||因而,ξ提供了决策边界在训练样本P上的误差估计第第4章章 分类和预测分类和预测图4-24 不可分离数据的松弛变量.第第4章章 分类和预测分类和预测 理论上,可以使用和前面相同的目标函数,然后加上公式(4.55)给定的约束来确定决策边界然而,由于在决策边界误分样本的数量上没有限制,学习算法可能会找到这样的决策边界:它的边缘很宽,但是误分了许多训练实例,如图4-25所示为了避免这个问题,必须修改目标函数,以惩罚那些松弛变量值很大的决策边界修改后的目标函数如下:.第第4章章 分类和预测分类和预测图4-25 一个具有宽边缘但训练误差很高的决策边界.第第4章章 分类和预测分类和预测 由此,被约束的优化问题的拉格朗日算子可以记作如下形式: (4.56).第第4章章 分类和预测分类和预测其中,前面两项是需要最小化的目标函数,第三项表示与松弛变量相关的不等式约束,而最后一项是要求当ξi的值非负的结果。
此外,利用如下的KKT条件,可以将不等式约束变换成等式约束: ξi≥0, λi≥0, μi≥0 (4.57) λi(yi(ω·xi+b)-1+ξi) (4.58) μiξi=0(4.59) .第第4章章 分类和预测分类和预测 令L关于ω、b和ξ的一阶导数为零,就得到如下公式: (4.60) (4.61) (4.62) .第第4章章 分类和预测分类和预测 将公式(4.60)、(4.61)和(4.62)代入拉格朗日算子中,得到如下的对偶拉格朗日算子: (4.63) .第第4章章 分类和预测分类和预测4.6.4 非线性支持向量机 1. 属性变换 为了说明怎样进行属性变换可以导致一个线性的决策边界,考察图4-26(a)给出的二维数据集,它包含方块(类标号y=1)和圆圈(类标号y=-1)数据集是这样生成的:所有的圆圈都聚集在图的中心附近,而所有的方块都分布在离中心较远的地方可以使用下面的公式对数据集中的实例分类: (4.64) .第第4章章 分类和预测分类和预测 因而,数据集的决策边界可以表示如下: 这可以进一步简化为下面的二次方程: .第第4章章 分类和预测分类和预测 需要一个非线性变换Φ将数据从原先的特征空间映射到一个新的空间,决策边界在这个空间下成为线性的。
假定选择下面的变换: (4.65) 在变换空间中,找到参数ω=(ω1,ω2,ω3,ω4,ω5),使得:.第第4章章 分类和预测分类和预测图4-26 分类具有非线性决策边界的数据.第第4章章 分类和预测分类和预测 2. 学习非线性SVM模型 尽管属性变换方法看上去大有可为,但是存在一些实现问题首先,不清楚应当使用什么类型的映射函数,确保可以在变换后空间构建线性决策边界一种可能的选择是把数据变换到无限维空间中,但是这样的高维空间可能很难处理其次,即使知道合适的映射函数,在高维特征空间中解决被约束的优化问题仍然是计算代价很高的任务第第4章章 分类和预测分类和预测 为了解释这些问题并考察处理它们的方法,假定存在一个合适的函数Φ(x)来变换给定的数据集变换后,需要构建一个线性的决策边界,把样本划分到它们各自所属的类中在变换空间中,线性决策边界具有以下形式 ω·Φ(x)+b=0 .第第4章章 分类和预测分类和预测 定义4.4 非线性SVM 一个非线性SVM的学习任务可以形式化表达为以下的优化问题:.第第4章章 分类和预测分类和预测 注意,非线性SVM的学习任务和线性SVM(参见定义4.3)很相似。
主要的区别在于,学习任务是在变换后的属性Φ(x),而不是在原属性x上执行的采用4.6.2和4.6.3节介绍的线性SVM所使用的方法,可以得到该受约束的优化问题的对偶拉格朗日算子: (4.66).第第4章章 分类和预测分类和预测 使用二次规划技术得到λi后,就可以通过下面的方程导出参数ω和b: (4.67) (4.68) .第第4章章 分类和预测分类和预测 这类似于公式(4.49)和(4.50)的线性SVM最后,可以通过下式对检验实例z进行分类: (4.69).第第4章章 分类和预测分类和预测 3. 核技术 点积经常用来度量两个输入向量间的相似度例如,余弦相似度可以定义为规范化后具有单位长度的两个向量间的点积类似地,点积Φ(x)·Φ(x)可以看做两个实例xi和xj在变换空间中的相似性度量第第4章章 分类和预测分类和预测 核技术是一种使用原属性集计算变换空间中的相似度的方法考虑公式(4.65)中的映射函数Φ两个输入向量u和v在变换空间中的点积可以写成如下形式:(4.70) 该分析表明,变换空间中的点积可以用原空间中的相似度函数表示: (4.71) .第第4章章 分类和预测分类和预测 图4-27显示了一个非线性决策边界,它是通过使用公式(4.71)给出的多项式核函数的SVM获得的。
检验实例z可以通过下式分类: (4.72).第第4章章 分类和预测分类和预测图4-27 具有多项式核的非线性SVM产生的决策边界.第第4章章 分类和预测分类和预测 4. Mercer定理 定理4.1 Mercer定理 核函数k可以表示为: 当且仅当对于任意满足 的函数g(x), 那么.第第4章章 分类和预测分类和预测 满足定理4.1的核函数称为正定(Positive Definite)核函数下面给出一些这种函数的例子: (4.73) (4.74) (4.75).第第4章章 分类和预测分类和预测4.6.5 支持向量机的特征 SVM具有许多很好的性质,已经成为最广泛使用的分类算法之一下面简要总结一下SVM的一般特征: (1) SVM学习问题可以表示为凸优化问题,因此可以利用已知的有效算法发现目标函数的全局最小值,而其他的分类方法(如基于规则的分类器和人工神经网络)都采用一种基于贪心学习的策略来搜索假设空间,这种方法一般只能获得局部最优解 (2) SVM通过最大化决策边界的边缘来控制模型的能力尽管如此,用户必须提供其他参数,如使用的核函数类型、为了引入松弛变量所需的代价函数C等。
第第4章章 分类和预测分类和预测 (3) 通过对数据中每个分类属性值引入一个哑变量,SVM可以应用于分类数据例如,如果婚姻状况有三个值{独身,已婚,离异},可以对每一个属性值引入一个二元变量 (4) 本节所给出的SVM公式表述是针对二类问题的,SVM可扩展到多类问题第第4章章 分类和预测分类和预测 4.7 预 测 数值预测是对于给定的输入预测连续值或有序值 .第第4章章 分类和预测分类和预测4.7.1 线性回归 直线回归分析涉及一个响应变量y和一个预测变量x它是最简单的回归形式,并用x的线性函数对y建模,即 y=b+wx (4.76)其中,y的方差假定为常数,b和w是回归系数,分别表示直线的Y轴截距和斜率回归系数b和w也可以看作权重,可以等价地记作 y=w0+w1x (4.77) .第第4章章 分类和预测分类和预测 这些系数可以用最小二乘方法求解,它将最佳拟合直线估计为最小化实际数据与直线的估计值之间的误差的直线。
设D是训练集,由预测变量x的值和与它们相关联的响应变量y的值组成第第4章章 分类和预测分类和预测 训练集包含||D||个形如(x1,y1),(x2,y2),…,(x||D||, y||D||)的数据点回归系数可以用下式估计: (4.78) (4.79).第第4章章 分类和预测分类和预测 [例4.5] 使用最小二乘法的直线回归 表4-3给出了一组成对的数据其中x表示大学毕业后工作的年数,而y是对应的年薪这些二维数据可以用散布图,如图4-28所示该图暗示两个变量x和y之间存性关系用方程y=w0+w1x对年薪和工作年数之间的关系建模第第4章章 分类和预测分类和预测.第第4章章 分类和预测分类和预测图4-28 例4.5中的表4-2的数据图示.第第4章章 分类和预测分类和预测 多元线性回归是直线回归的扩展,涉及多个预测变量它允许响应变量y用描述元组X的n个预测变量或属性A1,A2,…,An的线性函数建模,其中X=(x1,x2,…,xn)训练数据集D包含形如(X1,y1),(X2,y2),…,(X||D||,y||D||)的数据,其中Xi是n维训练元组,yi是与Xi相关联的响应变量值。
一个基于两个预测属性或变量A1和A2的多元线性回归模型的例子是:y=w0+w1x1+w2x2 (4.80).第第4章章 分类和预测分类和预测4.7.2 非线性回归 【例4.6】 多项式回归模型到线性回归模型的变换考虑下式给出的三次多项式关系: y=w0+w1x+w2x2+w3x3 (4.81) 为了将该方程转换成线性的,定义如下新变量: x1=x, x2=x2, x3=x3 方程(4.81)可以转换成线性形式,结果为 y=w0+w1x1+w2x2+w3x3 .第第4章章 分类和预测分类和预测4.7.3 其他基于回归的方法 线性回归用于对连续值函数进行建模的使用广泛,主要是由于它的简洁性广义线性模型提供了将线性回归用于分类响应变量建模的理论基础与线性回归不同,在广义线性模型中,响应变量y的方差是y的均值的函数而性回归中的方差为常数广义线性模型的常见形式包括逻辑斯谛回归和泊松回归逻辑斯谛回归模型将某个事件发生的概率看做预测变量集的线性函数计数数据常常呈现泊松分布,并通常使用泊松回归建模 .第第4章章 分类和预测分类和预测 4.8 预测和分类中的准确率、误差的度量4.8.1 分类器准确率度量 由于学习算法对数据的过于拟合,使用训练数据导出分类器或预测器,然后评估结果学习模型的准确率可能错误地导致过于乐观的估计。
准确率最好在检验集上评估检验集由在训练模型时未使用的类标记的元组组成 .第第4章章 分类和预测分类和预测.第第4章章 分类和预测分类和预测图4-29 正、负元组的混淆矩阵.第第4章章 分类和预测分类和预测 假设已经训练的分类器将医疗数据元组分类为“cancer〞或“not_cancer”90%的准确率使该分类器看上去相当准确,但是,如果实际只有3%~4%的训练元组是“cancer”,显然,90%的准确率是不能接受的,比如,该分类器只能正确地对“not_cancer〞的元组分类换一种方式,希望能够评估分类器识别“cancer〞元组(称做正元组)的情况和识别“not_cancer〞元组(称做负元组)的情况为此,可以分别使用灵敏性(Sensitivity)和特效性(Specificity)度量灵敏度也称真正率(即正确识别的正元组的百分比),而特效性是真负率(即正确识别的负元组的百分比) .第第4章章 分类和预测分类和预测 此外,可以使用精度(Precision)标记为“cancer”,实际是“cancer〞的元组的百分比这些度量定义为 (4.82) (4.83) (4.84).第第4章章 分类和预测分类和预测其中,t_pos是真正(正确地分类的“cancer〞元组)数,pos是正(“cancer”)元组数,t_neg是真负(正确地分类的“not_ cancer”元组)数,neg是负(“not_cancer”)元组数,而f_pos是假正(错误地标记为“cancer〞的“not_cancer〞元组)数。
可以证明正确率是灵敏性和特效性的函数: (4.85) .第第4章章 分类和预测分类和预测4.8.2 预测器误差度量 设D是形如(X1,y1),(X2,y2),…,(X||D||,y||D||)的检验集,其中Xi是n维检验元组,在响应变量y上具有已知值yi,||D||是D中的元组数由于预测器返回连续值,而不是分类标号,很难准确地说Xi的预测值yi′是否正确使用损失函数(Loss Function)度量实际值yi与预测值yi′之间的误差来检测yi′与yi的差异第第4章章 分类和预测分类和预测 最常见的损失函数是: 绝对误差: (4.86) 平方误差: (4.87).第第4章章 分类和预测分类和预测 基于上式,检验误差(率)或泛化误差(Generalization Error)是整个检验集的平均损失这样,得到如下误差率: 均值绝对误差: (4.88) 均方误差: (4.89).第第4章章 分类和预测分类和预测 有时,可能希望误差是相对的,相对于从训练数据D预测y的均值y换句话说,可以除以由预测均值导致的总损失来规范化总损失相对误差度量包括两类: 相对绝对误差: (4.90) 相对平方误差: (4.91).第第4章章 分类和预测分类和预测 4.9 评估分类器或预测器的准确率 坚持、随机子抽样、交叉确认和自助法都是基于给定数据的随机抽样划分、评估准确率的常用技术。
这些估计准确率的技术的使用增加了总体计算时间,但是对于模型选择是有用的第第4章章 分类和预测分类和预测4.9.1 保持方法和随机子抽样 (1) 坚持(Holdout)方法保持方法是目前为止讨论准确率时特指的方法 (2) 随机子抽样(Random Subsampling)随机子抽样是保持方法的一种变形,它将保持方法重复k次总准确率估计取每次迭代准确率的平均值对于预测,可以取预测器误差率的平均值第第4章章 分类和预测分类和预测图4-30 用保持方法估计准确率.第第4章章 分类和预测分类和预测4.9.2 交叉确认 在k折交叉确认(k-fold crossvalidation)中,初始数据随机划分成k个互不相交的子集或“折〞D1,D2,…,Dk,每个折的大小大致相等训练和检验进行k次 .第第4章章 分类和预测分类和预测4.9.3 自助法 与准确率估计方法不同,自助法(Bootstrap Method)从给定训练元组中有放回地均匀抽样也就是说,每当选中一个元组,它等可能地被再次选中并再次添加到训练集中例如,想像一台从训练集中随机选择元组的机器,在有放回的抽样中,允许机器多次选择同一个元组。
第第4章章 分类和预测分类和预测 假定每个元组被选中的概率是1/d,因此未被选中的概率是(1-1/d)要挑选d次,一个元组在全部d次挑选都未被选中的概率是(1-1/d)d如果d很大,该概率近似为e-1=0.368这样,36.8%的元组未被选为训练集而留在检验集中,其余的63.2%将形成训练集第第4章章 分类和预测分类和预测 可以重复抽样过程k次,每次迭代,使用当前的检验集得到从当前自助样本得到的模型的准确率估计模型的总体准确率则用下式估计: (4.92).第第4章章 分类和预测分类和预测 4.10 小 结 分类和预测是两种数据分析形式,可以用来提取模型,描述重要数据类或预测未来的数据趋势分类预测分类标号(类),而预测建立连续值函数模型 分类和预测准备阶段的数据预处理可能涉及数据清理(减少噪声或处理缺失值)、相关分析(删除不相关或冗余属性)和数据变换(如泛化数据到较高的概念层,或对数据规范化)第第4章章 分类和预测分类和预测 预测的准确率、计算速度、鲁棒性、可伸缩性和可解释性是评估分类和预测方法的五条标准 ID3、C4.5和CART是决策树归纳的核心算法。
每种算法都使用一种属性选择度量,为树中每个非树叶节点选择测试属性剪枝算法试图通过剪去反映数据中噪声的分枝,提高准确率早期的决策树算法通常假定数据驻留内存——对大型数据库的数据挖掘是一种限制已经提出了一些可伸缩的算法来解决这一问题,如SUA、SPRINT和雨林算法第第4章章 分类和预测分类和预测 朴素贝叶斯分类和贝叶斯信念网络基于后验概率的贝叶斯定理与贝叶斯分类(假定类条件独立)不同,贝叶斯信念网络允许在变量子集之间定义类条件独立性 基于规则的分类器使用IF-THEN规则分类规则可以从决策树提取,还可以直接从训练数据采用顺序覆盖法和关联分类法产生 后向传播是一种用于分类的神经网络算法,使用梯度下降方法它搜索一组权重,这组权重可以对数据建模,使得数据元组的网络类预测和实际类标号之间的均方距离最小可以由训练过的神经网络提取规则,帮助改进学习网络的可解释性第第4章章 分类和预测分类和预测 支持向量机(SVM)是一种用于线性和非线性数据的分类算法它将原数据变换到较高维空间,使用称做支持向量的基本训练元组,从中发现分离数据的超平面 决策树分类法、贝叶斯分类法、后向传播分类、支持向量机和基于关联的分类方法都是急切学习方法的例子。
使用训练元组构造泛化模型,从而为新元组的分类做好准备这与诸如最近邻分类法和基于案例的推理分类法等惰性学习方法或基于实例的方法相反,后者将所有训练元组存储在模式空间中,一直等到检验元组出现才进行泛化因而,惰性学习方法需要有效的索引技术第第4章章 分类和预测分类和预测 线性、非线性和广义线性回归模型都可以用于预测许多非线性问题都可以通过预测器变量的变换,转换成线性问题与决策树不同,回归树和模型树都可以用于预测在回归树中,每个树叶都存放连续值预测在模型树中,每个树叶都存放一个回归模型 分层k折交叉确认是一种推荐的评估准确率的方法对于分类,灵敏性、特效性和精度都是准确性度量的有用的选择,当感兴趣的主类为少数类时尤其如此有许多预测器误差度量,如均方误差、均值绝对误差、相对平方误差和相对绝对误差第第4章章 分类和预测分类和预测 已有许多不同的分类和预测方法的比较,并且该问题仍然是一个研究课题尚未发现有一种方法对所有数据集都优于其他方法如准确性、训练时间、鲁棒性、可解释性和可伸缩性都必须考虑,并且可能涉及比较评定,使得寻求更好方法进一步复杂化实验研究表明,许多算法的准确性非常类似,其差别不是统计显著的,而训练时间可能显著不同。
对于分类,大部分神经网络和涉及样条的统计方法与大部分决策树方法相比,趋向于更加计算密集。
