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

来源期刊：控制与决策2016年第11期

论文作者：赵洁 张恺航 董振宁

文章页码：1921 - 1935

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

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