·448· 智能系统学报 第4卷 a)将特征空间(x:)等分为L段，每段为6，其 整个搜索都是相当重要的.如果选择一个很好的搜 中LK; 索起点可以使得整个搜索更容易，也更能得到具有 b)重复合并相邻的一致性区域6，和61以产 判别性的特征.本文枚举了许多粒空间的Haar特征 生一个一致性区域集{8}1=1，…，L'; (图1)，也就是每个单元都是正方形而不是矩形的 c)如果L'>K,重复合并相邻的区域8-1， Haar特征，利用式(11)中定义的fitness函数选择具 8'1,,8'-1,其中l°=arg minlp(l,d1）-p(l,2)l, 有较大F的一部分构成开集.这样，判别性不好 如果L'<K',通过最大化交互信息增益，重复分离 的特征在第一次选择中就首先就被滤除了· 段6'，l°=arg min[min(p(l,w1)-p(l,2)]; d)对每一段6，计算 W:=P((x:)∈6，y:=c)= 0:,c=±1； 图1用于初始化开集的一些粒空间的Haar特征 i0(xi)E8kYi=e Fig.1 Some Haar-like features in granular space for the e)设置每一段的输出： initialization of open list H0(x:)∈6a,h(x:)= fitness函数是用来选择更具判别性的粒特征， 1n(+）,k=1,…,k 用于后续扩展以得到更好的特征.它在整个启发式 2T吧+e1 搜索过程至关重要.为了提高LUT型弱分类的分类 式中：8是一很小的正常数以防止分母为0. 性能，采用具有最小贝叶斯错误且更少粒的特征.因 3)输出： 为这样的特征更具判别性，而且具有更小的计算复 输出一个UT弱分类器： 杂性和结构风险.因而，启发式搜索倾向于寻找具有 Am)=贷p(✉. 更小贝叶斯错误和更少粒数的特征.粒特征的判别 性被定义为 1,u∈δk 式中：B(u)={ ,k=1,…,K D(0)=1-E(0). (10) 0,u华6 式中：E(9)是整个贝叶斯决策的贝叶斯错误上界。 1.3启发式搜索选择粒特征 因而一个具有更高D(:)的粒更具判别性.为整合 可以看出在1.1中定义的特征数目相当庞大， 特征中粒数目的影响，采用如下经验公式： 通过传统方法搜索整个特征空间几乎不可能.本文 Fns=D(0:)-0.001c. (11) 采用一种启发式搜索的方法来解决这个问题，它能 式中：c是粒特征的粒子数目，具有更高F的粒 选择有效而简洁的特征用于训练.启发式搜索是人 工智能领域一种经典的高效寻优算法[.在搜索过 特征更好. 为扩展一个选择的粒特征，引入3个不同的算 程中有2个集合，开集中的元素用于以后的扩展，闭 子：加、减、替换16]，分别是在该特征中加入一个新 集用于保留那些已经被扩展了的元素以避免重复扩 的粒，删除一个已有的粒，以及用它的相邻粒替换已 展.其具体算法如下： 有的粒.这样，产生一个新的特征集⊙·，可能包含 1)初始化： 更好的特征.表示待扩展的特征为0°，它包含的粒 开集0={81,02，…，0n},闭集C=0. 集合为p,P内的粒以及它相应的系数为P和aa,不 2)循环： a)从O中选择一个最优的特征0·： 在p中的粒以及相应的系数为Pu和aut,P内的粒 P的相邻粒为N(Pn),这3个算子可以表示为 0°=arg maxeeo(Fime（0)）; 8。={0。l0。=0°+ouP}, b)0=0-{0°}，C=CU{0*}; Pt生p,amt={-1,+1; (12)） c)扩展θ以构建一个新的特征集⊙·； 8a={0al0a=0°-4Pa},Pa∈p;(13)） d)0=0u{0·-C}. =10,1 0 =0*-ainPin aoup out, 3)输出： Pa∈P,Pt∈N(Pn),at=(-1,+1).(14) 构建的特征集O=OUC. 这样，扩展算子能构建一个新的稀疏特征集合， 开集的初始化是启发式搜索的第一步，这对于 为减少计算量，仅选择每个集合中最好的一个加人 扩展特征集中：