Tabu搜索算法


步骤 5 如果 x 的性能比 xg 的性能好，则令 xg x ； 步骤 6 如果Tabu表的长度等于规定长度，则删去表 中最早搜索过的解； 步骤 7 令 T T {x} ； xg为最终解， 步骤 8 若满足终止条件，则算法结束， 否则，令 i i 1 ，转2。
特征选择——分支定界法

分支定界法：若某一支已经搜索到叶节点，例 如，右侧的第一支的叶节点，该节点的特征组 为x*=(x1,x2)T，计算相应的准则函数值并将其 作为界：B=J(x*)。这时，树中的某个节点， 例如节点A，节点所表示的特征组为(x1,x4,x5)T； 计算出节点A相应的准则函数值JA，若JA≤ B， 则节点A以下各点都不必计算，这是由于准则 函数的单调性所确定的。
特征选择

需要解决的问题


如何确定选择的标准（前面学习过的类别可 分性准则）； 需要找到一个比较好的算法，以便在较短的 时间内找出一组最优的特征。
特征选择

两种最为显见的选择方法：单独选择法 与穷举法。

单独选择法指的是把n个特征单独使用时的 可分性准则都计算出，从大到小排序，如：
J ( x1 ) J ( x2 ) J ( xm ) J ( xn )
i 1 1
c)
J ( Xi x ) J ( Xi x )
i 1 2
J ( Xi x )
i 1 qi
J ( Xi x )
i 1 ri
从 i 中去掉 Qi ，并修改 ri
i 1 i Qi
ri 1 ri qi
特征选择——分支定界法

许多特征选择算法力求解决搜索 问题，经典算法有：


分支定界法 顺序后退法 顺序前进法 模拟退火法 Tabu搜索法 遗传算法
Ch8 特征的选择与提取之特征选择


特征选择的任务：从n个特征中选择出 m(m<n)个最有效的特征。 方法：根据专家的知识挑选那些对分类 最有效的、最有影响的特征；用数学的 方法进行筛选、比较找出对分类最有影 响的特征。
Tabu搜索算法

Tabu(禁忌)搜索算法


算法的基本思想：一个解的某个“邻域”中一般存 在性能更好的解。因此，Tabu搜索算法仅仅在一些 解的邻域中进行。为了避免搜索过程的重复，从而 能够搜索更大的解空间，因此该算法要求记录近期 的搜索过的解。 使用一个表，Tabu表，记录这一搜索过程的解。 如果一个解在Tabu表中，说明该解在近期被访问过。 一旦被收入Tabu表中，在某个时间段内禁止访问该 解。
特征选择——分支定界法

在下面的算法中，显然 i 和 X i 是已知的。 算法是从0级开始的，并从右边的第一支开始 计算，D是原始特征的数目，d是所要选择出 的特征数目，J是可分性准则函数，r0=D, 0 是全部特征集合， X0 0 。
特征选择——分支定界法
算法步骤

步骤1 a) 利用公式 qi ri (D d i 1) 计算 qi ； b) 根据下式计算 Qi ：



该算法考虑了所选特征与已入选特征之间的相关性。一般 来说，比前面所提出的单独选择方法要好。 缺点：对于已经入选的特征无法删除或替换。 注意：上述的SFS算法每次增加一个特征，实际上可以每 次增加多(r)个特征。
特征选择——次优搜索算法

顺序后退选择法(Sequential Backward Selection,SBS)
J ( X k x1 ) J ( X k x2 )
J ( X k xDk )
则下一步的特征组选为
X k 1 X k x1 注意：算法开始时 X 0 , k d 时算法结束
特征选择——次优搜索算法

顺序前进法(Sequential Forward Selection, SFS)


该算法是一种自上而下的方法。从全体特征中每次舍弃一个 特征，所删除的特征应该使得仍然保留特征组的J值最大。 假设已删除了k个特征，得到特征组 X k ，将 X k 中的各个特 j 1, 2, , D k 按照下述的J值进行排序： 征 xj ，
J ( X k x1 ) J ( X k x2 )
Tabu搜索算法

Tabu(禁忌)搜索算法的基本框架 步骤 1 令迭代步数 i 0 ，Tabu 表为 T ，给 出初始解为x，并令最优解 xg x ；



步骤 2 从x的邻域中选择一定数量的解构成候选集 合N(x)； 步骤 3 若N(x)＝Φ ，则转2，否则从N(x)中找出最 优解x’； 步骤 4 若 x ' T ，并且 x ' 不满足激活条件，则令 N ( x) N ( x) {x '} ，转3，否则，令 x x ' 。
Tabu搜索算法

Tabu(禁忌)搜索算法的分析pp:208
遗传算法(进化计算)

遗传算法(进化计算)
遗传算法主要是从达尔文的生物进化论得到 启示。生物在漫长的进化过程中，经过遗传 和变异，按照“物竞天泽，适者生存”这一 规则演变，逐渐从最简单的低级生物发展到 复杂的高级生物。基于这种思想，发展了用 于优化的遗传算法。
d
特征选择——分支定界法



分支定界法：是一种自上而下的启发式搜索算法，具 有回溯功能，可使所有可能的特征组合都被考虑到。 由于合理的组织了搜索过程，使得有可能不必计算某 些组合，而又不影响得到最优的结果。 分支定界法的必备条件：所使用的准则函数必须是具 有单调性的。即，从D个特征中选择d个特征组成d维 特征向量，再由这d个特征中选择k个特征组成k维向量， 对应的准则函数应满足： D>d>k J D Jd Jk
遗传算法

遗传算法发展的简要回顾




1950s，将进化原理应用于计算机科学的初步努力。 50年代末到60年代初，Holland应用模拟遗传算子研究适应性。 1967年，Bagley的论文中首次提出了遗传算法这一术语。 1975年，Holland的经典著作《自然和人工系统中的适应性》 出版，系统阐述了遗传算法的基本理论和方法。 1975年，DeJong的博士论文《遗传自适应系统的行为分析》， 将Holland的模式理论与他的计算试验结合起来。 1983年，Holland的学生Goldberg将遗传算法应用于管道煤气 系统的优化，取得了很好的效果。
使得J较大的前m个特征作为选择结果，但是 这样所得到的m个特征一般未必时最好的。
特征选择

穷举法：
从D个特征中选择d个，所有可能的组合数为 CD， 10 如D=20, d=10，这时有 C20 184756 种特征的 组合方法。把184756种特征组合的可分性准则 函数全部计算出来，然后看哪一种特征组合的准 则函数值最大，我们就应该选择这种组合的前10 个特征。
步骤 4 回溯 置 i i 1; ri ri 1; i i 1; 若 i 1，则终止算法； i 1 否则，把 xqi 放入到当前的特征集，即

i 1 X i X i 1 xqi 置 i 1，转向步骤3。
特征选择——分支定界法
算法步骤

步骤 5 修改界值 置 B J ( X Dd )，把X D d 作为当前最好的特 征组 X d ，置 l qi ，转向步骤3。
10.2 特征选择



特征选择是从原始特征中挑选出一些最 有代表性，分类性能最好的特征来。 每个特征的状态是离散的—选与不选 从N个特征中选取k个，共 种组合。若 不限定个数，则共2N种。－NP 问题 这是一个典型的组合优化问题
特征选择的方法大体可分两大类


Filter方法：不考虑所使用的学习算法。通常给 出一个独立于分类器的指标μ来评价所选择的 特征子集S，然后在所有可能的特征子集中搜 索出使得μ最大的特征子集作为最优特征子集。 Wrapper方法：将特征选择和分类器结合在一 起，即特征子集的好坏标准是由分类器决定的， 在学习过程中表现优异的的特征子集会被选中。
特征选择——分支定界法

分支定界法：整个搜索过程可以使用树来表示， 下图表示一个从5个特征中选择2个特征的例子， 节点上的标号表示去掉的特征序号。每一级在 上一级的基础上再去掉一个特征。级数正好是 已经去掉的特征数。
特征选择——分支定界法
0
1 2 3 4
2 A 3
3 4 4
3
3
5
4
5
5 5
5
5
5
特征选择——分支定界法
分析

优点：该算法可以求出最优解。 缺点：在很多情形，该算法的计算量太大， 难以实现。
特征选择——次优搜索算法

单独最优特征组合 顺序前进法 顺序后退法
特征选择——次优搜索算法

单独最优特征组合

最为简单的方法，是计算各个特征单独使用时的准 则函数值，并将其排序，取前d个作为所要选择的 特征。但是，一般为而言即使各特征是单独使用的， 这一结论也不是最优的。要保证所选则的特征的最 优性，必须使得可分性准则函数值满足：
算法步骤

步骤2：检验和后继节点相应的准则函数值是否小于B。 i 1 J ( X x q 0 若 ，则转向步骤4；否则，若 i qi ) B ，则置 l qi ， i i 1 然后转向步骤3，否则从 X 中去掉 xqi ，即
i
X i1 XΒιβλιοθήκη i xi 1 qi若 i 1 D d，则转向步骤5，否则置 i 1 ，然后转向 步骤1。
一种Filter算法: FOCUS