粗等价类双边递减下多次Hash的渐增式求核与约简算法  

Rough equivalence class bilateral-decreasing based incremental core and attribute reduction computation with multiple Hashing

作　　者：赵洁[1] 张恺航 董振宁[1] 徐克付[2] 

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

出　　处：《系统工程理论与实践》2017年第2期504-522,共19页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(71401045;71571052);广东省自然科学基金(2016A030310300)~~

摘　　要：为设计高效约简算法,首先以全局等价类为最小计算单位提出粗等价类概念,证明粗等价类下约简与原信息系统等价;然后深入剖析1,0,-1三类粗等价类的性质,把求正区域等价转化为0-粗等价类双边递减下的渐增式计算,结合1和-1-粗等价类的传递性,设计双边横向删减实体和纵向删减属性的优化规则,可在每一轮增量计算中缩减计算域,基于此设计多次Hash的属性增量划分方法;最后给出新的渐增式快速求核与约简算法,其中求核基于纵向优化规则,可在一次计算中求得多个非核属性,无需遍历全部属性.基于UCI、海量和超高维3类数据集进行多个实验,实验结果证明本文求核与约简算法是高效完备的,在海量数据与超高维数据集下有较大优势.To design an efficient attribution reduction algorithm, firstly, rough equivalence class （REC） is proposed based on the smallest computational unit of global equivalences, REC based reduction is proved to be equivalent to that of the original information system. Then the properties of 1, 0, and -1-RECs are studied, and the positive region computation is converted to the incremental computation of based on bilateral decreasing of 0-REC, integrated with the transitivity of 1 and -1-RECs, principles of optimality are designed to delete entities bilaterally and horizontally and to delete attributes vertically, which can decrease computational domain in each round of computation, base on which the incremental computation method with multiple Hashing is designed; at last, the incremental core and attribute reduction algorithms are proposed. Core computation is based on the vertical principle of optimality, more than one non-core attributes can be obtained in one round computation, and so not all the attributes need traversal. Data sets of UCI, massive and ultra-high dimension are used to verify the algorithms, and the results prove that the algorithms are complete and efficient and have superiority in massive and ultra-high dimensional data sets especially.

关 键 词：粗糙约简 核 粗等价类 多次Hash 

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