英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
局部保持投影
摘要
信息处理中的许多问题都涉及到某种形式的降维。在这篇论文中，我们介绍局部保持投影（LPP）。这些都是通过解决一个变分问题，从而最优地保留了数据集的邻域结构的线性投影图。LPP应该被看作是主成分分析（PCA）的替代。(PCA：一种经典的线性技术，它根据最大方差的方向投影数据) 当高维数据嵌入环绕空间内的低维流形时，通过对流形上的拉普拉斯-贝尔特米算子的特征函数求出最优线性逼近，得到局部保持投影。因此，LPP具有许多诸如拉普拉斯特征映射、局部线性嵌入等非线性技术的数据表示特性。然而LPP是线性的，更重要的是定义在整个环绕空间，而不仅仅在训练数据点上。这是通过一些高维数据集的例子来证明的。
1.引言
假设我们有一个从未知概率分布中提取的n维实向量的数据点集合。在越来越多的对机器学习和数据挖掘的案例中，往往面临的情况是特征维数n非常大。然而，可能有理由怀疑数据的“内在维度”要低得多。这使得人们考虑在更低维度空间中表示数据的降维方法。
本文提出了一种新的线性降维算法，称为局域保持投影(LPP)。它构建了一个包含数据集的邻域信息图。利用图中拉普拉斯算子的概念，我们计算出一个映射数据点到子空间的变换矩阵。这种线性变换在一定意义上最优地保留了局部邻域信息。由这个算法生成的表示图可以看作是一个连续映射的线性离散逼近，它自然地来自于流形的几何结构[2]。从众多角度来看，这个新算法很有趣。
1.经典的线性技术都是通过最小化不同的目标函数准则，从而得到映射方向。
2.在信息检索应用中，LPP的局部保持特性很可能具有特殊的应用。如果希望在向量空间模型下检索音频、视频和文本文档，那么最终需要在低维空间中进行最近的邻域搜索。由于LPP是被设计来保护局部结构，所以在低维空间中最近的邻域搜索可能会和在高维空间中搜索的结果类似。这使得索引方案能够快速检索。
3.LPP是线性的。这使它快速并且适用于实际应用。虽然许多非线性技术具有上面的属性(1)和(2)，但是其他线性投射技术都不具有这样的性质。
4.LPP可定义在任何地方。ISOMAP[6]、LLE[5]、拉普拉斯特征图[2]等非线性降维技术只在训练数据点上定义，并且如何评价新测试点的图是不清楚的。与此相反，在降维空间中，局部保持投影可以简单地应用到任何新的数据点并能定位它。
5.LPP可以在原始空间或再生核希尔伯特空间(RKHS)中映射数据点。这就产生了内核LPP。
由于所有这些特性，我们期望基于LPP的技术在探索性数据分析、信息检索和模式分类应用程序中可以代替基于PCA的技术。
2．局部保持投影
2.1线性降维问题
线性降维的一般问题如下。给定中的一个集合，找到一个变换矩阵A，该变换矩阵A可以将这些m个点映射到(l《n)中的，这样“对应”,其中 = 。在isin;M且M是一个嵌入的非线性流形的情况下，我们的方法具有特定适用性。
2.2算法
局部保持投影(LPP)是对非线性拉普拉斯特征图的线性逼近[2]。算法过程正式表述如下:
1.构造邻接图:令G表示一个有m个节点的图。如果和“相近”，那么我们在节点i和j之间设置了一条边线。有两种变化:
（a）ε邻域。[参数ε] isin;R]如果这里的范数是Rn空间的常见的欧几里得范数，那么节点i和j由一条边连接。
（b）k最近邻域。[变量kisin;N] 如果节点i是节点j的k近邻点或节点j是节点i的k近邻点，那么节点i和j由一条边连接。
注意：如果数据实际上位于一个低维流形上，那么构造上述邻接图的方法是正确的。然而，一般来说，往往可能会采取更功利的观点，并基于某个原则来构建一个邻接图(例如，对自然信号的感知相似性，网络文档的超链接结构等)。一旦获得了这样的邻接图，LPP将试图在选择投影时最佳地保存它。
2.选择权重。我们有两种不同的加权方法。W是一个mtimes;m的稀疏对称矩阵, 如果顶点i和j有边连接,就赋予权重值；如果没有边连接，权重值就是0。
（a）热核。[变量tisin;R] 如果节点i和j有边连接，
这种权值选择的理由可以追溯到[2]
（b）简化思想。[没有变量]当且仅当顶点i和j有边连接时。
3.特征映射。计算广义特征向量问题的特征向量和特征值，= (1)其中D是一个对角矩阵，它的元素是W的列和(或行,因为W是对称的)。。L=Dminus;W是拉普拉斯矩阵。矩阵X的第i列是。
令列向量为方程(1)的解,根据他们的特征值,lt;..lt;。因此，嵌入如下。
→=,A=
其中y是一个l维的向量，A是一个n*l的矩阵。
3论证
3.1最优线性嵌入
下面的部分是基于标准谱图理论。综合参考可以参阅文献[4]，想要了解应用程序的数据表示请参阅[2]。
给定一个数据集，我们构造一个加权图G=(V,E)，其中的边与相邻的点相连。将加权图G映射到一条直线上以便连接的点尽可能保持紧密。令y=为这样一幅图。选择“好”图的合理标准是在适当的约束下将下列目标函数最小化[2]。
如果相邻的点和被映射得很远，那么我们选择的目标函数就会出现严重的问题。因此，将它最小化是试图来确保和是“相近的”并且和也是相近的。
假设a是一个转换向量，即，其中X的第i个列向量是。通过简单的代数公式，可以将目标函数简化为
其中X =[，，hellip;，]，D是一个对角矩阵;它的元素是W的列和(或行,因为W是对称的), =。L=Dminus;W是拉普拉斯矩阵[4]。矩阵D为数据点提供了一种自然的测量方法。(对应于)值越大，越“重要”。因此，我们施加一个约束如下:
最后，最小化问题简化为：
将目标函数最小化的转换向量a通过对广义特征值问题的最小特征值解出:
=
显然，矩阵和是对称的、正半定的。将目标函数最小化的向量(i=0，2，hellip;，lminus;1)是通过对广义特征值问题的最小特征解给出的。
3.2几何证明
拉普拉斯矩阵L (=D -W)用于有限图,或[4], 在紧凑的黎曼流形上类似于拉普拉斯-贝尔特拉米算子L。然而一个流形的拉普拉斯-贝尔特拉米算子是由黎曼度量生成的，对于一个图，它来自于邻接关系。
令M为一个光滑、紧凑、d维的黎曼流形。如果在中嵌入了流形，那么流形上的黎曼结构是由上的标准黎曼结构导出的。寻找一个从流形到实线的映射，这样在流形上的点就会相交于直线上。令f为这样的一个图。假设f:M→R是两次可微的。
Belkin和Niyogi[2]表明，通过解决流形上的以下优化问题，可以找到最优的映射保存位置:
等价于：
积分是在黎曼流形上的标准度量。L是流形上的拉普拉斯-贝尔特拉米算子，即Lf=minus;divnabla;(f)。因此,最优的f是L的特征函数。积分在图上可以由{f(X),Lf(X)} = (X)Lf(X) 离散近似，其中
如果我们将映射限制为线性，即f(x)=x，则有
约束可计算如下：
其中dx是黎曼流形的标准度量。通过光谱图理论[4]，dx直接对应于图的度量，即顶点的度数，即。因此，可以离散近似如下
最后，我们得出最优线性投影图，即f(x)=x，可以通过求解以下目标函数得出，
这些投影图是对流形上拉普拉斯-贝尔特拉米算子特征函数的最优线性逼近。因此，它们能够发现非线性流形结构。
3.3内核LPP
假设欧几里得空间通过一个非线性映射函数phi;:Rn→H映射到希尔伯特空间H。令phi;(X)表示在希尔伯特空间里的数据矩阵，phi;(X)=[phi;()，phi;()，hellip;，phi;()]。现在，希尔伯特空间的特征向量问题可以写成:
LPP推广到非线性情况下,我们用点积的方式来表示它。因此，我们考虑在希尔伯特空间上通过下面的内核函数给出点积的表达：
因为(2)的特征向量是phi;()，phi;()，hellip;，phi;()的线性组合，存在系数alpha;i， i=1,2,hellip; ,m,使得
通过简单的代数公式，我们可以得到以下特征向量问题。
（3）
令列向量alpha;1，alpha;2，hellip;hellip;，alpha;m为方程（3）的解。对于一个测试点x,我们计算出在特征向量nu;k上的投影，
式中是向量中的第i个元素。对于原始的训练点，图可以由y=Kalpha;获得，其中y中的第i个元素是中的一维表示。此外，方程式（3）可以简化为
Ly= lambda;Dy （4）
这与拉普拉斯特征图的特征值问题相同[2]. 这表明内核LPP在训练点上产生的结果与拉普拉斯特征图相同。
4.实验结果
在本节中,我们将讨论LPP算法的几个应用。我们首先两个简单合成的例子来解释LPP是如何工作的。
4.1 简单合成的例子
图1给出了两个简单合成的例子。这两个数据集本质上对应于一个一维流形。将数据点投影到第一个基底上将会对应一维线性流形表示。在图中显示为短线段的第二个基底，在这个低维的例子中会被舍弃。
图像1：第一个和第三个图显示了PCA的结果。第二个和第四个图显示了LPP的结果。线段描述了两个基底。第一个基底显示为较长的线段，第二个基底显示为较短的线段。在这个例子中，LPP对异常值不敏感，但是比PCA具有更强的识别能力。
图像2：手写数字(#39;0#39;-#39;9#39;)被映射到二维空间。左边的图形是使用拉普拉斯特征图的所有数字图像集合的表示。中间图显示了LPP的结果。右图显示了PCA的结果。每个颜色对应一个数字。
LPP是通过保存局部信息而得到的，因此它对异常值的敏感程度要小于PCA。从图1清楚表明了这一特性。LPP在左下角的数据点上找到了主方向，而PCA找到的主方向则是在这个方向上数据点在左下角的位置坍塌为一个点。此外，LPP比PCA具有更强的识别能力。从图1可以看出，在PCA获得的主方向上，两个圆是完全重叠的，而在LPP得到的主方向上它们是完全分离的。
4.2二维数据可视化
对多特征数据库[3]进行了实验。手写数字(`0`-`9`)的特征数据集是从荷兰实用地图中提取的。每个类(总共2000个模式)的200个模式已经被二进制图像数字化了。数字用傅立叶系数、轮廓相关性、Karhunen-Love系数、像素平均值、泽尼克矩和形态学特征来表示。每个图像由一个649维的向量表示。使用PCA、LPP和拉普拉斯特征图等不同的降维算法，将这些数据点映射到二维空间。实验结果如图2所示。可以看出，LPP的性能比PCA好得多。LPPs是通过在流形上对拉普拉斯-贝尔特拉米算子特征函数进行最优线性逼近得到的。因此，LPP拥有许多诸如拉普拉斯特征图等非线性技术所没有的数据表示特性。但是，LPP在计算上更容易处理。
4.3面部图像流形
在本小节中，我们将LPP应用于人脸图像。这里使用的人脸图像数据集与[5]中使用的图像数据集相同。这个数据集包含从一个小视频里连续帧截取的1965张照片。每个图像的大小是20times;28，每像素256灰色阶层。因此，每个人脸图像都是由560维环绕空间中的一个点来表示的。图3显示了映射结果。人脸的图像被映射到二维平面上，由局部保持投影的前两个坐标描述。应该强调的是，用我们的方法所得到的从图像空间到低维空间的映射是线性的，而不是像之前那样是非线性的。线性算法在一定程度上检测了人脸图像的非线性流形结构。在空间的不同部分的数据点旁边显示了一些具有代表性的面孔。可以看出，人脸的图像清晰地分为两部分。左边是嘴巴紧闭，右边是嘴巴张开。这是因为，通过试图在嵌入中保护邻域结构，LPP算法隐含地强调了数据中的自然群集。具体地说，它使得环绕空间的相邻点比降维表示空间的更接近，而在环绕空间中的远点比在降维表示空间中的更远。底部的图像对应于沿着正确路径的点(由实线连接)，说明了一个特定的姿势变化模式。
图像3：用局部保持投影的所有人脸图像集合的二维表示。在空间不同部分的数据点旁边显示有代表性的面孔。可以看出，面部表情和观看点的变化很平稳。
4.4人脸识别
PCA和LDA是人脸识别中最广泛使用的子空间学习技术[1][7]。这些方法将训练样本面向低维度的表示空间进行识别。这一过程的主要假设是人脸空间(由特征向量给出)比图像空间(由图像中像素的数目)的维度更低，并且可以在这个降维的空间中进行人脸的识别。在本小节中，我们考虑了LPP在人脸识别中的应用。
这个实验使用的数据库源自耶鲁的面部数据库[8]。它是在耶鲁大学计算视觉和控制中心建造的。它包含了15个人的165个灰度图像。这些图片在不同的光照条件(左灯、中心灯、右灯)、面部表情(正常、快乐、悲伤、困倦、惊讶和眨眼) 、戴不戴眼镜等条件下各不相同。应用预处理来定位人脸。原始图像(在尺度和方向上)被标准化，这样两个眼睛在同一位置上对齐。然后，将面部区域裁剪成最终匹配的图像。每个裁剪图像的大小是32times;32像素,每像素256灰度阶层。因此，每个图像都可以用一个1024维的向量表示。
对于每一个个体，将6张带有标签的图像组成训练集，其余的数据库被认为是测试集。训练样本用于学习投影。然
全文共6128字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[12463]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
