粗等价类双边剪枝策略下多次Hash的约简算法

摘要：

提出一种新的约简算法。首先以全局等价类为最小计算粒度，提出粗等价类概念，深入研究其性质并证明粗等价类下求核和约简与原决策系统等价；剖析3类粗等价类与正区域间的内在关联，设计针对1和?1两类粗等价类双边删减下正区域的渐增式等价计算方法，从而设计双向剪枝策略以及多次Hash的属性增量划分算法，基于此给出高效完备的约简算法。最后用UCI中20个决策集、海量、超高维3类数据集从多个角度进行验证，结果表明，所提出的约简算法的完备性和高效性在绝大多数情况下优于现有算法，尤其适用于海量数据和超高维数据集。

关键词：粗糙约简、粗等价类、Hash、双边剪枝

所属期刊栏目：31

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金项目71401045；教育部人文社会科学基金项目12YJCZH129

在线出版日期：2016-11-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：1921-1935