基于VNS及马尔科夫毯分组的高维特征选择算法

关键词:高维特征选择,马尔科夫毯,变邻域搜索算法,特征分组

期刊:Information Science (一区)

①马尔科夫毯:

把一个随机变量全集U分成互斥的三部分,变量X以及集合A和B,三个子集没有交集,并集即为全集U;如果说给定集合A时,变量X与集合B没有任何关系,则称集合A为变量X的马尔可夫毯。在式(2-16)中,集合MB即为我说的集合A,{U-MB-{X}}即为我说的集合B,符号“⊥”表示“独立”,符号“|”表示在给定xx条件下,因此可读为“在给定集合MB时,变量X与{U-MB-{X}}独立”。

打个比方说,全集U是整个社会,X是你个人,MB就是你生活圈子里的人。按照哲学的说法,万事万物都是有联系的;但是,你并不会与社会里的所有人有什么关系,而是通过你的生活圈子和他们有间接的关系,即当给定你的生活圈子以后,你和社会其余的人是没啥关系的(独立的)。

②对称不确定性 (Symmetrical Uncertainty)

对每一个特征fi , 计算其对称不确定性,其中, IG(c l fi)表示类别c 与特征Ji 之间的信息增益, H(c)和H(fi) 分别表示类别c与特征Fi 的信息熵(entropy) 给定一个阔值γ, 如SU(fi,c) ≥γ,则fi对于类别c 来说是强相关特征,应该被保留,反之fi应该被去除。

③近似马尔科夫毯(Approximate Markov Blankets)

对于两个特征Xi和Xj(i≠j),Xj是Xi的近似马尔科夫毯的条件为:SU(Xj,c)>=SU(Xi,c),

且SU(Xi,Xj)≥SU(Xi,c)

一个特征Xi 为主元素,当且仅当没有元素是Xi 的近似马尔科夫毯。

④主元素组(Predominant group)生成算法——GPGG

STEP1冗余性分析. 对每一个特征Xi , 根据其对称不确定性给定一个阈值α, 如SU(Xi,y) > α ,则且

对于类别y来说是强相关特征,放入集合L中。

STEP2根据SU的值进行降序排序。

STEP3利用近似马尔科夫毯方法(判断每个元素是否存在马尔科夫毯)从L中寻找主元素放到集合g中。

⑤变邻域搜索算法(Variable Neighborhood Search,VNS)

变邻域搜索算法的主要思想是:采用多个不同的邻域进行系统搜索。首先采用最小的邻域搜索,当无法改进解时,则切换到稍大一点的邻域。如果能继续改进解,则退回到最小的邻域,否则继续切换到更大的邻域。

⑥PGVNS算法(PredominantGroupbasedVariableNeighborhoodSearch)

为了将VNS算法应用到高维数据集上,作者提出了基于VNS主元素组的特征选择方法,
首先利用GPGG算法产生主元素组作为初始的解,再 利用shaking method选出新的解集,如此迭代最终获得最好的解集。

原文:García-Torres M, Gómez-Vela F, Melián-Batista B, et al. High-dimensional feature selection via feature grouping: A Variable Neighborhood Search approach[J]. Information Sciences, 2016, 326(C):102-118.

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注