串行搜索的办法
串行搜索办法它又分两个
一个是这个固定的
一个是浮动的
但完全搜索的办法就是穷举法是所有的
这个可能的组合都做到了的
但向量这里它有一些这个相关性的
这个所以我们要去对它做一些搜索对吧
这个地方ok，所以这个是有一个次优的
就是搜索这样的技术
这个第一个是串行的办法
这个，串行又分前向和后向
这个。当然我们先讲一个前向办法
这有一个example
还有一个后向的办法
这也都有一定的exercise
这个又是比较简单一点
还有一个是这个推广的，或者叫
泛化的这样一个是串行的前向的办法
反向办法应该也是已有吧，是不是这样对吧
就是这两，这个其实就是逐渐往里加
还是往里往减，就是滚雪球
还是切西瓜
这两个跟那个有点类似的意思
从方法论角度来讲
自上而下还是自下而上
它这个是引下就是次优的这个办法是吧
就是最优的办法穷举法它那个是最优的
但是说有些时候也不是
有些时候很多时候这个计算很高
这是没有问题的
这个，而且有的时候并不可行的
刚才那前面说过的
这个就是一旦这个特征。其实不用太大
就是中等规模
就刚才说二十几个就就挺吓人的对吧
这个地方ok。当然还可以采用其他
一些计算效率并行计算的又一回事
所以这个我们大概有
这样就是串行前向的办法
泛化的串行
前向的办法。还有一个
串行的这个反向的办法
还有一个泛化的这样一个
串行了这个反向的办法
其实这个就是bp网络的就
反向传播就这个这个应该更早一些
还有就是串行的前向的浮点的办法
浮点的办法就一次不是找一个是找多个
明白我的意思吧
还有那个加进来再减掉的就ok
这个是反向的浮点的办法
就是先加还是先减对吧
就一开始是空集
还是一开始是全集
他是这样过来的
串行搜索这是前面总的说一下
这个方法是或者是逐渐加特征
就是这个特征集是逐渐在生长的
就是一个个往里加的
还是说这个特征集是在一点点减少的
对吧
当然你都是到了一个你
所需要的那个子集的那个尺寸的
然后它要么开始一个空集
就是前向的办法
这个然后后面是一个加进来，对吧
给你看一下，他这个，加特征
然后是one after the other
对吧，这个，还有是开始是一个全集
然后一个个删掉，它也是逐个删除的
这如果翻成中文的话来讲
然后如果是浮动那个办法就是多个
这个，取决于我们开始一个空集
还是一个全集的，这个就是
它是一个前向的办法
还是一个后向的办法，这个ok
这个方法并不是检查
所有的这个可能的子集
所以这个算法并不能
保证得到最优的这个结果
然后分支限界
他说这两个是能得到最优结果对吧
但是我们看到这个分支限界是
有个单调性假设的是吧
这个地方，甚至还有一些改进的办法
所以其实应该说只有穷举法才
真正能得到这个最优解对吧
或者这个然后这个分支限界
其实它得不到满足单调性情况
它是可以得到
所以这个地方可以做一些判断题
而另外这些方法都
受到一个nesting
就是叫雀巢咖啡是吧
是它镶嵌效应
也就是说一旦加进去一旦减掉
没有机会再去修改
就在那个时候那个特征可能不好
但是跟某些组合它可能又是好的
它就没有机会重新选择
就这个地方。其实社会现象就也比较多，对吧
就是生不逢时。这个。特征
这个可加可减的就串行，这个次优办法
并不是这个这个到没有什么。
但是它实现比较简单
然后很快就能产生一个结果
有些时候就是需要产生结果
就来不及等那个最优的对吧
其实很典型一些那个交通调度问题
还有一些事故处理
对吧 你等着计算那个最好的结果
可能很多损失就更大了
还不如赶紧找一个，对吧
所以就是说像什么遗传算法
这样一些蚁群算法这样一些
其实它都不能保证得到最优解
但是它那个次优解呢很多时候
它一般叫满意解
就是还能解决很多问题的这个地方
Okay所以也能体现就是时间
就这个时间就你这个怎么做一个平衡
这个前向的这个办法它
是还有一个对应的推广的办法
这我前面说过了，这我就不再说了
这个每次是要检查这个性能的
就是这个它一次是加一个特征
就这个，它是一个自下而上的办法吧，就逐渐加
开始是一个空集
然后逐渐的再加其他的特征
这个有1个例子我们可以
看总共是先有4个特征
这个然后是希望选2个4个选2个
然后计算一个准则函数，准则函数，从里面选
一个最好的这个自己，然后所有的这个组合
12 13 14计算这个准则函数
他最后是选择13
这个地方ok
如果这个三接着是这个
就是继续的这个就是形成一个三维的
这个就是从这二维里再加一个，对吧这个
ok，然后这个它是根据它整个的重要性
或者根据它的性能，这都是一样的
这个加，这也没有什么
okay，这个 ok
如果这个是这个特征
那就是把它加进来
对吧 这样这样一个做法
这个，然后这个最重要的特征
是跟这个特征集相关的
对吧 就这个，就是假定我要加进来一个的
跟它放到一起去计算它
就计算，再看它。其实就取决于加进来起不起作用
是不是这样一个意思对吧
就这个。然后这个，上面找一个最大的就是说可能把
这个然后最后这一个跟他这个这并不是相关性能的
从这里找这样一个这个地方
所以这个组合是对通这个 Im的这种情况的
这个一般的这个是就是大概这么多情况组合都要考虑
所以这个其实计算起来也是比较大的一个。但
他说这个特征一旦选择就不能够被再丢弃了
就没有二次被他重新那个选掉的机会是吧
所以这个叫nesting
这几个都是
这是有一个example例子
我们大致来看下，会理解更好一点好吧
这个。这个例子它是说这个差别对吧
这个次优的
就是前向的后向还有这个浮动的办法的
这个后面我们才会讲，先做第一个
这是跟这个所谓的穷举法去做一个对比
对吧这个对比，这个
他然后其实其实这个地方他也给出来
就程序化看着一个是黄金
标准或者一个标准答案是吧
这个地方。例子是图像
里面一个纹理分类的例子
就是什么遥感图像那样子
就是这一块是草地
还是沙漠，绿化的好不好
这样一些东西
就林地什么场地
还是这个种植的一些东西吧
这个地方ok。分类分类它是什么
是识别一个重要的应用
所以这个又分过来的
就模式识别可以看作是
人工智能里面一个子的这个方向的
然后它又可以用在图像分类
还有其他的一些
你看它大概是这样一些
它这个是现在数据集的
这个是说地形的地理的terriant
就是那个游戏里的一般使用表示地形的
这是叠加在上面的一些感兴趣区域的
就是选一些区域去计算的
这个地方ok，他选了这么多，两个图像
它有不同的纹理
然后每个纹理有代表
不同的类别的这个地方ok
他总共选了25个25个区域
总共有50个2个类别
各选25个，是吧
这个，这算他样本的数据
我们可以这样来说的
那这些就形成了训练集的
但其实我知道它那个所谓的类别
然后从里边选最好的特征组合的这个地方
但这个特征它是有20个特征
这就是比较实际的是吧
20个特征它包括一阶的统计性
这个就是我们前面讲过的这个均值标准差
还有这个偏度
还有一个峰度的
还有那个16个2阶的这个特征
这是一些纹理
这就是从那个4个共现是吧
这样一个，这是共现，再再加c就共线矩阵
每个取，这是图像里面
能够计算这样一些东西
然后他又有4个角度
就4X4，16对吧
sixteen，对吧
这个地方ok
而对于每个矩阵的这抽取的4
个特征是包括对比度、相关、能量
还有这个同质性
这就是它有些计算方法，先拿过来
我先不管它
我就把这些东西给出来
这是一阶的，这4个是对比度的4个，矩阵的这个。4个
那个共现矩阵的这个对比度计算4个，再4个是这个相关性的
这个。这特征生成了之后
他再去做这两个数据的20个特征
25个样本 它是这样一个意思吧
这个地方ok
然后它在一个二维的
特征库里这个便于可视化
要评价这4个特征选择方法的这样一个
当然我们现在只讲了这么两个，对吧
一个是穷举法，串行前向的
一个办法找两个特征
然后他是其实从句跟这个这个方法来比较
但后现我们后面再跟这个过来
它是放在一起讲
还有个浮动的办法
前向浮动、后向浮动，对
然后这也是要做规一化
0均值1方差
所以这个地方大家可以试一下其他的
规一化方法对它有多大影有没有影响的
接着rank排序是吧
再利用这个标量的特征选择
它应用一个这个是什么
费舍尔判别比，还有个交叉
这个相关的这个在这些一对特征之间
就这个，这是指那个标量的一个办法是吧
你看这个地方当时不太好这个标量
他用这样一些这样一些这个也给出来
就跟他比较 设置这两个是0.2、0.8
就各起的作用，对吧
就是已有的特征跟新加入
这个特征那个之间的那个相关性
各占计算它相关性的一个各占的权重
然后再选择14个这个最高排序的特征
用这个穷举法，你看这个选第三个准则是吧
这个地方ok，要选择最好的两个特征组合
然后再重复这个步骤
就这个，就是再看这几个得的结论
对 一般情况就是很简单
一个就是说这个组合的就是他
前面这个给出来去算
它，就是从计算角度来讲
反向的它好像更有效
但是也不是完全。后面大家也会
有体会。他就是把这些方法放在一起
给出这样一个结论
然后整个他说是加这个这个load进来
这个就没有什么的这个规一化
这也没有什么的
然后这个是，对，规一化的
然后这个是做那个标量选择的
但是它是用一个排序的
费舍尔这个，他也用了这样一个这个
组合的这个其实有点那个向量的味道
因为它计算已有特征跟
后面的特征之间一个相关系数的
它是通过计算那个，再选择这14
这个是做这个排序的
而用穷举法
用这个J3这个准则
这个决定这个最好的两个特征组合
这也是他给出来
这个地方ok。这个地方我们有好几种是吧
散度矩阵，差异
还有巴特沃斯的就有三个
你可以试一下
打印这个结果它就会给出来了
还有其他的，就是前
向的反向的还有浮动的办法吧
这个这些它都给，都给我们做好
就看一下 这后面会提一下这个ok
对，他，你看，他是两个穷举法是1跟6
前向的办法是1跟5
而反向的办法是2跟9
他刚才说那个反向的办法反而好一点的
但这里其实并没有体现出来
就是说他这个结论有时候
在有些地方能体现
有些地方反而体现不出来
后面大家也注意一下
然后浮动的办法是1跟6
这个还是比较明显
或者说有些时候是统计规律的做很多
得出这样一个结论
然后这个就是说这个穷举办法跟这个浮动的
办法这两个最后处理的结果是一致的
这个特征主要是这两个，这个ok
不同的特征组合的就是这个
他说浮动办法是比较好的
但它的成本也要高一点点
但又不像穷举法那么高
就是次优它是说
这个办法受这样一些启发
就是相似的这个串行的办法
就它是一个唯一的好处
就是这个能够纠正一些错误的
这个选择的这个 ok
但这个是要付出一些代价的
就加了一些更多的计算
这个就是浮动的办法。这个是4.83
这个但它里面都包含了这
这是加载两个数据的是吧
这个我就不再做了好吧
这是规一化标量的选择
还有这个合成的办法的这个
这个大家可以看一下中间的结果
然后这14个，对吧，做1个排序的
这个。他其实把这个做一个排序
大家也可以看这个
这个是给他就是他处理完之后的
再做一个，对，这个ok，做一个相关性
这样得到一个判断
你可以去掉这一步
这一步，就是并不去做这件事情
大家直接把或者你把这个命名拿过来
后面你再做看这两个效果
明白我的意思吧
这个大家试一下好吧
我就不在这试
这是穷举法。穷举法这个得到的是1跟6
这个是前向的办法，对吧，得到1跟5
这个。这个用这个就减到前向
所以这个是说特征向量选择
所以其实我也是从这借用过来这个词
然后这是一个前向的办法
这是说你要给出来
你希望从里面选几个特征是吧
当然还有是这个成本函数
就是类的可分离这个度量
当然我们大概前面它这个实现了三种吧
当然还有一些其他的这是一些计算
我们就不再看了
他们也不是太容易对应上
这个我简单过一下好吧
反向办法就是跟那个正好相反
一次删掉一个特征
刚才是加一个特征的
这个所以它这个叫自上而下
就开始的时候是一个全集
逐渐的丢掉丢弃特征
逐个丢弃特征
这样来说好吧
这个。然后他这个也是说一旦
丢弃就不能再被选回来了
但这个是希望能够这样才会更好一点
所以有浮动的办法
所以这个也能看到就是说我们做科研的
时候的一些学会发现问题的就是说
你是要用已有的
方法去试一下发现一些问题的
因为你一开始你也并不知道
或者前人也没有做这个工作
证明这个方法好还是不好是吧
所以我们前面也跟学生说
说老师我这个做不出来怎么办
因为本科生经常也有这种问题吧
就怕做不出来
然后其实你就跟他说就什么容忍失败
什么叫容忍失败和就是这个科研
也就是说你如果能证明这999
种方法都是不可行的
对别人也是有意义的是吧
别人就不用再做这个工作
是这个意思吧
并不是我什么都没做
我没做出来 而是说我这些方法都去做了
分析也好 理论分析也好
数学还是这个实验也好
最后证明这些方法都是不可行的
你要找另外的办法明白一下
这也是有意义的
所以它其实是从这个角度来讲
并不是说我没有做或者胡乱做
而是说你真正做了
但是这个不能解决的
但你能找到一个解决办法就更好一点的
这个地方，但也是你要跟已有的方法做比较的
你不能把已有的方法都不管他
你去弄了一个方法是吧
就究竟跟已有方法比较好还是不好
你也不用不清楚
这也是没有意义的是吧
这个ok
然后这个就是找到那个最差的
把它逐渐去掉对吧
那个是从后面找到最好的
逐渐把它加进来
这个大概是这样一个路子
这也是4个选这个2个的这个对吧
这个也是采用一次去掉1个特征对吧
再去掉一个
然后这个也是它的错误率对吧
这个地方ok，计算它这个特征
这样的一个特征
然后计算这个。再去做计算
这是它里面分，它写的还是很详细的
对 这就是它的计算量
这是有个MATLAB这前面我就没有加
这个。这也是4.83的
就是刚才那个他又加了一个反向的办法
反向的 这个你就那个是不是前面。对，在这
我们看一下
对在这在这就是
我们输入一个反向的办法的
反向的办法，接着输入就是得到这个2跟9
就是这个，是吧。这是它反向的
这跟刚才的一样向量的
反向的，对，这个是属于个数
就是成本函数，这是特征个数的
这个大致看一下
这个它有个exercise
就是你再用不同的4个、8个、10个
、20个去看一下它总共是24个是吧
这个去看一下这些
最后得出来你看一下
这如果是选两个是161529对吧
这个是穷举的前向的后向的这个地方
ok这是选4个的时候
你看一下穷举办法
跟前向办法、跟反向办法，你看这个一都选出来
2跟4也都选出来是吧
这个是五六对吧
这个是9
你看下这几个，这是11，这几个，这几个ok
这是124
你看这个是14、124看来
还是反向这个好一点的
这个好一点
但是前一个就得2个的
时候得出这个结论是吧
这个这是选8个的时候
我们看一下1~5这些几乎都有的
1~5都有 这有两个9的
这有两个14
这三个都有16的
明白我的意思吧，所以其实就是多种办法
其实那个集成学习或者说我们有的时候
就是我们也可以在这上做一些事情
就是说我对已有的分类器对它做一些组合
成串行并行的取交集取这个并集
这个时候也可以做一些事情
明白我的意思吧，也能得出一些有意义的结论
这是10个的时候
你看一直到1~5都有
69这两个有的12这两个有的，这14
这16都有，这有20
这几个，有几个不同
有几个相同，对吧
所以你可以在这里再从中求一下并集
还是交集 再看一下能得出什么结论
这是20个的时候
好像也是你看一下一直
到这时候都选择进来的
一直到20时候
然后还有一些这个叫推广的办法
这我们就简单说一下
其实串行的前向
办法也是加一个特征
这个就加多个特征对吧
多个特征加加多个
对 但这个最近r是取二取三又一回事
这个地方ok。这个当然计算量又大一点
这个地方，就是尽量多的这个组合情况
它这个是放在这里讲
就我们刚才讲一个交叉经验的对吧
就是它也是把特征集分成训练的跟测试的
然后指定这个串行的前向
还是推广的这个这两个推广版本
这两个方法，对吧，这个
然后在每一个阶段他是去做这个评估的吧
这个这个也是是训练集又是分10等分
9等分是做训练的
一等分是做测试的是吧
然后再去训练
这个，然后去测试它
其余的，然后得到一个性能指标的
然后去计算它
从里面找一个最小的对吧
性能应该是最好的一个
最优的一个，对吧，在这个地方
这个地方，它大概是这样的
这是这个，再评估测试集，再用这个
最小测试集，这个地方ok，得出这样一个结论
但还有一个这个反向的推广，好吧。