第十章 特征空间
? 10.0 引言
? 10.1 特征提取
? 10.2 特征选择
10.0 引言
? 模式识别中把每个对象都量化为一组特征来描述，构建特征空间是所有模式识别问题的第一步
? 通过直接测量得到的特征称为 原始特征
? 比如人体的各种生理指标（描述其健康状况）
? 数字图象中的每点灰度值（以描述图像内容）
10.0 引言
? 原始特征数量可能很大，不利于学习。
比如 1024*768的灰度图像,256灰度级。
? 直接表示，每幅需要 786,432 bytes。进行训练识别所需空间、时间、计算量都无法承受！
? 很少的样本分布会在如此高维的特征空间中显得十分稀疏，因而产生过学习的现象。
? 特征空间有很大的冗余。完全可以用很小的空间相当好地近似表示图像，这一点与压缩的思想类似。
10.0 引言
? 如何提取特征与具体问题有很大关系，
特征是 对象的表达,根据知识来考虑
? 特征的稳定性
? 特征的可分性
? 例：
? 白细胞的浓度
? 指纹的细节特征指纹细节特征
10.0 引言
? 模式识别中处理特征空间的方法可分为两类：
? 特征提取 (Feature Extraction)：用映射（或变换）
的方法把原始特征 变换 为新特征，称为特征提取
? 傅立叶变换
? 小波变换
? PCA变换
? ICA变换
? Gabor变换
? 。。。
10.0 引言
? 特征选择 (Feature Selection)：从原始特征中挑选 出一些最有代表性、可分性能最好的特征来，称为特征选择
10.1 特征提取
10.1 特征提取
? 特征提取的目的是希望通过变换把原来的特征变换到新的特征空间，使得特征的可分性更好。
? PCA
? LDA
10.1 特征提取－ PCA
? 希望通过变换，用较少的特征可以近似表示原来的对象,
而且误差尽量的小。
? 在所有正交线性变换中，这种最优的变换是 Karhunen-Loeve (KL)变换，相应的特征提取方法被称为 Principle Component
Analysis (PCA)。
T
m
yyy ),,,(
21
L
T
n
xxxx ),,,(
21
L=
nm<<
10.1 特征提取－ PCA
? 正交变换
? 给定 n维空间中的一组标准正交基,
它诱导了一个线性变换：
? 反之，任何一个正交变换也确定了一组正交基。
n
φφφ,,,
21
L
yxL →:
T
n
yyyyxL ),,,()(
21
L==
.
i
T
i
xy φ=
.,,2,1 ni L=
.
1
i
n
i
i
yx φ
∑
=
=
正交展开
10.1 特征提取－ PCA
? 误差
? 用 m个分量表示带来的误差：
? 希望误差平方的期望最小：
.)(
11
i
n
mi
ii
m
i
i
yyxmx φφ
∑∑
+==
=?=?
.)()(
1
2
2
2
∑
+=
=?=
n
mi
i
yEmxEme
对所有的 求期望。
x
10.1 特征提取－ PCA
? 求解最小均方误差正交基：
? 首先假定随机矢量为零均值（期望）的，否则减掉均值即可。
? 找 n个正交基,使得对任意一组正交基,和所有的
.0=Ex
n
φφφ,,,
21
L
.)()()()(
1
2
2
1
2
2
∑∑
+=+=
=≤=
n
mi
i
T
n
mi
i
T
xEmexEme?φ
φ
n
,,,
21
L
,nm≤
10.1 特征提取－ PCA
? 对于一个固定的 m
∑∑
+=+=
Σ==
n
mi
i
T
i
n
mi
i
TT
i
xxEme
11
2
minmin)(min φφφφ
φ
nmmits
i
L,2,1,1..
2
++==φ
).(
T
xxE=Σ
协方差矩阵。
10.1 特征提取－ PCA
? 用 Lagrange 乘子法：
)(min
1
2
1
∑∑
+=+=
Σ
n
mi
ii
n
mi
i
T
i
φλφφ
得到
iii
φλφ =Σ
是 的特征向量,是特征根。
i
λΣ
i
φ
∑∑
+=+=
=Σ=
n
mi
i
n
mi
i
T
i
me
11
2
)( λφφ
φ
10.1 特征提取－ PCA
? 协方差矩阵的所有特征根是实数，特征向量也是实的，所有 n个特征向量构成一组标准正交基，记作,分别对应特征根
n
ξξξ,,,
21
L
.
21 n
λλλ ≥≥≥ L
=Σ
T
T
T
n
n
n
ξ
ξ
ξ
λ
λ
λ
ξξξ
MO
2
1
2
1
21
),...,(
10.1 特征提取－ PCA
? 选择协方差矩阵的特征向量 作为正交基，可以使得均方误差最小
n
ξξξ,,,
21
L
10.1 特征提取－ PCA
? 总结：
? 向量在协方差矩阵的特征向量上的展开称为
Karhunen-Loeve(KL)展开，诱导的线性变换叫做 Karhunen-Loeve变换；
? 实际应用中，协方差矩阵是未知的，用样本协方差矩阵代替；
10.1 特征提取－ PCA
? 特征向量常被叫做,主分量,，每个样本被它在前几个主分量上的投影近似表示
? 特征值标记着相应特征向量上的能量
? 张成的空间称为原空间的子空间，
PCA实际上是在子空间上的投影，并且
.)(
111
i
m
i
i
T
i
m
i
ii
n
i
i
xyyx ξξξξ
∑∑∑
===
=≈=
m
ξξξ,,,
21
L
2
1
2
1
1
2
1
2
1
1
2
21 ∑∑∑∑
====
≈?=?
m
i
ii
m
i
ii
n
i
ii
n
i
ii
yyyyxx ξξξξ
10.1 特征提取－ PCA
? PCA的问题：由于用样本协方差矩阵代替协方差矩阵，主分量与训练数据有着很大关系，用一批训练数据得到的主成分，可能不反映其另外一批数据的特征。
10.1 特征提取－ PCA
PCA的例子：
1
x
2
x
1
y
2
y
1
φ
2
φ
1
b
2
b
2
λ1
λ
10.1 特征提取－ LDA
? 线性判别分析,Linear Discriminant
Analysis (LDA) Fisher(1936),Rao(1965)
? 在线性判别函数一章，我们讲过 Fisher线性判别函数。它的思想是，找一个方向作投影，
使得投影后的数据类间距尽可能大，类内距尽可能小。这实际上是两类数据的特征提取，
提取的特征数是１。这一思想可以推广到任意类数据，提取任意多个特征。
10.1 特征提取－ LDA
? 准则：
? 用原来的特征表示的数据记作
? 提取的特征表示的数据记作 W是
的矩阵。
? 沿用 Fisher判别函数中的记号，假设共有 类：
,
n
x?∈
,
m
Wxy?∈=
nm×
∑
=
k
ji
T
jijib
mmmm
k
S
,
))((
1
).(
1
21 kw
k
S ∑++∑+∑= L
k
类间散度矩阵类内总散度矩阵
10.1 特征提取－ LDA
? 用提取的 个特征表示的数据的类内、类间散度矩阵记作：
? 准则：求 W，希望类内距小、类间距大。
m
.
~
,
~
T
ww
T
bb
WWSS
WWSS
=
=
)).()((
)
~~
()(
1
1
T
b
T
w
bw
WWSWWStr
SStrWJ
=
=
10.1 特征提取－ LDA
? 求 ：
W
.0
)(
=
W
WJ
令得到：
).
~~
()(
11
bw
TT
bw
SSWWSS
=
小技巧：对角化
).
~~
(
1
bw
SS
存在矩阵 ，使得：
)( mm
A
×
.
~~
1
11
Λ=
ASSA
bw
为对角阵
（见习题１）
10.1 特征提取－ LDA
.)(
)(
1
1
1
1
1
Λ=
Λ=
AWAWSS
AAWWSS
TT
bw
TT
bw
于是：
是
( )
1
bw
SS
的 个特征向量！
m
AW
T
这说明特征向量的求解就用前面的对角化方法：
.
2
1
2
11
Λ=
Λ=
××
×
×
nnnnbw
nnbwnn
BBSS
BSSB
10.1 特征提取－ LDA
? m维空间中的任何非奇异变换矩阵 A都不改变 J(W)的值，因此可以忽略 A。 (请自己证明）
? 设矩阵 的特征值为：
? 则选取前 m个特征值对应的特征向量作为
W，则
)(
1
bw
SS
n
λλλ ≥≥≥ L
21
∑
=
=
m
i
i
WJ
1
)( λ
10.1 特征提取－ LDA
? 关于 LDA的几点说明：
? 对于 k类问题，选出的特征个数最多只有 k-1，
这是因为 的秩最多为 k-1。因此，对应非零特征根的特征向量最多有 k-1个，那些零特征根对应的特征向量对判据 的值没有任何影响。
b
S
J
10.1 特征提取－ LDA
? LDA可以从另一个角度很容易的推出：假设每类数据服从不同均值，相同协方差均阵
的正态分布。从最小错误率准则出发就可以得到相同的结果。
w
S
回忆 Bayes决策理论一章的习题，两类问题，正态分布且相同协方差矩阵的假设下，决策面是超平面：
)(
.
21
1
mmSw
constxw
w
T
=
=
特征：
10.1 特征提取－ LDA
)(
21
1
mmSw
w
=
就是矩阵
T
wbw
mmmmSSS ))((
2121
11
=
的特征向量。因为
wmmS
mmSmmmmS
wSS
w
w
T
w
bw
λλ =?=
=
)(
)}()){((
21
1
21
1
2121
1
1
10.1 特征提取－ LDA
? 推广：
? LDA可以从相同协方差矩阵的正态分布假设和最小错误率准则推出，是 Campbell在 1984
年指出的。
? 可以做两方面的推广：
? 假设各类服从协方差矩阵不同的正态分布，称为
Heteroscedastic Discriminant Analysis (HDA).
? 假设各类服从协方差矩阵相同的 Gauss混合分布。
10.2 特征选择
10.2 特征选择
? 特征选择是从原始特征中 挑选 出一些最有代表性，分类性能最好的特征来。
? 每个特征的状态是离散的 — 选与不选
? 从 N个特征中选取 k个,共 种 组合。若不限定个数，则共 2
N
种。－ NP 问题
? 这是一个典型的组合优化问题
k
N
C
10.2 特征选择
? 特征选择的方法大体可分两大类：
? Filter方法：不考虑所使用的学习算法。通常给出一个独立于分类器的指标μ来评价所选择的特征子集 S，然后在所有可能的特征子集中搜索出使得
μ最大的特征子集作为最优特征子集。
? Wrapper方法：将特征选择和分类器结合在一起，
即特征子集的好坏标准是由分类器决定的，在学习过程中表现优异的的特征子集会被选中。
10.2 特征选择
? 一种 Filter算法,FOCUS
? 该算法致力于寻找一个能够正确区分所有类别的 最小 特征集合。
? 例如，若区分每个人的特征有：姓名、
性别、籍贯、工作单位、身份证号 ……
则该算法会选择：身份证号
? 搜索时先看一个特征能否正确区分样本，
若不能，则考察两个特征 ……以此类推
10.2 特征选择
? 一种 Wrapper算法,OBLIVION
? 该方法与 最近邻法 结合，根据特征子集的分类表现来选择特征
? 用 顺序后退法 搜索特征子集：
从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率（基于最近邻法 )。依次迭代，直至识别率开始下降为止
? 用 leave-one-out 方法估计平均识别率：
用 N-1个样本判断余下一个的类别,N次取平均
10.2 特征选择
? 许多特征选择算法力求解决搜索问题，
经典算法有,
? 分支定界法
? 顺序后退法
? 顺序前进法
? 模拟退火法
? Tabu 搜索法
? 遗传算法
10.2 特征选择－遗传算法
? 该算法受进化论启迪，根据,物竞天择，
适者生存,这一规则演变
? 几个术语：
? 基因链码：使用遗传算法时要把问题的每个解编码成一个基因链码。比如要从 D个特征中挑选 d个,就用一个 D位的 0或 1组成的字符串表示一种特征组合。 1表示该特征被选中每个基因链码代表一个解，称作一个,个体,，
其中的每一位看作一个,基因,
10.2 特征选择－遗传算法
? 群体：若干个体的集合，也就是一些解的集合
? 交叉：选择群体中的两个个体，以这两个个体为双亲作基因链码的交叉，从而产生两个新的个体，作为后代。
? 变异：对某个体，随机选取其中一位，将其翻转
? 适应度：对每个解，以给定的优化准则来评价其性能的优劣，作为其适应度
X
1
1000 1100 X`
1
1000 1010
X
2
0100 1010 X`
2
0100 1100
1000010 1001010
10.2 特征选择－遗传算法
? 遗传算法的基本框架：
1,初始化进化世代数 t=0
2,给出初始化群体 P(t)，令 x
g
为任一个体
3,对 P(t) 中每个个体估值，并将群体中最优解 x`与 x
g
比较，若优于 x
g
，则令 x
g
=x`
4,如果终止条件满足，则算法结束,x
g
为最终结果。否则，转步骤 5
5,从 P(t)选择个体并进行交叉和变异操作，得到新一代个体
P(t+1)，令 t=t+1，转步骤 3。
10.2 特征选择－遗传算法
? 关于遗传算法的说明：
? 由步骤 3保证了最终解是所搜索过的最优解
? 常用的终止条件是群体的世代数超过一个给定值，或连续数个世代都没有得到更优解
? 群体的大小和演化代数是值得重视的参数。
在一定范围内，这两个参数大些能得到更好的解
? 对交叉的亲本选择可采用如下规则：个体的性能越好，被选中的可能性也越大
10.2 特征选择
? 例：用于癌症分类的基因选择
? 根据癌症患者与正常人的基因表达数据，挑选出与癌症相关的基因。
? 这种相关基因很可能就是致病基因，
它可以帮助我们查找病源，进而可以指导设计药物
? 在选出的基因上作病患识别，可以提高识别率，有助于临床诊断
10.2 特征选择
? 基因选择的困难
? 人类大约有3万个左右的基因，但与某种疾病有关的基因并不多
? 基因数（成千上万）远远大于实验样本数（几十）
10.2 特征选择
? 单基因选择算法,基于某种准则给每个基因打分，把得分低的基因滤掉，选取那些得分高的基因组成特征子集。
? 例如 G-S算法,该方法以 Fisher判别指标对每个特征打分。根据每维特征上两类的距离和方差来评价它分类能力。
? 准则函数为
? 其中 分别是基因 g在训练样本中在第一类和第二类的均值和标准差。
? 在分类时，该分值可作为每个特征的分类权重
gg
gg
ggenencorrelatioGS
21
21
)_(_
σσ
μμ
+
=
gggg
2211
,,,σμσμ
10.2 特征选择
? 多基因选择算法,与分类器相联系，采用各种搜索算法或优化算法进行特征选择
? Recursive Feature Elimination (RFE) 算法,根据训练得到的 SVM线性分类器的系数来判断每个特征的重要性和分类能力。
? 假设由线性SVM得到的分类器为
? 当 较大时，第i个特征对分类器影响较大；
? 当 较小时，第i个特征对分类器影响较小；
? 当 为0时,第i个特征对分类器几乎没有影响
∑
+= bxwxf
ii
)(
i
w
i
w
i
w
10.2 特征选择
? Fisher优化模型（ FOM）
? Fisher判别
? 但是基因数远远大于样本数，上面的式子无法求解，我们通过正则化来求解
wSw
wSw
wJ
w
T
b
T
=)(
mwS
w
=
22
1
)( wmwSwF
w
λ+?=
10.2 特征选择
? 我们的目的是进行特征选择，即希望得到的 最好是由少数非零元素组成。通过引入,求解 使得下式最小：
∑
=
>
=
N
k
w
k
w
1
]0[
2
1)(σ
w
)()(
2
2
1
2
2
wwmwSwF
w
σλλ ++?=
∑
=
++?=
N
i
w
w
i
ewmwSwF
1
2
2
1
2
)1()(
2
α
λλ
w
10.2 特征选择
0 0.5 1
0
20
40
60
80
100
0 0.5 1
0
10
20
30
40
50
0 0.5 1
0
10
20
30
40
50
0 0.5 1
0
10
20
30
40
50
First Iteration
Second Iteration
Third Iteration
Fourth Iteration
λ
1
=5000
λ
2
=10
参考文献
? [1] K,Fukunaga,Introduction to Statistical Pattern
Recognition,2
nd
Edition,Academic Press,1990.
? [2] R,Kohavi and G.H,John,Wrappers for feature
subsets selection problem,Artificial Intelligence
Journal,97:12,pp273-324,1997
? 10.0 引言
? 10.1 特征提取
? 10.2 特征选择
10.0 引言
? 模式识别中把每个对象都量化为一组特征来描述，构建特征空间是所有模式识别问题的第一步
? 通过直接测量得到的特征称为 原始特征
? 比如人体的各种生理指标（描述其健康状况）
? 数字图象中的每点灰度值（以描述图像内容）
10.0 引言
? 原始特征数量可能很大，不利于学习。
比如 1024*768的灰度图像,256灰度级。
? 直接表示，每幅需要 786,432 bytes。进行训练识别所需空间、时间、计算量都无法承受！
? 很少的样本分布会在如此高维的特征空间中显得十分稀疏，因而产生过学习的现象。
? 特征空间有很大的冗余。完全可以用很小的空间相当好地近似表示图像，这一点与压缩的思想类似。
10.0 引言
? 如何提取特征与具体问题有很大关系，
特征是 对象的表达,根据知识来考虑
? 特征的稳定性
? 特征的可分性
? 例：
? 白细胞的浓度
? 指纹的细节特征指纹细节特征
10.0 引言
? 模式识别中处理特征空间的方法可分为两类：
? 特征提取 (Feature Extraction)：用映射（或变换）
的方法把原始特征 变换 为新特征，称为特征提取
? 傅立叶变换
? 小波变换
? PCA变换
? ICA变换
? Gabor变换
? 。。。
10.0 引言
? 特征选择 (Feature Selection)：从原始特征中挑选 出一些最有代表性、可分性能最好的特征来，称为特征选择
10.1 特征提取
10.1 特征提取
? 特征提取的目的是希望通过变换把原来的特征变换到新的特征空间，使得特征的可分性更好。
? PCA
? LDA
10.1 特征提取－ PCA
? 希望通过变换，用较少的特征可以近似表示原来的对象,
而且误差尽量的小。
? 在所有正交线性变换中，这种最优的变换是 Karhunen-Loeve (KL)变换，相应的特征提取方法被称为 Principle Component
Analysis (PCA)。
T
m
yyy ),,,(
21
L
T
n
xxxx ),,,(
21
L=
nm<<
10.1 特征提取－ PCA
? 正交变换
? 给定 n维空间中的一组标准正交基,
它诱导了一个线性变换：
? 反之，任何一个正交变换也确定了一组正交基。
n
φφφ,,,
21
L
yxL →:
T
n
yyyyxL ),,,()(
21
L==
.
i
T
i
xy φ=
.,,2,1 ni L=
.
1
i
n
i
i
yx φ
∑
=
=
正交展开
10.1 特征提取－ PCA
? 误差
? 用 m个分量表示带来的误差：
? 希望误差平方的期望最小：
.)(
11
i
n
mi
ii
m
i
i
yyxmx φφ
∑∑
+==
=?=?
.)()(
1
2
2
2
∑
+=
=?=
n
mi
i
yEmxEme
对所有的 求期望。
x
10.1 特征提取－ PCA
? 求解最小均方误差正交基：
? 首先假定随机矢量为零均值（期望）的，否则减掉均值即可。
? 找 n个正交基,使得对任意一组正交基,和所有的
.0=Ex
n
φφφ,,,
21
L
.)()()()(
1
2
2
1
2
2
∑∑
+=+=
=≤=
n
mi
i
T
n
mi
i
T
xEmexEme?φ
φ
n
,,,
21
L
,nm≤
10.1 特征提取－ PCA
? 对于一个固定的 m
∑∑
+=+=
Σ==
n
mi
i
T
i
n
mi
i
TT
i
xxEme
11
2
minmin)(min φφφφ
φ
nmmits
i
L,2,1,1..
2
++==φ
).(
T
xxE=Σ
协方差矩阵。
10.1 特征提取－ PCA
? 用 Lagrange 乘子法：
)(min
1
2
1
∑∑
+=+=
Σ
n
mi
ii
n
mi
i
T
i
φλφφ
得到
iii
φλφ =Σ
是 的特征向量,是特征根。
i
λΣ
i
φ
∑∑
+=+=
=Σ=
n
mi
i
n
mi
i
T
i
me
11
2
)( λφφ
φ
10.1 特征提取－ PCA
? 协方差矩阵的所有特征根是实数，特征向量也是实的，所有 n个特征向量构成一组标准正交基，记作,分别对应特征根
n
ξξξ,,,
21
L
.
21 n
λλλ ≥≥≥ L
=Σ
T
T
T
n
n
n
ξ
ξ
ξ
λ
λ
λ
ξξξ
MO
2
1
2
1
21
),...,(
10.1 特征提取－ PCA
? 选择协方差矩阵的特征向量 作为正交基，可以使得均方误差最小
n
ξξξ,,,
21
L
10.1 特征提取－ PCA
? 总结：
? 向量在协方差矩阵的特征向量上的展开称为
Karhunen-Loeve(KL)展开，诱导的线性变换叫做 Karhunen-Loeve变换；
? 实际应用中，协方差矩阵是未知的，用样本协方差矩阵代替；
10.1 特征提取－ PCA
? 特征向量常被叫做,主分量,，每个样本被它在前几个主分量上的投影近似表示
? 特征值标记着相应特征向量上的能量
? 张成的空间称为原空间的子空间，
PCA实际上是在子空间上的投影，并且
.)(
111
i
m
i
i
T
i
m
i
ii
n
i
i
xyyx ξξξξ
∑∑∑
===
=≈=
m
ξξξ,,,
21
L
2
1
2
1
1
2
1
2
1
1
2
21 ∑∑∑∑
====
≈?=?
m
i
ii
m
i
ii
n
i
ii
n
i
ii
yyyyxx ξξξξ
10.1 特征提取－ PCA
? PCA的问题：由于用样本协方差矩阵代替协方差矩阵，主分量与训练数据有着很大关系，用一批训练数据得到的主成分，可能不反映其另外一批数据的特征。
10.1 特征提取－ PCA
PCA的例子：
1
x
2
x
1
y
2
y
1
φ
2
φ
1
b
2
b
2
λ1
λ
10.1 特征提取－ LDA
? 线性判别分析,Linear Discriminant
Analysis (LDA) Fisher(1936),Rao(1965)
? 在线性判别函数一章，我们讲过 Fisher线性判别函数。它的思想是，找一个方向作投影，
使得投影后的数据类间距尽可能大，类内距尽可能小。这实际上是两类数据的特征提取，
提取的特征数是１。这一思想可以推广到任意类数据，提取任意多个特征。
10.1 特征提取－ LDA
? 准则：
? 用原来的特征表示的数据记作
? 提取的特征表示的数据记作 W是
的矩阵。
? 沿用 Fisher判别函数中的记号，假设共有 类：
,
n
x?∈
,
m
Wxy?∈=
nm×
∑
=
k
ji
T
jijib
mmmm
k
S
,
))((
1
).(
1
21 kw
k
S ∑++∑+∑= L
k
类间散度矩阵类内总散度矩阵
10.1 特征提取－ LDA
? 用提取的 个特征表示的数据的类内、类间散度矩阵记作：
? 准则：求 W，希望类内距小、类间距大。
m
.
~
,
~
T
ww
T
bb
WWSS
WWSS
=
=
)).()((
)
~~
()(
1
1
T
b
T
w
bw
WWSWWStr
SStrWJ
=
=
10.1 特征提取－ LDA
? 求 ：
W
.0
)(
=
W
WJ
令得到：
).
~~
()(
11
bw
TT
bw
SSWWSS
=
小技巧：对角化
).
~~
(
1
bw
SS
存在矩阵 ，使得：
)( mm
A
×
.
~~
1
11
Λ=
ASSA
bw
为对角阵
（见习题１）
10.1 特征提取－ LDA
.)(
)(
1
1
1
1
1
Λ=
Λ=
AWAWSS
AAWWSS
TT
bw
TT
bw
于是：
是
( )
1
bw
SS
的 个特征向量！
m
AW
T
这说明特征向量的求解就用前面的对角化方法：
.
2
1
2
11
Λ=
Λ=
××
×
×
nnnnbw
nnbwnn
BBSS
BSSB
10.1 特征提取－ LDA
? m维空间中的任何非奇异变换矩阵 A都不改变 J(W)的值，因此可以忽略 A。 (请自己证明）
? 设矩阵 的特征值为：
? 则选取前 m个特征值对应的特征向量作为
W，则
)(
1
bw
SS
n
λλλ ≥≥≥ L
21
∑
=
=
m
i
i
WJ
1
)( λ
10.1 特征提取－ LDA
? 关于 LDA的几点说明：
? 对于 k类问题，选出的特征个数最多只有 k-1，
这是因为 的秩最多为 k-1。因此，对应非零特征根的特征向量最多有 k-1个，那些零特征根对应的特征向量对判据 的值没有任何影响。
b
S
J
10.1 特征提取－ LDA
? LDA可以从另一个角度很容易的推出：假设每类数据服从不同均值，相同协方差均阵
的正态分布。从最小错误率准则出发就可以得到相同的结果。
w
S
回忆 Bayes决策理论一章的习题，两类问题，正态分布且相同协方差矩阵的假设下，决策面是超平面：
)(
.
21
1
mmSw
constxw
w
T
=
=
特征：
10.1 特征提取－ LDA
)(
21
1
mmSw
w
=
就是矩阵
T
wbw
mmmmSSS ))((
2121
11
=
的特征向量。因为
wmmS
mmSmmmmS
wSS
w
w
T
w
bw
λλ =?=
=
)(
)}()){((
21
1
21
1
2121
1
1
10.1 特征提取－ LDA
? 推广：
? LDA可以从相同协方差矩阵的正态分布假设和最小错误率准则推出，是 Campbell在 1984
年指出的。
? 可以做两方面的推广：
? 假设各类服从协方差矩阵不同的正态分布，称为
Heteroscedastic Discriminant Analysis (HDA).
? 假设各类服从协方差矩阵相同的 Gauss混合分布。
10.2 特征选择
10.2 特征选择
? 特征选择是从原始特征中 挑选 出一些最有代表性，分类性能最好的特征来。
? 每个特征的状态是离散的 — 选与不选
? 从 N个特征中选取 k个,共 种 组合。若不限定个数，则共 2
N
种。－ NP 问题
? 这是一个典型的组合优化问题
k
N
C
10.2 特征选择
? 特征选择的方法大体可分两大类：
? Filter方法：不考虑所使用的学习算法。通常给出一个独立于分类器的指标μ来评价所选择的特征子集 S，然后在所有可能的特征子集中搜索出使得
μ最大的特征子集作为最优特征子集。
? Wrapper方法：将特征选择和分类器结合在一起，
即特征子集的好坏标准是由分类器决定的，在学习过程中表现优异的的特征子集会被选中。
10.2 特征选择
? 一种 Filter算法,FOCUS
? 该算法致力于寻找一个能够正确区分所有类别的 最小 特征集合。
? 例如，若区分每个人的特征有：姓名、
性别、籍贯、工作单位、身份证号 ……
则该算法会选择：身份证号
? 搜索时先看一个特征能否正确区分样本，
若不能，则考察两个特征 ……以此类推
10.2 特征选择
? 一种 Wrapper算法,OBLIVION
? 该方法与 最近邻法 结合，根据特征子集的分类表现来选择特征
? 用 顺序后退法 搜索特征子集：
从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率（基于最近邻法 )。依次迭代，直至识别率开始下降为止
? 用 leave-one-out 方法估计平均识别率：
用 N-1个样本判断余下一个的类别,N次取平均
10.2 特征选择
? 许多特征选择算法力求解决搜索问题，
经典算法有,
? 分支定界法
? 顺序后退法
? 顺序前进法
? 模拟退火法
? Tabu 搜索法
? 遗传算法
10.2 特征选择－遗传算法
? 该算法受进化论启迪，根据,物竞天择，
适者生存,这一规则演变
? 几个术语：
? 基因链码：使用遗传算法时要把问题的每个解编码成一个基因链码。比如要从 D个特征中挑选 d个,就用一个 D位的 0或 1组成的字符串表示一种特征组合。 1表示该特征被选中每个基因链码代表一个解，称作一个,个体,，
其中的每一位看作一个,基因,
10.2 特征选择－遗传算法
? 群体：若干个体的集合，也就是一些解的集合
? 交叉：选择群体中的两个个体，以这两个个体为双亲作基因链码的交叉，从而产生两个新的个体，作为后代。
? 变异：对某个体，随机选取其中一位，将其翻转
? 适应度：对每个解，以给定的优化准则来评价其性能的优劣，作为其适应度
X
1
1000 1100 X`
1
1000 1010
X
2
0100 1010 X`
2
0100 1100
1000010 1001010
10.2 特征选择－遗传算法
? 遗传算法的基本框架：
1,初始化进化世代数 t=0
2,给出初始化群体 P(t)，令 x
g
为任一个体
3,对 P(t) 中每个个体估值，并将群体中最优解 x`与 x
g
比较，若优于 x
g
，则令 x
g
=x`
4,如果终止条件满足，则算法结束,x
g
为最终结果。否则，转步骤 5
5,从 P(t)选择个体并进行交叉和变异操作，得到新一代个体
P(t+1)，令 t=t+1，转步骤 3。
10.2 特征选择－遗传算法
? 关于遗传算法的说明：
? 由步骤 3保证了最终解是所搜索过的最优解
? 常用的终止条件是群体的世代数超过一个给定值，或连续数个世代都没有得到更优解
? 群体的大小和演化代数是值得重视的参数。
在一定范围内，这两个参数大些能得到更好的解
? 对交叉的亲本选择可采用如下规则：个体的性能越好，被选中的可能性也越大
10.2 特征选择
? 例：用于癌症分类的基因选择
? 根据癌症患者与正常人的基因表达数据，挑选出与癌症相关的基因。
? 这种相关基因很可能就是致病基因，
它可以帮助我们查找病源，进而可以指导设计药物
? 在选出的基因上作病患识别，可以提高识别率，有助于临床诊断
10.2 特征选择
? 基因选择的困难
? 人类大约有3万个左右的基因，但与某种疾病有关的基因并不多
? 基因数（成千上万）远远大于实验样本数（几十）
10.2 特征选择
? 单基因选择算法,基于某种准则给每个基因打分，把得分低的基因滤掉，选取那些得分高的基因组成特征子集。
? 例如 G-S算法,该方法以 Fisher判别指标对每个特征打分。根据每维特征上两类的距离和方差来评价它分类能力。
? 准则函数为
? 其中 分别是基因 g在训练样本中在第一类和第二类的均值和标准差。
? 在分类时，该分值可作为每个特征的分类权重
gg
gg
ggenencorrelatioGS
21
21
)_(_
σσ
μμ
+
=
gggg
2211
,,,σμσμ
10.2 特征选择
? 多基因选择算法,与分类器相联系，采用各种搜索算法或优化算法进行特征选择
? Recursive Feature Elimination (RFE) 算法,根据训练得到的 SVM线性分类器的系数来判断每个特征的重要性和分类能力。
? 假设由线性SVM得到的分类器为
? 当 较大时，第i个特征对分类器影响较大；
? 当 较小时，第i个特征对分类器影响较小；
? 当 为0时,第i个特征对分类器几乎没有影响
∑
+= bxwxf
ii
)(
i
w
i
w
i
w
10.2 特征选择
? Fisher优化模型（ FOM）
? Fisher判别
? 但是基因数远远大于样本数，上面的式子无法求解，我们通过正则化来求解
wSw
wSw
wJ
w
T
b
T
=)(
mwS
w
=
22
1
)( wmwSwF
w
λ+?=
10.2 特征选择
? 我们的目的是进行特征选择，即希望得到的 最好是由少数非零元素组成。通过引入,求解 使得下式最小：
∑
=
>
=
N
k
w
k
w
1
]0[
2
1)(σ
w
)()(
2
2
1
2
2
wwmwSwF
w
σλλ ++?=
∑
=
++?=
N
i
w
w
i
ewmwSwF
1
2
2
1
2
)1()(
2
α
λλ
w
10.2 特征选择
0 0.5 1
0
20
40
60
80
100
0 0.5 1
0
10
20
30
40
50
0 0.5 1
0
10
20
30
40
50
0 0.5 1
0
10
20
30
40
50
First Iteration
Second Iteration
Third Iteration
Fourth Iteration
λ
1
=5000
λ
2
=10
参考文献
? [1] K,Fukunaga,Introduction to Statistical Pattern
Recognition,2
nd
Edition,Academic Press,1990.
? [2] R,Kohavi and G.H,John,Wrappers for feature
subsets selection problem,Artificial Intelligence
Journal,97:12,pp273-324,1997
