cho6特征降维和选择 Part1特征降维
Ch 06.特征降维和选择 Part 1 特征降维
误差与维数 例子 p(x|O,)~N(μ2∑),j=1,2 P(O=P(O,) 贝叶斯误差概率 P(e)= 到μ2的马氏距离 (p1-卩2)∑(1 r增加,误差概率P(e)减小引入新的特征可使增大, 进而降低误差概率P(e) F→>∞,P(e)→0 ·假设各特征独立: x=dgn…,a)G∑
误差与维数 • 例子 • 贝叶斯误差概率 • r增加，误差概率 减小 • ， • 假设各特征独立： ( | ) ( , ), 1, 2 j i p N j x μ Σ = 1 2 P P ( ) ( ) = 2 / 2 / 2 1 ( ) u r P e e du − = 2 1 1 2 1 2 ( ) ( ) t r − = − − μ μ Σ μ μ μ1 到 μ2 的马氏距离 P e( ) r → P e( ) 0 → 1 2 ( , , , ) d Σ = diag 2 2 1 2 1 d i i i i r = − = 引入新的特征可使r增大， 进而降低误差概率 P e( )
维度灾难 在实际应用中 ·当特征个数增加到某一个临界点后,继续增加反而会导 致分类器的性能变差—“维度灾难”( curse of dimensionality) 原因? ·假设的概率模型与真实模型不匹配 ·训练样本个数有限,导致概率分布的估计不准 对于高维数据,“维度灾难”使解决模式识别问 题非常困难,此时,往往要求首先降低特征向量 的维度
维度灾难 • 在实际应用中 • 当特征个数增加到某一个临界点后，继续增加反而会导 致分类器的性能变差——“维度灾难”（curse of dimensionality） • 原因？ • 假设的概率模型与真实模型不匹配 • 训练样本个数有限，导致概率分布的估计不准 • …… • 对于高维数据，“维度灾难”使解决模式识别问 题非常困难，此时，往往要求首先降低特征向量 的维度
降维 降低特征向量维度的可行性 特征向量往往是包含冗余信息的! 有些特征可能与分类问题无关 特征之间存在着很强的相关性 降低维度的方法 特征组合 把几个特征组合在一起,形成新的特征 特征选择 选择现有特征集的一个子集
降维 • 降低特征向量维度的可行性 特征向量往往是包含冗余信息的！ • 有些特征可能与分类问题无关 • 特征之间存在着很强的相关性 • 降低维度的方法 • 特征组合 把几个特征组合在一起，形成新的特征 • 特征选择 选择现有特征集的一个子集
降维 降维问题 线性变换s.非线性变换 ·利用类别标记(有监督)Vs.不用类别标记(无监督) ·不同的训练目标 ·最小化重构误差(主成分分析,PCA) ·最大化类别可分性(线性判别分析,LDA) 最小化分类误差(判别训练, discriminative training) 保留最多细节的投影(投影寻踪, projection pursuit) 最大限度的使各特征之间独立(独立成分分析,CA)
降维 • 降维问题 • 线性变换 vs. 非线性变换 • 利用类别标记（有监督） vs. 不用类别标记（无监督） • 不同的训练目标 • 最小化重构误差（主成分分析，PCA） • 最大化类别可分性（线性判别分析，LDA） • 最小化分类误差（判别训练，discriminative training） • 保留最多细节的投影（投影寻踪，projection pursuit） • 最大限度的使各特征之间独立（独立成分分析，ICA）
主成分分析(PcA) 用一维向量表示d维样本 ·用通过样本均值m的直线(单位向量为e)上的点表示 样本 ak唯一决定了xk 最小化平方重构误差 J(an…,an2e)=∑km+ae-x)=∑|age-(x-m) ∑ale-2∑ae(xkm)+∑|x-m k=1 a.e 2a4-2e(x-m)=0 C av=e(xr-m) (x-m)在e上的投影
主成分分析（PCA） • 用一维向量表示d维样本 • 用通过样本均值m的直线（单位向量为e）上的点表示 样本 • 最小化平方重构误差 ( ) t k k a = − e x m ˆ k k x m e = + a 2 2 1 1 1 1 2 2 2 1 1 1 ( , , , ) ( ) ( ( )) 2 ( ) n n n k k k k k k n n n t k k k k k k k J a a a a a a = = = = = = + − = − − = − − + − e m e x e x m e e x m x m k x ak 唯一决定了 ˆ k x 1 1 ( , , , ) 2 2 ( ) 0 n t k k k J a a a a = − − = e e x m (xk -m)在e上的投影
主成分分析(PcA) 用一维向量表示d维样本 Q
主成分分析（PCA） • 用一维向量表示d维样本 e ak xk m
主成分分析(PcA) 寻找e的最优方向 a=e(x4-m)J(a…,an,e)=∑alr-2ae(x4-m)+∑|4-m k=l J(e)∑a2-2∑+∑|x-m ∑e(x4-m)2+∑|x-m k=1 ∑e(x4-m)x-m)e+∑|;-m k=1 -eS+2xm s=∑(x-m)x-m) 散布矩阵( scatter matrix)
主成分分析（PCA） • 寻找e的最优方向 ( ) t k k a = − e x m 2 2 2 1 1 1 1 1 ( , , , ) 2 ( ) n n n t n k k k k k k k J a a a a = = = e e e x m x m = − − + − 2 2 2 1 1 1 1 2 2 1 1 2 1 1 2 1 ( ) 2 [ ( )] ( )( ) n n n k k k k k k n n t k k k k n n t t k k k k k n t k k J a a = = = = = = = = = − + − = − − + − = − − − + − = − + − e x m e x m x m e x m x m e x m e Se x m1 ( )( ) n t k k k= S x m x m = − − 散布矩阵（scatter matrix） = − ( 1) n C
主成分分析(PcA) 使J(e)最小的e最大化eSe 拉格朗日乘子法(约束条件ee=1) u=e'se-Ne'e-D) =2Se-2e=0 λ是S的本征值( eigenvalue) Se=he e是S的本征向量( eigenvector) e' se=dee 》最大本征值λ对应eSe的最大值 结论:e为散布矩阵最大的本征值对应的本征向量
主成分分析（PCA） • 使 最小的e最大化 • 拉格朗日乘子法（约束条件 ） • 结论：e为散布矩阵最大的本征值对应的本征向量 ( 1) t t u = − − e Se e e 1 J ( )e t e Se 2 2 0 u = − = Se e e 1 t e e = Se e = 是S的本征值（eigenvalue） e是S的本征向量（eigenvector） t t e Se e e = = 最大本征值 对应 e Se t 的最大值
主成分分析(PcA) 将一维的a扩展到d'(d≤d)维空间 用y=:2来表示x d x,=m+∑ake 最小化平方误差 Jg(e) ∑ m+>akeI-x k=1
主成分分析（PCA） • 将一维的 扩展到 维空间 • 用 来表示 • 最小化平方误差 1 ˆ d k ki i i a = x m e = + k a d d d ( ) 1 2 k k k kd a a a = y k x 2 1 1 ( ) n d d ki i k k i J a = = = + − e m e x