粗等价类融合禁忌搜索的最小约简完备算法  

Complete minimum attribute reduction algorithm using fusion of rough equivalence class and tabu search

作　　者：赵洁[1] 张恺航 董振宁[1] 华德义 徐克付[2] ZHAO Jie ZHANG Kaihang DONG Zhenning HUA Deyi XU Kefu(Department of Management Science and Engineering, School of Management, Guangdong University of Technology, Guangzhou 510520, China Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China)

机构地区：[1]广东工业大学管理学院管科系,广州510520 [2]中国科学院信息工程研究所,北京100093

出　　处：《系统工程理论与实践》2017年第7期1867-1883,共17页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71401045;71571052);广东省自然科学基金(2016A030310300);广东省自然科学基金:粗糙集和DS证据推理混合模型下抗信誉共谋攻击的行为信任研究~~

摘　　要：提出粗等价类融合禁忌搜索的最小约简完备算法.首先用全局等价类替换元组作为基本计算单位,给出3类粗等价类定义,结合0-粗等价类在约简的渐增式计算中递减至空的性质,推导出求正区域的等价方法,并设计求解中双向缩减计算域的优化策略,从而提供快速求初始解、验证解等基础算法;然后面向约简特性设计禁忌搜索下的多种策略,包括双向邻域搜索、藐视准则、有限随机搜索、有限解检验等,最后给出高效的最小约简完备算法.用UCI中20个决策表、KDDCup海量数据集从多个性能指标进行验证,实验结果证明粗等价类理论和禁忌搜索从双方面保证本文算法的完备和高效性,大多数情况下可有效求得最小约简,并在跳出局部最优解、收敛速度和处理海量数据效率等方面优于现有算法.A complete minimum attribute reduction algorithm based on fusion of rough equivalence class and tabu search is proposed. Firstly, three types of rough equivalence classes （RECs） are proposed based on the smallest computational granularity of global equivalences, 0-REC will be reduced to empty set in the incremental computation of reduction, through which an equal method to substitute positive region calculation is inferred. Also the two-directional diminishing strategies for reducing computation regions are designed, then basic algorithms are proposed such as the quick initial solution computation and limited solution certification. Then multiple tabu search strategies facing properties of attribute reduction are designed, including bidirectional neighbor search, aspiration criterion, limited random searching, limited validation. At last the complete minimum attribute reduction algorithm is proposed. 20 decision sets of UCI, KDDCup massive data sets are used to verify our algorithm using several performance measures, and the results prove that the theory of REC and tabu search can make the algorithm complete and efficient, in most conditions, the algorithm of this paper is able to acquire the minimum attribute reduction and superior to current algorithms in escaping from local optimum, rate of convergence and handling massive data.

关 键 词：最小约简 粗等价类 禁忌搜索 完备算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]