模式识别特征选择与提取

中国矿业大学计算机科学与技术学院电子信息科学系班级：信科11-1班，学号：08113545，姓名：褚钰博联系方法（QQ 或手机）：390345438，e-mail:[email protected]

日期：2014 年 06月 10日

摘要

实际问题中常常需要维数约简，如人脸识别、图像检索等。而特征选择和特征提取是两种最常用的维数约简方法。特征选择是从某些事物中提取出本质性的功能、应用、优势等，而特征提取是对特征空间进行变换，将原始特征空间映射到低维空间中。本文是对主成分分析和线性判别分析。

关键词：特征选择，特征提取，主成分分析，线性判别分析

1. 引言

模式识别的主要任务是利用从样本中提取的特征，并将样本划分为相应的模式类别，获得好的分类性能。而分类方法与分类器设计，都是在d （变量统一用斜体）维特征空间已经确定的前提下进行的。因此讨论的分类器设计问题是一个选择什么准则、使用什么方法, 将已确定的d 维特征空间划分成决策域的问题。对分类器设计方法的研究固然重要，但如何确定合适的特征空间是设计模式识别系统另一个十分重要，甚至更为关键的问题。如果所选用的特征空间能使同类物体分布具有紧致性，即各类样本能分布在该特征空间中彼此分割开的区域内，这就为分类器设计成功提供良好的基础。反之，如果不同类别的样本在该特征空间中混杂在一起，再好的设计方法也无法提高分类器的准确性。本文要讨论的问题就是特征空间如何设计的问题。

基于主成分分析的特征选择算法的思想是建立在这样的基础上的：主成分分析方法将原始特征通过线性变换映射到新的低维空间时，获得的主成分是去了新的物理意义，难以理解，并且主成分是所有原始特征的线性组合。所以将主成分分析与特征选择相结合，设计多种相似性度量准则，通过找到与主成分相关的关键特征或者删除冗余、不相关以及没有意义的特征，将主成分又重新映射到原始空间，来理解成主成分的实际意义。

基于线性判别分析的高维特征选择将单个特征的Fisher 准则与其他特征选择算法相结合，分层消除不相关特征与冗余特征。不相关特征滤波器按照每个特征的Fisher 评价值进行特征排序，来去除噪音和不相关特征。通过对高维数据特征关联性的分析，冗余特征滤波器选用冗余度量方法和基于相关性的快速过滤器算法。分别在不同情境下进行数据分类实验，验证其性能。

2. 原理分析

对一原始特征来说，特征选择的方案很多，从N 维特征种选择出M 个特征共有

M C N =

N !

中选法，其中哪一种方案最佳，则需要有一个原则来进行指导。

M ! N -M !

我们进行特征选择和特征提取的最终目的还是要进行识别，因此应该是以对识别最有利原则，这样的原则我们称为是类别的可分性判据。用这样的可分性判据可以度量当前特征维数下类别样本的可分性。可分性越大，对识别越有利，可分性越小，对识别越不利。

人们对的特征的可分性判据研究很多下面几种常用的判据，我们需要根据实际问题，从中选择出一种。

一般来说，我们希望可分性判据满足以下几个条件：

1. 与识别的错误率由直接的联系，当判据取最大值时，识别的错误率最小； 2. 当特征独立时有可加性，即：

J ij (x 1, x 2, , x N ) =∑J ij (x K )

K =1

J ij 是第i 类和第j 类的可分性判据，J ij 越大，两类的可分程度越大，(x 1, x 2,

特征；

3. 应具有某种距离的特点：

, x N )为N 维

J ij >0，当i ≠j 时； J ij =0，当i =j 时；

J ij =J ji ；

4. 单调性，加入新的特征后，判据不减小：

J ij (x 1, x 2, , x N )≤J ij (x 1, x 2, , x N , x N +1)。

但是遗憾的是现在所经常使用的各种判据很难满足上述全部条件，只能满足一个或几个条件。特征提取又称为特征变换，最常采用的特征变换是线性变换，即若x ∈R 是D 维原始特征，变换后的d 维新特征y ∈R 为y =W x ，其中，W 是D ⨯d 维矩阵，称作变换阵。特征提取就是根据训练样本求适当的W ，使得某种特征变换准则最优。

主成分分析方法的出发点是从一组特征中计算出一组按重要性从大到小排序的新特征，他们是原有特征的线性组合，并且相互之间是不相关的。

记x 1, x 2, , x p 为p 个原始特征，设新特征ξ，i=1, ，p 是这些原始特征的线性组合

ξi =∑αij x j =αi T x ，

j =1

为了统一ξi 的尺度，要求线性组合的模为1，即

αi T αi =1，

写成矩阵形式是

ξ=A T x ，

其中，ξ是由新特征ξi 组成的向量，A 是特征变换矩阵。要求解的是最优的正交变换A ，它使新特征ξi 的方差达到极值。

3. 理论证明或说明

特征选择的基本框图为:

一个典型的特征选择算法通常包括四个人基本步骤:

1. 子集产生，这是一个搜索过程，通过一定的搜索策略产生候选的特征子集。

2. 子集评价，每一个候选的特征子集都根据一定的评价准则得到，并与先前的最优特征子集进行比较。 3. 终止条件，算法结束所需要满足的条件，它与子集的产生过程和评价准则的选用有关。

4. 结果验证，就是根据一定的先验知识或通过合成现实数据集的测试来证明所选择的特征子集的性能。

基于特征提取主成分分析变换矩阵的一般过程：

训练数据全集

4. 实现方法或步骤流程

特征选择顺序前进法

每次从未入选的特征中选择一个特征，使得它与已入选的特征组合到一起所得到的可分性判据最大，直到特征数增加到M 为止。用X k 表示在第k 步时的特征集合，搜索算法如下：

1) 开始时，X 0=∅，从N 个特征中选择一个J (x i )最大的特征，加入已选特征集，X 1={x i }； 2) 在第k 步，X k 中包含已经选择的k 个特征，对未入选的N -k 个特征计算，J X k

其中j =1, 2,

({x })，

, N -k ，并且按照由大到小排序，将可分性判据最大的特征x l 加入X k ，

X k +1=X k

{x l }；

3) 直到所选的特征数等于M 为止。

特征抽取的方法—基于离散K-L 变换(DKLT)的特征抽取：设原始特征为N 为矢量X =(x 1, x 2,

, x N )，均值矢量m =E [X ]，相关矩阵R X =E ⎡⎣XX ⎤⎦，

协方差矩阵C X =E ⎡(X -m )(X -m )⎤。

⎣⎦

我们可以对X 作如下的标准正交变换，将其变为矢量Y =(y 1, y 2, , y N ):

⎡T 1T ⎤⎢T ⎥T

Y =T T X =⎢2⎥X

⎢⎥⎢T ⎥⎢T N ⎦⎥⎣

Y 的每个分量：y i =T i T X ，其中T 为一个N ⨯N 的标准正交矩阵，T i 为其第i 个列矢量，

⎧1, i =j

。也就是说Y 的每个分量是X 每一个分量的线性组合。 T i T T j =⎨

⎩0, i ≠j

同样X 可以表示为：

X =(T T )Y =TY =(T 1T 2

-1

⎡y 1⎤⎢y ⎥N

T N )⎢2⎥=∑y i T i

⎢⎥i =1⎢⎥⎢y N ⎦⎥⎣

我们要进行特征提取，也就是要用Y 的M 项来代替X ，这种代替必然带来误差，下面我们来对这

个误差进行估计：

ˆ=∑y T ，1≤M

i =1

e (M )=E ⎡X -X

⎢⎣

()(

⎤⎡⎤X -X ⎤=∑E ⎡y =E y y ∑i i i ⎦ ⎥⎦i =M +1⎣⎦i =M +1⎣N

)

N N

i =M +1

∑T E ⎡⎣XX

⎤⎦T i =

i =M +1

∑T R

X i

这又变成一个优化问题，我们希望寻找到一个标准正交矩阵T ，使得e 样的准则函数：

(M )最小，因此可以去这

J =

i =M +1

∑T R

T i

T i -

i =M +1

∑λ(T T -1)

T i

第一项保证均方误差最小，第二项保证T 为标准正交矩阵，λi 为一待定常数。

∂J

=(R X -λi I )T i =0，i =M +1, ∂T i

, N

即：R X T i =λi T i ，很明显λi 为相关矩阵R X 的特征值，T i 为对应于λi 的特征矢量，由于R X 是一个实对称矩阵，所以T 1, T 2,

. T N 相互正交，T 为一个正交矩阵。均方无差：

e (M )=

i =M +1

∑T R

T i

T i =

i =M +1

∑T λT =∑λ

T i

i i

i =M +1

N N

根据矩阵论，有这样的结论：一个N ⨯N 的正定实对称矩阵有N 个特征值和特征矢量，这些特征矢量之间是正交的。相关矩阵R X 就是一个实对称矩阵，当训练样本足够多时，也可以满足正定性，根据上式我们知道，当要从N 维特征中提取出M 维特征时，我们只需要统计出特征相关矩阵R X ，然后计算其特征值和特征矢量，选择对应特征值最大的前M 个特征矢量作成一个N ⨯M 特征变换矩阵T ，就可以完成特征提取。步骤如下：

T ⎤XX 1、利用训练样本集合估计出相关矩阵R X =E ⎡⎣⎦；

2、计算R X 的特征值，并由大到小排序：λ1≥λ2≥3、选择前M 个特征矢量作成一个变换矩阵T =[T 1

以及相应的特征矢量：T ≥λN ，1, T 2, , T N ；

T 2

T M ]；

4、在训练和识别时，每一个输入的N 维特征矢量X 可以转换为M 维的新特征矢量：Y =T X 。

这种方法是利用相关矩阵R X 进行变换，同样也可以利用协方差矩阵C X 进行变换，还可以利用样

-1

本的散度矩阵S W ，S B ，S T 或者S W S B 进行变换。过程都是一样的，需要计算特征值和特征向量，选

择最大的M 个特征值对应的特征矢量作出变换矩阵。

5. 实验设计和结果分析

基于特征相关性的特征选择算法选择c 均值聚类算法来去除冗余。

C 均值算法的基本思想即是通过迭代寻找c 个聚类的一种划分方案，使得用这c 个聚类的均值来代表相应各类样本时所得到的总体误差最小。

C 均值算法的基础是最小误差平方和准则。若N i 是第i 聚类Γi 中的样本数目，m i 是这些样本的均值，即m i =

N i

y ∈Γi

∑y

把Γi 中的各样本y 与均值m i 间的误差平方和对所有类相加后为

J e =∑∑y -m i

i =1y ∈Γi

J e 是误差平方和聚类准则，它是样本集y 和类别集Ω的函数。

C 均值算法的步骤：

1. 选择初始划分，并计算每个聚类的均值以及误差平方和； 2. 选择一个备选样本y ，设y ∈Γi ；

the first results of kmeans

X 3

1. 无论在聚类时，初始均值如何选取，在程序结果中总能得到相同的分类结果，同时J e 的结果相差很小。 2．当各聚类设定的初始均值不同时，程序结果经过的步骤不同。

3. J e 是随着聚类数目的增加而单调的减少的，当聚类数目等于样本数时J e =0，即每个样本自己成一类。 4. 此算法是个局部搜索算法，并不能保证收敛到全局最优解，即不能保证找到所有可能的聚类划分中误差平方和最小的解。算法的结果受到初始划分和样本调整顺序的影响。

6. 结论

模式识别技术是人工智能的基础技术，21世纪是智能化、信息化、计算花、网络化的世纪，在这个以数字计算为特征的世纪里，模式识别技术将会获得巨大的发展空间。

特征选择作为数据预处理的一个必要步骤，是模式识别中的一个关键问题。一个模式识别系统的成败，首先取决于所利用的特征是否较好的反映了将要研究的分类问题。而且高维数据是特征选择的一个挑战，研究人员总是努力的寻找着各种方法来尽量提高特征选择的性能。对于特征选择与特征提取，还有许多问题期待解决：高维数据的特征选择，特别是训练样本较少而特征维数极高的数据集；在样本的类别数未知的情况下，设计时间复杂度较低的非监督的特征选择；如何在进行特征选择时，选择有意义的训练样本；将维数约简与距离度量学习相结合；随着特征选择的应用领域不断扩大，当出现新的非线性相关的数据类型时，如何设计新的特征选择算法；将特征选择算法应用于人脸识别与人脸检测中，消除传统人脸识别方法如PCA 和LDA 固有的局限性。

模式识别是一门理论与实践紧密结合的学科，教与学的方式值得我们研究和探索。还可以看出模式识别具有相当大的前景，而且模式识别的应用得到越来越多的人的支持，而且它的成效也十分显著。因此它也得到各国的重视，正因各个单位集体对人工智能的模式识别给予相关的重视，模式识别技术在现今社会也能快速发展。当然，现在的模式识别还不算真正完整，不过人类科技的技术是不断发展的，相信总有一天人工智能中的模式识别会真正融入我们的社会，成为我们人类不可或缺的一部分。而设计具体的、专业的、高效的特征选择算法是一个值得重视值得探索的研究方向。

7. 参考文献：

[1] 张学工. 模式识别（第三版) . 北京：清华大学出版社，2010

[2] 朱明，王俊普，蔡庆生. 一种最优特征集的选择算法，计算机研究与发展.vol.35(9),pp.803-805,1998 [3] L.Yu,H.Lu,Efficient feature selection via analysis of relevance and redundancy,Machine Learning Research,vol.5,pp.1205-1224,2004

[4] M.Dash,K.Choi,P.Scheuermann and H.Liu,Feature selection for clustering-A filter solution,IEEE Int l Conf.on Data Mining,pp.115-122,2002

[5] 李弼程，邵美珍等. 模式识别原理及应用[M].西安：西安电子科技大学出版社,2008 [6] P.Berkhin,Survey of clustering data mining techniques,Technical Report,Accrue software,2002

，

模式识别特征选择与提取

日期：2014 年 06月 10日

摘要

关键词：特征选择，特征提取，主成分分析，线性判别分析

1. 引言

2. 原理分析

对一原始特征来说，特征选择的方案很多，从N 维特征种选择出M 个特征共有

M C N =

N !

中选法，其中哪一种方案最佳，则需要有一个原则来进行指导。

M ! N -M !

人们对的特征的可分性判据研究很多下面几种常用的判据，我们需要根据实际问题，从中选择出一种。

一般来说，我们希望可分性判据满足以下几个条件：

1. 与识别的错误率由直接的联系，当判据取最大值时，识别的错误率最小； 2. 当特征独立时有可加性，即：

J ij (x 1, x 2, , x N ) =∑J ij (x K )

K =1

J ij 是第i 类和第j 类的可分性判据，J ij 越大，两类的可分程度越大，(x 1, x 2,

特征；

3. 应具有某种距离的特点：

, x N )为N 维

J ij >0，当i ≠j 时； J ij =0，当i =j 时；

J ij =J ji ；

4. 单调性，加入新的特征后，判据不减小：

J ij (x 1, x 2, , x N )≤J ij (x 1, x 2, , x N , x N +1)。

主成分分析方法的出发点是从一组特征中计算出一组按重要性从大到小排序的新特征，他们是原有特征的线性组合，并且相互之间是不相关的。

记x 1, x 2, , x p 为p 个原始特征，设新特征ξ，i=1, ，p 是这些原始特征的线性组合

ξi =∑αij x j =αi T x ，

j =1

为了统一ξi 的尺度，要求线性组合的模为1，即

αi T αi =1，

写成矩阵形式是

ξ=A T x ，

其中，ξ是由新特征ξi 组成的向量，A 是特征变换矩阵。要求解的是最优的正交变换A ，它使新特征ξi 的方差达到极值。

3. 理论证明或说明

特征选择的基本框图为:

一个典型的特征选择算法通常包括四个人基本步骤:

1. 子集产生，这是一个搜索过程，通过一定的搜索策略产生候选的特征子集。

4. 结果验证，就是根据一定的先验知识或通过合成现实数据集的测试来证明所选择的特征子集的性能。

基于特征提取主成分分析变换矩阵的一般过程：

训练数据全集

4. 实现方法或步骤流程

特征选择顺序前进法

其中j =1, 2,

({x })，

, N -k ，并且按照由大到小排序，将可分性判据最大的特征x l 加入X k ，

X k +1=X k

{x l }；

3) 直到所选的特征数等于M 为止。

特征抽取的方法—基于离散K-L 变换(DKLT)的特征抽取：设原始特征为N 为矢量X =(x 1, x 2,

, x N )，均值矢量m =E [X ]，相关矩阵R X =E ⎡⎣XX ⎤⎦，

协方差矩阵C X =E ⎡(X -m )(X -m )⎤。

⎣⎦

我们可以对X 作如下的标准正交变换，将其变为矢量Y =(y 1, y 2, , y N ):

⎡T 1T ⎤⎢T ⎥T

Y =T T X =⎢2⎥X

⎢⎥⎢T ⎥⎢T N ⎦⎥⎣

Y 的每个分量：y i =T i T X ，其中T 为一个N ⨯N 的标准正交矩阵，T i 为其第i 个列矢量，

⎧1, i =j

。也就是说Y 的每个分量是X 每一个分量的线性组合。 T i T T j =⎨

⎩0, i ≠j

同样X 可以表示为：

X =(T T )Y =TY =(T 1T 2

-1

⎡y 1⎤⎢y ⎥N

T N )⎢2⎥=∑y i T i

⎢⎥i =1⎢⎥⎢y N ⎦⎥⎣

我们要进行特征提取，也就是要用Y 的M 项来代替X ，这种代替必然带来误差，下面我们来对这

个误差进行估计：

ˆ=∑y T ，1≤M

i =1

e (M )=E ⎡X -X

⎢⎣

()(

⎤⎡⎤X -X ⎤=∑E ⎡y =E y y ∑i i i ⎦ ⎥⎦i =M +1⎣⎦i =M +1⎣N

)

N N

i =M +1

∑T E ⎡⎣XX

⎤⎦T i =

i =M +1

∑T R

X i

这又变成一个优化问题，我们希望寻找到一个标准正交矩阵T ，使得e 样的准则函数：

(M )最小，因此可以去这

J =

i =M +1

∑T R

T i

T i -

i =M +1

∑λ(T T -1)

T i

第一项保证均方误差最小，第二项保证T 为标准正交矩阵，λi 为一待定常数。

∂J

=(R X -λi I )T i =0，i =M +1, ∂T i

, N

即：R X T i =λi T i ，很明显λi 为相关矩阵R X 的特征值，T i 为对应于λi 的特征矢量，由于R X 是一个实对称矩阵，所以T 1, T 2,

. T N 相互正交，T 为一个正交矩阵。均方无差：

e (M )=

i =M +1

∑T R

T i

T i =

i =M +1

∑T λT =∑λ

T i

i i

i =M +1

N N

T ⎤XX 1、利用训练样本集合估计出相关矩阵R X =E ⎡⎣⎦；

2、计算R X 的特征值，并由大到小排序：λ1≥λ2≥3、选择前M 个特征矢量作成一个变换矩阵T =[T 1

以及相应的特征矢量：T ≥λN ，1, T 2, , T N ；

T 2

T M ]；

4、在训练和识别时，每一个输入的N 维特征矢量X 可以转换为M 维的新特征矢量：Y =T X 。

这种方法是利用相关矩阵R X 进行变换，同样也可以利用协方差矩阵C X 进行变换，还可以利用样

-1

本的散度矩阵S W ，S B ，S T 或者S W S B 进行变换。过程都是一样的，需要计算特征值和特征向量，选

择最大的M 个特征值对应的特征矢量作出变换矩阵。

5. 实验设计和结果分析

基于特征相关性的特征选择算法选择c 均值聚类算法来去除冗余。

C 均值算法的基本思想即是通过迭代寻找c 个聚类的一种划分方案，使得用这c 个聚类的均值来代表相应各类样本时所得到的总体误差最小。

C 均值算法的基础是最小误差平方和准则。若N i 是第i 聚类Γi 中的样本数目，m i 是这些样本的均值，即m i =

N i

y ∈Γi

∑y

把Γi 中的各样本y 与均值m i 间的误差平方和对所有类相加后为

J e =∑∑y -m i

i =1y ∈Γi

J e 是误差平方和聚类准则，它是样本集y 和类别集Ω的函数。

C 均值算法的步骤：

1. 选择初始划分，并计算每个聚类的均值以及误差平方和； 2. 选择一个备选样本y ，设y ∈Γi ；

the first results of kmeans

X 3

6. 结论

7. 参考文献：

[1] 张学工. 模式识别（第三版) . 北京：清华大学出版社，2010

[4] M.Dash,K.Choi,P.Scheuermann and H.Liu,Feature selection for clustering-A filter solution,IEEE Int l Conf.on Data Mining,pp.115-122,2002

，

模式识别特征选择与提取

相关内容

热门内容

标签