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

提出粗等价类融合禁忌搜索的最小约简完备算法.首先用全局等价类替换元组作为基本计算单位,给出3类粗等价类定义,结合0-粗等价类在约简的渐增式计算中递减至空的性质,推导出求正区域的等价方法,并设计求解中双向缩减计算域的优化策略,从而提供快速求初始解、验证解等基础算法;然后面向约简特性设计禁忌搜索下的多种策略,包括双向邻域搜索、藐视准则、有限随机搜索、有限解检验等,最后给出高效的最小约简完备算法.用UCI中20个决策表、KDDCup海量数据集从多个性能指标进行验证,实验结果证明粗等价类理论和禁忌搜索从双方面保证本文算法的完备和高效性,大多数情况下可有效求得最小约简,并在跳出局部最优解、收敛速度和处理海量数据效率等方面优于现有算法.

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

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.