1、第四章第四章 统计分类统计分类 统计决策理论统计决策理论根据每个类别的总体根据每个类别的总体概率分布决定决策边界概率分布决定决策边界 Bayes决策理论是统计决策的基本方法决策理论是统计决策的基本方法每一类出现的先验概率每一类出现的先验概率类条件概率密度类条件概率密度Bayes(贝叶斯贝叶斯)分类分类 如何使分类错误率尽可能小，是研究如何使分类错误率尽可能小，是研究各种分类方法的中心议题。各种分类方法的中心议题。Bayes决策理论是随机模式分类方法决策理论是随机模式分类方法最重要的基础。最重要的基础。几个重要的概念几个重要的概念 先验概率先验概率:预先已知的或者可以估计的预先已知的或者可以估计
2、的某种类型在识别系统中出现的概率。某种类型在识别系统中出现的概率。若用两个类型若用两个类型A和和B为例，用为例，用P(A)和和P(B)表示各自的先验概率。满足表示各自的先验概率。满足P(A)+P(B)=1。推广到一般的推广到一般的c类问题中，用类问题中，用1,2,C表示类型，则各自的先验概率用表示类型，则各自的先验概率用P(1),P(2),P(C)表示，表示，则则满足满足P(1)+P(2)+P(C)=1几个重要的概念几个重要的概念(续续)类条件概率密度类条件概率密度:系统位于某种类别条件下，系统位于某种类别条件下，模式样本模式样本X出现的概率密度分布函数。出现的概率密度分布函数。常用常用p(X
3、|A),p(X|B)以及以及p(X|1),p(X|2),p(X|C)来表示。来表示。几个重要的概念几个重要的概念(续续)后验概率后验概率:系统在某个具体的样本系统在某个具体的样本X下，下，属于某种类型的概率属于某种类型的概率 用用P(A|X),P(B|X)以及以及P(1|X),P(2|X),P(C|X)表示。表示。后验概率可以根据后验概率可以根据Bayes公式计算出来，可公式计算出来，可直接用作分类判决的依据。直接用作分类判决的依据。几个重要的概念几个重要的概念(续续)Bayes公式公式)()()|()|(XpPXpXPiii 全概率公式全概率公式CiiiPXpXp1)()|()(几个重要的概
4、念几个重要的概念(续续)正态分布的概率密度函数正态分布的概率密度函数(标量形式标量形式)，(方差)(均值或数学期望)其中dxxpxxEdxxxpxENxxp)(,)()(:),(21exp21)(22222几个重要的概念几个重要的概念(续续)正态分布的概率密度函数正态分布的概率密度函数(矢量形式矢量形式)的行列式为的逆阵,为维协方差矩阵为维均值向量维特征向量其中121211212),.,(,.,:21exp21)(，nnnnxxxXXXXpTnTnTn已知先验分布和观测值的类条件分布，已知先验分布和观测值的类条件分布，Bayes决策理论是最优的。决策理论是最优的。最小错误的最小错误的Bayes
5、准则准则 样本属于后验概率较高的那种类型样本属于后验概率较高的那种类型 对两类的情形对两类的情形1211221212(|)(|)(|)(|)(|)(|)PXPXXPXPXXPXPXXX或者)()()|()|(XpPXpXPiii12(|)(|)PXPX1122(|)()(|)()()()p XPp XPp Xp X即1122111222112212(|)()(|)()(|)()(|)()(|)()(|)()p XPp XPXp XPp XPXp XPp XPXX因此有：或者 前式又可写成似然比形式前式又可写成似然比形式2112212122111221)()()|()|()()()|()|()(
6、)()|()|(XXPPXpXpXPPXpXpXPPXpXp或者 上式两边同时加上自然对数等单调增函数，上式两边同时加上自然对数等单调增函数，结论都成立结论都成立2112212122111221)()(ln)|()|(ln)()(ln)|()|(ln)()(ln)|()|(lnXXPPXpXpXPPXpXpXPPXpXp或者05000100001500000.511.522.533.54x 10-4 X=3100,p(X=3100|1)=2.178510-4 p(X=3100|2)=5.712310-52211000200021exp100021)1000,2000()|(xNXp222300
7、0700021exp300021)3000,7000()|(xNXp2221exp21),(xN(|).(|)().().,-41-522122.1785 103 81375.7123 1099 51990 53 8137199p Xp XPPX该病人不患病多类问题的多类问题的Bayes最小错误准则最小错误准则ijjCjiiXPXpPXp)()|(max)()|(1Bayes准则的误差分析准则的误差分析最小风险的最小风险的Bayes准则准则 最小风险判决规则也是一种最小风险判决规则也是一种Bayes分分类方法。类方法。最小错误率判决规则没有考虑错误判最小错误率判决规则没有考虑错误判决带来的决带
8、来的“风险风险”，或者说没有考虑，或者说没有考虑某种判决带来的损失。某种判决带来的损失。同一问题中，某种判决总会有一定的同一问题中，某种判决总会有一定的损失，特别是错误判决有风险。不同损失，特别是错误判决有风险。不同的错误判决有不同的风险的错误判决有不同的风险。例如：宁可错杀一千也不放过一个。例如：宁可错杀一千也不放过一个。前例中，判断是否血液病，可能有两种前例中，判断是否血液病，可能有两种错误判决：错误判决：正常细胞错判为癌细胞；正常细胞错判为癌细胞；癌细胞错判为正常细胞。癌细胞错判为正常细胞。两种错误带来的风险不同。两种错误带来的风险不同。中，会给健康人带来不必要的精神负担，中，会给健康人
9、带来不必要的精神负担，可以进一步的检查排除可以进一步的检查排除中，会使患者失去进一步检查、治疗的中，会使患者失去进一步检查、治疗的机会，造成严重后果。机会，造成严重后果。显然，第显然，第种错误判决的风险大于第种错误判决的风险大于第种种 判决风险也可以理解为判决损失，即使判决风险也可以理解为判决损失，即使在正确判决的情况下，一般也会付出某在正确判决的情况下，一般也会付出某种代价，也会有损失。种代价，也会有损失。由于有判决风险的存在，最小错误率判由于有判决风险的存在，最小错误率判决就不够了，必须引入最小风险判决规决就不够了，必须引入最小风险判决规则。则。用用i,i=1C 表示对问题可能作出的判决。
10、表示对问题可能作出的判决。对于给定的模式样本对于给定的模式样本X，令，令ij=(i|j)表示表示X属于属于j而被判决为而被判决为i所带来的风险或者损失所带来的风险或者损失 条件风险（也叫条件期望损失）条件风险（也叫条件期望损失）XPEXRjCjjijii|1 通过最小化各个风险通过最小化各个风险R(i|X)就可以使就可以使总的平均风险最小。总的平均风险最小。因此可得到因此可得到Bayes最小风险的决策规最小风险的决策规则则ijCjiXXRXR采取决策对样本)|(min)|(.1()|)()RRXX p X dx 若令若令21 21=12 12，11 11=2222=0=0，则则 “最最小风险的
11、小风险的BayesBayes决策决策”等价于等价于“最小错最小错误的误的BayesBayes决策决策”书中书中4-19式为前公式在两类问题并且式为前公式在两类问题并且认为判别正确无损失认为判别正确无损失(ii=0)情况下的结情况下的结论论 加上风险的概念加上风险的概念对把原本属于对把原本属于1(血液病血液病)的样本诊断为正常带的样本诊断为正常带来的风险最大，为来的风险最大，为6对把原本属于对把原本属于2（正常）的样本诊断为血液病（正常）的样本诊断为血液病的风险为的风险为2正确诊断的风险为正确诊断的风险为0.5 1为判别有病，为判别有病，2为判别正常，可以得到风险为判别正常，可以得到风险矩阵：矩
12、阵：12111=0.512=2221=622=0.5 X=3100,p(X=3100|1)=2.178510-4 p(X=3100|2)=5.712310-5(|).(|)()()(.).()()(.).,-41-52122222111122.1785 103 81375.7123 1020 5 99 554 272760 5 0 53 813754 2727p Xp XPPX该病人不患病 12111=0.512=2221=60022=0.5 X=3100,p(X=3100|1)=2.178510-4 p(X=3100|2)=5.712310-5(|).(|)()()(.).()()(.).,
13、-41-52122222111112.1785 103 81375.7123 1020 5 99 50 56000 5 0 53 81370 5p Xp XPPX该病人患病Bayes分类器的决策函数形式分类器的决策函数形式 将前面的将前面的Bayes最小错误和最小风险决策最小错误和最小风险决策法则写成第二章介绍的决策函数形式，则法则写成第二章介绍的决策函数形式，则 最小错误的最小错误的Bayes决策决策:gi(X)=P(i|X)最小风险的最小风险的Bayes决策决策:gi(X)=-R(i|X)判别规则：判别规则：如果如果gi(X)gj(X)对于一切对于一切ij时成立，则决策时成立，则决策Xi类
14、类 针对最小错误的针对最小错误的Bayes决策，以下这决策，以下这些决策函数形式都有相同的分类结果些决策函数形式都有相同的分类结果 分类问题，决策边界应该满足分类问题，决策边界应该满足 gi(X)=gj(X)对两类问题，决策边界写成对两类问题，决策边界写成 g(X)=g1(X)-g2(X)判别规则：如果判别规则：如果g(X)0,则决策则决策X1类，否则决策类，否则决策X2类类 根据前面定义的根据前面定义的gi(X),有两种常用的有两种常用的g(X)形式形式正态形式的正态形式的Bayes分类分类 类条件概率密度类条件概率密度p(X|i)符合正态分布符合正态分布根据中心极限定理，大量独立同分布的随
15、根据中心极限定理，大量独立同分布的随机变量的和收敛于一个正态分布。机变量的和收敛于一个正态分布。的行列式为的逆阵,为维协方差矩阵为维均值向量维特征向量其中121211212),.,(,.,:21exp21)(，nnnnxxxXXXXpTnTnTn 等密度点的轨迹是等密度点的轨迹是一个超椭球面。区一个超椭球面。区域中心由域中心由决定，区决定，区域形状由域形状由决定，决定，椭圆第椭圆第i个主轴长度个主轴长度与与的第的第i个特征值个特征值i的平方根成正比的平方根成正比 下面对两类分类问题，当类条件概率下面对两类分类问题，当类条件概率密度函数为正态分布时不同情况下的密度函数为正态分布时不同情况下的情形
16、加以分析。情形加以分析。采用决策函数：采用决策函数：g1(X)=ln p(X|1)+ln P(1)g2(X)=ln p(X|2)+ln P(2)类条件概率密度函数：类条件概率密度函数：p(X|1)N(1,1)p(X|2)N(2,2)1111111122222211()()()ln2lnln()22211()()()ln2lnln()222TTdg XXXPdgXXXP 当当i=2I,决策面为：决策面为：)()()(ln)(210)(21212212210210PPXWXXWT其中 当当i=,决策面为：决策面为：)()()()()(ln)(21)(0)(212112121210211-0TTPP
17、XWXXW其中 当当i任意任意,判别函数对判别函数对X是二次的是二次的拒绝区域拒绝区域 很多样本都位于边界的周围，只要有一些微小的很多样本都位于边界的周围，只要有一些微小的调整就会改变判别的结果。这意味着，这些样本调整就会改变判别的结果。这意味着，这些样本很大程度上具有两个类别的特征。对于这些样本很大程度上具有两个类别的特征。对于这些样本而言，将它们归入一个特殊的类别以便进行进一而言，将它们归入一个特殊的类别以便进行进一步的测试是更加合理的。步的测试是更加合理的。有时候这种方法是必须的，例如在医学领域，当有时候这种方法是必须的，例如在医学领域，当边界处的病例处于正常与不正常之间时，就需要边界处
18、的病例处于正常与不正常之间时，就需要进一步的分析。实现这个目的的一个方法，就是进一步的分析。实现这个目的的一个方法，就是在计算后验概率并决定将在计算后验概率并决定将 x 归入第归入第 i 类时，加上类时，加上所谓的必要性所谓的必要性“检验检验”。我们可以规定如果概率大于我们可以规定如果概率大于 0.9 就定为就定为“确定确定”，如果概率在，如果概率在 0.8 到到 0.9 之间，就之间，就定为定为“很可能很可能”，如果低于，如果低于 0.8 就定为就定为“可能可能”例如例如:长度为长度为 55 cm的鱼被归入的鱼被归入“鲑鱼高质鲑鱼高质量量”这一类且被定为这一类且被定为“可能可能”级，而长度级
19、，而长度为为 45cm 的鱼被归入的鱼被归入“鲈鱼鲈鱼”这一类且被这一类且被定为定为“很可能很可能”级。级。除了根据后验概率分级外除了根据后验概率分级外,在某些情况下在某些情况下,我我们设定一个新的类别们设定一个新的类别,成为拒绝类或者拒绝成为拒绝类或者拒绝区域。区域。令令代表所做的分类决策，代表所做的分类决策，i i是对当前样是对当前样本本X X具有最大后验概率的类别，设置具有最大后验概率的类别，设置r r为拒为拒绝阈值点，最大后验概率绝阈值点，最大后验概率P(P(i i|X|X)必须高于必须高于r r才能归入才能归入i i类类(|)(|)iirririfPxifPx模型模型-无关技巧无关技
20、巧 在不知道类条件概率密度函数在不知道类条件概率密度函数p(X|i)的情况下，采用统计的思想对各个点的情况下，采用统计的思想对各个点的密度进行估计，逐步逼近的密度进行估计，逐步逼近p(X|i)。选择适当大小形状的窗户，看落入窗选择适当大小形状的窗户，看落入窗户内的点的多少来估计该窗户所在为户内的点的多少来估计该窗户所在为止的密度止的密度 此方法估计概率密度函数要求连续性此方法估计概率密度函数要求连续性和平滑性。和平滑性。点点X对应的概率密度函数对应的概率密度函数p(X)可以考虑可以考虑一个包围一个包围X的一个非常小的邻域，其体的一个非常小的邻域，其体积为积为V，p(X)V可以近似认为是所有样可
21、以近似认为是所有样本中落入区域本中落入区域R的概率的概率RduupVXp)()(Xp(X)假设样本总数为假设样本总数为n时，有时，有k个样本个样本落入区域落入区域R中，由大数定理可知，中，由大数定理可知，当样本总数当样本总数n足够大时，样本落入足够大时，样本落入区域区域R中的概率约为中的概率约为k/n,我们可以我们可以得到：得到：VnkXp/)(需要考虑的是体积需要考虑的是体积V也就是区域也就是区域R的选取的选取R太小，得到的估计不稳定，变化尖锐太小，得到的估计不稳定，变化尖锐R太大，得到的估计太平滑，无法反映真实太大，得到的估计太平滑，无法反映真实的变化情况。的变化情况。可以用以下两种方法来
22、调节可以用以下两种方法来调节固定体积不变固定体积不变:能够获取的训练样本越多，能够获取的训练样本越多，设定的体积就越小设定的体积就越小parzen窗函数窗函数固定固定k值不变值不变:根据能够获取的样本数来确定根据能够获取的样本数来确定k值值k近邻法近邻法 采用模型无关技巧中，一般用采用模型无关技巧中，一般用于低维空间，因为在高维空间于低维空间，因为在高维空间中，随着维数的增加，需要的中，随着维数的增加，需要的样本数急剧膨胀。样本数急剧膨胀。Parzen窗函数法窗函数法 根据样本数根据样本数n来确定区域来确定区域R，可以用边，可以用边长为长为h(n)的的d维超正方体来表示，通过维超正方体来表示，
23、通过改变改变h(n)可以选择合适的区域可以选择合适的区域R。V(n)=hd(n)1111)201()()()kniixkdXXXk nXh n（，：定义其余希望样本落入区域R中则被计数为因此为超立方体中心Xh(n)X2X1n)很小(X,p则样本，当X邻域中只有少量的n)很大(X,p则本，当X邻域中有大量的样因此)()(1),(1niinhXXnnVnXp0limlim0limnkkVnnnnnn但均需满足：函数，可以采用别的形式的窗域外，除了采用立方体作为邻 例：采用正态窗函数，并设例：采用正态窗函数，并设hn=h1/n，考虑取考虑取h1=1/4，1，4，得到以下结，得到以下结果果采采用用正正
24、态态窗窗函函数数K-近邻法近邻法 原理：以样本原理：以样本X为中心的邻域中，固为中心的邻域中，固定落入邻域中的样本个数定落入邻域中的样本个数k(n)实现：在一个合适的距离尺度下，逐实现：在一个合适的距离尺度下，逐渐增大包围样本渐增大包围样本X点的区域的体积，点的区域的体积，直到有直到有k个样本点落入到这个区域中，个样本点落入到这个区域中，这样则确定了这样则确定了V(X)。若若X周围样本点个数较少，相应的邻周围样本点个数较少，相应的邻域会很大，域会很大，V(X)会很大，则该点的概会很大，则该点的概率密度函数就很小率密度函数就很小 若若X周围样本点个数较多，相应的邻周围样本点个数较多，相应的邻域会
25、很小，域会很小，V(X)会很小，则该点的概会很小，则该点的概率密度函数就很大率密度函数就很大)(/)()(XVnnkXp分类器的评价分类器的评价 根据已有的训练样本设计出相应的分根据已有的训练样本设计出相应的分类器，则需要对该分类器进行性能测类器，则需要对该分类器进行性能测试，用来测试的样本集称为试，用来测试的样本集称为测试集测试集。当手头能够获取的样本数量有限时，当手头能够获取的样本数量有限时，需要合理的对训练集和测试集进行分需要合理的对训练集和测试集进行分配配 重复利用法重复利用法整个样本集既作训练集，又作测试整个样本集既作训练集，又作测试集，这样得到的错误率过于乐观集，这样得到的错误率过
26、于乐观 两分法两分法整个样本集分为两份，一份为训练整个样本集分为两份，一份为训练集，一份为测试集，如此随机划分集，一份为测试集，如此随机划分几次，将得到的错误率作平均几次，将得到的错误率作平均 样本划分法：将现有的样本划分为一定样本划分法：将现有的样本划分为一定数目的子集，然后循环的利用这些自己数目的子集，然后循环的利用这些自己进行分类器的训练和测试进行分类器的训练和测试将总样本随机划分成将总样本随机划分成k个子集，每个子集有个子集，每个子集有n/k个样本个样本利用其中利用其中k-1个子集作为训练集，然后利用个子集作为训练集，然后利用剩余的那个子集作测试，得到错误率剩余的那个子集作测试，得到错
27、误率选择不同子集作测试集，循环第二步，得到选择不同子集作测试集，循环第二步，得到k个错误率个错误率对对k个错误率求均值和方差个错误率求均值和方差 备注备注:这里所说的分类器不是参数固定的决策面，这里所说的分类器不是参数固定的决策面，而是某种设计分类器的方法。而是某种设计分类器的方法。(例如：贝叶斯分类例如：贝叶斯分类器，但是参数未定；通过不同的训练集会获得不器，但是参数未定；通过不同的训练集会获得不同的参数，不同的测试集获得不同的错误率，通同的参数，不同的测试集获得不同的错误率，通过平均获得对当前数据集采用某种分类器设计方过平均获得对当前数据集采用某种分类器设计方法的平均错误率）法的平均错误率
28、）ROC曲线曲线 An introduction to ROC analysis特征选择特征选择 主成分分析主成分分析 基于最优准则的特征抽取基于最优准则的特征抽取基于最优准则的特征选择基于最优准则的特征选择 原始原始t个特征，个特征，F是选择特征的子集是选择特征的子集 特征选择的过程就是寻找使得某种目特征选择的过程就是寻找使得某种目标函数最优的特征子集的过程。标函数最优的特征子集的过程。穷举法穷举法 分枝定界法分枝定界法特征总个数特征总个数5，保留特征，保留特征2，丢弃个数为，丢弃个数为3，最后最后x1,x4,x5被丢弃被丢弃特征评价特征评价 图形考察图形考察盒装图盒装图三类数据用特征三类数
29、据用特征 ART和特征和特征 RAN 刻画时的散布图，和其他特征相比，刻画时的散布图，和其他特征相比，它们之间关联较少且有较强的分类能力它们之间关联较少且有较强的分类能力 分布模型评价分布模型评价 我们常常假定关于这些样本的一个分布模型。我们常常假定关于这些样本的一个分布模型。使用前我们必须估计一下特征向量的分布是否使用前我们必须估计一下特征向量的分布是否与我们使用的模型较好的吻合。与我们使用的模型较好的吻合。一些统计软件里包含了检验一个分布与模型吻一些统计软件里包含了检验一个分布与模型吻合程度的程序。例如通过柱合程度的程序。例如通过柱状图状图 Kolmogorov-Smirnov(简称简称 KS 检测检测)
