摘要
为设计高效约简算法,首先以全局等价类为最小计算单位提出粗等价类概念,证明粗等价类下约简与原信息系统等价;然后深入剖析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.
出处
《系统工程理论与实践》
EI
CSSCI
CSCD
北大核心
2017年第2期504-522,共19页
Systems Engineering-Theory & Practice
基金
国家自然科学基金(71401045
71571052)
广东省自然科学基金(2016A030310300)~~
关键词
粗糙约简
核
粗等价类
多次Hash
attribute reduction using rough set
core
rough equivalence class
multiple Hashing