CN4321258/TP ISSN10072130X 计算机工程与科学COMPU TER EN GIN EERIN G&SCIENCE2010年第32卷第1期 Vol132,No11,2010 文章编号:10072130X(2010)0120080203局部保持特征变换算法综述3A General Survey of LocalityPreserving Feat ure Transformatio n张笃振ZHANG Du2zhen(徐州师范大学计算机科学与技术学院,江苏徐州221116)(School of Computer Science and T echnology,X uzhou N orm al U niversity,X uzhou221116,China)摘 要:在机器学习研究领域,人们提出了很多特征变换算法。
这些算法的思路是把数据从原始特征空间映射到新的特征空间,从而改善数据的表示或区分能力。
所用技术主要包括特征向量或谱方法、最优化理论、图论等。
算法的步骤都是:(1)构造原始数据及关系的结构;(2)定义目标函数;(3)运用优化理论使目标函数最优,求得问题的解。
本文给出了两类常用的局部保持特征变换主要算法步骤,分析了算法优缺点,这使我们对特征变换的研究有较全面的了解。
Abstract:Many feature transform methods have been proposed for the machine learning research area.They generally try to project the available data f rom the original feature space to a new feature space so that those data are more representa2 tive,or discriminative if they are intended to be assigned with some specific labels.General techniques mainly involve the Eigenvector or Spectral method,the optimization theories(Linear or Convex),the graph theories,and so on.It is generally (1)to construct a structure for the original data and their correlations,(2)to define an objective f unction to evaluate the purpose of the projection or the characteristics of the new space,(3)to apply optimization theories to optimize the objective f unction to get the solution to the problem.This paper gives two classical methods of locality preserving transformation.By analyzing their key points together with their deficiencies,we get a general view of the currently most critical problems.关键词:特征变换;PCA;LL E;L E;ISOMA P;N PE;L PP;LDEK ey w ords:feature transformation;PCA;LL E;L E;ISOMA P;NPE;L PP;LDEdoi:10.3969/j.issn.10072130X.2010.01.024中图分类号:TP391.4文献标识码:A1 引言在高维样本数据聚类等分析中,一般先对原始数据进行预处理,将数据从原始输入空间映射到一个新空间中,这就是特征变换过程,这样可以得到数据的新表示,从而更有利于聚类或分类等后续处理。
本文首先以PCA算法为例简要分析了全局最优线性变换,然后比较详细地分析了两类局部保持特征变换算法,一类是局部保持非线性变换,另一类是局部保持线性变换。
2 全局最优线性变换PCA(Principal Component Analysis,简称PCA)[1]是一种经典的特征提取和降维算法,该算法通过保留主分量使数据从高维空间降低到低维空间。
假设有数据集{x i|i=1,2,3,…,N,x i∈R D}由N 点组成,每个点属于R D特征空间,PCA算法能够把数据映射到新的特征空间R d,这里d小于D,达到了数据降维的目的。
首先,计算数据集的均值:μ=1N∑Ni=1x i(1)接着,计算样本数据的协方差矩阵:S=∑Ni=1(x i-μ)(x i-μ)T(2)最后,通过计算特征向量得到主分量:S w=λw(3)3收稿日期:2008208216;修订日期:2008211216作者简介:张笃振(19672),男,江苏徐州人,硕士,研究方向为图像处理、图像检索和模式识别。
通讯地址:221116江苏省徐州市徐州师范大学计算机科学与技术学院;Tel:(0516)83310163;E2mail:zhduzhen@ Address:School of Computer Science and Technology,Xuzhou Normal University,Xuzhou,Jiangsu221116,P.R.China 把特征值从大到小排序,选取最大的d个特征值对应的特征向量,这d个特征向量构成了d维新特征空间。
PCA和从PCA发展来的CCIPCA(Candid Covariance2 Free Incremental Principal Component Analysis,简称CCIPCA)[2]等都属于这类算法,它们的缺点是:根据全局最优通过变换改变了数据分布,初始特征空间中数据间的关系和相应数据流形通过这种变换后不能得到保持,所以在新空间中肯定会丢失初始特征空间中数据的某些信息,即这种全局最优变换不能保持局部信息。
3 局部保持非线性变换为了解决PCA不能保持局部信息的问题,人们提出一些流形算法,如LL E[3]、L E[4]、ISOMA P[5]。
3.1 LL E算法LL E(Locally Linear Embedding,简称LL E)从局部线性关系中建立全局非线性结构。
算法主要有下面两步:对D维空间中的N个训练样本{X i∈R D,i=1,2,3,…,N}:(1)构造邻接图,假设W ij表示样本的第j分量与样本的第i分量的邻接值,W ij可从最小化式(4)误差代价函数得到:ε(W)=∑i|X i-∑j W ij X j|2(4) 约束条件是∑j W ij=1,使W ij=0,如果X j与X i 不属近邻。
(2)通过最小化式(5)误差代价函数构造局部保持映射:φ(Y)=∑i|Y i-∑j W ij Y j|2(5) 约束条件是:∑i Y i=0,1N∑i Y i Y i=I, 是外积,W ij是第(1)步得到的值,保持不变。
这样就把D维空间中的数据集X映射成了d维空间中的数据集Y。
在第(1)步,LL E算法获得高维空间中数据点间的权值,从而得到高维空间中的局部流形。
第(2)步,保持权值不变,得到数据集在低维空间中的局部线性嵌入新的数据集。
所以,LL E通过保持数据间的局部联系,把数据从原始高维空间映射到低维空间。
从几何结构上看,数据流形不变。
算法的缺陷有三点:(1)对于一个新样本点,没有显式的方法把该点嵌入到低维空间中,这在检索应用中不适用。
(2)新空间的维数没有显式准则进行确定,只有通过经验的方法。
(3)LL E没有利用数据点的类信息。
在分类问题中,对于有类标号的样本数据,LL E无能为力。
3.2 L E算法L E(Laplacian Eigenmaps,简称L E)算法也是基于邻接图模型的,利用局部性思想,获得高维数据所在的低维流形嵌入。
与LL E有相同的缺陷,不同的是,该算法的目标函数要求将高维数据映射到低维空间后,近邻点之间距离尽可能小。
算法步骤如下:对D维空间中的N个训练样本,X={x i∈R D,i= 1,2,3,…,N}:(1)构造有N个顶点的加权图,对顶点i和j,有两种方法可以确定两顶点之间是否存在一条边:①ε邻域法。
如果两个顶点i和j之间的距离小于预定义的阈值ε。
②k近邻法。
顶点i是j的k近邻时。
如果顶点i和j存在一条边,赋予权重W ij=e-‖xi-x j‖2t。
(2)最优化目标函数:最优化下式使得近邻点之间距离尽可能小。
∑ij(y i-y j)W ij(6) 这可以转换为最小化式(7)的优化问题。
Y T L Y(7) 约束条件是:Y T D Y=1,Y T D1=0,这里D ii=∑j W ji,L=D-W。
计算如下特征值问题:L y=λD y(8) 特征值从小到大排序:0=λ0≤λ1≤…≤λd,是d+ 1个最小特征值,f i(i=1,2,…,d)是对应λi的特征向量。
相应的嵌入到d维空间向量为:x i→(f1(i),…,f d(i))(9) 3.3 ISOMAP算法ISOMA P试图在非线性图中建立数据集的结构,这样较好地保持了数据集的局部信息。
算法的主要步骤是:(1)构造邻接图,对所有数据点定义图G,与L E算法一样(ε邻域法、k近邻法)在数据点间建立一条边。
(2)利用最短路径算法(Floyd’s)计算任两点间最短路径,并且把得到的最短路径作为两点之间的权值。
(3)最小化下式的目标函数,建立d维嵌入:E=‖τ(D G)-τ(D Y)‖L2(10)其中,D G={d G(i,j)|d G(i,j)是i和j间的距离},D Y= {d Y(i,j)|d Y(i,j)=‖y i-y j‖};‖A‖L2是L2范数∑i,jA2ij;τ(D)=-HS H/2,S ij=D2ij,H={H ij|H ij =δij-1/N}。
ISOMA P也利用基于图的流形结构,与LL E和L E不同之处在于,它通过最小路径算法把两个点联系起来,从而在点与点之间建立了联系。
第(3)步通过求解最小化目标函数,得出问题的解。
LL E和L E都通过样本数据及关系的非线性描述进行空间变换,保持权值不变使得局部流形不变。
LL E算法将高维数据映射到低维空间后保持近邻数据点之间的线性关系,比较适用于数据表示;L E算法将高维数据映射到低维空间后使近邻数据点尽可能靠近,适用于数据聚类。