决策表分解及其最小属性约简研究

现有的很多属性约简算法都是由构造决策表的差别矩阵出发,将矩阵中非空元素的合取范式转化为极小析取范式。为提高对大规模数据的决策表进行约简的效率,文中指出基于U/{a}划分的最小约简算法存在的缺陷,给出以划分粒度为启发式信息,利用单个条件属性把论域划分成多个等价类,将计算整个全域上的属性约简问题转化为计算在相应划分的子区域上属性约简问题,提出了一种基于决策表分解的最小属性约简算法。理论分析和实例表明该约简算法是有效的。

Decomposition of decision table and computation for minimum attribute reduction

Many existing algorithms of attribute reduction begin at constructing decision table’s discernibility matrix，then convert non-empty objects’ conjunctive normal form into minimal disjunctive normal form.It is important how to get a reduction more efficiently.This paper points out that the minimum attribute reduction algorithm is imperfect in some respect，and an improved algorithm for the minimum attribute reduction based on U/{a} partition is proposed.By regarding the significance of attributes defined from the viewpoint of partition granularity as heuristic information，and introducing the heuristic information into U/{a} partition which translates attribute reduction problem in macrocosm into attribute reduction problem in subdomain.Theoretical analysis and example show that this algorithm is effective.