张昭琴,徐泰华,鞠恒荣,刘克宇,4,王平心

(江苏科技大学 1.计算机学院;2.理学院,江苏 镇江 212100;3.南通大学 信息科学技术学院,江苏 南通 226019;4.西南交通大学 计算机与人工智能学院,四川 成都 611756)

属性约简[1,2]是粗糙集[3,4]理论研究中的一项核心内容。作为一种有效的特征选择技术[5,6],近年来属性约简已然成为了众多学者关注的焦点,其主要思想是依据不确定性度量评估候选属性,筛选并移除部分属性,最终得到满足给定约束条件的最小属性子集。作为一种数据预处理技术,属性约简既可以对数据进行降维,从而降低后续学习任务的复杂性,又能在一定程度上提升学习器的泛化性能。

目前,大量学者除了根据实际应用需求,对属性约简的结构及形式进行广泛探索,还着眼于设计一些搜索算法,以期能够快速地得到有效的约简结果。一般来说,在兼顾考虑约简求解效率与约简结果有效性的同时,众多学者倾向于使用前向贪心搜索策略。然而需指出的是,该策略需依据给定的度量标准对所有候选属性进行逐一评估,直至满足算法终止条件。这一进程需要迭代地遍历所有的候选属性,才能得出最终的约简结果,因而在属性数量急剧增加的情况下,利用前向贪心搜索进行约简求解将显式地带来较大的时间消耗。

根据上述分析,利用前向贪心搜索求解约简时,时间效率依然可以进一步提升,例如采用一些选择性的策略[7],来达到减少候选属性数量的目的。……