统计学习与模式分类

1、软计算专题3：统计学习与模式分类(2) （Statistical Learning and Pattern Classification）商船学院 彭静二、统计学习一、概率论基础知识概率论基本概念(1)随机变量及其分布cdf(Cumulative Distribution Function)pdf(Probability Density Function)/ pmf(Probability Mass Function)多元随机向量及其分布联合分布、边缘分布、条件分布贝叶斯公式条件独立Pr(Ai) = Prior distribution for the Ai. It summarizes yo

2、ur beliefs about the probability of event Ai before Ai or B are observed.Pr( B | Ai ) = The conditional probability of B given Ai. It summarizes the likelihood of event B given Ai. k Pr( Ak ) Pr( B | Ak ) = The normalizing constant. This is equal to the sum of the quantities in the numerator for all

3、 events Ak. Pr( Ai | B ) = The posterior distribution of Ai given B. It represents the probability of event Ai after Ai has B has been observed.范例吸毒者检测假设一个常规的检测结果的敏感度与可靠度均为99%，假设某公司将对其全体雇员进行一次鸦片吸食情况的检测，已知0.5%的雇员吸毒。问：每位医学检测呈阳性的雇员吸毒的概率有多高？（令“D”为雇员吸毒事件，“N”为雇员不吸毒事件，“+”为检测呈阳性事件。）概率论基本概念(2)期望期望的直观和数学含义条件期

4、望方差方差的直观和数学含义条件方差协方差/相关系数常见的离散型概率分布二项分布泊松概率常见的连续型概率分布均匀分布正态分布指数分布连续型随机变量的概率分布正态分布均匀分布其他分布几何分布离散型随机变量的概率分布泊松分布二项分布正态分布描述连续型随机变量的最重要的分布可用于近似离散型随机变量的分布例如: 二项分布经典统计推断的基础正态分布是一个分布族，每一特定正态分布通过均值的标准差来区分。决定曲线的高度，决定曲线的平缓程度，即宽度xf(x)CAB二、统计学习方法概述机器学习的基本问题和方法机器学习根据给定的训练样本求对某系统输入输出之间依赖关系的估计，使它能够对未知输出作出尽可能准确的预测。机

5、器学习问题的表示根据n个独立同分布观测样本确定预测函数f(x,w)。在一组函数f(x,w)中求一个最优的函数f(x,w0)对依赖关系进行估计，使预测的期望风险最小。训练器(S)学习机(LM)输入x输出y机器学习实现方法经典的参数统计估计方法需要已知样本分布形式样本数目趋于无穷大经验非线性方法缺乏统一的数学理论统计学习方法专门研究给定样本（特别是小样本情况）下的机器学习规律追求现有信息条件下的最优结果学习问题的一般表示学习目标Given an i.i.d. l-sample z1,zl drawn from a fixed distribution F(z)For a function clas

6、s loss functions Q(z,), with in We wish to minimise the risk, finding a function *相关概念损失函数 loss function (L, Q)：the error of a given function on a given example风险函数risk functional (R)：the expected loss of a given function on an example drawn from F(x,y) 学习问题的一般表示学习的目的在于使期望风险最小化，由于可利用的信息只有样本，期望风险往往无法

7、计算。经验风险最小化归纳原则 (The Empirical Risk Minimization (ERM) Inductive Principle)核心思想：用样本定义经验风险。Define the empirical risk (sample/training error):Define the empirical risk minimiser:ERM approximates Q(z,*) with Q(z,l) the Remp minimiserthat is ERM approximates * with lLeast-squares and Maximum-likelihood a

8、re realisations of ERMERM准则与统计学习理论的发展经验风险最小并不意谓着期望风险最小! 例子：神经网络的过学习问题。训练误差小并不总能导致好的预测效果. 若对有限的样本来说学习能力过强，足以记住每个样本，此时经验风险很快就可以收敛到很小甚至零，但却根本无法保证它对未来样本能给出好的预测. 需要在小样本情况下建立有效的学习和推广方法的理论小样本条件下的统计学习理论支持向量机(SVM)三类基本的机器学习问题模式识别问题：输出y是类别标号，两类情况下y=1,-1，预测函数称作指示函数(Indicator Function)，损失函数定义见下式，使期望风险最小就是Bayes决策

9、中使错误率最小。函数拟合问题：输出y是连续变量，它是x的函数，损失函数定义见下式:概率密度估计问题：根据训练样本确定x的概率分布p(x,w)，则损失函数可定义为:统计学习方法概述统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。 统计方法处理过程可以分为三个阶段：（1）搜集数据：采样、实验设计（2）分析数据：建模、知识发现、可视化（3）进行推理：预测、分类常见的统计方法有:回归分析（多元回归、自回归等）判别分析（贝叶斯判别、费歇尔判别、非参数判别等）聚类分析（系统聚类、动态聚类等）探索性分析（主元分析法、相关分析法等）等。统计学习方法的基本问题有监督/无监督学习有监督(Supervi

10、sed)：分类、回归无监督(Unsupervised)：概率密度估计、聚类、降维增强学习(Reinforcement Learning)模型选择模型评价：损失函数模型选择参数模型 vs. 非参数模型 复杂性 vs. 推广性有监督学习对训练样本集中的每一组输入能提供一组目标输出学习机根据目标输出与实际输出的误差信号来调节参数训练器(S)学习机(LM)比较环境实际输出输入期望输出误差信号p(n)t(n)a(n)e(n)S(x)=0 Class AS(x)0Class BS(x)=0ObjectsX2(area)(perimeter) X1Object Representation in Featu

11、re Space有监督学习框架示例：分类非监督学习与增强学习非监督学习：不存在教师，学习机根据外部数据的统计规律来调节系统参数，以使输出能反映数据的某种特性。增强学习：外部环境对输出只给出评价信息而非正确答案，学习机通过强化受奖励的动作来改善自身的性能。学习机(LM)环境输入学习机(LM)环境输入输出评价信息示例：聚类三、贝叶斯决策理论Bayes决策理论有什么用？用不同方法可能得到多个不同的估计，哪个估计更好一些？统计决策理论：比较统计过程的形式化理论决策是从样本空间S，到决策空间的一个映射，表示为D: S 评价决策有多种标准，对于同一个问题，采用不同的标准会得到不同意义下“最优”的决策。Ba

12、yes决策常用的准则最小错误率准则最小风险准则在限定一类错误率条件下使另一类错误率为最小的准则最小最大决策准则问题描述：Classification Problem给定：m个类，训练样本和未知数据目标：给每个输入数据标记一个类属性两个阶段：建模/学习：基于训练样本学习分类规则.分类/测试：对输入数据应用分类规则P(f1)f1鹅卵石救命稻草杆Pebbles StrawspebblesStrawsf1f2决策边界最大后验(Maximum A Posterior, MAP)分类什么是最优分类器?已有:类条件概率密度函数This is called the class-conditional prob

13、ability describing the probability of occurrence of the features on category.欲求:后验概率make a decision that maximize the conditional probability of the object, given certain feature measurements. Also called posterior probability function. p(x|1)p(x|2)类条件概率密度函数p(1|x)后验概率p(2|x)Bayes最小错误率(MAP)决策MAP决策:以后验

14、概率为判决函数:Choose category/class that has the maximumThis produces the optimal performance: minimum probability of error:A classifier that achieves this optimal performance is called Bayesian classifier.MAP决策的错误率Bayes Decision Rule minimizes the average error rate:Bayes决策是一致最优决策。使得每个观测值下的条件错误率最小因而保证了（平

15、均）错误率最小。基于最小错误率的贝叶斯决策规则平均错误率对于两类别问题An Example “I see a member of my family on the beach in a bikini. Surely that couldnt be Granny, but look, her hair is totally gray, so I guess it really is her.” What is the probability that it is Granny given the observation (hair gray)?p(Granny in bikini) = 0.01

16、 (almost unlikely)p(Wife in bikini) = 0.99p(hair gray |Granny)=0.5p(hair gray |Wife) = 0.001 (odd lighting？)Granny in a bikini p(m)=p(hair gray)=p(hair gray|wife)p(wife) + p(hair gray | Granny)p(Granny) = 0.5x0.01 + 0.001x0.99=0.006p(Gran|m)=p(hair gray|Gran) p(Gran)/p(hair gray) =0.005/0.006 = 5/6p

17、(Wife|m) = p(hair gray|Gran)p(Gran)/p(hair gray) = 0.001/0.006 = 1/6So we make a decision: It is really Granny! :-OMAP决策的扩展：最小Bayesian风险决策的风险：做决策要考虑决策可能引起的损失。以医生根据白细胞浓度判断一个人是否患血液病为例：没病(1)被判为有病(2) ，还可以做进一步检查，损失不大；有病(2)被判为无病(1) ，损失严重。Bayesian Risk: Combine decision riskThe risk of making a wrong decis

18、ionDecision Risk tableThe risk to make a decision : classify x (belong to class i) to class j, so:Decision Rule:例2：假设在某个局部地区细胞识别中正常（w1）和异常（w2）两类的先验概率分别为：正常状态： P(w1)=0.9异常状态： P(w2)=0.1（1）现有一待识别的细胞，其观察值为x，从类条件概率密度分布曲线上查得P(x|w1)=0.2， P(x|w2)=0.4试对该细胞x进行分类？（2）判断损失的决策表如下，试按照最小风险贝叶斯决策进行分类。损失12106210Bayes决

19、策：讨论基于Bayes决策的最优分类器Bayes决策的三个前提：类别数确定各类的先验概率P(Ci)已知各类的条件概率密度函数p(x|Ci)已知问题的转换：基于样本估计P(Ci)和p(x|Ci)基于样本直接确定判别函数四、主要统计学习方法简介统计学习方法统计推理用数据的似然度(likelihood)和假设(Hypothesis)的概率去预测新实例的值Bayesian学习：预测时利用所有假设的概率MAP：预测时只利用具有最高概率的假设ML：假定所有的假设均匀分布朴素Bayes方法(Nave Bayes, NB)基于实例的学习最近邻方法(Nearest Neighbor)神经网络(Neural Ne

20、tworks)支持向量机(Support Vector Machine)4.1 Bayesian学习基本思想给定训练数据 ,计算每个假设 的概率利用此概率来进行预测（注：预测时利用所有的假设，而不仅仅利用最好的一个）参数估计问题若训练数据独立同分布(i.e., i.i.d)，则对分类问题，需要估计两个参数：类的先验概率P(Ci)和类条件概率密度p(x|Ci)对分类问题，假设hi可直接视为类属性CiBayesian学习：示例Bayesian学习:参数估计的方法类的先验概率P(Ci)的估计：用训练数据中各类出现的频率估计依靠经验类条件概率密度p(x|Ci)估计的两种主要方法：参数估计：概率密度函数

21、的形式已知，而表征函数的参数未知，通过训练数据来估计最大似然估计Bayes估计（最大后验估计）非参数估计：密度函数的形式未知，也不作假设，利用训练数据直接对概率密度进行估计KN-近邻法Parzen窗法最大似然估计Maximum Likelihood (ML)样本集可按类别分开，不同类别的密度函数的参数分别用各类的样本集来训练。概率密度函数的形式已知，参数未知，为了描述概率密度函数p(x|Ci)与参数的依赖关系，用p(x|Ci,)表示。估计的参数是确定而未知的，Bayes估计方法则视为随机变量。独立地按概率密度p(x|)抽取样本集K=x1, x2 , xN，用K估计未知参数最大似然估计似然函数：

22、对数(loglarized)似然函数：ML估计例3（最大似然估计1：离散分布，离散有限参数空间 ） 考虑一个抛硬币的例子。假设这个硬币正面跟反面轻重不同。我们把这个硬币抛80次（即，我们获取一个采样 x1=H, x2=T,x80=T并把正面的次数记下来，正面记为H，反面记为T）。并把抛出一个正面的概率记为p，抛出一个反面的概率记为1 p（因此，这里的p即相当于上边的）。假设我们抛出了49个正面，31 个反面，即49次H，31次T。假设这个硬币是我们从一个装了三个硬币的盒子里头取出的。这三个硬币抛出正面的概率分别为p = 1 / 3, p = 1 / 2, p = 2 / 3. 这些硬币没有标记

23、，所以我们无法知道哪个是哪个。使用最大似然估计，通过这些试验数据（即采样数据），我们可以计算出哪个硬币的可能性最大。这个可能性函数取以下三个值中的一个： 我们可以看到当 时，可能性函数取得最大值。这就是p的最大似然估计. 例4（最大似然估计2：离散分布，连续参数空间）现在假设例3的盒子中有无数个硬币，对于中的任何一个p， 都有一个抛出正面概率为p的硬币对应，我们来求其可能性函数的最大值：其中0p1. 我们可以使用微分法来求最值。方程两边同时对p取微分，并使其为零。在不同比例参数值下一个二项式过程的可能性曲线 t = 3, n = 10；其最大似然估计值发生在其众数并在曲线的最大值处。其解为p

24、= 0, p = 1，以及p = 49 / 80. 使可能性最大的解显然是p = 49 / 80（因为p = 0 和p = 1 这两个解会使可能性为零）。因此我们说最大似然估计值为 例5（最大似然估计3：连续分布，连续参数空间）贝叶斯估计（最大后验概率）用一组样本集K=x1, x2 , xN估计未知参数未知参数视为随机变量，先验分布为 p()，而在已知样本集K出现的条件下的后验概率为p(|K)最大后验概率估计-Maximum a posteriori (MAP)Bayes学习：非参数估计非参数估计：密度函数的形式未知，也不作假设，利用训练数据直接对概率密度进行估计。又称作模型无关方法。参数估计

25、需要事先假定一种分布函数，利用样本数据估计其参数。又称作基于模型的方法两种主要非参数估计方法：Parzen窗法KN-近邻法非参数估计方法在此不作详细介绍。最大似然估计、贝叶斯估计、贝叶斯学习之间的关系最大似然估计是把参数看成确定的未知参数。最大似然估计就是求使似然函数l()为最大的作为最大似然估计量。贝叶斯估计是把参数看成为随机的未知参数，一般具有先验分布p()。样本通过似然函数p(K|)并利用贝叶斯公式将的先验分布p()转化为后验分布p(|K)。最后求出贝叶斯估计量MAP，它使平方误差损失函数的贝叶斯风险极小化。贝叶斯学习是利用的先验分布极样本提供的信息求出的后验分布，然后直接求出总体分布p

26、(x|K)简化模型：朴素贝叶斯Nave Bayes朴素贝叶斯学习模型（NB ）将训练实例表示成属性(特征)向量A和决策类别变量C。假定特征向量的各分量间相对于决策变量是相对独立的，也就是说各分量独立地作用于决策变量。降低了学习的复杂性在许多领域，表现出相当的健壮性和高效性NB的特点结构简单只有两层结构推理复杂性与网络节点个数呈线性关系Ca1a2an-1anNB用于分类NB假设：设样本A表示成属性向量，如果属性ak对于给定的类别独立，那么P(A|Ci)可以分解成几个分量的积：简单贝叶斯分类 (SBC: Simple Bayesian Classifier)一般认为，只有在独立性假定成立的时候，S

27、BC才能获得精度最优的分类效率；或者在属性相关性较小的情况下，能获得近似最优的分类效果。朴素贝叶斯分类的工作过程朴素贝叶斯分类或简单贝叶斯分类的工作过程如下： 每个数据样本用一个n维特征向量 X x1 . x2 , ， xn 表示，分别描述对n个性质A1，A2，An产本的n个度量。 假定有 m 个类 C1，C2，Cm。给定一个未知的数据样本X （即没有类标号），分类法将预测X属于具有最高后验概率（条件 X下）的类。即是说，朴素贝叶斯分类将未知的样本分配给类 Ci，当且仅当这样，最大化 P(Ci |X)。其中 P(Ci |X)最大的类Ci称为最大后验假定。根据贝叶斯定理由于 P(X) 对于所有类

28、为常数，只需要 P(XI C;)P(C) 最大即可。如果类的先验概率未知，则通常假定这些类是等概率的，即 P(C 1 ) P(C 2 ) =P(C m ) 。并据此对只 P(C i | X ) 最大化。否则，最大化 P(X |C i )P(C i ) 。注意，类的先验概率可以用 P(C i ) s i / s 计算其中 s i 是类 C i 中的训练样本数，而 s 是训练样本总数。 给定具有许多属性的数据集，计算 P(XI Ci) 的开销可能非常大。为降低计算 P(X | C i ) 的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值相互条件独立，即在属性间，不存在依赖关系。这样

29、，概率 P( x 1 |C i ), P( x 2 lC i ),. .,P( x n |C i ) 可以由训练样本估值，其中(a) 如果Ak是分类属性，则 P(xk|Ci)sik/si其中，Sik是在属性Ak上具有值 xk的类Ci的训练样本数，而 si是类Ci中的训练样本数。 (b) 如果Ak是连续值属性，则通常假定该属性服从高斯分布。因而，其中，给定类Cj的训练样本属性Ak的值，g(xk,c,c)是属性Ak的高斯密度函数，而c,c分别是平均值和标准差。为对未知样本X分类，对每个类Ci，计算P(X|Ci)P(Ci)。样本X被指派到类 Ci，当且仅当 换言之，X被指派到其 P(X|Ci)P(C

30、i)最大的类Ci。朴素贝叶斯分类器设x = ，为一个有m个属性的样例= max P(a1,a2am|cj)P(cj)P(a1,a2am)= max P(a1,a2am|cj)P(cj)(1)P(cMAP|x)= max P(cj|x) j(1,|C|)= max P(cj|a1,a2am) 朴素贝叶斯分类器基于一个简单的假定：在给定目标值时属性值之间相互条件独立。换言之，该假定说明给定实例的目标值情况下，观察到联合的a1,a2am的概率正好是对每个单独属性的概率乘积 (2) 将(2) 式其代入(1)式中，可得到朴素贝叶斯分类器，如下CNB=argmax P(cj)（3） 其中CNB表示朴素贝叶

31、斯分类器输出的目标值。注意在朴素贝叶斯分类器中，须从训练数据中估计的不同P(ai|cj)项的数量只是不同的属性值数量乘以不同目标值数量这比要估计P(a1,a2am|cj)项所需的量小得多。概括地讲，朴素贝叶斯学习方法需要估计不同的P(cj)和P(ai|cj)项，也就是它们在训练数据上的频率。然后使用公式(3)来分类新实例。举例说明目标概念PlayTennis的训练样例 DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4Rai

32、nMildHighWeakYesD5RainCoolNormalWeakYesD6RainCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainMildHighStrongNo第一步统计个数表1 类别为cj及在cj条件下Ai取ai的样例数Out

33、lookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong2432433663Yes93022214123No5估计先验概率和条件概率表2 先验概率P(cj) 和条件概率P(ai|cj)OutlookTemperatureHumidityWindPlayTennisSunnyOvercastRainHotMildCoolHighNormalWeakStrong0.2220.4440.3330.2220.4440.3330.3330.6670.6670.333Yes0.6430.600

34、.40.40.40.20.80.20.40.6No0.357样例判别现在假设有一个样例xx = Sunny,Hot,High,Weak等于yes的概率 P(Yes|x)= p(Yes)*p(Sunny|Yes)* p(Hot|Yes)* p(High|Yes)* p(Weak|Yes)*=0.643*0.222*0.222*0.333*0.667=0.007039等于No的概率 P(No|x) = p(No)*p(Sunny| No)* p(Hot| No)* p(High| No)* p(Weak| No)*=0.357*0.6*0.4*0.8*0.4=0.027418max (P(Yes|

35、x), P(No|x) ) = P(No|x) ,所以我们把x分类为No概率为零 在大多数情况下，观察到的比例P(ai|cj)是对其真实概率的一个良好估计，但当|Ai=aiC=cj|很小时估计较差。特别是当|Ai=aiC=cj|等于0时，P(ai|cj)也等于0，如果将来的待估样例中，包含第i个属性的取值ai时，此概率项会在分类器中占统治地位。概率为零之m-估计 一般采用m-估计来解决这个问题。m-估计定义如下： pi是将要确定的概率P(ai|cj)的先验概率，而m是等效样本大小的常量，它确定了对于观察到的数据如何衡量pi的作用。在缺少其他信息是选择p的一种典型方法是假定pi =1/|Ai|。

36、也就是将nj个实际观察扩大，加上m个按pi分布的虚拟样本。概率为零之个数比较在本次实现中我们采用的不是m-估计，而是下面一种简单的0个数比较法。即下面的几条规则。在公式（3）中，对每一个类别j，统计P(ai|cj)=0的个数，记为zj。然后按以下3条规则得到CNB。1.如果对任意的j，zj都为0，则直接按公式（3）得到CNB3.如果对任意的j，zj不为0且不相等，则取zj最小者对应的类别作为CNB。若zj最小者不唯一，则对这些最小值对应的j采用第二条规则进行判别。2.如果对任意的j，zj不为0且相等，则按公式（3）计算时只计算P(ai|cj)为非零的项,然后得到CNB实验结果数据库训练样例测试

37、样例训练精度标准差测试精度标准差BALANCE5716391.40.00387.40.056Hatehi1481689.20.01187.10.053heart2512886.10.00583.90.033Mushroom654672799.50.00099.50.003TIC-TAC-TOE8719671.00.01070.00.055结果分析 从上面的实验结果我们可以得到朴素贝叶斯分类器的以下几个特点: 训练精度测试精度 意义明确,便于理解 时间复杂度低,可以应用大型数据库 易于实现增量扩展：贝叶斯网(Bayes Network)为了提高推理的准确性，人们引入了概率理论。贝叶斯理论是处理不

38、确定性信息的重要工具。最早由Judea Pearl于1988年提出的贝叶斯网络(Bayesian Network)实质上就是一种基于概率的不确定性推理网络。它是用来表示变量集合连接概率的图形模型，提供了一种表示因果信息的方法。作为一种基于概率的不确定性推理方法，贝叶斯网络在处理不确定信息的智能化系统中已得到了重要的应用，已成功地用于医疗诊断、统计决策、专家系统等领域。这些成功的应用，充分体现了贝叶斯网络技术是一种强有力的不确定性推理方法。= P(A) P(S) P(T|A) P(L|S) P(B|S) P(C|T,L) P(D|T,L,B)P(A, S, T, L, B, C, D) 条件独立

39、性假设有效的表示CPT: T L B D=0 D=10 0 0 0.1 0.90 0 1 0.7 0.30 1 0 0.8 0.20 1 1 0.9 0.1 .Lung CancerSmokingChest X-rayBronchitisDyspnoeaTuberculosisVisit to AsiaP(D|T,L,B)P(B|S)P(S)P(C|T,L)P(L|S)P(A)P(T|A)贝叶斯网络是表示变量间概率依赖关系的有向无环图贝叶斯网络的概率解释任何完整的概率模型必须具有表示（直接或间接）该领域变量联合分布的能力。完全的枚举需要指数级的规模（相对于领域变量个数）贝叶斯网络提供了这种联合

40、概率分布的紧凑表示：分解联合分布为几个局部分布的乘积： 需要的参数个数随网络中节点个数呈线性增长，而联合分布的计算呈指数增长。网络中变量间独立性的指定是实现紧凑表示的关键。思考：什么是贝叶斯网络？动态贝叶斯网络？如何使用Matlab的Bayes网络工具箱？有关贝叶斯网络的站点： （A Brief Introduction to Graphical Models and Bayesian Networks） 4.2基于实例的学习Instance-basedBayeis方法的缺陷参数估计误差不描述概率分布，而直接描述决策规则，如最近邻规则：直接从训练数据构造假设K近邻方法K-NN最近邻方法NN:

41、K=1K-NN方法对输入样本 x, 从训练样本中找到与x距离最近的K个最近样本，以它们最可能的类标签来分类xxk=1k=6K-NN的性能亚优：在训练样本足够的情况下，错误概率小于最优错误率的两倍. Where: is the probability of error for Bayesian inference (Optimal) and NN rule;不能在有限的样本下获得同样的断言.K-NN的关键问题距离度量最常用方法: euclidean更好的距离度量: normalize each variable by standard deviation离散数据：Hamming distance

42、K的选择Increasing k reduces variance, increases bias高维空间的可区分性差For high-dimensional space, problem that the nearest neighbor may not be very close at all!大数据量时计算开销大Must make a pass through the data for each classification. This can be prohibitive for large data sets.Indexing the data can help; for examp

43、le KD treesEuclidean Distance（欧式距离）Euclidean Distance between x and pk is: The decision rule based on this metric is called theminimum Euclidean Distance (MED) classifier. Note all the variables x and z here are vectors. Dont have to take the square root.Euclidean DistancePattern space in general is

44、 not a Euclidean vector space.The various measurement will be more or less dependent and will have different units and have different variances. For example: Mahalanobis Distance（马氏距离）用方差的倒数来进行加权，相当于使决策界从方差较大的一方朝方差较小一方移动:Let the distribution be approximated by a multivariate normal density. The Maha

45、lanobis distance from x to m is given by :Where is the covariance matrix and is the sample mean of the prototype. 4.3神经网络(NN)：模拟人脑的学习胞体(Soma)枝蔓（Dendrite）胞体(Soma) 轴突（Axon）突触（Synapse）4.3神经网络(NN)：模拟人脑的学习InputsignalSynapticweightsSummingfunctionActivationfunctionLocalFieldvOutputox1x2xnw2wnw1w0 x0 = +1

46、人工神经元模拟生物神经元的一阶特性。输入：X=(x1, x2, , xn)联接权：W=(w1, w2, ,wn)T网络输入：net=xiwi向量形式：net=XW激活函数：f网络输出：o=f(net)4.3神经网络(NN)：模拟人脑的学习NN的基本构成一组突触和联结，联结具有权值 w1, w2, , wn通过加法器功能，将计算输入的权值之和 net=xiwi激励函数限制神经元输出的幅度o=f(net)netooc线性函数（Liner Function） F(net)=k*net+c - - net o 非线性斜面函数（Ramp Function）a+b o(0,c)netac=a+b/2 S形

47、函数 典型激励函数x1x2xno1o2onwnmw11w1mw2mwn1输出层输入层典型网络结构:简单单级网输出层x1o1w11w1mx2o2w2mxnomwn1输入层V典型网络结构:单级横向反馈网典型网络结构:多级网输出层隐藏层输入层o1o2omx1x2xn典型网络结构:循环网x1o1输出层隐藏层输入层x2o2omxn4.4 支持向量机SVM是一种基于统计学习理论的机器学习方法，是由Boser, Guyon, Vapnik于1992年提出，目前已经取得了广泛的成功应用。统计学习理论的主要目标专门研究小样本下的机器学习规律追求现有信息条件下的最优结果Vapnik统计学习理论的主要内容为研究学习

48、过程的速度和推广性，定义了函数集学习性能的指标，其中最重要的是VC维。VC维反映了函数集的学习能力，VC维越大则学习机器越复杂(容量越大)。研究了对于各种类型的函数集，经验风险和实际风险之间的关系，即推广性的界。结构风险最小化(SRM)原则结构风险最小化原则实际风险由两部分组成：经验风险(训练误差)VC置信范围(VC confidence)，它和学习机器的VC维及训练样本数有关。结构风险最小化(SRM)的基本思想在有限训练样本下，学习机器的VC维越高则置信范围越大,真实风险与经验风险之间可能的差别越大.这就是为什么会出现过学习现象的原因。机器学习过程不但要使经验风险最小，还要使VC维尽量小以缩

49、小置信范围，才能取得较小的实际风险，即对未来样本有较好的推广性。结构风险最小化示意图基于统计学习理论的支持向量机支持向量机方法是建立在统计学习理论中的结构风险最小化和VC维基础上根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷，以获得最好的推广能力的方法。支持向量机(Support Vector Machine-SVM),从线性可分情况下的最优分类面发展而来。最优分类面最优分类面分类间隔(Margin).分类间隔最大:实际上就是对推广能力的控制，这是SVM的核心思想之一.输入: S=(xi,yi) Rn -1, 1,对应于

50、yi , xi 可表示为两类: xi H1, yi = -1 xi H2, yi = 1目标: 找到一个分类函数(x)=wx+b能够对训练数据 xi 正确分类, 对其他的输入能够正确推广.进一步说:找到一个超平面 H : wx+b=0和两个与H平行且等距离的 H1 : wx+b=1 H2 : wx+b= -1数学模型最优分类面-直观描述(a) 小的分类间隔 (small margin) (b) 大的分类间隔(larger margin). 最优分类面就是要求分类面能将两类正确分开(训练错误率为0),且使分类间隔最大A-A+MalignantBenignA+A-支持向量直观地说，支持向量是两类集

51、合边界上的点。所有非支持向量的数据都可以从训练数据集合中去掉而不影响问题解的结果。对于新的数据点 x,要对其进行分类只需要计算 f(x) = sign (w x + b )其中w 和b是支持向量对应的参数。SVM的分类问题SVM分类问题大致有三种：线性可分问题、近似线性可分问题、线性不可分问题线性可分问题近似线性可分问题线性不可分问题非线性可分线性可分:直观描述将训练样本非线性映射到高维特征空间 在高维空间构造线性支持向量机还原到原来的输入空间则是一个非线性决策面Using a feature map to map the data from input space into a higher dimensional feature space F:Define kernel Functions:In the linear case, the kernel function is XXXXOOOO(O)(O