粗等价粒度下基于多种加速策略的增量式求核算法

Granularity of Rough Equivalence Class Based Incremental Attribute Core Computation Using Multiple Accelerating Strategies Pruning and Multiple Hashing

提出一种全新的渐增式求核算法。首先基于全局等价类提出粗等价类概念并分析其性质,研究粗等价类下的求核与约简;深入研究3类粗等价类与核属性的内在联系,设计粗等价类下判断核属性的等价方法和渐增式求核方法,通过该方法可在一次增量计算中求得多个非核属性,从而设计双向剪枝策略;可从属性和实体双方面缩减计算域,无需遍历全部属性和实体,在无核情况下,剪枝策略仍然有效。设计多次Hash的属性增量划分算法来完成上述增量式计算,基于此给出完整的渐增式求核算法。最后用UCI中20个决策表及海量、超高维3类数据集从多个角度进行验证,实验结果证明了所提算法的有效性和高效性,其尤其适用于大型决策表,大多数情况下优于现有算法。算法可进一步作为新型约简和优化算法的基础。

A new incremental core computation algorithm was proposed. Firstly, rough equivalence class （REC） was proposed based on the smallest computational granularity of global equivalences, the character of REC was analyzed and core and reduction computation under REC was studied. Then relationship of core attributes and REC were studied and then an equal method of judging core attribution and incremental core computation method based on 0-REC were de signed, through which multiple non-core attributions can be gained in one calculation. Based on which, bilateral pruning strategies were proposed to reduce calculation field of both attributes and entities, so it need not travel all the attributes and entities. The pruning strategies still work even there is no core. At last, 20 decision sets of UCI, massive and ultra- high dimension were used to verify the strategies and algorithms. The results show that the algorithm is effective and efficient, and in most conditions, the algorithm of this paper is superior to the current algorithms, and fit for massive de- cision table especially. The algorithm can be the basis of new reduction and optimization algorithms.