第7卷第6期 智能系统学报 Vol.7 No.6 2012年12月 CAAI Transactions on Intelligent Systems Dec.2012 D0I:10.3969/i.issn.16734785.201205025 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20121116.1702.010.html 从Parzen窗核密度估计到 特征提取方法：新的研究视角 刘忠宝12，王士同 (1.江南大学数字媒体学院，江苏无锡214122：2.中北大学电子与计算机科学技术学院，山西太原030051) 摘要：当前主流特征提取方法大致有2种研究思路：1)从高维数据的几何性质出发，根据某种寻优准则得到基于 原始空间特征的一组特征数更少的新特征；2)从降维误差角度出发，保证降维前后数据所呈现的某种偏差达到最 小.试图从降维过程中数据分布特征的变化入手，基于广泛使用的Parzen窗核密度估计方法，来审视和揭示Parzen 窗估计与典型特征提取方法LPP、LDA和PCA之间的关系，从而说明这些特征提取方法可统一在Parzen窗框架下进 行研究，为特征提取方法的研究提供了一个新的视角. 关键词：特征提取；Parzen窗；密度估计；数据分布特征；新视角 中图分类号：TP392文献标志码：A文章编号：16734785(2012)060471-10 From Parzen window estimation to feature extraction:a new perspective LIU Zhongbao2,WANG Shitong' (1.School of Digital Media,Jiangnan University,Wuxi 214122,China;2.School of Electronics and Computer Science Technology, North University of China,Taiyuan 030051,China) Abstract:Researches on current feature extraction methods are mainly based on two ways.One originates from geo- metric properties of high-dimensional datasets and attempt to extract fewer features from the original data space ac- cording to a certain criterion.The other originates from dimension reduction deviation and try to make the deviation between data before and after dimension reduction be as small as possible.However,there exists almost no study a- bout them from the perspective of the scatter change of a dataset.Based on Parzen window density estimator,we thoroughly revisit the relevant feature extraction methods from a new perspective and the relationships between Parzen window and classical feature extraction methods,ie length of perpendiculars(LPP),linear discriminant analysis (LDA) and principal component analysis(PCA)are built in this paper.Therefore,these feature extraction methods can be re- searched in the same Parzen window,which provides a new perspective for the research of feature extraction. Keywords:feature extraction;Parzen window;density estimation;data distribution characteristics;new perspec- tive 在实际应用中常常遇到高维数据，如多媒体数 过将原始特征空间低秩近似，保证降维后的特征非 据、文本数据、生物数据等.尽管高维数据比低维数 负；主成分分析(principal component analysis, 据拥有更多的信息量，但在实际操作中非常不便.一 PCA)[21通过对原始特征空间方差的研究得到一组 种有效的解决方法就是对其进行特征提取.所谓特 正交的主成分；奇异值分解(singular value decompo- 征提取是指原始特征空间根据某种准则变换得到低 iion,SVD)[3]通过考察奇异值的贡献率实现降维； 维投影空间的过程.近年来，研究人员提出众多特征 独立成分分析(independent component analysis, 提取方法(feature extraction methods,FEM):非负矩 ICA)[4同时利用原始特征空间的二阶和高阶统计 阵分解(non-negative matrix factorization,NMF)l通 信息，进一步提高了PCA的降维效率；线性判别分 析((linear discriminant analysis,LDA)[5通过最大化 收稿日期：201205-14.网络出版日期：2012-11-16. 类间离散度和类内离散度的广义Rayleigh熵实现特 基金项目：国家自然科学基金资助项目(61170122,61272210). 通信作者：刘忠宝.E-mail:liu_zhongbao@hotmail.com. 征变换；多维缩放（multi-dimensional scaling
.472 智能系统学报 第7卷 MDS)[6通过保持数据点间的相似性实现降维；局 a≥0，i=1,2,…,W 部线性嵌入(locally linear embedding,LLE)[利用 式中：K(x,x:)为窗宽为8的核函数，a:(i=1,2, 稀疏矩阵算法实现降维；拉普拉斯特征映射(Lapla- …,N)为系数.其中，核函数K必须满足： cian eigenmap)[8]利用谱技术实现降维；典型相关分 1)K(t)≥0； 析(canonical correlation analysis,CCA)9]利用综合 变量对之间的关系来反映2组指标之间的整体相关 2)K,(t)dt=1. 性；局部保持投影(locally preserving projections,. 常用的核函数有： LPP)[10通过保持原始特征空间内在的局部几何结 1)Gaussian核函数K(x,y)=exp(-‖x 构实现降维， y‖2/282)，参数6>0. 在实际应用中，针对不同的应用场合，本课题组 2)多项式核函数K(x,y)=(x'y+c),c和d 提出若干改进算法：皋军等I利用Fisher准则中的 为参数.当c=1且d=0时，K(x,y)=x「y.此时多项 类内散度重新构造势支撑向量机的目标函数，提出 式核为线性核 广义势支撑特征选择方法(generalized potential sup- 3)Sigmoid核函数.K(x,y)）=tanh(b(ry)+c), port features selection method,GPSFM),该方法具有 b(xy)>0,且c<0. 冗余度低、选择速度快等优点；王晓明等2]针对监 督的局部保持投影算法在小样本情况下矩阵的奇异 4)Epancbnikov核函数K(x）=名(1- 性问题，提出广义的局部保留投影算法(generalized su- pervised locality preserving projection,GSLPP),该方法 ),1xl≤1，d为参数。 2 有效地解决了小样本问题；王超等)提出有局部保持 Sigmoid核函数在特定参数下与Gaussian核函 的最大间距准则特征提取方法，该方法能使投影后的 数具有近似性能；多项式核函数参数较多，不易确 样本具有最大类间散度和最小类内散度，在解决小样 定，且当阶数d较高时运算可能出现溢出.因此本文 本问题的同时更好地保持人脸图像的局部流形结构. 重点关注Gaussian核函数和Epanechnikov核函数， 上述特征降维方法主要从空间几何和降维误差 它们均为最小均方差意义下的最优核函数.通过合 角度进行研究.从空间几何角度看，特征提取实质上 理的参数选择，它们可用于任意分布的数据 是根据一定规则最优化缩小特征空间的过程；从降 维误差角度看，特征提取的目的是保证降维前后数 2 Parzen窗与LPP 据的偏差尽可能小.目前大多数特征提取方法重点 大多数特征提取方法主要从空间几何和降维误 关注几何性质和降维误差，而对于降维过程中数据 差角度进行研究，而对于降维过程中数据分布特征 分布特征的变化往往重视不够.鉴于此，本文引入 的变化则关注不够.本文从降维过程中数据分布特 Parzen窗核密度估计表征数据的分布特征，通过分 征的变化入手，基于广泛使用的Parzen窗核密度估 析降维过程中数据分布特征的变化，揭示Parzen窗 计方法，通过探讨Parzen窗估计与典型特征提取方 估计与典型特征提取方法LPP、LDA和PCA之间的 法LPP、LDA和PCA之间的关系，进而说明这些特 关系，从而说明这些特征提取方法可统一在Parzen 征提取方法可统一在Parzen窗框架下进行研究.本 窗框架下进行研究，为特征提取方法的研究提供了 节首先讨论Parzen窗与LPP之间的关系 一个新的视角 设有样本X=[x12…xw]ER"xW,其中 1 Parzen窗 x(i=1,2,…,N)eRw表示第i个样本，N表示样 本总数 在统计学和其他相关领域，核密度估计备受关 2.1 LPP 注.Parzen、Silverman、.Rosenble等是当前主流的核密 度估计方法4.Parzen窗法具有优良性能5，因而被 LPP16在保持样本局部流形结构不变的基础上 广泛使用.本文采用Parzen窗表征数据的分布形状. 实现特征提取，即在高维空间的邻近样本点在低维 Parzen窗定义为 空间的相对关系保持不变.算法流程如下： 1)创建邻接图.如果样本点x:和￡满足 p(x)=∑aK(x,x)， ‖x-x‖2<e,则将两点相连； 2)计算权值.权值计算公式为 8.t. ,a=1, S=exp(-‖x-x‖2/e)
第6期 刘忠宝，等：从Parzen窗核密度估计到特征提取方法：新的研究视角 ·473· 3)求解投影矩阵W.W可通过最小化如下目标 函数得到： 降维过程中散度的变化速度用需表示。对 m∑(Wx-w)2s 式(1)求导可得 对上式进行代数变换有 、1 1 6=NV2m exp(-‖lx- 1∑(wx:-Wx,)Sg= 2行 xyI2/28)(1x:-xg12/-1). (2) 于xD,W-于wSW 针对某类数据降维，6已知.为了表示方便，将 N表示为N,6表示为6，去掉式(2)中常数项有 WX(D-S)XW WXLXW. 式中：D为对角阵，且Da=Sg,L=D-S 器-启-am(-I-p 约束条件为 (3) WXDXW=1. 令式(3)中x∈{训练样本}，则式(3)变为 上述优化问题可转化为求解如下广义特征值 问题： 器-盒em(--P) XLXW AXDXW. (4) 式中：前d个最小非零特征值对应的特征向量构成 为了使降维后的数据尽量保持原始空间的分布 的投影矩阵W=[0102·0a] 2.2 Parzen窗与LPP的关系 特征，因此投影方向W应满足散度的变化速度弧 06 从概率密度角度看，特征提取过程可以看作是 最小，可得目标函数： 数据分布特征保持的过程.用Parzen窗表征数据的 min IWTWI. (5) 分布特征并保证降维前后数据分布尽量保持一致. Parzen窗可定义为 式中：T=启1-与cm(wr(--与/ ,()=N合五2mex 1 。exp(-‖x-gI2/28). 282)W),I=[11…1].向量1保证式(4)投 影后仍为标量.由于exp(-‖x:-x‖2/282)可以 (1) 反映样本点x:和x之间关系，因此为了计算方便， 式中：方差6，表明各类样本偏离其类中心的程度， 式(5)中T可简化为 方差6，也称为散度.在降维过程中，方差6，的变化 速度越小，则数据的分布特征变化越小.若数据服从 T=x:2exp(W(-Ilx 22)W). 1 高斯分布，图1中的G1和G2表明降维前后数据分 式(5)可转化为 布的变化情况.降维后的数据在一定程度上进行了 min I'W'TWL. (6) 缩减，因此散度有变小的趋势 由于1与W无关，因此式(6)可表示为 G min W'X'LXW. -G. 式中：S,=em(-1出-128)，D.=2,1 D-S. D反映样本点x:附近的局部密度.D越大，则 x:局部密度越大.因此对其约束有 WXDXW =1. 基于上述分析，上述最优化问题可归纳为 min W'X'LXW, s.t.W'X DXW =1. (7) 图1降维前后数据分布变化 为了表述方便，将上述优化问题称为基于 Fig.1 The transformation of data distribution before Parzen窗的特征提取方法(feature extraction method and after dimension reduction based on Parzen window,FEMPW)
474 智能系统学报 第7卷 由LPP算法不难看出：当样本点x:和x满足 N- ‖x:-x‖2<e时，将2点相连并计算相应权重.当 类的样本均值为(i=1,2,…,c),则有x=N x∈{训练样本}时，令LPP的权重函数为 LDA的最优化表达式为 s=exp(-1x-2)/28). WSeW J(W)=max (11) √/2T8 w WSW 且满足 由拉格朗日乘子法可得：求解式(11)等价于求 上含盒 解一般矩阵SSg的特征值问题. -exp(-lx2)dx =1. 3.1.2最小误差解释 (8) 以二分类问题为例，从最小误差角度解释 式中：C为常数， LDA. 求解式(8)可得 1)用Bhattacharyya系数确定二分类问题的错 C=1/N(2Φ（ε）-1). 误率上界。 式中：a)=∫2n(-r2 由文献[18]可知，为了使二分类问题错误率上 界尽可能小，必须保证Bhattacharyya系数尽可能 对于任意给定的ε值，通过查表可求得④(e), 大.用JB表示Bhattacharyya系数，有 进而得到C值.当B→∞时，C=1/N,此时FEMPW Jn =-Inp(xI 0)p(1 @2)dx. 等价于LPP.也就是说，LPP是FEMPW的特例. 假设2类样本服从正态分布：xly=0~N(1, 3 Parzen窗与LDA和PCA 1),xly=1~N(u2,2)则有 LDAS)和PCA]是特征提取中最为经典和广 g:-,3含)-a,+ 泛使用的方法.针对于LDA和PCA,科学家们进行 了广泛研究并取得了众多成果.与已有研究思路不 1(+2)/2 (12) 同，本文主要贡献在于：1)出发点不同，目前已有研 究主要从空间几何和最小误差角度展开，而本文从 当1=2=Σ时，式(12)可转化为 降维过程中数据分布特征的变化入手对其进行探 。=g:-u)2:u月 讨；2)解释模型不同，目前已有研究主要基于空间 几何和最小误差2种解释模型，而本文通过Parzen 特别地，当=E时， 窗建立概率密度估计与LDA和PCA的关系，从概 h=g-4:-a, 率密度角度对其进行解释. 2)样本的最大似然估计. 3.1 LDA 最大似然估计函数可表示为 3.1.1几何解释 从几何角度看，LDA的目的是将高维特征降到 L(中12，∑)= 低维空间，保证在低维空间异类样本尽量分开，同类 logp(x中142，∑)= 样本尽量紧密： = 样本的类间离散度矩阵和类内离散度矩阵分别 l1ogp(x1w12,∑)p), 定义为 求导并令导数为零可得 SB=∑N,(E-E)(x-)T, (9) ∑=∑(x-u)(x:-4)1+ S,=合(5-0(5，-)(10) ∑(x:-2)(x-) 式中：xg∈R(i=1,2,…,c=1,2,…,N)表示第i 类中的第j个样本，N:表示第i类样本个数，c表示 式中：Σ是样本特征方差均值， 样本类别总数所有样本的均值一含：设第： 为了使错误率的上界和样本散度尽可能小，投 影方向W应满足
第6期 刘忠宝，等：从Parzen窗核密度估计到特征提取方法：新的研究视角 ·475· WSW J(W)=m阳xwSW 21x-x2 N- 式中： 82 ≤1- SB=(u2-1)(2-u1)T, 可得 S=(-u)(x-u4)r+ ∑NIE-x:I2 台 Ps(x)≤1- (16) 82 ∑(x:-w2)(x-42)月 为了表示方便，取式(16)的上界并求导可得 上述最优化问题可转化为求解S需S:的特征值 问题.同理，对于c(c>2)类问题，类间离散度矩阵 需=后-，=12 和类内离散度矩阵的定义分别同式(9)和式(10). 为了使降维后的各类样本尽可能隔开，因此投 3.2 Parzen窗与LDA的关系 本节从概率密度角度讨论Parzen窗与LDA的 影方向W应满足使得各类需最大去掉与6有关 关系.Epanechnikov核函数[9是在最小均方差意义 的常数项，则有 下最优的核函数之一.受Epanechnikov核函数的启 max IW'S,WL. (17) 发，采用如下核函数进行密度估计： 式中：Sa=含Nx-I 2x)=1-合*-出2合x-41 由于式(17)中1与W无关，则有 ≤1. 8 6 max WiSeW, (18 (13) 综合式(15)和式(18)可得 为了计算散度的变化速度，对式(13)求导可得 W SeW 器=最1-，=12… J(W)=max ws.W 3.3 PCA 针对某类数据降维，则8已知.当x∈{训练样 3.3.1几何解释 1 本时，则=N,i=12,…6. 从几何角度看，PCA通过计算方差来衡量样本 包含信息量的大小.PCA称方差较大的分量为主成 为了保证降维前后数据分布的稳定性，因此投 分，主成分反映了原始变量的主要信息， 影方向W应满足使得职最小.去掉与ò有关的常 设投影方向为W,为了使投影后样本的总体离 08 散度最大，由方差的定义可得 数项，则有 1 ∑(x-)W)2= min Iw∑‖xg-x2wm. (14) J(w)=mxN 式中：向量1保证式(14)为标量.式(14)中1与W x1之w(x:-(x-E)W= mgxN 无关，并综合考虑各类样本，可得 min W'S,W. (15) gm(哈含红--用w 式中，=名- 令S=名（出-）x-到，则上式变为 下面求类间离散度矩阵Sg,对式(13)进行如下 J(W)=maxW'S,W. 数学变换： W可通过求解如下特征值问题得到： c Ni S,W =AW. Ps(x)=1-台台 82 3.3.2最小误差解释 设样本点：降维后变为x',希望降维后的样 ∑INe-xI2 1、 本点与原样本点之间的误差尽可能小，则引入最小 8 平方误差：