英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料
多类线性降维加权结对Fisher准则
摘要：我们通过引入与线性判别分析（LDA）相关联的著名的K类别 Fisher准则的加权变体来派生出一个计算价格低廉的线性特征降维准则。它可以看作是LDA根据各个类表示的欧式距离的权重贡献。我们通过引入不同的加权函数.
1 简介
减少统计模式分类的特征维数是一种常用的技术用来解决估计问题以及与此相关的问题。在k－类问题的线性降维（LDR）中最知名的技术是线性判别分析（LDA）（FIsher5 介绍了2类LDA，而 RAo13把LDA推广到多类）：一个从一个n维的特征空间到一个d维空间的转换矩阵被确定使得总散射对平均类内离散的Fisher准则被最大化。坎贝尔表明，LDA的变换确定相当于找高斯模型的最大似然（ML）参数估计，假设所有类辨别信息主流在n维特征空间的d维子空间而且所有类的类内方差相等。
然而，对于一个Kgt;2的k类别问题来说，Fisher准则显然不理想。这一点可以在K类Fisher准则的分解（第二部分）成 1/2K（K－1）二类别标准的过程中看出，在那里它变得明显，大类距离被过分强调。所得转化保留了已经分好的类的距离，使得相邻类出现大的重叠，这对于考虑分类正确率来说是不理想的结果。但是，这种分解允许我们为了提高LDA来加权各个类对整体准则的贡献。在本文（第三节）讨论的权重方案被称为近似成对精度标准（aPAC ）［10］：在这里，权重是由企图逼近贝叶斯错误对类派生。虽然这种线性特征降维的方法可以被看作是LDA的一种概括，LDA的计算简单性被保留：一个广义的特征值问题必须解决，并且不需要复杂的迭代优化。
第四节比较了基于我们的aPAC的LDR方法和一个基于神经网络的方法。该理论的部分以前［10］中报道过而且实验结果已经在［4］中发表。结论则给第5节给出。
一些多类LDR的替代方法是已知的。在其中一些方法中，问题被陈述为一个ML估计任务，比如［9］［7］，在其它方法中散度被用于类分离的度量。然而，这些标准和分类正确率也没有直接的关系。这也同样适用于Young和 Odell基于特征值分解的方法。处理类重叠问题的程序通常采用迭代，因此需要更多的计算能力。例如，［8］中描述的帕特里克－菲舍尔方法，神经网络［8］中的非线性主成分分析，和常见的Buturovic［1］表明的非参数方法。
2 菲舍尔准则以及它的非最优状态
多类LDR关注的是寻求一个线性变换，该变换在把包含K个类的给定的n维统计模型降为d维（d lt;n）的同时在低维模型中保存最大量的判别信息。但是，在一般情况下，情况太复杂而不能直接把贝叶斯错误作为准则，这时需要一个不是最理想但是更易于优化的准则。LDA就是这样一个次优的准则。
一个转换矩阵被确定最大化 Jf，这就是所谓的菲舍尔准则：
（1）
这里,是类间协方差矩阵和类内协方差矩阵的集合，其中,K是类的数量，mi表示类i的均值矢量，pi是它的一个先验概率，而且整体均值mi等于。此外，Si是类i的类内协方差矩阵。可以从（1）看出，LDA使得类间散布 在低维空间的平均类内散步比例最大化。这个最优化问题的解决方法是由 Sw Sb 的特征值分解和取L的行等d个最大特征值对应的d个特征向量[6]。只要dgt;=K-1，当类为正态分布时信息不会有任何丢失。但是，任何使得维度降到K-1以下的降维都会扰乱类距。所以，现在的问题是：我们如何找到一个子空间在其中类方法的投影保留了这些距离使得类别可分离性尽可能的保持？
作为我们解决这个问题的方法的一部分，类间散列矩阵Sb，被改下为入如下
（2）
注意，分解使我们能够根据类含义的区别写出类间散列矩阵而且这项（mi-mj）（mi-mj）实际上是类i和i在一个二类模型的类间散列矩阵。使用（1）种的分解，我们获得费舍尔准则
（3）
其中 Sij=（mi-mj）（mi-mj）T。因此我们可以看出K类费舍尔准则可以被分解为1/2K（K-1）个2类费舍尔准则。在这篇文章种，我们把这些准则称作成对费舍尔准则。
现在，为了简化以后的讨论，假设汇聚类內散列矩阵等于n阶单位矩阵In 并假定A的行被缩放为正交：AAt = Id。这些限制不会影响到我们最终结论（见3.3），然后我们可以活得用于费舍尔准则（3）的下面的表达式：
其中 是一个被降维的模型中类i和j之间的平均平方距离。因此我们看到LDA方法到LDR是最大化低维空间类间的平均平方距离的线性变换。然而。这和最小化分类误差明显不同。
为了说明，考虑一个n维模型把它降为1维。假设一个类远离其他类就可以被称作一个异常值。在这种情况下，这个项目在优化费舍尔准则的方向是把这些异常值尽可能的与原来的类群分离。在最大化平方距离的情况下，类间距离很大的对类完全主宰了特征值分解过程。结果剩余的类之间有很大的重叠，导致一个低且不理想的整体分类率。
因此，在一般情况下，通过LDA的LDR对于最小化在低维空间里的分类错误率来说不是最佳的。因为离群类占据了特征值分解的主要部分，但是由LDR转换得到的会过度的影响已经分好的类。
3 加权结对费舍尔准则
3.1降为一维
我们现在来修改费舍尔准则使得它和分类错误相关度更高。但是我们想保留（3）的一般形式因为这样优化可以通过一个求广义特征值的问题来执行而不用采取复杂的迭代优化方案。为了达到目的，（3）通过引入一个加权函数omega;来推广：
（4）
其中是一个基于类i和类j在原始模型种中马氏距离的加权函数。
我们把这些准则称作加权结对费舍尔准则。这是一个合理的扩展，因为2个类之间的贝叶斯错误页取决于马氏距离。
找到一个解决方法L来优化准则，其优化方式和优化费舍尔准则的方式类似并且归结为确定矩阵的特征值分解
（5）
并且取dtimes;n的矩阵的行等于d个最大特征值所对应的特征向量d个特征向量。显然，选择常数函数omega;把Delta;ij映射到1是普通的费舍尔准则。
我们应该引入一个加权函数这样每个类对的权重就取决于类间的贝叶斯错误率。让我们再次假设，因此Delta;ij 等于普通欧式距离。（一般情况在3.3节中讨论）。然后，一个平均结对精度标准可以被表示为如下的方式：
（6）
这里，Aij(A)表示在低维空间中通过变换A得到的类i和类j的准确率（1减去贝叶斯错误率）。值得注意的是这个准则不同于K类问题贝叶斯准确率的最大化。
为了说明我们引入了哪些额外的近似值来把成对精度准则变为（4）的 形式，我们首先考虑一个将要被投射到一维的二类模型。模型如图1.a所示。改模型包含了2个常分布类i和j并且它们有单位协方差矩阵和相同的先验概率。聚类之间的距离被描述为
而且向量V表示我们把这个模型从二维投影到一维的矢量。这个向量，其中alpha;为向量V和垂直于mij 的轴之间的夹角。
在按照v投影后得到的一维模型的准确率Aij 可以表示为alpha;而且Delta;ij ：Aij(v)=
， 等于1减2个带方差的正态分布类的贝叶斯错误率和聚类之间的距离。另一方面，（4）读取此特殊模型
(7)
(K=2) ,其中矩阵A被行向量V替换因为我们把维数降为了1.注意这2个准则（7）和（6）并不是在所有的alpha; 取值下都相等（见图1.b和1.c）。
我们已经选择了近似（6）通过（7）的表达形式这样就可以在alpha;的极值，比如alpha;等于 0，pi;/2,pi;出达到相等（添加一个额外的常数1/2）。这样就推出了如下的加权函数： ，到这里，让V成为mij 的方向向量，比如。然后我们就可以得到（7）中的和项
（8）
是当alpha;等于pi;/2 准确的正确率，可以达到1/2的附加常数。但是，这个常数并不会影响优化。如果v垂直于mij(比如alpha;=0，pi;) ，然后等于0，贝叶斯准确率再一次高达常数1/2。
在图1种，我们说明了2种Delta;ij 取值下由表达式（7）得到的近似值，图像描绘了Aij(v)（实线）和加了一个常数1/2的近似值（虚线）随着alpha;变量变化的曲线。我们可以看到这个近似值估低了准确率，只有在极值处二者的准确率才相等。
图1.a 二类模型 其中v是投影方向向量，alpha;是v和X轴之间的夹角
图1.b 和图1.c 表示的是贝叶斯准确率。（实线）和估计值
（虚线）随着a中二类模型角度alpha; 的变化而变化的曲线，
其中（b）：Delta;ij =1
（c）：Delta;ij =9
3.2降到多维
遗憾的是，（7）只提供了降到一维的平均结对准确率的近似值因为V是一个向量。在一般要降到d（dgt;1）的情况下，我们采用一个和LDA类似的程序：确定（5）的特征值分解然后将LDR的转换矩阵L的行等于d个最大特征值对应的特征向量。矩阵L 最大化（4）。要看到这个过程提供和3.1节描述的减到1维的技术相等的结对精度，需要考虑以下论据。
因为我们仍然假设Sw=In，对称矩阵L是由特征向量组成。（N.B. ，我们略去了总和的限制当这些公式在文章中时），因此产生了一组正交向量我们表示为e1到ed。使用这个，我们可以写出（4），用L=（e1，...，ed）T代替A，如下：
（9）
注意（9）中的每一项都和（7）是类似的。我们可以看到最大化意味着我们确定了d个相互正交的方向，并且在这些方向的精度之和最大。而且假设特征向量em对应第m个最大的特征值，我们可以看到e1是近似值平均结对精确度最大的方向。特征向量e2实际上也是最大化准确度的一个向量但是现在是在它的方向和e1正交的条件下。同理e3也应该和e1和e2正交等等。因此第m个特征向量em确定了在（n-m 1）维最大平均结对精确度的方向并且与e1到em-1跨度的空间垂直。
我们的准则（4），，近似平均在类对中的平均准确度，因此，我们称之为近似结对精度准则（aPAC）。
3.3广义类内协方差矩阵
在这一节，我们把我们的结论推广到类內协方差矩阵SW不再等于单位矩阵的模型上。
把线性变换运用到最初的统计模型上，我们可以得到一个新的统计模型，其中类内协方差矩阵等于单位矩阵。因此，在这个模型中距离 Delta;ij归结为聚类之间的普通欧式距离。对于一个。类内协方差矩阵等于In来说，我们已经表明了（9）中定义的Jomega;是一个好的LDR准则。现在让Lrsquo;成为一个dtimes;n的而且使得Jomega;最大化的矩阵。这个LDR转换同样可以用于降低原始统计模型的维度：我们简单的用作为LDR变换,例如，原来的特征向量首先通过变换到一个新的统计模型然后再通过Lrsquo;进行降维。
我们现在来展示在初始模型中最大化加权结对准则。反过来，这表明我们可以确定并且直接堆初始模型最大化这个准则而不用明确地把初始模型转换为一个类內协方差矩阵为In的新模型。为了证明前面的陈述,设em是的一个特征向量，是应用后广义的类间协方差矩阵。因此在这个模型中最大化加权结对费舍尔准则的Lrsquo;是由这些特征向量em组成。现在，设lambda;m为em对应的特征值而且注意在2个模型中聚类之间的距离Delta;ij对于每一对（i,j）都相等。综上所述，我们可以写出下面的等
这个等式表明，如果em是 的一个特征向量并且和特征值lambda;m对应，那么就是的一个特征向量并且与同样的lambda;m相对应。反过来说，这表明最大化了加权结对费舍尔准则因为它是由对应d个最大特征值的d个特征向量组成。
我们得出结论，一个形如的LRD变换可以通过最大化（4）中定义的在LDA中的Jomega;直接在初始模型中被找到，而这可以通过一个简单的特征值分解来实现。
图2.a
图2.b
4 实验结果
为了测试通过aPAC方法得到的LDR我们准备了2个实验，一个采用模拟数据一个采用真实数据。也可以看[4]，里面有关于实验更广泛的说明。
在模拟问题中，我们假设已知类方法和相等的类协方差矩阵In。一套30的类方法是由一个协方差矩阵为4In的30维的正态分布推广过来的。假设所有类的先验概率都相等，比如为1/30。通过变换L从初始空间投影的1到29维线性降低的子空间被计算，在其中费舍尔准则和aPAC是最大化的。这些子空间的现行可分性是由一个蒙特卡洛程序估计的。标准的LAD和aPAC的10次
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[153958]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
