近似马尔科夫毯混合式特征选择

殷柯欣， 谢爱锋， 翟峻仁

(长春工业大学 计算机科学与工程学院，吉林 长春 130012)

0 引 言

特征选择[1-2]作为一种数据预处理技术被广泛应用于机器学习、模式识别和数据挖掘等领域。特征选择过程可以分为子集生成、子集评估、停止准则和验证四部分。子集生成是一个搜索过程，根据搜索策略生成特征子集，然后利用评价准则对特征子集进行评估。当特征子集的条件满足停止准则时，输出当前的特征子集，并对其进行验证。

在生成特征子集的过程中，根据特征子集的搜索方式可将搜索策略[3-4]分为全局搜索、序列搜索和随机搜索。全局搜索，又名指数搜索，需要评估的特征子集数量随着特征个数呈指数增加。这种方法虽然能够获得全局最优解，但由于计算量大、花费时间长，在高维数据集中是不适用的。全局搜索算法有穷举搜索法、分支定界法。随机搜索策略随机地选取特征，避免了算法陷入局部最优，能够获得近似最优解。常见的随机搜索算法有遗传算法(GA)、模拟退火算法(SA)等。与全局搜索和随机搜索相比，序列搜索的时间复杂度最低。序列选择策略从空集(全集)开始，然后添加特征(移除特征)，直到获得使准则函数最大化的特征子集。依据序列搜索策略已经开发了多个高性能的搜索算法。首先是序列前向选择算法(Sequential Forward Selection，SFS)和序列后向选择算法(Sequential Backward Selection，SBS)[5]。

SFS算法从空集开始，每次选择一个使准则函数最大的特征加入到已选特征子集中。而SBS算法与之相反，它从全集开始，每次删除一个对准则函数贡献最小的特征。SFS算法计算量小，但没有充分考虑到特征之间的联系[6]，即最优的单个特征组成的集合不一定是最优的特征子集。相对而言，SBS算法虽然计算量大，但其充分考虑了特征之间的联系，算法性能优于SFS算法。但是，SBS算法和SFS算法本身都存在“嵌套效应(nesting effect)[7]”。“嵌套效应”意味着SFS算法选中的特征以后不能丢弃，SBS算法丢弃的特征以后不能再选择。这导致SFS和SBS只能获得局部最优解。

广义序列前向选择算法(Generalized Sequential Forward Selection，GSFS)和广义序列后向选择算法(Generalized Sequential Backward Selection，GSBS)分别是SFS和SBS的加速算法。GSFS算法从空集开始，根据准则函数每次向已选特征集合中加入一定数量的特征。GSFS算法改进了SFS在特征关系上的不足，但增大了计算开销。与GSFS算法类似，GSBS算法根据准则函数，每一次删除一定个数的特征。GSBS算法速度相对较快，但是过快地进行特征删除，会导致重要特征的丢失，以至于无法找到最佳特征子集。无论是GSFS还是GSBS依旧存在“嵌套效应”。为了解决上述算法中存在的“嵌套效应”，提出了Plus-L-Minus-r(l-r)[8]的方法，即在每次循环中添加L个特征，删除r个特征，直到获得期望的特征子集。这种方法的主要缺点是没有理论上的方法来预测L和r的值，以获得最佳的特征集。与上述改进相比，最值得一提的改进算法就是序列浮动搜索[9]：序列前向浮动搜索算法(Sequential Forward Floating Selection，SFFS)和序列后向浮动搜索算法(Sequential Backward Floating Selection，SBFS)。

SFFS(SBFS)算法灵活地改进了Plus-L-Minus-r方法，使L和r的大小动态化不是固定值。在SFFS(SBFS)算法的每一轮循环中删除(添加)的特征个数是不同的,这是一种非常适用的改良。由于SFFS(SBFS)算法在一轮循环中只添加(删除)一个特征，这意味着SFFS(SBFS)算法所选取的特征子集中可能会包含两个高度相关的特征。并且在搜索过程中，SBFS算法和SFFS算法偶尔会偏好较差的特征子集，特别是SFFS算法。为了解决序列浮动搜索存在的问题，一种自适应的浮动搜索算法[10]被提出：自适应序列前向浮动选择(Adaptive Sequential Forward Floating Search，ASFFS)和自适应序列后向浮动选择(Adaptive Sequential Backward Floating Search，ASBFS)。由于这两种新的自适应浮动搜索方法比经典的浮动搜索更彻底地搜索，它们有可能找到更接近最优解的解，当然是以更长的计算时间为代价。

改进的正向浮动选择(Improved Forward Floating Selection，IFFS)[11]是对SFFS算法精度的一种改进，它在SFFS算法的回溯步骤之后增加额外的步骤，用新的更好的特征代替弱特征来形成当前子集。与SFFS相比，IFFS算法依旧增加了计算时间。

综上，上述所有SBS、SFS的改进算法在寻求算法最优解时，增加了时间耗费，以时间为代价换取高性能的特征子集。并且上述算法采用不同的特征选择方式(包装式或过滤式)，其时间复杂度、特征子集的性能是不同的。过滤式(filter)选择算法效率高、普适性强，但特征子集性能相对较差，因为特征子集之间存在冗余且所选特征子集不一定是最优特征子集。与过滤式选择算法相比，包装式(wrapper)特征选择算法选择出的特征子集性能较好，但时间复杂度高，不适合高维数据集。

针对以上存在的问题，文中提出基于近似马尔科夫毯[12-13]混合式[14]特征选择算法Hybrid Sequential Backward Selection Algorithm(HSBS算法)。该算法将包装式和过滤式有机结合，在保证时效的前提下，提高了特征子集的性能。所提算法HSBS框架如图1所示。

图1 混合式特征选择框架

其中，HSBS包括两个阶段：

1)利用近似马尔科夫毯算法对原始特征集合进行去冗余，输出精简特征子集；

2)使用SBS算法对精简特征子集进行选择，选出最佳特征子集。

实验结果表明，与SBS算法相比，HSBS算法所选的特征子集数平均减少9.0个，平均时间耗费降低约70%，成功克服了SBS算法在高维数据集上耗费时间大的问题。同时，混合式选择适用于高维数据集，克服了包装式方法在高维数据集不适用的缺陷。

1 背景知识

1.1 SBS算法

SBS算法是一种自上而下的搜索方法，从原始特征集开始搜索，每次从特征子集中删掉一个使评价函数达到最优的特征。SBS算法可以描述为：设原始特征集合为S,假设有一个含有n个特征的特征子集Xn，Xn是S的子集，对于Xn的每一个特征fi，计算其准则函数

Fi=J(Xn-fi)，

选择使Fi最大的那个特征，并把它从Xn中删除。SBS算法将分类正确率作为评价准则。

1.2 互信息

互信息(Mutual Information)[15]是信息论里一种很实用的信息度量，是一个随机变量中包含的关于另一个随机变量的信息量。两个随机变量X和Y的互信息可以定义为

(1)

式中：p(x),p(y)——分别为随机变量X和Y的边缘概率密度;

p(x,y)——联合概率密度。

1.3 相关性、冗余性与近似马尔科夫毯

1.3.1 相关性

特征的相关性[16-18]指的是特征与类标签之间的关系，特征与类标签的关系越紧密，特征的相关性越大。根据特征与类标签的相关度，特征被分为无关特征、弱相关特征和强相关特征。假设有一个特征集合S,Xi是S中的一个特征，

Si=S-{Xi},

式中：C——类标签;

I(·)——互信息。

如果特征Xi是强相关特征，需要满足

I(C|Xi,Si)≠I(C|Si)，

表明特征Xi的重要性，特征Xi有无直接影响类标签C发生的概率。

如果特征Xi是弱相关特征，需要满足

I(C|Xi,Si)=I(C|Si)，

∃Sj⊂Si，

I(C|Xi,Sj)≠I(C|Sj)，

表示特征Xi可以被其他特征所取代，取代后就变成无关特征。

如果特征Xi是无关特征，需要满足

∀Sj⊂Si,

I(C|Xi,Sj)=I(C|Sj)，

表示特征Xi对于类标签C毫无贡献。

1.3.2 冗余性与马尔科夫毯

马尔科夫毯[19]定义：特征Xj属于特征集合S，S0是S的一个子集，Xj不属于S0。如果S0满足

P(S-S0-Xj,C|Xj,S0)=

P(S-S0-Xj,C|S0)，

则称S0是Xj的马尔科夫毯。

冗余性[20]是指一个特征与其他一个或多个特征对分类任务起到相似的作用。如果特征Xj为弱相关特征且在特征集合S中存在一个马尔科夫毯S0，表明特征Xj是冗余特征。

1.3.3 近似马尔科夫毯

马尔科夫毯方法可以直接删除无关特征和冗余特征，由于马尔科夫毯方法是对所有的特征子集进行遍历搜索，导致马尔科夫毯在高维数据集上的时间复杂度为O(2n)，计算复杂度偏高。为了降低计算复杂度且保留马尔科夫毯的优点，文中引入马尔科夫毯的简化版，近似马尔科夫毯。

近似马尔科夫毯算法同样可以删除特征集合中冗余与不相关的特征，并且时间复杂度为O(n2)，计算复杂度较低[12]。

近似马尔科夫毯定义：对于来自于同一个特征集合的特征Xi和Xj(i≠j)，如果满足

I(Xi;C)>I(Xj;C),

I(Xj;C)

则说明特征Xi是特征Xj的马尔科夫毯，Xj为冗余特征，直接删除。

2 HSBS算法描述

2.1 HSBS特征选择方法

HSBS算法采用混合式特征选择模型，算法流程如图2所示。

图 2 HSBS算法流程

第一层采用filter选择方法，使用基于互信息的近似马尔科夫毯对特征集合进行精简。首先遍历特征集合S中的每一个特征fi，并计算特征fi与类标签C的互信息值I(fi;C)。按照互信息值I(fi;C)的大小对特征集合S进行排序,生成新的特征集合S′。根据近似马尔科夫毯的判断条件，即

I(Xi;C)>I(Xj;C),

I(Xj;C)

删除特征集合S′中冗余和不相关的特征，输出精简特征子集。

第二层wrapper选择方法采用SBS算法，从精简子集中选择出最优特征子集。输入精简特征子集X，利用SBS算法的准则函数逐个将分类效果差的特征从精简子集X中剔除，从而获得最佳特征子集S0。这一层在保证分类精度的同时进一步降低了特征个数。

2.2 HSBS算法伪代码

文中提出的HSBS算法具体步骤如下：

输入：原始特征集合S={f1,f2,…,fn},C为目标类，n为特征个数，d为选定的特征个数；

输出：最优特征子集S0

步骤：

1)X=∅,F=∅,S={f1,f2,…,fn}

2)计算S中每一个特征fi的I(fi;C)，并根据I(fi;C)值，从大到小对S进行排序，得到S′

3)for fiin S′

4)for fjin {S′-fi}

5)if I(fi;C)>I(fj;C)and I(fj;C)

6)S′=S′-{fj}

7)end if

8)end for

9)end for

10)X=S′

11)while len(X)!=d # len(X)表示X的长度

12)for in len(X)

13)x=arg maxJ(X-xi),xi∈X

14)end for

15)X=X-{x}

16)end while

17)S0=X

18)return S0

3 实验结果与分析

3.1 HSBS算法实验

文中实验环境为Inter(R)-Core(TM)i7-1050H,8 G内存，Window10-64 bit操作系统，仿真软件是python3.7 和Jupyter Notebook。

实验选择了UCI通用数据集，涉及医学、工程科学等领域，4个数据集包含不同的样本数、特征数和类别数。

数据集的具体参数描述见表1。

表1 数据集的描述

实验采用KNN分类器和Native Bayes分类器[21]来构造预测模型。

3.2 实验结果分析

在实验过程中，采用10折交叉验证方法，10折交叉验证就是每一次将数据集均分成10份，其中9份作为训练集，1份作为测试集。然后对数据集进行10次实验，用10次测试结果的平均值作为最终的准确率。与SBS算法和SBFS算法进行对比，验证文中算法在保证高分类准确率的前提下，是否降低了计算时间和减少了特征子集中特征的个数。

通过两种分类器分别在4个数据集上的实验数据来比较不同算法的优劣。

经过近似马尔科夫毯去冗余后的精简子集特征个数见表2。

表2 原始数据集与精简子集特征个数比较

由表2可以看出，经过近似马尔科夫毯去冗余后，所选特征子集的个数明显减少。

3种算法在KNN、Native Bayes两种分类器中时间花费、最佳特征子集个数和分类准确率分别见表3和表4。

表3 3种算法在KNN分类器上的时间花费(s)/特征选择数/分类准确率的比较

表4 3种算法在Native Bayes分类器上的时间花费(s)/特征选择数/分类准确率的比较

由表3可以看出,HSBS算法在相同数据集上所花费的时间均小于SBS算法。与 SBS 算法相比,HSBS算法平均时间花费降低约93%；HSBS算法所选出的平均特征子集数比SBS算法少 14个；HSBS算法在4个数据集上的分类准确率均略低于SBS算法,并且HSBS算法的平均分类准确率能达到90%。

由表4可以看出,在4个实验数据集中,HSBS算法花费的时间均低于SBS算法。同时,与SBS算法相比,HSBS算法的平均时间花费降低约77%；在4个数据集上,HSBS算法所选特征数均低于SBS算法,HSBS算法的平均特征子集数比SBS算法少14.5个；在Wdbc数据集中,HSBS算法的分类准确率略高于SBS算法,但在其他3个数据集上,HSBS算法分类准确率均低于SBS算法。虽然HSBS算法的平均分类准确率只有87.9%,但与最高的平均分类准确率相比,仅差3.7%。

从表 3可以看出,与SBFS算法相比,HSBS算法的平均时间花费降低约97.6%,平均特征子集数减少了10个,平均分类准确率降低了2.3%。

从表 4可以看出,与SBFS算法相比,HSBS算法的平均时间花费降低了91.6%,平均特征子集数减少14.25个,平均分类准确率降低了2.6%。

综合表3和表4实验数据分析发现,HSBS算法的平均时间花费仅占SBS算法的10.1%,时间花费降低约90%。与SBFS算法相比,HSBS算法效果更加明显,其时间花费降低约96.9%。HSBS算法的平均特征子集数也远小于SBS算法和SBFS算法。同时,HSBS算法也存在不足之处,它的分类准确率低于SBS算法和SBFS算法,但相差不大。因此,HSBS算法在降低时间花费、减少特征子集个数的同时,亦能保证较高的分类准确率,HSBS算法在高维数据集具有实用性。

4 结 语

提出一种基于近似马尔科夫毯的混合式特征选择算法——HSBS算法。该算法首先利用近似马尔科夫毯删除数据集中冗余和不相关的特征，生成精简特征子集;然后，利用SBS算法对过滤后的精简特征集进行选择，筛选出最佳特征子集。HSBS算法的优势在于，将数据集中冗余和不相关的特征删除后，降低了数据集的特征个数，提高了剩余特征的质量。

HSBS算法在KNN、Native Bayes分类器上均取得了优良的效果，其降低时间花费的优良表现在KNN分类器上尤为突出，同时还表现出较高的分类效果。

因此，HSBS算法在保证较高分类准确率的情况下，能够降低时间花费、减少最优特征子集的个数,它在高维数据集的分类任务中有较强的实用性。