19
基于熵的判据
熵（Entropy）:
Y
Ent(D) pk log2 pk k 1 样本类别确定： ������������ = 1, ������������������ = 0; 样本类别不确定： ������������ < 1, ������������������ > 0;
目标函数
m
min
( yi T xi )2 1
i 1
易获得稀疏解， 是一种嵌入式 特征选择方法
L1 norm
特征选择+特征提取
并行的思路
L1范数比L2范数更易获得稀疏解
m
min
( yi
i 1
T xi )2


2 2
L2 norm
33
嵌入式
34
总结
• 背景 • 特征子集搜索方法
14
基于距离的判据
• 搜索一个特征子集，我们希望 : 样本类内的距离尽可能小 样本类间距离尽可能大
Far away…
Far away…
Class1
Class2
15
基于距离的判据
样本均值向量:
ui

1 Ni
xDi
x,
(i 1, 2)
协方差矩阵:
Si (x ui )(x ui )T , (i 1, 2)
23Βιβλιοθήκη 基于熵的判据香农熵（Shannon Entropy）:
������
������ ������ = − ෍ ������(������������|������) log2 ������(������������|������)
������=1
平方熵（Square Entropy）:
���������2��� = ������ ������1 ������ , ������ ������2 ������ , … ������ ������������ ������
基于距离的类可区分性判据 Distance based separation criterion
基于概率分布的类可区分性判据 Probability distributions based separation criterion
基于熵的类可区分性判据 Entropy based separation criterion
8
特征选择
特征：对象所具有的属性 例如: 西瓜{颜色, 根蒂, 敲声, 纹理, 触感…}
根蒂: 蜷缩 敲声: 清脆 纹理: 清晰
有经验瓜农判断：
恩，这是一个好瓜
9
特征选择
相关特征: 和任务相关的属性，且属性之间互相不相关 比如：{根蒂、敲声、纹理} 好而不同
无关特征: 和任务不相关的属性 比如：{颜色、触感…}
空间 • 特征提取是特征工程的一种
37
特征提取的方法
• 线性方法
• Principal Component Analysis (PCA)[Pearson , 1901] • Linear Discriminant Analysis (LDA) [Ronald Fisher , 1936]
[Belhumeur, 1996]
特征选择：从所有的已知属性中选择出和任务相关，且相 互之间不相关的属性
10
特征选择
一般来说，特征选择步骤如下，主要包括子集搜索和子集评 估
原始特 征集合
子集搜索
子集评估
分类器
否
是否满足
是
停止条件
11
目录
• 背景 • 特征选择简介 • 特征子集搜索与子集评估 • 特征提取 • 特征选择与特征提取讨论 • 总结
25
特征选择
过滤式 ：特征选择发生在训练过程之前 （无训练过程）
代表性方法: Relief
包裹式：直接将分类器的性能作为特征选择中的子集评估方法 （无训练过程）
代表性方法: LVW（拉斯维加斯算法）
嵌入式：特征选择和学习器训练同时嵌入到一个优化过程中，特 征选择在学习器训练过程中完成（有训练过程）
分类错误率:
������
=
1
−
1 ������
=
������−1 ������
������������ ������ ������������ ������ = 1 , ������ ������������ ������ = 0, ������ ≠ ������
分类错误率: ������ = 0
熵值可以度量后验概率的分布!
• 非线性方法
• Multidimensional Scaling (MDS) [Torgerson, W.S. et al. ,1958] • Kernel principal component analysis (KPCA) [Scholkopf et al., 1998] • Principal Curves [Hastie, 1989] • Self-Organizing Feature Map (SOM) [Kohonen et al., 1995] • Generative topographic map (GTM) [Bishop et al., 1998] • Manifold Learning：Isomap,LLE,LE……. • ......
类 ������ ������ ������1 条 件 概 率 密 度
分离 ������ ������ ������2
x
Class1
Class2
类条件概率密度曲线
������ ������ ������1
类
条 件
������ ������ ������2
概 率
Class1
密
度
Class2
根据搜索到的特征子集，分析一下两 个类的类条件概率密度曲线分布情况
m
min
( yi
i 1
T xi )2

1
L1 norm
易获得稀疏解， 是一种嵌入式 特征选择方法
26
过滤式
过滤式 ：特征选择发生在训练过程之前
Relief (Relevant Features) [Kira and Rendell, 1992] • 给定‘相关统计量’，度量特征的重要性 • 设置一个阈值t, 如果某一个特征的相关统计量大于阈
其他子集搜索方法：
/heaad/archive/2011/01/02/1924088.html
How Question:
to evaluate the searched feature?
13
子集评估
类可区分性判据(Separation Criterion) 用于评估特征子集的类别 区分性的能力
• 特征提取： 将原始特征通过线性或者非线性组合的方式转化为新的特征表示 For example:������ = σ������������=1 ������������������������ 作用: 降维 特征优化 提升分类性能
7
目录
• 背景 • 特征选择简介 • 特征子集搜索与子集评估 • 特征提取 • 特征选择与特征提取讨论 • 总结
18
基于概率密度的判据
• 满足以上条件的任何函数都可以作为基于概率密 度的类可区分性判据的距离度量!!!
• 概率密度距离的常用函数: 1) 巴氏距离（Bhattacharyya distance） 2) Chernoff 界限（Chernoff bound ） 3) 散度（Divergence）
参考书: 边肇祺《模式识别》第8章
西瓜特征
分类器
(SVM,Beyes,KNN….)
好瓜 坏瓜
原始特征: 西瓜{颜色, 根蒂, 敲声, 纹理, 触感…}
以往研究，是特征固定，研究重点是分类器
4
背景
举例: 对于一个有经验的瓜农，怎么判断西瓜是好还是坏？
特征
结果
颜色：绿色 根蒂：蜷缩 ① 敲声：清脆 纹理：清晰 触感：光滑
好瓜
根蒂：蜷缩 ② 敲声：清脆
值t, 那么就将其加入特征子集 • 特征子集的重要性等于特征子集相关统计量的和
27
包裹式
包裹式：直接将分类器的性能作为特征选择中的子集评 估方法 LVW(Las Vegas Wrapper) 是一种典型的包裹式算法 1）在候选特征集中自由选择特征子集 2）在特征子集表示的数据集上，运行学习算法 3）用分类的错误率来评估特征子集的好坏
12
子集搜索
1) 前向搜索: 依次在候选集合中增加相关特征
Optimal feature:
⇒ ������2 ⟹ ������2, ������4 … . .
子集评估
2) 后向搜索: 在候选集合中，依次去除不相关特征
Optimal feature:
These strategies are greedy, only consider optimization of this round 这些方法是贪心的策略，因为是在上一轮的基础上考虑本轮最优， 所以不一定得到最优特征组合
前向搜索，后向搜索，双向搜索
• 特征子集评估方法
基于距离的判据，基于概率密度的判据，基于熵的判据
• 特征选择的策略
过滤式，包裹式，嵌入式
35
目录
• 背景 • 特征选择介绍 • 特征子集搜索与子集评估 • 特征提取 • 特征选择与特征提取讨论 • 总结
36
特征提取
• 特征提取不同于特征选择 • 特征提取是将原始特征通过组合转换到新的特征
纹理：清晰
好瓜
③ 颜色：绿色
① 相比 ②，部分特征冗余，需要选择特征
5
背景
特征: {根蒂，敲声，